GraphSAGE
An inductive framework that learns aggregation functions over a sampled neighbourhood, so it can compute representations for new nodes the network did not see during training.
Overview
| Name | GraphSAGE |
|---|---|
| Year introduced | 2017 |
| Researchers | William L. Hamilton, Rex Ying, Jure Leskovec |
| Institution | Stanford University |
| Original paper | Inductive representation learning on large graphs arXiv |
| Data type | Graphs |
| Domains | Recommender systems, Social network analysis, Learning on graph data |
| Computational cost | The cost per node is independent of graph size thanks to sampling: $O(\prod_k S_k)$. |
| Data size | Very large graphs (millions of nodes). |
Problem it solves
Transductive methods such as the original GCN and node embeddings (node2vec) need retraining when new nodes appear, and do not scale to huge, changing graphs.
Background and evolution
What came before: Graph Convolutional Network, DeepWalk/node2vec
- 2017
It was introduced at NeurIPS 2017 and tested on citation networks, Reddit and protein interactions. [ref]
Core idea
Instead of learning a representation for each node, the model learns a function: it takes a fixed-size sample of neighbours, aggregates their representations (mean, LSTM or max-pooling), then concatenates the result with the node's own representation and applies a linear transformation.
Interactive diagram
A simplified illustrative diagram with the dimensions of a small example, not a drawing matching every detail of the original implementation. Click any layer to see its role, dimensions and mathematical operation.
Select a layer in the diagram.
Components
| Component | Role |
|---|---|
| Neighbor sampling | A fixed-size sample of neighbours in each layer |
| Aggregator | Mean, LSTM or pooling |
| Concatenation | Concatenating the node's representation with the aggregate of its neighbours |
| Linear + ReLU | Shared transformation |
| L2 normalization | Normalising the representation |
Equations
1. GraphSAGE step
| $\mathcal{N}_S(v)$ | A sample of v's neighbours |
| $\mathrm{AGG}_k$ | Aggregation function |
| $W^{(k)}$ | A weight of shape $d^{\prime}\times2d$ |
How it works, step by step
- A sample of neighbours is taken for each layer.
- The neighbours' representations are aggregated.
- The result is concatenated with the node's representation.
- A linear transformation and activation are applied, then normalisation.
- The layers repeat K times.
Strengths and limitations
Strengths
- Inductive: generalises to new nodes and graphs.
- Scales to huge graphs by training on small batches.
Limitations
- Sampling adds variance to the results.
- Mean aggregation loses information about the number of neighbours.
When to use it, and when not?
Good for
- Large, changing graphs with new nodes arriving all the time.
- Recommender systems.
Not suited for
- Small, fixed graphs where a simpler GCN is enough.
Applications
| Domain | Use |
|---|---|
| Learning on graph data | Classifying nodes, links and whole graphs. |
| Recommender systems | Recommender systems that represent users and items as a bipartite graph. |
| Scientific computing | Predicting molecular properties in computational chemistry. |
| Fraud detection | Fraud detection in financial transaction networks. |
| Social network analysis | Social network analysis and community detection. |
PyTorch code
A simplified teaching code sample that runs on small synthetic data, covering: imports, model definition, data, forward pass, loss, optimizer, training loop, evaluation and inference. It is not the paper's full implementation.
# GraphSAGE (mean aggregation and neighbour sampling)
# A simplified educational example in PyTorch (not the paper's full original implementation): small synthetic data,
# runs on the CPU in seconds. The numbers it prints belong to this example only.
# 1) Import the libraries
import torch
import torch.nn as nn
import torch.nn.functional as F
torch.manual_seed(0)
# 2) Define the model
class SAGELayer(nn.Module):
def __init__(self, d_in, d_out, S=5):
super().__init__()
self.W, self.S = nn.Linear(2 * d_in, d_out), S
def forward(self, h, nbrs): # nbrs: list of each node's neighbours
agg = []
for lst in nbrs:
if len(lst) == 0: agg.append(torch.zeros(h.shape[1])); continue
pick = lst[torch.randint(len(lst), (self.S,))] if self.training else lst # a sample during training
agg.append(h[pick].mean(0))
out = self.W(torch.cat([h, torch.stack(agg)], 1)) # [h_v ‖ mean(h_u)]
return F.normalize(out, dim=1)
class GraphSAGE(nn.Module):
def __init__(self, d_in, d=32, n_classes=3):
super().__init__()
self.l1, self.l2, self.out = SAGELayer(d_in, d), SAGELayer(d, d), nn.Linear(d, n_classes)
def forward(self, X, nbrs):
h = F.relu(self.l1(X, nbrs))
return self.out(F.relu(self.l2(h, nbrs)))
# 3) Prepare the data
# A synthetic graph from a stochastic block model (SBM): 3 communities, more links inside than between
N, C, D = 150, 3, 8
y = torch.arange(N) % C
P = torch.where(y[:, None] == y[None, :], 0.12, 0.01)
A = (torch.rand(N, N) < P).float().triu(1); A = A + A.T # a symmetric adjacency matrix without loops
X = torch.randn(N, D) + 0.6 * F.one_hot(y, D).float() # weak-signal features; the structure helps
idx = torch.randperm(N); train_idx, test_idx = idx[:45], idx[45:] # only 30% labelled (semi-supervised)
nbrs = [A[i].nonzero().flatten() for i in range(N)]
model = GraphSAGE(D)
# 4) Loss function and optimizer
loss_fn = nn.CrossEntropyLoss()
opt = torch.optim.Adam(model.parameters(), lr=1e-2, weight_decay=5e-4)
# 5) Training loop (full-batch: the whole graph at each step, with the loss on the labelled nodes only)
for epoch in range(60):
model.train()
out = model(X, nbrs) # forward pass for all nodes
loss = loss_fn(out[train_idx], y[train_idx])
opt.zero_grad(); loss.backward(); opt.step()
if epoch % 15 == 0:
print(f"epoch {epoch:3d} loss={loss.item():.4f}")
# 6) Evaluation on the unlabelled nodes
model.eval()
with torch.no_grad():
pred = model(X, nbrs).argmax(1)
print(f"test accuracy = {(pred[test_idx] == y[test_idx]).float().mean().item():.3f}")
# 7) Inference: the class of node 0
print("node 0 predicted community:", pred[0].item(), " true:", y[0].item())
This code was run on 2026-11-20 in 3.4 seconds (PyTorch (CPU), Python 3 – local build machine).
Sample output:
test accuracy = 0.657
Trainable parameters in the example: model = 2,723.
These results are for small synthetic data and few epochs, and only prove that the code runs; do not compare them with published results.
Try it and go deeper
- Graph Network Explorer
- AI Model Atlas Another section of the site
- Graph Neural Networks Lab Another section of the site
Related architectures
Graph Convolutional Network
Graph Convolutional Network (GCN)
A simple graph layer that takes a normalised average of the representations of a node and its neighbours and then applies a shared linear transformation; it is a first-o…
Graph Attention Network
Graph Attention Network (GAT)
It replaces GCN's fixed weights with learned attention coefficients for each edge, so each node decides how important each neighbour is, with multiple attention heads.
Temporal Graph Networks
Temporal Graph Networks (TGN)
A framework for learning representations on dynamic graphs represented as a stream of timed events, using a memory for each node that is updated by events and an embeddi…
No results match the filters.
Research ideas
- Study the effect of the sample size S on prediction variance and inference time in a real recommender system.
Starting suggestions, not confirmed research gaps; review the recent literature before adopting them.
Test your understanding
What does it mean that GraphSAGE is "inductive"?
Why? It learns an aggregation function, not a fixed embedding table.
Why does GraphSAGE take a sample of neighbours?
Why? High-degree nodes may have thousands of neighbours.
What is the result of concatenating $h_v=(1,2)$ with $h_{N(v)}=(3,4)$?
Why? Concatenation places the two vectors one after the other.
References
Hamilton, W. L., Ying, R., & Leskovec, J. (2017). Inductive representation learning on large graphs. Advances in Neural Information Processing Systems (NeurIPS) 30. https://arxiv.org/abs/1706.02216
Kipf, T. N., & Welling, M. (2017). Semi-supervised classification with graph convolutional networks. International Conference on Learning Representations (ICLR). https://arxiv.org/abs/1609.02907
