mlsanityData to 14 Oct 2026

Almost Surely Asymptotically Constant Graph Neural Networks

arXiv 2403.03880 ↗First posted 6 Mar 2024cs.LG cs.LOcited by 7

Not on the map. Why?

Abstract (arXiv)

We present a new angle on the expressive power of graph neural networks (GNNs) by studying how the predictions of real-valued GNN classifiers, such as those classifying graphs probabilistically, evolve as we apply them on larger graphs drawn from some random graph model. We show that the output converges to a constant function, which upper-bounds what these classifiers can uniformly express. This strong convergence phenomenon applies to a very wide class of GNNs, including state of the art models, with aggregates including mean and the attention-based mechanism of graph transformers. Our results apply to a broad class of random graph models, including sparse and dense variants of the ErdHos-R'enyi model, the stochastic block model, and the Barab'asi-Albert model. We empirically validate these findings, observing that the convergence phenomenon appears not only on random graphs but also on some real-world graphs.

Key facts. Cited by 7 papers in the map (data through 14 Oct 2026). Builds on 33 of its 57 references that are in the map. First posted on arXiv 6 Mar 2024.

Builds on

33 of 57 references.

References · 33

  1. 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,361
  2. 2017Graph Attention Networkscited by 8,923
  3. 2018How Powerful are Graph Neural Networks?cited by 4,393
  4. 2017Neural Message Passing for Quantum Chemistrycited by 3,487
  5. 2018Relational inductive biases, deep learning, and graph networkscited by 1,360
  6. 2018Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networkscited by 881
  7. 2018Representation Learning on Graphs with Jumping Knowledge Networkscited by 877
  8. 2015Convolutional Networks on Graphs for Learning Molecular Fingerprintscited by 754
  9. 2022Recipe for a General, Powerful, Scalable Graph Transformercited by 713
  10. 2020Benchmarking Graph Neural Networkscited by 680
  11. 2021Graph Neural Networks with Learnable Structural and Positional Representationscited by 333
  12. 2016Molecular Graph Convolutions: Moving Beyond Fingerprintscited by 238
21 more
  1. 2018Modeling polypharmacy side effects with graph convolutional networkscited by 237
  2. 2020Can Graph Neural Networks Count Substructures?cited by 236
  3. 2020Generalization and Representational Limits of Graph Neural Networkscited by 218
  4. 2020The Surprising Power of Graph Neural Networks with Random Node Initializationcited by 198
  5. 2020Random Features Strengthen Graph Neural Networkscited by 186
  6. 2023Graph Inductive Biases in Transformers without Message Passingcited by 153
  7. 2023Rethinking the Expressive Power of GNNs via Graph Biconnectivitycited by 119
  8. 2020A PAC-Bayesian Approach to Generalization Bounds for Graph Neural Networkscited by 85
  9. 2020Convergence and Stability of Graph Convolutional Networks on Large Random Graphscited by 76
  10. 2019GNN-FiLM: Graph Neural Networks with Feature-wise Linear Modulationcited by 75
  11. 2022Expressiveness and Approximation Properties of Graph Neural Networkscited by 64
  12. 2022Generalization Analysis of Message Passing Neural Networks on Large Random Graphscited by 59
  13. 2023WL meet VCcited by 31
  14. 2023A graphon-signal analysis of graph neural networkscited by 30
  15. 2021On the Universality of Graph Neural Networks on Large Random Graphscited by 26
  16. 2023The Descriptive Complexity of Graph Neural Networkscited by 26
  17. 2023Some Might Say All You Need Is Sumcited by 21
  18. 2023PlanE: Representation Learning over Planar Graphscited by 11
  19. 2023Convergence of Message Passing Graph Neural Networks with Generic Aggregation On Large Random Graphscited by 9
  20. 2023Zero-One Laws of Graph Neural Networkscited by 7
  21. 2022Zero-One Laws and Almost Sure Valuations of First-Order Logic in Semiring Semanticscited by 2

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2025: 5; 2026: 2.

7 papers.

  1. 2025Logical Expressiveness of Graph Neural Networks with Hierarchical Node Individualizationcited by 3
  2. 2025Domain size asymptotics for Markov logic networkscited by 3
  3. 2025Sound Logical Explanations for Mean Aggregation Graph Neural Networkscited by 2
  4. 2025A convergence law for continuous logic and continuous structures with finite domainscited by 1
  5. 2025On Local Limits of Sparse Random Graphs: Color Convergence and the Refined Configuration Modelcited by 0
  6. 2026Investigating GNN Convergence on Large Randomly Generated Graphs with Realistic Node Feature Correlationscited by 0
  7. 2026A Spectral Theory of Normalized Corrected GNN Propagationcited by 0