WL Tests Are Far from All We Need: Revisiting WL-Test Hardness and GNN Expressive Power from a Distributed Computation Perspective

Guanyu Cui, Zhewei Wei, Hsin-Hao Su, Su, Hsin-Hao

Abstract

The expressive power of graph neural networks (GNNs) is often studied through their relationship to the Weisfeiler-Lehman (WL) tests. Despite its influence, this perspective leaves two gaps: (i) it is unclear whether WL tests are sufficiently primitive for understanding GNN expressivity, and (ii) WL-induced equivalence does not align well with characterizing the function classes that GNNs can approximate or compute. We attempt to address both gaps. First, we strengthen hardness results for the vanilla WL test, showing that in many settings it is not primitive enough to be implemented by constant-depth GNNs. Second, we propose an alternative framework for studying GNN expressivity based on an extended CONGEST model with an explicit preprocessing phase. Within this framework, we identify implicit shortcuts introduced in prior analyses and establish further results for WL tests in settings where graphs are augmented with virtual nodes and virtual edges.

Introduction

For years, the Weisfeiler-Lehman (WL) test has served as the primary benchmark for measuring the expressive power of Graph Neural Networks (GNNs). A GNN is typically deemed "powerful" if it can distinguish non-isomorphic graphs as effectively as the 1-WL test. However, this paper argues that equating GNN expressivity with WL-equivalence is a coarse metric that overlooks the actual computational complexity of simulating WL logic.

The authors identify two critical issues with the current paradigm. First, the assumption that one WL iteration corresponds to a single GNN layer is often false; if simulating one WL step requires substantial depth, then WL-equivalence is an impractical measure of efficiency. Second, WL tests focus on graph isomorphism (a discrete task), whereas GNNs are frequently used to approximate continuous functions, creating a semantic mismatch.

The RL-CONGEST Framework

To bridge these gaps, the authors reframe GNNs as distributed computing systems using the CONGEST model. In this model, nodes communicate via limited-size messages. The paper introduces Resource-Limited CONGEST (RL-CONGEST), which explicitly models the computational pipeline of a GNN.

The RL-CONGEST framework consists of three stages: (1) Preprocessing to generate initial features, (2) Message-passing with limited computational resources, and (3) Postprocessing for final readout.

The RL-CONGEST framework incorporates a Preprocessing Phase to account for features calculated before message passing (e.g., node degrees or distance metrics) and Computational Constraints that restrict the complexity of node update functions to specific classes (like $TC^0$) to reflect realistic hardware limitations.

Hardness of WL Simulation

Using RL-CONGEST, the authors derive bounds on the depth ($d$), width ($w$), and precision ($p$) required to simulate a single WL iteration. A key finding is that in a deterministic setting, the required depth is $\Omega(D + m/wp)$, where $D$ is the graph diameter and $m$ is the number of edges. This implies that for many graph topologies, simulating WL logic requires a depth that scales with the graph's size, rather than being a constant-depth "primitive."

Interestingly, randomness can act as a "cheat code." If the model allows for a small error probability and a sufficiently large "color space" (node label range), a WL iteration can be simulated in just one layer ($d=1$). However, if the color space is restricted, even randomness fails to overcome the depth requirements.

Preprocessing and "Shortcuts" in Expressivity

The paper also highlights how heavy preprocessing can create an illusion of high expressivity. Many GNN variants that claim to solve global problems, such as biconnectivity, do so by including precomputed features like "all-pairs shortest paths" or "resistance distances."

The authors prove that while biconnectivity is a global property, it becomes locally verifiable (0-local or 1-local) once such features are provided. This suggests that these GNNs aren't necessarily more powerful at processing information; they simply benefit from global information injected during the preprocessing stage. Empirical tests on Erdős-Rényi graphs confirm that simple indicator functions using these features can outperform complex GNNs on global tasks.

Summary of Theoretical Results

The main contributions are summarized in the following table of upper and lower bounds for depth ($d$) and width-precision ($wp$) across different settings.

Summary of the paper's main theoretical results, providing upper and lower bounds for GNN depth and width-precision across deterministic and randomized settings.

Conclusion

This work shifts the focus from simple WL-equivalence to a more nuanced understanding of GNN complexity. By analyzing GNNs through the lens of distributed computing, the authors demonstrate that the trade-off between depth, width, and preprocessing is fundamental to understanding what GNNs can actually compute. Future research should prioritize these trade-offs over chasing WL-equivalence in isolation.

Summary updated

Abstract

The expressive power of graph neural networks (GNNs) is often studied through their relationship to the Weisfeiler-Lehman (WL) tests. Despite its influence, this perspective leaves two gaps: (i) it is unclear whether WL tests are sufficiently primitive for understanding GNN expressivity, and (ii) WL-induced equivalence does not align well with characterizing the function classes that GNNs can approximate or compute. We attempt to address both gaps. First, we strengthen hardness results for the vanilla WL test, showing that in many settings it is not primitive enough to be implemented by constant-depth GNNs. Second, we propose an alternative framework for studying GNN expressivity based on an extended CONGEST model with an explicit preprocessing phase. Within this framework, we identify implicit shortcuts introduced in prior analyses and establish further results for WL tests in settings where graphs are augmented with virtual nodes and virtual edges.
BibTeX
@misc{cui2024wl,
  author = {Guanyu Cui and Zhewei Wei and Hsin-Hao Su and Su, Hsin-Hao},
  title = {{WL Tests Are Far from All We Need: Revisiting WL-Test Hardness and GNN Expressive Power from a Distributed Computation Perspective}},
  year = {2024},
  eprint = {2410.01308},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2410.01308},
}
Figure