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 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 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 layers on its local neighbourhood. The aggregator must not depend on neighbour order, because neighbours have no natural order.
Sample, aggregate, combine
- input node features; after K layers, z_v = h^K_v
- a uniform sample of neighbours of , redrawn every minibatch (with replacement if the degree is below )
- concatenation: the node's own vector is kept separate from the neighbourhood summary, a skip connection
- shared weight matrix of layer , shape ; is ReLU
Aggregators. The paper compares four. Mean: the elementwise mean of the sampled . GCN: the mean over , followed by and 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.
- elementwise max over the transformed neighbours: each output dimension reports its strongest neighbour
- unsupervised loss: co-occurs with on a short random walk, are negative samples from , as in Word2Vec
With labels, the final instead goes to a softmax or sigmoid layer trained with cross-entropy. The cost per target is , independent of the graph's size or degree, because minibatches are built from samples only.
Minibatch forward pass (Algorithm 2 of the paper)
- 1Start from the batch's target nodes: .
- 2Sample backwards: for , set . holds every node whose raw features are needed.
- 3Compute forwards: for , compute for only, from of and its samples.
- 4Output for the targets, apply the loss, backpropagate into 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
- 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, layers on a node of degree touch about nodes. On Reddit that is per target for , close to the whole graph. Sampling caps it at edges. The price is variance: the sampled mean is an unbiased but noisy estimate of the full neighbourhood mean, and the noise shrinks as grows.
Worked example
| node | neighbours used | h_N (mean) | W·[x_v ‖ h_N] | ReLU | h¹ (unit length) |
|---|---|---|---|---|---|
| A | B, C, D | (0.333, 1.333) | (1.333, −1.333) | (1.333, 0) | (1, 0) |
| B | A, C | (1, 0.5) | (1, 0.5) | (1, 0.5) | (0.894, 0.447) |
| C | A, B | (0.5, 0.5) | (1.5, 0.5) | (1.5, 0.5) | (0.949, 0.316) |
| D | A, E | (1.5, 0) | (1.5, 2) | (1.5, 2) | (0.6, 0.8) |
| E | D | (0, 2) | (2, −2) | (2, 0) | (1, 0) |
| A, sampled S = 2 | B, 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) |
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 with no retraining. The sampled row for A shows the cost of sampling: a different sample, , would give and a different pre-activation . Here ReLU and normalisation hide the difference.
1import torch, torch.nn.functional as F2from torch_geometric.datasets import Reddit3from torch_geometric.loader import NeighborLoader4from torch_geometric.nn import SAGEConv56data = Reddit("data/Reddit")[0] # 232,965 nodes, 602 features, 41 classes7loader = NeighborLoader(data, num_neighbors=[25, 10], # S1, S2 as in the paper8 batch_size=512, input_nodes=data.train_mask, shuffle=True)910class 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)1920model = 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 batch24 opt.zero_grad()25 out = model(batch.x, batch.edge_index)[:batch.batch_size] # target nodes come first26 loss = F.cross_entropy(out, batch.y[:batch.batch_size])27 loss.backward()28 opt.step()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: , then L2-normalise.
- ✓Aggregators: mean, GCN (no concatenation), LSTM on a random permutation, max-pool after a one-layer MLP.
- ✓Uniform neighbour sampling, , , : 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.