Message Passing & GNNs

Overview & Motivation

A graph neural network learns representations by passing messages along edges. At each layer, every node aggregates information from its neighbors, transforms the result, and produces an updated feature vector. After $L$ layers, each node’s representation encodes the structure of its $L$-hop neighborhood.

This idea unifies the entire Graph Theory track:

• Graph Laplacians: The GCN update rule $H^{(\ell+1)} = \sigma(\tilde{D}^{-1/2}\tilde{A}\tilde{D}^{-1/2} H^{(\ell)} W^{(\ell)})$ is one step of Laplacian smoothing on the renormalized graph. The filter is a first-order polynomial of the normalized Laplacian.
• Random Walks: Repeated message passing drives node features toward the stationary distribution $\boldsymbol{\pi}$. The spectral gap $\gamma$ controls how many layers before features become indistinguishable — the over-smoothing phenomenon.
• Expander Graphs: On expanders, information reaches all nodes in $O(\log n)$ layers — optimal receptive field growth. But over-smoothing also occurs in $O(\log n)$ layers. Expander-based rewiring adds long-range edges to bottlenecked graphs, importing the expansion benefits without the over-smoothing cost.

What this topic covers:

• The message passing framework — aggregate, update, readout as the universal GNN template.
• Spectral graph convolutions — from the graph Fourier transform to ChebNet to GCN as Laplacian smoothing.
• Spatial graph convolutions — GCN, GraphSAGE, GIN, and the neighborhood aggregation perspective.
• The Weisfeiler-Leman test — 1-WL isomorphism test, equivalence to message passing GNNs, and the expressiveness hierarchy.
• Attention-based message passing — Graph Attention Networks (GAT) and learned edge weights.
• Over-smoothing — the random walk convergence connection, Dirichlet energy decay, and depth limitations.
• Expander-based graph rewiring — SDRF, FoSR, and spectral gap optimization as architectural design.

---

The Message Passing Framework

The message passing neural network (MPNN) framework unifies virtually all graph neural network architectures into three phases: aggregate, update, and readout. We develop each in turn.

The MPNN Template

Matrix Form

For simple message passing (linear messages, mean aggregation), the layer update collapses to a matrix equation. Let $H^{(\ell)} \in \mathbb{R}^{n \times d_\ell}$ collect node features as rows:

$H^{(\ell+1)} = \sigma\left(\hat{A} H^{(\ell)} W^{(\ell)}\right)$

where $\hat{A}$ is a normalized adjacency operator and $W^{(\ell)} \in \mathbb{R}^{d_\ell \times d_{\ell+1}}$ is the learnable weight matrix. Different choices of $\hat{A}$ yield different architectures:

Architecture	$\hat{A}$	Name
GCN (Kipf & Welling)	$\tilde{D}^{-1/2}\tilde{A}\tilde{D}^{-1/2}$	Renormalized symmetric
GraphSAGE (mean)	$D^{-1}A$	Transition matrix
Simple GCN	$D^{-1/2}AD^{-1/2}$	Normalized adjacency (no self-loops)

Receptive Field Growth

After $L$ layers of message passing, each node’s representation depends on all nodes within $L$ hops. The receptive field of node $v$ at depth $L$ is the $L$-hop neighborhood $\mathcal{N}_L(v) = \{u : d(u,v) \leq L\}$.

GraphKarate Club (34)Barbell(5)Grid 4×4PetersenCycle(10)Path(10)ArchitectureGCNGraphSAGEGINLayer 0Animate

Spectral gap γ = 0.0726Over-smoothing depth: 2Nodes: 10

---

Spectral Graph Convolutions

The spectral perspective interprets message passing through the lens of the graph Laplacian eigendecomposition.

The Graph Fourier Transform

The eigenvectors $\mathbf{u}_k$ play the role of Fourier modes: $\mathbf{u}_0$ (the constant vector) is the “DC component,” and higher eigenvectors oscillate more across the graph. The eigenvalue $\lambda_k$ measures the frequency — low $\lambda_k$ means smooth variation along edges, high $\lambda_k$ means rapid oscillation.

Spectral Convolution

The problem: learning $n$ free parameters $g_\theta(\lambda_k)$ is expensive and non-transferable (different graphs have different eigenvectors).

ChebNet and Polynomial Filters

GCN as a First-Order Spectral Filter

---

Spatial Graph Convolutions

The spatial perspective bypasses eigendecomposition entirely. Instead of filtering in the spectral domain, we directly define how each node aggregates neighbor features.

