mlsanityData to 7 Oct 2026

A Theoretical Comparison of Graph Neural Network Extensions

arXiv 2201.12884 ↗First posted 30 Jan 2022cs.LGcited by 47

Not on the map. Why?

Abstract (arXiv)

We study and compare different Graph Neural Network extensions that increase the expressive power of GNNs beyond the Weisfeiler-Leman test. We focus on (i) GNNs based on higher order WL methods, (ii) GNNs that preprocess small substructures in the graph, (iii) GNNs that preprocess the graph up to a small radius, and (iv) GNNs that slightly perturb the graph to compute an embedding. We begin by presenting a simple improvement for this last extension that strictly increases the expressive power of this GNN variant. Then, as our main result, we compare the expressiveness of these extensions to each other through a series of example constructions that can be distinguished by one of the extensions, but not by another one. We also show negative examples that are particularly challenging for each of the extensions, and we prove several claims about the ability of these extensions to count cliques and cycles in the graph.

Key facts. Cited by 47 papers in the map (data through 7 Oct 2026). Builds on 27 of its 37 references that are in the map. First posted on arXiv 30 Jan 2022.

Builds on

27 of 37 references.

References · 27

  1. 2018How Powerful are Graph Neural Networks?cited by 4,355
  2. 2017Neural Message Passing for Quantum Chemistrycited by 3,460
  3. 2019A Comprehensive Survey on Graph Neural Networkscited by 2,906
  4. 2018Graph Convolutional Neural Networks for Web-Scale Recommender Systemscited by 1,133
  5. 2018Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networkscited by 878
  6. 2020Learning to Simulate Complex Physics with Graph Networkscited by 867
  7. 2019Provably Powerful Graph Networkscited by 385
  8. 2020Improving Graph Neural Network Expressivity via Subgraph Isomorphism Countingcited by 312
  9. 2020Can Graph Neural Networks Count Substructures?cited by 235
  10. 2021Weisfeiler and Lehman Go Topological: Message Passing Simplicial Networkscited by 219
  11. 2021Weisfeiler and Lehman Go Cellular: CW Networkscited by 218
  12. 2020Generalization and Representational Limits of Graph Neural Networkscited by 217
15 more
  1. 2021Identity-aware Graph Neural Networkscited by 197
  2. 2019What graph neural networks cannot learn: depth vs widthcited by 195
  3. 2020The Surprising Power of Graph Neural Networks with Random Node Initializationcited by 190
  4. 2020Random Features Strengthen Graph Neural Networkscited by 184
  5. 2021Equivariant Subgraph Aggregation Networkscited by 154
  6. 2021Nested Graph Neural Networkscited by 136
  7. 2021Weisfeiler and Leman go Machine Learning: The Story so farcited by 121
  8. 2021DropGNN: Random Dropouts Increase the Expressiveness of Graph Neural Networkscited by 117
  9. 2020A Survey on The Expressive Power of Graph Neural Networkscited by 111
  10. 2019Approximation Ratios of Graph Neural Networks for Combinatorial Problemscited by 68
  11. 2021Reconstruction for Powerful Graph Representationscited by 65
  12. 2018On Weisfeiler-Leman Invariance: Subgraph Counts and Related Graph Propertiescited by 63
  13. 2021Graph Neural Networks with Local Graph Parameterscited by 51
  14. 2021Ego-GNNs: Exploiting Ego Structures in Graph Neural Networkscited by 17
  15. 2019The Power of the Weisfeiler-Leman Algorithm to Decompose Graphscited by 4

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 7; 2023: 19; 2024: 11; 2025: 7; 2026: 3.

47 papers.

