Pith. sign in

REVIEW 2 major objections 5 minor 20 references

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

T0 review · 2 major / 5 minor · reviewed 2026-07-12 · grok-4.5

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read A damped continuation in p turns graph p-Laplacian SSL into near-linear solves that stay well-conditioned and scale past the factorization memory wall.

desk verdict Solid engineering paper that actually makes variational p-Laplacian SSL usable past the factorization memory wall; novelty is the reduction-plus-damped-continuation package, not a new outer method. read the letter →

arxiv 2607.03503 v1 pith:HAM5BTEO submitted 2026-07-03 cs.LG

Oren E. Livne This is my paper · ORCID
classification cs.LG MSC 65F1068T0565N5505C5062H3090C35
keywords semi-supervisedlearninggraphp-LaplacianlabelpropagationalgebraicmultigridLaplaciannumericalcontinuationinexactNewtonmethods
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Quadratic label propagation on graphs collapses when labels are scarce: with a fixed seed set and growing unlabeled data the p=2 estimate becomes nearly constant for dimension two or higher. Raising the energy exponent to p greater than the intrinsic dimension restores well-posedness, but existing solvers turn each outer step into a weighted Laplacian solve that they factorize directly, which fills memory and stalls at a few tens of thousands of edges. This paper shows that the nonlinear problem is exactly a source-form nonlinear Laplacian flow once labels are folded into a single grounded node. Solving that flow by damped chord-Newton continuation from p=2 keeps every linearized system well-conditioned, so a near-linear Laplacian engine can replace the factorization. On fixed graph families the wall-clock is empirically linear; a 68-million-edge social network finishes in minutes; and the same solver recovers the expected accuracy gain (64 percent versus 36 percent on MNIST at one label per class).

What carries the argument

Grounded-node reduction plus damped chord-Newton continuation in p: labels become linear mass edges to a single ground node, converting the stationarity condition into a monotone nonlinear Laplacian flow whose frozen Jacobians stay SPD and can be inverted by approximate Cholesky or algebraic multigrid.

What would settle it

On a controlled size-scaled family of irregular graphs, measure whether the chord-Newton step count grows with edge count once the conductance floor and Anderson guard are disabled; any clear growth with m would push wall-clock out of the near-linear regime.

Watch

Extended reading notes

Core claim

Recasting p-Laplacian semi-supervised learning as the source-form nonlinear Laplacian flow B ρ_p(B⊤ x)=b, then solving it by damped chord-Newton continuation in p, keeps every linearized system well-conditioned so that a near-linear Laplacian engine can replace direct sparse factorization. The resulting solver is empirically near-linear at fixed graph type, reaches tens of millions of edges, and reproduces the low-label degeneracy fix.

Load-bearing premise

The claim of near-linear total work rests on an observed flat outer Newton step count that is not proved and is restored on the stiffest graphs only by guarded acceleration with no step-count bound.

Editorial extensions

If this is right

  • Industrial label-propagation pipelines that already run on graphs of 10^8–10^9 edges can replace the quadratic energy by a moderate-p energy without leaving the near-linear regime.
  • The same continuation reaches the Lipschitz-learning (p o∞) limit on graphs that previously could not be factored.
  • Memory, not arithmetic, becomes the binding constraint: the O(m) hierarchy fits where a Cholesky factor of 10–280 imes fill does not.
  • Multiclass one-versus-rest problems amortize a single hierarchy setup across all classes, so cost grows only with the number of solves, not with repeated setup.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • Because the outer method is engine-agnostic, any future near-linear Laplacian solver can be dropped in without rewriting the SSL layer.
  • The same grounded-node device and continuation schedule should apply to other monotone edge laws that arise in robust regression or total-variation denoising on graphs.
  • If the empirical step-count bound can be proved under a mild conductance-spread assumption, the method would become the first practical almost-linear algorithm for variational p-Laplacian SSL.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 5 minor

