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.

图神经网络（GNN）是用于各种图学习任务的主要架构。我们通过研究 GNN 概率分类器在从某个随机图模型中抽取的较大图上应用时的预测如何演变来呈现 GNN 表达能力的新视角。我们展示了输出收敛为常函数的现象，这个常函数上界了这些分类器能够统一表达的内容。这种收敛现象适用于包括最先进模型在内的广泛类别的 GNN，其中包括均值聚合和图转换器中的基于注意力的机制。我们的结果适用于包括（稀疏的）Erdős-Rényi 模型和随机块模型在内的广泛类别的随机图模型。我们通过实证验证了这些发现，并观察到即使在相对较小的图上，收敛现象已经显现出来。