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.
翻译:普通聚合下具有消息传递图神经网络在大型随机图上的收敛
翻译后的摘要:
我们研究了具有消息传递图神经网络在随机图模型上的收敛性,当节点数趋近于无穷大时,网络趋近于连续极限。至今为止,这种收敛只针对具有形式为度归一化均值的聚合函数的体系架构已知。我们将这些结果扩展到了一个非常大的聚合函数类上,其中包含了所有经典的消息传递图神经网络,例如基于注意力的消息传递或在(度规则化)卷积消息传递之上的最大卷积消息传递。在温和的假设下,我们用高概率非渐近界定来定量此收敛。我们的主要结果基于麦克迪尔米德不等式。有趣的是,我们单独处理了协调式最大值的聚合情况,因为它需要一种非常不同的证明技巧,并产生了质量不同的收敛速度。