Message passing

A family of techniques that compute quantities on a network—such as centralities, probabilities, or model states—by propagating information (“messages”) between neighboring nodes. The following example from Newman (2023) gives the basic intuition.

Intuition: giant component#

Let $\mu_i$ be the probability that node $i$ is not in the giant connected component. Node $i$ is outside the giant component only if none of its neighbors connects it to that component, which suggests

$$\mu_i=\prod_{j\in\mathcal{N}_i}\mu_j.$$

This tempting equation fails for two reasons. First, neighboring nodes need not be independent: two neighbors connected to each other have correlated component membership. Second, a neighbor $j$ might reach the giant component only through $i$, so it cannot also be the route that connects $i$.

To remove this immediate backtracking, define the message $\mu_{i\leftarrow j}$ as the probability that $j$ is not in the giant component after $i$ is removed. Then

$$\mu_i=\prod_{j\in\mathcal{N}_i}\mu_{i\leftarrow j}, \qquad \mu_{i\leftarrow j}=\prod_{\substack{k\in\mathcal{N}_j\\k\ne i}}\mu_{j\leftarrow k}.$$

The second equation is the message-passing step: $j$ sends $i$ a summary computed from the messages arriving from all of $j$’s other neighbors. Iterating these local equations lets information propagate across the network.

Cavity-style message passing#

More generally, a cavity-style method places a message $m_{i\to j}$ on each directed edge and updates it from the messages arriving at $i$ from neighbors other than $j$:

$$m_{i\to j}=f\big(\{m_{k\to i}:k\in\mathcal{N}(i)\setminus j\}\big), \qquad b_i=g\big(\{m_{k\to i}:k\in\mathcal{N}(i)\}\big),$$

Here $f$ updates an edge message, while $g$ is the node readout: it combines all messages arriving at $i$ to recover the node-level estimate $b_i$. In the giant-component example, $f$ multiplies the messages from every neighbor except the recipient, whereas $g$ multiplies the messages from all neighbors.

For belief-propagation and cavity equations with the appropriate factorization assumptions, excluding the recipient prevents immediate backtracking and gives exact results on trees. On networks with cycles, messages may be correlated and accuracy depends on the approximation and network structure. For percolation, Allard and Hébert-Dufresne (2019) identify the random-network ensemble computed by the usual approximation, while Cantwell et al. (2023) let each node use a different approximation level to target the cost of correcting for cycles.

The classic tree-like approximation developed by Gleeson (2008) and adapted by Nematzadeh et al. (2014) can be understood as a population-averaged form of the same procedure. These papers do not formulate an edge-message algorithm on a fixed graph, so the method is not message passing in that narrow sense. Instead, it averages probabilities by degree and community on an infinite-tree approximation. Its auxiliary quantity $y_n^{A(B)}$ nevertheless has the same cavity structure as an edge message: the recursion uses the remaining $k-1$ neighbors after excluding the parent edge, and the final active fraction $\rho_\infty^{A(B)}$ is reconstructed using all $k$ neighbors.

Belief propagation is a canonical message-passing algorithm and is closely connected to the Cavity method from statistical physics (spin glasses). Message-passing equations are also used to analyze Percolation and phase transitions in networks. See also graphical models.

Neural message passing#

Neural message passing is related but distinct: a message-passing GNN applies a finite number of learned update rounds rather than solving cavity equations to a fixed point. GNN is a broader category, not a synonym for message-passing neural network (MPNN). A GNN is an MPNN when each layer updates a node by aggregating messages from its graph neighbors with a permutation-invariant operation. It can be written compactly as

$$H^{(k)}=M\left(A,H^{(k-1)};\theta^{(k)}\right),$$

where $A$ describes the graph’s connection structure, $H^{(k-1)}\in\mathbb{R}^{N\times d_{k-1}}$ contains the representations of the $N$ nodes entering layer $k$, and $\theta^{(k)}$ denotes that layer’s learned parameters. The operator $M$ updates each node by combining its current representation with information from its neighbors, producing $H^{(k)}$.

For one-hop message-passing layers on the original graph, after $K$ layers each node’s representation can depend only on nodes within $K$ graph steps. This $K$-hop blindness is therefore a limitation of local MPNNs, not of every GNN. Architectures can escape it through global attention, global spectral operations, higher-order states defined on tuples or subgraphs, or graph transformations such as adding long-range edges, rewiring, and coarsening. Some of these architectures can still be described as message passing on a complete or augmented graph, but then their horizon is no longer determined by distance in the original graph.

Under a restrictive definition based on layered linear spectral filters, Vasileiou et al. (2026) show that spectral and spatial GNNs have largely equivalent expressive power, while emphasizing the complementary strengths of the two perspectives. Pao-Huang et al. (2026) propose propagating over negative (absent) edges as a dissimilarity signal rather than ignoring them.

References#

• Newman, Message passing methods on complex networks (2023): broad review of message-passing methods, applications, limitations, and connections to network phase transitions.
• Gilmer et al., Neural Message Passing for Quantum Chemistry (2017): introduces the Message Passing Neural Network framework that unifies several neural models for graphs.