GraphSB: Boosting Imbalanced Node Classification on Graphs through Structural Balance

• URL: http://arxiv.org/abs/2511.10022v1
• Date: Fri, 14 Nov 2025 01:26:54 GMT
• Title: GraphSB: Boosting Imbalanced Node Classification on Graphs through Structural Balance
• Authors: Chaofan Zhu, Xiaobing Rui, Zhixiao Wang,
• Abstract summary: Imbalanced node classification is a critical challenge in graph learning, where most existing methods typically utilize Graph Neural Networks (GNNs) to learn node representations.<n>We propose GraphSB, a novel framework that incorporates Structural Balance as a key strategy to address the underlying imbalanced graph structure before node synthesis.
• Score: 2.367568291148072
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Imbalanced node classification is a critical challenge in graph learning, where most existing methods typically utilize Graph Neural Networks (GNNs) to learn node representations. These methods can be broadly categorized into the data-level and the algorithm-level. The former aims to synthesize minority-class nodes to mitigate quantity imbalance, while the latter tries to optimize the learning process to highlight minority classes. However, neither category addresses the inherently imbalanced graph structure, which is a fundamental factor that incurs majority-class dominance and minority-class assimilation in GNNs. Our theoretical analysis further supports this critical insight. Therefore, we propose GraphSB (Graph Structural Balance), a novel framework that incorporates Structural Balance as a key strategy to address the underlying imbalanced graph structure before node synthesis. Structural Balance performs a two-stage structure optimization: Structure Enhancement that adaptively builds similarity-based edges to strengthen connectivity of minority-class nodes, and Relation Diffusion that captures higher-order dependencies while amplifying signals from minority classes. Thus, GraphSB balances structural distribution before node synthesis, enabling more effective learning in GNNs. Extensive experiments demonstrate that GraphSB significantly outperforms the state-of-the-art methods. More importantly, the proposed Structural Balance can be seamlessly integrated into state-of-the-art methods as a simple plug-and-play module, increasing their accuracy by an average of 3.67\%.

Related papers

• GraphSB: Boosting Imbalanced Node Classification on Graphs through Structural Balance [40.55283955016589]
  Imbalanced node classification is a critical challenge in graph learning, where most existing methods typically utilize Graph Neural Networks (GNNs) to learn node representations.<n>We propose GraphSB, a novel framework that incorporates Structural Balance as a key strategy to address the underlying imbalanced graph structure before node synthesis.
  arXiv  Detail & Related papers  (2026-01-27T08:34:06Z)
• GraphIFE: Rethinking Graph Imbalance Node Classification via Invariant Learning [49.47096910857841]
  Most graph neural networks implicitly assume a balanced class distribution, which can lead to biased learning and degraded performance on minority classes.<n>We propose GraphIFE, a novel framework designed to mitigate quality inconsistency in synthesized nodes.<n>Our approach incorporates two key concepts from graph invariant learning and introduces strategies to strengthen the embedding space representation.
  arXiv  Detail & Related papers  (2025-09-28T03:41:16Z)
• Unsupervised Graph Clustering with Deep Structural Entropy [25.38926876388394]
  DeSE is a novel unsupervised graph clustering framework incorporating Deep Structural Entropy.<n>It enhances the original graph with quantified structural information and deep neural networks to form clusters.<n>Our clustering assignment method learns node embeddings and a soft assignment matrix to cluster on the enhanced graph.
  arXiv  Detail & Related papers  (2025-05-20T07:38:06Z)
• IsoSEL: Isometric Structural Entropy Learning for Deep Graph Clustering in Hyperbolic Space [57.036143666293334]
  Graph clustering is a longstanding topic in machine learning.<n>In this paper, we study a challenging yet practical problem: deep graph clustering without K considering the imbalance in reality.<n>We present a novel IsoSEL framework for deep graph clustering, where we design a hyperbolic neural network to learn partitioning tree in the Lorentz model of hyperbolic space.
  arXiv  Detail & Related papers  (2025-04-14T08:21:41Z)
• Overcoming Class Imbalance: Unified GNN Learning with Structural and Semantic Connectivity Representations [29.361821020752505]
  Class imbalance is pervasive in real-world graph datasets, where the majority of annotated nodes belong to a small set of classes.<n>We introduce a novel Unified Graph Neural Network Learning (Uni-GNN) framework to tackle class-imbalanced node classification.
  arXiv  Detail & Related papers  (2024-12-30T02:20:40Z)
• Graph Structure Refinement with Energy-based Contrastive Learning [56.957793274727514]
  We introduce an unsupervised method based on a joint of generative training and discriminative training to learn graph structure and representation.<n>We propose an Energy-based Contrastive Learning (ECL) guided Graph Structure Refinement (GSR) framework, denoted as ECL-GSR.<n>ECL-GSR achieves faster training with fewer samples and memories against the leading baseline, highlighting its simplicity and efficiency in downstream tasks.
  arXiv  Detail & Related papers  (2024-12-20T04:05:09Z)
• Learning to Model Graph Structural Information on MLPs via Graph Structure Self-Contrasting [50.181824673039436]
  We propose a Graph Structure Self-Contrasting (GSSC) framework that learns graph structural information without message passing. The proposed framework is based purely on Multi-Layer Perceptrons (MLPs), where the structural information is only implicitly incorporated as prior knowledge. It first applies structural sparsification to remove potentially uninformative or noisy edges in the neighborhood, and then performs structural self-contrasting in the sparsified neighborhood to learn robust node representations.
  arXiv  Detail & Related papers  (2024-09-09T12:56:02Z)
• Synergistic Deep Graph Clustering Network [14.569867830074292]
  We propose a graph clustering framework named Synergistic Deep Graph Clustering Network (SynC) In our approach, we design a Transform Input Graph Auto-Encoder (TIGAE) to obtain high-quality embeddings for guiding structure augmentation. Notably, representation learning and structure augmentation share weights, significantly reducing the number of model parameters.
  arXiv  Detail & Related papers  (2024-06-22T09:40:34Z)
• SE-GSL: A General and Effective Graph Structure Learning Framework through Structural Entropy Optimization [67.28453445927825]
  Graph Neural Networks (GNNs) are de facto solutions to structural data learning. Existing graph structure learning (GSL) frameworks still lack robustness and interpretability. This paper proposes a general GSL framework, SE-GSL, through structural entropy and the graph hierarchy abstracted in the encoding tree.
  arXiv  Detail & Related papers  (2023-03-17T05:20:24Z)
• Semantic Graph Neural Network with Multi-measure Learning for Semi-supervised Classification [5.000404730573809]
  Graph Neural Networks (GNNs) have attracted increasing attention in recent years. Recent studies have shown that GNNs are vulnerable to the complex underlying structure of the graph. We propose a novel framework for semi-supervised classification.
  arXiv  Detail & Related papers  (2022-12-04T06:17:11Z)

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.