A multi-relational neighbors constructed graph neural network for heterophily graph learning

Graph neural networks (GNNs) have shown great power in exploring graph representation. However, most current GNNs are based on the homophily assumption and they have two primary weaknesses when applied to heterophily graphs: difficult to capture long-range dependence and unable to distinguish spatial relationships of neighbors. In an attempt to address these issues, we propose a multi-relational neighbors constructed graph neural network (MRN-GNN). Our core components, neighbor reconstruction and the bi-level attention aggregation mechanism, provide an effective way to enhance the ability to express heterophily graphs. Specifically, for neighbor reconstruction, we establish connections between node pairs with highly similar features, making it possible to capture long-range dependences. Meanwhile, we construct multi-relational neighbors for each node to distinguish different spatial structure of neighbors. Based on the reconstructed graph, a bi-level aggregation scheme is proposed to enable hierarchical aggregation, facilitating better feature transmission among multi-relational nodes. During this process, an attention mechanism is built to dynamically assign weights to each neighbor under different relations, further strengthening the representation capability. In this work, we focus on the node classification task on heterophily graphs. We conduct comprehensive experiments on seven datasets, including both heterophily and homophily datasets. Compared with representative methods, our MRN-GNN demonstrates significant superiority on heterophily graphs, while also achieving competitive results on homophily graphs.