Almost Surely Asymptotically Constant Graph Neural Networks
<|reference_start|>Almost Surely Asymptotically Constant Graph Neural Networks: We present a new angle on the expressive power of graph neural networks (GNNs) by studying how the predictions of a GNN probabilistic classifier evolve as we apply it 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\H{o}s-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.<|reference_end|>
@article{adam-day2024almost,
    title={Almost Surely Asymptotically Constant Graph Neural Networks},
    author={Sam Adam-Day, Michael Benedikt, .Ismail .Ilkan Ceylan, Ben
  Finkelshtein},
    journal={arXiv preprint arXiv:2403.03880},
    year={2024},
    archivePrefix={arXiv},
    eprint={2403.03880},
    primaryClass={cs.LG cs.LO}
}