Graph neural network outputs are almost surely asymptotically constant
Sam Adam-Day Michael Benedikt İsmail İlkan Ceylan Ben Finkelshtein
Graph neural networks (GNNs) are the predominant architectures for a variety
of learning tasks on graphs. We present a new angle on the expressive power of
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 express uniformly. This 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 the (sparse)
Erd\H{o}s-R\'enyi model and the stochastic block model. We empirically validate
these findings, observing that the convergence phenomenon already manifests
itself on graphs of relatively modest size.