深入探讨置换敏感的图神经网络

图与邻接矩阵的置换不变性是图神经网络（GNNs）的首要要求，传统模型通过置换不变的聚合操作来满足这一前提条件。然而，这种置换不变的方式可能会忽略邻居与邻居之间的相互关系，进而阻碍GNN的表达能力。为了解决这一问题，本工作利用置换群（permutation groups）设计了一种新颖的置换敏感（与置换不变相反）聚合机制，通过置换采样捕获邻居与邻居之间的成对相关性，从而高效地提升GNN的表达能力：我们证明了所提出的方法严格地比二维Weisfeiler-Lehman（2-WL）图同构测试更强大，并且能够区分一些3-WL测试无法区分的非同构图对；此外，我们还证明了所提出的方法实现了线性的置换采样复杂度。综合而言，本工作通过置换敏感聚合机制设计了一种强大而高效的图神经网络，它在保证表达能力的同时，先后借助近似置换不变性的思想与线性置换采样策略，从而显著降低了计算复杂度。在多个合成数据集和真实数据集上的大量实验验证了所提出模型的优越性。