mlsanityData to 14 Oct 2026

On the equivalence between graph isomorphism testing and function approximation with GNNs

arXiv 1905.12560 ↗First posted 29 May 2019cs.LG stat.MLcited by 172

Not on the map. Why?

Abstract (arXiv)

Graph Neural Networks (GNNs) have achieved much success on graph-structured data. In light of this, there have been increasing interests in studying their expressive power. One line of work studies the capability of GNNs to approximate permutation-invariant functions on graphs, and another focuses on the their power as tests for graph isomorphism. Our work connects these two perspectives and proves their equivalence. We further develop a framework of the expressive power of GNNs that incorporates both of these viewpoints using the language of sigma-algebra, through which we compare the expressive power of different types of GNNs together with other graph isomorphism tests. In particular, we prove that the second-order Invariant Graph Network fails to distinguish non-isomorphic regular graphs with the same degree. Then, we extend it to a new architecture, Ring-GNN, which succeeds in distinguishing these graphs and achieves good performances on real-world datasets.

Key facts. Cited by 172 papers in the map (data through 14 Oct 2026). First posted on arXiv 29 May 2019.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 28; 2022: 48; 2023: 36; 2024: 39; 2025: 14; 2026: 7.

172 papers.

Sort:

By area:

  1. 2022Recipe for a General, Powerful, Scalable Graph Transformercited by 713
  2. 2021Graph Neural Networks with Learnable Structural and Positional Representationscited by 333
  3. 2021Combinatorial optimization and reasoning with graph neural networkscited by 268
  4. 2021Weisfeiler and Lehman Go Cellular: CW Networkscited by 218
  5. 2021Identity-aware Graph Neural Networkscited by 198
  6. 2022Discovering Invariant Rationales for Graph Neural Networkscited by 188
  7. 2022Sign and Basis Invariant Networks for Spectral Graph Representation Learningcited by 179
  8. 2022How Powerful are Spectral Graph Neural Networkscited by 169
  9. 2021From Stars to Subgraphs: Uplifting Any GNN with Local Structure Awarenesscited by 155
  10. 2021Equivariant Subgraph Aggregation Networkscited by 154
  11. 2023Temporal Graph Benchmark for Machine Learning on Temporal Graphscited by 138
  12. 2021Nested Graph Neural Networkscited by 137
38 more
  1. 2023Representational Strengths and Limitations of Transformerscited by 133
  2. 2021Scalars are universal: Equivariant machine learning, structured like classical physicscited by 127
  3. 2021Weisfeiler and Leman go Machine Learning: The Story so farcited by 122
  4. 2023Rethinking the Expressive Power of GNNs via Graph Biconnectivitycited by 119
  5. 2021A Unified Lottery Ticket Hypothesis for Graph Neural Networkscited by 118
  6. 2021DropGNN: Random Dropouts Increase the Expressiveness of Graph Neural Networkscited by 118
  7. 2022Equivariant and Stable Positional Encoding for More Powerful Graph Neural Networkscited by 94
  8. 2022A Generalization of ViT/MLP-Mixer to Graphscited by 93
  9. 2022How Powerful are K-hop Message Passing Graph Neural Networkscited by 90
  10. 2023On the Expressive Power of Geometric Graph Neural Networkscited by 90
  11. 2021Topological Graph Neural Networkscited by 87
  12. 2023Attending to Graph Transformerscited by 83
  13. 2022A Survey on Graph Representation Learning Methodscited by 66
  14. 2021Reconstruction for Powerful Graph Representationscited by 65
  15. 2024Polynormer: Polynomial-Expressive Graph Transformer in Linear Timecited by 65
  16. 2022Expressiveness and Approximation Properties of Graph Neural Networkscited by 64
  17. 2022Theory of Graph Neural Networks: Representation and Learningcited by 61
  18. 2023CktGNN: Circuit Graph Neural Network for Electronic Design Automationcited by 58
  19. 2022Ordered Subgraph Aggregation Networkscited by 57
  20. 2022Boosting the Cycle Counting Power of Graph Neural Networks with I2-GNNscited by 56
  21. 2021Optimization of Graph Neural Networks: Implicit Acceleration by Skip Connections and More Depthcited by 55
  22. 2024A Survey of Graph Neural Networks in Real world: Imbalance, Noise, Privacy and OOD Challengescited by 54
  23. 2021Graph Neural Networks with Local Graph Parameterscited by 52
  24. 2022A Short Tutorial on The Weisfeiler-Lehman Test And Its Variantscited by 52
  25. 2022MIP-GNN: A Data-Driven Framework for Guiding Combinatorial Solverscited by 49
  26. 2024KAGNNs: Kolmogorov-Arnold Networks meet Graph Learningcited by 49
  27. 2022Message passing all the way upcited by 47
  28. 2023Towards Understanding the Generalization of Graph Neural Networkscited by 41
  29. 2022On Representing Linear Programs by Graph Neural Networkscited by 39
  30. 2024Beyond Weisfeiler-Lehman: A Quantitative Framework for GNN Expressivenesscited by 39
  31. 2023Equivariant Polynomials for Graph Neural Networkscited by 38
  32. 2022SpeqNets: Sparsity-aware Permutation-equivariant Graph Networkscited by 37
  33. 2021Bag of Tricks for Training Deeper Graph Neural Networks: A Comprehensive Benchmark Studycited by 36
  34. 2023An Empirical Study of Realized GNN Expressivenesscited by 33
  35. 2023Path Neural Networks: Expressive and Accurate Graph Neural Networkscited by 32
  36. 2023WL meet VCcited by 31
  37. 2023A graphon-signal analysis of graph neural networkscited by 30
  38. 2022Weisfeiler and Leman Go Relationalcited by 28

50 most cited of 172 All 172 (JSON)