# Beyond Weisfeiler-Lehman: A Quantitative Framework for GNN Expressiveness

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

## Key facts

- Cited by 39 papers in the map (data through 14 Oct 2026).
- Builds on 58 of its 96 references that are in the map.
- First posted on arXiv 16 Jan 2024.

## Builds on (most cited first, 30 of 58)

- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Batch Normalization: Accelerating Deep Network Training by Reducing Internal Covariate Shift](https://mlsanity.com/paper/1502.03167/) (2015)
- [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)
- [Neural Message Passing for Quantum Chemistry](https://mlsanity.com/paper/1704.01212/) (2017)
- [Fast Graph Representation Learning with PyTorch Geometric](https://mlsanity.com/paper/1903.02428/) (2019)
- [Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering](https://mlsanity.com/paper/1606.09375/) (2016)
- [Recipe for a General, Powerful, Scalable Graph Transformer](https://mlsanity.com/paper/2205.12454/) (2022)
- [Benchmarking Graph Neural Networks](https://mlsanity.com/paper/2003.00982/) (2020)
- [A Generalization of Transformer Networks to Graphs](https://mlsanity.com/paper/2012.09699/) (2020)
- [Principal Neighbourhood Aggregation for Graph Nets](https://mlsanity.com/paper/2004.05718/) (2020)
- [Rethinking Graph Transformers with Spectral Attention](https://mlsanity.com/paper/2106.03893/) (2021)
- [Residual Gated Graph ConvNets](https://mlsanity.com/paper/1711.07553/) (2017)
- [Graph Neural Networks with Learnable Structural and Positional Representations](https://mlsanity.com/paper/2110.07875/) (2021)
- [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)
- [Weisfeiler and Lehman Go Cellular: CW Networks](https://mlsanity.com/paper/2106.12575/) (2021)
- [Structure-Aware Transformer for Graph Representation Learning](https://mlsanity.com/paper/2202.03036/) (2022)
- [Universal Invariant and Equivariant Graph Neural Networks](https://mlsanity.com/paper/1905.04943/) (2019)
- [Sign and Basis Invariant Networks for Spectral Graph Representation Learning](https://mlsanity.com/paper/2202.13013/) (2022)
- [On the equivalence between graph isomorphism testing and function approximation with GNNs](https://mlsanity.com/paper/1905.12560/) (2019)
- [From Stars to Subgraphs: Uplifting Any GNN with Local Structure Awareness](https://mlsanity.com/paper/2110.03753/) (2021)
- [Equivariant Subgraph Aggregation Networks](https://mlsanity.com/paper/2110.02910/) (2021)
- [Nested Graph Neural Networks](https://mlsanity.com/paper/2110.13197/) (2021)
- [Weisfeiler and Leman go Machine Learning: The Story so far](https://mlsanity.com/paper/2112.09992/) (2021)
- [Rethinking the Expressive Power of GNNs via Graph Biconnectivity](https://mlsanity.com/paper/2301.09505/) (2023)
- [DropGNN: Random Dropouts Increase the Expressiveness of Graph Neural Networks](https://mlsanity.com/paper/2111.06283/) (2021)
- [Understanding and Extending Subgraph GNNs by Rethinking Their Symmetries](https://mlsanity.com/paper/2206.11140/) (2022)

## Built on by (most cited first, 30 of 39)

- [Position: Graph Foundation Models are Already Here](https://mlsanity.com/paper/2402.02216/) (2024)
- [GFT: Graph Foundation Model with Transferable Tree Vocabulary](https://mlsanity.com/paper/2411.06070/) (2024)
- [GraphArena: Evaluating and Exploring Large Language Models on Graph Computation](https://mlsanity.com/paper/2407.00379/) (2024)
- [Towards Graph Foundation Models: Learning Generalities Across Graphs via Task-Trees](https://mlsanity.com/paper/2412.16441/) (2024)
- [A Canonicalization Perspective on Invariant and Equivariant Learning](https://mlsanity.com/paper/2405.18378/) (2024)
- [Beyond Message Passing: Neural Graph Pattern Machine](https://mlsanity.com/paper/2501.18739/) (2025)
- [Homomorphism Counts for Graph Neural Networks: All About That Basis](https://mlsanity.com/paper/2402.08595/) (2024)
- [On the Expressive Power of Spectral Invariant Graph Neural Networks](https://mlsanity.com/paper/2406.04336/) (2024)
- [Revisiting Random Walks for Learning on Graphs](https://mlsanity.com/paper/2407.01214/) (2024)
- [Towards Bridging Generalization and Expressivity of Graph Neural Networks](https://mlsanity.com/paper/2410.10051/) (2024)
- [Generative Graph Pattern Machine](https://mlsanity.com/paper/2505.16130/) (2025)
- [Homomorphism Counts as Structural Encodings for Graph Learning](https://mlsanity.com/paper/2410.18676/) (2024)
- [Semantic Refinement with LLMs for Graph Representations](https://mlsanity.com/paper/2512.21106/) (2025)
- [Higher-Order Topological Directionality and Directed Simplicial Neural Networks](https://mlsanity.com/paper/2409.08389/) (2024)
- [Graph Representational Learning: When Does More Expressivity Hurt Generalization?](https://mlsanity.com/paper/2505.11298/) (2025)
- [Multi-Domain Riemannian Graph Gluing for Building Graph Foundation Models](https://mlsanity.com/paper/2603.00618/) (2026)
- [Demystifying Higher-Order Graph Neural Networks](https://mlsanity.com/paper/2406.12841/) (2024)
- [Towards Graph Foundation Models: A Study on the Generalization of Positional and Structural Encodings](https://mlsanity.com/paper/2412.07407/) (2024)
- [Homomorphism Expressivity of Spectral Invariant Graph Neural Networks](https://mlsanity.com/paper/2503.00485/) (2025)
- [On Universality Classes of Equivariant Networks](https://mlsanity.com/paper/2506.02293/) (2025)
- [Foundations and Frontiers of Graph Learning Theory](https://mlsanity.com/paper/2407.03125/) (2024)
- [Plain Transformers Can be Powerful Graph Learners](https://mlsanity.com/paper/2504.12588/) (2025)
- [Weisfeiler and Leman Go Loopy: A New Hierarchy for Graph Representational Learning](https://mlsanity.com/paper/2403.13749/) (2024)
- [Separation Power of Equivariant Neural Networks](https://mlsanity.com/paper/2406.08966/) (2024)
- [Generalization Performance of Hypergraph Neural Networks](https://mlsanity.com/paper/2501.12554/) (2025)
- [What Expressivity Theory Misses: Message Passing Complexity for GNNs](https://mlsanity.com/paper/2509.01254/) (2025)
- [Position: Don't be Afraid of Over-Smoothing And Over-Squashing](https://mlsanity.com/paper/2601.07419/) (2026)
- [Fine-Grained Expressive Power of Weisfeiler-Leman: A Homomorphism Counting Perspective](https://mlsanity.com/paper/2410.03517/) (2024)
- [Enhancing Graph Neural Networks in Large-scale Traffic Incident Analysis with Concurrency Hypothesis](https://mlsanity.com/paper/2411.02542/) (2024)
- [FloydNet: A Learning Paradigm for Global Relational Reasoning](https://mlsanity.com/paper/2601.19094/) (2026)

## Abstract (arXiv)

Designing expressive Graph Neural Networks (GNNs) is a fundamental topic in the graph learning community. So far, GNN expressiveness has been primarily assessed via the Weisfeiler-Lehman (WL) hierarchy. However, such an expressivity measure has notable limitations: it is inherently coarse, qualitative, and may not well reflect practical requirements (e.g., the ability to encode substructures). In this paper, we introduce a unified framework for quantitatively studying the expressiveness of GNN architectures, addressing all the above limitations. Specifically, we identify a fundamental expressivity measure termed homomorphism expressivity, which quantifies the ability of GNN models to count graphs under homomorphism. Homomorphism expressivity offers a complete and practical assessment tool: the completeness enables direct expressivity comparisons between GNN models, while the practicality allows for understanding concrete GNN abilities such as subgraph counting. By examining four classes of prominent GNNs as case studies, we derive simple, unified, and elegant descriptions of their homomorphism expressivity for both invariant and equivariant settings. Our results provide novel insights into a series of previous work, unify the landscape of different subareas in the community, and settle several open questions. Empirically, extensive experiments on both synthetic and real-world tasks verify our theory, showing that the practical performance of GNN models aligns well with the proposed metric.