Geometric Imbalance in Semi-Supervised Node Classification

Class imbalance in graph data poses a major challenge for effective node classification, particularly in semi-supervised settings. In this work, we formally introduce the concept of geometric imbalance, which characterizes how message passing on class-imbalanced graphs induces geometric ambiguity among minority nodes in the embedding space. We provide a rigorous theoretical analysis and propose a unified framework to explicitly mitigate geometric imbalance through pseudo-label alignment, node reordering, and ambiguity filtering. Extensive experiments on diverse benchmarks show that our approach consistently outperforms existing methods, especially under severe class imbalance. Our findings offer new theoretical insights and practical tools for robust semi-supervised node classification.

Overview of Geometric Imbalance. Figure (a) presents a conceptual overview of geometric imbalance under different pretraining and fine-tuning scenarios for both GNNs and MLPs. Figure (b)--(e) use t-SNE visualizations to directly contrast the evolution of node embeddings: for GNNs (Case 1 and 2), fine-tuning on imbalanced data leads to a substantial increase in intra-class dispersion and a reduction in inter-class separation for minority classes, resulting in pronounced geometric imbalance. In contrast, MLPs (Case 3 and 4) preserve compact and well-separated clusters, showing minimal change regardless of class imbalance. This empirical contrast highlights that geometric imbalance is a distinctive and aggravated issue in GNNs, primarily due to their message passing mechanisms, while it remains marginal in MLPs. Furthermore, Figure (f) and (g) quantitatively validate our theoretical results, demonstrating a strong positive correlation between geometric imbalance and prediction entropy (as predicted by Theorem 1), as well as a monotonic relationship between geometric imbalance and the class imbalance ratio (as characterized by Theorem 2). Taken together, these empirical observations not only substantiate our theoretical claims but also underscore the need for GNN-specific mitigation strategies.

Overall pipeline of UNREAL. Our UNREAL framework mitigates geometric imbalance through three flexible and complementary components: (1) DPAM: a DualPath PseudoLabeler that enhances pseudo-label quality via alignment between clustering and classification; (2) NR: a Node-Reordering mechanism that jointly considers geometric proximity and classifier confidence; and (3) DGIS: a Discarding Geometrically Imbalanced Nodes module that filters out samples with ambiguous geometric positioning. Notably, DGIS can be viewed as a lightweight, approximate alternative to direct geometric imbalance scoring, enabling scalable filtering without requiring true labels or dense computations. These components can be used independently or in combination, allowing the framework to adapt to various scenarios and computational budgets.

Experimental results of our method and other baselines on four class-imbalanced node classification benchmark datasets with p=10. We report averaged balanced accuracy (bAcc., %) and F1-score (%) with the standard errors over 5 repetitions on three representative GNN architectures (GCN, GAT, and GraphSAGE).

Experimental results of our method and other baselines on four class-imbalanced node classification benchmark datasets with p=20. We report averaged balanced accuracy (bAcc., %) and F1-score (%) with the standard errors over 5 repetitions on three representative GNN architectures (GCN, GAT, and GraphSAGE).

Experimental results of our method and other baselines on four class-imbalanced node classification benchmark datasets with p=50. We report averaged balanced accuracy (bAcc., %) and F1-score (%) with the standard errors over 5 repetitions on three representative GNN architectures (GCN, GAT, and GraphSAGE).

Experimental results of our method and other baselines on four class-imbalanced node classification benchmark datasets with p=100. We report averaged balanced accuracy (bAcc., %) and F1-score (%) with the standard errors over 5 repetitions on three representative GNN architectures (GCN, GAT, and GraphSAGE).

Experimental results of our method and other baselines on Computers-Random. We report averaged balanced accuracy (bAcc., %) and F1-score (%) with the standard errors over 5 repetitions on three representative GNN architectures.

Experimental results of our method and other baselines on CS-Random. We report averaged balanced accuracy (bAcc., %) and F1-score (%) with the standard errors over 5 repetitions on three representative GNN architectures.

Experimental results of our method and other baselines on Flickr. We report averaged balanced accuracy (bAcc., %) and F1-score (%) with the standard errors over 5 repetitions on three representative GNN architectures.

Experimental results of our method and other baselines on Ogbn-Arxiv. We report averaged balanced accuracy (bAcc., %) and F1-score (%) with the standard errors over 5 repetitions on three representative GNN architectures.