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

arXiv:2607.03503v1 Announce Type: new 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 dge2 (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 Brho_p(B^op 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.8imes10^7-edge social network in minutes. Memory is the binding constraint: Cholesky fill reaches 10-280imes the graph nonzeros vs. our O(m) hierarchy. Against the released FCL solver we are 1.5-14imes 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.

Source: arXiv cs.LG | 2026-07-07