Finding Global Homophily in Graph Neural Networks When Meeting Heterophily

2022/05/15 by Xiang Li, Renyu Zhu, Li, Xiang +11 · 17 citations
Computer Science · Neuroscience · #Advanced Graph Neural Networks #Artificial Intelligence (cs.AI) #Brain Tumor Detection and Classification #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning and ELM

paper · pdf · doi:10.48550/arxiv.2205.07308

openalex publication_date 2022/05/15 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We investigate graph neural networks on graphs with heterophily. Some existing methods amplify a node's neighborhood with multi-hop neighbors to include more nodes with homophily. However, it is a significant challenge to set personalized neighborhood sizes for different nodes. Further, for other homophilous nodes excluded in the neighborhood, they are ignored for information aggregation. To address these problems, we propose two models GloGNN and GloGNN++, which generate a node's embedding by aggregating information from global nodes in the graph. In each layer, both models learn a coefficient matrix to capture the correlations between nodes, based on which neighborhood aggregation is performed. The coefficient matrix allows signed values and is derived from an optimization problem that has a closed-form solution. We further accelerate neighborhood aggregation and derive a linear time complexity. We theoretically explain the models' effectiveness by proving that both the coefficient matrix and the generated node embedding matrix have the desired grouping effect. We conduct extensive experiments to compare our models against 11 other competitors on 15 benchmark datasets in a wide range of domains, scales and graph heterophilies. Experimental results show that our methods achieve superior performance and are also very efficient.

Cited by

• ATLAS: Adaptive Topology-based Learning at Scale for Homophilic and Heterophilic Graphs
• Rethinking Message Passing Neural Networks with Diffusion Distance-guided Stress Majorization
• Gauge-Equivariant Graph Networks via Self-Interference Cancellation
• Beyond Fixed Depth: Adaptive Graph Neural Networks for Node Classification Under Varying Homophily
• Graph Few-Shot Learning via Adaptive Spectrum Experts and Cross-Set Distribution Calibration
• GraphTARIF: Linear Graph Transformer with Augmented Rank and Improved Focus
• Bridging Computational Social Science and Deep Learning: Cultural Dissemination-Inspired Graph Neural Networks
• Gumbel-MPNN: Graph Rewiring with Gumbel-Softmax
• Attention Beyond Neighborhoods: Reviving Transformer for Graph Clustering
• Graph Homophily Booster: Rethinking the Role of Discrete Features on Heterophilic Graphs
• Flow Matters: Directional and Expressive GNNs for Heterophilic Graphs
• Adaptive Heterogeneous Graph Neural Networks: Bridging Heterophily and Heterogeneity
• Hypergraph Neural Network with State Space Models for Node Classification
• TANGO: Graph Neural Dynamics via Learned Energy and Tangential Flows
• Sheaf Graph Neural Networks via PAC-Bayes Spectral Optimization
• Aggregation-aware MLP: An Unsupervised Approach for Graph Message-passing
• ReDiSC: A Reparameterized Masked Diffusion Model for Scalable Node Classification with Structured Predictions

Related

• On Local Aggregation in Heterophilic Graphs
• RAW-GNN: RAndom Walk Aggregation based Graph Neural Network
• SIGMA: An Efficient Heterophilous Graph Neural Network with Fast Global Aggregation
• Graph Homophily Booster: Rethinking the Role of Discrete Features on Heterophilic Graphs
• Incorporating Heterophily into Graph Neural Networks for Graph Classification