{"id":"e2a57d44-1eb7-4d22-891a-a9196c12ffeb","arxiv_id":"2607.03503","paper_version":1,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":6.0,"correctness_risk":"low","formal_verification":"none","parameter_count":4,"one_line_summary":"p-Laplacian SSL recast as a nonlinear Laplacian flow and solved by damped chord-Newton continuation in p yields empirically near-linear wall-clock and web-scale graphs while fixing p=2 low-label collapse.","lead":"A new solver makes nonlinear p-Laplacian label propagation practical on graphs with tens of millions of edges by pairing continuation in p with near-linear Laplacian engines. This removes the memory wall that kept the statistically better low-label method stuck at small graphs.","discovery_kind":"new_method","skeptic_critique":{"model":"grok-4.5","headline":"No significant objection identified beyond the paper's own caveats on empirical step count.","rationale":"The paper's central claim is an engineering one: recasting p-Laplacian SSL as NLF + damped chord-Newton continuation in p lets a near-linear Laplacian engine replace direct factorization without stagnation, producing a practical solver that is empirically O(m) at fixed type, memory-feasible far beyond the factorization wall, and 1.5–14\times faster than released FCL at matched accuracy while realizing the low-label fix. The reduction (Prop. 2.1), ε-floor (Jacobian only), and Appendix A global-convergence argument are standard and internally consistent. The only soft spot is exactly the one the reader named—unproved flat step count—and the authors already list it under Limitations. Because the claim is framed as empirical near-linearity (with AC's O(m log^{3} n) guarantee conditional on that count) rather than a proved complexity theorem, the caveat does not overturn the evidence in Tables 5.1–5.5, Figs. 5.1–5.2, or the MNIST/ogbn-products results. Code is public. No stronger load-bearing concern (e.g., incorrect reduction, floor altering the fixed point, or non-reproducible scaling) appears. Verdict remains ACCEPT; confidence stays high.","tokens_in":18943,"tokens_out":681,"duration_ms":5471,"concrete_test":"On the controlled Delaunay and RGG families of Table 5.1, re-run the full p=2\to3 continuation with Anderson acceleration disabled and record chord-Newton steps vs. m; if steps remain flat (≤16) and wall-clock exponents stay ≤1.05, the load-bearing empirical O(1) holds without the guard on the families that support the O(m) claim. (The single stiff corpus graph can be checked separately.)","verdict_should_be":"UNCHANGED","load_bearing_attack":"The reader's weakest_assumption correctly flags that total near-linear complexity rests on an unproved O(1) outer chord-Newton step count (median 11, ≤50 on 228 graphs), restored on the stiffest case only by guarded Anderson acceleration with no step-count bound (§3.4, §6). That is a genuine limitation of the asymptotic claim, but it is already stated by the authors and does not undermine the central engineering claim as written: the damped continuation keeps linearized systems well-conditioned enough for a near-linear engine to replace factorization, yielding empirically near-linear wall-clock at fixed graph type, memory-feasible solves at 6.8e7 edges, and matched-accuracy speedups over released FCL. Global convergence of the outer iteration itself is proved self-contained in Appendix A from strict convexity (Prop. 2.1) under a fixed forcing tolerance; only the rate/step count is empirical. No hidden inconsistency in the reduction, floor, or continuation was found that would falsify the reported results.","agreement_with_reader":"agree"},"referee_report":{"model":"grok-4.5","summary":"The paper recasts graph p-Laplacian semi-supervised learning as a source-form nonlinear Laplacian flow B ρ_p(B^\top 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.","tokens_in":19160,"tokens_out":1379,"duration_ms":21265,"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":[{"comment":"§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.","section":null},{"comment":"§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.","section":null}],"minor_comments":[{"comment":"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.","section":null},{"comment":"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.","section":null},{"comment":"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.","section":null},{"comment":"§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.","section":null},{"comment":"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.","section":null}],"recommendation":"minor_revision","confidential_remarks":"The manuscript imports the NLF outer machinery and LAMG+ from the author’s concurrent arXiv preprints, but Appendix A re-proves outer convergence from Proposition 2.1 alone and the empirical SSL results (MNIST, FCL head-to-head, corpus scaling) are independent measurements. Novelty disclosure is adequate. Fit for a numerical methods / scalable ML journal is good; the contribution is engineering-plus-analysis rather than new learning theory. I see no integrity or citation-pattern concerns."},"author_rebuttal":null,"desk_editor":{"model":"grok-4.5","letter":"Punchline: this closes a real gap. Variational p-Laplacian SSL was the statistically right tool at low labels and was stuck behind direct factorization. Livne shows how to keep the linearized systems well-conditioned enough that a near-linear Laplacian engine can replace the factor, and then measures that combination carefully.\n\nWhat is actually new is not continuation in p (FCL, Storn already do that) and not the NLF chord-Newton machinery (his concurrent work). It is (i) the grounded-node reduction that turns SSL into a verbatim NLF instance, (ii) the diagnosis that undamped near-linear inners stall when conductances floor near flat edges, and (iii) the empirical package: controlled family scaling, 228-graph corpus, head-to-head vs released FCL, and a 68M-edge LiveJournal solve in minutes. Prop. 2.1 and Appendix A are clean; global outer convergence is proved from strict convexity under a fixed forcing tolerance without leaning on the NLF paper. Code is public. MNIST and ogbn-products reproduce the low-label fix at scale.\n\nSoft spots, in proportion: total near-linear complexity rests on an empirical flat outer step count (median 11, ≤50), restored on the stiffest graph by guarded Anderson with no step-count bound. The authors say this in §6; it weakens the asymptotic slogan, not the engineering claim as written. Pooled m^1.19 is a mixed-class fit; per-family numbers are the honest ones. FCL speedups partly mix Julia vs MATLAB, and that comparison stops around 3e5 edges—again flagged. Free parameters (ε-floor, p-schedule multiplier, inner tol) are standard and not load-bearing for the fixed point.\n\nWho this is for: people who run or build large-scale label propagation, and anyone who needs p-Laplacian SSL past ~1e5 edges. Not a theory paper; a methods paper with honest caveats and reproducible numbers. I would send it to peer review. Worth engaging if you care about scalable graph SSL; the central claim holds up under the paper’s own stated limits.","headline":"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.","tokens_in":19829,"tokens_out":549,"would_cite":true,"duration_ms":8719,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["65F10","68T05","65N55","05C50","62H30","90C35"],"pacs":[],"model":"grok-4.5","headline":"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.","keywords":["semi-supervised learning","graph p-Laplacian","label propagation","algebraic multigrid","graph Laplacian","numerical continuation","inexact Newton methods"],"falsifier":"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.","tokens_in":19761,"feed_emoji":"⚡","tokens_out":970,"duration_ms":6995,"temperature":0.7,"pith_summary":"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).","feed_headline":"p-Laplacian SSL now runs in near-linear time past 68M edges","feed_subtitle":"Damped continuation keeps every linear solve well-conditioned, beating factorization memory walls","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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\to∞) 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\times 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."],"fun_headline_variants":["Near-linear p-Laplacian SSL via damped continuation past 68M edges","Source-form flow and p-continuation keep p-Laplacian SSL well-conditioned","p-Laplacian SSL scales near-linearly, handling 68M-edge networks in minutes","Chord-Newton continuation in p replaces direct factorization for SSL","Near-linear solver fixes low-label degeneracy for graph p-Laplacian SSL"],"cache_read_input_tokens":16512,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Near-linear p-Laplacian SSL via damped continuation past 68M edges","Source-form flow and p-continuation keep p-Laplacian SSL well-conditioned","p-Laplacian SSL scales near-linearly, handling 68M-edge networks in minutes","Chord-Newton continuation in p replaces direct factorization for SSL","Near-linear solver fixes low-label degeneracy for graph p-Laplacian SSL"]},"model":"grok-4.5","effort":"low","cost_usd":0.00516,"raw_usage":{"total_tokens":1580,"prompt_tokens":984,"num_sources_used":0,"completion_tokens":106,"cost_in_usd_ticks":51600000,"prompt_tokens_details":{"text_tokens":984,"audio_tokens":0,"image_tokens":0,"cached_tokens":256},"completion_tokens_details":{"audio_tokens":0,"reasoning_tokens":490,"accepted_prediction_tokens":0,"rejected_prediction_tokens":0}},"tokens_in":984,"tokens_out":106,"duration_ms":4282,"temperature":1.0,"reasoning_tokens":490,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-07-12T02:01:28.373166+00:00","model_set":{"reader":"grok-4.5"},"falsifier":"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.","supporting_citations":[],"review_version":1}