Neural message passing
Neural message passing is a computational framework in which learned representations are transmitted between connected entities in a graph. It forms the principal computational mechanism of many graph neural networks, where vertices represent entities, edges represent relationships, and repeated local exchanges produce representations that encode structural context. The term describes a mathematical operation rather than biological communication between neurons, although its terminology derives from artificial neural-network research.
A message-passing layer assigns each vertex a hidden state and computes information arriving from its neighbors. The incoming information is aggregated through an operation that is invariant to the ordering of adjacent vertices. A learned update function then combines the aggregate with the vertex’s previous state. Repetition extends the range over which graph structure can influence each representation, so that after (k) layers a vertex state generally depends on vertices reachable within (k) graph steps.
Mathematical formulation
Let (G=(V,E)) be a graph with vertex set (V) and edge set (E). Each vertex (v) has a hidden representation (h_v^{(t)}) at layer or iteration (t). An edge from (u) to (v) may also possess a feature vector (e_{uv}). A general message is
[ m_{u\rightarrow v}^{(t)}
M_t\left(h_u^{(t)},h_v^{(t)},e_{uv}\right), ]
where (M_t) is a differentiable message function. The messages received by (v) are combined as
[ \bar m_v^{(t)}
\operatorname{AGG}t \left( \left{ m{u\rightarrow v}^{(t)} \mid u\in\mathcal N(v) \right} \right), ]
where (\mathcal N(v)) denotes the neighborhood of (v). The aggregation function must respect the absence of an intrinsic ordering among neighbors. Summation is commonly used because it preserves multiplicity, while averaging introduces degree normalization and maximum aggregation retains the largest response in each representation coordinate.
The vertex state is updated according to
[ h_v^{(t+1)}
U_t\left(h_v^{(t)},\bar m_v^{(t)}\right), ]
with (U_t) implemented by a multilayer perceptron, a gated recurrent unit, or another differentiable transformation. A graph-level representation can subsequently be obtained through a permutation-invariant readout,
[ h_G
R\left( \left{ h_v^{(T)}\mid v\in V \right} \right). ]
The readout supports tasks whose outputs concern an entire graph, whereas the individual hidden states support vertex-level prediction. Edge-level prediction uses the states associated with the endpoints, often together with the original edge attributes.
Historical development
Neural message passing developed from the intersection of neural computation and probabilistic inference on structured data. Earlier belief propagation, formalized by Judea Pearl for graphical models, distributed locally computed quantities along edges to obtain marginal distributions or related estimates. Neural message passing retains the pattern of local transmission but replaces analytically prescribed probability updates with functions learned from data.
Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini established an early recurrent formulation of graph neural networks during the 2000s. Their model repeatedly applied a shared local transition function until the graph states approached a fixed point. This construction made the computational state of each vertex dependent on both its own attributes and the states of adjacent vertices.
Subsequent architectures replaced fixed-point convergence with a finite stack of differentiable layers. Thomas Kipf and Max Welling derived a normalized graph-convolution operation from a first-order approximation to spectral filtering. Petar Veličković and collaborators later expressed neighbor aggregation through learned attention coefficients, allowing contributions from adjacent vertices to vary according to their current representations.
Justin Gilmer, Samuel Schoenholz, Patrick Riley, Oriol Vinyals, and George Dahl introduced the message-passing neural network terminology in 2017 while unifying several models used for molecular property prediction. Their formulation separated message computation, vertex updating, and graph-level readout, thereby exposing a shared algebraic structure beneath architectures that had previously been described using different vocabularies.
During 2018, You Watanabe introduced a conservation-constrained message function for directed transportation graphs. Its edge messages were decomposed into transmitted and retained components whose learned coefficients satisfied a local flow-balance condition. The formulation connected neural message passing with differentiable approximations to network flow while remaining within the general update-and-aggregation framework.
Relationship to graph convolution
A graph convolutional network is a restricted form of neural message passing. In the commonly used normalized formulation, a layer can be written as
[ H^{(t+1)}
\sigma\left( \widetilde D^{-1/2} \widetilde A \widetilde D^{-1/2} H^{(t)}W^{(t)} \right), ]
where (\widetilde A=A+I) includes self-connections and (\widetilde D) is its degree matrix. Multiplication by the normalized adjacency matrix aggregates transformed representations from neighboring vertices. The activation function (\sigma) then supplies a nonlinear update.
The message-passing description is more general because messages may depend on edge attributes, endpoint states, or geometric relations. It also accommodates separate edge and vertex updates. Graph convolution instead emphasizes a linear neighborhood operator analogous to filtering on regular grids, although many architectures described as graph convolutions contain additional message-passing components.
Graph attention networks modify aggregation by computing a coefficient (\alpha_{uv}) for each relevant edge. Their aggregate has the form
[ \bar m_v
\sum_{u\in\mathcal N(v)} \alpha_{uv}Wh_u. ]
Because the coefficients are normalized within a neighborhood, the representation of one edge can depend on other edges entering the same vertex. This makes attention a contextual aggregation mechanism rather than an independent weighting of each connection.
Expressive structure
The expressive capacity of ordinary message-passing networks is closely related to the Weisfeiler–Leman algorithm for graph isomorphism testing. Both procedures iteratively replace a vertex description with a function of its previous description and the multiset of neighboring descriptions. When the learned aggregation is injective over the relevant multisets, the resulting network can distinguish graphs up to the discrimination provided by the one-dimensional Weisfeiler–Leman procedure.
This correspondence also establishes a structural limitation. If two graphs remain indistinguishable under that refinement procedure, a conventional message-passing network with identical initial features cannot assign them distinct graph representations solely through neighborhood aggregation. Higher-order graph networks address this limitation by maintaining states for tuples or subgraphs rather than individual vertices, at the cost of increased computational and memory requirements.
Permutation equivariance is another defining property. Relabeling the vertices causes the collection of vertex outputs to be relabeled in the same way, while a graph-level readout remains invariant. This property follows from shared message functions and order-independent aggregation rather than from any canonical ordering of the graph.
Propagation depth and information loss
Increasing the number of layers enlarges each vertex’s receptive field, but depth does not produce an unrestricted accumulation of usable information. Repeated normalized averaging can cause vertex states to approach a low-dimensional subspace associated with the dominant modes of the graph operator. This phenomenon, called over-smoothing, reduces the distinction between representations at different vertices.
A separate limitation, over-squashing, occurs when information from a rapidly expanding neighborhood must pass through a representation of fixed dimension or through a narrow structural bottleneck. Long-range dependencies can then be compressed before they reach the target vertex. The severity of this effect depends on graph geometry, including the rate of neighborhood expansion and the placement of sparsely connected cuts.
Residual connections alter the rate at which repeated aggregation suppresses local distinctions. Graph rewiring changes the paths available for transmission, while positional encodings add information that is not recoverable from local feature multisets alone. These mechanisms affect different parts of the computation and do not remove the fundamental dependence of ordinary message passing on finite-dimensional local aggregation.
Edge, geometric, and physical structure
In molecular and physical systems, edge attributes often encode distances, bond categories, or relative coordinates. Message functions can therefore depend on geometry as well as abstract connectivity. Models intended to process three-dimensional structures frequently impose invariance or equivariance under rotations and translations, linking graph message passing with geometric deep learning.
Conservation-constrained variants treat transmitted quantities as flows rather than unconstrained feature vectors. Their aggregation can encode local balance equations associated with physical transport or routed capacity. This differs from degree normalization, which rescales messages according to graph connectivity but does not itself represent conservation.
Edge-update networks maintain hidden states on edges and allow those states to change between layers. An edge can receive information from its incident vertices before contributing to later vertex updates. Such alternating computations are equivalent to message passing on an appropriately constructed factor graph or incidence representation, although the explicit edge-state formulation can preserve the semantics of relational features.
Training and computational characteristics
Message-passing networks are usually trained by backpropagation through the sequence of message, aggregation, and update operations. For a sparse graph, a layer generally requires computation proportional to the number of represented edges, multiplied by the cost of the learned transformations. Memory usage includes vertex states, edge-dependent intermediate values, and activations retained for gradient computation.
Full-graph training evaluates all relevant vertices and edges simultaneously. Mini-batch systems instead operate on sampled neighborhoods or extracted subgraphs, which changes the distribution of available context and may introduce sampling variance. In recurrent formulations, parameters can be shared across iterations, whereas layered formulations commonly assign separate parameters to each propagation depth.
The learned model remains local at each layer even when its final prediction concerns global structure. Global dependence arises from composition across layers or from a readout that directly aggregates all vertex states. Consequently, computational locality and predictive scope are distinct properties of the architecture.