{"id":"b15b1e13-c545-4831-ae10-bb856d895f10","arxiv_id":"2608.09031","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":5,"one_line_summary":"HOPPER learns graph- and hop-adaptive sequence extraction for linearized graph sequence models, recovering fixed LGSM extractors as special cases and achieving the best reported scores on eccentricity and shortest-path prediction in ECHO-SYNTH.","lead":"This paper introduces HOPPER, a graph neural network that learns how to build the multi-hop propagation sequences fed to a state-space model, instead of using fixed graph operations. The result is a flexible extractor that matches or beats prior sequence-based graph models on two of three long-range synthetic benchmarks, alongside new stability and locality theorems.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theory-experiment gap is load-bearing: the normalized recurrence actually evaluated (Eq. 22) does not exactly realize the non-backtracking special case, and Chebyshev realization requires zeroing the degree-channel coefficients; the optimal-sensitivity explanation is unproven for the reported model.","rationale":"The reader's weakest assumption identifies exactly the same gap: the evaluated model uses the normalized recurrence while the containment and optimality theorems are proved for the exact recurrence. My pass confirms the gap is real and load-bearing. Under eU=D^{1/2}U, the A-channel becomes A_sym, but the degree channel I-D^{-1} is not conjugated away and is not a multiple of the identity; hence the experimental recurrence is not simply a symmetric-shift polynomial propagator. The Chebyshev special case can be recovered only by zeroing α_D, and the non-backtracking special case cannot be recovered exactly at all. Since the paper offers Theorem 4.4.1 as the mechanism by which a richer extractor reduces over-squashing, and since the experiments are the only evidence that learning helps, the missing proof that Eq. (22) realizes the analyzed propagators is a genuine correctness risk. The empirical results themselves are not undermined: HOPPER's ECC/SSSP numbers stand as published, and the reader's CONDITIONAL verdict is the right response. I therefore do not move the verdict; the condition should be that the authors either prove containment for the normalized recurrence with the trained coefficient behavior or evaluate the exact recurrence. The secondary contradictions in the LRIM sweep and the absent baselines are minor and do not change this assessment.","tokens_in":23326,"tokens_out":12638,"duration_ms":115130,"concrete_test":"Run ECHO-SYNTH ECC and SSSP with the exact recurrence Eq. (15) in place of Eq. (22), stabilizing only to prevent overflow (e.g., rescaling the feature matrix), with all other components and hyperparameters unchanged. If the exact-path results match the normalized-path numbers within seed noise, the gap is immaterial; if they differ materially, the paper must either prove that Eq. (22) with the learned α_D realizes the Chebyshev special case or restrict the theoretical claims to the exact path. During the same run, log the learned α_D coefficients: if they are not identically zero at convergence, the Chebyshev realization condition is violated.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central theoretical mechanism -- that learnable extraction mitigates over-squashing by realizing Chebyshev-optimal first-arrival sensitivity (Theorem 4.4.1) -- is proved for the exact recurrence (Eq. 15) with unnormalized A and D, or for a symmetric shift S. Appendix B states that all experiments use the normalized recurrence (Eq. 22), with A_rw and I-D^{-1}, because L=40 and L=32 exceed the L=20 cutoff. The similarity argument after Theorem 4.3.1 conjugates only the adjacency channel: D^{1/2} A_rw D^{-1/2}=A_sym. The degree channel transforms to D^{1/2}(I-D^{-1})D^{-1/2}=I-D^{-1}, a diagonal operator that is not a multiple of the identity. Consequently, the non-backtracking coefficient assignment of Theorem 4.3.1(ii) does not produce B(k) in the evaluated recurrence, and the Chebyshev special case is realized only if the hypernetwork sets α_D[j]=0 for every hop. The paper provides no evidence about the learned α_D values, so the claimed containment and the optimal-sensitivity explanation are not established for the model behind Tables 1-2. This does not invalidate the empirical ECC/SSSP results, but it removes the theoretical support for why the learnable extractor helps, which is central to the paper's framing.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"HOPPER proposes a learnable hop-sequence extractor for Linearized Graph Sequence Models (LGSMs). Instead of a fixed propagation rule, a hypernetwork conditions hop-dependent coefficients on a permutation-invariant graph summary, and a finite-memory linear recurrence produces structural states that are processed by a Mamba2-based SSM. The paper claims permutation equivariance, polynomial locality, containment of adjacency-power and non-backtracking LGSM extractors, an optimal Chebyshev first-arrival sensitivity result, and preservation of nonstationary spectral information. Experiments on ECHO-SYNTH report best or competitive results on eccentricity, SSSP, and diameter, and a memory-window sweep on LRIM-16 is reported.","tokens_in":23493,"tokens_out":7329,"duration_ms":69219,"significance":"If the central claims held as stated, this would be a useful contribution: it generalizes fixed LGSM extractors to an adaptive family while preserving equivariance and locality, and the Chebyshev sensitivity analysis provides a clean theoretical mechanism for mitigating over-squashing. The appendix proofs are a genuine strength: the permutation-equivariance argument, polynomial-locality proof, containment construction, Chebyshev extremal lemma, and spectral-average calculation are carefully presented and check out. The empirical results, however, are only moderately supportive: the ECC win has high variance, the LRIM window comparison is statistically inconclusive, and no LRIM baseline is provided. Most importantly, the theoretical optimality statements are proved for the exact recurrence with unnormalized operators or a symmetric shift, while all experiments use the normalized recurrence; the connection between the theory and the reported gains is not established for the implemented model.","major_comments":[{"comment":"The theoretical containment results are proved for the exact recurrence in Eq. (15) with unnormalized A and D, or for the generalized recurrence with a symmetric shift S, but Appendix B states that all experiments use the normalized recurrence Eq. (22) with A_rw = D^{-1}A and I-D^{-1}. The similarity argument after Theorem 4.3.1 conjugates only the adjacency channel: D^{1/2} A_rw D^{-1/2} = A_sym. The degree channel transforms as D^{1/2}(I-D^{-1})D^{-1/2} = I-D^{-1}, which is a non-scalar diagonal operator. Consequently, the non-backtracking coefficient assignment of Theorem 4.3.1(ii) does not produce B^(k) in the evaluated recurrence, and Chebyshev propagation is realized only if the learned coefficients satisfy alpha_D[j]=0 for every hop. The paper provides no evidence about the learned alpha_D values, so the claimed containment and the optimal-sensitivity explanation are not established for the model behind Tables 1-2. This does not invalidate the empirical results, but it removes the theoretical support for why the learnable extractor helps, which is central to the paper's framing.","section":"Appendix B and §4.3"},{"comment":"Theorem 4.4.1 and Corollary 4.4.1 are stated for a symmetric graph operator with spectrum in [-1,1]. The experimental recurrence uses the non-symmetric random-walk operator A_rw. Similarity to A_sym is not by itself sufficient: the extremal class P_r is defined on [-1,1] for polynomials of a symmetric operator, and the proof uses the spectral theorem for that symmetric operator. Even in the special case alpha_D=alpha_I=0, the paper does not prove that the normalized recurrence exactly realizes T_r(A_sym) or that the stated sensitivity bound holds for the non-symmetric T_r(A_rw) under the same stability constraint. An analogous extremal statement for the normalized family, or an explicit weakening of the theoretical claims, is needed before Theorem 4.4.1 can be cited as the mechanism behind the empirical gains.","section":"§4.4 and Definition 1"},{"comment":"The headline empirical claim that HOPPER 'achieves the best performance on eccentricity' rests on an ECC MSE of 6.571 with standard deviation 2.656 over only three seeds, compared with LGSM's 13.549±0.539. With this variance, the ECC improvement is not statistically robust, and the DIAM result (3.200±0.528 vs. LGSM 3.089±0.389) is within noise. The SSSP result (0.021±0.008 vs. 0.040±0.008) is more convincing, but the overall state-of-the-art claim is overstated. Additional seeds, confidence intervals, or a paired comparison would be needed to support the strength of the current wording.","section":"Table 1 and §5"},{"comment":"The LRIM experiment does not establish that learnable extraction is beneficial. Table 2 reports log10(MSE) values for M=2,4,8,16, but Appendix B states 'We evaluate M in {2,4,8}', so the table and text are contradictory. Moreover, M=8 (-3.505±0.063) and M=16 (-3.502±0.081) differ by less than one standard deviation, and each value is the mean of only two seeds. There is no comparison against LGSM or any fixed-extractor baseline on LRIM, so the claim that varying the structural memory window 'can optimize accuracy' is not supported as an advantage of HOPPER over existing extractors.","section":"Table 2 and Appendix B"}],"minor_comments":[{"comment":"The number K of learnable seed queries is introduced as a free parameter in Eq. (12) but its value is never reported in Appendix B or in the experimental setup. Please state the value used and whether it was swept.","section":"§3.2 and Appendix B"},{"comment":"The discussion following Theorem 4.4.2 says the Cesàro average of Dirichlet energy converges to 1/2 E(H), but the theorem's conclusion is 1/2 ||H_perp||_F^2, which equals 1/2 E(H) only when the stationary component vanishes. Please correct this statement.","section":"§4.4"},{"comment":"The term 'Dirchlet energy' is misspelled and should be 'Dirichlet energy' in the two places it appears.","section":"Throughout"},{"comment":"The sentence 'No clipping occurs in any of our reported experiments, so the characterization of Theorem C.2.1 applies throughout' is misleading, because Theorem C.2.1 characterizes the exact recurrence while the reported experiments use the normalized recurrence of Eq. (22). The claim should be restricted to the polynomial-structure and locality parts that hold for both recurrences.","section":"Appendix B"}],"recommendation":"major_revision","confidential_remarks":"The appendix is clearly the strongest part of the paper and the proofs appear sound. The main issue is a mismatch between the theory (exact recurrence, symmetric operators) and the experiments (normalized recurrence, random-walk operators), which currently leaves the paper's central mechanism unsupported for the implemented model. I would like to see either an extension of the theory to the normalized family or a revised framing that separates the theoretical contribution from the empirical one. The experimental section also needs more seeds and a LRIM baseline before the stated claims are publishable at the level suggested by the abstract."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Quick take: HOPPER is a real new method—learnable hop-sequence extraction for LGSMs via a hypernetwork conditioned on a permutation-invariant graph summary—and the theory in Appendix C is clean and checks out. The containment results (adjacency and non-backtracking as special cases), the polynomial-locality theorem, and the Chebyshev extremal argument are all solid. The spectral-preservation result is a nice formal statement as well. The authors do not oversell the theory; the proofs are straightforward but correct.\n\nThe soft spot is the gap between theory and the evaluated model. Every experiment uses the normalized recurrence (Eq. 22) with A_rw and I-D^{-1}, because L=40/32 exceeds the L=20 cutoff. The theory is proved for the exact recurrence with unnormalized A and D, or for a symmetric shift S. The similarity argument conjugates only the adjacency channel; the degree channel becomes I-D^{-1}, and that is not a multiple of the identity. So the non-backtracking special case of Theorem 4.3.1 does not transfer exactly to the evaluated recurrence, and Chebyshev realization works only if the learned α_D coefficients are all zero. The paper gives no evidence about learned α_D values. That means the central mechanistic explanation—Chebyshev-optimal first-arrival sensitivity is why learnable extraction helps—is unproven for the architecture behind Tables 1 and 2. The empirical wins on ECC and SSSP can stand on their own, but they lose their theoretical underpinning.\n\nOn the empirical side: the ECC MSE win is high-variance (6.571±2.656), the LRIM M=8 vs M=16 difference is within noise, and LGSM still wins DIAM. Some graph-SSM baselines from related work are absent from Table 1, so \"state-of-the-art\" is relative to the published ECHO baselines only. There are also small internal inconsistencies: the memory-window sweep text says M∈{2,4,8} while Table 2 includes M=16, and the ECHO sequence length is not reconciled in the text.\n\nNone of this invalidates the method or the theory on its own terms. The gap is fixable by either running the exact-path experiments for L≤20 and showing the same results, or extending the containment/sensitivity theorems to the normalized recurrence (possibly via the D^{1/2} similarity plus an argument for the diagonal term). The paper deserves a serious referee: a competent reviewer can verify the proofs quickly and the authors have supplied enough detail to reproduce the architecture. I'd send it to review with a request for a major revision focusing on the theory-experiment connection and the experimental inconsistencies. Whoever gets this should read the appendix carefully; the main text alone overstates what is actually established.","headline":"A genuinely new learnable hop-extraction method with clean, checkable theory, but the central explanation for its empirical gains is not established for the architecture that was actually evaluated.","tokens_in":24188,"tokens_out":2396,"would_cite":true,"duration_ms":23248,"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":"HOPPER makes the hop-sequence extractor of linearized graph sequence models learnable, recovers fixed propagators as special cases, and reports best results on two long-range ECHO-SYNTH tasks.","keywords":["learnable hop extraction","linearized graph sequence models","long-range graph learning","over-squashing","Chebyshev polynomial propagation","state-space sequence models","permutation equivariance","graph polynomial filters"],"falsifier":"Run the exact unnormalized recurrence and the normalized experimental recurrence side by side on a small graph using the coefficient settings from Theorem 4.3.1, and compare the resulting sequences with $B^{(k)}H$ and $T_k(A_{\\mathrm{sym}})H$; any mismatch at hop $k$ means the deployed model is not covered by the containment and optimality proofs. A second check: clamp HOPPER's coefficients to the Chebyshev values and compare with free training on ECHO-SYNTH; if free training is not at least as good, the reported gains are not evidence of attaining the theorem's optimum.","tokens_in":22970,"feed_emoji":"🕸️","tokens_out":12834,"duration_ms":111193,"temperature":0.7,"pith_summary":"Linearized Graph Sequence Models (LGSMs) decouple how far information travels on a graph from how many nonlinear layers process it, but they rely on fixed propagation rules such as adjacency powers or non-backtracking walks. HOPPER's central claim is that making the hop-sequence extractor learnable—conditioned on the graph, the node features, and the hop index—improves long-range propagation without losing permutation equivariance. The paper shows that the learnable extractor contains standard LGSM extractors as exact special cases, and that inside the class of uniformly stable degree-$r$ polynomial propagators the Chebyshev polynomial maximizes first-arrival sensitivity by a factor of $2^{r-1}$, mitigating over-squashing. Empirically, HOPPER reports the best results on eccentricity and single-source shortest-path prediction in ECHO-SYNTH while remaining competitive on diameter, and the memory-window size matters on the LRIM-16 benchmark.","feed_headline":"Learnable hop extraction beats fixed rules on long-range graph tasks","feed_subtitle":"The same framework recovers standard LGSM propagators and amplifies distant messages exponentially at distance r","key_machinery":"The carrier of the argument is the linear structural-state recurrence\n$$$U^{{(k)}}$ = \\sum_{j=1}^{M}\\left(\\$alpha_A^{{(k)}}$[j]A + \\$alpha_D^{{(k)}}$[j]D + \\$alpha_I^{{(k)}}$[j]I\\right)$U^{{(k-j)}}$,$$\nwith $U^{(0)} = H$ and $U^{(i)} = 0$ for $i < 0$. The coefficients are produced by a hypernetwork from a permutation-invariant graph summary and a hop embedding, so the propagation rule varies across graphs, node features, and hop depth; the memory window $M$ controls how many previous structural states contribute. This recurrence does three jobs: it keeps the extracted states linear in $H$ (Theorem 4.2.1), it contains adjacency-power, non-backtracking, and Chebyshev propagation as exact special cases (Theorem 4.3.1), and it sets up the degree-$r$ polynomial class $\\mathcal{P}_r$ in which Chebyshev's extremal leading coefficient yields the first-arrival sensitivity bound (Theorem 4.4.1). A shared state-space sequence model then processes each node's hop trajectory independently, which preserves permutation equivariance and keeps propagation depth separate from nonlinear processing depth.","core_discovery":"On its own terms, the paper claims that the hop sequences fed to a linearized graph sequence model should not be fixed in advance. HOPPER replaces the fixed extractor with a hypernetwork-conditioned linear structural-state recurrence: an MLP reads a permutation-invariant summary of the graph together with a hop embedding and emits coefficients for a finite-memory combination of adjacency, degree, and identity operators, with a feature-attention term applied only to the output states. Conditional on those coefficients, each state is a finite-hop polynomial in $A$ and $D$, so locality is preserved. The paper proves the family recovers adjacency-power and non-backtracking propagation exactly and that, among uniformly stable degree-$r$ polynomial propagators, the Chebyshev polynomial attains the maximum first-arrival sensitivity $2^{r-1}|[G^r]_{uv}|$, compared with $|[G^r]_{uv}|$ for power propagation. It concludes that HOPPER can transmit long-range information exponentially more strongly than fixed adjacency powers while staying non-expansive, preserve nonstationary spectral content across the sequence, and still report best ECC and SSSP numbers with a competitive diameter number on ECHO-SYNTH.","pith_inferences":["If the normalized recurrence used in the experiments inherits the containment and optimality theorems, the learnable family can smoothly interpolate between power, non-backtracking, and Chebyshev behavior per hop, giving a direct testable knob for over-squashing.","The theory suggests a non-learnable Chebyshev extractor might capture much of HOPPER's gain on long-range structural tasks; comparing free HOPPER with coefficients clamped to the Chebyshev setting would isolate what learnability itself adds.","The permutation-invariant graph summary and hop-conditioned coefficients could extend to directed or heterophilic graphs, where symmetric normalized propagation is a poor fit; the paper does not test this.","A practical diagnostic is to inspect the learned coefficients on sparse long-range benchmarks: if they do not approach Chebyshev-like values, the empirical gains likely come from the feature-attention correction or the state-space processor rather than from the proved sensitivity bound."],"forward_implications":["Users of an LGSM can keep the separation of propagation depth from processing depth while letting propagation adapt to the graph and task; the standard adjacency-power and non-backtracking sequences remain available as fixed coefficient choices.","On graphs with spectrum in $[-1,1]$, the Chebyshev-extractible sequence delivers first-arrival sensitivity up to $2^{r-1}$ times that of power propagation at distance $r$ without increasing the spectral norm, so over-squashing is mitigated without rewiring or added nonlinear depth.","The sequence-level spectral-preservation result means the downstream sequence model receives a stable amount of nonstationary spectral information at every depth, instead of watching it decay geometrically through repeated adjacency powers.","The reported ECHO-SYNTH and LRIM-16 results imply that learnable extraction is at least competitive with hand-designed extractors, and that the memory window $M$ is a meaningful tuning knob for tasks with different long-range demands."],"supporting_citations":[{"why":"Defines LGSMs and the fixed adjacency/non-backtracking extractors that HOPPER extends and recovers as special cases.","marker":"[37]"},{"why":"Supplies the state-space sequence model used to process hop sequences after extraction.","marker":"[12]"},{"why":"Provides the ECHO-SYNTH benchmark and evaluation protocol for diameter, eccentricity, and single-source shortest-path tasks.","marker":"[38]"},{"why":"Provides the LRIM-16 physics-based long-range benchmark used to test memory-window sensitivity.","marker":"[36]"},{"why":"Introduces hypernetworks, the mechanism for generating graph- and hop-conditioned propagation coefficients.","marker":"[22]"},{"why":"Identifies over-squashing as the bottleneck that the sensitivity bound in Theorem 4.4.1 is meant to address.","marker":"[2]"},{"why":"Provides the adaptive generalized-PageRank filter family as a precedent for adaptive propagation that HOPPER generalizes.","marker":"[10]"}],"fun_headline_variants":["Learnable hops amplify long-range signals exponentially","Hop selector learns graph-specific sequences for long-range tasks","Exponential long-range amplification via learned hop extraction","HOPPER: Learn where to hop for exponential long-range memory","Learnable hops: exponential long-range gain"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The experiments use a numerically stabilized version of the propagation recurrence, while the theorems that pin down the method's beneficial Chebyshev behavior are proved for the exact version; if the stabilized version cannot realize the same propagation, the paper's theoretical explanation of the empirical gains does not apply.","fun_headline_variants_meta":{"raw":{"variants":["Learnable hops amplify long-range signals exponentially","Hop selector learns graph-specific sequences for long-range tasks","Exponential long-range amplification via learned hop extraction","HOPPER: Learn where to hop for exponential long-range memory","Learnable hops: exponential long-range gain"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000703,"raw_usage":{"total_tokens":3221,"prompt_tokens":1046,"completion_tokens":2175,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":662,"completion_tokens_details":{"reasoning_tokens":2115}},"tokens_in":662,"tokens_out":2175,"duration_ms":15505,"temperature":1.0,"reasoning_tokens":2115,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T04:18:16.807010+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the exact unnormalized recurrence and the normalized experimental recurrence side by side on a small graph using the coefficient settings from Theorem 4.3.1, and compare the resulting sequences with $B^{(k)}H$ and $T_k(A_{\\mathrm{sym}})H$; any mismatch at hop $k$ means the deployed model is not covered by the containment and optimality proofs. A second check: clamp HOPPER's coefficients to the Chebyshev values and compare with free training on ECHO-SYNTH; if free training is not at least as good, the reported gains are not evidence of attaining the theorem's optimum.","supporting_citations":[{"cited_title":"From Message-Passing to Linearized Graph Sequence Models","cited_arxiv_id":"2605.12358","evidence_quote":"Defines LGSMs and the fixed adjacency/non-backtracking extractors that HOPPER extends and recovers as special cases."},{"cited_title":"Transformers are SSMs: Generalized models and efficient algorithms through structured state space duality","cited_arxiv_id":null,"evidence_quote":"Supplies the state-space sequence model used to process hop sequences after extraction."},{"cited_title":"Can you hear me now? a benchmark for long-range graph propagation","cited_arxiv_id":null,"evidence_quote":"Provides the ECHO-SYNTH benchmark and evaluation protocol for diameter, eccentricity, and single-source shortest-path tasks."},{"cited_title":"LRIM: a physics-based benchmark for provably evaluating long-range capabilities in graph learning","cited_arxiv_id":null,"evidence_quote":"Provides the LRIM-16 physics-based long-range benchmark used to test memory-window sensitivity."},{"cited_title":"Dai, and Quoc V","cited_arxiv_id":null,"evidence_quote":"Introduces hypernetworks, the mechanism for generating graph- and hop-conditioned propagation coefficients."},{"cited_title":"On the bottleneck of graph neural networks and its practical implications","cited_arxiv_id":null,"evidence_quote":"Identifies over-squashing as the bottleneck that the sensitivity bound in Theorem 4.4.1 is meant to address."},{"cited_title":"Adaptive universal generalized PageRank graph neural network","cited_arxiv_id":null,"evidence_quote":"Provides the adaptive generalized-PageRank filter family as a precedent for adaptive propagation that HOPPER generalizes."}],"review_version":1}