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.
翻译:区分图表中节点的自动等同性在许多科学领域,例如计算生物学家和社会网络分析中发挥着必不可少的作用。然而,现有的图形神经网络(GNN)未能捕捉到如此重要的属性。为了使GNN意识到自动等同性,我们首先引入了这一概念的本地变体 -- -- 以自我为中心的自动等同(Ego-AE)。然后,我们设计了一个GNN(GRAPE)的新变体,即GRAPE,使用可学的 AE-aware聚合器将每个节点的邻居的Ego-AE与各种子图样板的辅助数据明确区分开来。虽然子图样板的设计可能很困难,但我们进一步提议了一种基因算法,以便从图表数据中自动搜索它们。此外,我们理论上证明,GRAPE在为具有不同 Ego-AE特征的节点提供独特的表达方式,填补了现有的GNNV变量的根本空白。最后,我们从经验上验证了我们关于八个真实世界图表数据的模型模型,包括社会网络、e-Com-com-comfi-comflical commas 以及现有的G-commastrubs 。