Graph Neural Networks: Learning by Passing Messages Along Edges
A graph neural network is a stack of layers, each of which rewrites every node's representation from that node's current features and an order-invariant summary of its neighbours' features. Graph data arrives as a set of nodes, a set of edges, and a feature vector per node — with no canonical ordering of the nodes. That missing ordering is the whole design problem: the question this note answers is what a layer is allowed to look like when the index a node happens to carry means nothing, and what that restriction costs in the end.
The running example is a small citation graph: nodes are papers, edges are citations, and each paper belongs to one of two research communities. Everything below — the relabelling demo, the message-passing walkthrough, the normalisation heatmap, the over-smoothing slider, and the trained classifier — reads from that graph.
🕸️ The data has no rows
A graph is a pair G = (V, E). Attach a feature vector to each node and stack them into a matrix X ∈ ℝN×d, and record the edges in an adjacency matrix A ∈ {0,1}N×N with Auv = 1 when u and v are joined. Both matrices need node indices to exist — and those indices were invented by whoever serialised the graph. Renumbering the papers is not a different dataset.
Write the renumbering as a permutation matrix P. Applying it moves the rows of X and both the rows and columns of A. A layer f is permutation equivariant when relabelling the input relabels the output the same way and changes nothing else:
This is a constraint on the function, not a property to be learned. A multilayer perceptron applied to the flattened adjacency matrix does not satisfy it: its weights are indexed by position, so moving an edge from cell (2,7) to cell (5,3) sends the input somewhere else in the weight space entirely. Every architecture in this note is built to satisfy it by construction — which is why each one turns out to be some form of "collect from the neighbours, then update".
The marked paper keeps its output through every relabelling: the equivariant layer reads only the neighbourhood, and the neighbourhood is a property of the graph. The dense readout over vec(A) — a fixed set of weights, one per matrix cell — moves every time, because it was never reading the graph in the first place.
📨 One layer is one round of messages
Equivariance leaves one natural template, formalised by Gilmer et al. as the message passing neural network. Each node sends a message to each neighbour, every node aggregates the messages it received with a function that ignores their order, and the aggregate is combined with the node's own state:
The doubled braces are deliberate: the thing being aggregated is a multiset. Two neighbours carrying identical features are two separate elements, and any aggregator that forgets this forgets something real about the graph — §4 is about exactly that. AGGREGATE must be order-invariant, because the neighbours arrive in whatever order the edge list happened to store them; UPDATE is applied to every node with the same parameters, which is what makes the whole layer equivariant rather than merely invariant.
One layer moves information one hop. After k layers a node's representation is a function of everything within k hops of it — its receptive field — and of nothing outside it. Depth in a GNN buys reach, in exactly the way depth in a CNN buys a larger patch.
The scalars shown are the simplest possible instance — AGGREGATE is a mean and UPDATE is the identity, so each round replaces every value with the average over its closed neighbourhood. Watch two things: how fast the selected node's shell swallows the graph, and how fast the numbers stop differing from each other. Both are consequences of the same operator, and §5 is about the second one.
🧮 The GCN layer
Kipf & Welling's graph convolutional network picks the cheapest members of that template: the message is the neighbour's feature vector scaled by a fixed coefficient, AGGREGATE is a sum, and UPDATE is a shared linear map followed by a pointwise nonlinearity. The whole layer is one sparse matrix product.
Two design choices are hiding in there, and both matter more than the matrix notation suggests.
Self-loops. Plain A excludes v from its own neighbourhood, so a layer would throw away the node's current features and keep only the neighbours' — after two such layers a node's own input has been laundered through its neighbours twice. Adding the identity, Ã = A + I, puts the node back in its own sum. This is the analogue of GraphSAGE keeping hv in a concatenation, done with a cheaper mechanism.
Symmetric normalisation. Aggregating with raw à makes a node's output scale with its degree, so hubs shout and leaves whisper, and stacking such layers lets activations grow without bound. Dividing by the degree of the receiving node alone gives the row-normalised operator D̃−1Ã, an honest mean. Kipf & Welling's renormalisation splits the division between both endpoints instead, which keeps the operator symmetric and its eigenvalues inside [−1, 1]:
Read per-node, a message from u to v is discounted by both endpoints' degrees. A message from a hub counts for less, because the hub is telling everyone the same thing; a message into a hub counts for less too, because the hub is already hearing from everyone.
Node 4 is the hub, joined to six others. Under none its row sums to 7 while node 8's sums to 3, so a single layer already amplifies the hub by more than a factor of two. row flattens every row sum to exactly 1. symmetric does not — hub rows stay slightly below 1 and leaf rows slightly above — which is the price of keeping the operator symmetric, and cheap next to what symmetry buys: Â is then a real symmetric matrix with a clean spectrum, so stacking layers is a well-behaved filtering operation rather than a source of blow-up.
🧺 The aggregator decides what the layer can tell apart
A neighbourhood is a multiset, so AGGREGATE is a function on multisets, and whatever it cannot distinguish the layer cannot distinguish either — no amount of training fixes a collision that happens before the weights are reached. Xu et al. rank the three standard choices by exactly this criterion.
- Mean keeps proportions and drops counts: {{a, a, a}} and {{a}} are the same input.
- Max keeps only the set of distinct elements, dropping both counts and multiplicities: {{a, b}} and {{a, a, b, b, b}} are the same input.
- Sum keeps the full multiset. Over a countable feature space there is a mapping under which summation is injective on bounded multisets, so a sum followed by a sufficiently expressive MLP can represent any multiset function — that is the graph isomorphism network, GIN:
The ranking is sum > mean > max in discriminative power, and it is strict: every pair that mean separates, sum separates too, and there are pairs — the counts preset — that only sum separates. This does not make mean a mistake. On a citation graph where degree is noise rather than signal, mean's invariance to neighbourhood size is a useful prior, and it is what the GCN layer's normalisation approximates. The ranking says what is possible, not what generalises.
Sum is also where the ceiling sits. Any message passing GNN of this shape is at most as powerful as the 1-dimensional Weisfeiler–Leman test, the classical colour-refinement heuristic for graph isomorphism — proved independently by Xu et al. and by Morris et al. Colour refinement does exactly what message passing does: hash each node's colour together with the multiset of its neighbours' colours, repeat. Two graphs that 1-WL cannot separate produce identical node representations under every such GNN, at any width and any depth.
🌫️ Over-smoothing: why deep is not better here
Depth extends the receptive field, so a deeper GCN should see more. It does not work out that way. Li, Han & Wu identified the reason: the propagation step  H is a form of Laplacian smoothing, and smoothing is a contraction on everything except one direction. Iterating it drives the representations of a connected component together — Oono & Suzuki later showed the collapse is exponential in depth.
The surviving direction is easy to name. Â D̃1/2 1 = D̃−1/2Ã 1 = D̃1/2 1, so D̃1/2 1 is an eigenvector with eigenvalue exactly 1 while every other mode has modulus below 1 and decays. The fixed point is therefore hv → √d̃v · c for one shared vector c: after enough layers a node's representation encodes its degree and nothing else.
At k = 0 the colours are noise: the raw features barely encode the community. Two or three steps resolve them into two blocks, which is the entire benefit — averaging over a neighbourhood cancels independent noise and leaves the shared community offset intact. Past that, the same averaging eats the signal it just recovered. The mean pairwise distance falls geometrically, from 1.40 at k = 0 to 0.80 at k = 10, 0.37 at k = 20 and 0.13 at k = 40, and the two blocks fade into one colour on the way. The rate is set by the second-largest eigenvalue of  — the exponential decay Oono & Suzuki describe — so a graph with well-separated communities buys a few extra layers of grace and nothing more. There is a useful depth and it is small; on standard citation benchmarks it is 2, which is why the reference GCN has two layers and not ten.
🎓 Training a GCN
The setting below is the one Kipf & Welling used: transductive semi-supervised node classification. One fixed graph, features for every node, labels for a handful, and a model that sees the whole graph at training time and is scored on the unlabelled nodes. The reference architecture is two layers, softmax on the output, and a cross-entropy loss summed over labelled nodes only:
The graph is a 50-node stochastic block model with two planted communities, drawn from a fixed seed. Each node carries an 8-dimensional feature vector: a small community-dependent offset buried in unit Gaussian noise. Deliberately weak — a classifier that sees only the features has a low ceiling, so anything above it comes from the edges. The model is a few hundred parameters, trained full-batch with Adam and L2 weight decay, on hand-written gradients.
Untick use the graph and  is replaced by the identity. Every other part of the model is untouched — same weights, same optimiser, same labels — so what remains is a plain MLP on the raw features, and its held-out accuracy plateaus far below. The two best readouts keep the high-water mark for each setting side by side; the gap between them is the graph's contribution, and it is the reason to use one of these models at all. With four labels per class the run above settles around 0.90 held-out accuracy with  and around 0.60 with I — eight labelled papers, and the edges supply the rest.
Two other controls are worth moving. Dropping labels per class to 1 leaves two labelled nodes in the entire graph, and accuracy barely moves — around 0.94, higher than the four-label run rather than lower. The propagation matrix is doing the work, spreading two labels across fifty nodes, and the features-only model at the same setting stays near 0.63. On layers, 1 is clearly too few — the single propagation gets to roughly 0.79 where two layers reach 0.90 — while 3 costs more per step and buys nothing, landing on the same accuracy as 2 at most label budgets and below it at the smallest. On a graph whose communities are two hops wide, that is where the useful depth ends.
🧭 Where this generalises
Every architecture below is the same UPDATE/AGGREGATE template with a different answer to one question: where does the coefficient on a neighbour's message come from?
| Model | Coefficient on the message from u to v | What it buys |
|---|---|---|
| GCN | Fixed, structural: 1 ∕ √(d̃u d̃v). | One sparse matrix product per layer; nothing to learn in the aggregation. The default baseline. |
| GraphSAGE | Aggregate over a fixed-size uniform sample of N(v), then concatenate hv before the weight matrix. | Bounded per-node cost regardless of degree, so it minibatches and runs inductively on nodes never seen in training. |
| GAT | Learned: αvu = softmax over N(v) of LeakyReLU(a⊤[Whv ‖ Whu]). | The graph chooses which neighbours matter instead of the degrees choosing. This is self-attention with the softmax restricted to N(v) rather than run over every position. |
| GIN | Uniform 1, self weighted by (1 + ε), the sum fed to an MLP. | Injective on neighbourhood multisets, hence as discriminative as 1-WL — the maximum for this template. |
Seen this way, attention is not a separate idea bolted onto graphs. A transformer is a GNN run on a complete graph with learned edge weights and positional information supplied separately; a GAT is that same computation with the complete graph replaced by a sparse one. The restriction is the point: the edges are a prior, and on a citation graph it is a good one.
The layer stack is only half of a model. The other half is the readout, which depends on what the prediction is about:
- Node level — classify or regress hv(K) directly. Node classification, as in §6; also fraud detection and role labelling.
- Edge level — score a pair, typically from hu(K) and hv(K) via a dot product or a small MLP. Link prediction and recommendation.
- Graph level — pool all node states into one vector with a permutation-invariant readout, R({hv(K)}), then predict from that. Molecular property prediction, the task MPNNs were written for. The readout faces the same multiset question as AGGREGATE, with the same answer: sum preserves the most, and hierarchical pooling is used when the graphs are large.
🎯 Consequences worth remembering
- Permutation equivariance is the axiom, message passing is the consequence. Once a layer may not depend on node indices, it has to read each node's neighbourhood through an order-invariant aggregate. Every model here is a choice of aggregate.
- Self-loops and normalisation are not cosmetic. Without à = A + I a node discards its own features; without degree normalisation hubs dominate and activations grow with depth.
- The aggregator sets a ceiling before training starts. Mean forgets counts, max forgets multiplicities, sum with an MLP forgets nothing — and no message passing GNN of this shape beats the 1-WL test, whatever its width or depth.
- Depth in a GNN is not depth in a CNN. Propagation is smoothing, and iterated smoothing converges to a degree-dominated fixed point. Two or three layers is usually the right number; going deeper requires skips, jumping knowledge, or explicit distance-preserving normalisation.
- The graph is what pays. With features weak enough to be interesting, the gap between  and I in §6 is the entire argument for the architecture — and it shows up most clearly when the labels are scarce.
- Attention is a special case, not an alternative. Replace the fixed degree-based coefficients with learned ones and a GCN becomes a GAT; replace the sparse graph with a complete one and it becomes a transformer layer.