  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.
