Message
passing.

Rung 1, so the comparison is against the two architectures that dominate the rest of this site. A convolution assumes a grid: every pixel has the same number of neighbours, in fixed relative positions. A transformer assumes a sequence, or at least a set whose elements can be given positions. A graph offers neither — a node may have two neighbours or two thousand, there is no "left" neighbour, and relabelling the nodes must not change the answer.

The change is to define the layer in terms of the only structure that survives those constraints: each node updates itself from an order-independent aggregate of its neighbours. One layer mixes a node's own features with a pooled summary of the features one hop away and applies a learned transform. Stack k layers and each node's representation depends on everything within k hops, which is the graph analogue of a receptive field.

The specific choices in this rung's layer are where the content is, and both are corrections to the naive version. Aggregating over neighbours alone loses the node itself, so self-loops are added to the adjacency before aggregating. And summing over neighbours means a node with a thousand edges produces activations orders of magnitude larger than a node with two, so the adjacency is normalised by degree symmetrically — each edge's contribution is scaled down by the degrees at both of its ends, which keeps the scale of the representation comparable across a graph with wildly uneven connectivity.

Convolutional networks exploit the grid of an image; recurrent nets and Transformers exploit the order of a sequence. But an enormous amount of real data has neither. A molecule is atoms joined by bonds; a citation network is papers linked by references; a social graph is people connected by follows. These are graphs — sets of nodes joined by edges — and they have no canonical ordering and no fixed neighborhood size. There's nothing for a convolution to slide over.

A graph neural network learns on this structure directly. The Graph Convolutional Network (Kipf & Welling, 2017) is the canonical, minimal form. Its promise: give each node a feature vector and a list of neighbors, and it produces a new feature vector per node that blends in information from the neighborhood — useful for classifying nodes, predicting missing edges, or scoring an entire graph. The whole thing reduces to one operation applied over and over: a node updates itself from its neighbors.

The engine of every GNN is message passing. In one layer, each node gathers messages from its neighbors, aggregates them into a single summary, and combines that with its own current feature to produce a new one. For a GCN the aggregation is a normalized weighted sum; other GNNs use a max, a mean, or an attention-weighted sum, but the shape is always the same: gather, aggregate, update.

Because every node runs the same shared function, the network handles graphs of any size and any connectivity — a property images and sequences don't demand. And depth buys reach:

Stacking layers grows the receptive field one hop at a time. But there's a tension: go too deep and repeated averaging causes over-smoothing, where every node's feature converges to nearly the same value and the network loses its ability to tell nodes apart. Most GCNs are shallow — two or three layers — for exactly this reason.

Two details separate a naive "sum my neighbors" from a GCN layer that actually trains, and both live inside the normalized adjacency Â:

The self-loops matter because without A + I a node's new feature would be built only from its neighbors, discarding what it already knew. The symmetric normalization matters because raw neighbor-sums are dominated by high-degree hubs — a node with 1,000 neighbors would accumulate a huge vector and drown out low-degree nodes, and repeated layers would make magnitudes explode or vanish. Dividing each edge weight by √(dᵢ·dⱼ) turns every aggregation into a stable, degree-balanced average that behaves well no matter the graph's structure. That single normalized matrix is the whole trick.

One layer of a Graph Convolutional Network is a single line:

H⁽ˡ⁾ is the node-feature matrix at layer l;  mixes each node with its neighbors (normalized); W⁽ˡ⁾ is the learned weight; σ is a nonlinearity (ReLU). ·H is the message passing; ·W and σ are an ordinary neural layer on top.

Read right to left, it does exactly three things:  H replaces every node's feature with the degree-normalized average of its neighborhood (the message passing); · W applies a learned linear transformation shared across all nodes; and σ adds a nonlinearity. Stack two of these with a softmax on top and you have a node classifier that, on citation benchmarks, beat far more complicated methods. The runnable version below builds  from a raw adjacency and propagates features one hop — the entire heart of the model in a few lines of plain Python.

Kipf and Welling's paper does two things: it derives a cheap graph convolution from spectral graph theory, and it uses that layer for semi-supervised node classification, where only a few nodes carry labels. The derivation is short enough to follow step by step.

1. Start from a spectral filter. On a graph with adjacency A and degree matrix D, the normalized Laplacian L = I − D^^−1/2AD^^−1/2 has eigendecomposition UΛU^^T. A spectral convolution filters a signal x as U g_θ(Λ) U^^Tx, which needs the eigenvectors: O(N³) to compute and O(N²) per multiplication.
2. Approximate with Chebyshev polynomials. Following Hammond and colleagues and the ChebNet model of Defferrard and colleagues, the filter is truncated to a K-th order polynomial in a rescaled Laplacian. No eigenvectors are needed, the cost is linear in the number of edges, and each filter reaches at most K hops.
3. Keep only first order. Set K = 1 and approximate the largest eigenvalue by 2, trusting the network's parameters to adapt to the scale. The filter becomes θ′₀x − θ′₁D^^−1/2AD^^−1/2x, and depth, not polynomial order, now controls how far information travels.
4. Share one parameter. Setting θ = θ′₀ = −θ′₁ curbs overfitting and gives θ(I + D^^−1/2AD^^−1/2)x.
5. Renormalize. The operator I + D^^−1/2AD^^−1/2 has eigenvalues between 0 and 2, so stacking it can make activations and gradients explode or vanish. The renormalization trick replaces it with D̃^^−1/2ÃD̃^^−1/2, where à = A + I adds self-loops and D̃ is Ã's degree matrix; its eigenvalues are at most 1.
6. Generalize to feature matrices. With C input channels and F filters, a layer computes ÂXΘ with  = D̃^^−1/2ÃD̃^^−1/2. As a sparse-dense product it costs O(|E|FC).
7. Build the classifier. Compute  once, in preprocessing. The model is Z = softmax( ReLU(ÂXW^⁽⁰⁾) W^⁽¹⁾): two layers, so each prediction depends on a node's two-hop neighborhood.
8. Train on the labeled nodes only. The loss is cross-entropy over the labeled nodes, but every node's features flow through Â, which is what makes the method semi-supervised. Training is full-batch gradient descent with Adam: learning rate 0.01, up to 200 epochs, early stopping after 10 epochs without improvement in validation loss, dropout 0.5, L2 regularization of 5 × 10^⁻⁴ on the first layer, 16 hidden units and row-normalized input features.

