Graph Neural Networks (GNN)

Definition

A graph neural network is a neural network whose notion of which inputs are next to which comes from the data rather than from the architecture. Every network that is any good at structured data mixes information between nearby inputs; the interesting question is who decided what "nearby" means. A convolutional neural network has that answer welded in: a pixel's neighbours are the eight pixels touching it, in every image, forever. A transformer welds in the opposite answer: every token is adjacent to every other token, which is powerful and costs n² comparisons. A GNN is simply handed the adjacency list — this account paid that one, this carbon is bonded to that oxygen, this road segment feeds into that junction — and mixes along exactly those edges and no others.

That one substitution is the whole idea, and it is why a single family of models covers molecules, road networks, citation graphs, payment networks and recommendation catalogues. It also fixes the cost: work per layer scales with the number of edges, not with the number of nodes squared, so a sparse graph of a million nodes and five million edges is cheap where a transformer over the same million nodes is not.

One boundary is worth drawing before the mechanism. A knowledge graph is a data structure — entities, typed relations, and the querying and retrieval built on top of them. A GNN is one of the things you can run on such a structure, and far from the only one; most knowledge-graph work is traversal and lookup with no learned message passing anywhere. This page is about what happens when you train a network on a graph, whatever produced the graph.

What breaks if you ignore this: the two obvious workarounds both throw away the thing you were paid to model. Flatten each node into a hand-built feature vector — "this account has 43 counterparties, 12 of them flagged" — and you have summarised one hop and destroyed everything beyond it, which is exactly where a fraud ring lives. Feed the raw node set to a transformer instead and you pay quadratic cost to make the model rediscover, from data, an adjacency structure you already knew exactly. The GNN's bet is that the edges you were given are worth more as an input than as something to be inferred, and when they are, the gap is not small: GraphSAGE's supervised variant improved classification F1 by an average of 51% over node features alone, and Pinterest's PinSage reached a 67% recommendation hit-rate where the best content-only baseline managed 27%.

How It Works

One round of message passing, by hand

Every mainstream GNN is a special case of one loop: each node collects the current vectors of its neighbours, combines them into a single message, and updates itself from that message plus its own previous state. Repeat. The variants differ only in how the combining is done.

Here is the loop on six accounts, which is small enough to check with a pencil. Nodes 0, 1 and 2 form a triangle; nodes 3, 4 and 5 form another; a single edge 2–3 bridges them. The features are one-dimensional, and only account 0 is flagged, so the starting vector is 1, 0, 0, 0, 0, 0. The aggregation is the simplest useful one — the mean over a node's neighbours and itself, which is what the self-loop in a GCN buys you.

Node 2 has neighbours 0, 1 and 3, so its closed neighbourhood has four members and its first update is (1 + 0 + 0 + 0) / 4 = 0.25. Nodes 0 and 1 each have a closed neighbourhood of three, both containing the flagged account, so both become 1 / 3 = 0.3333. Node 3's closed neighbourhood is 2, 3, 4, 5 — all still zero — so node 3 stays at 0. Run that forward:

Read the zeros. After one round only nodes 0, 1 and 2 know anything, because they are the only ones within one hop of the flagged account. Node 3 first hears about it at round 2; nodes 4 and 5, which sit three hops away, first move at round 3. The number of rounds is the radius of what a node can possibly know, and nothing in the model can shortcut it. A two-layer GNN cannot detect a pattern that requires seeing three hops out, no matter how wide its layers are or how long you train it.

k layers reach k hops, and k hops is d^k nodes

The flip side arrives immediately. If the average node has d neighbours, then a node's k-hop neighbourhood contains on the order of d^k nodes. At d = 10 and k = 3 — a modest social graph and a modest depth — a single node's embedding already depends on roughly 1,000 others. At k = 4 it is 10,000. This is the arithmetic underneath both of the field's central problems, and it is worth internalising before any of the architecture names.

The practical bite is that a minibatch stops being independent. In an ordinary network you can train on 512 examples in isolation; in a GNN, computing 512 node embeddings at depth 3 requires touching 512 × d^3 nodes' features. The GraphSAGE dataset makes the point brutally: their Reddit graph has 232,965 posts with an average degree of 492, so the nominal two-hop neighbourhood of a single post is 492² ≈ 242,000 nodes — more than the 232,965 the entire graph contains. At two hops, "a node's neighbourhood" and "the whole dataset" are the same object.

This is exactly why neighbourhood sampling exists. GraphSAGE (Hamilton, Ying and Leskovec, NeurIPS 2017) draws a fixed-size uniform sample of neighbours at each hop instead of using all of them, which makes the per-batch cost the constant product of the sample sizes rather than a function of the graph. Their reported settings are K = 2 with sample sizes 25 and 10 — at most 250 nodes touched per target node, about a thousandth of that 242,000-node closure — and a general rule of thumb that the product of the per-hop samples should stay under 500.

