Message Passing Neural Networks (MPNN)

Introduction

In the GNN introduction, we saw that GNNs learn by aggregating information from neighbors. Message Passing is the formal framework that unifies virtually all GNN architectures.

The idea is elegant: each node sends "messages" to its neighbors, collects messages from its neighbors, and uses them to update its own representation. Different GNN architectures (GCN, GAT, GraphSAGE, GIN) are just different implementations of this same idea.

Why It Works

Message passing is a form of neural network inductive bias. By forcing nodes to learn from their local neighborhoods, we inject the prior knowledge that "connected things are related." This is similar to how CNNs inject the prior that "nearby pixels are related."

The MPNN Framework

The Message Passing Neural Network (MPNN) framework, introduced by Gilmer et al. (2017), provides a unified view. One layer of message passing consists of three steps:

General Message Passing Layer

Step 1: MESSAGE

m_{v\leftarrow u} = \text{MESSAGE}(h_{u}^{(l)},h_{v}^{(l)},e_{uv})

Creates a "message" from neighbor u to target v using their features and edge attributes

Step 2: AGGREGATE

m_{v} = \text{AGGREGATE}(\{ m_{v\leftarrow u}:u \in \mathcal{N}(v)\})

Combines all incoming messages (must be permutation-invariant: sum, mean, max, attention)

Step 3: UPDATE

h_{v}^{(l + 1)} = \text{UPDATE}(h_{v}^{(l)},m_{v})

Merges aggregated message with node's current features (usually an MLP or GRU)

The Unifying Pattern

Every GNN architecture follows this pattern. They differ only in how they implement MESSAGE, AGGREGATE, and UPDATE. This abstraction makes it easy to understand and compare different approaches.

Aggregation Functions

The aggregation function must be permutation-invariant: the result should not depend on the order in which we process neighbors. This is a fundamental requirement for graph neural networks.

SUM

m_{v} = \sum_{u \in \mathcal{N}(v)}m_{v\leftarrow u}

Pros:

Preserves neighborhood size information. Captures "how much" signal.

Cons:

Different scales for different degrees. Needs normalization.

Used by: GIN, original spectral GNNs

MEAN

m_{v} = \frac{1}{\mid\mathcal{N}(v)\mid}\sum_{u \in \mathcal{N}(v)}m_{v\leftarrow u}

Pros:

Normalizes for degree. Stable across graph sizes.

Cons:

Loses neighborhood size information.

Used by: GCN, GraphSAGE-mean

MAX

m_{v} = {\max}_{u \in \mathcal{N}(v)}m_{v\leftarrow u}

Pros:

Captures strongest signal. Robust to outliers.

Cons:

Loses information from non-max neighbors.

Used by: GraphSAGE-pool, PointNet

ATTENTION (Weighted Sum)

m_{v} = \sum_{u \in \mathcal{N}(v)}\alpha_{vu} \cdot m_{v\leftarrow u}

Pros:

Learns which neighbors are important. Adaptive weighting.

Cons:

More parameters, slower, can overfit on small graphs.

Used by: GAT, Graph Transformers

Update Functions

The update function combines the aggregated message with the node's own features. The choice of update function affects both expressivity and trainability.

Simple: Replace

h_{v}^{\prime} = \sigma(W \cdot m_{v})

Just use the message, ignore self. Risk: lose self-information over layers.

Concatenate + MLP

h_{v}^{\prime} = \text{MLP}(\lbrack h_{v}\,\parallel\, m_{v}\rbrack)

Concatenate self and message, let MLP learn combination. Most flexible.

Skip Connection

h_{v}^{\prime} = h_{v} + \sigma(W \cdot m_{v})

Residual connection. Essential for deep GNNs (helps gradient flow).

GRU Update

h_{v}^{\prime} = \text{GRU}(h_{v},m_{v})

Gated recurrent unit. Used in GGNN for sequential message passing.

The Over-Smoothing Problem

Deep GNNs (many layers) suffer from over-smoothing: all node representations converge to the same value. Skip connections and careful normalization (like in BatchNorm) help, but this limits GNN depth to typically 2-4 layers.

GCN: Graph Convolutional Network

GCN (Kipf & Welling, 2017) is the foundational modern GNN. It's derived from spectral graph theory but has a simple spatial interpretation:

H^{(l + 1)} = \sigma\left( {\overset{\sim}{D}}^{- 1/2}\overset{\sim}{A}{\overset{\sim}{D}}^{- 1/2}H^{(l)}W^{(l)} \right)

Where à = A + I (add self-loops) and D̃ is the degree matrix of Ã.

In message passing terms:

MESSAGE: Linear transform of neighbor feature: m = W · h_u

AGGREGATE: Normalized sum with symmetric weighting: \frac{1}{\sqrt{d_{u} \cdot d_{v}}}

UPDATE: Include self-loop (via Ã), then apply nonlinearity σ

Key Insight: Symmetric Normalization

The 1/\sqrt{d_{u} \cdot d_{v}} normalization prevents high-degree nodes from dominating. It's derived from the normalized graph Laplacian and ensures stable learning across graphs with varying degree distributions.

