Conflicting Node Discrimination Graph Neural Network for Semi-supervised Node Classification

Abstract

Graph Neural Networks (GNNs) have exhibited extraordinary performance in data mining. The success depends on the message passing mechanism, which is consistent with the homophily assumption that adjacent nodes share similar behaviors. However, the connected nodes in real-world graphs often show dissimilar behaviors, which is presented as the heterophily problem. A series of works proposed various models to solve the heterophily problem. They usually assume that the neighborhood distribution of nodes with the same class tends to be similar, while distinguishable from nodes of different classes. However, our experiments discovered that many nodes belonging to different classes share the same neighbor distribution in the mainstream datasets. The performance of GNN also degrades in these conflicting nodes. To detect the conflicting nodes and improve their prediction accuracy, we propose the Conflicting Node Discrimination GNN (CNDGNN). It firstly detects the possible conflicting nodes with the same neighbor distribution according to the selected high-quality pseudo-label. Then it estimates the class type of conflicting nodes with the same neighbor distribution through nodes' high-order neighbor distributions and original features, and the aggregation weights are learned to assign positive weights for nodes of the same class type and negative weights for nodes of different classes. The theoretical analysis proves that CNDGNN performs better than GCN in the conflicting nodes and explores the key design view when solving the conflicting node problem. The experiments demonstrate the effectiveness of our method in the mainstream datasets and verify that our method performs better in conflicting nodes.