Concept
Message Passing
The computational paradigm underlying virtually all modern graph neural networks - iteratively passing information between neighbouring nodes and updating representations based on aggregated neighbourhood messages.
Added May 18, 2026
Message passing is the unifying framework for describing how graph neural networks compute node representations. Rather than being a specific algorithm, it is a computational paradigm: a description of the general form that GNN layers take. Understanding message passing is understanding the essence of how GNNs work.
The message passing paradigm describes each GNN layer as two steps. In the message step, for each edge (u, v), a message m_uv = phi(h_u, h_v, e_uv) is computed, where h_u and h_v are the current node features of the source and target nodes, e_uv is an optional edge feature, and phi is a learnable message function. In the aggregation and update step, each node v collects all incoming messages from its neighbours N(v), aggregates them into a single vector a_v = AGG({m_uv | u in N(v)}), and updates its representation: h'_v = psi(h_v, a_v), where psi is a learnable update function.
Different GNN architectures correspond to different choices of phi, AGG, and psi. GCN: phi is a linear transformation, AGG is degree-normalised sum, psi concatenates with self-features. GAT: phi computes attention weights, AGG is an attention-weighted sum. GraphSAGE: phi is identity, AGG is max-pooling or LSTM, psi concatenates and applies a linear transformation. GIN: phi is identity, AGG is sum (the most expressive choice), psi applies an MLP. The message passing neural network (MPNN) framework from Gilmer et al. (2017) formalised this unified view.
Edge features can be incorporated into message functions, allowing richer information passing in graphs where edges represent qualitatively different types of relationships (e.g., different bond types in molecular graphs, different relationship types in knowledge graphs).
The expressive power of message passing GNNs is bounded by the Weisfeiler-Lehman (WL) graph isomorphism test: a GNN using sum aggregation is at most as powerful as the 1-WL test at distinguishing non-isomorphic graphs. GIN was specifically designed to match this upper bound. To go beyond 1-WL expressivity, higher-order GNNs or subgraph-based methods are needed, at greater computational cost.
The message passing abstraction also connects GNNs to other structured inference algorithms: belief propagation in probabilistic graphical models, the graph kernel methods of earlier ML for graphs, and even the attention mechanism in Transformers (which can be viewed as message passing on a fully connected graph with attention-weighted messages).
Analogy
Rumour spreading through a social network, but with computation replacing gossip. Each person (node) has some private information (features). In each round (layer), everyone shares their information with their immediate contacts (message passing), each person integrates what they heard from their contacts with what they already know (aggregation and update), and a new, richer shared understanding emerges. After several rounds, each person's knowledge reflects not just their own original information but the synthesised knowledge of their extended neighbourhood.
Real-world example
In AlphaFold 2's EvoFormer, a message passing-style operation propagates information through the residue pair representation matrix. Each pair of residues exchanges information with other pairs that share a residue, iteratively building up an understanding of the 3D geometric relationships consistent with the multiple sequence alignment. This graph-based reasoning over residue interactions is central to AlphaFold 2's ability to predict protein structure.
Why it matters
Message passing is the conceptual core of all GNNs. Understanding it enables reasoning about the expressive power of any GNN (which graph structures it can and cannot distinguish), the computational complexity (how message passing complexity grows with graph size), and how to design GNN architectures for specific problems (which aggregation functions suit which types of relational reasoning). It provides the vocabulary for reading and understanding the GNN literature.
In the news
No recent coverage - check back later.
Related concepts