# Graph-based Semi-Supervised Learning via Maximum Discrimination

arXiv: https://arxiv.org/abs/2602.08042 · HTML: https://mlsanity.com/paper/2602.08042/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 8 of its 32 references that are in the map.
- First posted on arXiv 8 Feb 2026.

## Builds on (most cited first, 8 of 8)

- [Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithms](https://mlsanity.com/paper/1708.07747/) (2017)
- [FixMatch: Simplifying Semi-Supervised Learning with Consistency and Confidence](https://mlsanity.com/paper/2001.07685/) (2020)
- [AET vs. AED: Unsupervised Representation Learning by Auto-Encoding Transformations rather than Data](https://mlsanity.com/paper/1901.04596/) (2019)
- [Poisson Learning: Graph Based Semi-Supervised Learning At Very Low Label Rates](https://mlsanity.com/paper/2006.11184/) (2020)
- [Semi-Supervised AUC Optimization based on Positive-Unlabeled Learning](https://mlsanity.com/paper/1705.01708/) (2017)
- [Analysis and algorithms for ℓp-based semi-supervised learning on graphs](https://mlsanity.com/paper/1901.05031/) (2019)
- [Weakly Supervised AUC Optimization: A Unified Partial AUC Approach](https://mlsanity.com/paper/2305.14258/) (2023)
- [Semi-Supervised Laplace Learning on Stiefel Manifolds](https://mlsanity.com/paper/2308.00142/) (2023)

## Abstract (arXiv)

Semi-supervised learning (SSL) addresses the critical challenge of training accurate models when labeled data is scarce but unlabeled data is abundant. Graph-based SSL (GSSL) has emerged as a popular framework that captures data structure through graph representations. Classic graph SSL methods, such as Label Propagation and Label Spreading, aim to compute low-dimensional representations where points with the same labels are close in representation space. Although often effective, these methods can be suboptimal on data with complex label distributions. In our work, we develop AUC-spec, a graph approach that computes a low-dimensional representation that maximizes class separation. We compute this representation by optimizing the Area Under the ROC Curve (AUC) as estimated via the labeled points. We provide a detailed analysis of our approach under a product-of-manifold model, and show that the required number of labeled points for AUC-spec is polynomial in the model parameters. Empirically, we show that AUC-spec balances class separation with graph smoothness. It demonstrates competitive results on synthetic and real-world datasets while maintaining computational efficiency comparable to the field's classic and state-of-the-art methods.