Graph Neural Networks and Message Passing

How you define an edge changes which evidence can travel. Nothing in the raw data announces what a node is. A person picks, and the pick fixes what the model will ever be able to see.

Google Maps made that pick in production, and its nodes are not intersections. Each node is a road segment. Two segments get an edge when they are connected. A run of connected segments along a typical traffic route is a Supersegment, written as a graph S = (S, E), and extended Supersegments hang extra off-route nodes on the side. Seventeen authors described the deployed ETA model in 2021. The textbook road graph — intersections as nodes, roads as edges — was available to them. It is the choice they did not make.

The consequences of the choice were measured, not asserted. Against the previous production baseline, the deployed GNN significantly reduced negative ETA outcomes, above 40% in cities like Sydney. DeepMind's own post on the collaboration put it in accuracy terms in 2020: “Researchers at DeepMind have partnered with the Google Maps team to improve the accuracy of real time ETAs by up to 50% in places like Berlin, Jakarta, São Paulo, Sydney, Tokyo, and Washington D.C.” That improvement was won against a baseline already accurate for over 97% of trips.

For each edge, a message function combines sender, receiver, and edge information. An aggregation function summarizes incoming messages without depending on neighbor order. An update function combines the aggregate with the current node state. After several layers, a readout can produce node, edge, pair, or whole-graph predictions.

Order-independence is not a free virtue. It is paid for, and two separate groups priced it in 2019. Xu and three colleagues showed that neighbourhood-aggregation GNNs are at most as discriminative as the Weisfeiler-Lehman graph isomorphism test, and that GCN and GraphSAGE cannot distinguish certain simple graph structures. Morris and six colleagues fixed the level exactly: “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.”

The practical reading is blunt. If two graphs your task must separate look identical to the 1-dimensional Weisfeiler-Leman heuristic, no width, no depth and no amount of training will separate them. The four-operation recipe cannot represent the difference. The response is a change of representation — richer node or edge features, higher-order or positional information. Not a longer training run.

The same learned functions are reused across nodes and edges of different graph sizes. One layer runs the cycle once. Construct edge messages: compute the information sent along each permitted relationship. Aggregate by receiver: sum, mean, max, attention, or another invariant operator combines neighbors. Update the node state: merge neighborhood evidence with the previous representation.

Repeating the cycle expands the receptive field by roughly one hop per layer, and a readout turns the resulting node states into local, relational, or graph-level outputs. Every one of those steps is a place where the modeling choices of the previous section — direction, edge type, time — decide what is allowed to move.

The split must match whether new nodes, edges, or whole graphs will appear. Transductive node prediction shares one graph between training and test, so unlabeled test nodes still influence propagation. Inductive node prediction must handle unseen nodes or subgraphs with reusable aggregation functions. Whole-graph prediction treats each example as a separate graph and needs graph-level pooling. Link prediction scores missing or future relations, where negative sampling and temporal splits decide the result.

The first two rows have a citable origin. GraphSAGE, published in 2017, opened with a complaint. “Most existing approaches require that all nodes in the graph are present during training of the embeddings; these previous approaches are inherently transductive and do not naturally generalize to unseen nodes.” It instead learns “a function that generates embeddings by sampling and aggregating features from a node’s local neighborhood”. It is tested on citation and Reddit graphs. It is tested as well on “a multi-graph dataset of protein-protein interactions” whose test graphs it has never seen.

The remaining rows now come with a price list. The Open Graph Benchmark, built in 2020, splits by domain rather than at random: molecules by two-dimensional scaffold, citation graphs by time. ogbn-arxiv and ogbn-papers100M train on arXiv papers published up to 2017, validate on 2018, and test on 2019 onwards. These are not toy graphs. ogbn-arxiv carries 169,343 nodes and 1,166,243 edges. ogbn-papers100M carries 111,059,956 nodes and 1,615,685,872 edges.

