【ICML2022】深入探讨置换敏感图神经网络

邻接矩阵排列的不变性，即图同构，是图神经网络(GNNs)的首要要求。通常，聚合消息时，节点排列上的不变操作可以满足这个前提条件。但是，这种不变性可能会忽略相邻节点之间的关系，从而影响GNN的表达能力。在这项工作中，我们通过排列组设计了一种高效的排列敏感聚合机制，捕获相邻节点之间的成对关联。我们证明了我们的方法严格地比二维Weisfeiler-Lehman (2-WL)图同构检验更强大，且不低于3-WL检验。此外，我们证明了我们的方法实现了线性抽样复杂度。在多个合成数据集和真实数据集上的综合实验证明了我们的模型的优越性。

https://www.zhuanzhi.ai/paper/da818de2d710f7cb9087582587f6240f