Message Passing Neural Networks (MPNN)

Unified MPNN view, 1-WL test, expressiveness limits, higher-order GNNs, graph Transformers

A caffeine molecule has 24 atoms (nodes) and 25 bonds (edges). Task: predict whether it is toxic. Each atom has features — element type, charge, hybridization. Each bond has features — single, double, or aromatic. A standard MLP on a feature vector per atom would ignore the molecular structure entirely. You need a model that propagates information through the chemical graph.

Message passing is the mechanism. In each round, every atom sends its representation to its bonded neighbors. Every atom aggregates messages from its neighbors and updates its representation. After K rounds, each atom's representation encodes its K-hop chemical environment — the atoms within K bonds of it. A readout function aggregates all atom representations to a molecular property prediction. After 3 rounds, the nitrogen in caffeine's ring "knows" what the carbons 3 bonds away look like. This structural awareness is what makes the model useful.

GCN, GAT, and GraphSAGE look different architecturally, but they are all instances of the same three-step pattern: compute messages, aggregate at nodes, update node states. This unification — the MPNN framework (Gilmer et al., 2017) — also reveals a hard ceiling: no MPNN can be more powerful than the 1-dimensional Weisfeiler-Leman graph isomorphism test. Mean-aggregation GNNs like GCN are strictly below even that ceiling. GIN with sum aggregation reaches the 1-WL ceiling. For most node classification tasks on social networks, this ceiling rarely matters. For molecular chemistry where ring structure determines chemical properties, it matters a great deal.

NOT this. "Message passing requires a fixed number of rounds K." In practice K = 3–6 works for most molecular property prediction tasks, matching the chemical neighborhood relevant to properties. More rounds cause over-smoothing: all nodes converge to similar representations as information propagates through the entire graph, and individual atom identities are lost. The right K depends on the task's relevant locality — drug toxicity depends mostly on functional groups within 3–4 bonds, not the entire molecule. Long-range interactions in protein folding require a different architecture (graph Transformers) rather than more message-passing rounds.

Key points

• MPNN framework (Gilmer et al., 2017): three phases per layer. (1) Message: m_{vw}^t = M_t(h_v^t, h_w^t, e_{vw}) — compute a message for each directed edge using source features, target features, and edge features. (2) Aggregate: a_v^t = Σ_{w∈N(v)} m_{vw}^t — collect all incoming messages with a permutation-invariant function. (3) Update: h_v^{t+1} = U_t(h_v^t, a_v^t) — update node state from previous state and aggregated messages. GCN, GAT, and GraphSAGE are all instances of this framework with different M, aggregate, and U choices.
• 1-Weisfeiler-Leman (1-WL) test: algorithm for deciding if two graphs are isomorphic. Each node starts with a color (hash of its label). At each step: new color = hash(current color, sorted multiset of neighbor colors). Repeat until stable. Two graphs are distinguished if they produce different final color histograms. 1-WL is the formal upper bound on what any MPNN can express — an MPNN that is 1-WL equivalent can distinguish any pair of graphs that 1-WL can distinguish, and fails on any pair 1-WL cannot.
• GIN (Graph Isomorphism Network, Xu et al. 2019): the maximally expressive MPNN. Key theorem: a GNN reaches the 1-WL upper bound if and only if its aggregation function is injective over multisets. GIN achieves this with: h_v^{l+1} = MLP((1+ε)h_v^l + Σ_{u∈N(v)} h_u^l). The (1+ε) term ensures the self-embedding and neighbor sum combine injectively. Sum aggregation is injective (different multisets map to different sums); mean is not ({1,2,3} and {1,1,4} have the same mean of 2).
• 1-WL failure cases matter for chemistry: regular graphs — all k-regular graphs with the same node count look identical to 1-WL because every node has the same degree and identical 1-hop neighborhood structure. Cycles: 1-WL cannot distinguish a 3-cycle + 3-cycle (two disconnected triangles) from a 6-cycle. In chemistry, these correspond to molecules with the same atom types and degree sequence but different ring structures — directly limiting GNN accuracy for property prediction of cyclic compounds.
• Higher-order WL and GNNs: k-WL tests work on k-tuples of nodes rather than individual nodes, achieving exponentially greater expressiveness. k-GNN computes messages between k-tuples. DS-GNN and PPGN approximate higher-order expressiveness with better scalability. For most real-world node classification and link prediction tasks, 1-WL expressiveness is sufficient — the graphs that fool 1-WL rarely appear in social or transactional graphs.
• Structural features can be precomputed and added as node features to augment GNN expressiveness beyond 1-WL: degree, triangle count, clustering coefficient, eigenvector centrality, betweenness centrality. These encode structural information that message passing cannot extract from features alone. Random positional encodings can also break the symmetry that causes 1-WL failures — giving each node a unique identity breaks regular graph symmetry at the cost of losing permutation equivariance.
• Graph Transformers apply self-attention to all pairs of nodes rather than only connected pairs. Every node attends to every other node — O(|V|²) complexity. This exceeds 1-WL expressiveness because attention sees all pairwise relationships simultaneously. Graphormer achieves SOTA on molecular benchmarks. GPS combines local MPNN with global Transformer attention at tractable cost. For small molecular graphs (≤100 atoms), O(|V|²) is feasible; for social networks with millions of nodes, it is not.
• Over-squashing: information from distant nodes must be compressed through narrow topological bottlenecks. In a tree-like graph, the single bridge node between two subtrees must carry all cross-subtree information — gradients vanish through the bridge, making the model insensitive to distant but relevant nodes. Symptom: removing distant node features doesn't change predictions. Fixes: graph rewiring (add shortcuts), virtual nodes (one global node connected to all others), or graph Transformers that bypass topological constraints entirely.

Recap

• MPNN = 3 phases/layer: message $M_t(h_v,h_w,e_{vw})$ → aggregate (permutation-invariant) → update $U_t$. GCN/GAT/GraphSAGE are all instances.
• 1-WL test is the hard ceiling: no MPNN can distinguish graphs 1-WL can't. Formal upper bound on expressiveness.
• GIN reaches 1-WL iff aggregation is injective: sum is injective, mean is not ({1,2,3} and {1,1,4} share mean 2).
• 1-WL fails on regular graphs and cycles — two triangles vs a 6-cycle look identical; matters for molecular ring structure.
• Beyond 1-WL: k-WL/k-GNN, graph Transformers (all-pairs attention, O(|V|²)), or precomputed structural features (degree, triangle count).
• K = 3–6 rounds matches relevant locality; more rounds → over-smoothing, node identities lost.
• Over-squashing: distant info compressed through topological bottlenecks → vanishing gradients; fix with rewiring/virtual nodes.

Check your understanding