Heterophily-Based Graph Neural Network for Imbalanced Classification

• URL: http://arxiv.org/abs/2310.08725v1
• Date: Thu, 12 Oct 2023 21:19:47 GMT
• Title: Heterophily-Based Graph Neural Network for Imbalanced Classification
• Authors: Zirui Liang, Yuntao Li, Tianjin Huang, Akrati Saxena, Yulong Pei, Mykola Pechenizkiy
• Abstract summary: We introduce a unique approach that tackles imbalanced classification on graphs by considering graph heterophily. We propose Fast Im-GBK, which integrates an imbalance classification strategy with heterophily-aware GNNs. Our experiments on real-world graphs demonstrate our model's superiority in classification performance and efficiency for node classification tasks.
• Score: 19.51668009720269
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• 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.

Related papers

• The Heterophilic Graph Learning Handbook: Benchmarks, Models, Theoretical Analysis, Applications and Challenges [101.83124435649358]
  Homophily principle, ie nodes with the same labels or similar attributes are more likely to be connected. Recent work has identified a non-trivial set of datasets where GNN's performance compared to the NN's is not satisfactory.
  arXiv  Detail & Related papers  (2024-07-12T18:04:32Z)
• Learning to Reweight for Graph Neural Network [63.978102332612906]
  Graph Neural Networks (GNNs) show promising results for graph tasks. Existing GNNs' generalization ability will degrade when there exist distribution shifts between testing and training graph data. We propose a novel nonlinear graph decorrelation method, which can substantially improve the out-of-distribution generalization ability.
  arXiv  Detail & Related papers  (2023-12-19T12:25:10Z)
• Breaking the Entanglement of Homophily and Heterophily in Semi-supervised Node Classification [25.831508778029097]
  We introduce AMUD, which quantifies the relationship between node profiles and topology from a statistical perspective. We also propose ADPA as a new directed graph learning paradigm for AMUD.
  arXiv  Detail & Related papers  (2023-12-07T07:54:11Z)
• GNNEvaluator: Evaluating GNN Performance On Unseen Graphs Without Labels [81.93520935479984]
  We study a new problem, GNN model evaluation, that aims to assess the performance of a specific GNN model trained on labeled and observed graphs. We propose a two-stage GNN model evaluation framework, including (1) DiscGraph set construction and (2) GNNEvaluator training and inference. Under the effective training supervision from the DiscGraph set, GNNEvaluator learns to precisely estimate node classification accuracy of the to-be-evaluated GNN model.
  arXiv  Detail & Related papers  (2023-10-23T05:51:59Z)
• Simplifying Node Classification on Heterophilous Graphs with Compatible Label Propagation [6.071760028190454]
  We show that a well-known graph algorithm, Label Propagation, combined with a shallow neural network can achieve comparable performance to GNNs in semi-supervised node classification on graphs with high homophily. In this paper, we show that this approach falls short on graphs with low homophily, where nodes often connect to the nodes of the opposite classes. Our algorithm first learns the class compatibility matrix and then aggregates label predictions using LP algorithm weighted by class compatibilities.
  arXiv  Detail & Related papers  (2022-05-19T08:34:34Z)
• Optimal Propagation for Graph Neural Networks [51.08426265813481]
  We propose a bi-level optimization approach for learning the optimal graph structure. We also explore a low-rank approximation model for further reducing the time complexity.
  arXiv  Detail & Related papers  (2022-05-06T03:37:00Z)
• Graph Neural Network with Curriculum Learning for Imbalanced Node Classification [21.085314408929058]
  Graph Neural Network (GNN) is an emerging technique for graph-based learning tasks such as node classification. In this work, we reveal the vulnerability of GNN to the imbalance of node labels. We propose a novel graph neural network framework with curriculum learning (GNN-CL) consisting of two modules.
  arXiv  Detail & Related papers  (2022-02-05T10:46:11Z)
• Imbalanced Graph Classification via Graph-of-Graph Neural Networks [16.589373163769853]
  Graph Neural Networks (GNNs) have achieved unprecedented success in learning graph representations to identify categorical labels of graphs. We introduce a novel framework, Graph-of-Graph Neural Networks (G$2$GNN), which alleviates the graph imbalance issue by deriving extra supervision globally from neighboring graphs and locally from graphs themselves. Our proposed G$2$GNN outperforms numerous baselines by roughly 5% in both F1-macro and F1-micro scores.
  arXiv  Detail & Related papers  (2021-12-01T02:25:47Z)
• Distance-wise Prototypical Graph Neural Network in Node Imbalance Classification [9.755229198654922]
  We propose a novel Distance-wise Prototypical Graph Neural Network (DPGNN) for imbalanced graph data. The proposed DPGNN almost always significantly outperforms all other baselines, which demonstrates its effectiveness in imbalanced node classification.
  arXiv  Detail & Related papers  (2021-10-22T19:43:15Z)
• Is Homophily a Necessity for Graph Neural Networks? [50.959340355849896]
  Graph neural networks (GNNs) have shown great prowess in learning representations suitable for numerous graph-based machine learning tasks. 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
  arXiv  Detail & Related papers  (2021-06-11T02:44:00Z)
• Graph Classification by Mixture of Diverse Experts [67.33716357951235]
  We present GraphDIVE, a framework leveraging mixture of diverse experts for imbalanced graph classification. With a divide-and-conquer principle, GraphDIVE employs a gating network to partition an imbalanced graph dataset into several subsets. Experiments on real-world imbalanced graph datasets demonstrate the effectiveness of GraphDIVE.
  arXiv  Detail & Related papers  (2021-03-29T14:03:03Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.