由于消息传递—图神经网络(MPNN)应用在稀疏图时相对于节点数量具有线性复杂性,因此它们已被广泛使用, 不过它们的理论表达能力bounded by一阶 Weisfeiler-Lehman 检验 (1-WL)。
在本文中,我们表明,如果自定义特征值相关的非线性函数设计图卷积supports并使用任意大的感受野进行掩蔽,则 MPNN 在理论上比 1-WL 测试更强大。实验表明该方法与3-WL 同样强大,同时能够保持空间局部化(spatially localized)。此外,通过设计自定义滤波器函数,输出可以具有各种频率分量,从而允许卷积过程学习给定输入图信号与其相关属性的不同关系。
目前,最好的 3-WL 等效图神经网络的计算复杂度为 O(n^3 ),内存使用量为 O(n^2 ),考虑非局部更新机制,并且不提供输出的频谱。但是本文所提出的方法克服了所有上述问题,并在许多下游任务中达到了最先进的结果。