Summary. The paper recasts graph p-Laplacian semi-supervised learning as a source-form nonlinear Laplacian flow B ρ_p(B^ op x)=b via a grounded-node reduction (Proposition 2.1), then solves it by damped chord-Newton continuation in p whose linearized systems are inverted by a near-linear Laplacian engine (approximate Cholesky by default; LAMG+ interchangeable). It claims that the damped outer iteration keeps each frozen Jacobian well-conditioned despite large-p conductance degeneracy, yielding empirically near-linear wall-clock at fixed graph type (m^{0.96}–m^{1.02} with LAMG+; near-linear with AC), a pooled corpus fit of m^{1.19} over 228 SuiteSparse graphs, feasibility on a 6.8×10^7-edge social network, 1.5–14× speedups over the released FCL Newton solver at matched accuracy, and reproduction of the low-label degeneracy fix (MNIST 10-NN: 64% at p=3 vs 36% at p=2 with one label per class). Global outer-loop convergence under a fixed forcing tolerance is proved self-contained in Appendix A from strict convexity alone.

Significance. If the reported results hold, the paper closes a genuine practical gap: p-Laplacian SSL is the theoretically preferred remedy for the Nadler–Srebro–Zhou low-label collapse of quadratic label propagation, yet prior variational solvers were capped by direct sparse factorization or incomplete-Cholesky PCG. The grounded-node reduction, the pairing of continuation with a near-linear inner engine, the self-contained global-convergence argument (Appendix A), the controlled-family scaling with R²≥0.997, the 228-graph corpus, the head-to-head against released FCL code, and the public Julia implementation are concrete strengths. The work makes a method that is already known to be statistically useful at few labels actually runnable at industrial graph sizes; that is a solid numerical-methods contribution to graph SSL, not a new statistical theory.

major comments (2)
  1. §3.4 and §6 correctly state that total near-linear complexity is conditional on an empirical O(1) outer chord-Newton step count (median 11, ≤50 on the corpus), restored on the stiffest graph only by guarded Anderson acceleration with no step-count bound. The title and opening abstract sentence, however, read as an unconditional near-linear-time claim. For a methods journal this is a load-bearing framing issue: either qualify the title/abstract to “empirically near-linear” (matching the body and Table 5.2), or add a short, explicit statement that the O(m log^{3} n log p) expected bound holds only conditional on the observed flat step count. The limitation is already disclosed; it needs to be reflected consistently at the claim surface.
  2. §5.3.2 head-to-head vs released FCL is the sharpest solver comparison and is well designed (identical kNN graphs, same labels, matched classification). The authors note the Julia vs MATLAB/Octave language gap and correctly emphasize that the growth of the margin with size and p is language-independent (inner CG iteration climb). Still, the absolute factors (1.5–14×) are used in the abstract without that caveat. A single clarifying sentence in the abstract or Table 5.4 caption—that the small-graph 1.5× is within the language/implementation gray zone, while the size-dependent growth is the algorithmic signal—would keep the central speed claim proportionate and harder to over-read.
minor comments (5)
  1. Free parameters (ε-floor 10^{-6}, geometric p-multiplier 1.5, inner tolerance 10^{-6}, clamp μ) are fixed throughout. A one-paragraph sensitivity note (or a short appendix table) showing that accuracies and step counts are stable over the ranges already mentioned for ε and the multiplier would strengthen the “out-of-the-box” practicality claim.
  2. Figure 5.1(A) fit is quoted as m^{1.24} in the panel label but m^{1.19} in the text and abstract; align the reported exponents.
  3. Proposition 2.1 proof is clear; a one-line remark that the mass-edge orientation convention (labeled → ground) is arbitrary up to sign would remove a possible source of implementation confusion.
  4. §4.2 ogbn-products experiment (feature-free, three largest classes, five labels/class) is a useful web-scale sanity check. State explicitly whether the 527 s figure is for the full 47-class one-vs-rest sweep or only the three-class subset, so the multiclass amortization claim (3.1) can be checked against the timing.
  5. Typos / polish: “ichol-preconditioned” vs “incomplete-Cholesky-PCG” consistency; “∞-Laplacian sweep” hyphenation; arXiv numbers of concurrent NLF/LAMG+ papers should be checked against final versions if available.