GCN (Kipf & Welling 2017)

The GCN layer with mean aggregation:

$\mathbf{h}_v^{(\ell+1)} = \sigma\left(W^{(\ell)} \cdot \text{MEAN}\left(\{\mathbf{h}_u^{(\ell)} : u \in \mathcal{N}(v) \cup \{v\}\}\right)\right)$

This is equivalent to the spectral derivation via the renormalized adjacency.

GraphSAGE (Hamilton, Ying & Leskovec 2017)

GraphSAGE separates the self-loop from neighbor aggregation:

$\mathbf{h}_v^{(\ell+1)} = \sigma\left(W^{(\ell)} \cdot \text{CONCAT}\left(\mathbf{h}_v^{(\ell)}, \text{AGG}(\{\mathbf{h}_u^{(\ell)} : u \in \mathcal{N}(v)\})\right)\right)$

where AGG can be mean, LSTM, or max-pool. The concatenation preserves the node’s own identity separately from its aggregated neighborhood.

GIN (Xu, Hu, Leskovec & Jegelka 2019)

---

The Weisfeiler-Leman Test & GNN Expressiveness

The 1-WL Color Refinement Algorithm

GNN = 1-WL (in Expressive Power)

Limitations of 1-WL

Graph pairC₆ vs Two K₃K₃,₃ vs PrismPetersen vs 3-reg(10)Step 0Auto-refine1-WL cannot distinguish ✗

---

Attention-Based Message Passing

Graph Attention Networks (GAT)

Multi-Head Attention

GAT uses multi-head attention to stabilize training:

$\mathbf{h}_v^{(\ell+1)} = \Big\|_{k=1}^{K} \sigma\left(\sum_{u \in \mathcal{N}(v)} \alpha_{vu}^k W^k \mathbf{h}_u^{(\ell)}\right)$

where $\|$ denotes concatenation over $K$ attention heads. Each head learns different edge importance patterns.

The Attention Matrix Perspective

The attention weights define a learned, data-dependent graph: the attention graph $\tilde{G}$ where edge $(v, u)$ has weight $\alpha_{vu}$. This is a soft version of graph rewiring — attention can effectively increase or decrease edge weights, reshaping the message-passing topology without changing the underlying graph.

---

Over-Smoothing & the Random Walk Connection

The Over-Smoothing Problem

Over-Smoothing is Random Walk Convergence

Measuring Over-Smoothing: MAD and Dirichlet Energy

Mitigation Strategies

Several strategies combat over-smoothing:

1. Residual connections: $H^{(\ell+1)} = H^{(\ell)} + \text{MP}(H^{(\ell)})$ preserves the original signal.
2. Jumping knowledge: $H_{\text{final}} = \text{CONCAT}(H^{(0)}, H^{(1)}, \ldots, H^{(L)})$ accesses all depths.
3. DropEdge: Randomly remove edges during training to slow diffusion.
4. PairNorm / NodeNorm: Normalize features to maintain diversity.
5. Graph rewiring: Add long-range edges to reduce diameter without adding layers (see next section).

Families:Path(10)Cycle(10)Grid 3×3Barbell(5)PetersenComplete(8)Karate Club

Active graphPath(10)Cycle(10)Grid 3×3Barbell(5)PetersenComplete(8)Karate ClubLayer 0Show FoSR rewiring

---

Expander-Based Graph Rewiring

The Bottleneck Problem

Many real-world graphs have bottlenecks — vertices or small edge cuts that separate communities. From the Cheeger inequality, a small spectral gap $\lambda_2$ implies a tight bottleneck $h(G)$. Message passing across the bottleneck requires $\Omega(1/\lambda_2)$ layers — far more than the receptive field within each community.

Graph Rewiring via Spectral Gap Optimization

Expander Graph Augmentation

Beyond Standard Message Passing

Several architectures break the message passing paradigm to overcome its limitations:

Architecture	Key Innovation	Expressiveness
Graph Transformers	Full self-attention (no edge constraint)	Beyond 1-WL
k-GNN	Higher-order WL (k-tuples)	$k$-WL
Subgraph GNNs	Run MPNN on subgraph ensembles	3-WL
Equivariant GNNs	Geometric symmetries (E(3), SE(3))	Task-dependent

---

Computational Notes

PyTorch Geometric

The standard library for GNN implementation in Python is PyTorch Geometric (PyG). A GCN layer in PyG:

