Automorphic Equivalence-aware Graph Neural Network

Distinguishing the automorphic equivalence of nodes in a graph plays an essential role in many scientific domains, e. g. , computational biologist and social network analysis. However, existing graph neural networks (GNNs) fail to capture such an important property. To make GNN aware of automorphic equivalence, we first introduce a localized variant of this concept --- ego-centered automorphic equivalence (Ego-AE). Then, we design a novel variant of GNN, i. e. , GRAPE, that uses learnable AE-aware aggregators to explicitly differentiate the Ego-AE of each node's neighbors with the aids of various subgraph templates. While the design of subgraph templates can be hard, we further propose a genetic algorithm to automatically search them from graph data. Moreover, we theoretically prove that GRAPE is expressive in terms of generating distinct representations for nodes with different Ego-AE features, which fills in a fundamental gap of existing GNN variants. Finally, we empirically validate our model on eight real-world graph data, including social network, e-commerce co-purchase network, and citation network, and show that it consistently outperforms existing GNNs. The source code is public available at https: //github. com/tsinghua-fib-lab/GRAPE.

Authors

• Fengli Xu
• Quanming Yao Tsinghua university
• Pan Hui
• Yong Li

Keywords

No keywords are indexed for this paper.