Is Homophily a Necessity for Graph Neural Networks?

Abstract

Graph neural networks (GNNs) have shown great prowess in learning representations suitable for numerous graph-based machine learning tasks. When applied to semi-supervised node classification, GNNs are widely believed to work well due to the homophily assumption ("like attracts like"), and fail to generalize to heterophilous graphs where dissimilar nodes connect. Recent works design new architectures to overcome such heterophily-related limitations, citing poor baseline performance and new architecture improvements on a few heterophilous graph benchmark datasets as evidence for this notion. In our experiments, we empirically find that standard graph convolutional networks (GCNs) can actually achieve better performance than such carefully designed methods on some commonly used heterophilous graphs. This motivates us to reconsider whether homophily is truly necessary for good GNN performance. We find that this claim is not quite true, and in fact, GCNs can achieve strong performance on heterophilous graphs under certain conditions. Our work carefully characterizes these conditions, and provides supporting theoretical understanding and empirical observations. Finally, we examine existing heterophilous graphs benchmarks and reconcile how the GCN (under)performs on them based on this understanding.

References in corpus (9)

• Semi-Supervised Classification with Graph Convolutional Networks
• Simple and Deep Graph Convolutional Networks
• Geom-GCN: Geometric Graph Convolutional Networks
• Measuring and Improving the Use of Graph Information in Graph Neural Networks
• Is Heterophily A Real Nightmare For Graph Neural Networks To Do Node Classification?
• Grale: Designing Networks for Graph Learning
• Interpreting and Unifying Graph Neural Networks with An Optimization Framework
• Improving Graph Neural Networks with Simple Architecture Design
• Graph Convolution for Semi-Supervised Classification: Improved Linear Separability and Out-of-Distribution Generalization

Cited by in corpus (5)

• Subgroup Generalization and Fairness of Graph Neural Networks
• GCNH: A Simple Method For Representation Learning On Heterophilous Graphs
• GraphGLOW: Universal and Generalizable Structure Learning for Graph Neural Networks
• Finding Heterophilic Neighbors via Confidence-based Subgraph Matching for Semi-supervised Node Classification
• Clarify Confused Nodes via Separated Learning