Expressive Power and the WL Test

Most questions about a neural architecture's power are empirical. For message-passing graph networks there is an exact answer, and it is a limitation rather than a capability: no such network can distinguish two graphs that the one-dimensional Weisfeiler-Leman colour refinement test cannot distinguish (Xu et al., 2019, How Powerful are Graph Neural Networks?, arXiv:1810.00826).

The correspondence

The 1-WL test refines node colours iteratively: each node's new colour is a hash of its own colour together with the multiset of its neighbours' colours. Two graphs are declared possibly isomorphic if their colour histograms match at every round.

A message-passing network does structurally the same thing with learned functions instead of a hash: each node's new representation is a function of its own representation and an aggregation over its neighbours'. If two nodes have identical colours under 1-WL, no message-passing network can give them different representations, because the network's information is exactly the information WL uses.

The correspondence is tight in both directions. The network is bounded above by WL, and with a sufficiently expressive aggregation it reaches that bound.

Why the aggregation function decides

The bound is achieved only if the aggregation is injective over multisets, meaning different neighbour multisets produce different outputs.

Mean loses multiplicity. A node with neighbours \(\{a, a, b\}\) and one with \(\{a, b\}\) produce the same mean, so degree information and repetition are discarded.

Max loses everything but the extreme. \(\{a, a, b\}\) and \(\{a, b, b\}\) have the same maximum.

Sum preserves the multiset, since different multisets of distinct elements sum differently, which is why the Graph Isomorphism Network uses sum aggregation followed by an MLP and achieves the WL bound while mean- and max-based architectures provably do not.

This is a rare case where a small architectural detail has a proven consequence rather than an empirical one.

What lies beyond the ceiling

1-WL cannot count triangles, cannot distinguish two disjoint triangles from a six-cycle, and cannot distinguish many regular graphs. Since triangle counts and cycle structure matter in molecular chemistry and in social networks, this is a practical limitation rather than a theoretical curiosity.

The escapes are all forms of adding information the message passing cannot derive. Injecting structural features such as cycle counts or subgraph counts as node attributes; adding random or positional node identifiers so symmetric nodes become distinguishable; passing messages over higher-order structures rather than nodes; or operating on subgraphs. Each buys expressiveness and costs either computation or permutation invariance.

When it breaks

Expressiveness is not accuracy. A more expressive architecture can distinguish more graphs and can also overfit more, and on many benchmarks simpler models perform comparably. The theory bounds what is possible, not what is useful.

Node features often make the bound irrelevant. WL analysis assumes uninformative initial features. With rich node attributes, nodes are already distinguishable and the structural ceiling rarely binds, which is why the limitation matters most on molecular and combinatorial graphs and least on attributed social or citation graphs.

Random identifiers break invariance. Adding random node features makes the network's output depend on the random draw, so permutation invariance is lost and must be recovered by averaging over draws, which costs multiple forward passes.

Higher-order methods scale badly. Passing messages over node tuples has complexity growing with the tuple size, which limits it to small graphs regardless of its theoretical appeal.