mlsanityData to 7 Oct 2026

Theory of Graph Neural Networks: Representation and Learning

arXiv 2204.07697 ↗First posted 16 Apr 2022cs.LG stat.MLcited by 60

Not on the map. Why?

Abstract (arXiv)

Graph Neural Networks (GNNs), neural network architectures targeted to learning representations of graphs, have become a popular learning model for prediction tasks on nodes, graphs and configurations of points, with wide success in practice. This article summarizes a selection of the emerging theoretical results on approximation and learning properties of widely used message passing GNNs and higher-order GNNs, focusing on representation, generalization and extrapolation. Along the way, it summarizes mathematical connections.

Key facts. Cited by 60 papers in the map (data through 7 Oct 2026). Builds on 84 of its 129 references that are in the map. First posted on arXiv 16 Apr 2022.

Builds on

84 of 129 references.

References · 84

  1. 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,282
  2. 2017Inductive Representation Learning on Large Graphscited by 6,284
  3. 2016PointNet: Deep Learning on Point Sets for 3D Classification and Segmentationcited by 5,223
  4. 2018How Powerful are Graph Neural Networks?cited by 4,355
  5. 2017Neural Message Passing for Quantum Chemistrycited by 3,460
  6. 2018Neural Tangent Kernel: Convergence and Generalization in Neural Networkscited by 2,597
  7. 2016Convolutional Neural Networks on Graphs with Fast Localized Spectral Filteringcited by 2,085
  8. 2016node2vec: Scalable Feature Learning for Networkscited by 1,913
  9. 2017Deep Setscited by 1,394
  10. 2018Relational inductive biases, deep learning, and graph networkscited by 1,341
  11. 2013Spectral Networks and Locally Connected Networks on Graphscited by 1,097
  12. 2018Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networkscited by 878
38 more
  1. 2020Learning to Simulate Complex Physics with Graph Networkscited by 867
  2. 2015Convolutional Networks on Graphs for Learning Molecular Fingerprintscited by 751
  3. 2018Gradient Descent Provably Optimizes Over-parameterized Neural Networkscited by 655
  4. 2020A Generalization of Transformer Networks to Graphscited by 653
  5. 2018Gradient Descent Finds Global Minima of Deep Neural Networkscited by 572
  6. 2019On Exact Computation with an Infinitely Wide Neural Netcited by 572
  7. 2019Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networkscited by 562
  8. 2017Learning Combinatorial Optimization Algorithms over Graphscited by 557
  9. 2016Interaction Networks for Learning about Objects, Relations and Physicscited by 503
  10. 2017Representation Learning on Graphs: Methods and Applicationscited by 456
  11. 2019Provably Powerful Graph Networkscited by 385
  12. 2019The Neuro-Symbolic Concept Learner: Interpreting Scenes, Words, and Sentences From Natural Supervisioncited by 369
  13. 2017A simple neural network module for relational reasoningcited by 345
  14. 2018Invariant and Equivariant Graph Networkscited by 339
  15. 2020Discovering Symbolic Models from Deep Learning with Inductive Biasescited by 335
  16. 2020Improving Graph Neural Network Expressivity via Subgraph Isomorphism Countingcited by 312
  17. 2018Neural-Symbolic VQA: Disentangling Reasoning from Vision and Language Understandingcited by 304
  18. 2018On the Generalization of Equivariance and Convolution in Neural Networks to the Action of Compact Groupscited by 296
  19. 2021Combinatorial optimization and reasoning with graph neural networkscited by 267
  20. 2019Deep Learning for Symbolic Mathematicscited by 266
  21. 2018Modeling polypharmacy side effects with graph convolutional networkscited by 237
  22. 2020Can Graph Neural Networks Count Substructures?cited by 235
  23. 2021Weisfeiler and Lehman Go Topological: Message Passing Simplicial Networkscited by 219
  24. 2020How Neural Networks Extrapolate: From Feedforward to Graph Neural Networkscited by 218
  25. 2021Weisfeiler and Lehman Go Cellular: CW Networkscited by 218
  26. 2020Generalization and Representational Limits of Graph Neural Networkscited by 217
  27. 2021Identity-aware Graph Neural Networkscited by 197
  28. 2019What graph neural networks cannot learn: depth vs widthcited by 195
  29. 2020The Surprising Power of Graph Neural Networks with Random Node Initializationcited by 190
  30. 2020Random Features Strengthen Graph Neural Networkscited by 184
  31. 2019Universal Invariant and Equivariant Graph Neural Networkscited by 182
  32. 2020Graph-Bert: Only Attention is Needed for Learning Graph Representationscited by 176
  33. 2022Sign and Basis Invariant Networks for Spectral Graph Representation Learningcited by 176
  34. 2019On the equivalence between graph isomorphism testing and function approximation with GNNscited by 172
  35. 2018Measuring abstract reasoning in neural networkscited by 165
  36. 2019Graph Neural Tangent Kernel: Fusing Graph Neural Networks with Graph Kernelscited by 160
  37. 2019What Can Neural Networks Reason About?cited by 155
  38. 2021Equivariant Subgraph Aggregation Networkscited by 154

50 most cited of 84 All 84 (JSON)

Built on by

Cited by year