Their depth ablation is the number to remember when someone proposes a ten-layer GNN: moving from one layer to two gave "a consistent boost in accuracy of around 10-15%, on average", while increasing depth beyond two gave "marginal returns in performance (0-5%) while increasing the runtime by a prohibitively large factor of 10-100×". Pinterest measured the same curve on the neighbourhood size instead of the depth. In PinSage's Table 4, sampling 10 neighbours per node gave a 60% hit-rate for 20 hours of training; 20 neighbours gave 63% for 33 hours; 50 neighbours gave 67% for 78 hours. Five times the neighbourhood bought 3.9 times the training time and seven points of hit-rate, and they stopped there.

The same averaging, run too long, erases everything

Depth in a GNN is not merely expensive. It is actively destructive, and the reason is visible in the table above: repeated neighbourhood averaging is a diffusion process, and diffusion converges to a constant. Li, Han and Wu made this precise at AAAI 2018 in "Deeper Insights into Graph Convolutional Networks for Semi-Supervised Learning", showing that graph convolution "is actually a special form of Laplacian smoothing, which is the key reason why GCNs work, but it also brings potential concerns of over-smoothing with many convolutional layers." Their Theorem 1 states that on a graph with no bipartite components, repeated smoothing converges to a linear combination of the connected components' indicator vectors — which on a single connected graph means every node ends up at the same value. (Bipartiteness would make plain adjacency averaging oscillate instead; adding the self-loop that GCNs already use creates odd cycles and removes the exception.)

Continue the six-account run and watch it happen:

The limit is not approximate and not empirical — it is arithmetic. Mean aggregation with self-loops is a random walk on the graph, so every node converges to the degree-weighted average of the starting features. The closed-neighbourhood sizes here are 3, 3, 4, 4, 3, 3, summing to 20, and only node 0 started at 1, so every node converges to exactly 3/20 = 0.1500. By round 50 the spread between the most and least suspicious account is 0.0002. A classifier reading these embeddings has nothing left to classify. This is why production GNNs are two or three layers deep while production CNNs are fifty, and why residual connections, jumping knowledge and explicit normalisation exist in this field: they are all attempts to buy depth back from a process whose natural end state is a constant.

What comes out, and where the ceiling is

The output of the loop is one vector per node — a node embedding, with the same properties as any other embedding: the coordinates mean nothing individually, only distances within one model's space are comparable, and you feed them to a downstream classifier or a nearest- neighbour index. What is specific to GNNs is how the vector was built: it is a summary of a k-hop neighbourhood rather than of a text or an image. For graph-level tasks — is this molecule toxic? — the node vectors are pooled into one graph vector by a readout function.

There is a sharp, provable ceiling on what those vectors can distinguish, and it is the most useful thing to know about GNNs that introductory material almost never mentions. In "How Powerful are Graph Neural Networks?" (Xu, Hu, Leskovec and Jegelka, ICLR 2019), Lemma 2 says that for any two non-isomorphic graphs, if a message-passing GNN maps them to different embeddings, then the Weisfeiler-Lehman graph isomorphism test also decides they are not isomorphic. The paper draws the conclusion in the next line: "any aggregation-based GNN is at most as powerful as the WL test in distinguishing different graphs." The test in question is the 1-dimensional form, "naïve vertex refinement", which is the same colour-refinement loop the GNN is running. The paper's companion result is that a GNN reaches that bound only when its aggregation and readout are injective — most common aggregators, including mean and max, are not.

Check the consequence by hand. Take a six-node cycle and, separately, two disjoint triangles. Every node in both graphs has degree 2. With no distinguishing input features, every node starts with the same colour, every node's neighbour multiset is identical, and the refinement never separates anything — at every round the two graphs have the same colour histogram. So no message-passing GNN can tell a six-ring from two three-rings. That is not a training failure to debug; it is a structural fact, and it is why chemistry-facing models add ring counts, distances or random node identifiers as input features rather than hoping the architecture will notice.

Types

The named architectures are all the same loop with a different answer to one question: who decides how much each neighbour counts?

GAT is the one worth understanding as a bridge rather than a new thing. It is ordinary self-attention — query, key, softmax, weighted sum — with the softmax restricted to a node's neighbour set instead of running over the whole input. Which reframes the last row of the table: a graph transformer is a GNN that has abandoned the edge restriction, and a standard transformer is a GNN on a complete graph. The family is one dial, not four inventions.

Real-World Applications

Google Maps arrival times. DeepMind and the Maps team put a GNN into production for ETA prediction, described in "ETA Prediction with Graph Neural Networks in Google Maps" (CIKM 2021). Road networks are the ideal case: adjacency is literal, and traffic on one segment propagates to segments it feeds. They report "significantly reducing negative ETA outcomes in several regions compared to the previous production baseline (40+% in cities like Sydney)", where a negative ETA outcome is defined as an ETA error above a fixed threshold. The paper is also honest about the operational cost: ETA prediction in production "invites particularly unstable training conditions across many batches of queries, particularly over routes of different scales", and they had to import MetaGradients from reinforcement learning to tune the learning rate on the fly before the model was stable enough to deploy.

