Node Classification in GNNs: Impact of Neighborhood Label Distribution on Homophily and Heterophily

In node classification, traditional graph neural networks (GNNs) typically assume implicit homophily, indicating that intraclass nodes are likely connected. However, real-world graphs frequently exhibit heterophily, in which interclass nodes are also commonly connected. To address this challenge, recent methods have adopted approaches such as expanding local neighborhoods and employing adaptive message aggregation to enhance the GNN performance on heterophily graphs. Nevertheless, these methods are restricted by the homophily assumption and fail to effectively capture long-range dependencies (e.g., widely separated intraclass nodes) and insufficiently leverage the graph topology. This study investigates the performance differences of GNN when it is applied to both homophily and heterophily graphs and finds that the distinguishability of neighborhood label distributions (NLDs) exhibits a significant correlation with the accuracy of node classification. To assess the impact of NLD on node classification, this study proposes a novel homophily metric based on node distinguishability. Subsequently, this study introduces a new GNN model named NLD-based GNN (NLDGNN) for node classification. First, NLDGNN initializes node representations by integrating node features with node NLDs. To address long-range dependencies in heterophily graphs, NLDGNN utilizes the global label relationship matrix with low-rank characteristics for global message passing. By combining the attention scores derived from the initial node representations, NLDGNN constructs the global label relationship matrix for enhanced message passing, thereby improving the expressiveness of node representations. Experimental results indicate that NLDGNN outperforms existing GNN models on both real-world homophily and heterophily graphs. The code of this study is available at https://github.com/wanli6/NLDGNN.