Circularity Check

1 steps flagged · score 2.0 of 10

Minor self-citation of the author's concurrent NLF/LAMG+ engines; outer convergence is re-proved self-containedly from Prop. 2.1, and all scaling/accuracy claims are independent external measurements.

  1. self citation load bearing [§1.3 Contribution / §3.1 Algorithm]
    "Our recent Nonlinear Laplacian Flow (NLF) solver [1] solves Bρ(B⊤ϕ)=αd for a monotone edge law ρ by an inexact chord-Newton iteration whose frozen linearization is a weighted graph Laplacian, inverted by a near-linear Laplacian engine (AC by default; LAMG+ interchangeable). We show that p-Laplacian SSL is an instance of exactly this equation and inherits its near-linear inner solve."

    The chord-Newton iteration, lazy hierarchy, and guarded Anderson step that constitute the practical solver are taken wholesale from the author's concurrent NLF paper rather than re-derived. The dependency is real, yet the paper immediately neutralizes the load-bearing risk by (i) restating the algorithm, (ii) proving global convergence self-containedly in Appendix A from the new Prop. 2.1 alone, and (iii) basing all quantitative claims on external SuiteSparse/FCL/MNIST measurements. The circularity is therefore only the ordinary self-citation of a software substrate, not a definitional reduction of the central SSL result.

full rationale

The paper's derivation chain is the grounded-node reduction (Prop. 2.1, proved here by direct incidence algebra) that makes p-Laplacian SSL an instance of the source-form NLF equation, followed by damped chord-Newton continuation in p whose linearized systems are floored weighted Laplacians. Global convergence of that outer loop is proved from scratch in Appendix A using only strict convexity/coercivity of the augmented energy (Prop. 2.1) plus the standard inexact-Newton + Armijo theorem; the proof explicitly does not rely on [1]. The near-linear engines (AC, LAMG+) and the chord-Newton/Anderson machinery are imported from the author's concurrent arXiv preprints, which is ordinary engineering reuse rather than a definitional loop. No parameter is fitted to data and then re-presented as a prediction; the MNIST 64% vs 36% numbers, the m^{0.96}-m^{1.02} family exponents, the 1.5-14x FCL wall-clock ratios, and the 68 M-edge solve are all direct measurements against SuiteSparse graphs and third-party released code. The only residual circularity is the ordinary self-citation of the solver substrate; it is not load-bearing for the novel reduction or the empirical claims. Hence score 2.

Assumptions & free parameters 4 free parameters · 6 assumptions · 0 invented entities

The central near-linear claim rests on standard convex analysis, the existence of near-linear SDDM solvers from prior literature, a small set of hand-chosen numerical parameters (conductance floor, p-schedule, tolerances), and the empirical observation that outer Newton steps stay flat. No new physical entities are postulated. The reduction and convergence proof use only strict convexity of the augmented energy and uniform positive-definiteness of the floored Jacobian.

free parameters (4)
  • conductance floor ε = 10^{-6}
    ε=10^{-6} floors we ρ'_p(ge) in the frozen Jacobian only; chosen by hand as graph analogue of lagged diffusivity. Fixed point independent of ε, but step quality and conditioning depend on it.
  • p-continuation geometric multiplier = 1.5
    Schedule p_{k+1}=min(p, 1.5 p_k + 0.5); multiplier chosen 'just large enough' that each stage stays in the previous basin. Stated insensitive over [1.3,1.7] but not derived.
  • inner linear residual tolerance = 10^{-6}
    Fixed forcing tolerance 10^{-6} for inexact Newton; meets Dembo–Eisenstat–Steihaug condition but is a free numerical choice.
  • label clamp μ
    Uniform penalty weight on labeled nodes in the energy; treated as a standard SSL hyperparameter, not fitted in the scaling experiments but required for the grounded mass edges.
