mlsanityData to 7 Oct 2026

An Empirical Study of Realized GNN Expressiveness

arXiv 2304.07702 ↗First posted 16 Apr 2023cs.LG cs.AIcited by 33

Not on the map. Why?

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.

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

Builds on

31 of 50 references.

References · 31

  1. 2018How Powerful are Graph Neural Networks?cited by 4,355
  2. 2018Graph Neural Networks: A Review of Methods and Applicationscited by 1,571
  3. 2018CosFace: Large Margin Cosine Loss for Deep Face Recognitioncited by 968
  4. 2015Convolutional Networks on Graphs for Learning Molecular Fingerprintscited by 751
  5. 2019Graph Neural Networks for Social Recommendationcited by 711
  6. 2019Provably Powerful Graph Networkscited by 385
  7. 2018Invariant and Equivariant Graph Networkscited by 339
  8. 2020Improving Graph Neural Network Expressivity via Subgraph Isomorphism Countingcited by 312
  9. 2020Can Graph Neural Networks Count Substructures?cited by 235
  10. 2021Identity-aware Graph Neural Networkscited by 197
  11. 2020The Surprising Power of Graph Neural Networks with Random Node Initializationcited by 190
  12. 2019On the equivalence between graph isomorphism testing and function approximation with GNNscited by 172
19 more
  1. 2021Equivariant Subgraph Aggregation Networkscited by 154
  2. 2021From Stars to Subgraphs: Uplifting Any GNN with Local Structure Awarenesscited by 154
  3. 2019Relational Pooling for Graph Representationscited by 150
  4. 2018RippleNet: Propagating User Preferences on the Knowledge Graph for Recommender Systemscited by 136
  5. 2021Nested Graph Neural Networkscited by 136
  6. 2023Rethinking the Expressive Power of GNNs via Graph Biconnectivitycited by 119
  7. 2021DropGNN: Random Dropouts Increase the Expressiveness of Graph Neural Networkscited by 117
  8. 2022Understanding and Extending Subgraph GNNs by Rethinking Their Symmetriescited by 112
  9. 2020A Survey on The Expressive Power of Graph Neural Networkscited by 111
  10. 2021Breaking the Limits of Message Passing Graph Neural Networkscited by 101
  11. 2022How Powerful are K-hop Message Passing Graph Neural Networkscited by 90
  12. 2021Reconstruction for Powerful Graph Representationscited by 65
  13. 2023A Complete Expressiveness Hierarchy for Subgraph GNNs via Subgraph Weisfeiler-Lehman Testscited by 64
  14. 2022Expressiveness and Approximation Properties of Graph Neural Networkscited by 63
  15. 2022Ordered Subgraph Aggregation Networkscited by 57
  16. 2022Boosting the Cycle Counting Power of Graph Neural Networks with I2-GNNscited by 55
  17. 2022A Short Tutorial on The Weisfeiler-Lehman Test And Its Variantscited by 52
  18. 2022A Theoretical Comparison of Graph Neural Network Extensionscited by 47
  19. 2022A Practical, Progressively-Expressive GNNcited by 20

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2023: 4; 2024: 8; 2025: 10; 2026: 11.

33 papers.

Sort:

  1. 2024Comparing Graph Transformers via Positional Encodingscited by 20
  2. 2023Embedding in Recommender Systems: A Surveycited by 19
  3. 2023Extending the Design Space of Graph Neural Networks by Rethinking Folklore Weisfeiler-Lehmancited by 13
  4. 2023MAG-GNN: Reinforcement Learning Boosted Graph Neural Networkcited by 11
  5. 2024Aligning Transformers with Weisfeiler-Lemancited by 8
  6. 2024Demystifying Higher-Order Graph Neural Networkscited by 4
  7. 2025Bridging Theory and Practice in Link Representation with Graph Neural Networkscited by 4
  8. 2025Spectral Graph Neural Networks are Incomplete on Graphs with a Simple Spectrumcited by 3
  9. 2024Weisfeiler and Leman Go Loopy: A New Hierarchy for Graph Representational Learningcited by 2
  10. 2024Theoretical Insights into Line Graph Transformation on Graph Learningcited by 2
  11. 2025Plain Transformers Can be Powerful Graph Learnerscited by 2
  12. 2025Generalizable Insights for Graph Transformers in Theory and Practicecited by 2
21 more
  1. 2025On topological descriptors for graph productscited by 2
  2. 2023Torsion Graph Neural Networkscited by 1
  3. 2024On the Utilization of Unique Node Identifiers in Graph Neural Networkscited by 1
  4. 2024Grothendieck Graph Neural Networks Framework: An Algebraic Platform for Crafting Topology-Aware GNNscited by 1
  5. 2025Positional Encoding meets Persistent Homology on Graphscited by 1
  6. 2025Graph Persistence goes Spectralcited by 1
  7. 2025Graph Homomorphism Distortion: A Metric to Distinguish Them All and in the Latent Space Bind Themcited by 1
  8. 2026FloydNet: A Learning Paradigm for Global Relational Reasoningcited by 1
  9. 2026Measuring Structure in Graph Benchmark Datasets Using Graph Invariantscited by 1
  10. 2024Enhancing GNNs with Architecture-Agnostic Graph Transformations: A Systematic Analysiscited by 0
  11. 2025Enhancing the Utility of Higher-Order Information in Relational Learningcited by 0
  12. 2025Message Passing on the Edge: Towards Scalable and Expressive GNNscited by 0
  13. 2026Property-Driven Evaluation of GNN Expressiveness at Scale: Datasets, Framework, and Studycited by 0
  14. 2026Invariant-Stratified Propagation for Expressive Graph Neural Networkscited by 0
  15. 2026Diversity Curves for Graph Representation Learningcited by 0
  16. 2026Weisfeiler-Leman Is Incomplete on Simple Spectrum Graphs, so Canonicalize Themcited by 0
  17. 2026Understanding Truncated Positional Encodings for Graph Neural Networkscited by 0
  18. 2026Scalable Message-Passing Quantum Graph Neural Networks in the Weisfeiler-Leman Hierarchycited by 0
  19. 2026CLEARMIND: Closed-Form Laplacian Embeddings of Arakelov-Green Resistance for Morphological Intrinsic Neuronal Distancescited by 0
  20. 2026Edge-Girth as a Structural Edge Feature for Graph Neural Networkscited by 0
  21. 2026On the Expressive Power of Implicit Line-Graph Higher-Order Weisfeiler--Lemancited by 0