Graph Neural Networks, Step by Step

Prelude

What problem do GNNs solve?

Many applied data sources are graphs, not images or sequences. A network of air-quality sensors with shared weather context. A grid of satellite tiles connected by spatial adjacency. A road network with traffic counters at intersections. The natural inductive bias for these is message passing: a node's prediction should depend on itself and its neighbourhood.

The slogan. A GNN is a CNN where the receptive field is set by the graph instead of a square. Each layer is one hop; $K$ layers see a $K$-hop neighbourhood.

Step 1

One layer of message passing

For each node $i$, gather messages from neighbours, aggregate them (sum / mean / max / attention), and combine with the node's own feature through a small MLP. That's the entire recipe. Specific GNNs (GCN, GraphSAGE, GAT, MPNN) differ in how they pick the message function, the aggregator, and the combination.

Step 2

Watch a feature spread

Click any node to set its feature to 1 (and clear the rest). Step through 0, 1, 2, 3 rounds of message passing and watch the value diffuse to the neighbourhood, then to the neighbours-of-neighbours.

aggregation rounds K 2

Click any node to spike its feature. Greens encode the feature value (darker = higher). Edges show the graph; dashed labelled nodes are the 4 supervised seeds for Step 3.

Step 3

Node classification with 4 labels

Add a 2-class structure: 4 of the 14 nodes are labelled (red ring vs blue ring). After $K$ rounds of message passing, a logistic head reads each node's representation and predicts a class. The boundary you see emerging is a graph-aware classifier — neighbours of red seeds tend to be classified red, etc.

The classifier is trained from scratch in your browser at every aggregator change. Crank K up: at K=0 the classifier can only see the 4 labelled nodes' own features and generalises poorly. At K=2 labels propagate to neighbours and the predictions improve. Past K~5 you'll see over-smoothing — every node's representation looks the same and the classifier collapses to majority class. That's a known GNN failure mode (Li et al., 2018).

Step 3 ½

The oversmoothing curve — and why "deeper GNN" usually backfires

A natural instinct for any neural net: stack more layers, get more capacity. For GNNs this fails badly. After a few message-passing rounds, every node's representation becomes a smoothed average of its receptive field; eventually all nodes look the same and the classifier collapses to majority class (Li et al., 2018; Oono & Suzuki, 2020).

Below: the same 14-node graph, three aggregators, K from 0 to 8. Two metrics tracked: node-classifier accuracy on the unlabelled nodes, and feature variance across nodes (the textbook oversmoothing diagnostic). Watch accuracy peak around K=2-3 and then collapse as variance shrinks to ~0.

Solid: classifier accuracy on unlabelled nodes. Dashed: cross-node feature variance (log scale). Three aggregators overlaid.

The fix. Real GNNs ($\le$ 2-3 layers in practice) shouldn't go deep. When you need long-range information, use either residual connections (PairNorm, GCNII), an attention-based aggregator (GAT, GATv2), or a graph transformer with positional encodings. Stacking vanilla GCN past 4 layers almost always hurts.

Step 3¾

Expressivity — the Weisfeiler-Lehman ceiling

A natural question: which graphs can a GNN tell apart? The classical answer (Xu et al., 2019; Morris et al., 2019): a message-passing GNN is at most as expressive as the 1-dimensional Weisfeiler-Lehman graph-isomorphism test (1-WL). That test:

Label every node with its degree (or any consistent feature).
Replace each label with a hash of (own label, multiset of neighbour labels).
Repeat. If two graphs ever produce different label multisets, they're not isomorphic.

1-WL fails on regular graphs with the same degree sequence (e.g. two non-isomorphic 6-cycles). So does any vanilla message-passing GNN. Two ways forward:

