Message Passing on Graphs

A graph $G = (V, E)$ has nodes $v \in V$, each carrying a feature vector $h_v^{(0)} \in \mathbb{R}^{d_0}$ (e.g., atom type, user profile, word embedding), and edges $(u, v) \in E$, optionally carrying their own features $e_{uv}$. Message passing is a computational scheme in which each node's representation is updated, layer by layer, as a function of its own previous representation and the representations of its neighbors $\mathcal{N}(v) = \{u : (u,v) \in E\}$. Formally, layer $k$ computes

Three roles matter here, and they generalize the "receptive field" language of convolutional networks:

• MESSAGE is a learned function applied per edge, typically an MLP or linear map on the concatenation (or difference) of the two endpoint features and the edge feature. It plays the role of a convolution's filter, but instead of a fixed spatial kernel it is applied identically to every edge regardless of how many neighbors a node has.
• AGGREGATE collapses a set of incoming messages — of variable, unknown size — into one fixed-size vector. Because a node's neighbors have no natural ordering (there is no "top" or "left" neighbor the way a pixel grid has), this function must be permutation-invariant: reordering the messages must not change the result. Sum, mean, max, and softmax-weighted sums (attention) all satisfy this; concatenation in a fixed order does not, unless neighbors are canonically sortable.
• UPDATE combines the aggregated neighborhood signal with the node's own previous state, typically via a gated combination (GRU-style), a residual/skip connection, or a simple concatenation followed by an MLP.

Stacking $L$ such layers is exactly analogous to stacking $L$ convolutional layers: after $L$ rounds, $h_v^{(L)}$ is a function of every node within graph-distance $L$ of $v$ — its $L$-hop neighborhood. This is the graph analogue of a receptive field, except the "field" is not a fixed spatial patch but whatever the graph's actual connectivity happens to expose. When $\text{AGGREGATE}$ is instantiated as a softmax-weighted sum over neighbor messages — with weights computed from a compatibility score between $v$ and $u$ — message passing recovers graph attention, a direct graph-structured application of the Attention Mechanism; when it is instantiated as an unweighted sum with a learned linear message, it recovers the graph convolutional layer. Both are special cases of the same three-step primitive.

Concretely, running $L$ layers of message passing over an entire graph proceeds as follows. Note that all nodes update synchronously within a layer — layer $k$'s messages always use layer $(k-1)$'s representations, never a mixture of old and new, so the computation is well-defined and order-independent across nodes. ``` Input: graph G = (V, E) initial node features h[v] for v in V (h_v^(0)) optional edge features e[u, v] for (u, v) in E number of layers L learned functions MESSAGE_k, AGGREGATE_k, UPDATE_k for k = 1..L Output: node representations h[v] after L rounds (h_v^(L)) for k = 1 to L:

# --- Phase 1: compute messages on every edge, using LAST layer's states --- for each edge (u, v) in E: msg[u -> v] = MESSAGE_k(h[v], h[u], e[u, v])

# --- Phase 2: aggregate incoming messages per node --- for each node v in V: incoming = { msg[u -> v] : u in N(v) } agg[v] = AGGREGATE_k(incoming) # permutation-invariant reduction

# (if N(v) is empty, use a fixed default,

# e.g. agg[v] = 0, or h[v] itself)

# --- Phase 3: update every node's state, using OLD state + new aggregate --- for each node v in V: h_new[v] = UPDATE_k(h[v], agg[v]) h = h_new # commit synchronously: no node uses a partially-updated layer return h ``` Two implementation details matter for correctness. First, phases 2 and 3 must read `h` (the layer-$(k-1)$ values) throughout phase 1 and 2 — computing `agg[v]` must never see an already-updated `h[u]` from the same layer, or the result becomes order-dependent on how nodes happen to be iterated, breaking the guarantee that the whole layer is a well-defined function of the previous layer alone. Second, isolated nodes (empty neighborhoods) need an explicit default for `AGGREGATE`, since summation and mean are undefined (or division-by-zero) over the empty set; the standard convention is to treat the aggregate as the zero vector, or to add a self-loop so every node is its own neighbor. In vectorized form (as implemented in practice), the whole layer is a sparse matrix operation. Let $H^{(k-1)} \in \mathbb{R}^{|V| \times d}$ stack all node states as rows, and let $A$ be the (possibly normalized) adjacency matrix. A basic graph-convolutional layer computes