assumptions (6)
  • standard math The augmented energy is strictly convex and coercive on the gauge quotient for p>1, yielding a unique minimizer (Prop. 2.1).
    Follows from strict monotonicity of ρ_p and connectedness of the augmented graph; standard convex analysis.
  • domain assumption Approximate Cholesky solves floored SDDM systems to fixed relative accuracy in O(m log^3 n) expected time (Kyng–Sachdeva).
    Invoked for the near-linear per-solve cost; the paper does not re-prove it.
  • domain assumption LAMG+ is empirically O(m) on the graph families tested.
    Used interchangeably with AC; empirical, from the author’s concurrent LAMG+ work.
  • domain assumption p>d restores well-posedness of continuum p-Laplacian SSL with few labels (Slepčev–Thorpe, Calder).
    Motivates why p>2 is needed; the solver paper does not re-derive the continuum theory.
  • standard math Guarded Anderson acceleration preserves monotone energy decrease and the fixed point (Lemma A.3).
    Proved in Appendix A from the energy-guard definition; used to restore convergence on stiff graphs.
  • ad hoc to paper Outer Newton step count remains O(1) in m on SSL-relevant graphs when Anderson is enabled.
    Empirical only (median 11, max 50 on 228 graphs); no a priori bound; load-bearing for the total near-linear claim (§3.4, §6).

how reviews work

0 comments
Cite this review

Pith. "Pith review of A Near-Linear-Time Solver for Graph $p$-Laplacian Semi-Supervised Learning via Continuation in $p$." pith.science (2026). https://pith.science/paper/HAM5BTEO

@misc{pith2026260703503,
  author       = {Pith},
  title        = {Pith review of: A Near-Linear-Time Solver for Graph $p$-Laplacian Semi-Supervised Learning via Continuation in $p$},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/HAM5BTEO}},
  note         = {Machine review of arXiv:2607.03503}
}
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\rho_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.

Figures

Figures reproduced from arXiv: 2607.03503 by the authors.

