{"id":"d0bd0c3a-a134-42f3-8f2a-80bf83d7572b","arxiv_id":"2506.16110","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":4,"one_line_summary":"GOKU improves GNN accuracy by reconstructing a denser latent graph and then spectrally sparsifying it, preserving the original spectrum and edge count while improving connectivity.","lead":"This paper introduces GOKU, a graph rewiring method that adds bottleneck-reducing edges and then sparsifies back to the original edge count while keeping the Laplacian spectrum close to the input graph. It targets over-squashing in graph neural networks, and reports accuracy gains over six existing rewiring baselines on ten datasets.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The spectrum-preservation guarantee depends on the unverified assumption that the heuristic latent graph Gl is spectrally similar to G; Theorem 4.1 only proves a pointwise bound for one fixed vector, so the transitivity argument Go ≈ Gl ≈ G is not supported.","rationale":"The reader's weakest assumption correctly identifies the key gap: the assertion that the observed graph G is a spectral sparsifier of the reconstructed latent graph Gl. My independent reading of the manuscript confirms this. Section 3.1 makes the assertion without proof, and Section 4.1's construction of Gl is explicitly heuristic, using a restricted candidate set, uniform weights, an approximate MLE, and an edge-count formula (Eq. 12) based on uniform sampling that is inconsistent with Algorithm 1's nonuniform probabilities. The theorem offered as justification, Theorem 4.1, is stated and proved only for a fixed vector x, not uniformly over all x, so it cannot yield the spectral similarity relation required for transitivity. I also independently noticed the direction error in Eq. (9) of Appendix D.2, though the subsequent use of the corrected inequality suggests it is a typographical slip rather than a fundamental flaw in the ER-based sparsification argument. The empirical work is a real contribution: the method is clearly specified, the experiments span ten datasets and three backbone architectures, and the gains on heterophilic node classification are large and consistent across baselines. The visualizations and effective-resistance measurements provide indirect evidence that the heuristic preserves useful spectral structure in practice. However, the paper's strongest theoretical claim, that GOKU provably preserves the spectrum, is not supported by the supplied proofs and construction. Therefore the appropriate disposition remains CONDITIONAL: the method may be practically useful and worth publishing as an empirical technique, but the spectrum-preservation guarantee must be either rigorously proven for the actual Gl construction, empirically verified via direct G-to-Gl spectral similarity measurements on the reported datasets, or explicitly downgraded to a heuristic property.","tokens_in":22678,"tokens_out":5658,"duration_ms":55962,"concrete_test":"Run the public GOKU implementation on the Texas dataset (or another heterophilic graph) with the paper's default settings (ϵ=0.1, α as selected in the paper). After constructing Gl exactly as in Section 4.1, compute the spectral similarity factor between G and Gl using the generalized eigenvalue problem restricted to the subspace orthogonal to the all-ones vector: σ = max_{x⊥1} |x^T L_G x − x^T L_Gl x| / x^T L_Gl x. If σ exceeds 1.1 (or even the compounded factor (1.1)^2 = 1.21), then G is not a (1±0.1)-spectral sparsifier of Gl, and the transitivity argument for spectrum preservation does not hold. Additionally, simulate q draws from Algorithm 1's actual nonuniform distribution on the constructed Gl, count the number of distinct edges, and compare this count with the prediction of Eq.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim of the paper is that GOKU preserves the Laplacian spectrum from the input graph G to the output graph Go through the transitivity Go ≈ Gl and Gl ≈ G. Section 3.1 asserts 'Since G is a spectral sparsifier of Gl' immediately after defining Gl as the maximum likelihood solution. In the actual construction (Section 4.1), Gl is obtained empirically: candidate edges are restricted to 4j nodes chosen by Fiedler magnitude and degree, edge weights are forced to be uniform, the MLE objective is replaced by an independent-edge product approximation (Eq. 3), and the edge-count estimate |El| is derived from Eq. (12) under a uniform sampling model that contradicts Algorithm 1's nonuniform sampling probabilities pe ∝ (deg(u)+deg(v)+1)/|fu−fv|. No step verifies that G is a (1±ϵ)-spectral sparsifier of the Gl that is actually built. The theorem cited for densification, Theorem 4.1, does not supply a spectral sparsification guarantee: it bounds the quadratic form for a single fixed vector x with probability at least 3/4, and the required number of samples q depends on κ(x) for that vector. Spectral similarity requires the inequality to hold uniformly over all x, which is not established anywhere. The proof of Theorem 4.2 also contains a reversed inequality in Eq. (9): with pe ∝ (1+Se)Re, the correct lower bound is pe ≥ Re/(2(n−1)), not pe ≤ Re/(2(n−1)); the subsequent norm bound in the proof uses the correct direction, so this is likely a typo rather than a fatal flaw, but it further shows the appendix was not carefully checked. Because the transitivity claim loses its premise if G is not spectrally similar to Gl, the advertised 'spectrum-preserving' guarantee is currently a heuristic property supported only by visualizations and effective-resistance measurements, not by proof.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes GOKU, a graph rewiring method for mitigating over-squashing in GNNs. GOKU instantiates a densification-sparsification rewiring (DSR) paradigm: it treats the input graph G as a spectral sparsifier of a latent graph Gl, reconstructs Gl by an inverse-sparsification maximum-likelihood procedure, and then applies an effective-resistance-based spectral sparsifier to obtain a sparse output graph Go. The central theoretical claim is that the composition preserves the Laplacian spectrum: since both G and Go are spectral sparsifiers of Gl, transitivity gives Go ≈ Gl ≈ G. The paper reports experiments on ten datasets for node and graph classification, comparisons against six rewiring baselines with GCN, GIN, and GCNII backbones, spectral visualizations, ablations, and complexity analysis. The authors also provide code and claims near-linear-time operation.","tokens_in":23004,"tokens_out":9125,"duration_ms":96221,"significance":"If the central claims were established, this would be a noteworthy contribution: DSR appears to be a novel paradigm that explicitly targets the tension between connectivity improvement, sparsity, and spectral fidelity, and the experimental evaluation is broad and carefully reported. The paper has clear strengths: extensive experiments with multiple backbones and baselines, reproducible code, ablation studies, spectral visualizations, and a transparent discussion of hyperparameter sensitivity. However, the central spectrum-preservation guarantee is not currently supported: the key transitivity step relies on an unverified assumption, and the main theorem proved for densification is only a pointwise statement for a fixed vector. The empirical results may still be valuable, but the theoretical framing overstates what is established.","major_comments":[{"comment":"The central transitivity argument Go ≈ Gl and Gl ≈ G → Go ≈ G rests on the sentence 'Since G is a spectral sparsifier of Gl', which is asserted as fact immediately after Gl is defined as the maximum-likelihood solution. The actual Gl constructed in Section 4.1 is obtained from a heuristic candidate-set construction (2j nodes by Fiedler magnitude and 2j by degree), uniform edge weights, an approximate independent-edge MLE objective (Eq. 3), and an edge-count estimate from Eq. (12). No step verifies that G is a (1±ε)-spectral sparsifier of the Gl that is actually built. Without this premise, the transitivity argument loses its left leg and the spectrum-preservation guarantee collapses. The authors should either prove that the constructed Gl is spectrally similar to G, verify it numerically for their datasets, or explicitly weaken the claimed guarantee.","section":"Section 3.1 (Combination)"},{"comment":"Theorem 4.1 does not prove that Algorithm 1 yields spectral sparsifiers. The proof bounds |x^T L̃x - x^T Lx| for a single fixed vector x, with probability at least 3/4 and with the required number q depending on κ(x) for that specific vector. Spectral similarity as defined in Definition 2.1 requires the inequality to hold uniformly for all x ∈ R^n. No epsilon-net argument or union bound is supplied, so the uniform statement is not established. Moreover, κ(x) can be unbounded as p_min → 0, and the probability 3/4 is not a high-probability guarantee. This is a load-bearing gap for the claim that densification 'provably produces spectral sparsifiers'.","section":"Appendix D.1 / Theorem 4.1"},{"comment":"The inequality in Eq. (9) has the incorrect direction. With p_e ∝ (1+S_e)R_e and S_e ∈ [0,1], the correct bound is p_e ≥ R_e / (2(n−1)), not p_e ≤ R_e / (2(n−1)). The subsequent proof uses the lower bound on p_e to upper-bound ||y||₂; with the printed inequality, the bound ||y||₂ ≤ √(2(n−1)) does not follow. This is likely a typo rather than a fatal error, because the norm bound in the proof uses the correct direction, but it must be fixed for the proof of Theorem 4.2 to be valid.","section":"Appendix D.2, Eq. (9)"},{"comment":"There is a mismatch between the theorem and the practical algorithm regarding the stopping rule. Section 4.2 states that 'We sample edges until β|E| distinct edges are selected', and the hyperparameter description repeats this ('we keep sampling until β|E| distinct edges are sampled'). However, Algorithm 2 and Algorithm 3 sample exactly q edges with replacement, and Theorem 4.2 guarantees spectral approximation for this fixed-q with-replacement procedure. Adaptive sampling until a fixed number of distinct edges is a stopping rule that changes the sampling distribution, and no argument is provided that it preserves the guarantees of Theorem 4.2. The algorithm, theorem, and implementation description should be aligned.","section":"Section 4.2 / Algorithms 2 and 3"},{"comment":"The derivation of |El|, the number of edges in the latent graph, is inconsistent with the USS sampling distribution. Eq. (12) determines |El| by assuming a uniform edge sampling model, x(1 − (1 − 1/x)^q) = |E|, but Algorithm 1 samples edges nonuniformly with p_e ∝ (deg(u)+deg(v)+1)/|f_u − f_v|. Consequently, the claim in Section 3.2 that the number of added edges is 'derived from a well-established theoretical result rather than being a heuristically chosen value' is not supported as stated. Additionally, the p_e values in Eq. (3) are defined over the latent graph Gd, which is unknown; the practical computation appears to substitute quantities from G without justification. These approximations should be acknowledged explicitly or replaced by a consistent derivation.","section":"Section 4.1 / Appendix E"}],"minor_comments":[{"comment":"The sampling probability p_e ∝ (deg(u)+deg(v)+1)/|f_u − f_v| can have a zero denominator when f_u = f_v, and the Fiedler vector is not uniquely defined when the graph is disconnected. The paper does not discuss how these cases are handled.","section":"Algorithm 1"},{"comment":"The text says '0.5 < β ≤ 1' in one place and 'β ∈ [0.5, 1.0]' in the hyperparameter description; these are inconsistent.","section":"Section 4.2"},{"comment":"The caption and table labels describe the graph scales as '20 edges', '245 edges', and '80352 edges', while the text refers to graphs with 20, 200, and 2000 nodes; the relationship between the node count and the edge-count labels should be clarified.","section":"Table 5 / Figure 3"}],"recommendation":"major_revision","confidential_remarks":"The experimental effort and the proposed paradigm are valuable, but the paper's central theoretical claim is not currently established. If the authors can replace Theorem 4.1 with a genuine uniform spectral guarantee, or if they can clearly reframe the spectrum-preservation statement as an empirical property of a heuristic with supporting verification on their datasets, then the contribution could be acceptable. As it stands, the transitivity argument Go ≈ Gl ≈ G is built on an unverified assumption, so the theoretical framing overclaims relative to what is proved."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The short version: GOKU is a genuinely new rewiring approach with strong empirical results, but the paper's central claim that it provably preserves the Laplacian spectrum does not hold together. If you use it, treat spectrum preservation as a heuristic property supported by experiments, not as a theorem.\n\nWhat is actually new: the DSR paradigm—treating the input graph as a sparsifier of a latent densified graph, reconstructing that latent graph via an inverse sparsification MLE, then sparsifying again. That framing is absent from the rewiring literature the paper cites. GOKU is a concrete instance with pseudocode, a code link, and nearly linear-time complexity. The experiments are extensive: ten datasets, three backbones, six baselines. The gains on heterophilic node classification (Texas, Cornell, Wisconsin) are large and consistent, and the ablations show both densification and sparsification contribute. The spectral visualizations and effective-resistance reductions are plausible supporting evidence. Citation pattern looks fine; the relevant sparsification and rewiring works are covered.\n\nSoft spots. Theorem 4.1, supposedly showing the USS step produces spectral sparsifiers, only proves a pointwise bound for one fixed vector x, with q depending on κ(x). Spectral similarity requires the bound to hold uniformly over all x; no epsilon-net or union bound is provided. So the theorem, as written, does not support the claim. Theorem 4.2 is the standard effective-resistance sparsification with a feature-similarity twist and probably goes through, but the proof in Appendix D.2 contains a reversed inequality in Eq. (9): with pe ∝ (1+Se)Re, the correct lower bound is pe ≥ Re/(2(n−1)), not ≤. The next line uses the correct direction, so it is likely a typo, but it suggests the appendix was not carefully checked.\n\nThe more serious problem is the transitivity argument. Section 3.1 says \"Since G is a spectral sparsifier of Gl\" immediately after Gl is defined as the MLE solution. In practice, Gl is built from a heuristic candidate set (Fiedler magnitude and degree), uniform edge weights, an approximate MLE objective, and Eq. (12) assumes a uniform sampling model that contradicts Algorithm 1's nonuniform pe. No step verifies that G is spectrally similar to the Gl actually constructed. Without that, the chain Go ≈ Gl ≈ G loses its left leg. The empirical evidence suggests the heuristic works, but it is not a proof.\n\nWho this is for: people working on graph rewiring for GNNs, especially heterophilic node classification. GOKU is usable as a baseline even if you ignore the theory. The paper deserves a serious referee—the empirical contribution and the DSR idea are worth engaging—but the authors should either repair the proof or explicitly downgrade the guarantee to a heuristic property. If I were the editor, I would send it out with that request.","headline":"GOKU's densification-sparsification idea is fresh and the experiments are strong, but the spectrum-preservation guarantee rests on an unproved transitivity step and a pointwise-only bound.","tokens_in":23664,"tokens_out":3192,"would_cite":true,"duration_ms":31533,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C50","68R10"],"pacs":[],"model":"deepseek-v4-flash","headline":"GOKU rewires graphs to reduce over-squashing bottlenecks while keeping the Laplacian spectrum nearly unchanged, by first densifying through inverse spectral sparsification and then sparsifying back to the original edge density.","keywords":["over-squashing","graph rewiring","spectral sparsification","graph neural networks","Laplacian spectrum","effective resistance","densification-sparsification","heterophily"],"falsifier":"Compute, on a graph rewired by GOKU, the ratio |x^T L_{G_o} x − x^T L_G x| / x^T L_G x over many random vectors x, or the ordered eigenvalue differences, and check whether the values stay within the claimed (1±ε)^2 window; a consistent violation would refute the spectrum-preservation claim.","tokens_in":22372,"feed_emoji":"🕸️","tokens_out":5093,"duration_ms":42981,"temperature":0.7,"pith_summary":"This paper argues that graph rewiring for over-squashing does not have to sacrifice the graph's spectral fingerprint. It proposes a densification-then-sparsification paradigm (DSR): first add edges that an inverse sparsification process would identify as missing, then prune the densified graph with spectral sparsification. The paper's method, GOKU, claims the output graph is spectrally similar to the input because both are spectral sparsifiers of the same latent graph, while effective resistance between nodes drops and edge density stays equal. Experimental results on ten datasets are presented as evidence that this balance improves node and graph classification accuracy, especially on heterophilic graphs.","feed_headline":"Graph rewiring that cuts over-squashing without losing the spectrum","feed_subtitle":"GOKU densifies then sparsifies, so messages travel further at the original edge density.","key_machinery":"The central object is the Laplacian quadratic form x^T L x together with the (1±ε)-spectral similarity relation. The argument runs through two sampling-based sparsification algorithms: USS (Algorithm 1) assigns low sampling probability to edges that are crucial for connectivity, identified through the Fiedler vector, and ISS (Algorithm 2) samples edges with probability proportional to (1 + feature cosine similarity) × effective resistance. The transitivity statement Go ≈ Gl ≈ G is what carries the spectrum-preservation guarantee, and the same sparsification machinery defines the maximum-likelihood inverse problem solved to construct Gl.","core_discovery":"GOKU treats the input graph G as the observed output of an unimportance-based spectral sparsification applied to an unknown latent graph Gl, reconstructs Gl by maximum-likelihood estimation, then applies importance-based spectral sparsification to Gl to obtain the output graph Go. By transitivity of spectral similarity, Go ≈ Gl ≈ G, so the spectrum is explicitly preserved from G to Go. At the same time, densification adds edges with high topological significance (low Fiedler-vector difference and low degree), which lowers effective resistance, and sparsification removes edges with low effective resistance and low feature similarity, so Go is no denser than G.","pith_inferences":["A direct test would measure actual spectral distance between G and Go across all ten datasets; the paper mostly visualizes spectra on a few graphs, so the reader cannot yet confirm the claimed (1±ε)^2 bound empirically.","The transitivity guarantee depends on G being a spectral sparsifier of Gl, which is asserted rather than verified; checking that link empirically, for example by comparing quadratic forms on random test vectors, would confirm or break the argument.","The Fiedler-vector/degree heuristic for identifying missing edges could be replaced by a learned or curvature-based importance model; the DSR loop is agnostic to that choice.","If real graphs are not of the 'sparsified latent graph' form, the recovered edges may optimize the proxy objective without corresponding to genuine missing structure, which would weaken the claim that rewiring recovers the true bottlenecks."],"forward_implications":["Graph rewiring no longer has to trade spectral fidelity for connectivity; the same graph can get both, because the output stays spectrally close while effective resistance drops.","Heterophilic node-classification datasets (Texas, Cornell, Wisconsin) show the largest gains, suggesting that spectrum-preserving rewiring helps exactly where topology is easily damaged.","Training cost stays close to the original because Go has at most as many edges as G, so message passing on the rewired graph is not denser.","The densification-sparsification recipe is general: any inverse-sparsification model of an observed graph can seed a rewiring method, not only the Fiedler-vector heuristic used here."],"supporting_citations":[{"why":"Supplies the effective-resistance sparsification technique that GOKU adapts for its ISS sparsification step and for the proof of Theorem 4.2.","marker":"Spielman & Srivastava (2008)"},{"why":"Establishes that (1±ε)-spectral sparsifiers exist with O(n log n / ε^2) edges, used to justify the densification premise.","marker":"Benczúr & Karger (1996)"},{"why":"Provides the near-linear-time effective-resistance approximation used in the ISS step.","marker":"Koutis et al. (2014)"},{"why":"Defines over-squashing as the problem GOKU targets and motivates the rewiring objective.","marker":"Alon & Yahav (2021)"},{"why":"FoSR, a first-order spectral rewiring baseline that GOKU compares against in the experiments.","marker":"Karhadkar et al. (2023)"},{"why":"SDRF, a curvature-based rewiring baseline, and a prior edge-modification method for over-squashing.","marker":"Topping et al. (2022)"},{"why":"GTR baseline that minimizes total effective resistance, closely related to GOKU's connectivity goal.","marker":"Black et al. (2023)"},{"why":"Delaunay rewiring baseline whose spectral drift motivates GOKU's spectrum-preservation objective.","marker":"Attali et al. (2024)"},{"why":"LASER baseline, the locality-aware rewiring method GOKU is compared with in the experiments.","marker":"Barbero et al. (2024)"}],"fun_headline_variants":["Spectrum-preserving sparsification fixes over-squashing in GNNs","GOKU: rewiring GNNs without losing spectral properties","Densify then sparsify to reduce over-squashing while keeping spectrum","Sparsify to boost GNN message passing, preserve Laplacian spectrum","New rewiring method cuts over-squashing, keeps graph spectrum"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing claim is that the input graph G can be treated as a spectral sparsifier of the reconstructed latent graph Gl, but the actual Gl is built with heuristic approximations and this spectral similarity is never verified.","fun_headline_variants_meta":{"raw":{"variants":["Spectrum-preserving sparsification fixes over-squashing in GNNs","GOKU: rewiring GNNs without losing spectral properties","Densify then sparsify to reduce over-squashing while keeping spectrum","Sparsify to boost GNN message passing, preserve Laplacian spectrum","New rewiring method cuts over-squashing, keeps graph spectrum"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00057,"raw_usage":{"total_tokens":2655,"prompt_tokens":864,"completion_tokens":1791,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":480,"completion_tokens_details":{"reasoning_tokens":1691}},"tokens_in":480,"tokens_out":1791,"duration_ms":11048,"temperature":1.0,"reasoning_tokens":1691,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T19:29:11.536026+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Compute, on a graph rewired by GOKU, the ratio |x^T L_{G_o} x − x^T L_G x| / x^T L_G x over many random vectors x, or the ordered eigenvalue differences, and check whether the values stay within the claimed (1±ε)^2 window; a consistent violation would refute the spectrum-preservation claim.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the effective-resistance sparsification technique that GOKU adapts for its ISS sparsification step and for the proof of Theorem 4.2."},{"cited_title":"L., and Peng, R","cited_arxiv_id":null,"evidence_quote":"Provides the near-linear-time effective-resistance approximation used in the ISS step."},{"cited_title":"K., and Mont \\' u far, G","cited_arxiv_id":null,"evidence_quote":"FoSR, a first-order spectral rewiring baseline that GOKU compares against in the experiments."},{"cited_title":"D., Chamberlain, B","cited_arxiv_id":null,"evidence_quote":"SDRF, a curvature-based rewiring baseline, and a prior edge-modification method for over-squashing."},{"cited_title":"Understanding oversquashing in gnns through the lens of effective resistance","cited_arxiv_id":null,"evidence_quote":"GTR baseline that minimizes total effective resistance, closely related to GOKU's connectivity goal."},{"cited_title":"Delaunay graph: Addressing over-squashing and over-smoothing using delaunay triangulation","cited_arxiv_id":null,"evidence_quote":"Delaunay rewiring baseline whose spectral drift motivates GOKU's spectrum-preservation objective."},{"cited_title":"M., and Giovanni, F","cited_arxiv_id":null,"evidence_quote":"LASER baseline, the locality-aware rewiring method GOKU is compared with in the experiments."}],"review_version":1}