# An Effective Flow-based Method for Positive-Unlabeled Learning: 2-HNC

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 6 of its 42 references that are in the map.
- First posted on arXiv 13 May 2025.

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

- [Positive-Unlabeled Learning with Non-Negative Risk Estimator](https://mlsanity.com/paper/1703.00593/) (2017)
- [Learning from positive and unlabeled data: a survey](https://mlsanity.com/paper/1811.04820/) (2018)
- [One-Class Classification: Taxonomy of Study and Review of Techniques](https://mlsanity.com/paper/1312.0049/) (2013)
- [Positive-Unlabeled Learning using Random Forests via Recursive Greedy Risk Minimization](https://mlsanity.com/paper/2210.08461/) (2022)
- [A Robust Ensemble Approach to Learn From Positive and Unlabeled Data Using SVM Base Models](https://mlsanity.com/paper/1402.3144/) (2014)
- [HNCcorr: A Novel Combinatorial Approach for Cell Identification in Calcium-Imaging Movies](https://mlsanity.com/paper/1703.01999/) (2017)

## Abstract (arXiv)

In many scenarios of binary classification, only positive instances are provided in the training data, leaving the rest of the data unlabeled. This setup, known as positive-unlabeled (PU) learning, is addressed here with a network flow-based method which utilizes pairwise similarities between samples. The method we propose here, 2-HNC, leverages Hochbaum's Normalized Cut (HNC) and the set of solutions it provides by solving a parametric minimum cut problem. The set of solutions, that are nested partitions of the samples into two sets, correspond to varying tradeoff values between the two goals: high intra-similarity inside the sets and low inter-similarity between the two sets. This nested sequence is utilized here to deliver a ranking of unlabeled samples by their likelihood of being negative. Building on this insight, our method, 2-HNC, proceeds in two stages. The first stage generates this ranking without assuming any negative labels, using a problem formulation that is constrained only on positive labeled samples. The second stage augments the positive set with likely-negative samples and recomputes the classification. The final label prediction selects among all generated partitions in both stages, the one that delivers a positive class proportion, closest to a prior estimate of this quantity, which is assumed to be given. Extensive experiments across synthetic and real datasets show that 2-HNC yields strong performance and often surpasses existing state-of-the-art algorithms.