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 · 3 min read
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.
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 - search for Message Passing.
Related concepts
Graph Attention Network
A GNN variant that learns to assign different importance weights to different neighbours during aggregation - letting the model focus on the most relevant connections rather than treating all neighbours equally.
Graph Convolutional Network
The foundational GNN architecture that adapts convolutional operations to graph-structured data by treating each node's new representation as a weighted sum of its own features and its neighbours' features - making deep learning on graphs tractable.
Graph Neural Network
A class of deep learning models designed to operate directly on graph-structured data - learning representations that capture both the features of individual nodes and the structural relationships between them.