import torch
from torch_geometric.nn import GCNConv

class GCN(torch.nn.Module):
    def __init__(self, in_channels, hidden_channels, out_channels):
        super().__init__()
        self.conv1 = GCNConv(in_channels, hidden_channels)
        self.conv2 = GCNConv(hidden_channels, out_channels)

    def forward(self, x, edge_index):
        x = self.conv1(x, edge_index).relu()
        x = self.conv2(x, edge_index)
        return x

DGL (Deep Graph Library)

An alternative implementation framework:

import dgl
import torch
from dgl.nn import GraphConv

class GCN(torch.nn.Module):
    def __init__(self, in_feats, h_feats, num_classes):
        super().__init__()
        self.conv1 = GraphConv(in_feats, h_feats)
        self.conv2 = GraphConv(h_feats, num_classes)

    def forward(self, g, in_feat):
        h = self.conv1(g, in_feat).relu()
        h = self.conv2(g, h)
        return h

Spectral vs Spatial Complexity

Approach	Per-Layer Cost	Localized?	Transferable?
Full spectral ($g_\theta(\Lambda)$)	$O(n^2)$	No	No
ChebNet (order $K$)	$O(K \cdot \|E\|)$	$K$-hop	Yes
GCN (1st order)	$O(\|E\|)$	1-hop	Yes
GAT	$O(\|E\| \cdot d)$	1-hop	Yes
Graph Transformer	$O(n^2 \cdot d)$	Global	Yes

Monitoring Over-Smoothing

Track Dirichlet energy and MAD during training to detect over-smoothing:

def dirichlet_energy_torch(x, edge_index):
    row, col = edge_index
    diff = x[row] - x[col]
    return (diff ** 2).sum()

If energy drops below a threshold after the first few layers, consider reducing depth, adding residual connections, or applying graph rewiring.

---

Connections & Further Reading

Cross-Track and Within-Track Connections

Topic	Track	Connection
Graph Laplacians & Spectrum	Graph Theory	The GCN update rule is a first-order polynomial of the normalized Laplacian. Spectral graph convolutions filter signals via the Laplacian eigendecomposition. The Fiedler vector drives spectral rewiring.
Random Walks & Mixing	Graph Theory	Over-smoothing is random walk convergence: repeated application of $\hat{A}$ drives features to the stationary distribution. The spectral gap $\gamma$ controls the over-smoothing rate. Mixing time bounds directly predict GNN depth limits.
Expander Graphs	Graph Theory	Expanders give $O(\log n)$ receptive fields but also $O(\log n)$ over-smoothing depth. Expander-based graph rewiring (FoSR, SDRF) increases $\lambda_2$ to improve information flow. The Expander Mixing Lemma implies quasi-random message passing on expanders.
The Spectral Theorem	Linear Algebra	The spectral decomposition of $\hat{A}$ underlies both GCN smoothing analysis and the 1-WL expressiveness proof. Eigenvalue bounds govern convergence rates.
Gradient Descent & Convergence	Optimization	GNNs are trained via backpropagation through message-passing layers. The gradient flow through $\hat{A}^L$ suffers from vanishing/exploding gradients governed by the spectral radius.
PCA & Low-Rank Approximation	Linear Algebra	Node embeddings from GNNs approximate a low-rank factorization of the graph. DeepWalk = implicit matrix factorization. Spectral clustering uses the bottom Laplacian eigenvectors as a low-rank embedding.
Concentration Inequalities	Probability & Statistics	PAC-style generalization bounds for GNNs use Rademacher complexity. The number of message-passing layers affects the model’s effective capacity and generalization.

Notation Summary

Symbol	Meaning
$\mathbf{h}_v^{(\ell)}$	Node $v$‘s feature vector at layer $\ell$
$H^{(\ell)}$	Feature matrix at layer $\ell$ ($n \times d_\ell$)
$W^{(\ell)}$	Learnable weight matrix at layer $\ell$
$\hat{A}$	Normalized adjacency operator (GCN: $\tilde{D}^{-1/2}\tilde{A}\tilde{D}^{-1/2}$)
$\bigoplus$	Permutation-invariant aggregation (sum, mean, max)
$\alpha_{vu}$	GAT attention weight from $v$ to $u$
$E(H)$	Dirichlet energy: $\text{tr}(H^T L H)$
$c_v^{(\ell)}$	1-WL color of node $v$ at iteration $\ell$
$\text{MAD}(H)$	Mean Average Distance of node features