Learn · Intermediate

Graph neural networks: learning from things defined by their connections

A graph neural network is a model for data whose meaning lives in its connections rather than in its order or its position on a grid. A molecule is atoms joined by bonds; a road network is junctions joined by streets; a citation network is papers joined by references. In each case, shuffling the list of items changes nothing and losing the connections destroys everything. Graph neural networks, or GNNs, learn by having every node repeatedly exchange messages with its neighbours until each one's representation reflects the neighbourhood it sits in.

The reason this needs its own architecture comes down to a mismatch. Neural networks generally assume a shape. A convolutional network assumes a grid, where "next to" is well defined and every pixel has the same number of neighbours. A recurrent network assumes a sequence with a first and last element. A graph has neither. Nodes have wildly different numbers of neighbours, there is no canonical ordering, and two drawings of the same molecule with the atoms listed in a different order must produce the same answer. That last requirement — permutation invariance — is the constraint that shapes everything else.

The mechanism that satisfies it is message passing, formalized in Neural Message Passing for Quantum Chemistry. One round works like this. Every node looks at each of its neighbours and computes a message from it. All incoming messages are combined with an operation that does not care about order — a sum, a mean, a maximum. Each node then updates its own representation using its old state and that combined message. Because the combining step ignores order, relabelling the nodes cannot change the result.

The analogy that makes this click is gossip in a village. On day one, everyone knows only about themselves. That evening, each person tells their immediate neighbours what they know. By the end of day two, everyone's picture includes their neighbours' neighbours. After a few rounds, each person holds a summary of their local region — richer the closer it is to them, vaguer further out. That is precisely what a GNN computes: after k rounds of message passing, a node's representation encodes the structure within k hops of it.

That analogy also explains the field's most characteristic failure. Keep the gossip going long enough and everyone in the village converges on the same story. In a GNN this is called over-smoothing: with too many layers, all node representations drift toward one another and the distinctions the model needs are washed out. It is the reason GNNs are usually shallow — two to four rounds — while transformers stack a hundred layers happily. Depth in a graph network buys reach and costs discrimination.

Several important variants adjust who gets listened to and how far you look. Graph Convolutional Networks, from Thomas Kipf and Max Welling, use a simple normalized average of neighbours and remain the standard baseline. Graph Attention Networks, from Petar Velickovic and colleagues, let a node learn how much to weight each neighbour rather than treating them equally — the same attention idea that powers language models, restricted to the edges that actually exist. GraphSAGE samples a fixed number of neighbours instead of using all of them, which is what makes the approach tractable on graphs with billions of edges and, crucially, allows the model to handle nodes it never saw in training.

Once you notice the pattern, the relationship to transformers becomes clear and clarifies when to use which. A transformer is, in effect, a graph network run on a fully connected graph: every token can attend to every other token, and positional encodings are bolted on to reintroduce the order that this structure discards. That generality is why transformers dominate — they assume almost nothing. But it costs computation growing with the square of the input, and it throws away structure you may already know for certain. If you know which atoms are bonded, telling the model is strictly better than making it rediscover the bonds from data. This is the argument made in Relational Inductive Biases, Deep Learning, and Graph Networks: built-in structure is not a limitation, it is a way of not wasting capacity on facts you already have.

Where this pays off is science and infrastructure. Molecular property prediction and drug screening are graph problems by nature, and message passing over bonds is the workhorse behind much of modern computational chemistry, including the systems underpinning de novo protein design. Google's travel-time predictions run on road graphs. Recommendation systems run on user-item graphs. Physics simulators represent particles and their interactions as nodes and edges, which is one route into world models.

The honest limits: GNNs are hard to scale because a node's neighbourhood explodes combinatorially with depth, over-smoothing caps useful depth at a handful of layers, and standard message passing is provably unable to distinguish certain non-isomorphic graphs — there are structurally different graphs it simply cannot tell apart. They are also less amenable to the brute-force scaling that made language models work, since graph datasets are smaller and far more heterogeneous. GNNs are a specialist tool, and the right question is always whether your data's connection structure is real, known and genuinely informative. When it is, nothing else uses it as well.

Ground Truth. (2026, September 8). Graph neural networks: learning from things defined by their connections. Ground Truth. https://groundtruth.day/learn/graph-neural-networks.html

@misc{groundtruth:graph-neural-networks,
  title  = {Graph neural networks: learning from things defined by their connections},
  author = {{Ground Truth}},
  year   = {2026},
  month  = {sep},
  url    = {https://groundtruth.day/learn/graph-neural-networks.html}
}

Topics: architectures · graphs · message-passing · ai-for-science · representation-learning