where $D$ is the degree matrix of $A + I$ (adding self-loops so each node aggregates its own previous state too) and $W^{(k)}$ is a learned weight matrix shared across all nodes. Here $\hat A H^{(k-1)}$ is the aggregate-message step (a normalized sum over neighbors, done for all nodes simultaneously via one sparse matrix multiply), and $W^{(k)}$ followed by $\sigma$ is the update/message transform. This is why message passing is efficient on real hardware: the "for each edge / for each node" loops in the pseudocode compile down to one sparse matrix–dense matrix multiplication per layer.

Time complexity. For one layer, MESSAGE is computed once per directed edge; if MESSAGE is (e.g.) a linear map of concatenated $d$-dimensional vectors followed by an activation, this costs $O(d^2)$ per edge (dominated by the weight-matrix multiply), giving $O(|E| \, d^2)$ for the message phase — or $O(|E| d)$ if the message is a simple linear transform of a $d$-vector reused across edges (as in $\hat A H W$, where the $HW$ multiply is shared). AGGREGATE is a linear scan over each node's incoming messages, so summed across all nodes it touches each edge once: $O(|E| d)$. UPDATE is applied once per node, typically another $O(d^2)$ matrix multiply, giving $O(|V| d^2)$. Total per layer:

and across $L$ layers, $O(L (|V|+|E|) d^2)$. This is linear in the size of the graph (nodes plus edges) for fixed hidden dimension and depth — the same complexity class as one pass of belief propagation or BFS with vector-valued payloads, and it is why message passing scales to graphs with millions of edges when implemented via sparse matrix multiplication on GPUs.

Space complexity. Storing all node states across layers costs $O(L \, |V| \, d)$ (or $O(|V| d)$ if only the current layer is kept, at the cost of recomputing intermediates during backpropagation). Storing per-edge messages transiently costs $O(|E| d)$. Total: $O(L(|V| + |E|) d)$, again linear in graph size.

Correctness argument — well-definedness and permutation invariance. The central thing to prove is not "the algorithm terminates" (it trivially does — $L$ fixed rounds over a fixed graph) but that the output is a well-defined function of the graph's isomorphism class and node features, independent of how nodes or neighbors happen to be indexed in memory. This matters because a graph has no canonical node ordering: two adjacency-matrix representations of the same graph, permuted by any $P$, must yield permuted-but-identical outputs. Claim: if AGGREGATE is a permutation-invariant function of the multiset of incoming messages (sum, mean, max, or a softmax-weighted sum — anything that depends only on the multiset, not on an assumed order), then $h_v^{(k)}$ depends only on $v$'s (isomorphism-invariant) rooted neighborhood structure up to depth $k$, not on node indexing. Proof sketch by induction on $k$. Base case $k=0$: $h_v^{(0)}$ is v's own feature, trivially independent of any global ordering. Inductive step: assume $h_u^{(k-1)}$ for every node $u$ depends only on $u$'s $(k-1)$-hop rooted subgraph. Then $\{\text{MESSAGE}(h_v^{(k-1)}, h_u^{(k-1)}, e_{uv}) : u \in \mathcal{N}(v)\}$ is a multiset determined entirely by $v$'s immediate neighbors and their $(k-1)$-hop histories — not by any ordering imposed on $\mathcal N(v)$ by array indices. Applying a permutation-invariant AGGREGATE to this multiset yields a value depending only on the multiset, hence only on $v$'s $k$-hop rooted subgraph. UPDATE then combines two such invariant quantities, preserving invariance. $\blacksquare$ This is precisely why concatenating neighbor features "in the order they appear in the adjacency list" is not a valid instantiation of AGGREGATE: it silently makes the model's output depend on an arbitrary index ordering, so isomorphic graphs (or the same graph with nodes relabeled) can get different outputs — a correctness bug, not just an inelegance.

Expressive power (and its limit). The above argument also exposes the ceiling on what sum/mean/max-aggregation message passing can distinguish: it is exactly as powerful as the 1-dimensional Weisfeiler-Leman graph isomorphism test. Any two nodes with identical multisets of $(k-1)$-hop neighbor labels get identical $h^{(k)}$ — so if 1-WL cannot distinguish two graphs (there exist nontrivial non-isomorphic graphs it cannot, e.g. regular graphs with the same degree sequence), no sum/mean/max message-passing GNN can either, regardless of depth or width. This is a real, provable limitation, not a training artifact — it motivates strictly more expressive variants (higher-order WL, subgraph-based methods) covered separately.

