# Analysis and algorithms for ℓp-based semi-supervised learning on graphs

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

## Key facts

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

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

- [Uniform Convergence Rates for Lipschitz Learning on Graphs](https://mlsanity.com/paper/2111.12370/) (2021)
- [Hamilton-Jacobi equations on graphs with applications to semi-supervised learning and data depth](https://mlsanity.com/paper/2202.08789/) (2022)
- [Graph-based Active Learning for Semi-supervised Classification of SAR Data](https://mlsanity.com/paper/2204.00005/) (2022)
- [Bi-stochastically normalized graph Laplacian: convergence to manifold Laplacian and robustness to outlier noise](https://mlsanity.com/paper/2206.11386/) (2022)
- [Consistency of semi-supervised learning, stochastic tug-of-war games, and the p-Laplacian](https://mlsanity.com/paper/2401.07463/) (2024)
- [Numerical solution of a PDE arising from prediction with expert advice](https://mlsanity.com/paper/2406.05754/) (2024)
- [Laplace Learning in Wasserstein Space](https://mlsanity.com/paper/2511.13229/) (2025)
- [Persistent Laplacian-enhanced Algorithm for Scarcely Labeled Data Classification](https://mlsanity.com/paper/2305.16239/) (2023)
- [Semi-Supervised Laplace Learning on Stiefel Manifolds](https://mlsanity.com/paper/2308.00142/) (2023)
- [Hypergraph p-Laplacian equations for data interpolation and semi-supervised learning](https://mlsanity.com/paper/2411.12601/) (2024)
- [Laplacian-based Semi-Supervised Learning in Multilayer Hypergraphs by Coordinate Descent](https://mlsanity.com/paper/2301.12184/) (2023)
- [A Laplacian-based Quantum Graph Neural Network for Semi-Supervised Learning](https://mlsanity.com/paper/2408.05498/) (2024)
- [ModSSC: A Modular Framework for Semi-Supervised Classification on Heterogeneous Data](https://mlsanity.com/paper/2512.13228/) (2025)
- [Graph-based Semi-Supervised Learning via Maximum Discrimination](https://mlsanity.com/paper/2602.08042/) (2026)

## Abstract (arXiv)

This paper addresses theory and applications of ℓp-based Laplacian regularization in semi-supervised learning. The graph p-Laplacian for p>2 has been proposed recently as a replacement for the standard (p=2) graph Laplacian in semi-supervised learning problems with very few labels, where Laplacian learning is degenerate. In the first part of the paper we prove new discrete to continuum convergence results for p-Laplace problems on k-nearest neighbor (k-NN) graphs, which are more commonly used in practice than random geometric graphs. Our analysis shows that, on k-NN graphs, the p-Laplacian retains information about the data distribution as p→ ∞ and Lipschitz learning (p=∞) is sensitive to the data distribution. This situation can be contrasted with random geometric graphs, where the p-Laplacian forgets the data distribution as p→ ∞. We also present a general framework for proving discrete to continuum convergence results in graph-based learning that only requires pointwise consistency and monotonicity. In the second part of the paper, we develop fast algorithms for solving the variational and game-theoretic p-Laplace equations on weighted graphs for p>2. We present several efficient and scalable algorithms for both formulations, and present numerical results on synthetic data indicating their convergence properties. Finally, we conduct extensive numerical experiments on the MNIST, FashionMNIST and EMNIST datasets that illustrate the effectiveness of the p-Laplacian formulation for semi-supervised learning with few labels. In particular, we find that Lipschitz learning (p=∞) performs well with very few labels on k-NN graphs, which experimentally validates our theoretical findings that Lipschitz learning retains information about the data distribution (the unlabeled data) on k-NN graphs.