# Classification from Pairwise Similarities/Dissimilarities and Unlabeled Data via Empirical Risk Minimization

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

## Key facts

- Cited by 21 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 26 Apr 2019.

## Built on by (most cited first, 21 of 21)

- [Learning from Similarity-Confidence Data](https://mlsanity.com/paper/2102.06879/) (2021)
- [A General Framework for Learning from Weak Supervision](https://mlsanity.com/paper/2402.01922/) (2024)
- [Training Deep Architectures Without End-to-End Backpropagation: A Survey on the Provably Optimal Methods](https://mlsanity.com/paper/2101.03419/) (2021)
- [Unified Risk Analysis for Weakly Supervised Learning](https://mlsanity.com/paper/2309.08216/) (2023)
- [Applications of Deep Learning in Fish Habitat Monitoring: A Tutorial and Survey](https://mlsanity.com/paper/2206.05394/) (2022)
- [Multi-Class Classification from Single-Class Data with Confidences](https://mlsanity.com/paper/2106.08864/) (2021)
- [Labels, Information, and Computation: Efficient Learning Using Sufficient Labels](https://mlsanity.com/paper/2104.09015/) (2021)
- [Learning from Label Proportions with Instance-wise Consistency](https://mlsanity.com/paper/2203.12836/) (2022)
- [Learning from Positive and Unlabeled Data with Augmented Classes](https://mlsanity.com/paper/2207.13274/) (2022)
- [A Symmetric Loss Perspective of Reliable Machine Learning](https://mlsanity.com/paper/2101.01366/) (2021)
- [RoLNiP: Robust Learning Using Noisy Pairwise Comparisons](https://mlsanity.com/paper/2303.02341/) (2023)
- [Q&A Label Learning](https://mlsanity.com/paper/2305.04539/) (2023)
- [Learning from Concealed Labels](https://mlsanity.com/paper/2412.02230/) (2024)
- [Learning from M-Tuple Dominant Positive and Unlabeled Data](https://mlsanity.com/paper/2506.15686/) (2025)
- [A Unified Empirical Risk Minimization Framework for Flexible N-Tuples Weak Supervision](https://mlsanity.com/paper/2507.07771/) (2025)
- [Learning from Similarity-Confidence and Confidence-Difference](https://mlsanity.com/paper/2508.05108/) (2025)
- [A Unified and Stable Risk Minimization Framework for Weakly Supervised Learning with Theoretical Guarantees](https://mlsanity.com/paper/2511.22823/) (2025)
- [FastBUS: A Fast Bayesian Framework for Unified Weakly-Supervised Learning](https://mlsanity.com/paper/2603.00517/) (2026)
- [Binary Classification from Coupled Pairwise Labels](https://mlsanity.com/paper/2603.19713/) (2026)
- [Generalized Distribution-Free Semi-Supervised Learning with Risk Rewrite](https://mlsanity.com/paper/2607.11947/) (2026)
- [Importance Weighting for Unlabeled-unlabeled Learning under Distribution Shift](https://mlsanity.com/paper/2609.10994/) (2026)

## Abstract (arXiv)

Pairwise similarities and dissimilarities between data points might be easier to obtain than fully labeled data in real-world classification problems, e.g., in privacy-aware situations. To handle such pairwise information, an empirical risk minimization approach has been proposed, giving an unbiased estimator of the classification risk that can be computed only from pairwise similarities and unlabeled data. However, this direction cannot handle pairwise dissimilarities so far. On the other hand, semi-supervised clustering is one of the methods which can use both similarities and dissimilarities. Nevertheless, they typically require strong geometrical assumptions on the data distribution such as the manifold assumption, which may deteriorate the performance. In this paper, we derive an unbiased risk estimator which can handle all of similarities/dissimilarities and unlabeled data. We theoretically establish estimation error bounds and experimentally demonstrate the practical usefulness of our empirical risk minimization method.