A graph neural network can look busy.

Messages move along edges. Node states get updated. A graph-level embedding appears at the end. The whole procedure feels geometric and learned and continuous.

But for a large and important family of graph neural networks, there is a small discrete machine hiding under the hood:

color refinement

That machine is also called the 1-dimensional Weisfeiler-Leman test, or 1-WL. It is not a metaphor. It is the algorithmic shadow of ordinary message passing.

If the shadow cannot separate two graphs, then a message-passing model with the same information contract cannot be trained, widened, or optimizer-tuned into separating them. The model can be useful. It can be state of the art on a real dataset. It can still have this exact blind spot.

The simplest version is almost rude:

a six-cycle       versus       two disconnected triangles

They have different triangle counts. They have different connected-component counts. They are obviously not isomorphic. And 1-WL, starting from identical node features, does not distinguish them.

The Contract

Gilmer et al. gave a clean name to a broad class of graph models: Message Passing Neural Networks.1 In the common form, each layer updates node v from its current state and a permutation-invariant summary of its neighbors:

\[h_v^{(t+1)} = \phi_t\left(h_v^{(t)}, \operatorname{AGG}_t\{h_u^{(t)} : u \in N(v)\}\right).\]

Then a readout pools node states into a graph representation.

This recipe is natural because graphs do not come with a canonical order of neighbors. The node called 17 in memory is not semantically the seventeenth node in the object. So the aggregator has to be symmetric: sum, mean, max, attention over a multiset, or another order-insensitive operation.

That symmetry is the beginning of the theorem.

Color refinement uses the same recursive idea without neural parameters:

initial color of every node
repeat:
  new color(v) = hash(old color(v), multiset of old colors of neighbors)

At graph level, compare the histogram of node colors after every round. If the histograms ever differ, the graphs are not isomorphic. If they never differ, 1-WL gives up. The graphs may still be different.

Kiefer and McKay describe color refinement as a central graph-isomorphism subroutine and give the same iterative definition in terms of a vertex color plus the multiset of neighbor colors.2

Xu et al. and Morris et al. made the neural connection precise from the GNN side.34 In short: under the usual neighborhood-aggregation setup, message passing is bounded by 1-WL in its ability to distinguish graph structure. With sufficiently injective aggregation and update functions, a model such as GIN can reach the 1-WL boundary. Mean and max aggregators can be weaker because they can collapse different multisets even before 1-WL would.

So 1-WL is not the whole story of graph learning.

It is the ceiling for this particular kind of story.

A Four-Graph Microscope

The lab below runs exact joint color refinement on graph pairs. The two graphs share the same color dictionary at every round, so the histograms are directly comparable. The rightmost panel deliberately tracks facts that color refinement may miss: triangle count, connected components, edge count, and bipartiteness.

color class new class selected round hidden gap right graph bars

Exact deterministic 1-WL experiment. The audit verifies the C6 versus two triangles failure, the triangular prism versus K3,3 failure, the path versus cycle positive control, the relabeling sanity check, graph validity, triangle counts, component counts, and bipartiteness.

Start with C6 vs two triangles.

At round zero every node has the same color. At round one every node still has the same color, because every node has two neighbors of the same previous color. Nothing changes at round two, or round three, or at stabilization.

The graph-level readout sees:

six nodes of color 0

on both sides.

But the graphs disagree on facts a human would notice instantly:

C6:       0 triangles, 1 component
C3 + C3: 2 triangles, 2 components

Now switch to prism vs K3,3. This pair removes the cheap objection that the previous example was disconnected. Both graphs are connected. Both have six nodes. Both have nine edges. Both are 3-regular. Starting from a single node feature, every node again receives the same multiset of neighbor colors at every round.

Still, the triangular prism has two triangles and is not bipartite. K3,3 has no triangles and is bipartite.

The path/cycle pair is the control. A path has two degree-one endpoints, while the cycle does not. 1-WL catches that immediately because the first refinement is basically a degree histogram when all initial colors are equal.

The relabeled cycle is the other control. Changing node names should not change the answer, and it does not.

Why This Is Not Just a Bad Aggregator

