{"id":"4d3b3186-5943-43a2-bf02-436a5f1a99d8","arxiv_id":"2501.04570","paper_version":1,"verdict":"REJECT","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"high","formal_verification":"none","parameter_count":2,"one_line_summary":"SGNN-LS approximates dense multi-hop spectral filters with sparse random-walk graphs, enabling end-to-end training on 111M-node graphs, but the theory for negative filter coefficients has a gap.","lead":"A graph-learning research team proposes scaling up spectral graph neural networks by replacing dense multi-hop propagation with a sparse random sample of paths, called Laplacian sparsification. The method trains end-to-end on graphs with over 100 million nodes, but the proof that it preserves the filter's behavior is not valid as written for filters with negative coefficients.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The proof for learnable signed polynomial filters fails because per-hop eps-sparsifiers of nonnegative graphs do not combine into an eps-sparsifier of a signed sum; Loewner order and effective-resistance guarantees do not survive subtraction.","rationale":"The reader's weakest assumption identifies exactly the load-bearing flaw: Appendix A.1 treats independent per-hop eps-sparsifiers as composable into an eps-sparsifier of the signed polynomial. That step is not a theorem and is generally false because signed edge weights leave the domain of Laplacian sparsification, and Loewner order is incompatible with subtraction. I verified that the paper's own proof text in Appendix A.1 states the 'sufficient condition' without proving it, and that Theorem 3.2 is the basis for the headline theoretical contribution. The APPNP-specific loss bound in Theorem 4.4 has nonnegative coefficients and does not cover GPR-GNN-style signed learnable filters; the experiments do not repair the proof. I agree with the reader's REJECT recommendation because the central advertised guarantee is unsound as written. I would note that the empirical contribution, including reproduction on Ogbn-papers100M and MAG-scholar-C, is substantial and could support a revised paper that either restricts the theory to nonnegative coefficients or supplies a genuine cancellation-aware error bound for signed polynomials.","tokens_in":35429,"tokens_out":3949,"duration_ms":40506,"concrete_test":"On a small graph (e.g., a 100-node cycle or a 3-regular expander), fix K=2 and coefficients w0=1, w1=-2, w2=1 so that the target polynomial sum_k w_k P^k is PSD (e.g., proportional to (I-P)^2). Independently construct per-hop sparsifiers using Algorithm 1 with M = C n log n / eps^2 for eps=0.1, stack them with the signed weights, and compute the Rayleigh quotient ratio x^T \\tilde L_K x / x^T L_K x for x equal to the leading eigenvectors of L_K and for 10^4 random vectors. If any ratio falls outside [1-eps, 1+eps], or equivalently the generalized eigenvalue range is violated, the stacked signed construction is not an eps-sparsifier, contradicting the Appendix A.1 sufficient condition. Repeat with w0=1, w1=1, w2=-1 to confirm that the failure depends on the sign pattern rather than on the specific polynomial.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim for learnable coefficients rests on Appendix A.1, which asserts that if each hop graph D(D^{-1}A)^k is replaced by an eps-sparsifier, then stacking these sparsifiers with coefficients w_k yields an eps-sparsifier of sum_k w_k D(D^{-1}A)^k. This inference is invalid. Spectral sparsification is defined for weighted graphs with nonnegative edge weights; once w_k contains both signs, the stacked object has signed edge weights, is not a graph Laplacian, and the effective-resistance sampling guarantee (Theorem A.1) does not apply. Loewner order is not preserved under linear combinations with mixed signs: from (1-eps)L_i <= \\tilde L_i <= (1+eps)L_i for each i it does not follow that (1-eps) sum_i w_i L_i <= sum_i w_i \\tilde L_i <= (1+eps) sum_i w_i L_i unless all w_i >= 0 and the relevant matrices are ordered compatibly. With signed coefficients, per-hop errors can cancel or amplify, and unbiasedness alone supplies no spectral similarity bound. Theorem 4.4 is proven only for APPNP with nonnegative coefficients, so it does not rescue the learnable case. Additionally, Equation (2) identifies L^k with (-P)^k by absorbing the negative sign into w_k, but for the normalized Laplacian L = I - P one must re-expand (I-P)^k in the P basis; as written, the coefficient mapping is not consistently defined. The empirical results are extensive and the method may work in practice, but the advertised theoretical guarantee for fixed and learnable filters is unsupported for signed learnable coefficients.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes SGNN-LS, a Laplacian sparsification method for approximating the propagation matrix of spectral GNNs, enabling end-to-end training without detaching the linear layers from the graph propagation. The authors claim to construct an epsilon-sparsifier of the polynomial filter sum_k w_k L^k with O(n log n / epsilon^2) edges and probability at least 1-K/n, for both static and learnable coefficients w. They validate the approach empirically on datasets ranging up to Ogbn-papers100M (111M nodes) and MAG-scholar-C (2.8M features), reporting accuracy competitive with or better than the corresponding base models.","tokens_in":35801,"tokens_out":4668,"duration_ms":46463,"significance":"If the theoretical guarantee were valid, this would be a valuable contribution: it would allow spectral GNNs with learnable polynomial filters to be trained end-to-end on very large graphs, avoiding the detached precomputation that limits existing scalability tricks. The empirical study is extensive, covers diverse homophilous and heterophilous datasets, and includes a code release, which are strengths. However, the central theorem for learnable signed coefficients is not established; the proof relies on an invalid combination of per-hop sparsifiers. This leaves the spectral guarantee only for nonnegative coefficient polynomials (e.g., APPNP), while the method's headline application, GPR-GNN, uses signed coefficients. The paper would need a substantially weakened claim to be correct, which changes its main contribution.","major_comments":[{"comment":"The claim that GLSGC produces an epsilon-sparsifier of sum_k w_k D(D^{-1}A)^k for signed coefficients w is unsupported. The argument that 'a sufficient condition is that all generated K sparsifiers are eps-sparsifiers' is invalid because Loewner order is not preserved under linear combinations with mixed signs: from (1-eps)L_i <= \\tilde L_i <= (1+eps)L_i for each hop i it does not follow that (1-eps) sum_i w_i L_i <= sum_i w_i \\tilde L_i <= (1+eps) sum_i w_i L_i when the w_i have different signs. Moreover, the stacked object has signed edge weights and is not the Laplacian of a nonnegative-weight graph, so the effective-resistance sampling guarantee in Theorem A.1 does not apply. The proof establishes only unbiasedness of the stacked approximation, not spectral similarity, so Theorem 3.2 is not proved for learnable coefficients.","section":"Section 3.2.2 and Appendix A.1"},{"comment":"The identification L^K = sum_k w_k L^k approx sum_k w_k P^k is not a valid coefficient-wise mapping because L = I - P, so L^k = sum_{j=0}^k binom(k,j)(-1)^j P^j. 'Absorbing the negative sign into the coefficients w_k' changes the coefficient vector in a way that is never specified; the new coefficients of P^j would be sums over k of w_k binom(k,j)(-1)^j, not the original w_j. This basis mismatch means the polynomial in P that is actually sparsified is not shown to be the same as the intended polynomial in L, which undermines the theoretical analysis for both static and learnable filters.","section":"Equation (2)"},{"comment":"The proof of Theorem 4.4 contains algebraic steps that do not follow. From the displayed identity x^T (f + \\tilde f) L \\Delta x, the line x^T(f+\\tilde f)L\\Delta x / x^T f^T L f x = 2 x^T f L \\Delta x / (x^T f L f x - x^T \\Delta L \\Delta x) is not justified; substituting \\tilde f = f - \\Delta gives (f + \\tilde f) = 2f - \\Delta, not an equality of denominators. In addition, the proof asserts the Loewner orderings (1-eps)(I-f) <= I - \\tilde f <= (1+eps)(I-f) directly from the sparsifier condition, but it has not been shown that an epsilon-sparsifier of the random-walk polynomial D sum_k w_k (D^{-1}A)^k yields those inequalities for f(P,K) and \\tilde f(P,K). The claim that the relative loss error is O(epsilon) is therefore not rigorously established.","section":"Appendix A.3"}],"minor_comments":[{"comment":"The phrase 'The scalability' at the start of the second sentence should be 'the scalability', and 'Spectral Graph Neural Networks' is inconsistently capitalized across the abstract and body.","section":"Abstract"},{"comment":"The expression 'our desiring matrix L_K' should read 'the desired matrix L_K'.","section":"Section 3.2"},{"comment":"The caption contains the typos 'sparsification' and 'spasified'; these should be corrected.","section":"Figure 1 caption"},{"comment":"The self-loop (v,v) with weight w0 is added to every node, but the edge count and the unbiasedness analysis for this zero-hop term are not discussed; please clarify how this is consistent with the O(n log n / eps^2) edge bound.","section":"Algorithm 5"},{"comment":"The statement 'We have extended the original theorem proposed by [8] to accommodate non-normalized polynomial coefficients w' is only true for w in the nonnegative orthant; the paper should state this limitation explicitly where the theorem is introduced.","section":"Theorem 3.2"}],"recommendation":"reject","confidential_remarks":"The paper's empirical work is substantial and the scale of the experiments is commendable, but the advertised theoretical guarantee for learnable signed polynomial filters is the core selling point and it is invalid as written. The flaw in Appendix A.1 is not a minor gap; it is a false inference that cannot be repaired without changing the main claim of the paper. I would recommend rejection, though a future version that restricts the spectral guarantee to nonnegative coefficients and treats the signed case purely as an unbiased approximation with empirical support could be reconsidered."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: the paper has a genuinely useful plug-and-play approach for training spectral GNNs on huge graphs, and the experiments are serious—100M-node graphs, 2.8M features, code released. But the central theoretical guarantee advertised in the abstract is not established. The proof in Appendix A.1 assumes that if you independently sparsify each hop D(D^-1 A)^k and stack with coefficients w_k, you get an eps-sparsifier of the signed sum. That's true only when all w_k are nonnegative. Loewner order doesn't survive subtraction; once any coefficient is negative the stacked object has signed edge weights, isn't a graph Laplacian, and the effective-resistance guarantee (Theorem A.1) doesn't apply. Unbiasedness alone gives you no spectral similarity bound. So the proof for GPR-GNN-style learnable filters is invalid.\n\nThere's also a smaller issue in Eq (2). You can't just replace L with P and absorb the minus sign into w_k. L^k = (I-P)^k needs to be re-expanded in the P basis; the coefficient mapping is not a one-for-one flip. This matters if you want to make the polynomial identity exact before sparsifying.\n\nTo be fair, the paper does other things well. The node-wise sampling scheme for semi-supervised tasks is a nice adaptation, and the experimental evaluation is extensive and reproducible—they actually trained GPR-LS and APPNP-LS on Ogbn-papers100M and MAG-scholar-C, which is not trivial. The fact that the LS variants often match or beat the base models is an interesting empirical finding even without the proof. For the static APPNP case, all the coefficients are nonnegative, so a version of the theory likely goes through; the paper just overgeneralizes.\n\nBottom line: this is a serious research effort with a real flaw in the load-bearing theorem. It deserves a referee who can push for the theory to be fixed or restricted, and who can ask the authors to clarify Eq (2). As is, I wouldn't cite the main theorem, but I'd point someone to the empirical results and the node-wise sampler. Bring it to a reading group if you want to discuss what counts as a valid spectral sparsifier for signed graphs.","headline":"Real scalability idea and strong experiments, but the proof for signed learnable filters is unsound; needs major revision before it can be a trustworthy reference.","tokens_in":36299,"tokens_out":3135,"would_cite":false,"duration_ms":31024,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper claims that the K-hop propagation of spectral GNNs can be replaced by one pass of message passing on an $O(n\\log n/\\varepsilon^2)$-edge Laplacian sparsifier with spectral error $\\varepsilon$, enabling end-to-end training on…","keywords":["spectral graph neural networks","Laplacian sparsification","random-walk matrix polynomials","effective resistance sampling","graph scalability","polynomial filters","node classification","semi-supervised learning"],"falsifier":"The decisive check is numerical: pick a small graph, fix a coefficient vector $w$ with both signs, use the paper's construction at the certified edge budget, and test the defining inequality $(1-\\varepsilon)L \\preceq \\tilde{L} \\preceq (1+\\varepsilon)L$ on random signals $x$ (equivalently, compute the largest $|x^{\\top}(L-\\tilde{L})x|/x^{\\top}L x$ over sampled $x$). If the stacked sparsifier $\\tilde{L}$ violates the bound while every per-hop sparsifier satisfies its own, the stacking step in Appendix A.1 is refuted and the polynomial-level guarantee does not follow from the per-hop ones; the estimator's unbiasedness would survive, but the claimed spectral error bound would not.","tokens_in":35203,"feed_emoji":"🕸️","tokens_out":13940,"duration_ms":120371,"temperature":0.7,"pith_summary":"This paper claims that the multi-hop propagation step of a spectral graph neural network — applying a polynomial filter $\\sum_{k=0}^{K} w_k L^k$ to node features — can be replaced by a single round of message passing on a sparse surrogate graph built by random-walk edge sampling. The surrogate is a Laplacian sparsifier with $O(n\\log n/\\varepsilon^2)$ edges that the paper proves approximates the full polynomial filter to spectral error $\\varepsilon$ with probability at least $1-K/n$, for fixed coefficients and for coefficients learned during training. If correct, spectral GNNs such as GPR-GNN, APPNP, and JacobiConv become trainable end-to-end on graphs with hundreds of millions of nodes and features with millions of dimensions — regimes where they currently exhaust GPU memory or are forced into the 'detach propagation from training' trick. The paper supports the claim with an error analysis of the propagated signal and with experiments reaching OGB-papers100M (111M nodes, 1.6B edges) and MAG-scholar-C (2.8M feature dimensions), where the sparsified models match or beat their exact counterparts.","feed_headline":"One sparse pass now trains spectral GNNs on 111M nodes","feed_subtitle":"K-hop polynomial filters compress into O(n log n) edges while keeping end-to-end training and raw-text features.","key_machinery":"The load-bearing object is the random-walk matrix polynomial sparsifier produced by Algorithm 1: to approximate a single hop matrix $D(D^{-1}A)^{k}$, sample one edge uniformly, split the walk length $k$ into two parts, extend random walks of those lengths from the two endpoints, and repeat $M$ times; each sampled path becomes an edge weighted by $m/M$ times the endpoint degree-normalization ($d_u^{-1/2}d_v^{-1/2}$), with sign and norm corrections ${\\rm sgn}(w_k)\\lVert w\\rVert_1$ for static coefficients or plain $w_k$ for learnable ones. Because a length-$k$ random-walk path has effective resistance bounded by a constant $2k$, the sampled set is an unbiased $\\varepsilon$-sparsifier of that hop, and Theorem 3.2 (an extension of the random-walk polynomial sparsification theorem) certifies the $O(n\\log n/\\varepsilon^2)$ edge count and $1-K/n$ probability. Learnable coefficients are handled hop-by-hop so the sampled edge weights carry the gradient of each $w_k$; Theorem 4.4 then transfers the spectral guarantee to training, bounding the relative error of the APPNP-style loss $\\mathcal{L}(z)=(1-\\alpha)\\operatorname{Tr}(z^{\\top}L z)+\\alpha\\lVert z-x\\rVert_F^2$ by $O(\\varepsilon)$.","core_discovery":"The central claim is that the entire propagation pattern of a spectral GNN — the matrix polynomial $\\sum_{k=0}^{K} w_k D^{-1/2}(D^{-1}A)^{k}D^{-1/2}$, with signs absorbed into $w_k$ — admits a spectral sparsifier that can be sampled directly by random walks on the original graph, never materializing a dense hop matrix. Encoding the magnitude and sign of each coefficient into sampled edge weights, the construction yields an $\\varepsilon$-sparsifier with $O(n\\log n/\\varepsilon^2)$ edges and success probability at least $1-K/n$, for static coefficients (SLSGC) and for learnable coefficients (GLSGC, which samples each hop independently so that gradients reach every $w_k$). A node-wise variant samples only walks starting from training nodes, making semi-supervised training compatible with mini-batching. The consequence the paper draws is that one round of message passing on the sparse graph reproduces the effect of $K$ rounds on the original graph while keeping the linear feature layers inside the training loop, so graphs that previously caused out-of-memory failures become trainable.","pith_inferences":["The sparsified models' small but consistent gains over exact propagation, together with the paper's observation that more sampling does not always help, suggest the random-walk sampling acts as a stochastic regularizer that drops unreliable long-range paths; a testable consequence (not tested in the paper) is that this advantage should shrink when noisy links are artificially removed from the grap","The sampler is an anytime estimator of personalized-PageRank-style propagation matrices, so the same machinery could replace the expensive precomputation step in any algorithm that needs a PPR or polynomial-filter matrix once per query or per epoch, beyond the GNN training loop studied here.","GLSGC's hop-by-hop independence inflates the edge budget by a factor of K relative to SLSGC, so a joint sampling scheme that reuses walk prefixes across hops while keeping gradient flow to each w_k should close the gap; the paper's own ablation (good results at 'ec' between 1 and 10) suggests the theoretical bound is far from tight in practice."],"forward_implications":["Spectral GNNs with fixed filters (APPNP) and learnable filters (GPR-GNN, JacobiConv, FavardGNN) train in a single propagation pass per epoch, with memory proportional to the mini-batch instead of the full graph, so 111M-node graphs fit on one GPU.","End-to-end training survives: the linear layers stay coupled to propagation, so dimensionality reduction and raw text features (2.8M dimensions on MAG-scholar-C) are handled by the model rather than by preprocessing.","The approximation error transfers to the optimization target: for APPNP-style models the relative error of the training loss between exact and sparsified propagation is O(epsilon), so the edge-budget hyperparameter 'ec' tunes the training bias predictably.","Per-epoch cost drops from K full graph propagations to one pass over O(n log n / epsilon^2) sampled edges, and the node-wise variant computes only propagation rows touching training nodes, which is what makes semi-supervised training on OGB-papers100M feasible.","In the reported experiments the sparsified variants match or exceed their exact counterparts across homophilous and heterophilous graphs, with the largest gain on the heterophilous network Penn94 (GPR-LS improves on GPR-GNN by +2.08 accuracy points)."],"supporting_citations":[{"why":"Supplies the random-walk matrix polynomial sparsification theorem that Theorem 3.2 extends to non-normalized coefficients w.","marker":"[8]"},{"why":"Provides the effective-resistance sampling algorithm (Algorithm 2) into which the paper's random-walk path sampling plugs.","marker":"[43]"},{"why":"Defines spectral similarity and the O(n log n / epsilon^2)-edge sparsifier guarantee that the construction inherits.","marker":"[45]"},{"why":"GPR-GNN, the main learnable-coefficient spectral model whose propagation GLSGC sparsifies and evaluates against.","marker":"[11]"},{"why":"APPNP, the static-coefficient model that anchors Theorem 4.4's propagated-signal loss analysis and the APPNP-LS experiments.","marker":"[27]"},{"why":"Prior approximation of random-walk matrix polynomials that motivates the hop-by-hop sampling view of the propagation matrix.","marker":"[36]"}],"fun_headline_variants":["Spectral GNNs scale via one sparse Laplacian pass","111M nodes: spectral GNNs now trainable with sparsified Laplacians","Sparse Laplacian enables end-to-end spectral GNNs at scale","Train spectral GNNs on 111M nodes with a single sparse pass"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise, asserted in Appendix A.1, is that if each hop matrix $D(D^{-1}A)^k$ has its own sparse approximation with error $\\varepsilon$, then stacking those approximations with the signed coefficients $w_k$ gives an $\\varepsilon$-sparsifier of the whole polynomial $\\sum_k w_k L^k$ — a step that assumes closeness under subtraction, which the underlying effective-resistance guarantee does not by itself establish.","fun_headline_variants_meta":{"raw":{"variants":["Spectral GNNs scale via one sparse Laplacian pass","111M nodes: spectral GNNs now trainable with sparsified Laplacians","Sparse Laplacian enables end-to-end spectral GNNs at scale","Train spectral GNNs on 111M nodes with a single sparse pass"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00038,"raw_usage":{"total_tokens":2077,"prompt_tokens":1066,"completion_tokens":1011,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":682,"completion_tokens_details":{"reasoning_tokens":927}},"tokens_in":682,"tokens_out":1011,"duration_ms":9382,"temperature":1.0,"reasoning_tokens":927,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-10T21:30:24.131808+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"The decisive check is numerical: pick a small graph, fix a coefficient vector $w$ with both signs, use the paper's construction at the certified edge budget, and test the defining inequality $(1-\\varepsilon)L \\preceq \\tilde{L} \\preceq (1+\\varepsilon)L$ on random signals $x$ (equivalently, compute the largest $|x^{\\top}(L-\\tilde{L})x|/x^{\\top}L x$ over sampled $x$). If the stacked sparsifier $\\tilde{L}$ violates the bound while every per-hop sparsifier satisfies its own, the stacking step in Appendix A.1 is refuted and the polynomial-level guarantee does not follow from the per-hop ones; the estimator's unbiasedness would survive, but the claimed spectral error bound would not.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"GPR-GNN, the main learnable-coefficient spectral model whose propagation GLSGC sparsifies and evaluates against."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"APPNP, the static-coefficient model that anchors Theorem 4.4's propagated-signal loss analysis and the APPNP-LS experiments."}],"review_version":1}