mlsanityData to 7 Oct 2026

A Survey on The Expressive Power of Graph Neural Networks

arXiv 2003.04078 ↗First posted 9 Mar 2020cs.LG stat.MLcited by 111

Not on the map. Why?

Abstract (arXiv)

Graph neural networks (GNNs) are effective machine learning models for various graph learning problems. Despite their empirical successes, the theoretical limitations of GNNs have been revealed recently. Consequently, many GNN models have been proposed to overcome these limitations. In this survey, we provide a comprehensive overview of the expressive power of GNNs and provably powerful variants of GNNs.

Key facts. Cited by 111 papers in the map (data through 7 Oct 2026). First posted on arXiv 9 Mar 2020.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 18; 2022: 32; 2023: 23; 2024: 24; 2025: 11; 2026: 3.

111 papers.

Sort:

By area:

  1. 2022Recipe for a General, Powerful, Scalable Graph Transformercited by 702
  2. 2021Graph Neural Networks with Learnable Structural and Positional Representationscited by 326
  3. 2021Weisfeiler and Lehman Go Cellular: CW Networkscited by 218
  4. 2022Sign and Basis Invariant Networks for Spectral Graph Representation Learningcited by 176
  5. 2021Equivariant Subgraph Aggregation Networkscited by 154
  6. 2023Rethinking the Expressive Power of GNNs via Graph Biconnectivitycited by 119
  7. 2022Understanding and Extending Subgraph GNNs by Rethinking Their Symmetriescited by 112
  8. 2021SLAPS: Self-Supervision Improves Structure Learning for Graph Neural Networkscited by 108
  9. 2021Breaking the Limit of Graph Neural Networks by Improving the Assortativity of Graphs with Local Mixing Patternscited by 95
  10. 2021Size-Invariant Graph Representations for Graph Classification Extrapolationscited by 82
  11. 2023Efficient and Degree-Guided Graph Generation via Discrete Diffusion Modelingcited by 75
  12. 2021Subgroup Generalization and Fairness of Graph Neural Networkscited by 69
38 more
  1. 2021Understanding Pooling in Graph Neural Networkscited by 69
  2. 2024Polynormer: Polynomial-Expressive Graph Transformer in Linear Timecited by 64
  3. 2023Graph Neural Networks for temporal graphs: State of the art, open challenges, and opportunitiescited by 60
  4. 2022A Short Tutorial on The Weisfeiler-Lehman Test And Its Variantscited by 52
  5. 2021Graph Neural Networks with Local Graph Parameterscited by 51
  6. 2022A Theoretical Comparison of Graph Neural Network Extensionscited by 47
  7. 2022On Representing Linear Programs by Graph Neural Networkscited by 39
  8. 2023The expressive power of pooling in Graph Neural Networkscited by 35
  9. 2023An Empirical Study of Realized GNN Expressivenesscited by 33
  10. 2022Parallel and Distributed Graph Neural Networks: An In-Depth Concurrency Analysiscited by 29
  11. 2022Graph Neural Networks in IoT: A Surveycited by 27
  12. 2023The Expressive Power of Graph Neural Networks: A Surveycited by 27
  13. 2023Over-Squashing in Graph Neural Networks: A Comprehensive surveycited by 23
  14. 2023Exposition on over-squashing problem on GNNs: Current Methods, Benchmarks and Challengescited by 22
  15. 2022Graph Neural Networks Designed for Different Graph Types: A Surveycited by 21
  16. 2023Going beyond persistent homology using persistent homologycited by 21
  17. 2022A Practical, Progressively-Expressive GNNcited by 20
  18. 2021Theoretically Improving Graph Neural Networks via Anonymous Walk Graph Kernelscited by 19
  19. 2023Permutation Equivariant Graph Framelets for Heterophilous Graph Learningcited by 19
  20. 2021Motif Prediction with Graph Neural Networkscited by 18
  21. 2022Group-invariant max filteringcited by 18
  22. 2023On the Expressivity of Persistent Homology in Graph Learningcited by 18
  23. 2023Efficient Subgraph GNNs by Learning Effective Selection Policiescited by 17
  24. 2021Graph Neural Networks: Methods, Applications, and Opportunitiescited by 16
  25. 2024Expressive Power of Graph Neural Networks for (Mixed-Integer) Quadratic Programscited by 16
  26. 2022Weisfeiler and Leman Go Infinite: Spectral and Combinatorial Pre-Coloringscited by 15
  27. 20221-WL Expressiveness Is (Almost) All You Needcited by 15
  28. 2021Graph Kernel Neural Networkscited by 13
  29. 2022Homophily modulates double descent generalization in graph convolution networkscited by 13
  30. 2022Graph Neural Networks in Particle Physics: Implementations, Innovations, and Challengescited by 12
  31. 2022Neural Topological Ordering for Computation Graphscited by 12
  32. 2022Weisfeiler-Lehman goes Dynamic: An Analysis of the Expressive Power of Graph Neural Networks for Attributed and Dynamic Graphscited by 12
  33. 2023A Survey of Graph Unlearningcited by 12
  34. 2024Rethinking the Capacity of Graph Neural Networks for Branching Strategycited by 12
  35. 2022Neural Graph Databasescited by 11
  36. 2022From Local to Global: Spectral-Inspired Graph Neural Networkscited by 11
  37. 2024Explaining Graph Neural Networks via Structure-aware Interaction Indexcited by 10
  38. 2021On the approximation capability of GNNs in node classification/regression taskscited by 9

50 most cited of 111 All 111 (JSON)