mlsanityData to 7 Oct 2026

Zero-One Laws of Graph Neural Networks

arXiv 2301.13060 ↗First posted 30 Jan 2023cs.LGcited by 7

Not on the map. Why?

Abstract (arXiv)

Graph neural networks (GNNs) are the de facto standard deep learning architectures for machine learning on graphs. This has led to a large body of work analyzing the capabilities and limitations of these models, particularly pertaining to their representation and extrapolation capacity. We offer a novel theoretical perspective on the representation and extrapolation capacity of GNNs, by answering the question: how do GNNs behave as the number of graph nodes become very large? Under mild assumptions, we show that when we draw graphs of increasing size from the ErdHos-R'enyi model, the probability that such graphs are mapped to a particular output by a class of GNN classifiers tends to either zero or to one. This class includes the popular graph convolutional network architecture. The result establishes 'zero-one laws' for these GNNs, and analogously to other convergence laws, entails theoretical limitations on their capacity. We empirically verify our results, observing that the theoretical asymptotic limits are evident already on relatively small graphs.

Key facts. Cited by 7 papers in the map (data through 7 Oct 2026). Builds on 27 of its 44 references that are in the map. First posted on arXiv 30 Jan 2023.

Builds on

27 of 44 references.

References · 27

  1. 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,282
  2. 2017Graph Attention Networkscited by 8,854
  3. 2017Inductive Representation Learning on Large Graphscited by 6,284
  4. 2018How Powerful are Graph Neural Networks?cited by 4,355
  5. 2017Neural Message Passing for Quantum Chemistrycited by 3,460
  6. 2018Relational inductive biases, deep learning, and graph networkscited by 1,341
  7. 2018Deeper Insights into Graph Convolutional Networks for Semi-Supervised Learningcited by 1,099
  8. 2018Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networkscited by 878
  9. 2015Gated Graph Sequence Neural Networkscited by 792
  10. 2015Convolutional Networks on Graphs for Learning Molecular Fingerprintscited by 751
  11. 2020On the Bottleneck of Graph Neural Networks and its Practical Implicationscited by 624
  12. 2019Provably Powerful Graph Networkscited by 385
15 more
  1. 2016Molecular Graph Convolutions: Moving Beyond Fingerprintscited by 238
  2. 2018Modeling polypharmacy side effects with graph convolutional networkscited by 237
  3. 2020How Neural Networks Extrapolate: From Feedforward to Graph Neural Networkscited by 218
  4. 2019What graph neural networks cannot learn: depth vs widthcited by 195
  5. 2020The Surprising Power of Graph Neural Networks with Random Node Initializationcited by 190
  6. 2020Random Features Strengthen Graph Neural Networkscited by 184
  7. 2019Universal Invariant and Equivariant Graph Neural Networkscited by 182
  8. 2019On the Universality of Invariant Networkscited by 151
  9. 2019Stability Properties of Graph Neural Networkscited by 125
  10. 2020From Local Structures to Size Generalization in Graph Neural Networkscited by 119
  11. 2020Graphon Neural Networks and the Transferability of Graph Neural Networkscited by 117
  12. 2019Transferability of Spectral Graph Convolutional Neural Networkscited by 90
  13. 2021The Logic of Graph Neural Networkscited by 84
  14. 2020Convergence and Stability of Graph Convolutional Networks on Large Random Graphscited by 75
  15. 2022On Evaluation Metrics for Graph Generative Modelscited by 44

Built on by

Cited by year (2026 to 7 Oct)

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

7 papers.

  1. 2024Almost Surely Asymptotically Constant Graph Neural Networkscited by 7
  2. 2024Future Directions in the Theory of Graph Machine Learningcited by 5
  3. 2025Learning from one graph: transductive learning guarantees via the geometry of small random worldscited by 3
  4. 2025A convergence law for continuous logic and continuous structures with finite domainscited by 1
  5. 2025Domain size asymptotics for Markov logic networkscited by 1
  6. 2026Investigating GNN Convergence on Large Randomly Generated Graphs with Realistic Node Feature Correlationscited by 0
  7. 2026A concentration result for multilayer feedforward neural networkscited by 0