Title: The Impact of Neighborhood Distribution in Graph Convolutional Networks. Abstract: Graph Convolutional Networks (GCNs) which aggregate information from neighbors to learn node representation, have shown excellent ability in processing graph-structured data. However, it is inaccurate that the notable performance of GCNs tends to depend on strong homophily assumption of networks, since GCNs can also perform well over some heterophilous graphs. Thus the impact of homophily on GCNs needs to be reconsidered. In this paper, we study what influences the aggregation of GCNs from the perspective of neighborhood distribution. Theoretical and empirical analysis is provided to reveal that the distinguishability of neighborhood distribution plays a more important role in the performance of GCN than homophily. Furthermore, we address that neighborhood structure and neighborhood range are two key factors for GCNs to promote neighborhood distinguishability. Based on the conclusion, we propose an improved graph convolution network (GCN-PND) including updating graph topology based on the similarity between local neighborhood distribution of nodes and designing extensible aggregation from multi-hop neighbors. We did extensive experiments on graph benchmark datasets to analyze the superiority of the proposed method. The experimental results demonstrate that GCN-PND is more effective on heterophilous datasets than most of existing state-of-the-art GCN methods.
