Graph Neural Networks and Message Passing

A graph contains nodes, edges, and optional features on both. Nodes might be accounts, molecules, papers, products, or road intersections. Edges might represent transactions, bonds, citations, co-purchases, or physical connections. The graph can be directed, weighted, typed, dynamic, or contain several relation families.

A message-passing layer computes messages along edges, aggregates incoming messages for each node, and updates the node representation. Aggregation should be insensitive to arbitrary neighbor order. Sums, means, maxima, attention-weighted combinations, and learned set functions are common choices. Stacking layers expands the receptive field: after two layers, a node can incorporate information from paths of roughly two hops.

More layers are not automatically better, and the reason has been characterised twice. A 2018 paper by Li and two co-authors found the mechanism. Graph convolution, they showed, “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”. The smoothing is not a defect bolted onto the method. It is the method, and depth is the dose.

The end state has a name and a rate as well, given by Oono and Suzuki in 2019. They open from the practitioner's side: “However, it is known that they do not improve (or sometimes worsen) their predictive performance as we pile up many layers and add non-lineality.” Their proof says where the representations go. When the GCN's weights satisfy conditions set by the spectra of the augmented normalised Laplacian, the output exponentially approaches a set of signals that carry only connected-component and node-degree information. That is the whole surviving content of a node after enough layers: which component it sits in, and how many neighbors it has. Everything the features contained has been averaged away.

The exact neural functions vary, but the computational pattern is broadly shared. A layer forms messages along edges from source-node, target-node, edge and relation features; aggregates the unordered set of incoming messages at each destination node; updates the node state by combining the old representation with that aggregate; optionally updates edge or global state as well; and then the next layer repeats the cycle for another hop.

What that loop can and cannot do is not a matter of taste. Two groups reached the same ceiling in 2019, working separately. One paper came from Xu and three co-authors, the other from Morris and six. Both showed that a standard neighbourhood-aggregation GNN is at most as powerful as the 1-dimensional Weisfeiler-Leman graph isomorphism test at telling non-isomorphic graphs apart. Morris and colleagues state it flatly: “We show that GNNs have the same expressiveness as the 1-WL in terms of distinguishing non-isomorphic (sub-)graphs. Hence, both algorithms also have the same shortcomings.” GCN and GraphSAGE therefore provably cannot distinguish certain simple graph structures. No amount of data or training removes the limit. It belongs to the aggregation, not to the fit.

The second limit concerns information that has to travel far through a fixed topology, and it has a measured price. Alon and Yahav, in 2021, took GNNs that Brockschmidt had already tuned over 500 configurations. They changed one thing. The last of the eight layers became a fully-adjacent layer — no additional tuning, no extra learnable weights. On QM9: “The main results are that breaking the bottleneck by modifying a single layer to be an FA layer significantly reduces the error rate, by 42% on average, across six GNN types.” The same single change cut error by 12% on ENZYMES and by 4.8% on NCI1. Di Giovanni and five co-authors later proved the mechanism behind that gain: depth cannot mitigate over-squashing, and graph topology dominates it. One layer's connectivity bought 42%. More layers would not have.

The supervision level changes pooling, negative sampling, and evaluation. Node prediction assigns a label or value to each node using neighborhood context — a fraud account, a paper topic. It carries the risk of split leakage through edges, and it may be transductive or inductive. Edge or link prediction asks whether, how, or when two nodes are related. It therefore requires a negative-edge strategy, usually respects temporal ordering, and is scored with ranking metrics, as in recommendation and knowledge graphs. Graph prediction pools node and edge representations into a single output per graph — a molecule property, a program's behavior. There, pooling must preserve the relevant structure, graph size can confound the prediction, and splits may need scaffold or entity controls.

GraphCast shows what a node-level target looks like when the graph is the planet. It is a message-passing GNN operating on a multi-scale mesh over the globe. It produces 10-day forecasts of hundreds of weather variables at 0.25° resolution in under a minute. Lam and colleagues reported the result in Science in 2023: “We show that GraphCast significantly outperforms the most accurate operational deterministic systems on 90% of 1380 verification targets, and its forecasts support better severe event prediction, including tropical cyclones, atmospheric rivers, and extreme temperatures.” The denominator is the part worth copying. The claim is not a headline average over an unnamed evaluation. It is a stated count of 1,380 verification targets, with the fraction won given against it.

