Message-Passing Neural Networks

The message-passing framework describes most graph neural networks as three steps: compute messages on edges, aggregate them at nodes, and update node states.

A unifying abstraction

Message-passing neural networks (MPNNs) give a single vocabulary for graph learning. Each layer runs three operations. First, a message function computes a message on every edge from the features of its two endpoints and any edge attributes. Second, each node aggregates the messages arriving from its neighbors with a permutation-invariant operator. Third, an update function combines a node's current state with the aggregated message to produce its new state. Many named architectures are just particular choices of these three functions.

The three functions

• Message: m_ij = M(h_i, h_j, e_ij), often a small MLP or linear map
• Aggregate: sum, mean, or max over incoming messages, which must be order-independent
• Update: h_i' = U(h_i, aggregated_message), often a GRU cell or MLP

Sum aggregation preserves the most structural information and is provably more expressive than mean or max for distinguishing graph structures, but mean is more stable when node degrees vary widely. The choice is a genuine design decision, not a detail.

Expressive power

The discriminative power of standard MPNNs is bounded by the Weisfeiler-Lehman graph isomorphism test: two graphs the WL test cannot tell apart will receive identical representations. This explains why plain message passing cannot count certain substructures, and it motivates additions such as positional encodings, edge features, and higher-order schemes that push past the WL limit.

for layer in range(L):
    messages = message_fn(h[src], h[dst], edge_attr)   # per edge
    agg = scatter_sum(messages, dst, dim_size=N)        # per node
    h = update_fn(h, agg)

Why the framing matters

Seeing graph convolution and graph attention as message-passing variants makes their differences precise: they choose different message and aggregation functions. The abstraction also guides new designs, since improving any of the three functions, or the way readouts pool node states into a graph-level vector, is a clear axis for research. Global readouts turn node states into a single vector for graph classification or regression.