Graph Neural Networks and Message Passing

A molecule is not a sequence and not a grid. Its atoms have no canonical order, so a model that reads them as a list must either learn to ignore the ordering or be handed a permutation-invariant architecture. Graph neural networks are the second option: they build node representations by repeatedly aggregating information from neighbours, an operation that does not depend on how the nodes are numbered. Almost every architecture in this space is a special case of one template (Gilmer et al., 2017, Neural Message Passing for Quantum Chemistry, arXiv:1704.01212).

The primitive

At layer \(k\), every node \(v\) collects messages from its neighbourhood \(\mathcal{N}(v)\), pools them with a permutation-invariant function, and updates its own state:

The design space is the choice of those two functions. GCN uses a degree-normalised mean followed by a linear layer and a nonlinearity, which is cheap and scales linearly in edges (Kipf and Welling, 2016, arXiv:1609.02907). GraphSAGE samples a fixed number of neighbours so cost does not blow up on hub nodes (Hamilton et al., 2017, arXiv:1706.02216). GAT computes attention coefficients over neighbours instead of fixed weights (Veličković et al., 2017, arXiv:1710.10903). After \(K\) layers each node has seen its \(K\)-hop neighbourhood, and a readout (sum, mean, or attention pooling over all nodes) produces a graph-level vector when the task is graph-level.

The expressive ceiling

Message passing with these aggregators is provably no more discriminative than the one-dimensional Weisfeiler-Lehman graph isomorphism test. Two non-isomorphic graphs that WL cannot separate will receive identical embeddings from any such GNN, no matter how many parameters or layers you add. The proof also gives the recipe for reaching that ceiling: the aggregator must be injective on multisets, which mean and max are not and sum is, giving the Graph Isomorphism Network (Xu et al., 2018, How Powerful are Graph Neural Networks?, arXiv:1810.00826).

This has a practical consequence: a plain GNN cannot count triangles or distinguish certain regular graphs, which matters for molecules where ring structure is chemically meaningful. Common repairs are to inject structural features (cycle counts, distance encodings) as node attributes, or to move to a graph transformer where attention is global and structure enters through positional encodings.

Depth does not work the way it does elsewhere

Two failure modes attack from opposite directions and together explain why most production GNNs are two to four layers deep.

Oversmoothing. Repeated neighbourhood averaging is a low-pass filter. As layers accumulate, node representations within a connected component converge toward each other, and past some depth every node looks the same, which destroys exactly the discriminative signal a node-classification head needs (Li et al., 2018, arXiv:1801.07606).

Oversquashing. To capture a dependency between nodes \(K\) hops apart you need \(K\) layers, but the number of nodes within \(K\) hops grows exponentially in most real graphs. All that information is compressed into one fixed-size vector, and long-range signal is squashed out (Alon and Yahav, 2020, On the Bottleneck of Graph Neural Networks, arXiv:2006.05205). Graph rewiring, adding virtual nodes, and attention over the full graph are the standard responses, each trading the sparsity that made GNNs cheap.

Where they earn their keep

The strongest results are in the sciences, where the graph is not a modelling convenience but the actual object: interatomic potentials that reach near-quantum accuracy at classical cost, crystal-stability screening that expanded the set of known stable inorganic materials by a large factor in the GNoME work, and the evolutionary and structural graphs inside protein-structure prediction. Industrial recommendation is the other large deployment, where the bipartite user-item graph is billions of edges and the engineering problem is sampling and sharding rather than architecture.

When it breaks

• Neighbour explosion in training. Full-batch training is impossible past a few million edges; sampling introduces variance, and the sampled subgraph may not contain the structure the label depends on.
• Heterophily. GCN-style smoothing assumes neighbours share labels. On graphs where they systematically do not, such as fraud rings that deliberately connect to legitimate accounts, plain aggregation actively removes signal.
• Dynamic graphs. Most of the literature assumes a static graph. Handling edges that appear and vanish requires either recomputation or a temporal model, and the standard benchmarks do not measure it.
• The benchmark suite is small and leaky. Cora, Citeseer, and PubMed are tiny, and reported gains on them frequently fail to reproduce under standardised splits.