# Properly-weighted graph Laplacian for semi-supervised learning

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

## Key facts

- Cited by 19 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 10 Oct 2018.

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

- [Graph-based Semi-supervised Learning: A Comprehensive Review](https://mlsanity.com/paper/2102.13303/) (2021)
- [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)
- [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)
- [Consistency of semi-supervised learning, stochastic tug-of-war games, and the p-Laplacian](https://mlsanity.com/paper/2401.07463/) (2024)
- [Improved Graph-based semi-supervised learning Schemes](https://mlsanity.com/paper/2407.00760/) (2024)
- [Robust Certification for Laplace Learning on Geometric Graphs](https://mlsanity.com/paper/2104.10837/) (2021)
- [Learning Label Initialization for Time-Dependent Harmonic Extension](https://mlsanity.com/paper/2205.01358/) (2022)
- [Hypergraph p-Laplacian regularization on point clouds for data interpolation](https://mlsanity.com/paper/2405.01109/) (2024)
- [MALADY: Multiclass Active Learning with Auction Dynamics on Graphs](https://mlsanity.com/paper/2409.09475/) (2024)
- [Advancing Local Clustering on Graphs via Compressive Sensing: Semi-supervised and Unsupervised Methods](https://mlsanity.com/paper/2504.19419/) (2025)
- [Higher-Order Regularization Learning on Hypergraphs](https://mlsanity.com/paper/2510.26533/) (2025)
- [Interface Laplace Learning: Learnable Interface Term Helps Semi-Supervised Learning](https://mlsanity.com/paper/2408.05419/) (2024)
- [Momentum-based minimization of the Ginzburg-Landau functional on Euclidean spaces and graphs](https://mlsanity.com/paper/2501.00389/) (2024)
- [A signal separation view of classification](https://mlsanity.com/paper/2509.24140/) (2025)
- [Topology-Aware Active Learning on Graphs](https://mlsanity.com/paper/2510.25892/) (2025)
- [Planner-Admissible Graph-PDE Value Extensions for Sparse Goal-Conditioned Planning](https://mlsanity.com/paper/2605.19185/) (2026)

## Abstract (arXiv)

The performance of traditional graph Laplacian methods for semi-supervised learning degrades substantially as the ratio of labeled to unlabeled data decreases, due to a degeneracy in the graph Laplacian. Several approaches have been proposed recently to address this, however we show that some of them remain ill-posed in the large-data limit. In this paper, we show a way to correctly set the weights in Laplacian regularization so that the estimator remains well posed and stable in the large-sample limit. We prove that our semi-supervised learning algorithm converges, in the infinite sample size limit, to the smooth solution of a continuum variational problem that attains the labeled values continuously. Our method is fast and easy to implement.