The honest split costs measurable accuracy, and the cost is published. On a random split of ogbg-molhiv the best GIN reaches 82.73±2.02% ROC-AUC, 5.66 percentage points above its scaffold-split score. On ogbg-molpcba it reaches 34.40±0.90% AP, 7.37 points above scaffold. On ogbg-moltox21 it reaches 86.03±1.37% against 77.57±0.62% under the scaffold split, a gap of 8.46 points. Scaffold splitting itself came from MoleculeNet, a benchmark covering over 700,000 compounds, and its authors said what it was for: “Since scaffold splitting attempts to separate structurally different molecules into different subsets, it offers a greater challenge for learning algorithms than the random split.” Those percentage points are not performance lost by splitting honestly. They are performance the random split was never entitled to report.

A GNN should beat baselines that use the same legal information without message passing. Validate the graph construction first — direction, types, duplicates, time, missing edges, identity resolution. Then compare node-only models and engineered neighborhood summaries; ablate edges and relation types; slice by degree and distance; and monitor similarity, gradient flow and performance as depth increases.

Step two is the one that gets skipped, and it is the one that GNNs regularly lose. Errica and three colleagues ran more than 47,000 controlled experiments over five GNNs and nine benchmarks. On D&D, PROTEINS and ENZYMES no GNN beat their structure-agnostic baseline. The baseline scored 78.4±4.5 on D&D against 76.6±4.3 for DGCNN, 75.8±3.7 on PROTEINS against 73.7±3.5 for DiffPool, and 65.2±6.4 on ENZYMES against 59.6±4.5 for GIN. Among the four chemical benchmarks only on NCI1 was the baseline clearly outperformed (GIN 80.0±1.4 against baseline 69.8±2.2). On the social benchmarks the graph did pay: GIN 89.9±1.9 against baseline 82.2±3.0 on REDDIT-BINARY with degree features. Their own summary: “Moreover, by comparing GNNs with structure-agnostic baselines we provide convincing evidence that, on some datasets, structural information has not been exploited yet.”

A second group found the same thing on its own. On DD and PROTEINS, six authors report in the Journal of Machine Learning Research, the graph-agnostic MLP baselines perform as well as GNNs. Re-running the identical 10-fold protocol with a different seed changed the model ranking. So the node-only baseline is not a formality you clear before the interesting result. On some datasets it is the result. And a ranking that flips with the random seed is not a finding at all.

Over-smoothing makes node representations increasingly similar after repeated mixing. Over-squashing compresses information from a rapidly growing neighborhood through limited-dimensional states or narrow graph cuts. Both have a named origin, and both have been proved rather than merely observed.

Over-smoothing was named in 2018, and traced to the model's own working principle taken too far: “First, we show that the graph convolution of the GCN model 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.” Oono and Suzuki then proved the asymptotic version in 2019. Under conditions set by the spectra of the augmented normalized Laplacian, a GCN's output exponentially approaches a set of signals carrying only connected-component and node-degree information for distinguishing nodes. Depth does not erode distinction gently. At the limit the network can tell nodes apart only by which component they sit in and how many neighbors they have.

Over-squashing is the opposite complaint, and it comes with a measurement. Alon and Yahav named it in 2020: “This bottleneck causes the over-squashing of exponentially growing information into fixed-size vectors.” On their synthetic NeighborsMatch benchmark, GCN's training accuracy at problem radius r=4 is 70%. That is a failure to fit data it has already seen, on a task with a known answer. At r=5 every GNN tested fails to fit the training data perfectly. Their fix is topological rather than dimensional. Turning a single layer of an already-tuned model into a fully-adjacent layer reduces the QM9 error rate by 42% on average across six GNN types. Doubling the hidden dimensions instead yields only 5.5% improvement.

A 2023 proof then ordered the remedy list instead of leaving it flat. Six authors formalised the phenomenon: width can mitigate over-squashing, depth cannot, and over-squashing occurs between nodes at high commute time. Rewiring, selective long-range edges and hierarchical pooling attack topology and commute time, which is where the failure lives. Extra width can help. Extra layers are provably not the answer, and they make the other failure worse. Diagnose which of the two you have before changing the architecture.