Message Passing Neural Networks

A standard neural network expects a fixed-size vector as input — a row of features. A company's supplier network, a portfolio's correlation graph, or a molecule's bond structure isn't naturally a row of features; it's a set of nodes connected by edges, with no fixed size and no natural ordering. Feeding a graph into an ordinary network means throwing away the very thing that makes it a graph — who's connected to whom. Message passing is the mechanism that lets a network learn directly on the graph structure itself, by having each node repeatedly gather information from its immediate neighbors.

The analogy: office gossip, formalized

Picture an office where nobody reads a company-wide memo — everyone only ever talks to their direct desk-neighbors. On day one, everyone knows only their own situation. At the end of day one, everyone has swapped a short update with their immediate neighbors, so now everyone's understanding includes a summary of their direct neighbors' situations too, folded into their own. On day two, they swap updates again — but this time, since everyone's "situation" already includes what they learned yesterday, a two-hop chain of gossip effectively reaches them: they now know something about their neighbors' neighbors, without ever talking to them directly. Run this for a few more days and information from a whole local neighborhood eventually reaches every desk, purely through repeated local exchanges — no one ever needed the company-wide memo. Message passing does exactly this with vectors instead of gossip: each node's internal representation gets updated, layer by layer, using only what its direct neighbors currently know.

The mechanism: aggregate, then update

At layer $k$, every node $v$ has a current representation vector $h_v^{(k)}$ — a summary, in numbers, of what node $v$ "knows" after $k$ rounds of message passing (at $k=0$, this is just the node's own raw features). One layer of message passing does two things:

$$m_v^{(k+1)} = \text{AGGREGATE}\Big(\big\{\, h_u^{(k)} : u \in \mathcal{N}(v) \,\big\}\Big), \qquad h_v^{(k+1)} = \text{UPDATE}\Big(h_v^{(k)},\ m_v^{(k+1)}\Big)$$

Here $\mathcal{N}(v)$ is the set of node $v$'s direct neighbors in the graph, $\text{AGGREGATE}$ is some order-independent combining function — commonly a sum, mean, or max — that squashes the (variable-length, unordered) set of neighbor vectors into a single fixed-size message $m_v^{(k+1)}$, and $\text{UPDATE}$ is a small neural network layer that combines the node's own previous representation with the incoming message to produce its new representation. In words: every node collects a combined summary of what its neighbors currently know, then blends that summary with its own current knowledge to form an updated self. Stacking $K$ layers of this lets information reach nodes up to $K$ hops away, because each layer only reaches one hop further than the last.

The choice of AGGREGATE has to be order-independent — a node's set of neighbors has no natural ordering, so summing or averaging (which don't care what order the numbers arrive in) work, but something order-sensitive like concatenation in a fixed sequence would not, since which neighbor is "first" is meaningless on a graph.

Worked example 1: two nodes, one layer, by hand

Take a tiny 3-node graph: $A$ connects to $B$ and $C$. Give each node a 1-dimensional starting feature: $h_A^{(0)} = 1.0$, $h_B^{(0)} = 2.0$, $h_C^{(0)} = 4.0$. Use AGGREGATE = mean, and UPDATE = "average the old value with the message."

Node $A$'s neighbors are $B$ and $C$: aggregated message $m_A = (2.0+4.0)/2 = 3.0$. New representation: $h_A^{(1)} = (h_A^{(0)} + m_A)/2 = (1.0+3.0)/2 = 2.0$. Node $A$'s value moved from $1.0$ toward $2.0$, pulled by its neighbors' average of $3.0$ — exactly what "gossip" should do: shift a node's self-knowledge partway toward what its neighbors reported.

Worked example 2: two layers reach two hops

Extend the graph: $D$ connects only to $C$ (so $A$ and $D$ are two hops apart, not directly connected), with $h_D^{(0)} = 10.0$. After layer 1, $C$'s neighbors are $A$ and $D$: $m_C = (1.0+10.0)/2 = 5.5$, so $h_C^{(1)} = (4.0+5.5)/2 = 4.75$.

Now layer 2 for node $A$: its neighbors' layer-1 values are $h_B^{(1)}$ (computed similarly, say it comes out to $2.5$) and $h_C^{(1)} = 4.75$. So $m_A^{(2)} = (2.5+4.75)/2 = 3.625$, and $h_A^{(2)} = (h_A^{(1)} + m_A^{(2)})/2 = (2.0+3.625)/2 = 2.8125$. Node $A$'s final value, $2.8125$, has been pulled by node $D$'s original value of $10.0$ even though $A$ and $D$ are never directly connected — it arrived indirectly, through $C$, exactly two layers after node $A$ started, matching the two-hop graph distance between them.

What this means in practice

Message passing networks are the foundation for learning on any graph-structured financial data: a supplier-customer network, a syndicate-loan network, an order-book limit-price ladder treated as a graph, or a portfolio's correlation network. They let a model learn features like "how exposed is this company to distress two supply-chain tiers away" directly from graph structure, rather than requiring an analyst to hand-engineer that feature. Graph convolutional networks and graph attention networks are both specific choices of AGGREGATE and UPDATE within this same message-passing template.

Practice

1. In a 5-node chain graph $A$–$B$–$C$–$D$–$E$, how many message-passing layers are needed before $A$'s representation depends at all on $E$'s original features?
2. Explain why AGGREGATE must be an order-independent function like sum or mean, using the office-gossip analogy's notion of "neighbors with no natural ordering."
3. A model uses 10 stacked message-passing layers on a densely connected graph. Predict, using the over-smoothing idea, what is likely to happen to how distinguishable two arbitrary nodes' final representations are.