Message Passing Neural Networks

Let $G=(V,E)$ be a finite graph. Each node $v\in V$ has a hidden vector at layer $\ell$:

$$h_v^{(\ell)}\in\mathbb{R}^{d}.$$

The one-hop neighborhood of $v$ is

$$\mathcal{N}(v)=\{u:(u,v)\in E\}.$$

A message-passing layer can be written in three steps.

First, compute a message from each neighbor $u$ to node $v$:

$$m_{u\to v}^{(\ell)} = \phi_m\left(h_u^{(\ell)}, h_v^{(\ell)}, e_{uv}\right).$$

Here $\phi_m$ is a learned message function. The optional edge feature $e_{uv}$ can encode edge type, distance, bond type, or any edge annotation. This page keeps $e_{uv}$ out of the demo so the core mechanism stays visible.

Second, aggregate the incoming messages:

$$a_v^{(\ell)} = \operatorname{AGG}_{u\in\mathcal{N}(v)} m_{u\to v}^{(\ell)}.$$

The aggregator must be permutation-invariant. Mean aggregation is one simple choice:

$$a_v^{(\ell)} = \frac{1}{|\mathcal{N}(v)|} \sum_{u\in\mathcal{N}(v)} m_{u\to v}^{(\ell)}.$$

Third, update the node representation:

$$h_v^{(\ell+1)} = \phi_u\left(h_v^{(\ell)}, a_v^{(\ell)}\right).$$

The update function $\phi_u$ may be an MLP, a gated recurrent update, a residual block, or a simpler affine map plus nonlinearity.

The key invariant is local and repeated:

$$\text{new node state} = \text{update}\left( \text{old node state}, \text{aggregate of neighbor messages} \right).$$

After one layer, a node has information from one-hop neighbors. After two layers, it can contain information from nodes two hops away, because its neighbors have already absorbed their own neighbors.

This locality is powerful, but it also creates caveats:

• many layers can blur node representations if aggregation repeatedly averages neighborhoods;
• nodes with different local structure can still become hard to distinguish;
• attention, normalization, residual connections, and edge features change the layer behavior;
• implementation libraries use sparse batching and indexing tricks that are not visible in the small formula.

Those are later pages. This page isolates the mechanism every learner should feel first: send, aggregate, update.