# 1-WL Expressiveness Is (Almost) All You Need

arXiv: https://arxiv.org/abs/2202.10156 · HTML: https://mlsanity.com/paper/2202.10156/

## 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 (most cited first, 26 of 26)

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Geometric Deep Learning: Grids, Groups, Graphs, Geodesics, and Gauges](https://mlsanity.com/paper/2104.13478/) (2021)
- [Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networks](https://mlsanity.com/paper/1810.02244/) (2018)
- [TUDataset: A collection of benchmark datasets for learning with graphs](https://mlsanity.com/paper/2007.08663/) (2020)
- [Benchmarking Graph Neural Networks](https://mlsanity.com/paper/2003.00982/) (2020)
- [Provably Powerful Graph Networks](https://mlsanity.com/paper/1905.11136/) (2019)
- [Improving Graph Neural Network Expressivity via Subgraph Isomorphism Counting](https://mlsanity.com/paper/2006.09252/) (2020)
- [A Fair Comparison of Graph Neural Networks for Graph Classification](https://mlsanity.com/paper/1912.09893/) (2019)
- [Can Graph Neural Networks Count Substructures?](https://mlsanity.com/paper/2002.04025/) (2020)
- [Weisfeiler and Lehman Go Topological: Message Passing Simplicial Networks](https://mlsanity.com/paper/2103.03212/) (2021)
- [Generalization and Representational Limits of Graph Neural Networks](https://mlsanity.com/paper/2002.06157/) (2020)
- [Weisfeiler and Lehman Go Cellular: CW Networks](https://mlsanity.com/paper/2106.12575/) (2021)
- [What graph neural networks cannot learn: depth vs width](https://mlsanity.com/paper/1907.03199/) (2019)
- [The Surprising Power of Graph Neural Networks with Random Node Initialization](https://mlsanity.com/paper/2010.01179/) (2020)
- [Random Features Strengthen Graph Neural Networks](https://mlsanity.com/paper/2002.03155/) (2020)
- [On the equivalence between graph isomorphism testing and function approximation with GNNs](https://mlsanity.com/paper/1905.12560/) (2019)
- [Equivariant Subgraph Aggregation Networks](https://mlsanity.com/paper/2110.02910/) (2021)
- [Weisfeiler and Leman go Machine Learning: The Story so far](https://mlsanity.com/paper/2112.09992/) (2021)
- [DropGNN: Random Dropouts Increase the Expressiveness of Graph Neural Networks](https://mlsanity.com/paper/2111.06283/) (2021)
- [A Survey on The Expressive Power of Graph Neural Networks](https://mlsanity.com/paper/2003.04078/) (2020)
- [Breaking the Limits of Message Passing Graph Neural Networks](https://mlsanity.com/paper/2106.04319/) (2021)
- [A Short Tutorial on The Weisfeiler-Lehman Test And Its Variants](https://mlsanity.com/paper/2201.07083/) (2022)
- [Understanding Isomorphism Bias in Graph Data Sets](https://mlsanity.com/paper/1910.12091/) (2019)

## Built on by (most cited first, 15 of 15)

- [Pure Transformers are Powerful Graph Learners](https://mlsanity.com/paper/2207.02505/) (2022)
- [A Generalization of ViT/MLP-Mixer to Graphs](https://mlsanity.com/paper/2212.13350/) (2022)
- [Evaluating Self-Supervised Learning for Molecular Graph Embeddings](https://mlsanity.com/paper/2206.08005/) (2022)
- [Learning Graph Quantized Tokenizers](https://mlsanity.com/paper/2410.13798/) (2024)
- [FSW-GNN: A Bi-Lipschitz WL-Equivalent Graph Neural Network](https://mlsanity.com/paper/2410.09118/) (2024)
- [Graph Representational Learning: When Does More Expressivity Hurt Generalization?](https://mlsanity.com/paper/2505.11298/) (2025)
- [Theoretical and Empirical Insights into the Origins of Degree Bias in Graph Neural Networks](https://mlsanity.com/paper/2404.03139/) (2024)
- [Graphtester: Exploring Theoretical Boundaries of GNNs on Graph Datasets](https://mlsanity.com/paper/2306.17482/) (2023)
- [On the Relationship Between Robustness and Expressivity of Graph Neural Networks](https://mlsanity.com/paper/2504.13786/) (2025)
- [What Expressivity Theory Misses: Message Passing Complexity for GNNs](https://mlsanity.com/paper/2509.01254/) (2025)
- [Attacking Graph Neural Networks with Bit Flips: Weisfeiler and Lehman Go Indifferent](https://mlsanity.com/paper/2311.01205/) (2023)
- [Model-Level GNN Explanations via Rule-to-Graph Readout for Logit Reconstruction](https://mlsanity.com/paper/2503.09051/) (2025)
- [Exact Generalisation Error Exposes Benchmarks Skew Graph Neural Networks Success (or Failure)](https://mlsanity.com/paper/2509.10337/) (2025)
- [Understanding Truncated Positional Encodings for Graph Neural Networks](https://mlsanity.com/paper/2606.13671/) (2026)
- [On the Expressive Power of Implicit Line-Graph Higher-Order Weisfeiler--Leman](https://mlsanity.com/paper/2609.16412/) (2026)

## 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.