Message Passing

Message passing is the unifying recipe of graph neural networks: gather from neighbors, aggregate symmetrically, then update each node.

The three steps

Message passing describes a GNN layer as three operations repeated for every node. Message: compute a message from each neighbor, often a learned function of the neighbor's features and the connecting edge. Aggregate: combine all incoming messages with a permutation-invariant function such as sum, mean, or max. Update: produce the node's new representation from its old state and the aggregated message. This framework subsumes most graph architectures.

Formal form

Kronos motion — recipe star

For node v with neighbors N(v), the update is h_v^{k+1} = update(h_v^k, aggregate({message(h_v^k, h_u^k, e_{vu}) : u in N(v)})). The choice of message, aggregate, and update functions distinguishes one GNN from another. Graph convolution uses a normalized mean; attention networks weight neighbors; more expressive variants use sum aggregation and learned update networks.

Why symmetric aggregation

Neighbors have no natural order, so the aggregation must give the same output regardless of how they are listed. Sum, mean, and max all satisfy this. The choice affects expressive power: sum can count and distinguish multiset sizes, mean captures proportions, and max captures the most salient neighbor. Sum aggregation, used in the Graph Isomorphism Network, is provably the most discriminative of the three.

python

import numpy as np
def mp_layer(H, adj, W_msg, W_upd):
    # H: node features, adj: adjacency matrix
    messages = H @ W_msg
    agg = adj @ messages                 # sum over neighbors
    return np.maximum(0, H @ W_upd + agg) # update

Depth and receptive field

Each message-passing layer extends a node's view by one hop. After k layers, a node's representation depends on its entire k-hop neighborhood, analogous to how the receptive field grows with depth in a CNN. Too few layers miss relevant structure; too many cause over-smoothing, where repeated averaging makes all nodes look alike. Choosing depth trades reach against distinctiveness.

Relation to attention and convolution

Message passing generalizes both. A convolution is message passing on a grid with fixed weights per relative position. Attention is message passing where the aggregation weights are computed from query-key similarity. Seen this way, GNNs, CNNs, and transformers are variations on the same theme: build a representation of an element from a function of its neighbors.

Message, aggregate, update, repeated per node.
Aggregation must be permutation-invariant.
Sum aggregation is the most expressive of the simple choices.
Depth sets the neighborhood reach; too much over-smooths.