# Almost Surely Asymptotically Constant Graph Neural Networks

arXiv: https://arxiv.org/abs/2403.03880 · HTML: https://mlsanity.com/paper/2403.03880/

## 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 (most cited first, 30 of 33)

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Neural Message Passing for Quantum Chemistry](https://mlsanity.com/paper/1704.01212/) (2017)
- [Relational inductive biases, deep learning, and graph networks](https://mlsanity.com/paper/1806.01261/) (2018)
- [Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networks](https://mlsanity.com/paper/1810.02244/) (2018)
- [Representation Learning on Graphs with Jumping Knowledge Networks](https://mlsanity.com/paper/1806.03536/) (2018)
- [Convolutional Networks on Graphs for Learning Molecular Fingerprints](https://mlsanity.com/paper/1509.09292/) (2015)
- [Recipe for a General, Powerful, Scalable Graph Transformer](https://mlsanity.com/paper/2205.12454/) (2022)
- [Benchmarking Graph Neural Networks](https://mlsanity.com/paper/2003.00982/) (2020)
- [Graph Neural Networks with Learnable Structural and Positional Representations](https://mlsanity.com/paper/2110.07875/) (2021)
- [Molecular Graph Convolutions: Moving Beyond Fingerprints](https://mlsanity.com/paper/1603.00856/) (2016)
- [Modeling polypharmacy side effects with graph convolutional networks](https://mlsanity.com/paper/1802.00543/) (2018)
- [Can Graph Neural Networks Count Substructures?](https://mlsanity.com/paper/2002.04025/) (2020)
- [Generalization and Representational Limits of Graph Neural Networks](https://mlsanity.com/paper/2002.06157/) (2020)
- [The Surprising Power of Graph Neural Networks with Random Node Initialization](https://mlsanity.com/paper/2010.01179/) (2020)
- [Random Features Strengthen Graph Neural Networks](https://mlsanity.com/paper/2002.03155/) (2020)
- [Graph Inductive Biases in Transformers without Message Passing](https://mlsanity.com/paper/2305.17589/) (2023)
- [Rethinking the Expressive Power of GNNs via Graph Biconnectivity](https://mlsanity.com/paper/2301.09505/) (2023)
- [A PAC-Bayesian Approach to Generalization Bounds for Graph Neural Networks](https://mlsanity.com/paper/2012.07690/) (2020)
- [Convergence and Stability of Graph Convolutional Networks on Large Random Graphs](https://mlsanity.com/paper/2006.01868/) (2020)
- [GNN-FiLM: Graph Neural Networks with Feature-wise Linear Modulation](https://mlsanity.com/paper/1906.12192/) (2019)
- [Expressiveness and Approximation Properties of Graph Neural Networks](https://mlsanity.com/paper/2204.04661/) (2022)
- [Generalization Analysis of Message Passing Neural Networks on Large Random Graphs](https://mlsanity.com/paper/2202.00645/) (2022)
- [WL meet VC](https://mlsanity.com/paper/2301.11039/) (2023)
- [A graphon-signal analysis of graph neural networks](https://mlsanity.com/paper/2305.15987/) (2023)
- [On the Universality of Graph Neural Networks on Large Random Graphs](https://mlsanity.com/paper/2105.13099/) (2021)
- [The Descriptive Complexity of Graph Neural Networks](https://mlsanity.com/paper/2303.04613/) (2023)
- [Some Might Say All You Need Is Sum](https://mlsanity.com/paper/2302.11603/) (2023)
- [PlanE: Representation Learning over Planar Graphs](https://mlsanity.com/paper/2307.01180/) (2023)

## Built on by (most cited first, 7 of 7)

- [Logical Expressiveness of Graph Neural Networks with Hierarchical Node Individualization](https://mlsanity.com/paper/2506.13911/) (2025)
- [Domain size asymptotics for Markov logic networks](https://mlsanity.com/paper/2509.04192/) (2025)
- [Sound Logical Explanations for Mean Aggregation Graph Neural Networks](https://mlsanity.com/paper/2511.11593/) (2025)
- [A convergence law for continuous logic and continuous structures with finite domains](https://mlsanity.com/paper/2504.08923/) (2025)
- [On Local Limits of Sparse Random Graphs: Color Convergence and the Refined Configuration Model](https://mlsanity.com/paper/2510.21392/) (2025)
- [Investigating GNN Convergence on Large Randomly Generated Graphs with Realistic Node Feature Correlations](https://mlsanity.com/paper/2602.16145/) (2026)
- [A Spectral Theory of Normalized Corrected GNN Propagation](https://mlsanity.com/paper/2606.23572/) (2026)

## 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.