Tradeoffs. Message passing buys locality-aware, permutation-invariant, linear-time computation on arbitrary topologies — but at real costs: (1) over-smoothing — as $L$ grows, repeated averaging drives all node representations in a connected component toward the same value, exactly as repeated application of a random-walk-like operator converges to a stationary distribution; (2) over-squashing — information from an exponentially large $k$-hop neighborhood must be compressed into one fixed-size $d$-dimensional vector, so long-range signal is bottlenecked and can be exponentially attenuated by the time it reaches a fixed-size receptive field passing through low-degree/bridge edges; (3) sum/mean/max aggregation is bounded by 1-WL expressiveness, so highly symmetric substructures may become indistinguishable no matter how deep the network goes.

Consider a tiny 5-node graph — a molecule fragment abstraction — with node features being 1-D "atom weights" for simplicity (real GNNs use vectors, but a scalar trace makes the arithmetic checkable by hand): ``` Nodes: A(1.0) B(2.0) C(3.0) D(4.0) E(0.5) Edges: A-B, B-C, B-D, C-D, D-E ``` Adjacency (with self-loops added, $\hat A$-style, so every node aggregates itself too):

Take MESSAGE$(h_v, h_u) = h_u$ (identity — pass the raw neighbor value), AGGREGATE = mean, UPDATE$(h_v, m_v) = m_v$ (replace with the aggregate; this is exactly one layer of unweighted, un-normalized "graph averaging," the simplest possible instantiation).

Layer 1 — average each node with its neighbors' initial values:

Layer 2 — average each node with its neighbors' layer-1 values (this is the crucial step: use $h^{(1)}$ for everyone, not a mix of $h^{(0)}$ and $h^{(1)}$):

Notice the spread: layer 0 values range over $[0.5, 4.0]$ (spread 3.5); after layer 1, range is $[1.50, 3.00]$ (spread 1.5); after layer 2, range is $[2.00, 2.625]$ (spread 0.625) — this is over-smoothing in miniature: every additional round of neighborhood averaging on a small, well-connected graph pulls all values closer together, converging toward the graph's stationary "average" value as $L \to \infty$. A real GNN uses nonlinear MESSAGE and UPDATE functions with learned weights (so it need not converge this fast, and can in principle counteract smoothing via residual connections), but the qualitative mechanism — repeated local averaging homogenizes far-apart layers — is exactly this.

Message passing as an explicit computational abstraction traces back to belief propagation on graphical models and to early neural approaches for structured data, before crystallizing into the modern "graph neural network" framing.

Message passing underlies production systems well beyond academic benchmarks. Pinterest's PinSAGE and related industrial recommenders run message passing over billion-node user–item graphs to generate embeddings for recommendation at web scale, using sampled neighborhoods to keep the linear-time-per-layer cost tractable. DeepMind's graph-network simulators use message passing over particle/mesh graphs to learn physics — fluid dynamics, cloth, rigid-body interactions — by treating each simulation step as one round of aggregate-and-update. Drug discovery pipelines (e.g., models behind antibiotic and antiviral candidate screening) represent molecules as atom-bond graphs and use message passing to predict properties like toxicity, solubility, and binding affinity, directly exploiting the permutation invariance argued above: a molecule's predicted property must not depend on the arbitrary order atoms are listed in a file. Traffic forecasting systems (e.g., Google Maps ETA prediction) run message passing over road-segment graphs so that congestion information propagates along actual road connectivity rather than geographic proximity. Fraud and anti-money-laundering systems propagate risk scores across transaction graphs using exactly this aggregate-and-update primitive, since a node (account) is suspicious partly because of who it transacts with. All of these are instances of the same three-step computational primitive introduced here, and they set up the fuller architectural taxonomy — GCN, GraphSAGE, GAT, and message-passing neural networks as a unifying framework — developed in Graph Neural Networks: An Introduction.

:::faq[What role does the Attention Mechanism play in message passing?] Attention supplies one natural, and now very popular, instantiation of AGGREGATE. Instead of averaging or summing neighbor messages with fixed or uniform weights, a Graph Attention Network computes a learned compatibility score between a node and each neighbor (using the same query-key scoring idea as sequence attention), converts the scores to weights via softmax over the neighborhood, and takes the weighted sum of neighbor messages as the aggregate. This preserves permutation invariance (softmax over a set, not a sequence, is still invariant to reordering) while letting the model learn that some neighbors matter more than others — e.g., a strong chemical bond should be weighted more than a weak one.

Ask the tutor: How does adding an attention mechanism to AGGREGATE change the expressiveness limits of message passing, and does it break or preserve the 1-WL equivalence?