Graph neural network (GNN) has recently been established as an effective representation learning framework on graph data. However, the popular message passing models rely on local permutation invariant aggregate functions, which gives rise to the concerns about their representational power. Here, we introduce the concept of automorphic equivalence to theoretically analyze GNNs expressiveness in differentiating nodes structural role. We show that the existing message passing GNNs have limitations in learning expressive representations. Moreover, we design a novel GNN class that leverages learnable automorphic equivalence filters to explicitly differentiate the structural roles of each nodes neighbors, and uses a squeeze-and-excitation module to fuse various structural information. We theoretically prove that the proposed model is expressive in terms of generating distinct representations for nodes with different structural feature. Besides, 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 strong baselines.
Download