GraphSAGE: Scalable Inductive Learning

While GCNs are powerful, they have two major flaws: they are Transductive (requiring the entire graph at once) and they don't scale well to massive networks. GraphSAGE (Sample and AggreGatE) was designed by Stanford researchers to solve these exact problems.

---

1. Inductive vs. Transductive

• Transductive (GCN/DeepWalk): The model learns embeddings for a fixed graph. If a new user joins a social network, you have to re-train the model to embed them.
• Inductive (GraphSAGE): The model learns a function that generates embeddings. It learns how to aggregate features from a neighborhood. This means it can embed nodes it has never seen before during training.

The Key Insight: GraphSAGE doesn't learn a vector for node $A$; it learns a recipe for how to build a vector for any node based on its local neighborhood.

---

2. The GraphSAGE Recipe

Instead of using the full adjacency matrix, GraphSAGE follows a three-step process for every node:

Step 1: Neighborhood Sampling

To handle massive graphs, we don't look at all neighbors. We sample a fixed-size set of neighbors (e.g., 5 neighbors). This keeps the computational cost per node constant, regardless of the node's degree.

Step 2: Aggregation

The sampled neighbors' features are passed through an Aggregator Function. The aggregator must be symmetric (invariant to the order of neighbors).

• Mean Aggregator: Simple average of neighbor vectors.
• LSTM Aggregator: Applies an LSTM to a random permutation of neighbors (higher capacity).
• Pooling Aggregator: Passes each neighbor through a fully connected layer followed by an element-wise max or sum.

Step 3: Concatenation & Projection

The aggregated neighborhood vector is concatenated with the node's own features and projected into the next layer's dimension.

$h_v^{(k)} = \sigma \left( W^{(k)} \cdot \text{CONCAT} \left( h_v^{(k-1)}, \text{AGGREGATE} \left( \{h_u^{(k-1)}, \forall u \in \mathcal{N}_{sampled}(v)\} \right) \right) \right)$

---

3. Implementation in PyTorch

A simplified version of the GraphSAGE aggregation step:

graphsage_layer.py

import torch
import torch.nn as nn

class SageLayer(nn.Module):
    def __init__(self, in_features, out_features, aggregator_type='mean'):
        super().__init__()
        self.agg_type = aggregator_type
        self.projection = nn.Linear(in_features * 2, out_features)

    def forward(self, x, neighbors_x):
        # x: [Batch, In_Feats] (Target nodes)
        # neighbors_x: [Batch, Num_Samples, In_Feats] (Sampled neighbors)

        # 1. Aggregate neighbors
        if self.agg_type == 'mean':
            neigh_agg = torch.mean(neighbors_x, dim=1)
        elif self.agg_type == 'max':
            neigh_agg, _ = torch.max(neighbors_x, dim=1)

        # 2. Concatenate with self
        combined = torch.cat([x, neigh_agg], dim=1)

        # 3. Project and Activate
        return torch.relu(self.projection(combined))

---

4. Why GraphSAGE?

Feature	Benefit
Inductive Learning	Generalizes to new nodes and entirely new graphs.
Fixed-size Sampling	Ensures predictable memory usage and runtime.
Feature Integration	Seamlessly combines structural information with node attributes.

Pro Tip: Production GNNs

GraphSAGE is the "workhorse" of industrial GNNs. Companies like Pinterest and Uber use variations of GraphSAGE (e.g., PinSAGE) to recommend content across billions of nodes because of its incredible scalability.