MIT 6.7960 Graph Neural Networks (GNN) — Message Passing, Permutation Equivariance, and the Expressiveness Ceiling

🌏 中文版

Source: based on MIT 6.7960 Fall 2024 OCW (corresponds to OCW Lec 05). Videos, slides, and assignments are all open on MIT OCW. This lecture is taught by Phillip Isola.

What data on graphs looks like

Earlier architectures all handled regular structures: MLP = flat vectors, CNN = regular grid (images), RNN/Transformer = sequences. But a lot of real data is a graph: molecules (atoms = nodes, bonds = edges), social networks, knowledge graphs, chip layouts, road networks.

The hard part: there is no fixed input order, and topology is arbitrary. You cannot just flatten a graph into an MLP like an image — permute the nodes and the features scramble.

GNNs in light of MLP / CNN

• MLP: each sample is an independent vector, ignores relationships between samples.
• CNN: aggregates over a fixed grid neighborhood, weight sharing → translation equivariance.
• GNN: generalizes CNN's "grid neighborhood" to a "graph neighborhood," aggregating locally over arbitrary topology.

So a GNN can be thought of as "an MLP with neighbor aggregation, operating on a graph." It keeps weight sharing (every node uses the same update function) but the aggregation scope is dictated by graph structure.

Message Passing

The dominant GNN is the Message Passing Neural Network (MPNN) framework. At each layer, for every node v:

1. Gather (aggregate): collect messages from neighbors u ∈ N(v), m_{uv} = MSG(h_u, h_v, e_{uv}).
2. Update (update): h_v' = UPD(h_v, AGG({m_{uv} : u ∈ N(v)})).

Repeat for L layers and each node aggregates information from L-hop neighbors — the receptive field grows with depth. Minimal implementation:

import torch
def message_pass(h, edge_index, W_msg, W_upd):
    # h: [N, D] node features; edge_index: [2, E] (src, dst)
    src, dst = edge_index
    msg = h[src] @ W_msg.T                 # neighbor messages
    agg = torch.zeros_like(h).index_add(0, dst, msg)  # aggregate by dst
    return torch.tanh((h @ W_upd.T) + agg) # update

This is the shared skeleton of GCN / GIN / GraphSAGE; they differ only in the choice of MSG / AGG / UPD.

Permutation Equivariance / Invariance

A graph has no natural order, so a GNN must satisfy:

• Equivariant: after permuting node order, each node's output permutes accordingly → node-level tasks (node classification) need this.
• Invariant: after permuting, the whole-graph output is unchanged → graph-level tasks (is this molecule toxic?) need this.

This is the inductive bias of GNNs: they inherently respect the symmetries of the graph, in the same spirit as CNN translation equivariance and Transformer permutation equivariance (see L08).

The expressiveness ceiling: Weisfeiler–Lehman

A key question: can a GNN distinguish any two graphs?

The answer is no. The expressiveness of a first-order message-passing GNN is bounded above by the Weisfeiler–Lehman (WL) graph isomorphism test: it iteratively hashes the multiset of each node's neighborhood; if the final hashed multisets differ, WL declares "non-isomorphic."

But WL itself cannot distinguish certain non-isomorphic graphs (the classic counterexample: strongly regular graphs that are 1-WL indistinguishable). Since GNN expressiveness ≤ WL, GNNs also cannot tell those apart. This is a fundamental ceiling of GNNs, not a training issue.

Practical ways to patch the ceiling

To break past the WL ceiling, common approaches:

• GIN (Xu et al.): uses an injective aggregation (sum + MLP) to reach the WL limit.
• Positional / structural encodings: inject node-distance or random-walk information to break symmetry.
• Subgraph / higher-order messages: pass edges or triangles and other higher-order structures.
• Attention (GAT): replace fixed aggregation with attention weights to capture heterogeneous neighbors.

These all echo one theme: when expressiveness is insufficient, either add structural priors or change the aggregation — the same thread as L13's inductive bias and L12's representation learning.

When to use a GNN

• ✅ Data is inherently relational/topological (molecules, social, recommendation, knowledge graphs).
• ✅ Variable node counts, no fixed grid.
• ⚠️ If the graph is huge and sparse, watch neighbor explosion and over-smoothing (deep layers make all node features converge).
• ⚠️ If your "graph" is actually very regular, CNN/Transformer may be simpler and more effective.

References

• MIT 6.7960 OCW (Fall 2024): course home
• Kipf & Welling, Semi-Supervised Classification with Graph Convolutional Networks: arXiv:1609.02907
• Gilmer et al., Neural Message Passing for Quantum Chemistry: arXiv:1704.01212
• Xu et al., How Powerful are Graph Neural Networks (GIN): arXiv:1810.00826