# Rates of Convergence for Laplacian Semi-Supervised Learning with Low Labeling Rates

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

## Key facts

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

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

- [Gamma-convergence of a nonlocal perimeter arising in adversarial machine learning](https://mlsanity.com/paper/2211.15223/) (2022)
- [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)
- [Poisson Reweighted Laplacian Uncertainty Sampling for Graph-based Active Learning](https://mlsanity.com/paper/2210.15786/) (2022)
- [Minimax Optimal Regression over Sobolev Spaces via Laplacian Eigenmaps on Neighborhood Graphs](https://mlsanity.com/paper/2111.07394/) (2021)
- [Boundary Estimation from Point Clouds: Algorithms, Guarantees and Applications](https://mlsanity.com/paper/2111.03217/) (2021)
- [Rates of Convergence for Regression with the Graph Poly-Laplacian](https://mlsanity.com/paper/2209.02305/) (2022)
- [Consistency of semi-supervised learning, stochastic tug-of-war games, and the p-Laplacian](https://mlsanity.com/paper/2401.07463/) (2024)
- [Conic Formulations of Transport Metrics for Unbalanced Measure Networks and Hypernetworks](https://mlsanity.com/paper/2508.10888/) (2025)
- [Robust Certification for Laplace Learning on Geometric Graphs](https://mlsanity.com/paper/2104.10837/) (2021)
- [Nonparametric regression on random geometric graphs sampled from submanifolds](https://mlsanity.com/paper/2405.20909/) (2024)
- [MALADY: Multiclass Active Learning with Auction Dynamics on Graphs](https://mlsanity.com/paper/2409.09475/) (2024)
- [Predicting Anthropometric Body Composition Variables Using 3D Optical Imaging and Machine Learning](https://mlsanity.com/paper/2506.14815/) (2025)
- [Higher-Order Regularization Learning on Hypergraphs](https://mlsanity.com/paper/2510.26533/) (2025)
- [Manifold limit for the training of shallow graph convolutional neural networks](https://mlsanity.com/paper/2601.06025/) (2026)
- [Finsler Geometry, Graph Neural Networks, and You](https://mlsanity.com/paper/2606.17185/) (2026)
- [Convergence of graph Dirichlet energies and graph Laplacians on intersecting manifolds of varying dimensions](https://mlsanity.com/paper/2509.24458/) (2025)
- [Planner-Admissible Graph-PDE Value Extensions for Sparse Goal-Conditioned Planning](https://mlsanity.com/paper/2605.19185/) (2026)

## Abstract (arXiv)

We study graph-based Laplacian semi-supervised learning at low labeling rates. Laplacian learning uses harmonic extension on a graph to propagate labels. At very low label rates, Laplacian learning becomes degenerate and the solution is roughly constant with spikes at each labeled data point. Previous work has shown that this degeneracy occurs when the number of labeled data points is finite while the number of unlabeled data points tends to infinity. In this work we allow the number of labeled data points to grow to infinity with the number of labels. Our results show that for a random geometric graph with length scale varepsilon>0 and labeling rate β>0, if β llvarepsilon2 then the solution becomes degenerate and spikes form, and if βgg varepsilon2 then Laplacian learning is well-posed and consistent with a continuum Laplace equation. Furthermore, in the well-posed setting we prove quantitative error estimates of O(varepsilonβ-1/2) for the difference between the solutions of the discrete problem and continuum PDE, up to logarithmic factors. We also study p-Laplacian regularization and show the same degeneracy result when β ll varepsilonp. The proofs of our well-posedness results use the random walk interpretation of Laplacian learning and PDE arguments, while the proofs of the ill-posedness results use Gamma-convergence tools from the calculus of variations. We also present numerical results on synthetic and real data to illustrate our results.