# Asymptotic behavior of ℓp-based Laplacian regularization in semi-supervised learning

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

## Key facts

- Cited by 16 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 2 Mar 2016.

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

- [Eigen-convergence of Gaussian kernelized graph Laplacian by manifold heat interpolation](https://mlsanity.com/paper/2101.09875/) (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)
- [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)
- [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)
- [Continuum limit of p-biharmonic equations on graphs](https://mlsanity.com/paper/2404.19689/) (2024)
- [Hypergraph p-Laplacian regularization on point clouds for data interpolation](https://mlsanity.com/paper/2405.01109/) (2024)
- [Graph-Based Semi-Supervised Segregated Lipschitz Learning](https://mlsanity.com/paper/2411.03273/) (2024)
- [Hypergraph p-Laplacian equations for data interpolation and semi-supervised learning](https://mlsanity.com/paper/2411.12601/) (2024)
- [Interface Laplace Learning: Learnable Interface Term Helps Semi-Supervised Learning](https://mlsanity.com/paper/2408.05419/) (2024)
- [Large Data Limits of Laplace Learning for Gaussian Measure Data in Infinite Dimensions](https://mlsanity.com/paper/2601.14515/) (2026)
- [Planner-Admissible Graph-PDE Value Extensions for Sparse Goal-Conditioned Planning](https://mlsanity.com/paper/2605.19185/) (2026)
- [A Near-Linear-Time Solver for Graph p-Laplacian Semi-Supervised Learning via Continuation in p](https://mlsanity.com/paper/2607.03503/) (2026)
- [Target-Aware State-Adaptive p-Dirichlet Graph Neural Regression for Non-Invasive Body-Composition Estimation](https://mlsanity.com/paper/2608.29496/) (2026)

## Abstract (arXiv)

Given a weighted graph with N vertices, consider a real-valued regression problem in a semi-supervised setting, where one observes n labeled vertices, and the task is to label the remaining ones. We present a theoretical study of ℓp-based Laplacian regularization under a d-dimensional geometric random graph model. We provide a variational characterization of the performance of this regularized learner as N grows to infinity while n stays constant, the associated optimality conditions lead to a partial differential equation that must be satisfied by the associated function estimate hatf. From this formulation we derive several predictions on the limiting behavior the d-dimensional function hatf, including (a) a phase transition in its smoothness at the threshold p = d + 1, and (b) a tradeoff between smoothness and sensitivity to the underlying unlabeled data distribution P. Thus, over the range p ≤ d, the function estimate hatf is degenerate and "spiky," whereas for p≥ d+1, the function estimate hatf is smooth. We show that the effect of the underlying density vanishes monotonically with p, such that in the limit p = ∞, corresponding to the so-called Absolutely Minimal Lipschitz Extension, the estimate hatf is independent of the distribution P. Under the assumption of semi-supervised smoothness, ignoring P can lead to poor statistical performance, in particular, we construct a specific example for d=1 to demonstrate that p=2 has lower risk than p=∞ due to the former penalty adapting to P and the latter ignoring it. We also provide simulations that verify the accuracy of our predictions for finite sample sizes. Together, these properties show that p = d+1 is an optimal choice, yielding a function estimate hatf that is both smooth and non-degenerate, while remaining maximally sensitive to P.