{"ID":5935653,"CreatedAt":"2026-07-07T01:22:02.77346169Z","UpdatedAt":"2026-07-07T02:10:06.972658124Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2607.03503","arxiv_id":"2607.03503","title":"A Near-Linear-Time Solver for Graph $p$-Laplacian Semi-Supervised Learning via Continuation in $p$","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\u003ed$. 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.","short_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 dri...","url_abs":"https://arxiv.org/abs/2607.03503","url_pdf":"https://arxiv.org/pdf/2607.03503v1","authors":"[\"Oren E. Livne\"]","published":"2026-07-03T17:24:15Z","proceeding":"cs.LG","tasks":"[\"cs.LG\"]","methods":"[]","has_code":false,"code_links":[{"ID":613924,"CreatedAt":"2026-07-07T01:22:02.77346169Z","UpdatedAt":"2026-07-07T01:22:02.77346169Z","DeletedAt":null,"paper_id":5935653,"paper_url":"https://arxiv.org/abs/2607.03503","paper_title":"A Near-Linear-Time Solver for Graph $p$-Laplacian Semi-Supervised Learning via Continuation in $p$","repo_url":"https://github.com/orenlivne/np","is_official":false,"mentioned_in_paper":false,"mentioned_in_github":true,"github_stars":0}]}