@inproceedings{
adam-day2024almost,
title={Almost Surely Asymptotically Constant Graph Neural Networks},
author={Sam Adam-Day and Michael Benedikt and Ismail Ilkan Ceylan and Ben Finkelshtein},
booktitle={The Thirty-eighth Annual Conference on Neural Information Processing Systems},
year={2024},
url={https://openreview.net/forum?id=Dn68qdfTry}
}
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 Erdős-Rényi model, the stochastic block model, and the Barabási-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.
Almost Surely Asymptotically Constant Graph Neural Networks
Sam Adam-Day Michael Benedikt Ismail Ilkan Ceylan Ben Finkelshtein