mlsanityData to 13 Oct 2026

The Expressive Power of Graph Neural Networks: A Survey

arXiv 2308.08235 ↗First posted 16 Aug 2023cs.LG cs.SIcited by 27

Not on the map. Why?

Abstract (arXiv)

Graph neural networks (GNNs) are effective machine learning models for many graph-related applications. Despite their empirical success, many research efforts focus on the theoretical limitations of GNNs, i.e., the GNNs expressive power. Early works in this domain mainly focus on studying the graph isomorphism recognition ability of GNNs, and recent works try to leverage the properties such as subgraph counting and connectivity learning to characterize the expressive power of GNNs, which are more practical and closer to real-world. However, no survey papers and open-source repositories comprehensively summarize and discuss models in this important direction. To fill the gap, we conduct a first survey for models for enhancing expressive power under different forms of definition. Concretely, the models are reviewed based on three categories, i.e., Graph feature enhancement, Graph topology enhancement, and GNNs architecture enhancement.

Key facts. Cited by 27 papers in the map (data through 13 Oct 2026). Builds on 89 of its 139 references that are in the map. First posted on arXiv 16 Aug 2023.

Builds on

89 of 139 references.

References · 89

  1. 2017Graph Attention Networkscited by 8,888
  2. 2017Inductive Representation Learning on Large Graphscited by 6,303
  3. 2018How Powerful are Graph Neural Networks?cited by 4,373
  4. 2017Neural Message Passing for Quantum Chemistrycited by 3,471
  5. 2019A Comprehensive Survey on Graph Neural Networkscited by 2,911
  6. 2018Graph Neural Networks: A Review of Methods and Applicationscited by 1,574
  7. 2018Relational inductive biases, deep learning, and graph networkscited by 1,353
  8. 2018Predict then Propagate: Graph Neural Networks meet Personalized PageRankcited by 991
  9. 2018Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networkscited by 878
  10. 2020Geom-GCN: Geometric Graph Convolutional Networkscited by 826
  11. 2018Hierarchical Graph Representation Learning with Differentiable Poolingcited by 787
  12. 2020On the Bottleneck of Graph Neural Networks and its Practical Implicationscited by 629
38 more
  1. 2020Adaptive Universal Generalized PageRank Graph Neural Networkcited by 595
  2. 2017Learning Combinatorial Optimization Algorithms over Graphscited by 557
  3. 2019Measuring and Relieving the Over-smoothing Problem for Graph Neural Networks from the Topological Viewcited by 545
  4. 2016Interaction Networks for Learning about Objects, Relations and Physicscited by 505
  5. 2021Understanding over-squashing and bottlenecks on graphs via curvaturecited by 473
  6. 2019MixHop: Higher-Order Graph Convolutional Architectures via Sparsified Neighborhood Mixingcited by 443
  7. 2018Deep Learning on Graphs: A Surveycited by 393
  8. 2019Provably Powerful Graph Networkscited by 386
  9. 2019KGAT: Knowledge Graph Attention Network for Recommendationcited by 342
  10. 2018Invariant and Equivariant Graph Networkscited by 341
  11. 2020Improving Graph Neural Network Expressivity via Subgraph Isomorphism Countingcited by 312
  12. 2020SIGN: Scalable Inception Graph Neural Networkscited by 284
  13. 2018Auto-Encoding Scene Graphs for Image Captioningcited by 255
  14. 2020Can Graph Neural Networks Count Substructures?cited by 235
  15. 2020Reinforcement Learning for Combinatorial Optimization: A Surveycited by 235
  16. 2021Weisfeiler and Lehman Go Topological: Message Passing Simplicial Networkscited by 220
  17. 2020Generalization and Representational Limits of Graph Neural Networkscited by 217
  18. 2022Neural Sheaf Diffusion: A Topological Perspective on Heterophily and Oversmoothing in GNNscited by 210
  19. 2019Position-aware Graph Neural Networkscited by 203
  20. 2019What graph neural networks cannot learn: depth vs widthcited by 198
  21. 2021Identity-aware Graph Neural Networkscited by 197
  22. 2020The Surprising Power of Graph Neural Networks with Random Node Initializationcited by 192
  23. 2020Random Features Strengthen Graph Neural Networkscited by 184
  24. 2019Universal Invariant and Equivariant Graph Neural Networkscited by 182
  25. 2019On the equivalence between graph isomorphism testing and function approximation with GNNscited by 172
  26. 2018Measuring abstract reasoning in neural networkscited by 165
  27. 2019What Can Neural Networks Reason About?cited by 158
  28. 2021Equivariant Subgraph Aggregation Networkscited by 154
  29. 2021From Stars to Subgraphs: Uplifting Any GNN with Local Structure Awarenesscited by 154
  30. 2019On the Universality of Invariant Networkscited by 151
  31. 2019Relational Pooling for Graph Representationscited by 150
  32. 2021Nested Graph Neural Networkscited by 136
  33. 2021Interpreting and Unifying Graph Neural Networks with An Optimization Frameworkcited by 131
  34. 2020AM-GCN: Adaptive Multi-channel Graph Convolutional Networkscited by 121
  35. 2023Rethinking the Expressive Power of GNNs via Graph Biconnectivitycited by 119
  36. 2021DropGNN: Random Dropouts Increase the Expressiveness of Graph Neural Networkscited by 117
  37. 2022Understanding and Extending Subgraph GNNs by Rethinking Their Symmetriescited by 112
  38. 2020A Survey on The Expressive Power of Graph Neural Networkscited by 111

