# Consistency of semi-supervised learning algorithms on graphs: Probit and one-hot methods

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 18 Jun 2019.

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

- [Graph-based Semi-supervised Learning: A Comprehensive Review](https://mlsanity.com/paper/2102.13303/) (2021)
- [Model-Change Active Learning in Graph-Based Semi-Supervised Learning](https://mlsanity.com/paper/2110.07739/) (2021)
- [Graph Laplacian-based Bayesian Multi-fidelity Modeling](https://mlsanity.com/paper/2409.08211/) (2024)
- [A few-shot graph Laplacian-based approach for improving the accuracy of low-fidelity data](https://mlsanity.com/paper/2304.04862/) (2023)
- [Inference with non-differentiable surrogate loss in a general high-dimensional classification framework](https://mlsanity.com/paper/2405.11723/) (2024)

## Abstract (arXiv)

Graph-based semi-supervised learning is the problem of propagating labels from a small number of labelled data points to a larger set of unlabelled data. This paper is concerned with the consistency of optimization-based techniques for such problems, in the limit where the labels have small noise and the underlying unlabelled data is well clustered. We study graph-based probit for binary classification, and a natural generalization of this method to multi-class classification using one-hot encoding. The resulting objective function to be optimized comprises the sum of a quadratic form defined through a rational function of the graph Laplacian, involving only the unlabelled data, and a fidelity term involving only the labelled data. The consistency analysis sheds light on the choice of the rational function defining the optimization.