GraphSAGE

GraphSAGE (Hamilton et al., 2017) introduced two key innovations: neighborhood sampling for scalability and explicit self-loop handling via concatenation.

h_{v}^{(l + 1)} = \sigma\left( W \cdot \text{CONCAT}\left( h_{v}^{(l)},\text{AGG}(\{ h_{u}^{(l)}:u \in \mathcal{N}(v)\}) \right) \right)

Neighborhood Sampling

Instead of using all neighbors, sample a fixed number (e.g., 10-25). Makes training O(1) per node rather than O(degree), enabling massive-scale graphs.

Inductive Learning

Learns an aggregator function, not node-specific embeddings. Can generalize to completely unseen nodes and graphs at test time.

Aggregator options: MEAN (simple average), LSTM (order neighbors randomly for sequence), MAX-POOL (apply MLP element-wise then max).

GAT: Graph Attention Network

GAT (Veličković et al., 2018) uses attention mechanisms to learn which neighbors are most important for each node. This is a major departure from fixed aggregation weights.

Attention coefficient:

e_{vu} = \text{LeakyReLU}\left( \mathbf{a}^{T}\lbrack Wh_{v}\parallel Wh_{u}\rbrack \right)

Softmax normalization:

\alpha_{vu} = \frac{\exp(e_{vu})}{\sum_{u^{\prime} \in \mathcal{N}(v)}\exp(e_{vu^{\prime}})}

Weighted aggregation:

h_{v}^{(l + 1)} = \sigma\left( \sum_{u \in \mathcal{N}(v)}\alpha_{vu}Wh_{u} \right)

Multi-Head Attention

Like Transformers, GAT uses K independent attention heads and concatenates (or averages) their outputs. This stabilizes training and captures different "aspects" of neighbor importance. Typically K = 8 for intermediate layers.

Interactive: Attention Weights

See how attention mechanisms dynamically weight neighbors. Unlike GCN's fixed normalization, GAT learns which connections matter most.

Attention Weights

GAT learns to weight neighbors based on feature similarity.

Interactive Mode

Feature Modulation

Target Vector (Query)

Dim 0

Dim 1

Neighbor Vectors (Keys)

N1w = 53.5%

N2w = 20.5%

N3w = 26.0%

Attention Calculation

Score

e_{ij} = \text{LeakyReLU}(\mathbf{a}^{T}\lbrack Wh_{i}\parallel Wh_{j}\rbrack)

(Simplified here as dot product similarity)

Weight

\alpha_{ij} = \frac{\exp(e_{ij})}{\sum_{k}\exp(e_{ik})}

GIN: Graph Isomorphism Network

GIN (Xu et al., 2019) asks a fundamental question: what's the most expressive possible GNN? The answer: one that's as powerful as the Weisfeiler-Lehman (WL) graph isomorphism test.

h_{v}^{(l + 1)} = \text{MLP}\left( (1 + \epsilon) \cdot h_{v}^{(l)} + \sum_{u \in \mathcal{N}(v)}h_{u}^{(l)} \right)

ε is a learnable parameter (or fixed small value like 0).

Key Theoretical Insights

• SUM not MEAN: Sum preserves multiset cardinality; mean loses it. Critical for distinguishing graphs.
• MLP not linear: Needs a universal approximator (MLP) to be injective. Linear transforms can't distinguish all neighborhoods.
• (1 + ε) term: Distinguishes self from sum of neighbors. Without it, some non-isomorphic graphs look identical.

Readout & Graph-Level Tasks

For graph classification or regression, we need a single vector representing the entire graph. This is done via a READOUT (or pooling) function that aggregates node embeddings.

h_{G} = \text{READOUT}(\{ h_{v}^{(L)}:v \in V\})

Global Sum/Mean

Simplest approach. Sum (or mean) all final node embeddings. Works surprisingly well.

Hierarchical Pooling

Learn to coarsen graph iteratively (DiffPool, MinCutPool). More expressive but complex.

Set2Set

LSTM-based attention over all nodes. Order-invariant but sequential processing.

Virtual Node

Add a "super node" connected to all others. Its embedding represents the graph.

Architecture Comparison

Choosing the Right Architecture

GCN for node classification with smooth labels. GraphSAGE for massive graphs or inductive settings. GAT when neighbor importance varies (e.g., molecular graphs). GIN for graph-level tasks requiring maximum expressivity.

Interactive: All Architectures

Compare all four GNN architectures side-by-side. Select an architecture to see its specific message passing mechanism, aggregation function, and update rule on the same graph.

GNN Architecture Comparison

Select an architecture to see how it processes graph information. Click nodes to change target.

GCN

GraphSAGE

GAT

GIN

MPNN

GCN Mode

GCN

Fixed spectral normalization prevents explosion

Update Rule

h^{\prime} = \sigma({\overset{\sim}{D}}^{- 1/2}\overset{\sim}{A}{\overset{\sim}{D}}^{- 1/2}HW)

Message

Wh_{u}

Aggregate

Normalized sum

Update

\text{Self-loop} + \sigma