How Powerful Are Graph Neural Networks?

Takeaway

Message-passing GNNs are at most as powerful as the 1-WL isomorphism test; architecture choices affect expressivity and oversmoothing.

The problem (before → after)

Before: Many GNNs existed with unclear theoretical limits.
After: A unifying framework ties GNN expressivity to Weisfeiler–Lehman tests and pinpoints when architectures can distinguish graphs.

Mental model first

Think of each node gossiping with neighbors, then updating its state. If two neighborhoods always gossip the same way, the network can’t tell them apart.

Just-in-time concepts

Message passing: h_v^{(k+1)} = U(h_v^{(k)}, AGG({M(h_v^{(k)}, h_u^{(k)}) : u ∈ N(v)})).
1-WL test: Iteratively color nodes by hashing neighbor colors; if colors stabilize identically, graphs remain indistinguishable.
Oversmoothing: Repeated aggregation washes out differences; skip connections and normalization help.

First-pass solution

Design injective aggregators (e.g., sum) with MLPs to match 1-WL power (GIN). Use positional encodings or subgraph features to go beyond.

Long-range dependencies: Add attention or sparsified message passing.
Expressivity: Higher-order WL, subgraph GNNs, spectral methods.
Scalability: Sampling neighbors, graph partitioning, mini-batching.

Code as a byproduct (GIN layer)

import torch
import torch.nn as nn

class GINLayer(nn.Module):
    def __init__(self, mlp, eps=0.0):
        super().__init__()
        self.mlp = mlp
        self.eps = nn.Parameter(torch.tensor(eps))

    def forward(self, x, adj):
        agg = adj @ x
        out = self.mlp((1 + self.eps) * x + agg)
        return out

Principles, not prescriptions

Use injective aggregations and expressive updates to avoid information loss.
Mitigate oversmoothing with residuals, normalization, and limited hops.

Common pitfalls

Mean/Max aggregators can collapse different multisets.
Deep stacking without skip connections exacerbates oversmoothing.

Connections and contrasts

See also: [/blog/attention-is-all-you-need] (global attention), [/blog/variational-inference] (graphical models vs GNNs).

Quick checks

What limits MP-GNN power? — Equivalence to the 1-WL test.
How to reach 1-WL? — Injective sum aggregation + MLP (GIN).
How to go beyond? — Higher-order structures and subgraph features.