The evaluation protocol

The citation datasets (Citeseer, Cora, Pubmed) use the split from Yang and colleagues' Planetoid paper: 20 labeled nodes per class for training, 500 nodes for validation and hyperparameter tuning, and 1,000 for testing. Documents are nodes, citations are treated as undirected edges and bag-of-words vectors are the features. NELL, a knowledge-graph dataset, used larger hidden layers and lighter regularization.

Where this sits in message passing

Seen from outside spectral theory, the layer is one round of message passing: each node takes a fixed, degree-normalized weighted sum of its own and its neighbors' transformed features. Later models change the aggregation, with learned attention weights in GAT or a sum followed by an MLP in GIN, and add a pooling readout over nodes when the task is to classify a whole graph.

• Tk — Chebyshev polynomials (T₀ = 1, T₁(x) = x, T_k = 2xT_k−1 − T_k−2); L̃ — the Laplacian rescaled so its eigenvalues lie in [−1, 1].
• θ′k — the filter's coefficients: one per hop in ChebNet, a single shared θ after the simplification.
• Ã, D̃ — adjacency with self-loops and its degree matrix; the result has 1/√(d̃_id̃_j) for each edge and 1/d̃_i on the diagonal.
• Y, Z — one-hot labels and the softmax output; only labeled rows enter the loss.

At the extremes: a large K lets one layer see K hops at the price of more parameters per filter, while K = 1 relies on stacking layers. Without renormalization, ten stacked layers could amplify one component of the signal by up to 2^¹⁰, before weights and nonlinearities; with it, no component grows, since the largest eigenvalue is 1.

The paper compared against label propagation, manifold regularization, semi-supervised embedding, iterative classification, DeepWalk and Planetoid on the three citation graphs and on NELL, using the Planetoid splits described above. Accuracy is on 1,000 test nodes, averaged over 100 runs with random weight initializations.

The GCN also trained quickly, in seconds on the citation graphs and under a minute on NELL, with the whole graph in memory. The more informative experiment compared propagation rules with everything else held fixed:

The renormalized first-order rule beat both the higher-order Chebyshev filters and the unrenormalized first-order variants, so the simplification, once renormalized, cost no accuracy. The MLP row measures what the graph itself contributes: 26 points on Cora. On the negative side, a depth experiment with 1 to 10 layers found the best results at two or three, and without residual connections models deeper than about seven layers became hard to train. Full-batch training also needs the whole graph in memory, which the authors flag as a limit for large graphs.

Two limits are visible in the paper's own setup. It is transductive: the normalised adjacency of the whole graph is part of the computation, so a node that did not exist at training time cannot simply be handed to the model — which is a poor fit for the social and commerce graphs the method is most wanted for. And the networks are shallow, typically two layers, which is the opposite of the pattern everywhere else in deep learning.

The reason for the shallowness turned out to be a real phenomenon rather than a tuning accident. Repeatedly averaging each node with its neighbours is, viewed from far enough away, a diffusion process, and it converges: stack enough layers and every node's representation approaches the same value. Over-smoothing means depth on a graph has a cost that depth on an image does not, and the fixes — residual connections, explicitly keeping the initial features, normalising per node — are patches on it rather than a solution.

How it held up: the frame held and the specific layer did not. GraphSAGE made the method inductive by sampling a fixed-size neighbourhood, so unseen nodes work; attention-based variants replaced the fixed degree normalisation with learned per-edge weights, which is worth noting for a reason beyond graphs — a transformer is exactly that layer on a complete graph, so the attention paper and this one are two points in one design space rather than two fields. Later work also bounded what any message-passing network can distinguish, showing the standard layer cannot tell apart certain non-isomorphic graphs however wide or deep it is, which is an unusually crisp expressiveness limit.

Because so much important data is a graph, GNNs became a standard tool across science and industry. They predict molecular properties for drug discovery, estimate travel times in mapping apps by treating road networks as graphs, catch fraud in transaction networks, power recommendation systems over user–item graphs, and simulate physical systems of interacting particles. Anywhere relationships matter as much as the entities, message passing is the natural model.

There's also a deep connection to the rest of modern AI. Self-attention — the core of the Transformer — is essentially message passing on a fully connected graph, where the attention weights play the role of learned edge strengths. Graph attention networks made that link explicit, and the two families remain mathematically close cousins. Meanwhile the "learn node representations" goal connects back to embedding methods like word2vec (node2vec and DeepWalk borrow its skip-gram idea for graphs). The GCN's clean, degree-normalized layer is still the clearest doorway into all of it — one matrix multiply that taught neural networks to reason over structure.

Work each one out before you open it — a number, a prediction or a reason, not a definition. Producing the answer is what makes it stick. Your progress is kept on this device.

What to do when the data is a graph rather than a line of tokens — message passing, and the protein-folding system built on it.

1. 1Graph Neural Networks2017
2. 2AlphaFold 22021

All 110 papers, in 19 ladders →