Going Deeper into Permutation-Sensitive Graph Neural Networks
This addresses a fundamental limitation in GNN expressivity for graph learning tasks, offering a novel method rather than an incremental improvement.
The paper tackled the problem of Graph Neural Networks (GNNs) being limited by permutation invariance, which ignores relationships among neighboring nodes, by developing a permutation-sensitive aggregation mechanism that captures pairwise correlations. The result shows it is strictly more powerful than the 2-WL test, not less powerful than the 3-WL test, and achieves linear sampling complexity, with experiments demonstrating superiority on multiple datasets.
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.