Weisfeiler and Lehman Go Measurement Modeling: Probing the Validity of the WL Test

Arjun Subramonian, Adina Williams, Maximilian Nickel, Yizhou Sun, Levent Sagun

Abstract

The $k$-Weisfeiler-Leman ($k$-WL) test has become the standard theoretical benchmark for assessing the expressive power of Graph Neural Networks (GNNs). This paper critiques this reliance by applying measurement modeling—a framework from the social sciences—to evaluate the reliability and validity of $k$-WL as a proxy for practical GNN performance. Through expert surveys and empirical audits, the authors demonstrate that $k$-WL is often misaligned with real-world tasks, fails to guarantee generalization due to a lack of isometry, and can inadvertently compromise privacy and fairness.

Introduction: The Expressivity Gap

In the GNN community, "expressive power" is frequently equated with the $k$-WL isomorphism test. A GNN is considered "as powerful as 1-WL" if it can distinguish any two graphs that the 1-WL algorithm can. This theoretical hierarchy has driven researchers to develop increasingly complex models to climb the $k$-WL ladder.

However, a persistent "performance gap" exists: models with higher theoretical expressivity often fail to deliver empirical gains on real-world datasets. This research asks whether $k$-WL actually measures the "expressive power" that practitioners care about, or if the field has been optimizing for a misaligned metric.

Methodology: Auditing the Gold Standard

The authors employ a multi-pronged approach to "audit" the $k$-WL test:

  1. Measurement Modeling: Treating "expressive power" as a theoretical construct and $k$-WL as its operationalization to analyze their link.
  2. Practitioner Survey: A survey of 18 graph ML experts to surface conceptualizations of expressive power and assumptions about $k$-WL.
  3. Graph-Theoretic Analysis: Investigating whether $k$-WL respects metric space axioms, specifically isometry (the principle that similar graphs should have similar representations).
  4. Benchmark Auditing: An empirical analysis of popular GNN benchmarks (e.g., MUTAG, IMDB, PROTEINS) to determine if $k$-WL-based distinctions are necessary for task success.

Key Insights: The Limitations of $k$-WL

The Isometry Problem

A major finding is that $k$-WL is a "binary" test: it identifies if two graphs are different but fails to quantify how different they are. This lack of isometry means two graphs with a small edit distance might be mapped to entirely different $k$-WL "colors," while two structurally distinct graphs might be mapped to the same one.

Figure 2: The 1-WL algorithm assigns colors to nodes based on local neighborhoods. While it distinguishes G2 and G3, it fails to distinguish the 6-cycle (G1) from two 3-cycles (G4) as both result in identical color distributions.

This behavior is antithetical to generalization, which requires that similar inputs produce similar outputs. Without isometry, a model's theoretical power does not necessarily translate to an ability to learn meaningful patterns.

Benchmarks are "Too Easy"

The empirical audit of standard benchmarks like IMDB-BINARY and PROTEINS revealed that the simplest version of the test, 1-WL, can already distinguish 100% of the unique graph instances in these datasets. If a GNN fails to reach 100% accuracy on these tasks, the bottleneck is likely optimization or generalization, not a lack of "expressive power" as defined by $k$-WL.

Results: Privacy and Performance

  • 1-WL Sufficiency: On many popular benchmarks, 1-WL provides more than enough information to solve the tasks. A simple majority-vote baseline using 1-WL colors achieves near 100% accuracy on MUTAG and REDDIT-BINARY.
  • Privacy Risks: High expressivity can be a liability for trustworthiness. In the "German" credit dataset, 100% of nodes are uniquely identifiable by 1-WL after just three iterations. This "identifiability" makes it easier to leak private information or overfit to sensitive attributes like age or gender, creating a direct trade-off between expressivity and fairness.

Conclusion and Future Directions

The survey results highlighted that even experts disagree on what "expressive power" should entail, suggesting that a single test like $k$-WL cannot satisfy all community needs. The authors advocate for extensional definitions of expressive power, where a model's capabilities are defined by its performance on rigorous, task-aligned benchmarks rather than abstract logic tests.

To move forward, the researchers propose a shift toward benchmarks that prioritize generalization and trustworthiness alongside raw power, providing a set of guiding questions to help the community build more valid measurement tools for GNNs.

Summary updated

Abstract

The expressive power of graph neural networks is usually measured by comparing how many pairs of graphs or nodes an architecture can possibly distinguish as non-isomorphic to those distinguishable by the $k$-dimensional Weisfeiler-Lehman ($k$-WL) test. In this paper, we uncover misalignments between graph machine learning practitioners' conceptualizations of expressive power and $k$-WL through a systematic analysis of the reliability and validity of $k$-WL. We conduct a survey ($n = 18$) of practitioners to surface their conceptualizations of expressive power and their assumptions about $k$-WL. In contrast to practitioners' opinions, our analysis (which draws from graph theory and benchmark auditing) reveals that $k$-WL does not guarantee isometry, can be irrelevant to real-world graph tasks, and may not promote generalization or trustworthiness. We argue for extensional definitions and measurement of expressive power based on benchmarks. We further contribute guiding questions for constructing such benchmarks, which is critical for graph machine learning practitioners to develop and transparently communicate our understandings of expressive power.
BibTeX
@misc{subramonian2023weisfeiler,
  author = {Arjun Subramonian and Adina Williams and Maximilian Nickel and Yizhou Sun and Levent Sagun},
  title = {{Weisfeiler and Lehman Go Measurement Modeling: Probing the Validity of the WL Test}},
  year = {2023},
  eprint = {2307.05775},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2307.05775},
}
Figure