# A Near-Linear-Time Solver for Graph p-Laplacian Semi-Supervised Learning via Continuation in p

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 12 of its 21 references that are in the map.
- First posted on arXiv 3 Jul 2026.

## Builds on (most cited first, 12 of 12)

- [Open Graph Benchmark: Datasets for Machine Learning on Graphs](https://mlsanity.com/paper/2005.00687/) (2020)
- [The Intrinsic Dimension of Images and Its Impact on Learning](https://mlsanity.com/paper/2104.08894/) (2021)
- [Combining Label Propagation and Simple Models Out-performs Graph Neural Networks](https://mlsanity.com/paper/2010.13993/) (2020)
- [Poisson Learning: Graph Based Semi-Supervised Learning At Very Low Label Rates](https://mlsanity.com/paper/2006.11184/) (2020)
- [Analysis of p-Laplacian Regularization in Semi-Supervised Learning](https://mlsanity.com/paper/1707.06213/) (2017)
- [Maximum Flow and Minimum-Cost Flow in Almost-Linear Time](https://mlsanity.com/paper/2203.00671/) (2022)
- [Approximate Gaussian Elimination for Laplacians: Fast, Sparse, and Simple](https://mlsanity.com/paper/1605.02353/) (2016)
- [The game theoretic p-Laplacian and semi-supervised learning with few labels](https://mlsanity.com/paper/1711.10144/) (2017)
- [Asymptotic behavior of ℓp-based Laplacian regularization in semi-supervised learning](https://mlsanity.com/paper/1603.00564/) (2016)
- [Resurrecting Label Propagation for Graphs with Heterophily and Label Noise](https://mlsanity.com/paper/2310.16560/) (2023)
- [Flows in Almost Linear Time via Adaptive Preconditioning](https://mlsanity.com/paper/1906.10340/) (2019)
- [The dual IRLS scheme for (hyper-)graph p-Laplacians and ℓp regression with large exponents](https://mlsanity.com/paper/2603.26061/) (2026)

## Abstract (arXiv)

Graph-based semi-supervised learning (SSL) propagates a few labels over a similarity graph by minimizing a Dirichlet-type energy. The standard quadratic (p=2) energy reduces to a single graph-Laplacian solve, but it degenerates exactly where SSL is most useful when labels are scarce: gathering more unlabeled data drives the p=2 estimate to a near-constant function whenever d≥2 (Nadler-Srebro-Zhou). Well-posedness requires the nonlinear p-Laplacian energy with p>d. Existing solvers reduce this to a sequence of weighted Laplacian solves, but their reference implementations use a direct sparse factorization or ichol-preconditioned CG instead. Plugging a near-linear Laplacian solver is not straightforward: at large p the conductance weights degenerate near flat-gradient edges, making the system nearly singular and causing stagnation without a damped outer iteration. We close this gap. Recasting p-Laplacian SSL as a source-form nonlinear Laplacian flow Bρp(B^top x)=b and solving by damped chord-Newton continuation in p, every linearized system stays well-conditioned and can be delegated to a near-linear Laplacian engine. On size-scaled graph families the wall-clock is empirically m0.96-m1.02 per family (approximate Cholesky default), and a pooled fit across 228 SuiteSparse graphs gives m1.19 vs. m1.45 for direct factorization; the solver handles a 6.8×107-edge social network in minutes. Memory is the binding constraint: Cholesky fill reaches 10-280× the graph nonzeros vs. our O(m) hierarchy. Against the released FCL solver we are 1.5-14× faster at matched accuracy. On MNIST 10-NN, p=3 scores 64% at one label per class vs. 36% for p=2. Code: https://github.com/orenlivne/np.