50 most cited of 89 All 89 (JSON)

Built on by

Cited by year (2026 to 13 Oct)

Citing papers per year: 2023: 1; 2024: 9; 2025: 12; 2026: 5.

27 papers.

Sort:

By area:

  1. 2023Exposition on over-squashing problem on GNNs: Current Methods, Benchmarks and Challengescited by 22
  2. 2024Expressivity and Generalization: Fragment-Biases for Molecular GNNscited by 8
  3. 2024Homomorphism Counts as Structural Encodings for Graph Learningcited by 7
  4. 2024Future Directions in the Theory of Graph Machine Learningcited by 6
  5. 2024Multi-Type Point Cloud Autoencoder: A Complete Equivariant Embedding for Molecule Conformation and Posecited by 3
  6. 2024Heterogeneous Graph Auto-Encoder for CreditCard Fraud Detectioncited by 3
  7. 2025RoME: Domain-Robust Mixture-of-Experts for MILP Solution Prediction across Domainscited by 3
  8. 2024The Role of Fibration Symmetries in Geometric Deep Learningcited by 2
  9. 2025On the Interplay between Graph Structure and Learning Algorithms in Graph Neural Networkscited by 2
  10. 2024Understanding the Robustness of Graph Neural Networks against Adversarial Attackscited by 1
  11. 2025Khan-GCL: Kolmogorov-Arnold Network Based Graph Contrastive Learning with Hard Negativescited by 1
  12. 2025Heat Kernel Goes Topologicalcited by 1
15 more
  1. 2024SE-VGAE: Unsupervised Disentangled Representation Learning for Interpretable Architectural Layout Design Graph Generationcited by 0
  2. 2024Enhancing Missing Data Imputation through Combined Bipartite Graph and Complete Directed Graphcited by 0
  3. 2025Graph Attention Networks Unleashed: A Fast and Explainable Vulnerability Assessment Framework for Microgridscited by 0
  4. 2025Disentangled Graph Representation Based on Substructure-Aware Graph Optimal Matching Kernel Convolutional Networkscited by 0
  5. 2025A method for the systematic generation of graph XAI benchmarks via Weisfeiler-Leman coloringcited by 0
  6. 2025Chordless Structure: A Pathway to Simple and Expressive GNNscited by 0
  7. 2025Topology-Assisted Spatio-Temporal Pattern Disentangling for Scalable MARL in Large-scale Autonomous Traffic Controlcited by 0
  8. 2025Exploring Graph-Transformer Out-of-Distribution Generalization Abilitiescited by 0
  9. 2025PAC-Bayesian Generalization Bounds for Graph Convolutional Networks on Inductive Node Classificationcited by 0
  10. 2025On The Expressive Power of GNN Derivativescited by 0
  11. 2026Hyperbolic Heterogeneous Graph Transformercited by 0
  12. 2026A Boolean Function-Theoretic Framework for Expressivity in GNNs with Applications to Fair Graph Miningcited by 0
  13. 2026Contraction and Hourglass Persistence for Learning on Graphs, Simplices, and Cellscited by 0
  14. 2026Weisfeiler Lehman Test on Combinatorial Complexes: Generalized Expressive Power of Topological Neural Networkscited by 0
  15. 2026Polarity-Asymmetric Structural Calibration for Link Sign Predictioncited by 0