Sort:

  1. 2023Rethinking the Expressive Power of GNNs via Graph Biconnectivitycited by 119
  2. 2022Understanding and Extending Subgraph GNNs by Rethinking Their Symmetriescited by 112
  3. 2023A Complete Expressiveness Hierarchy for Subgraph GNNs via Subgraph Weisfeiler-Lehman Testscited by 64
  4. 2022Ordered Subgraph Aggregation Networkscited by 57
  5. 2022Boosting the Cycle Counting Power of Graph Neural Networks with I2-GNNscited by 55
  6. 2024Beyond Weisfeiler-Lehman: A Quantitative Framework for GNN Expressivenesscited by 38
  7. 2023An Empirical Study of Realized GNN Expressivenesscited by 33
  8. 2023WL meet VCcited by 30
  9. 2023Graph Positional Encoding via Random Feature Propagationcited by 30
  10. 2023The Expressive Power of Graph Neural Networks: A Surveycited by 27
  11. 2023Provably Powerful Graph Neural Networks for Directed Multigraphscited by 24
  12. 2023Curvature Filtrations for Graph Generative Model Evaluationcited by 18
35 more
  1. 2023On the Expressivity of Persistent Homology in Graph Learningcited by 18
  2. 2023From Relational Pooling to Subgraph GNNs: A Universal Framework for More Expressive Graph Neural Networkscited by 17
  3. 2023Efficient Subgraph GNNs by Learning Effective Selection Policiescited by 17
  4. 2024Homomorphism Counts for Graph Neural Networks: All About That Basiscited by 16
  5. 2022Agent-based Graph Neural Networkscited by 13
  6. 2023An Efficient Subgraph GNN with Provable Substructure Counting Powercited by 13
  7. 2024Weisfeiler-Leman at the margin: When more expressivity matterscited by 13
  8. 2022On the Ability of Graph Neural Networks to Model Interactions Between Verticescited by 12
  9. 2023What functions can Graph Neural Networks compute on random graphs? The role of Positional Encodingcited by 11
  10. 2023Convergence of Message Passing Graph Neural Networks with Generic Aggregation On Large Random Graphscited by 9
  11. 2024Subgraphormer: Unifying Subgraph GNNs and Graph Transformers via Graph Productscited by 8
  12. 2024A Flexible, Equivariant Framework for Subgraph GNNs via Graph Products and Graph Coarseningcited by 8
  13. 2022Generalizing Downsampling from Regular Data to Graphscited by 6
  14. 2023Union Subgraph Neural Networkscited by 6
  15. 2022Learning Graph Algorithms With Recurrent Graph Neural Networkscited by 5
  16. 2025Balancing Efficiency and Expressiveness: Subgraph GNNs with Walk-Based Centralitycited by 5
  17. 2023Improving Subgraph-GNNs via Edge-Level Ego-Network Encodingscited by 4
  18. 2025Graph Representational Learning: When Does More Expressivity Hurt Generalization?cited by 4
  19. 2024Foundations and Frontiers of Graph Learning Theorycited by 3
  20. 2025Logical Expressiveness of Graph Neural Networks with Hierarchical Node Individualizationcited by 3
  21. 2023Graphtester: Exploring Theoretical Boundaries of GNNs on Graph Datasetscited by 2
  22. 2024Expressive Higher-Order Link Prediction through Hypergraph Symmetry Breakingcited by 2
  23. 2025Plain Transformers Can be Powerful Graph Learnerscited by 2
  24. 2023Flood and Echo Net: Algorithmically Aligned GNNs that Generalizecited by 1
  25. 2024On the Utilization of Unique Node Identifiers in Graph Neural Networkscited by 1
  26. 2026On the Expressive Power of GNNs for Boolean Satisfiabilitycited by 1
  27. 2026Measuring Structure in Graph Benchmark Datasets Using Graph Invariantscited by 1
  28. 2023Local Fragments, Global Gains: Subgraph Counting using Graph Neural Networkscited by 0
  29. 2024Graph Neural Network based Handwritten Trajectories Recognitioncited by 0
  30. 2024GraphFSA: A Finite State Automaton Framework for Algorithmic Learning on Graphscited by 0
  31. 2024Enhancing GNNs with Architecture-Agnostic Graph Transformations: A Systematic Analysiscited by 0
  32. 2025OpenGLT: A Comprehensive Benchmark of Graph Neural Networks for Graph-Level Taskscited by 0
  33. 2025BEACON: A Benchmark for Efficient and Accurate Counting of Subgraphscited by 0
  34. 2025On The Expressive Power of GNN Derivativescited by 0
  35. 2026Weisfeiler Lehman Test on Combinatorial Complexes: Generalized Expressive Power of Topological Neural Networkscited by 0