GIN (Xu et al., 2019) — provably attains the 1-WL bound with the right aggregator: $h_v = \mathrm{MLP}\bigl((1+\epsilon) h_v + \sum_{u \in \mathcal{N}(v)} h_u\bigr)$. Use this when you suspect graph distinguishability matters.
Higher-order GNNs / k-WL. Aggregate over $k$-tuples of nodes instead of single neighbours. More expressive but $O(N^k)$ cost. PPGN, $k$-GNN.
Subgraph GNNs / positional encodings. Augment each node with structural features (Laplacian eigenvectors, random walk encodings). Cheap and often enough in practice.

Step 3⅞

Scaling to million-node graphs

A full-batch GNN forward pass on a graph with $|V|$ nodes and average degree $d$ touches every edge — $O(|V| d)$ memory and compute. Beyond ~10⁶ nodes that's prohibitive. Three escapes:

Neighbour sampling (GraphSAGE, Hamilton et al., 2017). For each target node, sample a fixed number $S$ of neighbours per layer. Cost becomes $O(B \cdot S^K)$ per batch instead of $O(|V| d)$.
Subgraph sampling (Cluster-GCN, GraphSAINT). Partition or sample subgraphs and train on them; full message passing within, ignoring inter-subgraph edges. Much higher throughput at a small accuracy cost.
Layer-wise sampling (FastGCN, LADIES). Sample nodes per layer independently. Variance-reduction tricks (importance sampling) keep gradient bias low.
Frontier methods (2024+): NeurIPS-era graph transformers with linear-attention; pre-computed positional encodings; GNN distillation into MLP for serving.

Library defaults: PyG and DGL ship all of the above; the practical first try at scale is GraphSAGE with neighbour sampling $S = 25, 10$ for two layers.

Step 4

The variants worth knowing

GCN. Symmetric-normalised mean aggregation. Cheapest, the default first try.
GraphSAGE. Neighborhood sampling + mean / LSTM / pooling aggregator. Scales to large graphs.
GAT. Attention over neighbours. Edge weights become learnable and content-dependent — useful for heterogeneous neighbourhoods.
MPNN. The general framework above; any choice of message and aggregator.
GIN. Provably as expressive as the Weisfeiler-Lehman test — needed when graph isomorphism actually matters.
Graph Transformer. Self-attention over all nodes (with positional / Laplacian encodings). Computationally heavier; helps for global structure.

Step 5

Where GNNs are the right tool

Molecular property prediction. Atoms = nodes, bonds = edges. GNNs (MPNN, SchNet, DimeNet, ChemProp) routinely top MoleculeNet leaderboards; the inductive bias matches chemistry's locality.
Recommender systems. User-item bipartite graph; node embeddings learnt by message passing. PinSage (Pinterest), GraphSAGE-based pipelines power production recommenders.
Traffic forecasting. Road network + traffic counters; spatio-temporal GNNs (DCRNN, STGCN, Graph WaveNet) outperform pure time-series models for citywide forecasting.
Knowledge graphs. Relational GNNs (R-GCN, CompGCN) for link prediction in heterogeneous knowledge bases.
Power-grid / sensor networks. Nodes = sensors/stations; edges = physical connections or spatial proximity. GNNs interpolate missing readings, flag anomalous sensors, propagate alerts.
Social and citation networks. The Cora / Citeseer / Pubmed benchmarks that started the field; still standard baselines.

Final takeaway. If your data has a graph in it, build the GNN before the MLP. The inductive bias is free; the expressive ceiling is higher; and over-smoothing is the only real footgun.

Step 6

Reading list

Kipf & Welling (2017) — Semi-Supervised Classification with Graph Convolutional Networks. The GCN paper.
Hamilton, Ying, Leskovec (2017) — Inductive Representation Learning on Large Graphs. GraphSAGE.
Veličković et al. (2018) — Graph Attention Networks.
Xu, Hu, Leskovec, Jegelka (2019) — How Powerful are Graph Neural Networks? GIN + WL connection.
Li, Han, Wu (2018) — the oversmoothing paper.
Hamilton (2020) — Graph Representation Learning textbook. Free online.
PyG & DGL — the two production libraries. Both ship every model above and the sampling methods.