The Weisfeiler-Lehman Test: How Powerful Are GNNs?

Intuition First: Why Can GNNs Fail to Tell Graphs Apart?

Imagine two cities with different road layouts but where every intersection has exactly the same number of roads connecting to it (i.e., regular graphs). If you stand at any intersection and look only at the local road count, every intersection looks identical — you cannot tell the cities apart without a map. A GNN operating by local neighbourhood aggregation faces the same problem: if two graphs have identical local multiset statistics at every scale, the GNN sees the same numbers everywhere and produces identical outputs.

The WL test formalises exactly which graph pairs fall into this trap.

What Is Graph Isomorphism?

Two graphs G and G’ are isomorphic (G ≅ G’) if there exists a bijection σ: V(G) → V(G’) such that (u,v) ∈ E(G) ↔ (σ(u), σ(v)) ∈ E(G’). Informally: they are the same graph up to node relabelling.

Graph isomorphism testing is a fundamental problem. It is not known to be in P or NP-complete (it’s in NP ∩ co-AM ∩ GI-complete). For practical purposes, the 1-WL algorithm provides a fast, powerful (but not complete) test.

The 1-WL Algorithm (Color Refinement)

Initialisation: assign each node a colour (label) based on its initial feature or degree.

Iteration: at each step, each node v updates its colour by hashing the multiset of its neighbours’ colours:

Where {{ }} denotes a multiset (counts matter, order does not).

Termination: stop when no colour changes between iterations.

Test: compare the multisets of final colours between G and G’. If they differ → G ≇ G’. If they match → 1-WL declares G ≅ G’ (though this can be wrong for some graph pairs).

Concrete Worked Example: Running 1-WL

Consider two graphs:

• G₁: a triangle (3-cycle): nodes A–B–C–A, all degree 2
• G₂: three isolated edges: A–B, C–D, E–F (6 nodes, all degree 1)

Iteration 0: assign initial colours by degree.

• G₁: every node gets colour “deg=2” → histogram {deg2: 3}
• G₂: every node gets colour “deg=1” → histogram {deg1: 6}

Histograms differ → 1-WL correctly distinguishes G₁ from G₂. ✓

Now consider two harder graphs:

• G₃: two disconnected triangles (6 nodes, all degree 2)
• G₄: a 6-cycle A–B–C–D–E–F–A (6 nodes, all degree 2)

Iteration 0: both have histogram {deg2: 6}. Same. Iteration 1: each node hashes its colour with its neighbours’ colour multiset. In G₃ every node has two neighbours both coloured “deg2” within a triangle. In G₄ every node also has two neighbours coloured “deg2” in a cycle. The multisets are identical! 1-WL cannot distinguish G₃ from G₄ — and neither can any MPNN.

1-WL as Message Passing

The 1-WL iteration is exactly message passing with an injective aggregation:

Message:  m_{u→v} = c_u   (send colour to neighbour)
Aggregate: m_v = {c_u : u in N(v)}   (multiset of neighbour colours)
Update:   c_v = HASH(c_v, m_v)    (inject own colour + multiset into new colour)

The HASH function must be injective: different (c_v, m_v) → different c_v’. This is the key requirement.

The Main Theorem (Xu et al., 2019)

Theorem: Let A and B be two graphs. If 1-WL determines A ≅ B (cannot distinguish them), then no MPNN can distinguish them either — regardless of the message function M, aggregation □, or update function U.

Conversely, there exists an MPNN that is as powerful as 1-WL: one that uses sum aggregation and an injective update function.

This means:

• 1-WL is the exact upper bound on MPNN expressivity
• The bound is tight — achievable by a specific architecture (GIN)
• More expressive architectures must go beyond MPNN (higher-order WL, graph Transformers, structural encodings)

What 1-WL Cannot Distinguish

Two classes of graphs that fool 1-WL (and therefore any MPNN):

1. Regular graphs: if every node in G has the same degree, then after initialisation all nodes get the same colour → 1-WL cannot distinguish any two regular graphs with the same number of nodes and edges.

Triangle (3 nodes, 3 edges, degree-2 regular)
vs.
No edges + 3 isolated nodes: distinguished (different degrees)

Two different 3-regular graphs on 6 nodes: NOT distinguished by 1-WL

2. Structurally indistinguishable substructures: any two nodes v and v’ with identical K-hop neighbourhood multisets for all K have the same 1-WL colour — even if their global structural roles differ (e.g., one is in a 4-cycle, one is not, but their up-to-K-hop neighbourhood multisets match).

GIN: The Most Expressive MPNN

GIN (Graph Isomorphism Network, Xu et al., 2019) achieves 1-WL expressiveness:

Sum aggregation (not mean or max) is crucial. By the theory of multisets: sum is injective over multisets of bounded values, while mean and max are not.

• Mean cannot distinguish {1,1,1} from {1} (normalises out count information)
• Max cannot distinguish {1,2,3} from {2,3} (drops minimum)
• Sum distinguishes both: 3 ≠ 1, 6 ≠ 5

The MLP must be sufficiently expressive (universal approximator) to implement the injective mapping.

Beyond 1-WL: Higher-Order Tests

To go beyond 1-WL, you need:

The k-WL hierarchy: k-WL is strictly more powerful than (k-1)-WL. The price: k-WL considers k-tuples of nodes simultaneously — O(N^k) in complexity.

Summary

The WL test is the lens through which GNN expressivity is understood. It tells you not just what GNNs can do, but precisely what they cannot — and why adding structural encodings, higher-order interactions, or global attention is necessary for harder graph reasoning tasks.

References

• Xu, K., Hu, W., Leskovec, J., & Jegelka, S. (2019). How Powerful are Graph Neural Networks?. ICLR 2019.
• Weisfeiler, B., & Lehman, A. A. (1968). A Reduction of a Graph to a Canonical Form and an Algebra Arising During This Reduction. Nauchno-Technicheskaya Informatsia.
• Babai, L., & Kucera, L. (1979). Canonical Labelling of Graphs in Linear Average Time. FOCS 1979.