mlsanityData to 7 Oct 2026

Future Directions in the Theory of Graph Machine Learning

arXiv 2402.02287 ↗First posted 3 Feb 2024cs.LG cs.AI cs.DMcited by 5

Not on the map. Why?

Abstract (arXiv)

Machine learning on graphs, especially using graph neural networks (GNNs), has seen a surge in interest due to the wide availability of graph data across a broad spectrum of disciplines, from life to social and engineering sciences. Despite their practical success, our theoretical understanding of the properties of GNNs remains highly incomplete. Recent theoretical advancements primarily focus on elucidating the coarse-grained expressive power of GNNs, predominantly employing combinatorial techniques. However, these studies do not perfectly align with practice, particularly in understanding the generalization behavior of GNNs when trained with stochastic first-order optimization techniques. In this position paper, we argue that the graph machine learning community needs to shift its attention to developing a balanced theory of graph machine learning, focusing on a more thorough understanding of the interplay of expressive power, generalization, and optimization.

Key facts. Cited by 5 papers in the map (data through 7 Oct 2026). Builds on 94 of its 122 references that are in the map. First posted on arXiv 3 Feb 2024.

Builds on

94 of 122 references.

References · 94

  1. 2015Deep Residual Learning for Image Recognitioncited by 51,809
  2. 2018How Powerful are Graph Neural Networks?cited by 4,355
  3. 2017Neural Message Passing for Quantum Chemistrycited by 3,460
  4. 2019Fast Graph Representation Learning with PyTorch Geometriccited by 2,414
  5. 2020Open Graph Benchmark: Datasets for Machine Learning on Graphscited by 2,148
  6. 2018Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networkscited by 878
  7. 2020On the Bottleneck of Graph Neural Networks and its Practical Implicationscited by 624
  8. 2019Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networkscited by 562
  9. 2020Graph Neural Networks in Recommender Systems: A Surveycited by 493
  10. 2021Understanding over-squashing and bottlenecks on graphs via curvaturecited by 471
  11. 2021Gradient Descent on Neural Networks Typically Occurs at the Edge of Stabilitycited by 413
  12. 2018Invariant and Equivariant Graph Networkscited by 339
38 more
  1. 2020Improving Graph Neural Network Expressivity via Subgraph Isomorphism Countingcited by 312
  2. 2019PairNorm: Tackling Oversmoothing in GNNscited by 297
  3. 2023Exploring the Potential of Large Language Models (LLMs) in Learning on Graphscited by 271
  4. 2021Combinatorial optimization and reasoning with graph neural networkscited by 267
  5. 2022Long Range Graph Benchmarkcited by 258
  6. 2023A Survey on Oversmoothing in Graph Neural Networkscited by 246
  7. 2019Deep Graph Library: A Graph-Centric, Highly-Performant Package for Graph Neural Networkscited by 241
  8. 2020Can Graph Neural Networks Count Substructures?cited by 235
  9. 2020How Neural Networks Extrapolate: From Feedforward to Graph Neural Networkscited by 218
  10. 2020Generalization and Representational Limits of Graph Neural Networkscited by 217
  11. 2020The Surprising Power of Graph Neural Networks with Random Node Initializationcited by 190
  12. 2022Discovering Invariant Rationales for Graph Neural Networkscited by 186
  13. 2022Sign and Basis Invariant Networks for Spectral Graph Representation Learningcited by 176
  14. 2023Talk like a Graph: Encoding Graphs for Large Language Modelscited by 175
  15. 2019On the equivalence between graph isomorphism testing and function approximation with GNNscited by 172
  16. 2021Training Graph Neural Networks with 1000 Layerscited by 169
  17. 2022Multi-modal Molecule Structure-text Model for Text-based Retrieval and Editingcited by 165
  18. 2023On Over-Squashing in Message Passing Neural Networks: The Impact of Width, Depth, and Topologycited by 163
  19. 2019Graph Neural Tangent Kernel: Fusing Graph Neural Networks with Graph Kernelscited by 160
  20. 2019What Can Neural Networks Reason About?cited by 155
  21. 2021Equivariant Subgraph Aggregation Networkscited by 154
  22. 2022G-Mixup: Graph Data Augmentation for Graph Classificationcited by 145
  23. 2023Neural Architecture Search: Insights from 1000 Paperscited by 136
  24. 2022Data Augmentation for Deep Graph Learning: A Surveycited by 132
  25. 2021Weisfeiler and Leman go Machine Learning: The Story so farcited by 121
  26. 2020From Local Structures to Size Generalization in Graph Neural Networkscited by 119
  27. 2023Rethinking the Expressive Power of GNNs via Graph Biconnectivitycited by 119
  28. 2020Graphon Neural Networks and the Transferability of Graph Neural Networkscited by 117
  29. 2022Understanding and Extending Subgraph GNNs by Rethinking Their Symmetriescited by 112
  30. 2020A Survey on The Expressive Power of Graph Neural Networkscited by 111
  31. 2023GraphText: Graph Reasoning in Text Spacecited by 110
  32. 2022The CLRS Algorithmic Reasoning Benchmarkcited by 103
  33. 2018On the Power of Over-parametrization in Neural Networks with Quadratic Activationcited by 102
  34. 2019Transferability of Spectral Graph Convolutional Neural Networkscited by 90
  35. 2023On the Expressive Power of Geometric Graph Neural Networkscited by 89
  36. 2020A PAC-Bayesian Approach to Generalization Bounds for Graph Neural Networkscited by 84
  37. 2021The Logic of Graph Neural Networkscited by 84
  38. 2023Attending to Graph Transformerscited by 81

50 most cited of 94 All 94 (JSON)

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2024: 1; 2025: 3; 2026: 1.

5 papers.

  1. 2025Graph Representational Learning: When Does More Expressivity Hurt Generalization?cited by 4
  2. 2025On Universality Classes of Equivariant Networkscited by 4
  3. 2024Foundations and Frontiers of Graph Learning Theorycited by 3
  4. 2025Backward Oversmoothing: why is it hard to train deep Graph Neural Networks?cited by 2
  5. 2026Out-of-Distribution Generalization in Graph Foundation Modelscited by 0