Figure 4
Figure 4. [PITH_FULL_IMAGE:figures/full_fig_p008_4.png] view at source ↗
Figure 5
Figure 5. [PITH_FULL_IMAGE:figures/full_fig_p010_5.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

20 extracted references · 3 linked inside Pith

  1. [1]

    O. E. Livne,NLF: A Resistor-Network Framework and Linear-Time Solver for Con- vex Network-Flow Equilibria, arXiv:2607.02041, 2026. https://arxiv.org/abs/2607.02041. Code: https://github.com/orenlivne/nlf

    arXiv 2026

  2. [2]

    Nadler, N

    B. Nadler, N. Srebro, and X. Zhou,Semi-supervised learning with the graph Laplacian: the limit of infinite unlabelled data, in Adv. Neural Inf. Process. Syst. (NIPS) 22, 2009, pp. 1330–1338

    2009

  3. [3]

    Slepˇ cev and M

    D. Slepˇ cev and M. Thorpe,Analysis ofp-Laplacian regularization in semisupervised learning, SIAM J. Math. Anal., 51 (2019), pp. 2085–2120

    2019

  4. [4]

    El Alaoui, X

    A. El Alaoui, X. Cheng, A. Ramdas, M. J. Wainwright, and M. I. Jordan,Asymptotic behav- ior ofℓ p-based Laplacian regularization in semi-supervised learning, in Proc. 29th Conf. Learning Theory (COLT), PMLR 49, 2016, pp. 879–906

    2016

  5. [5]

    Calder,The game theoreticp-Laplacian and semi-supervised learning with few labels, Non- linearity, 32 (2019), pp

    J. Calder,The game theoreticp-Laplacian and semi-supervised learning with few labels, Non- linearity, 32 (2019), pp. 301–330

    2019

  6. [6]

    Calder, B

    J. Calder, B. Cook, M. Thorpe, and D. Slepˇ cev,Poisson learning: graph based semi-supervised learning at very low label rates, in Proc. 37th Int. Conf. Machine Learning (ICML), PMLR 119, 2020, pp. 1306–1316

    2020

  7. [7]

    Flores, J

    M. Flores, J. Calder, and G. Lerman,Analysis and algorithms forℓ p-based semi-supervised learning on graphs, Appl. Comput. Harmon. Anal., 60 (2022), pp. 77–122

    2022

  8. [8]

    Storn,The dual IRLS scheme for (hyper-)graphp-Laplacians andℓ p regression with large exponents, arXiv:2603.26061, 2026

    J. Storn,The dual IRLS scheme for (hyper-)graphp-Laplacians andℓ p regression with large exponents, arXiv:2603.26061, 2026

    arXiv 2026

Show all 20 references
  1. [9]

    R. Kyng, R. Peng, S. Sachdeva, and D. Wang,Flows in almost linear time via adaptive pre- conditioning, in Proc. 51st ACM Symp. Theory of Computing (STOC), 2019

    2019

  2. [10]

    L. Chen, R. Kyng, Y. P. Liu, R. Peng, M. Probst Gutenberg, and S. Sachdeva,Maximum flow and minimum-cost flow in almost-linear time, in Proc. 63rd IEEE Symp. Foundations of Computer Science (FOCS), 2022

    2022

  3. [11]

    Hein and J.-Y

    M. Hein and J.-Y. Audibert,Intrinsic dimensionality estimation of submanifolds inR d, in Proc. 22nd Int. Conf. Machine Learning (ICML), 2005, pp. 289–296

    2005

  4. [12]

    P. Pope, C. Zhu, A. Abdelkader, M. Goldblum, and T. Goldstein,The intrinsic dimension of images and its impact on learning, in Int. Conf. Learning Representations (ICLR), 2021

    2021

  5. [13]

    Kyng and S

    R. Kyng and S. Sachdeva,Approximate Gaussian elimination for Laplacians—fast, sparse, and simple, in Proc. 57th IEEE Symp. Foundations of Computer Science (FOCS), 2016, pp. 573–582

    2016

  6. [14]

    R. S. Dembo, S. C. Eisenstat, and T. Steihaug,Inexact Newton methods, SIAM J. Numer. Anal., 19 (1982), pp. 400–408

    1982

  7. [15]

    Nocedal and S

    J. Nocedal and S. J. Wright,Numerical Optimization, 2nd ed., Springer, 2006 (Thm. 3.2, global convergence of gradient-related line-search methods)

    2006

  8. [16]

    O. E. Livne and A. Brandt,Lean algebraic multigrid (LAMG): fast graph Laplacian linear solver, SIAM J. Sci. Comput., 34 (2012), pp. B499–B522

    2012

  9. [17]

    O. E. Livne,LAMG+: A Robust Lean Algebraic Multigrid Solver for Graph Laplacians, arXiv:2606.24791, 2026. https://github.com/orenlivne/lamgplus

    2026 arXiv

  10. [18]

    Huang, H

    Q. Huang, H. He, A. Singh, S.-N. Lim, and A. R. Benson,Combining label propagation and simple models out-performs graph neural networks, in Int. Conf. Learning Representations (ICLR), 2021

    2021

  11. [19]

    Cheng, C

    Y. Cheng, C. Shan, Y. Shen, X. Li, S. Luo, and D. Li,Resurrecting label propagation for graphs with heterophily and label noise, in Proc. 30th ACM SIGKDD Conf. Knowledge Discovery and Data Mining (KDD), 2024. arXiv:2310.16560

    2024 arXiv

  12. [20]

    W. Hu, M. Fey, M. Zitnik, Y. Dong, H. Ren, B. Liu, M. Catasta, and J. Leskovec,Open Graph Benchmark: datasets for machine learning on graphs, in Adv. Neural Inf. Process. Syst. (NeurIPS) 33, 2020

    2020

Pith tools

Reviewed July 12, 2026 · model on record in the stance chip above.