Abstract
Graph-based semi-supervised learning (GSSL) is a powerful paradigm for leveraging large amounts of unlabeled data. However, its performance is severely compromised when the initial labeled set is imbalanced, as label propagation tends to favor majority classes, skewing decision boundaries. This paper discusses the Iterative Nearest Neighborhood Oversampling (INNO) algorithm, which addresses this "majority rules" bias. INNO intelligently expands the minority labeled set by recruiting high-confidence unlabeled samples while employing a boundary-aware safety check. Evaluations on the IRIS, MNIST, and synthetic datasets show that INNO-enhanced GSSL maintains high accuracy even under extreme imbalance, outperforming existing state-of-the-art methods.
Introduction
In many real-world applications, such as fraud detection or rare disease identification, the data available for training is often highly imbalanced. While semi-supervised learning (SSL) aims to mitigate the scarcity of labeled data by utilizing unlabeled samples, standard graph-based SSL (GSSL) methods like Gaussian Fields and Harmonic Functions (GFHF) and Learning with Local and Global Consistency (LGC) are sensitive to class distribution. When labels are imbalanced, the propagation process naturally favors the majority class, pushing the decision boundary into the minority class's territory and leading to poor classification performance for the "underdog" class.
Existing oversampling techniques like SMOTE are designed for supervised learning and often rely on synthetic data generation. In contrast, SSL environments offer a wealth of real, unlabeled data. The INNO algorithm leverages this resource to balance the labeled set before the final classification phase.
The INNO Algorithm
The core of the Iterative Nearest Neighborhood Oversampling (INNO) approach is to iteratively "recruit" the most representative unlabeled samples into the minority class. Unlike simple oversampling, INNO incorporates a critical "Safety Check" to maintain the integrity of class boundaries.
The algorithm follows an iterative process:
- Minority Identification: The class with the fewest labeled samples is targeted for expansion.
- Neighborhood Search: For each labeled sample in the minority class, the algorithm identifies its $k$-nearest neighbors within the unlabeled pool.
- Boundary Safety Check: To prevent mislabeling near decision boundaries, any unlabeled sample that possesses an edge connecting it to a different class is excluded from recruitment.
- Recruitment: The unlabeled sample with the highest similarity to the existing minority labels is assigned the minority label and moved to the labeled set.
- Iteration: This process repeats until the dataset reaches a balanced state or a predefined stopping criterion is met.
By ensuring that only "safe" samples—those clearly within the minority manifold—are labeled, INNO provides a robust foundation for subsequent GSSL algorithms.
Experimental Evaluation
The effectiveness of INNO was tested across several benchmarks, including the IRIS dataset, the MNIST handwritten digit collection, and synthetic "two-moon" data.
Visualizing the Boundary Shift
The two-moon toy dataset provides a clear visualization of the problem and the INNO solution. In imbalanced scenarios, standard GSSL methods fail to identify the structural gap between the two classes, as the majority class labels dominate the propagation.
As shown in the visualization, while standard GFHF, LGC, and even the more advanced GTAM struggle with boundary skew, the combination of INNO with these algorithms correctly identifies the underlying data structure by first balancing the labeled distribution.
Quantitative Results
On the IRIS dataset, the impact of INNO is even more pronounced as the imbalance ratio increases. Standard methods see a sharp decline in accuracy as the ratio of majority to minority labels grows.
While GFHF and LGC accuracy drops toward 70% at a 9:1 imbalance ratio, the INNO-enhanced versions maintain a stable accuracy of approximately 95%. Similar trends were observed in the MNIST 10-class experiments, where INNO+LGC consistently outperformed the state-of-the-art GTAM algorithm.
Discussion and Conclusion
The INNO algorithm represents a significant step forward in making graph-based SSL practical for real-world, imbalanced datasets. Its primary strength lies in its "boundary awareness"—by refusing to label samples near class intersections, it avoids the propagation of errors that typically plagues oversampling methods. Furthermore, by utilizing real unlabeled data rather than synthetic points, it preserves the natural manifold structure of the dataset.
Overall, INNO provides a computationally efficient and highly effective "safety net" for semi-supervised classification, ensuring that the structure of the data, rather than the distribution of labels, drives the learning process.
Summary updated