GraphSAGE

GraphSAGE learns shared aggregators, not per-node vectors, so it embeds unseen nodes: each layer samples a fixed number of neighbours (25, then 10), aggregates them by mean, LSTM or max-pool, concatenates the node's own vector and applies W.

8 min read688 wordscore0 viewsupdated 2026-10-21

Definition

GraphSAGE (SAmple and aggreGatE) is an inductive message-passing GNN. Each layer samples a fixed-size set of a node's neighbours, aggregates their vectors with a learned, permutation-invariant function, and combines the result with the node's own vector. Introduced by William L. Hamilton, Rex Ying and Jure Leskovec, "Inductive Representation Learning on Large Graphs" (NeurIPS 2017).

The task is to map each node of a graph to a vector zvz_v that a classifier or a link scorer can use (see Node classification and Link prediction). Shallow methods such as DeepWalk and node2vec learn one free vector per node (see Graph representation learning). They are transductive: a node added after training has no vector until the whole optimisation is rerun. A spectral Graph Convolutional Network (GCN) in its original form is trained full-batch on one fixed graph, with the normalised adjacency of the whole graph in memory.

GraphSAGE is inductive. It learns KK weight matrices and aggregators, not node vectors. Any node with features and neighbours, in the training graph or in a new graph, gets an embedding by running the same KK layers on its local neighbourhood. The aggregator must not depend on neighbour order, because neighbours have no natural order.

Sample, aggregate, combine

hN(v)k=AGG⁡k({huk−1:u∈Sk(v)})hvk=σ(Wk [ hvk−1 ∥ hN(v)k ]),hvk←hvk/∥hvk∥2\begin{aligned}h^{k}_{\mathcal N(v)}&=\operatorname{AGG}_k\big(\{h^{k-1}_u : u\in\mathcal S_k(v)\}\big)\\ h^{k}_v&=\sigma\big(W^{k}\,[\,h^{k-1}_v\,\Vert\,h^{k}_{\mathcal N(v)}\,]\big),\qquad h^{k}_v\leftarrow h^{k}_v/\lVert h^{k}_v\rVert_2\end{aligned}
hv0=xvh^0_v=x_v
input node features; after K layers, z_v = h^K_v
Sk(v)\mathcal S_k(v)
a uniform sample of SkS_k neighbours of vv, redrawn every minibatch (with replacement if the degree is below SkS_k)
[⋅∥⋅][\cdot\Vert\cdot]
concatenation: the node's own vector is kept separate from the neighbourhood summary, a skip connection
WkW^k
shared weight matrix of layer kk, shape dk×2dk−1d_k\times 2d_{k-1}; σ\sigma is ReLU
1 · sample S1 = 3, S2 = 22 · compute bottom-up on the sampled tree (K = 2)ABCDEFGHIJKLMhop 1 · hop 2 · dashed: unsampledk = 0: input features xGHBIJCKLDABCDk = 1k = 2: outputz_A = h²_Apaper: S1 = 25, S2 = 10 → ≤ 276 nodes per target(1 + 25 + 250), whatever the degree; Reddit avg 4923 · one GraphSAGE layer k (same W^k for every node, so it applies to unseen nodes)h^(k−1)_uu ∈ S_k(v)AGG_kmean/LSTM/poolCONCAT[h_v ‖ h_N(v)]W^k, σ2d → d÷ ‖·‖₂unit lengthh^k_vto layer k + 1mean: (1/|S|) Σ h_u · GCN: mean over S ∪ {v}, no concat · LSTM: over a random order of Spool: max_u σ(W_pool h_u + b), elementwise · output z_v = h^K_v feeds a softmax or theunsupervised random-walk loss with negative samples
fig.GraphSAGE with K = 2 on a toy graph. Target A has 5 neighbours; with S1 = 3 it samples B, C and D, and each of those samples S2 = 2 of its own neighbours. The sampled nodes form a computation tree. Layer 1 builds h¹ for A, B, C and D from raw features, and layer 2 combines them into z_A. Each layer is aggregate, concatenate with self, multiply by W^k, ReLU and normalise. With the paper's S1 = 25 and S2 = 10, one target needs at most 1 + 25 + 250 = 276 nodes, however large its true 2-hop neighbourhood.

Aggregators. The paper compares four. Mean: the elementwise mean of the sampled huh_u. GCN: the mean over S(v)∪{v}\mathcal S(v)\cup\{v\}, followed by WW and σ\sigma with no concatenation; this is an inductive form of the GCN layer. LSTM: a Long short-term memory (LSTM) network run over the neighbours. It is not permutation-invariant, so it is applied to a random permutation. Pooling: each neighbour goes through a one-layer MLP, then an elementwise max.

