GraphSAGE: Inductive Learning on Large Graphs
Published:
The Inductive vs. Transductive Distinction
Transductive GNNs (GCN, GAT): as originally formulated, these operate on one fixed graph: the layer is a product with a normalised adjacency \(\hat{A}\) built from the whole training graph. Add a new node tomorrow and \(\hat{A}\) changes, so at minimum you must rebuild it and re-run a full-graph forward pass.
Inductive GNNs (GraphSAGE): learn a function that maps a node’s local neighbourhood to an embedding. Apply this function to any neighbourhood, seen or unseen, to get an embedding.
This matters enormously in practice:
- Pinterest uses GraphSAGE to embed new pins (items) in real-time as users upload them.
- Social networks onboard new users continuously, their profiles must be embedded immediately.
The Algorithm
For each node \(v\) at each layer \(k = 1, \dots, K\):
Where:
- \(K\), the number of layers, equivalently the number of hops each node sees.
- \(S\), the fixed neighbourhood sample size, a hyperparameter. Note that \(\mathcal{S}_v\) always has exactly \(S\) elements: when \(\lvert \mathcal{N}(v) \rvert < S\) the sample is drawn with replacement, which is what keeps the per-node cost constant.
- \(\Vert\), concatenation, so \(W^{(k)}\) has twice as many input columns as \(h\) has dimensions.
- \(\lVert \cdot \rVert_2\), the Euclidean norm; step 4 projects every embedding onto the unit sphere.
The key novelty is step 3: concatenate the node’s own previous representation with the aggregated neighbourhood representation, then apply a shared learned \(W^{(k)}\). This ensures the node retains its own identity while incorporating neighbour information, and because \(W^{(k)}\) does not depend on which node it is applied to, the same layer works for a node that was never seen during training.
Concrete Example: Embedding a New Node at Inference Time
Suppose we trained GraphSAGE on a product graph. A new product \(P\) is uploaded tonight with features \(h_P = [0.8,\, 0.3,\, 0.1]\) and two existing, similar products as neighbours: \(h_{n_1} = [0.7,\, 0.4,\, 0.2]\) and \(h_{n_2} = [0.6,\, 0.5,\, 0.1]\).
Without retraining, with one layer and sample size \(S = 2\):
The resulting embedding places \(P\) in the correct region of the embedding space relative to existing products, ready for recommendation, all without touching the training set.
Aggregator Choices
GraphSAGE proposes three aggregators (all operating on the sampled set \(\mathcal{S}_v\)):
| Aggregator | Formula | Properties |
|---|---|---|
| Mean | \(\frac{1}{\lvert \mathcal{S}_v \rvert}\sum_{u \in \mathcal{S}_v} h_u\) | Fast, size-invariant, closest to GCN |
| Max-pooling | \(\max_{u \in \mathcal{S}_v} \sigma(W_{\text{pool}} h_u + b)\), elementwise | Captures extreme features |
| LSTM | LSTM applied to a random ordering of \(\mathcal{S}_v\) | Highest capacity, not permutation-invariant |
The LSTM aggregator violates permutation invariance (an LSTM cares about input order), GraphSAGE handles this by applying it to a random permutation of the neighbours, which empirically works well but gives no invariance guarantee.
Because mean and max are not injective over multisets, none of these aggregators reaches the 1-WL expressiveness bound; the GIN post explains why sum is required for that.
Mini-Batch Training
Because GraphSAGE uses neighbourhood sampling, it supports mini-batch training on arbitrarily large graphs:
- Sample a batch of target nodes.
- Sample their \(K\)-hop neighbourhoods, expanding the computation graph outwards, with a fixed sample size \(S\) per hop, this costs \(O(S^K)\) nodes per target instead of the whole graph.
- Compute embeddings bottom-up: 0-hop → 1-hop → … → target nodes.
- Update the \(W^{(k)}\) via backprop.
Pinterest’s PinSage builds on exactly this idea to scale to a graph with billions of nodes and edges.
✅ Key Takeaways
- GraphSAGE is inductive: it learns an aggregation function \(\operatorname{AGGREGATE}_k\) and shared weights \(W^{(k)}\), not per-node embeddings, so it generalises to nodes never seen in training.
- Neighbourhood sampling of a fixed \(S\) neighbours per node bounds the cost of a \(K\)-layer forward pass at \(O(S^K)\) nodes, which is what enables mini-batch training on billion-scale graphs.
- Concatenates own representation with the aggregated neighbourhood before the linear transform, preserving node identity, then L2-normalises.
- The same idea underpins production systems such as Pinterest's PinSage for real-time item embedding.