We study the convergence of message passing graph neural networks on random
graph models to their continuous counterpart as the number of nodes tends to
infinity. Until now, this convergence was only known for architectures with
aggregation functions in the form of degree-normalized means. We extend such
results to a very large class of aggregation functions, that encompasses all
classically used message passing graph neural networks, such as attention-based
mesage passing or max convolutional message passing on top of
(degree-normalized) convolutional message passing. Under mild assumptions, we
give non asymptotic bounds with high probability to quantify this convergence.
Our main result is based on the McDiarmid inequality. Interestingly, we treat
the case where the aggregation is a coordinate-wise maximum separately, at it
necessitates a very different proof technique and yields a qualitatively
different convergence rate.

本文研究了随机图模型上信息传递图神经网络收敛于其连续对应物的情况，我们扩展了聚合函数的类别，并利用 McDiarmid 不等式提供了高概率的非渐进上界，最终得到了定量的收敛结论。

具有通用聚合的消息传递图神经网络在大型随机图上的收敛

Convergence of Message Passing Graph Neural Networks with Generic  Aggregation On Large Random Graphs

We explore in some detail the notion of algorithmic stability as a viable
framework for analyzing the generalization error of learning algorithms. We
introduce the new notion of training stability of a learning algorithm and show
that, in a general setting, it is sufficient for good bounds on generalization
error. In the PAC setting, training stability is both necessary and sufficient
for learnability.\ The approach based on training stability makes no reference
to VC dimension or VC entropy. There is no need to prove uniform convergence,
and generalization error is bounded directly via an extended McDiarmid
inequality. As a result it potentially allows us to deal with a broader class
of learning algorithms than Empirical Risk Minimization. \ We also explore the
relationships among VC dimension, generalization error, and various notions of
stability. Several examples of learning algorithms are considered.

探讨了算法稳定性作为分析学习算法泛化误差的可行框架的概念。引入了学习算法训练稳定性的新概念，并证明在一般情况下它足以得到泛化误差的好界。在 PAC 设置中，训练稳定性在可学习性上既是必要的也是充分的。基于训练稳定性的方法不涉及 VC 维或 VC 熵，不需要证明一致收敛，而广义 McDiarmid 不等式可直接限制泛化误差。因此，它可能使我们处理比经验风险最小化更广泛的学习算法类。还探讨了 VC 维、泛化误差和各种稳定性概念之间的关系，并考虑了几个学习算法的例子。