Abstract
This paper proposes and develops a new graph-based semi-supervised learning method. Different from previous graph-based methods that are based on discriminative models, our method is essentially a generative model in that the class conditional probabilities are estimated by graph propagation and the class priors are estimated by linear regression. Experimental results on various datasets show that the proposed method is superior to existing graph-based semi-supervised learning methods, especially when the labeled subset alone proves insufficient to estimate meaningful class priors.
Introduction
In many machine learning domains, acquiring labeled data is a costly and time-consuming process, whereas unlabeled data is often readily available. Semi-supervised learning (SSL) seeks to bridge this gap by utilizing unlabeled samples to enhance classification performance. Most conventional graph-based SSL techniques are discriminative, aiming to directly estimate the posterior probability $P(y|x)$. However, these methods frequently falter when the labeled subset is "unbalanced"—where the ratio of classes in the small labeled set does not reflect the true population distribution. Furthermore, discriminative graph methods often lack a rigorous theoretical foundation for why graph-computed functions should represent posterior probabilities.
This work addresses these shortcomings by reframing graph-based SSL as a generative process, separately estimating the class-conditional probabilities $P(x|y)$ and the class priors $P(y)$.
Methodology
The proposed generative framework consists of two primary estimation steps followed by a classification phase.
Estimating Class-Conditional Probabilities
The method begins by constructing a weighted affinity graph where nodes represent individual data points. In an ideal scenario with perfectly separated classes, the diagonal elements of the degree matrix $D$ converge to the class-conditional probabilities. For practical, non-ideal datasets, the authors employ an iterative propagation algorithm: $f \leftarrow S \cdot f$.
A critical challenge in iterative propagation is preventing "label washout," where scores eventually homogenize across all points. To solve this, the authors introduced a stopping criterion based on the second derivative of the average likelihood. This identifies the optimal point where the manifold structure is fully captured before class boundaries begin to blur.
Estimating Class Priors
Rather than relying on simple counts from the potentially biased labeled set, the model estimates true class proportions by solving a linear regression problem across the entire graph. This utilizes the structure of both labeled and unlabeled data to infer the global distribution. A Beta distribution is further applied to smooth these estimates in cases of extreme label sparsity.
Classification
Final classification for new data points is performed using kernel regression, integrating the learned conditional probabilities and priors.
Experimental Results
The model was evaluated against state-of-the-art methods like Gaussian Random Fields (GRF) and Local/Global Consistency (LGC) on two benchmarks:
- Cedar Buffalo Binary Digits: Handwritten digit classification ("1 vs 2" and "Odd vs Even").
- Genre Dataset: High-dimensional text classification across 10 document genres.
Robustness to Imbalance
While the proposed method performs comparably to existing models on balanced datasets, it demonstrates significant superiority in unbalanced scenarios. In the digit tasks, while discriminative methods' accuracy dropped sharply when labels were biased, the generative model remained stable. Similarly, on the Genre dataset, the method excelled at identifying minority categories (e.g., "political articles") despite heavily skewed class priors (0.1 vs 0.9).
Discussion and Conclusion
The generative approach offers a deeper "understanding" of underlying data clusters compared to boundary-focused discriminative methods. By leveraging the entire graph to estimate priors, the model effectively corrects for initial labeling bias. Theoretical proofs provided in the paper confirm that these graph-based functions converge to true statistical probabilities as data volume increases.
Future work will focus on refining the heuristic stopping criterion into a more mathematically principled version and exploring the integration of Active Learning to further optimize label selection.
Summary updated