The architecture then followed the result into public operations. ECMWF's own account of building its Artificial Intelligence Forecasting System records that “the design choice of graph neural networks was made for the first implementation”. AIFS Single became operational in February 2025.

Most graph failures begin with an unjustified representation choice, so it helps to read a system that had to make one and then run on it. Google Maps' production ETA model is a graph neural network over the road network. Road segments are the nodes. Edges join segments that are consecutive or share an intersection. The unit the model works over is a “Supersegment” of adjacent segments sharing significant traffic volume. Derrow-Pinion and sixteen co-authors report what the deployed system did: “Our GNN proved powerful when deployed, significantly reducing negative ETA outcomes in several regions compared to the previous production baseline (40+% in cities like Sydney).” DeepMind's release of the system, on 3 September 2020, reported real-time ETA accuracy improvements of up to 50% in cities including Berlin, Jakarta, São Paulo, Sydney, Tokyo and Washington D.C.

None of those figures are architectural. They rest on the answers given before any layer was written: what a node is, what makes an edge, and what unit the prediction is attached to. Ask the same questions of your own graph before choosing an aggregation rule.

Graph structure should demonstrate incremental value over simpler features, and the published cost of skipping the ladder is that the ranking stops carrying information. Shchur and three co-authors re-ran four prominent GNN models in 2018, under one common, fairly tuned protocol: “We perform a thorough empirical evaluation of four prominent GNN models and show that considering different splits of the data leads to dramatically different rankings of models.” Once hyperparameters and the training procedure were tuned equally for every model, the simpler architectures outperformed the more sophisticated ones. The OGB authors report the same fragility from the other direction. GNN scores on the small citation datasets — Cora, CiteSeer and PubMed, 2,700 to 20,000 nodes — are “often unstable and nearly statistically identical to each other”.

The ladder exists so that a reported gain survives that test. Build a non-graph baseline first, using node attributes and carefully engineered aggregate features. Add one-hop aggregation and see whether immediate neighborhoods add signal at all. Compare simple GNN variants — GCN-, GraphSAGE-, or attention-style layers — at matched capacity, tuned equally, since unequal tuning is precisely what reversed the ordering. Vary depth and measure both the gain and the oversmoothing that Oono and Suzuki bounded. Audit hubs and isolated nodes by inspecting performance by degree and component. Then stress the split, evaluating new nodes, new graphs, or future windows as deployment requires — the difference the OGB team measured at 8.46 percentage points on ogbg-moltox21.

A sophisticated GNN cannot rescue an invalid edge definition or a contaminated split. The two largest effects in this lesson were not architectural: 8.46 percentage points on ogbg-moltox21 came from changing the split, and 42% of the QM9 error came from changing the connectivity of a single layer. Review the graph accordingly.

Define nodes and edges, explaining what each relation means and when it becomes observable. Road segments joined where they are consecutive or share an intersection is a definition a reader can check; a similarity edge computed from the target is not. Timestamp the topology, so that future relationships cannot appear in historical training neighborhoods. Build relational baselines from degree, counts, and neighborhood aggregates before any message passing runs. Test edge ablations, removing or shuffling relation types to measure which parts of the topology actually contribute signal — the gap between 11 out of 13 QM9 targets with geometry and 5 out of 13 from topology alone is what a well-run ablation looks like. Inspect degree and component slices, evaluating hubs, isolated nodes, cold-start nodes and disconnected regions separately, because a node with no neighbors receives nothing from the mechanism the model is being credited for. Finally, specify inductive behavior: state how new nodes, new edges and new graph versions are handled. And remember the ceiling. A standard neighbourhood-aggregation GNN cannot distinguish structures beyond the 1-dimensional Weisfeiler-Leman test, so a task that requires that distinction requires a different model rather than more layers.