mlsanityData to 14 Oct 2026

1-WL Expressiveness Is (Almost) All You Need

arXiv 2202.10156 ↗First posted 21 Feb 2022cs.LGcited by 15

Not on the map. Why?

Abstract (arXiv)

It has been shown that a message passing neural networks (MPNNs), a popular family of neural networks for graph-structured data, are at most as expressive as the first-order Weisfeiler-Leman (1-WL) graph isomorphism test, which has motivated the development of more expressive architectures. In this work, we analyze if the limited expressiveness is actually a limiting factor for MPNNs and other WL-based models in standard graph datasets. Interestingly, we find that the expressiveness of WL is sufficient to identify almost all graphs in most datasets. Moreover, we find that the classification accuracy upper bounds are often close to 100%. Furthermore, we find that simple WL-based neural networks and several MPNNs can be fitted to several datasets. In sum, we conclude that the performance of WL/MPNNs is not limited by their expressiveness in practice.

Key facts. Cited by 15 papers in the map (data through 14 Oct 2026). Builds on 26 of its 39 references that are in the map. First posted on arXiv 21 Feb 2022.

Builds on

26 of 39 references.

References · 26

  1. 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,361
  2. 2017Graph Attention Networkscited by 8,923
  3. 2017Inductive Representation Learning on Large Graphscited by 6,320
  4. 2018How Powerful are Graph Neural Networks?cited by 4,393
  5. 2021Geometric Deep Learning: Grids, Groups, Graphs, Geodesics, and Gaugescited by 1,167
  6. 2018Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networkscited by 881
  7. 2020TUDataset: A collection of benchmark datasets for learning with graphscited by 728
  8. 2020Benchmarking Graph Neural Networkscited by 680
  9. 2019Provably Powerful Graph Networkscited by 389
  10. 2020Improving Graph Neural Network Expressivity via Subgraph Isomorphism Countingcited by 313
  11. 2019A Fair Comparison of Graph Neural Networks for Graph Classificationcited by 244
  12. 2020Can Graph Neural Networks Count Substructures?cited by 236
14 more
  1. 2021Weisfeiler and Lehman Go Topological: Message Passing Simplicial Networkscited by 221
  2. 2020Generalization and Representational Limits of Graph Neural Networkscited by 218
  3. 2021Weisfeiler and Lehman Go Cellular: CW Networkscited by 218
  4. 2019What graph neural networks cannot learn: depth vs widthcited by 201
  5. 2020The Surprising Power of Graph Neural Networks with Random Node Initializationcited by 198
  6. 2020Random Features Strengthen Graph Neural Networkscited by 186
  7. 2019On the equivalence between graph isomorphism testing and function approximation with GNNscited by 172
  8. 2021Equivariant Subgraph Aggregation Networkscited by 154
  9. 2021Weisfeiler and Leman go Machine Learning: The Story so farcited by 122
  10. 2021DropGNN: Random Dropouts Increase the Expressiveness of Graph Neural Networkscited by 118
  11. 2020A Survey on The Expressive Power of Graph Neural Networkscited by 111
  12. 2021Breaking the Limits of Message Passing Graph Neural Networkscited by 101
  13. 2022A Short Tutorial on The Weisfeiler-Lehman Test And Its Variantscited by 52
  14. 2019Understanding Isomorphism Bias in Graph Data Setscited by 23

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2022: 3; 2023: 2; 2024: 3; 2025: 5; 2026: 2.

15 papers.

Sort:

  1. 2022Pure Transformers are Powerful Graph Learnerscited by 188
  2. 2022A Generalization of ViT/MLP-Mixer to Graphscited by 93
  3. 2022Evaluating Self-Supervised Learning for Molecular Graph Embeddingscited by 22
  4. 2024Learning Graph Quantized Tokenizerscited by 19
  5. 2024FSW-GNN: A Bi-Lipschitz WL-Equivalent Graph Neural Networkcited by 8
  6. 2025Graph Representational Learning: When Does More Expressivity Hurt Generalization?cited by 5
  7. 2024Theoretical and Empirical Insights into the Origins of Degree Bias in Graph Neural Networkscited by 4
  8. 2023Graphtester: Exploring Theoretical Boundaries of GNNs on Graph Datasetscited by 3
  9. 2025On the Relationship Between Robustness and Expressivity of Graph Neural Networkscited by 3
  10. 2025What Expressivity Theory Misses: Message Passing Complexity for GNNscited by 2
  11. 2023Attacking Graph Neural Networks with Bit Flips: Weisfeiler and Lehman Go Indifferentcited by 0
  12. 2025Model-Level GNN Explanations via Rule-to-Graph Readout for Logit Reconstructioncited by 0
3 more
  1. 2025Exact Generalisation Error Exposes Benchmarks Skew Graph Neural Networks Success (or Failure)cited by 0
  2. 2026Understanding Truncated Positional Encodings for Graph Neural Networkscited by 0
  3. 2026On the Expressive Power of Implicit Line-Graph Higher-Order Weisfeiler--Lemancited by 0