Beyond 1-WL: Higher-Order and Subgraph GNNs

A message-passing network cannot tell a 6-cycle from two disjoint triangles. Every node in both graphs has degree two, every neighbourhood looks identical at every depth, and so the multiset of node representations is identical however many layers you stack. The ceiling is exactly the one-dimensional Weisfeiler-Leman test, and sum aggregation with an injective update reaches it but cannot pass it (Xu et al., 2019, How Powerful are Graph Neural Networks?, ICLR). If your task depends on counting cycles, detecting substructures, or distinguishing regular graphs, that ceiling is not academic.

Three families of fix exist, and they differ mainly in what they charge you. (Expressive power and the WL test covers the ceiling itself; this concept is about the ways out.)

Climbing the WL hierarchy directly

The \(k\)-dimensional WL test colours \(k\)-tuples of nodes rather than single nodes, and the hierarchy is strict: \((k+1)\)-WL distinguishes graph pairs that \(k\)-WL cannot. Building a network on that colouring gives \(k\)-GNNs, which are provably more powerful than ordinary message passing (Morris et al., 2019, Weisfeiler and Leman Go Neural, AAAI).

The arithmetic is brutal. There are \(n^k\) tuples, so memory grows as \(O(n^k)\) and a layer touches every tuple's neighbourhood. For \(k=3\) on a 100-node molecule that is a million states per layer; on a social graph it is not expressible at all.

The equivariant-tensor view narrows the gap. \(k\)-order invariant networks match \(k\)-WL, and a 2-order model built from matrix multiplication of feature tensors achieves 3-WL power with \(O(n^2)\) memory and no \(n^3\) tensor (Maron et al., 2019, Provably Powerful Graph Networks, NeurIPS). That is the practical ceiling of this family: 3-WL at quadratic cost.

Subgraphs instead of tuples

The second family notices something cheaper. Graphs that 1-WL confuses usually contain subgraphs that 1-WL can tell apart, so run the base network on local pieces and aggregate.

Nested GNNs give each node a rooted subgraph, run a base GNN inside it, and pool the subgraph representations. The representation is then of a rooted subgraph rather than a rooted subtree, which is what 1-WL is really limited to; the result is strictly stronger than 1-WL, discriminates almost all \(r\)-regular graphs, and costs only a constant factor over a standard GNN (Zhang and Li, 2021, Nested Graph Neural Networks, NeurIPS).

Equivariant Subgraph Aggregation Networks generalise the idea to a bag of subgraphs produced by a policy, for example every graph obtained by deleting one edge, processed by an architecture equivariant to the bag's symmetries. The paper proves lower bounds on expressivity in terms of WL variants defined on bags, and raises the power of both message passing and stronger backbones (Bevilacqua et al., 2022, Equivariant Subgraph Aggregation Networks, ICLR). The cost is the bag size: a policy producing \(|E|\) subgraphs multiplies every forward pass by \(|E|\), which is why the same paper offers subgraph sampling as a stochastic approximation.

Encodings instead of architecture

The third family changes nothing about the message passing and adds precomputed structural features: counts of triangles or small cycles per node, random-walk return probabilities, shortest-path distances as attention biases. A network that receives a per-node triangle count can distinguish the 6-cycle from two triangles at layer one, with no change to its asymptotics. This is the cheapest escape and the reason graph positional and structural encodings matter well beyond graph transformers.

The catch is that the encoding fixes what you can count in advance. Subgraph and higher-order models learn which structures matter; encodings require you to have guessed.

When it breaks

Isomorphism distinguishing is a weak proxy for the task. A model can be strictly more expressive and generalise worse, because the extra capacity is spent on distinctions the labels do not depend on. The ranking of expressivity classes and the ranking of test accuracy are different orders, and nothing guarantees they agree.

The benchmark gaps that motivated the search keep shrinking under tuning. On the Long-Range Graph Benchmark, the reported advantage of graph transformers over message passing largely disappeared once the baselines received basic hyperparameter optimisation, and one of the metrics had been implemented incorrectly (Tönshoff et al., 2024, Where Did the Gap Go?, TMLR). Before paying for expressivity, check that a tuned baseline cannot close the gap.

Cost lands at inference as well as training. A bag-of-subgraphs model pays its multiplier on every prediction, which rules it out for online serving on large graphs even where the accuracy is real.

Sampling removes the guarantee you paid for. Subgraph sampling makes ESAN-style models affordable, and the expressivity proofs apply to the full bag. The sampled model is an approximation whose discriminative power is not what was proved.