# An Empirical Study of Realized GNN Expressiveness

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

## Key facts

- Cited by 33 papers in the map (data through 14 Oct 2026).
- Builds on 31 of its 50 references that are in the map.
- First posted on arXiv 16 Apr 2023.

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

- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Graph Neural Networks: A Review of Methods and Applications](https://mlsanity.com/paper/1812.08434/) (2018)
- [CosFace: Large Margin Cosine Loss for Deep Face Recognition](https://mlsanity.com/paper/1801.09414/) (2018)
- [Convolutional Networks on Graphs for Learning Molecular Fingerprints](https://mlsanity.com/paper/1509.09292/) (2015)
- [Graph Neural Networks for Social Recommendation](https://mlsanity.com/paper/1902.07243/) (2019)
- [Provably Powerful Graph Networks](https://mlsanity.com/paper/1905.11136/) (2019)
- [Invariant and Equivariant Graph Networks](https://mlsanity.com/paper/1812.09902/) (2018)
- [Improving Graph Neural Network Expressivity via Subgraph Isomorphism Counting](https://mlsanity.com/paper/2006.09252/) (2020)
- [Can Graph Neural Networks Count Substructures?](https://mlsanity.com/paper/2002.04025/) (2020)
- [The Surprising Power of Graph Neural Networks with Random Node Initialization](https://mlsanity.com/paper/2010.01179/) (2020)
- [Identity-aware Graph Neural Networks](https://mlsanity.com/paper/2101.10320/) (2021)
- [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)
- [Relational Pooling for Graph Representations](https://mlsanity.com/paper/1903.02541/) (2019)
- [RippleNet: Propagating User Preferences on the Knowledge Graph for Recommender Systems](https://mlsanity.com/paper/1803.03467/) (2018)
- [Nested Graph Neural Networks](https://mlsanity.com/paper/2110.13197/) (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)
- [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)
- [How Powerful are K-hop Message Passing Graph Neural Networks](https://mlsanity.com/paper/2205.13328/) (2022)
- [Reconstruction for Powerful Graph Representations](https://mlsanity.com/paper/2110.00577/) (2021)
- [Expressiveness and Approximation Properties of Graph Neural Networks](https://mlsanity.com/paper/2204.04661/) (2022)
- [A Complete Expressiveness Hierarchy for Subgraph GNNs via Subgraph Weisfeiler-Lehman Tests](https://mlsanity.com/paper/2302.07090/) (2023)
- [Ordered Subgraph Aggregation Networks](https://mlsanity.com/paper/2206.11168/) (2022)
- [Boosting the Cycle Counting Power of Graph Neural Networks with I2-GNNs](https://mlsanity.com/paper/2210.13978/) (2022)
- [A Short Tutorial on The Weisfeiler-Lehman Test And Its Variants](https://mlsanity.com/paper/2201.07083/) (2022)
- [A Theoretical Comparison of Graph Neural Network Extensions](https://mlsanity.com/paper/2201.12884/) (2022)

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

- [Embedding in Recommender Systems: A Survey](https://mlsanity.com/paper/2310.18608/) (2023)
- [Comparing Graph Transformers via Positional Encodings](https://mlsanity.com/paper/2402.14202/) (2024)
- [Extending the Design Space of Graph Neural Networks by Rethinking Folklore Weisfeiler-Lehman](https://mlsanity.com/paper/2306.03266/) (2023)
- [MAG-GNN: Reinforcement Learning Boosted Graph Neural Network](https://mlsanity.com/paper/2310.19142/) (2023)
- [Aligning Transformers with Weisfeiler-Leman](https://mlsanity.com/paper/2406.03148/) (2024)
- [Demystifying Higher-Order Graph Neural Networks](https://mlsanity.com/paper/2406.12841/) (2024)
- [Bridging Theory and Practice in Link Representation with Graph Neural Networks](https://mlsanity.com/paper/2506.24018/) (2025)
- [Plain Transformers Can be Powerful Graph Learners](https://mlsanity.com/paper/2504.12588/) (2025)
- [Spectral Graph Neural Networks are Incomplete on Graphs with a Simple Spectrum](https://mlsanity.com/paper/2506.05530/) (2025)
- [On topological descriptors for graph products](https://mlsanity.com/paper/2511.08846/) (2025)
- [Weisfeiler and Leman Go Loopy: A New Hierarchy for Graph Representational Learning](https://mlsanity.com/paper/2403.13749/) (2024)
- [Theoretical Insights into Line Graph Transformation on Graph Learning](https://mlsanity.com/paper/2410.16138/) (2024)
- [On the Utilization of Unique Node Identifiers in Graph Neural Networks](https://mlsanity.com/paper/2411.02271/) (2024)
- [Graph Persistence goes Spectral](https://mlsanity.com/paper/2506.06571/) (2025)
- [Generalizable Insights for Graph Transformers in Theory and Practice](https://mlsanity.com/paper/2511.08028/) (2025)
- [Torsion Graph Neural Networks](https://mlsanity.com/paper/2306.13541/) (2023)
- [Grothendieck Graph Neural Networks Framework: An Algebraic Platform for Crafting Topology-Aware GNNs](https://mlsanity.com/paper/2412.08835/) (2024)
- [Positional Encoding meets Persistent Homology on Graphs](https://mlsanity.com/paper/2506.05814/) (2025)
- [Graph Homomorphism Distortion: A structural (pseudo)-metric for attributed graphs](https://mlsanity.com/paper/2511.03068/) (2025)
- [FloydNet: A Learning Paradigm for Global Relational Reasoning](https://mlsanity.com/paper/2601.19094/) (2026)
- [Measuring Structure in Graph Benchmark Datasets Using Graph Invariants](https://mlsanity.com/paper/2605.06462/) (2026)
- [Scalable Message-Passing Quantum Graph Neural Networks in the Weisfeiler-Leman Hierarchy](https://mlsanity.com/paper/2606.26873/) (2026)
- [Enhancing GNNs with Architecture-Agnostic Graph Transformations: A Systematic Analysis](https://mlsanity.com/paper/2410.08759/) (2024)
- [Enhancing the Utility of Higher-Order Information in Relational Learning](https://mlsanity.com/paper/2502.09570/) (2025)
- [Message Passing on the Edge: Towards Scalable and Expressive GNNs](https://mlsanity.com/paper/2510.13615/) (2025)
- [Property-Driven Evaluation of GNN Expressiveness at Scale: Datasets, Framework, and Study](https://mlsanity.com/paper/2603.00044/) (2026)
- [Invariant-Stratified Propagation for Expressive Graph Neural Networks](https://mlsanity.com/paper/2603.01388/) (2026)
- [Diversity Curves for Graph Representation Learning](https://mlsanity.com/paper/2605.06466/) (2026)
- [Weisfeiler-Leman Is Incomplete on Simple Spectrum Graphs, so Canonicalize Them](https://mlsanity.com/paper/2605.23446/) (2026)
- [Understanding Truncated Positional Encodings for Graph Neural Networks](https://mlsanity.com/paper/2606.13671/) (2026)

## Abstract (arXiv)

Research on the theoretical expressiveness of Graph Neural Networks (GNNs) has developed rapidly, and many methods have been proposed to enhance the expressiveness. However, most methods do not have a uniform expressiveness measure except for a few that strictly follow the k-dimensional Weisfeiler-Lehman (k-WL) test hierarchy, leading to difficulties in quantitatively comparing their expressiveness. Previous research has attempted to use datasets for measurement, but facing problems with difficulty (any model surpassing 1-WL has nearly 100% accuracy), granularity (models tend to be either 100% correct or near random guess), and scale (only several essentially different graphs involved). To address these limitations, we study the realized expressive power that a practical model instance can achieve using a novel expressiveness dataset, BREC, which poses greater difficulty (with up to 4-WL-indistinguishable graphs), finer granularity (enabling comparison of models between 1-WL and 3-WL), a larger scale (consisting of 800 1-WL-indistinguishable graphs that are non-isomorphic to each other). We synthetically test 23 models with higher-than-1-WL expressiveness on BREC. Our experiment gives the first thorough measurement of the realized expressiveness of those state-of-the-art beyond-1-WL GNN models and reveals the gap between theoretical and realized expressiveness. Dataset and evaluation codes are released at: https://github.com/GraphPKU/BREC.