A Near-Linear-Time Solver for Graph $p$-Laplacian Semi-Supervised Learning via Continuation in $p$
2026-07-03 • Machine Learning
Machine Learning
AI summaryⓘ
The authors study a method for semi-supervised learning on graphs, which spreads label information across similar data points. They focus on a nonlinear approach using the p-Laplacian with p greater than the data dimension to avoid issues seen in the usual p=2 case when labels are very few. They develop a new solver that efficiently handles these nonlinear problems by breaking them into well-conditioned steps solvable by fast graph Laplacian solvers. Their method speeds up computations on large graphs and improves accuracy on examples like MNIST compared to standard quadratic methods. They provide open-source code for their solver.
semi-supervised learninggraph Laplacianp-LaplacianDirichlet energynonlinear PDEchord-Newton methodgraph-based learningLaplacian solverMNIST datasetsparse linear algebra
Authors
Oren E. Livne
Abstract
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\ge2$ (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 $m^{0.96}$-$m^{1.02}$ per family (approximate Cholesky default), and a pooled fit across 228 SuiteSparse graphs gives $m^{1.19}$ vs.\ $m^{1.45}$ for direct factorization; the solver handles a $6.8\times10^7$-edge social network in minutes. Memory is the binding constraint: Cholesky fill reaches $10$-$280\times$ the graph nonzeros vs.\ our $O(m)$ hierarchy. Against the released FCL solver we are $1.5$-$14\times$ 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.