BasicGraph Neural Networks

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

NameGraphSAGE
Year introduced2017
ResearchersWilliam L. Hamilton, Rex Ying, Jure Leskovec
InstitutionStanford University
Original paperInductive representation learning on large graphs arXiv
Data typeGraphs
DomainsRecommender systems, Social network analysis, Learning on graph data
Computational costThe cost per node is independent of graph size thanks to sampling: $O(\prod_k S_k)$.
Data sizeVery 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

  1. 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.

Example: On a recommendation platform, a user who joined today gets a representation straight away from the items they interacted with, without retraining the model.

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

ComponentRole
Neighbor samplingA fixed-size sample of neighbours in each layer
AggregatorMean, LSTM or pooling
ConcatenationConcatenating the node's representation with the aggregate of its neighbours
Linear + ReLUShared transformation
L2 normalizationNormalising the representation

Equations

1. GraphSAGE step

$$h_{\mathcal{N}(v)}^{(k)}=\mathrm{AGG}_k\!\left(\{h_u^{(k-1)},\,u\in\mathcal{N}_S(v)\}\right),\quad h_v^{(k)}=\sigma\!\left(W^{(k)}\left[h_v^{(k-1)}\,\|\,h_{\mathcal{N}(v)}^{(k)}\right]\right)$$

Symbols
$\mathcal{N}_S(v)$A sample of v's neighbours
$\mathrm{AGG}_k$Aggregation function
$W^{(k)}$A weight of shape $d^{\prime}\times2d$
Dimensions
$h_v^{(k)}\in\mathbb{R}^{d^{\prime}}$
Numerical example
$h_v=(1,0)$ and the neighbour mean is $(0,2)$ ⇒ the concatenated vector is $(1,0,0,2)$, which is then multiplied by $W$.
Relation to the architecture
Separating the node's representation from its neighbours' helps on heterophilous graphs.

How it works, step by step

  1. A sample of neighbours is taken for each layer.
  2. The neighbours' representations are aggregated.
  3. The result is concatenated with the node's representation.
  4. A linear transformation and activation are applied, then normalisation.
  5. 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

DomainUse
Learning on graph dataClassifying nodes, links and whole graphs.
Recommender systemsRecommender systems that represent users and items as a bipartite graph.
Scientific computingPredicting molecular properties in computational chemistry.
Fraud detectionFraud detection in financial transaction networks.
Social network analysisSocial 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.

Python (PyTorch)
# 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

Related architectures

Basic2017

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 Neural Networks

Intermediate2018

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.

Graph Neural Networks

Advanced2020

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…

Temporal and Sequential NetworksGraph Neural Networks

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

  1. Concept

    What does it mean that GraphSAGE is "inductive"?

  2. Concept

    Why does GraphSAGE take a sample of neighbours?

  3. Mathematical

    What is the result of concatenating $h_v=(1,2)$ with $h_{N(v)}=(3,4)$?

References

  1. 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

    arXivAutomatically verified via OpenAlex/arXiv – 2026-11-20

  2. 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

    arXivAutomatically verified via OpenAlex/arXiv – 2026-11-20