论文标题
更深入地进入置换敏感的图形神经网络
Going Deeper into Permutation-Sensitive Graph Neural Networks
论文作者
论文摘要
邻接矩阵的排列的不变性，即图同构，是图神经网络（GNNS）的总体要求。通常，在汇总消息时，可以通过对节点排列的不变操作来满足此先决条件。但是，这种不变的方式可能会忽略相邻节点之间的关系，从而阻碍GNN的表现。在这项工作中，我们通过排列组设计了有效的置换敏感聚合机制，从而捕获相邻节点之间的成对相关性。我们证明，与二维Weisfeiler-Lehman（2-WL）图同构测试相比，我们的方法严格强大，并且比3-WL测试强大。此外，我们证明我们的方法达到了线性抽样的复杂性。关于多个合成和现实世界数据集的全面实验证明了我们模型的优势。
The invariance to permutations of the adjacency matrix, i.e., graph isomorphism, is an overarching requirement for Graph Neural Networks (GNNs). Conventionally, this prerequisite can be satisfied by the invariant operations over node permutations when aggregating messages. However, such an invariant manner may ignore the relationships among neighboring nodes, thereby hindering the expressivity of GNNs. In this work, we devise an efficient permutation-sensitive aggregation mechanism via permutation groups, capturing pairwise correlations between neighboring nodes. We prove that our approach is strictly more powerful than the 2-dimensional Weisfeiler-Lehman (2-WL) graph isomorphism test and not less powerful than the 3-WL test. Moreover, we prove that our approach achieves the linear sampling complexity. Comprehensive experiments on multiple synthetic and real-world datasets demonstrate the superiority of our model.