Pinterest recommendations. PinSage (Ying et al., KDD 2018) runs graph convolutions over a pin-and-board graph of 3 billion nodes and 18 billion edges, trained on 7.5 billion examples. It reached a 67% hit-rate and 0.59 MRR against 46% and 0.56 for the strongest baseline offline, and in production A/B tests delivered "10-30% improvements in repin rate" over annotation- and image-embedding-based recommendation. The interesting part for anyone building one is Table 4, quoted above: the neighbourhood size is a direct dial between accuracy and training hours, and they stopped at 50.

Molecular property prediction. A molecule is a graph with no ambiguity about it — atoms are nodes, bonds are edges — which is why this was the first domain GNNs genuinely won. "Neural Message Passing for Quantum Chemistry" (Gilmer et al., 2017) unified the existing models into the message-passing framework and reported predicting the density-functional theory result "to within chemical accuracy on 11 out of 13 targets" on the QM9 benchmark, and on 5 of 13 using the molecule's topology alone with no spatial coordinates. The economics are the point: a DFT calculation for a single nine-heavy-atom molecule "takes around an hour" and up to eight for seventeen atoms, while the paper notes neural network inference is roughly 300,000 times faster. At that ratio a virtual screen that would take a decade of DFT time — about 87,600 hours — finishes in under twenty minutes, which is the entire mechanism behind AI drug discovery pipelines.

Challenges

Depth is capped by physics, not by budget. The over-smoothing arithmetic above is not an implementation detail you can engineer around with more GPUs — averaging converges, full stop. If your task genuinely requires eight-hop reasoning, a stack of eight message-passing layers will deliver eight hops of reach and a set of nearly identical embeddings. The realistic responses are to add shortcut edges, use a graph transformer, or accept that the task needs a different model.

Minibatches are not independent, so nothing about your training loop transfers. The d^k explosion means sampling is a modelling decision, not an optimisation. Every training run is therefore on a slightly different graph, which is where the Google Maps team's curriculum instability came from.

The graph is a choice, and a bad one is unfixable downstream. Nothing in the model questions the edges you supply. GraphSAGE's Reddit graph was built by connecting two posts whenever the same user commented on both — a defensible rule that produced an average degree of 492 and made two-hop neighbourhoods larger than the graph. Move the threshold to "the same user commented on both twice" and you have changed the cost, the semantics and the results, with nothing in the model to tell you. A GNN on a graph built from a careless join learns the join.

The 1-WL ceiling shows up as specific blind spots. Message passing cannot count triangles or distinguish regular graphs of the same degree, which matters concretely in chemistry (ring systems) and fraud (dense clusters of similar accounts). The fix is input features — ring counts, shortest path distances, random identifiers — not a deeper network.

Explaining a prediction means explaining a subgraph. A node's score depends on hundreds or thousands of others through the d^k fan-out, so "why was this account flagged" has no single-feature answer. Regulated deployments need subgraph-attribution tooling that does not exist in the same mature form as feature attribution for tabular models.

Code Example

Twenty lines of NumPy reproduce every number in this page: message passing as one matrix multiply per round, and over-smoothing as its inevitable limit.

import numpy as np

# Six accounts: two triangles (0,1,2) and (3,4,5) joined by one bridge, 2-3.
edges = [(0, 1), (0, 2), (1, 2), (2, 3), (3, 4), (3, 5), (4, 5)]
A = np.zeros((6, 6))
for u, v in edges:
    A[u, v] = A[v, u] = 1.0

A_hat = A + np.eye(6)                    # a node hears itself as well as its neighbours
P = np.diag(1.0 / A_hat.sum(axis=1)) @ A_hat   # row-normalise -> mean aggregation

h = np.array([1.0, 0.0, 0.0, 0.0, 0.0, 0.0])   # only account 0 is flagged

print("round " + "".join(f"   node{i}" for i in range(6)) + "      spread")
for r in range(51):
    if r in (0, 1, 2, 3, 5, 10, 20, 50):
        print(f"{r:5d} " + "".join(f"{x:8.4f}" for x in h) + f"{h.max() - h.min():11.6f}")
    h = P @ h

Output:

round    node0   node1   node2   node3   node4   node5      spread
    0   1.0000  0.0000  0.0000  0.0000  0.0000  0.0000   1.000000
    1   0.3333  0.3333  0.2500  0.0000  0.0000  0.0000   0.333333
    2   0.3056  0.3056  0.2292  0.0625  0.0000  0.0000   0.305556
    3   0.2801  0.2801  0.2257  0.0729  0.0208  0.0208   0.259259
    5   0.2462  0.2462  0.2059  0.0940  0.0538  0.0538   0.192387
   10   0.1954  0.1954  0.1764  0.1236  0.1046  0.1046   0.090716
   20   0.1601  0.1601  0.1559  0.1441  0.1399  0.1399   0.020164
   50   0.1501  0.1501  0.1501  0.1499  0.1499  0.1499   0.000221

A real GNN differs from this in two ways only: h is a matrix of feature vectors rather than a column of scalars, and each round applies a learned weight matrix and a nonlinearity before the next multiplication by P. Neither changes the geometry. P is still a stochastic matrix, its powers still converge, and the spread column still marches to zero — which is why the useful question about a GNN is almost never "how deep" but "how few layers can I get away with".