AGG⁡kpool=max⁡u∈Sk(v)σ(Wpool huk−1+b)J(zu)=−log⁡σ(zu⊤zv)−Q Evn∼Pnlog⁡σ(−zu⊤zvn)\operatorname{AGG}^{\text{pool}}_k=\max_{u\in\mathcal S_k(v)}\sigma\big(W_{\text{pool}}\,h^{k-1}_u+b\big)\qquad\qquad J(z_u)=-\log\sigma(z_u^{\top}z_v)-Q\,\mathbb E_{v_n\sim P_n}\log\sigma(-z_u^{\top}z_{v_n})
max⁡\max
elementwise max over the transformed neighbours: each output dimension reports its strongest neighbour
J(zu)J(z_u)
unsupervised loss: vv co-occurs with uu on a short random walk, vnv_n are QQ negative samples from PnP_n, as in Word2Vec

With labels, the final zvz_v instead goes to a softmax or sigmoid layer trained with cross-entropy. The cost per target is O(∏kSk)O(\prod_k S_k), independent of the graph's size or degree, because minibatches are built from samples only.

Minibatch forward pass (Algorithm 2 of the paper)

  1. 1Start from the batch's target nodes: BK\mathcal B^K.
  2. 2Sample backwards: for k=K,…,1k=K,\dots,1, set Bk−1=Bk∪⋃v∈BkSk(v)\mathcal B^{k-1}=\mathcal B^k\cup\bigcup_{v\in\mathcal B^k}\mathcal S_k(v). B0\mathcal B^0 holds every node whose raw features are needed.
  3. 3Compute forwards: for k=1,…,Kk=1,\dots,K, compute hvkh^k_v for v∈Bkv\in\mathcal B^k only, from hk−1h^{k-1} of vv and its samples.
  4. 4Output zv=hvKz_v=h^K_v for the targets, apply the loss, backpropagate into W1,…,WKW^1,\dots,W^K and the aggregator weights.

Paper setting (Hamilton et al., 2017)

Depth and fan-out
K = 2, S1 = 25, S2 = 10. K = 2 beat K = 1 by roughly 10–15 %; K = 3 added at most a few percent at 10–100× the runtime
Reddit
232,965 posts from September 2014, linked when the same user commented on both; average degree 492. Features: 300-d GloVe vectors of the title and comments plus post statistics (602-d in the released data). Train on the first 20 days, test on later posts
PPI
24 protein–protein interaction graphs (one per human tissue): 20 for training, 2 for validation, 2 for testing, so test graphs are entirely unseen. 121 multi-label targets, about 2,373 nodes per graph
Supervised micro-F1
GraphSAGE-LSTM: 0.954 on Reddit, 0.612 on PPI. The LSTM and pooling aggregators beat mean and GCN; pooling was about as accurate as LSTM and faster
Later
the Graph Attention Network (GAT) paper reported 0.973 micro-F1 on PPI. PinSage (Ying et al., 2018) scaled the GraphSAGE recipe to Pinterest's graph of 3 billion nodes and 18 billion edges, with neighbourhoods chosen by random-walk visit counts

Fan-out against cost

Without sampling, KK layers on a node of degree dd touch about dKd^K nodes. On Reddit that is 4922≈242,000492^2\approx242{,}000 per target for K=2K=2, close to the whole graph. Sampling caps it at S1+S1S2=275S_1+S_1S_2=275 edges. The price is variance: the sampled mean is an unbiased but noisy estimate of the full neighbourhood mean, and the noise shrinks as SS grows.

target 0 (class 0, deg 11) · fan-out S1 = 5, S2 = 3 · tree edges 20 of 105node colour = input feature x (+ / −) · ring: target · hop-1 sample · hop-2 sample · click a nodeclass 0: x = −0.5 + noiseclass 1: x = +0.5 + noisesweep S1 = S2 = S, 5 seeds0.50.70.91612accuracybars: edges/nodeh²(target) sampled -0.405 vs full -0.433 · 15 distinct nodes touchedall 48 nodes, sign(h²): accuracy 83.3% (full 85.4%, raw x 64.6%)mean |h² − h²full| = 0.103 · edges per node 19.1 vs full 65.2layer: h^k = ½ h^(k−1)_self + ½ mean(sampled neighbours), i.e. W = [½ I, ½ I] on the concatenation
sampling seed 1
fig.A 48-node two-community graph (174 edges, 12 between communities, degrees 2–11). Each node's scalar feature is ±0.5 plus N(0, 1) noise, so sign(x) alone classifies 64.6 % correctly. Neighbours are sampled without replacement, as PyG does. Two mean layers h^k = ½ h^(k−1) + ½ mean(sampled neighbours) average the noise away. At the default S1 = 5, S2 = 3, target 0 (degree 11) uses 20 of its 105 tree edges, and its sampled h² = −0.405 against −0.433 with full neighbourhoods. Over all nodes, sign(h²) is right 83.3 % of the time (full neighbourhoods: 85.4 %) at 19.1 edges per node instead of 65.2. With S1 = S2 = 1 it falls to 60.4 %, worse than the raw feature. The sweep (5 seeds) climbs from 66.7 % at S = 1 to 77.9 % at S = 3 and 85.4 % once S reaches the maximum degree.

Worked example

