A graph neural network is a stack of layers that each update every node’s vector from its own vector and the average of its neighbours’. That is the whole mechanism, it is one sparse matrix multiply per layer, and the interesting part is what stops you from stacking more than about three of them.
The shapes
A graph is a set of nodes with feature vectors and a set of edges. Two tensors describe it:
X : (num_nodes, d_in) one feature vector per node
edge_index : (2, num_edges) source and destination of each edge
A molecule: 24 atoms, 26 bonds, 16 features per atom
X : (24, 16)
edge_index : (2, 52) each bond stored in both directions
Note what is not in there: any ordering. A sequence model gets position for free; a graph model has none, and the layer must be invariant to the order the nodes happen to be listed in. That constraint is why the aggregation step is always a sum, a mean or a max rather than anything that reads its inputs in order.
One layer, as a matrix multiply
The message-passing form, per node:
h_v' = sigma( W_self @ h_v + W_neigh @ AGG_{u in N(v)} h_u )
AGG is mean, sum or max over the neighbours of v.
Written for the whole graph at once it collapses into something a GPU already knows how to do. Let A_hat be the adjacency matrix with self-loops added and rows normalised by degree:
H' = sigma( A_hat @ H @ W )
A_hat : (num_nodes, num_nodes) sparse, num_edges non-zeros
H : (num_nodes, d_in) dense
W : (d_in, d_out) dense
That is the graph convolutional layer of Kipf and Welling (2016), and it is worth seeing it in this form because it makes the cost obvious: one dense matmul for the feature transform, one sparse matmul for the neighbourhood mixing. Attention-style variants (GAT) replace the fixed normalised weights in A_hat with learned per-edge weights, which is attention restricted to the edges that exist rather than all pairs.
What a layer costs
Take a graph with 100,000 nodes, 1,000,000 edges and 128-dimensional features:
feature transform H @ W:
100,000 * 128 * 128 = 1.64 billion MACs
neighbourhood mixing A_hat @ (HW):
1,000,000 edges * 128 channels = 128 million adds
ratio: the dense transform is about 13x the arithmetic.
The arithmetic says the dense part dominates. The wall clock usually says otherwise, and the reason is memory access. The gather step reads a 128-float row from an arbitrary location for every one of the million edges, in an order the graph decides. That is a scattered read pattern on hardware built for contiguous ones, so a GNN layer typically runs at a small fraction of the arithmetic throughput the same GPU reaches on a dense matmul of equal size.
It is the same lesson as everywhere else in inference: the number that predicts speed is memory traffic, not FLOPs. Graph batching libraries exist mostly to make that traffic more regular.
Two things that stop you adding layers
Over-smoothing
Each layer replaces a node’s vector with a blend of its neighbourhood. Repeat that and it is a diffusion process, and diffusion has a fixed point: within a connected component, every node converges to the same vector. At that point the representations carry the component identity and nothing else.
This is not a subtle effect. On many benchmark graphs a plain GCN peaks at two or three layers and degrades measurably by six. Residual connections, initial-residual schemes and normalisation push the usable depth up, but the pressure is always there, and it is the exact opposite of the situation in a transformer where more layers keep helping.
Neighbourhood explosion
To compute one node’s output at layer L you need its L-hop neighbourhood. With average degree 10:
1 hop: 10 nodes
2 hops: 100 nodes
3 hops: 1,000 nodes
4 hops: 10,000 nodes ...to produce one output vector
On a social graph with high-degree hubs it is worse: one celebrity node in the two-hop neighbourhood pulls in millions. The standard answer is neighbour sampling — GraphSAGE-style fan-outs like 25 at the first hop and 10 at the second, capping the subgraph at a fixed size per target node and accepting the variance that introduces.
The variants, and what each changes
The acronyms all describe the same loop with one piece swapped. The first question to ask of any of them is not accuracy but whether it is transductive or inductive — whether it needs the whole graph present at training time, or can produce an embedding for a node it has never seen. In any system where the graph grows, only the second is usable.
| Variant | Description |
|---|---|
| GCN | Fixed symmetric normalisation by node degree, no learned weighting per edge. The cheapest, and transductive as usually formulated: the normalised adjacency matrix is built from the whole graph. |
| GraphSAGE | Sample a fixed number of neighbours, aggregate them, and concatenate with the node’s own vector rather than summing into it. Inductive by design — the learned function is over neighbourhoods, not over specific nodes — which is why it is what production systems tend to use. |
| GAT | Learn a weight per edge with an attention score instead of normalising by degree. Correct when neighbours differ in importance; costs an attention computation per edge, and edges outnumber nodes. |
| GIN | Sum aggregation with an MLP, argued to be maximally expressive among this class. The argument is concrete: mean and max cannot tell a neighbourhood of three identical items from one of five, because both collapse to the same value. Sum can. Where counts matter — chemistry, fraud rings — that is not a technicality. |
| Relational GNN | A separate weight matrix per edge type, for knowledge graphs where “works at” and “founded” should not be aggregated by the same transformation. Parameter count grows with the number of relation types, which is why basis decomposition of those matrices is standard. |
One use case, end to end
Molecular property prediction, because it is the case where the graph is the natural representation rather than an imposed one.
- Build the graph. Atoms are nodes; bonds are edges. Node features: atomic number one-hot, formal charge, degree, aromaticity, hybridisation — roughly 30 to 100 dimensions after encoding. Edge features: bond type, ring membership.
- Three message-passing layers. After layer one each atom knows its bonded neighbours; after two, the atoms two bonds away; after three, a chemical neighbourhood about the size of a functional group. That is the right depth for the physics, which is a nice case of the over-smoothing limit not binding.
- Pool. Sum or mean the atom vectors into one molecule vector. Sum-pooling is the choice when the property is extensive — something that grows with molecule size — and mean when it is not.
- Read out. A two-layer MLP from the molecule vector to the property: solubility, toxicity flag, binding affinity.
- Train on a few thousand labelled molecules. This is the regime where a GNN is clearly correct: the labels are expensive wet-lab measurements, the datasets are small, and the graph structure is exactly the prior that substitutes for the data you do not have.
The trade
What it buys: the relational structure is in the architecture rather than in the input format. A model that must be told about a graph in text has to spend context on it, has to be given an arbitrary ordering, and gets no guarantee that reordering the same graph produces the same answer. A GNN gets permutation invariance for free and scales to graphs far larger than any context window.
What it costs: depth is capped by over-smoothing, receptive field is capped by depth, hardware utilisation is poor because the access pattern is irregular, batching several graphs means building a block-diagonal supergraph, and the whole tooling ecosystem is a fraction of the size of the one around transformers. There is also a plain practical point worth making: if your graph is small enough to serialise into a prompt, doing that with a general model is often the cheaper engineering decision even when it is the less elegant one.
Top comments (0)