【ICML2021】 突破图神经网络中消息传递的限制

由于消息传递—图神经网络（MPNN）应用在稀疏图时相对于节点数量具有线性复杂性，因此它们已被广泛使用， 不过它们的理论表达能力bounded by一阶 Weisfeiler-Lehman 检验 (1-WL)。

在本文中，我们表明，如果自定义特征值相关的非线性函数设计图卷积supports并使用任意大的感受野进行掩蔽，则 MPNN 在理论上比 1-WL 测试更强大。实验表明该方法与3-WL 同样强大，同时能够保持空间局部化(spatially localized)。此外，通过设计自定义滤波器函数，输出可以具有各种频率分量，从而允许卷积过程学习给定输入图信号与其相关属性的不同关系。

目前，最好的 3-WL 等效图神经网络的计算复杂度为 O(n^3 )，内存使用量为 O(n^2 )，考虑非局部更新机制，并且不提供输出的频谱。但是本文所提出的方法克服了所有上述问题，并在许多下游任务中达到了最先进的结果。

http://honeine.fr/paul/publi/21.icml.gnn.pdf