Beyond Homophily in Graph Neural Networks: Current Limitations and Effective Designs

Abstract

We investigate the representation power of graph neural networks in the semi-supervised node classification task under heterophily or low homophily, i.e., in networks where connected nodes may have different class labels and dissimilar features. Many popular GNNs fail to generalize to this setting, and are even outperformed by models that ignore the graph structure (e.g., multilayer perceptrons). Motivated by this limitation, we identify a set of key designs -- ego- and neighbor-embedding separation, higher-order neighborhoods, and combination of intermediate representations -- that boost learning from the graph structure under heterophily. We combine them into a graph neural network, H2GCN, which we use as the base method to empirically evaluate the effectiveness of the identified designs. Going beyond the traditional benchmarks with strong homophily, our empirical analysis shows that the identified designs increase the accuracy of GNNs by up to 40% and 27% over models without them on synthetic and real networks with heterophily, respectively, and yield competitive performance under homophily.

arXiv commentAccepted to NeurIPS 2020; version with full appendix

References in corpus (13)

• Emergence of scaling in random networks
• The Emerging Field of Signal Processing on Graphs: Extending High-Dimensional Data Analysis to Networks and Other Irregular Domains
• Inductive Representation Learning on Large Graphs
• Simplifying Graph Convolutional Networks
• Representation Learning on Graphs with Jumping Knowledge Networks
• Pitfalls of Graph Neural Network Evaluation
• Open Graph Benchmark: Datasets for Machine Learning on Graphs
• GMNN: Graph Markov Neural Networks
• Geom-GCN: Geometric Graph Convolutional Networks
• Machine Learning on Graphs: A Model and Comprehensive Taxonomy
• Residual Correlation in Graph Neural Network Regression
• Measuring and Improving the Use of Graph Information in Graph Neural Networks
• Semi-Supervised Learning with Heterophily

Cited by in corpus (23)

• Adaptive Universal Generalized PageRank Graph Neural Network
• SE-GSL: A General and Effective Graph Structure Learning Framework through Structural Entropy Optimization
• Learning Strong Graph Neural Networks with Weak Information
• Homophily-oriented Heterogeneous Graph Rewiring
• Domain-adaptive Message Passing Graph Neural Network
• Bag of Tricks for Node Classification with Graph Neural Networks
• How does Heterophily Impact the Robustness of Graph Neural Networks? Theoretical Connections and Practical Implications
• Beyond Low-Pass Filters: Adaptive Feature Propagation on Graphs
• Graph Neural Networks with Diverse Spectral Filtering
• MM-GNN: Mix-Moment Graph Neural Network towards Modeling Neighborhood Feature Distribution
• Complete the Missing Half: Augmenting Aggregation Filtering with Diversification for Graph Convolutional Networks
• Spatial Heterophily Aware Graph Neural Networks
• Topology-aware Embedding Memory for Continual Learning on Expanding Networks
• Disambiguated Node Classification with Graph Neural Networks
• Neighborhood Homophily-based Graph Convolutional Network
• Robust Node Classification on Graphs: Jointly from Bayesian Label Transition and Topology-based Label Propagation
• Resurrecting Label Propagation for Graphs with Heterophily and Label Noise
• Finding Heterophilic Neighbors via Confidence-based Subgraph Matching for Semi-supervised Node Classification
• Mini-batch graphs for robust image classification
• Node Copying: A Random Graph Model for Effective Graph Sampling
• Beyond Homophily with Graph Echo State Networks
• How to Use Graph Data in the Wild to Help Graph Anomaly Detection?
• Graph Feature Gating Networks