nodeneighbours usedh_N (mean)W·[x_v ‖ h_N]ReLUh¹ (unit length)
AB, C, D(0.333, 1.333)(1.333, −1.333)(1.333, 0)(1, 0)
BA, C(1, 0.5)(1, 0.5)(1, 0.5)(0.894, 0.447)
CA, B(0.5, 0.5)(1.5, 0.5)(1.5, 0.5)(0.949, 0.316)
DA, E(1.5, 0)(1.5, 2)(1.5, 2)(0.6, 0.8)
ED(0, 2)(2, −2)(2, 0)(1, 0)
A, sampled S = 2B, D(0, 1.5)(1, −1.5)(1, 0)(1, 0)
new node F, x = (1, 2)B, E(1, 0.5)(2, 1.5)(2, 1.5)(0.8, 0.6)
Worked example: one mean-aggregator layer on the graph A–B, A–C, A–D, B–C, D–E with features A (1, 0), B (0, 1), C (1, 1), D (0, 2), E (2, 0) and W = [[1, 0, 1, 0], [0, 1, 0, −1]], so W·[x_v ‖ h_N] = (x₁ + h₁, x₂ − h₂) (computed with numpy)

The last row is the inductive step. F joins the graph after training, attached to B and E, and gets an embedding from the same WW with no retraining. The sampled row for A shows the cost of sampling: a different sample, {B,C}\{B,C\}, would give hN=(0.5,1)h_{\mathcal N}=(0.5,1) and a different pre-activation (1.5,−1)(1.5,-1). Here ReLU and normalisation hide the difference.

python
1import torch, torch.nn.functional as F
2from torch_geometric.datasets import Reddit
3from torch_geometric.loader import NeighborLoader
4from torch_geometric.nn import SAGEConv
5
6data = Reddit("data/Reddit")[0] # 232,965 nodes, 602 features, 41 classes
7loader = NeighborLoader(data, num_neighbors=[25, 10], # S1, S2 as in the paper
8 batch_size=512, input_nodes=data.train_mask, shuffle=True)
9
10class SAGE(torch.nn.Module):
11 def __init__(self, d_in, d_h, d_out):
12 super().__init__()
13 self.c1 = SAGEConv(d_in, d_h, aggr="mean")
14 self.c2 = SAGEConv(d_h, d_out, aggr="mean")
15 def forward(self, x, edge_index):
16 x = F.relu(self.c1(x, edge_index))
17 x = F.dropout(x, p=0.5, training=self.training)
18 return self.c2(x, edge_index)
19
20model = SAGE(data.num_features, 256, 41)
21opt = torch.optim.Adam(model.parameters(), lr=0.01)
22model.train()
23for batch in loader: # one sampled 2-hop subgraph per batch
24 opt.zero_grad()
25 out = model(batch.x, batch.edge_index)[:batch.batch_size] # target nodes come first
26 loss = F.cross_entropy(out, batch.y[:batch.batch_size])
27 loss.backward()
28 opt.step()
Two-layer GraphSAGE on Reddit with sampled minibatches in PyTorch Geometric (not run here). PyG's SAGEConv computes W₁x_v + W₂·mean(x_u), which equals W·[x_v ‖ mean] with W = [W₁ W₂]; normalize=False by default

Use when

  • +Inductive: embeds new nodes and whole new graphs (PPI test graphs) without retraining
  • +Cost per target is bounded by the product of fan-outs, independent of graph size, so minibatch training scales to very large graphs
  • +Concatenating self and neighbours keeps the node's own signal

Avoid when

  • −Sampling adds variance; small fan-outs lose accuracy
  • −The computation tree still grows exponentially with depth, so K stays at 2–3
  • −Mean and max aggregators cannot tell some neighbourhoods apart (see Graph Isomorphism Network (GIN)); the LSTM aggregator is not permutation-invariant

Check yourself

A 3-layer GraphSAGE uses fan-outs S1 = 10, S2 = 5, S3 = 5. At most how many nodes does the computation tree of one target contain?

Check yourself

Why can GraphSAGE embed a node that was added after training, while DeepWalk cannot?

Remember

  • ✓Layer: hvk=σ(Wk[hvk−1∥AGG⁡({huk−1}u∈S(v))])h^k_v=\sigma(W^k[h^{k-1}_v\Vert\operatorname{AGG}(\{h^{k-1}_u\}_{u\in\mathcal S(v)})]), then L2-normalise.
  • ✓Aggregators: mean, GCN (no concatenation), LSTM on a random permutation, max-pool after a one-layer MLP.
  • ✓Uniform neighbour sampling, K=2K=2, S1=25S_1=25, S2=10S_2=10: at most 276 nodes per target, whatever the degree.
  • ✓Inductive: the parameters are shared functions, so unseen nodes and graphs (the PPI test graphs) are embedded without retraining.
  • ✓Supervised micro-F1: 0.954 on Reddit and 0.612 on PPI with the LSTM aggregator.
← back to Deep Learning roadmap