Citing papers per year: 2022: 10; 2023: 20; 2024: 15; 2025: 15.

60 papers.

Sort:

By area:

  1. 2023On Over-Squashing in Message Passing Neural Networks: The Impact of Width, Depth, and Topologycited by 163
  2. 2023On the Expressive Power of Geometric Graph Neural Networkscited by 89
  3. 2023A Hitchhiker's Guide to Geometric GNNs for 3D Atomic Systemscited by 65
  4. 2022Theory for Equivariant Quantum Neural Networkscited by 60
  5. 2022On Representing Linear Programs by Graph Neural Networkscited by 39
  6. 2022Tree Mover's Distance: Bridging Graph Metrics and Stability of Graph Neural Networkscited by 39
  7. 2023Generalization in Graph Neural Networks: Improved PAC-Bayesian Bounds on Graph Diffusioncited by 39
  8. 2023What can a Single Attention Layer Learn? A Study Through the Random Features Lenscited by 39
  9. 2023Neural Algorithmic Reasoning with Causal Regularisationcited by 30
  10. 2022Exponentially Improving the Complexity of Simulating the Weisfeiler-Lehman Test with Graph Neural Networkscited by 20
  11. 2023Learning to Extrapolate: A Transductive Approachcited by 19
  12. 2023Limits, approximation and size transferability for GNNs on sparse graphs via graphopscited by 17
38 more
  1. 2024On the hardness of learning under symmetriescited by 13
  2. 2022Weisfeiler-Lehman goes Dynamic: An Analysis of the Expressive Power of Graph Neural Networks for Attributed and Dynamic Graphscited by 12
  3. 2023A Survey of Graph Unlearningcited by 12
  4. 2024Rethinking the Capacity of Graph Neural Networks for Branching Strategycited by 12
  5. 2023Convergence of Message Passing Graph Neural Networks with Generic Aggregation On Large Random Graphscited by 9
  6. 2023Are GATs Out of Balance?cited by 9
  7. 2025Graph neural networks extrapolate out-of-distribution for shortest pathscited by 9
  8. 2024An Efficient Memory Module for Graph Few-Shot Class-Incremental Learningcited by 8
  9. 2022BIP: Boost Invariant Polynomials for Efficient Jet Taggingcited by 7
  10. 2022Analysis of Convolutions, Non-linearity and Depth in Graph Neural Networks using Neural Tangent Kernelcited by 7
  11. 2023On the power of graph neural networks and the role of the activation functioncited by 7
  12. 2024DE-HNN: An effective neural model for Circuit Netlist representationcited by 7
  13. 2023Knowledge-augmented Graph Machine Learning for Drug Discovery: A Surveycited by 6
  14. 2024Precedence-Constrained Winter Value for Effective Graph Data Valuationcited by 6
  15. 2024Deeper Insights into Deep Graph Convolutional Networks: Stability and Generalizationcited by 6
  16. 2022On Classification Thresholds for Graph Attention with Edge Featurescited by 5
  17. 2023Optimizing Solution-Samplers for Combinatorial Problems: The Landscape of Policy-Gradient Methodscited by 5
  18. 2024Future Directions in the Theory of Graph Machine Learningcited by 5
  19. 2024Training-free Graph Neural Networks and the Power of Labels as Featurescited by 5
  20. 2022Empowering GNNs via Edge-Aware Weisfeiler-Leman Algorithmcited by 4
  21. 2023Graph Neural Networks can Recover the Hidden Features Solely from the Graph Structurecited by 4
  22. 2023On the Two Sides of Redundancy in Graph Neural Networkscited by 4
  23. 2022Graph Neural Network Based Node Deployment for Throughput Enhancementcited by 3
  24. 2023How Graph Neural Networks Learn: Lessons from Training Dynamicscited by 3
  25. 2024Foundations and Frontiers of Graph Learning Theorycited by 3
  26. 2024Graph Neural Networks Are More Than Filters: Revisiting and Benchmarking from A Spectral Perspectivecited by 3
  27. 2025Unveiling Mode Connectivity in Graph Neural Networkscited by 3
  28. 2025On the Relationship Between Robustness and Expressivity of Graph Neural Networkscited by 3
  29. 2023Learning Resource Allocation Policy: Vertex-GNN or Edge-GNN?cited by 2
  30. 2023On the Robustness of Post-hoc GNN Explainers to Label Noisecited by 2
  31. 2024The Role of Fibration Symmetries in Geometric Deep Learningcited by 2
  32. 2025Generalization Performance of Hypergraph Neural Networkscited by 2
  33. 2025Performance Heterogeneity in Graph Neural Networks: Lessons for Architecture Design and Preprocessingcited by 2
  34. 2025On the Interplay between Graph Structure and Learning Algorithms in Graph Neural Networkscited by 2
  35. 2025Parameter-Efficient Conditioning for Material Generalization in Graph-Based Simulatorscited by 2
  36. 2025Heat Kernel Goes Topologicalcited by 1
  37. 2025What Expressivity Theory Misses: Message Passing Complexity for GNNscited by 1
  38. 2023Attacking Graph Neural Networks with Bit Flips: Weisfeiler and Lehman Go Indifferentcited by 0

50 most cited of 60 All 60 (JSON)