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.