mlsanityData to 7 Oct 2026

Generalization and Representational Limits of Graph Neural Networks

arXiv 2002.06157 ↗First posted 14 Feb 2020cs.LG stat.MLcited by 217

Not on the map. Why?

Abstract (arXiv)

We address two fundamental questions about graph neural networks (GNNs). First, we prove that several important graph properties cannot be computed by GNNs that rely entirely on local information. Such GNNs include the standard message passing models, and more powerful spatial variants that exploit local graph structure (e.g., via relative orientation of messages, or local port ordering) to distinguish neighbors of each node. Our treatment includes a novel graph-theoretic formalism. Second, we provide the first data dependent generalization bounds for message passing GNNs. This analysis explicitly accounts for the local permutation invariance of GNNs. Our bounds are much tighter than existing VC-dimension based guarantees for GNNs, and are comparable to Rademacher bounds for recurrent neural networks.

Key facts. Cited by 217 papers in the map (data through 7 Oct 2026). First posted on arXiv 14 Feb 2020.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 41; 2022: 48; 2023: 45; 2024: 44; 2025: 23; 2026: 16.

217 papers.

Sort:

By area:

  1. 2021GemNet: Universal Directional Graph Neural Networks for Moleculescited by 342
  2. 2021Combinatorial optimization and reasoning with graph neural networkscited by 267
  3. 2022Sign and Basis Invariant Networks for Spectral Graph Representation Learningcited by 176
  4. 2022How Powerful are Spectral Graph Neural Networkscited by 169
  5. 2021Spherical Message Passing for 3D Graph Networkscited by 166
  6. 2022Handling Distribution Shifts on Graphs: An Invariance Perspectivecited by 163
  7. 2021Weisfeiler and Leman go Machine Learning: The Story so farcited by 121
  8. 2023Rethinking the Expressive Power of GNNs via Graph Biconnectivitycited by 119
  9. 2021DropGNN: Random Dropouts Increase the Expressiveness of Graph Neural Networkscited by 117
  10. 2021GeoMol: Torsional Geometric Generation of Molecular 3D Conformer Ensemblescited by 106
  11. 2022Out-Of-Distribution Generalization on Graphs: A Surveycited by 97
  12. 2023On the Expressive Power of Geometric Graph Neural Networkscited by 89
38 more
  1. 2022Trustworthy Graph Neural Networks: Aspects, Methods and Trendscited by 88
  2. 2021Size-Invariant Graph Representations for Graph Classification Extrapolationscited by 82
  3. 2022What's Behind the Mask: Understanding Masked Graph Modeling for Graph Autoencoderscited by 82
  4. 2024GFT: Graph Foundation Model with Transferable Tree Vocabularycited by 82
  5. 2021OOD-GNN: Out-of-Distribution Generalized Graph Neural Networkcited by 78
  6. 2024A Survey of Large Language Models for Graphscited by 71
  7. 2021Graph Convolution for Semi-Supervised Classification: Improved Linear Separability and Out-of-Distribution Generalizationcited by 70
  8. 2021Subgroup Generalization and Fairness of Graph Neural Networkscited by 69
  9. 2021Reconstruction for Powerful Graph Representationscited by 65
  10. 2022Theory of Graph Neural Networks: Representation and Learningcited by 60
  11. 2021On Provable Benefits of Depth in Training Graph Convolutional Networkscited by 58
  12. 2022Generalization Analysis of Message Passing Neural Networks on Large Random Graphscited by 58
  13. 2022Provably expressive temporal graph networkscited by 56
  14. 2021Optimization of Graph Neural Networks: Implicit Acceleration by Skip Connections and More Depthcited by 55
  15. 2023How does over-squashing affect the power of GNNs?cited by 53
  16. 2022Oversquashing in GNNs through the lens of information contraction and graph expansioncited by 52
  17. 2021Graph Neural Networks with Local Graph Parameterscited by 51
  18. 2021Learning Theory Can (Sometimes) Explain Generalisation in Graph Neural Networkscited by 51
  19. 2022A Theoretical Comparison of Graph Neural Network Extensionscited by 47
  20. 2022PipeGCN: Efficient Full-Graph Training of Graph Convolutional Networks with Pipelined Feature Communicationcited by 45
  21. 2023Towards Understanding the Generalization of Graph Neural Networkscited by 41
  22. 2023Demystifying Structural Disparity in Graph Neural Networks: Can One Size Fit All?cited by 41
  23. 2021Autobahn: Automorphism-based Graph Neural Netscited by 39
  24. 2021p-Laplacian Based Graph Neural Networkscited by 39
  25. 2022Tree Mover's Distance: Bridging Graph Metrics and Stability of Graph Neural Networkscited by 39
  26. 2023Generalization in Graph Neural Networks: Improved PAC-Bayesian Bounds on Graph Diffusioncited by 39
  27. 2023Equivariant Polynomials for Graph Neural Networkscited by 38
  28. 2023The expressive power of pooling in Graph Neural Networkscited by 35
  29. 2024GraphEdit: Large Language Models for Graph Structure Learningcited by 33
  30. 2023On the Stability of Expressive Positional Encodings for Graphscited by 31
  31. 2023WL meet VCcited by 30
  32. 2024Towards Graph Foundation Models: Learning Generalities Across Graphs via Task-Treescited by 30
  33. 2023A graphon-signal analysis of graph neural networkscited by 29
  34. 2022Topology-aware Graph Neural Networks for Learning Feasible and Adaptive ac-OPF Solutionscited by 28
  35. 2023Sequence Length Independent Norm-Based Generalization Bounds for Transformerscited by 28
  36. 2023The Expressive Power of Graph Neural Networks: A Surveycited by 27
  37. 2021On the Universality of Graph Neural Networks on Large Random Graphscited by 26
  38. 2021Directional Message Passing on Molecular Graphs via Synthetic Coordinatescited by 24

50 most cited of 217 All 217 (JSON)