mlsanityData to 14 Oct 2026

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

arXiv 2307.05775 ↗First posted 11 Jul 2023cs.LG cs.SIcited by 0

Not on the map. Why?

Abstract (arXiv)

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-Leman (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' beliefs, 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.

Key facts. No citing papers in the map yet (data through 14 Oct 2026). Builds on 40 of its 81 references that are in the map. First posted on arXiv 11 Jul 2023.

Builds on

40 of 81 references.

References · 40

  1. 2019PyTorch: An Imperative Style, High-Performance Deep Learning Librarycited by 20,305
  2. 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,361
  3. 2017Graph Attention Networkscited by 8,923
  4. 2017Inductive Representation Learning on Large Graphscited by 6,320
  5. 2018How Powerful are Graph Neural Networks?cited by 4,393
  6. 2019Fast Graph Representation Learning with PyTorch Geometriccited by 2,434
  7. 2020Open Graph Benchmark: Datasets for Machine Learning on Graphscited by 2,163
  8. 2018Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networkscited by 881
  9. 2020TUDataset: A collection of benchmark datasets for learning with graphscited by 728
  10. 2019Graph Neural Networks for Social Recommendationcited by 714
  11. 2020Benchmarking Graph Neural Networkscited by 680
  12. 2019GraphSAINT: Graph Sampling Based Inductive Learning Methodcited by 618
28 more
  1. 2020Graph Neural Networks in Recommender Systems: A Surveycited by 494
  2. 2019Provably Powerful Graph Networkscited by 389
  3. 2018Invariant and Equivariant Graph Networkscited by 346
  4. 2020Improving Graph Neural Network Expressivity via Subgraph Isomorphism Countingcited by 313
  5. 2019Measurement and Fairnesscited by 308
  6. 2018Hypothesis Only Baselines in Natural Language Inferencecited by 295
  7. 2021Combinatorial optimization and reasoning with graph neural networkscited by 268
  8. 2020Can Graph Neural Networks Count Substructures?cited by 236
  9. 2020Generalization and Representational Limits of Graph Neural Networkscited by 218
  10. 2021What Will it Take to Fix Benchmarking in Natural Language Understanding?cited by 203
  11. 2019What graph neural networks cannot learn: depth vs widthcited by 201
  12. 2022Pure Transformers are Powerful Graph Learnerscited by 188
  13. 2023On Over-Squashing in Message Passing Neural Networks: The Impact of Width, Depth, and Topologycited by 166
  14. 2021Towards a Unified Framework for Fair and Stable Graph Representation Learningcited by 128
  15. 2023Rethinking the Expressive Power of GNNs via Graph Biconnectivitycited by 119
  16. 2020Stealing Links from Graph Neural Networkscited by 115
  17. 2020Quantifying Privacy Leakage in Graph Embeddingcited by 82
  18. 2021LinkTeller: Recovering Private Edges from Graph Neural Networks via Influence Analysiscited by 65
  19. 2023A Complete Expressiveness Hierarchy for Subgraph GNNs via Subgraph Weisfeiler-Lehman Testscited by 64
  20. 2018GraKeL: A Graph Kernel Library in Pythoncited by 54
  21. 2022Message passing all the way upcited by 47
  22. 2020Targeting the Benchmark: On Methodology in Current Natural Language Processing Researchcited by 45
  23. 2023Queer In AI: A Case Study in Community-Led Participatory AIcited by 34
  24. 2018Attack Graph Convolutional Networks by Adding Fake Nodescited by 26
  25. 2019Understanding Isomorphism Bias in Graph Data Setscited by 23
  26. 2020Counting Substructures with Higher-Order Graph Neural Networks: Possibility and Impossibility Resultscited by 19
  27. 2020Distance Encoding: Design Provably More Powerful Neural Networks for Graph Representation Learningcited by 9
  28. 2023Generalization Limits of Graph Neural Networks in Identity Effects Learningcited by 3

Built on by

Not cited yet.