Some neural aggregators lose more information than 1-WL.

Mean aggregation can map different multisets to the same average. Max aggregation can forget multiplicity. Xu et al. make this concrete and argue for injective multiset aggregation when the goal is maximum discrimination within the message-passing family.3

But the lab examples are not failures of mean instead of sum. They are failures of the whole 1-WL contract.

For C6 versus C3 + C3, even an injective multiset function has no separating information to inject. Every node in both graphs keeps receiving the same recursive description:

I am a node whose neighbors are two nodes like me.

The statement is true in the cycle. It is also true in each triangle. The local description never says whether walking forward eventually returns after three steps, six steps, or inside a different connected component. A finite-depth message-passing network may sample that neighborhood repeatedly, but the symmetry of the recursive colors has already collapsed the witnesses.

This is the important distinction:

weak aggregator:      model throws away a multiset difference it was given
1-WL blind spot:      the recursive multisets themselves never differ

The first is an architecture bug you might fix with a better aggregator.

The second is a boundary condition.

The Escape Hatches Change the Problem

There are many ways to beat this lab. None are free.

You can add node features that already break the symmetry. You can give nodes unique IDs, random features, positional encodings, Laplacian eigenvectors, short-cycle counts, or other structural features. You can use higher-order GNNs that pass messages over tuples or subgraphs instead of only over nodes. Morris et al. take this direction explicitly by connecting GNN expressivity to 1-WL and then developing higher-order models tied to stronger WL variants.4

Those are legitimate moves. They also change the input contract.

If you add triangle counts as node features, the model can learn from triangle counts. If you add random identifiers, the model is no longer purely a permutation-invariant function of an unlabeled graph in the same sense. If you move to higher-order message passing, the computational object is no longer just a node state updated from neighboring node states.

This is why “GNNs cannot count triangles” is too sloppy.

A better sentence is:

plain 1-WL-bounded message passing, from identical node labels,
cannot distinguish some graph pairs with different triangle counts

That sentence has enough qualifiers to be useful.

A Practical Debugging Habit

When a graph model succeeds, ask what information contract made success possible.

What were the initial node and edge labels?
Was the task graph-level, node-level, or pairwise?
How many message-passing rounds were used?
Was aggregation injective over multisets, or mean/max-like?
Were positional encodings or random IDs supplied?
Did the readout pool node states in an injective way?
Is the target property visible to 1-WL, or is a higher-order witness needed?

That last question is a good dataset diagnostic. Before training a large GNN, run a small color-refinement baseline. If 1-WL already separates most labels, the model may be learning a robust structural signal. If the labels require triangles, cycles, parity, connectivity, or other witnesses that 1-WL can miss, then a plain message-passing baseline deserves suspicion before it deserves more compute.

The theorem does not make graph neural networks small.

It makes one part of their eyesight auditable.

Sometimes the model is not failing to look hard enough.

Sometimes the graph has already forgotten the triangle.

The lab exports that audit as code. WLMessagePassingLab.audit() checks graph validity, triangle counts, component counts, bipartiteness, the path/cycle positive control, the two blind graph pairs, and the relabeled-cycle sanity case. It also relabels each graph pair with nontrivial left/right permutations and verifies that the equality tape, first distinguishing round, stable round, and color-class size sequence survive the relabeling. The current run performs 310 checks. That is still a microscope, not a theorem prover, but it guards the exact examples the essay asks the reader to trust.

  1. Justin Gilmer, Samuel S. Schoenholz, Patrick F. Riley, Oriol Vinyals, and George E. Dahl, “Neural Message Passing for Quantum Chemistry”, Proceedings of Machine Learning Research 70:1263-1272, 2017. ↩

  2. Sandra Kiefer and Brendan D. McKay, “The Iteration Number of Colour Refinement”, ICALP, 2020. ↩

  3. Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka, “How Powerful are Graph Neural Networks?”, ICLR, 2019. ↩ ↩2

  4. Christopher Morris, Martin Ritzert, Matthias Fey, William L. Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe, “Weisfeiler and Leman Go Neural: Higher-Order Graph Neural Networks”, AAAI, 2019. ↩ ↩2