基于通用聚合的消息传递图神经网络在大型随机图上的收敛性。

​

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

解决问题：
这篇论文旨在研究随机图模型上的信息传递图神经网络，探究节点数量趋于无穷时，这些网络是否会收敛于其连续对应物。同时，论文还扩展了之前仅限于度规范化均值形式聚合函数的收敛结果，将其推广至包括所有经典信息传递图神经网络所使用的聚合函数，如基于注意力的信息传递或在（度规范化的）卷积信息传递之上的最大卷积信息传递等。这是否是一个新问题？是的，这是一个新问题。

关键思路：
论文的关键思路是基于McDiarmid不等式，给出了非渐进的较高概率界限，以量化信息传递图神经网络在随机图模型上收敛于其连续对应物的程度。此外，论文还将收敛结果扩展至包括所有经典信息传递图神经网络所使用的聚合函数，这是之前的研究所没有的。因此，相比当前这个领域的研究状况，这篇论文的思路有新意。

其他亮点：
论文的实验设计采用了随机图模型，并给出了详细的实验结果。此外，论文还探究了聚合函数为坐标最大值时的情况，这需要一种完全不同的证明技巧，并产生了一种定性上不同的收敛速率。论文没有开源代码。这项工作值得进一步深入研究。

关于作者：
Matthieu Cordonnier、Nicolas Keriven、Nicolas Tremblay和Samuel Vaiter是本篇论文的主要作者。Matthieu Cordonnier和Nicolas Keriven分别来自法国国家信息和自动化研究所和巴黎综合理工学院，他们之前的代表作包括“Learning with Average Precision: Training Image Retrieval with a Listwise Loss”和“Convolutional Networks with Dense Connectivity”。Nicolas Tremblay和Samuel Vaiter分别来自法国国家信息和自动化研究所和巴黎萨克雷大学，他们之前的代表作包括“High-dimensional estimation with finite random matrices”和“Adaptive Sampling for Low-rank Tensor Completion”。

相关研究：
近期的相关论文包括：

1. “Graph Neural Networks with convolutional ARMA filters”，作者：Ferrari, C., & Defferrard, M.，机构：瑞士洛桑联邦理工学院。
2. “On the convergence of graph convolutional networks on random graphs”，作者：Jiang, J., Chang, K. W., & Liu, Y.，机构：纽约大学。
3. “Graph Convolutional Networks with EigenPooling”，作者：Gao, H., Zhang, Z., & Ji, S.，机构：伊利诺伊大学香槟分校。

论文摘要：我们研究了随着节点数量趋近于无穷大，消息传递图神经网络在随机图模型上收敛于其连续对应物的情况。直到现在，这种收敛仅适用于聚合函数采用度规范化均值形式的体系结构。我们将这些结果扩展到一类非常广泛的聚合函数中，该类函数包括所有经典的消息传递图神经网络，例如基于注意力的消息传递或置顶的最大卷积消息传递（在规范化卷积消息传递之上）。在温和的假设下，我们给出了高概率的非渐近界限来量化这种收敛。我们的主要结果基于McDiarmid不等式。有趣的是，我们单独处理了聚合是逐个坐标最大值的情况，因为它需要非常不同的证明技巧，并产生了一种性质上不同的收敛速率。

​Read More