Heterophily-Based Graph Neural Network for Imbalanced Classification

arXiv (Cornell University)

Abstract

Graph neural networks (GNNs) have shown promise in addressing graph-related problems, including node classification. However, conventional GNNs assume an even distribution of data across classes, which is often not the case in real-world scenarios, where certain classes are severely underrepresented. This leads to suboptimal performance of standard GNNs on imbalanced graphs. In this paper, we introduce a unique approach that tackles imbalanced classification on graphs by considering graph heterophily. We investigate the intricate relationship between class imbalance and graph heterophily, revealing that minority classes not only exhibit a scarcity of samples but also manifest lower levels of homophily, facilitating the propagation of erroneous information among neighboring nodes. Drawing upon this insight, we propose an efficient method, called Fast Im-GBK, which integrates an imbalance classification strategy with heterophily-aware GNNs to effectively address the class imbalance problem while significantly reducing training time. Our experiments on real-world graphs demonstrate our model's superiority in classification performance and efficiency for node classification tasks compared to existing baselines.

Authors 5

1. Zirui Liang

   Eindhoven University of Technology

   Affiliation as printed

   Eindhoven University of Technology , Eindhoven , The Netherlands

2. Yuntao Li

   Eindhoven University of Technology

   Affiliation as printed

   Eindhoven University of Technology , Eindhoven , The Netherlands

3. Tianjin Huang

   Eindhoven University of Technology

   Affiliation as printed

   Eindhoven University of Technology , Eindhoven , The Netherlands

4. Akrati Saxena Aachen Leiden Institute of Advanced Computer Science

   Leiden University

   Affiliation as printed

   Leiden Institute of Advanced Computer Science , Leiden University , Leiden , The Netherlands

5. Mykola Pechenizkiy

   Eindhoven University of Technology

   Affiliation as printed

   Eindhoven University of Technology , Eindhoven , The Netherlands