acceptodds
Under review as a conference paper at ICLR 2027

HOPPER: Learnable Hop Extraction for Linearized Graph Sequence Models

Abstract

Graph neural networks typically propagate information through repeated message-passing layers, coupling the distance over which information travels with the number of nonlinear transformations applied. This coupling can make deep architectures difficult to optimize and can lead to over-smoothing, over-squashing, and the loss of long-range information. Linearized Graph Sequence Models (LGSMs) address this issue by separating information depth from processing depth and treating the successive propagation states of each node as a sequence. However, existing LGSMs construct these sequences using fixed graph operators, limiting their ability to adapt propagation to the input graph, node features, and downstream task. We introduce HOPPER, an end-to-end learnable extension of LGSM that learns how hop sequences should be extracted before they are processed by a modern state-space model. Our framework supports feature-conditioned, structure-aware, graph and hop-adaptive propagation mechanisms while preserving permutation equivariance, with standard adjacency-based and non-backtracking LGSM sequences arising as special cases of our extractor family. We show that HOPPER is state-of-the-art or competitive across the ECHO-Synth benchmark and performs strongly on the City-Networks dataset. On the LRIM physics-based long-range dependency benchmark, we find that varying the maximum neighborhood size of message-backtracking cancellation, corresponding to the structural memory window, can substantially affect performance. Ablation studies further isolate the contributions of the learnable extraction mechanism and its structural and feature-adaptive components, demonstrating that adaptive hop-sequence construction is important beyond the downstream sequence model alone. Together, these results show that learnable sequence extraction provides a flexible and effective approach to long-range graph representation learning across synthetic, physics-based, and real-world graph benchmarks.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
graph neural networks, message-passing, linearized graph sequence models, state-space models

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_Nuo4OpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper builds upon and extends the work of [Mathys et al., 2026]. In particular, Mathys et al., proposes to separate the information propagation and non-linear processing aspects of standard message passing neural network (MPNNs), and introduces a new type of graph learning frameworks, called Linearized Graph Sequence Models (LGSM). Essentially, LGSM first captures information propagation by constructing a sequence of node embeddings via repeatedly applying some linear operator (e.g, applying adjacency matrix or graph Laplacian). It then captures (non-linear) information processing by another sequence processing model (State Space Machine in their case).

The current paper proposes HOPPER, which adopts the same conceptual separation, and essentially is an end-to-end learnable extension of LGSM. builds upon LGSM. The main methodology contribution is to make the first sequence extraction stage learnable. In particular, it uses various suitable attention based mechanisms to learn hop-dependent and (global) graph dependent combination of certain linear operators, applied to original node features, instead of using fixed operators as in LGSM. Theoretically, they show that the new learnable model respects permutation equivariance, and has the capacity to recover the fixed LGSM extractor as well as Chebyshev propagation (Theorem 4.3). The paper also provide theoretical results on long range sensitivity (Theorem 4.4, Corollary 4.1) and preservation of non-stationary spectral energy (Theorem 4.5) under fixed propagation rules. In both cases, Chebyshev propagation obtains strong results, compared to say, fixed Adjacency power propagation. Empirically, the authors evaluate HOPPER on two long-range graph benchmarks, where HOPPER achieves similar or better performance than those comparison methods on ECHO-Synth, and close performance on the large real-world graphs in CITY-NETWORKS.

Critical strengths

++ Making sequence extraction learnable makes lots of sense. The authors also give careful considerations to make the propagation rules dependent on not just hops but also global graph structures via a learned graph summary. I particularly like the dependency on global graph summary.

++ I appreciate the theoretical analysis.

Critical weaknesses

-- While the learnable sequence extraction is interesting, the work feels somewhat incremental.

-- I also feel that the linearized sequence models itself has not yet been fully justified: how strong are such models theoretically? Does it have the same expressive power as MPNNs or graph transformers or are we losing expressivity here?

(The paper provides some theoretical analysis, which I like. But (1) Theorem 4.3 just showed that the adaptable polynomial propagation can recover other choices of linear sequence extraction models. (2) Other results are on fixed propagation linear rules (especially Chebyshev propagation). )

-- Empirical results are not particularly strong: on the real city networks, the performance of HOPPER is worse than Exphormer for most cases. There are not much discussions on insights when and why HOPPER is most beneficial.

Furthermore, the baslines compared with are not consistently evaluated across the two benchmark families: in Table 2, Exphormer is the the strongest method, yet it is not compared against for the ECHO-SYNTH in Table 1. The paper also didn't compare its HOPPER against its predecessor LGSM for the CITY-NETWORKS benchmark. With such omissions, I am not sure we can argue that HOPPER is the best on ECHO-SYNTH (since the best performing Exphormer is not here), and its improvement over LGSM also needs more demonstration.

Minor comment:

  • Perhaps one can look into a learned model to see what are the coefficients (those \alpha_A, \alpha_D and \alpha_I's) learned, and develop some insights.
Questions for authors

See weakness

3 comments
AuthorsOpenReview ↗

Response to Reviewer Nuo4 (Part 1/3)

Dear reviewer, thank you for your helpful feedback. We are glad that you found our proposed learnable sequence extraction approach to be well-motivated, particularly the incorporation of global graph information through a learned graph summary. We also appreciate that you found our theoretical analysis to be informative. We thank you for your comments and suggestions, and would like to respond to the points you raised below.

W1. While we agree with the reviewer that this work is drawn on previous literature and work in adaptive graph filtering and graph propagation, we believe that HOPPER introduces a useful new perspective on graph sequence construction that can motivate further research in this direction.

In particular, a wide range of existing graph learning architectures rely on predetermined propagation mechanisms or structural encodings to extract information from the input graph. For example, multi-hop GNN architectures such as MixHop [1] and SIGN [2] construct representations using predefined graph operators, while graph transformers and hybrid architectures such as NAGphormer [3], Graphormer [4], and GraphGPS [5] incorporate structural information through fixed propagation schemes or positional and structural encodings. Although these mechanisms have proven effective, how this structural information is extracted can substantially influence downstream performance, and a single fixed mechanism may not be equally suitable across different graph structures and tasks.

Our work explores this idea in the context of LGSMs by making hop-sequence extraction itself adaptive and end-to-end learnable. We believe this is a meaningful extension because it shifts part of the learning process from how graph representations are processed to how they are constructed in the first place.

Importantly, while we investigate this approach within LGSMs, we believe the underlying idea is more broadly applicable. With appropriate architectural modifications, similar adaptive extraction mechanisms could potentially be incorporated into MPNNs, graph transformers, and hybrid models by replacing fixed multi-hop propagation features or structural encodings with learnable, graph-conditioned alternatives. This may be particularly beneficial in settings where no single propagation mechanism adequately captures the relevant structural information across different graphs and tasks.

Our empirical results provide initial support for this perspective. In particular, HOPPER substantially outperforms fixed-propagation LGSM on several benchmarks, with especially pronounced improvements on Shanghai and London in City-Networks. Together with our architectural ablations, this suggests that adaptively constructing graph representations can provide meaningful benefits beyond relying on stronger downstream sequence models alone. Thus, we believe that treating graph sequence construction as an adaptive learning problem is a useful methodological direction with potential applications beyond LGSMs.

[1] Abu-El-Haija, S., Perozzi, B., Kapoor, A., Alipourfard, N., Lerman, K., Harutyunyan, H., ... & Galstyan, A. (2019). MixHop: Higher-order graph convolutional architectures via sparsified neighborhood mixing. International Conference on Machine Learning (ICML).

[2] Frasca, F., Rossi, E., Eynard, D., Chamberlain, B., Bronstein, M., & Monti, F. (2020). SIGN: Scalable inception graph neural networks. Graph Representation Learning and Beyond (GRL+) Workshop at the International Conference on Machine Learning (ICML).

[3] Chen, J., Gao, K., Li, G., & He, K. (2023). NAGphormer: A tokenized graph transformer for node classification in large graphs. International Conference on Learning Representations (ICLR).

[4] Ying, C., Cai, T., Luo, S., Zheng, S., Ke, G., He, D., ... & Liu, T. Y. (2021). Do transformers really perform badly for graph representation? Advances in Neural Information Processing Systems (NeurIPS).

[5] Rampášek, L., Galkin, M., Dwivedi, V. P., Luu, A. T., Wolf, G., & Beaini, D. (2022). Recipe for a general, powerful, scalable graph transformer. Advances in Neural Information Processing Systems (NeurIPS).

AuthorsOpenReview ↗

Response to Reviewer Nuo4 (Part 2/3)

W2. We thank the reviewer for raising this important question. Our primary motivation for adopting LGSMs [1] is due to the growing body of literature demonstrating the effectiveness of state-space models (SSMs) for learning long-range dependencies in graphs. In particular, [2, 3] demonstrate that selective state-space model architectures can indeed outperform MPNNs and transformer-based graph architectures including GraphGPS, across several long-range graph learning benchmarks, often with reduced computational requirements. Furthermore, there is some literature such as [4] which uses ideas from state-space models to carefully construct a permutation equivariant set aggregation function which preserves the desirable properties of state-space models in which they find this aggregator can capture long-range dependencies (Proposition 3.1) and has greater expressive power than MPNNs (Proposition 3.2). It would be an interesting future direction to investigate whether HOPPER, either in its current form or with some modification, can yield the same expressivity results as [4].

LGSMs builds on this body of literature by considering ways to construct the graph sequences as previous literature such as [2, 3] often introduce techniques such as node prioritization, neighborhood tokenization, etc which often break the inductive bias of graphs being permutation symmetry. By applying fixed propagation rules to extract sequences which they can pass into a state-space model, they are able to decouple information and processing depth in the sense that one can propagate information far in the graph while also controlling the number of nonlinearities. As HOPPER builds on LGSMs by augmenting the fixed propagation sequence extraction with adaptive learned sequence extraction conditioned on the properties of the graph itself, it is reasonable to believe that our architecture would maintain the same expressive power as MPNNs and (possibly) graph transformers as evident from previous literature.

As for our theoretical results, our motivation is to indeed demonstrate that HOPPER is able to represent propagation mechanisms that can achieve improved long-range sensitivity while preserving spectral stability. In particular, our analysis in Theorem 4.3 shows that HOPPER can recover Chebyshev propagation which we additionally prove with Theorem 4.4 and 4.5 is able to improve long-range sensitivity and preserve spectral stability compared to adjacency propagation i.e. S(ℓ)=AℓH\mathbf{S}^{(\ell)} = \mathbf{A}^{\ell} \mathbf{H} for fixed H∈Rn×d\mathbf{H} \in \mathbb{R}^{n \times d} where A∈Rn×n\mathbf{A} \in \mathbb{R}^{n \times n} is the adjacency matrix. We are also able to recover the propagation mechanisms used in [1]. We agree that Theorem 4.4 and 4.5 are for fixed Chebyshev propagation as the purpose of these results is to motivate the design of the recurrence and show that this recurrence family can adaptively identify a subset of propagation families conditioned on the graph which has favorable properties. Doing such an analysis with the learned coefficients would prove difficult as it would necessitate constraints and/or theoretically conservative assumptions which may not hold in practice, hence why we took this direction. Additionally, with our empirical ablations in mind, we believe that adaptive propagation can possibly learn propagation mechanisms which can be even better than Chebyshev propagation for specific problems, although the form of these mechanisms and why they perform better is unclear.

We hope our response provides the reviewer with more clarity on why we decided to combine HOPPER with a sequence model, particularly as an extension of LGSM. We also hope that the motivation for our theoretical results and its intended implications are also more clear.

[1] Mathys, J., Rohner, B., Peltonen, S., & Wattenhofer, R. (2026). From Message-Passing to Linearized Graph Sequence Models. arXiv preprint arXiv:2605.12358.

[2] Behrouz, A., & Hashemi, F. (2024). Graph Mamba: Towards learning on graphs with state space models. Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, 119–130.

[3] Wang, C., Tsepa, O., Ma, J., & Wang, B. (2024). Graph-Mamba: Towards long-range graph sequence modeling with selective state spaces. arXiv preprint arXiv:2402.00789.

[4] Huang, Y., Miao, S., & Li, P. (2024). What can we learn from state space models for machine learning on graphs? arXiv preprint arXiv:2406.05815.

AuthorsOpenReview ↗

Response to Reviewer Nuo4 (Part 3/3)

W3. We thank the reviewer for this feedback. We agree that Exphormer is ahead of HOPPER on Paris, Shanghai, and Los Angeles, by 0.3, 0.8, and 2.7 points. However, HOPPER performs more uniformly across the four cities. On London, the largest graph (569k nodes, diameter 404), HOPPER is the best model while Exphormer falls 6.0 points behind it. HOPPER’s largest gap to the best model on any city is 2.7 points, against 6.0 for Exphormer, and HOPPER has the highest mean accuracy over the four cities (60.2 against 59.7 for Exphormer).

On when and why HOPPER is most beneficial, our results point to three settings. First, when the target depends on structure many hops away where one cannot rely on a fixed propagation operator. On ECHO-Synth, HOPPER has the lowest SSSP error and the lowest ECC MSE among models that are not given precomputed distances, roughly halving LGSM’s MSE on both, and it improves on Exphormer by a wide margin on all three tasks. Second, when a fixed propagation rule is a poor match for the graph. On City-Networks, HOPPER improves on LGSM, which shares its backbone but fixes the propagation rule, by 21.5 points on London and 32.4 on Shanghai. Third, when graphs differ in structure, the hypernetwork adapts the coefficients to each input graph. Our new ablation (response to Reviewer 8qtd, W1) shows that removing this graph conditioning increases DIAM MAE by 30% and SSSP MSE by nearly 3x.

HOPPER is less beneficial when local information already determines most labels, as on City-Networks where label homophily is 0.70 to 0.76 (Table 5), and when global shortcut edges, as used by Exphormer, are enough to reach the relevant nodes. We will add this discussion to the revised manuscript.

W4. We thank the reviewer for pointing out the inconsistent baselines. We have now evaluated Exphormer on ECHO-Synth and LGSM on City-Networks, each over three seeds.

The ECHO-Synth results, including Exphormer, are in the table in our response to Reviewer mBfT’s W2. HOPPER outperforms Exphormer on all three tasks, lowering MSE by 2.3x on DIAM (3.200 vs 7.297), 1.9x on ECC (6.571 vs 12.662) and by three orders of magnitude on SSSP (0.021 vs 27.210), so Exphormer’s strength on City-Networks does not carry over to ECHO-Synth. HOPPER is not the best model on every ECHO-Synth task, however. LGSM is slightly better on DIAM, and GSM++ with its distance-based positional encoding is better on all three tasks, which we discuss in the same response.

The City-Networks results for LGSM are in the table in our response to Reviewer 8qtd’s W2. HOPPER improves on LGSM in every city, by 2.9 points on Paris, 5.5 on Los Angeles, 21.5 on London, and 32.4 on Shanghai.

Regarding the minor comment, we agree that inspecting the learned coefficients would be informative. In the revised manuscript, we will add per-hop heatmaps of the learned αA\alpha_A, αD\alpha_D, αI\alpha_I, and β\beta for each task, compare them with the GCN and Chebyshev priors, and report how much they vary across graphs. Our new graph-conditioning ablation (response to Reviewer 8qtd, W1) gives a first insight. Forcing the coefficients to be identical across graphs increases DIAM MAE by 30% and SSSP MSE by nearly 3x, which indicates that the learned coefficients vary across graphs in a useful way.

We hope our response clarifies our use of LGSMs in this work, the significance of our contribution, and our empirical results. We would be very happy to discuss further. Thank you again for your time and consideration!

Reviewer_mBfTOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

This paper introduces HOPPER, a learnable hop extraction framework for linearized graph sequence models, aiming to better capture long-range dependencies. The method uses a hypernetwork conditioned on graph information and hop position to generate adaptive propagation coefficients. The resulting hop representations are refined through a gated attention mechanism and processed by a Mamba-based sequence model. The authors provide theoretical analyses of expressivity, stability, and long-range sensitivity, and evaluate HOPPER on synthetic graph-distance tasks, long-range interaction modeling, and urban road networks.

Critical strengths
  1. The problem it addresses is very specific, and it solved it using an interesting method.
  2. The theoretical derivation is quite comprehensive.
Critical weaknesses
  1. The model performs well on tasks related to graph structure, but its performance on real-world tasks is relatively modest.
  2. The paper includes relatively recent baselines such as SWAN and PH-DGN, but it does not directly compare with MP-SSM and GSM++, which are mentioned in the appendix. It also does not discuss the similarities between DIGRAM and HOPPER in their use of hop sequences combined with Mamba. A clearer discussion of these methods would help readers understand HOPPERs distinct contributions.
  3. Regarding the figures, I think larger fonts, clearer legends, and more readable error bars would help readers quickly compare different methods and results.
Questions for authors
  1. Could the authors explain why HOPPERs reported ability to capture long-range dependencies does not consistently translate into better performance on downstream tasks? Evaluating a wider range of downstream tasks would also make the evidence more convincing.
  2. All tasks in ECHO-Synth focus on graph distance, while the labels in the urban network experiments are constructed using eccentricity-related indicators. To what extent do the authors believe these experiments support HOPPERs applicability to a broader range of long-range graph learning problems?
  3. Other architectures, such as GOFA, LLM-BP, and other LLM-based approaches, have also been proposed for related graph problems. To what extent are these methods affected by long-range dependencies? On comparable graph tasks, what are the main advantages of HOPPER over these approaches? A brief discussion would help clarify where HOPPER is particularly useful.
6 comments
AuthorsOpenReview ↗

Response to Reviewer mBfT (Part 1/3)

​​Dear reviewer, thank you for your helpful feedback. We are glad that you found our proposed approach to be interesting and our theoretical analysis to be comprehensive. We also thank you for your comments and suggestions, and would like to respond to the points you raised below.

W1. We thank the reviewer for this comment. We agree that HOPPER’s margins on City-Networks are smaller than on ECHO-Synth, and we would like to clarify HOPPER’s performance on City-Networks. Exphormer indeed surpasses HOPPER on Paris, Shanghai, and Los Angeles. That being said, our claim is about what these graphs require and how consistently each model handles that.

  • Graph topology: City-Networks are sparse road graphs with average degree 2.7 to 3.2, clustering around 0.03 to 0.04 and diameters between 121 and 404 hops (Tables 4 and 5). Each label is the weighted eccentricity of a node within its 16-hop neighborhood [1], so a model has to carry distance information across many hops of a graph with very few shortcuts. Topology also varies from city to city, which makes it unlikely that a single fixed propagation rule suits all four graphs.

  • Learned versus fixed propagation: To test this directly, we evaluated LGSM with non-backtracking propagation through HOPPER’s own training pipeline, with the hypernetwork and attention components switched off, and NAGphormer, which builds per-node hop sequences but aggregates them with a fixed rule (full table in our response to Reviewer 8qtd’s W2). HOPPER improves on LGSM (NBT) in every city, by 2.9 points on Paris, 5.5 on Los Angeles, 21.5 on London, and 32.4 on Shanghai. The two models share the Mamba backbone, the graph-mixing blocks, and the training setup, so the gap comes from HOPPER’s adaptive extraction (the learned hop coefficients and the feature-attention correction) rather than from the sequence model. NAGphormer stays between 30 and 45 percent on all four cities.

  • Consistency across cities: When averaged across all four cities in Table 2, HOPPER has the highest mean accuracy (60.2, against 59.9 for GraphSAGE and 59.7 for Exphormer) and is within 2.7 points of the best model on every city. Exphormer, the strongest model on three cities, falls 6.0 points below HOPPER on London. We note that when compared with LGSM, one can clearly see the benefit of adaptive extraction over fixed propagation. We will add this discussion to the revised manuscript.

W2. We thank the reviewer for raising this concern. Neither MP-SSM nor GSM++ has public code available, so we re-implemented both using the implementation details from their papers to the best of our ability. We evaluated them on ECHO-Synth under the official ECHO baseline protocol, selecting hyperparameters on validation loss over a small grid and reporting three seeds. For GSM++, we use the HAC-based tokenization that its authors recommend for global tasks, together with its hierarchical positional encoding (PE), and we also report GSM++ without this PE. The table also includes Exphormer, as requested by Reviewer Nuo4.

ModelDIAM MSE ↓DIAM MAE ↓ECC MSE ↓ECC MAE ↓SSSP MSE ↓SSSP MAE ↓
Exphormer7.297 ± 0.3261.701 ± 0.02312.662 ± 0.3702.715 ± 0.05827.210 ± 0.2483.771 ± 0.027
MP-SSM6.962 ± 3.8511.686 ± 0.64734.816 ± 2.5864.855 ± 0.17920.655 ± 12.3583.238 ± 1.299
GSM++0.489 ± 0.1760.418 ± 0.0740.137 ± 0.0490.214 ± 0.0380.0016 ± 0.00050.024 ± 0.005
GSM++ w/o hierarchical PE5.376 ± 0.2811.325 ± 0.0717.758 ± 0.4191.801 ± 0.06511.825 ± 0.0782.216 ± 0.017
LGSM3.089 ± 0.3890.859 ± 0.04413.549 ± 0.5392.430 ± 0.0700.040 ± 0.0080.076 ± 0.009
HOPPER (ours)3.200 ± 0.5280.973 ± 0.0406.571 ± 2.6561.820 ± 0.3860.021 ± 0.0080.035 ± 0.002

HOPPER outperforms MP-SSM on all three tasks, lowering MSE by 2.2x on DIAM, 5.3x on ECC, and roughly 1000x on SSSP. MP-SSM behaves like the other baselines in Table 1 apart from LGSM, whose ECC MSE values all fall between 32 and 44.

[1] Liang, H., Sáez de Ocáriz Borde, H., Sripathmanathan, B., Bronstein, M., & Dong, X. (2026). Towards quantifying long-range interactions in graph machine learning: A large graph dataset and a measurement. International Conference on Learning Representations (ICLR).

AuthorsOpenReview ↗

Response to Reviewer mBfT (Part 2/3)

W2 (cont). GSM++ is the strongest model on all three tasks, and its hierarchical PE explains most of this. The PE adds the shortest-path distance between every pair of tokens at every level of the hierarchy as an attention bias, and at the finest level these are the exact node-to-node shortest-path distances. Diameter, eccentricity, and SSSP are all maxima or entries of that distance matrix, so the PE already encodes the quantity each task asks for. HOPPER, like LGSM, takes no positional or structural encodings as input. [2] highlight this as a property of LGSMs in their Peptides comparison, where all message-passing baselines use such encodings. HOPPER therefore has to recover distance information through propagation, and the like-for-like comparison is GSM++ without its PE. Without the PE, GSM++ falls well behind HOPPER on DIAM and SSSP and is on par with it on ECC. Precomputing all-pairs distances also needs an n×nn \times n matrix, which ranges from about 13 billion entries for Paris to about 324 billion for London. That rules out this PE on City-Networks, where HOPPER runs directly on the full graphs. We note that both models are our re-implementations based on their respective papers.

Regarding DIGRAM, we agree that it is closely related and will cite and discuss it. DIGRAM builds one token per hop with a fixed, parameter-free magnetic-Laplacian propagation and reads the token sequence with Mamba. It is designed for directed graphs, where the magnetic Laplacian encodes edge direction. On undirected graphs, which cover all of our benchmarks, the magnetic Laplacian reduces to the ordinary normalized adjacency, so DIGRAM’s hop tokens become fixed adjacency powers. This is the same fixed-propagation setting as LGSM, which HOPPER’s recurrence can recover (Theorem 4.3). HOPPER differs in that a hypernetwork conditioned on the input graph generates the propagation coefficients for each hop, and feature attention corrects them, so the extraction rule itself is learned. The comparison with LGSM in our response to Reviewer 8qtd’s W2 shows the effect of this difference on City-Networks. We will add this discussion to the related work section.

[2] Mathys, J., Rohner, B., Peltonen, S., & Wattenhofer, R. (2026). From Message-Passing to Linearized Graph Sequence Models. arXiv preprint arXiv:2605.12358.

W3. We thank the reviewer for this suggestion. We will include larger fonts, clearer legends, and more readable error bars across all our figures in the revised manuscript so readers can quickly compare different methods and results.

Q1. We thank the reviewer for this question. We see three reasons, which connect to our answers to W1 and Q2.

  • First, most real-world benchmarks mix local and long-range signal, and local signal is often enough to do well. On City-Networks, label homophily is 0.70 to 0.76 (Table 5), so neighboring junctions usually share a class and local aggregation already recovers much of the label, which is why GraphSAGE and ChebNet are strong there. Long-range capacity can only add the part of the signal that local models miss, so margins are smaller than on ECHO-Synth, where the targets cannot be computed locally.

  • Second, when fixed propagation is a poor fit for the graph, adaptive extraction benefits real graphs. HOPPER improves on LGSM, which uses the same backbone with fixed non-backtracking propagation, by 2.9 to 32.4 accuracy points across the four cities, and it has the highest mean accuracy over the four cities in Table 2.

  • Third, models with explicit global shortcuts can do well on some graphs without long-range propagation. Exphormer adds expander edges and virtual nodes, which helps on Paris, Shanghai, and Los Angeles, but its accuracy falls 6.0 points below HOPPER on London, the largest graph with a diameter of 404 hops.

We agree that a wider range of downstream tasks would make the evidence more convincing. In this rebuttal, we have added comparisons with LGSM, NAGphormer, MP-SSM, and GSM++ and a new ablation of graph conditioning, and the paper already includes LRIM-16, whose targets come from long-range physical interactions rather than graph distance. We intend to extend the evaluation to further long-range benchmarks in the revised manuscript.

AuthorsOpenReview ↗

Response to Reviewer mBfT (Part 3/3)

Q2. We thank the reviewer for this question. The City-Networks labels are also defined through graph distance. Following [1] (Eq. 1), each node vv is labeled by its local eccentricity

\begin{align} \hat{\varepsilon}_{k}(v) = \max_{u \in \mathcal{N}_{k}(v)} \rho_{w}(v,u), \quad \rho_{w}(v,u) = \min_{\pi \in P(v,u)} \sum_{e \in \pi} w(e), \end{align}

where Nk(v)\mathcal{N}_{k}(v) is the set of nodes within kk hops of vv, P(v,u)P(v,u) is the set of paths between vv and uu, w(e)w(e) is the road length of edge ee, and ρw(v,u)\rho_{w}(v,u) is the resulting weighted shortest-path distance. The benchmark sets k=16k = 16 and splits the values of ε^16\hat{\varepsilon}_{16} into 10 quantiles that serve as the class labels. The City-Networks task is therefore a weighted, 16-hop counterpart of ECHO-Synth's eccentricity task.

These two benchmarks also differ in their primary goals. ECHO-Synth is synthetic and small, with about 84 nodes per graph, unweighted edges and random scalar node features, so it isolates whether a model can move distance information over many hops. City-Networks are real road networks with 114k to 569k nodes and diameters of 121 to 404 hops. Here, a model is not told the label's hop radius and has to infer accessibility from distant structure together with spatial features such as location and road type. This makes City-Networks larger and harder by construction. Doing well on both shows that HOPPER's extraction carries over from fairly small-scale synthetic graphs to real graphs at scale. We agree that both benchmarks are distance-based and will state this scope clearly in the revised manuscript.

[1] Liang, H., Sáez de Ocáriz Borde, H., Sripathmanathan, B., Bronstein, M., & Dong, X. (2026). Towards quantifying long-range interactions in graph machine learning: A large graph dataset and a measurement. International Conference on Learning Representations (ICLR).

Q3. We thank the reviewer for pointing us to these methods. GOFA [1] and LLM-BP [2] are designed for text-attributed graphs, where every node carries natural-language text that an LLM reads. GOFA adds GNN layers to a pretrained LLM and is pretrained on text graphs such as MAG240M. LLM-BP encodes node text with an LLM and runs belief propagation for zero-shot node classification. Both rely on that text as their main input, and their goal is transfer across text domains and tasks rather than long-range propagation. GOFA works on small sampled subgraphs (up to 3 hops in its supervised setting) and LLM-BP uses five message-passing steps, so neither is built to carry information over tens of hops.

ECHO-Synth and City-Networks have numeric node features and no text, so these methods cannot be applied to them as they are, and we consider them outside the scope of this work. HOPPER targets graphs without text where the target depends on structure many hops away, and it runs on graphs with hundreds of thousands of nodes without an LLM. Combining HOPPER’s learned hop sequences with an LLM-based encoder for text-attributed graphs is an interesting direction that we will note in the revised manuscript.

[1] Kong, L., Feng, J., Liu, H., Huang, C., Huang, J., Chen, Y., & Zhang, M. (2025). GoFA: A generative one-for-all model for joint graph language modeling. International Conference on Learning Representations (ICLR).

[2] Wang, H., Liu, S., Wei, R., & Li, P. (2025). Generalization principles for inference over text-attributed graphs with large language models. International Conference on Machine Learning (ICML).

We will incorporate all rebuttals into our manuscript to improve its quality. We hope our response helps clarify the significance of our contribution, and we would be very happy to discuss further. Thank you again for your time and consideration!

Reviewer_8qtdOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The authors propose HOPPER, an extension of Linearized Graph Sequence Models (LGSMs), where HOPPER replaces LGSM's fixed hop-sequence extractor with a learnable one, including four components: 1) a permutation-invariant graph summary module, 2) hop-conditioned coefficients generator using the graph summary and a learnable hop embedding, 3) a linear recurrence over the adjacency, degree, and identity operators using these coefficients, and 4) a hop-specific feature-based attention module that modifies the corresponding hop's extracted state. The authors then prove permutation equivariance, show the polynomial structure and finite-hop support of the structural recurrence, and show that non-backtracking propagation is a special case, while adjacency and Chebyshev propagation are covered with an augmented recurrence. They also give sensitivity and spectral-preservation results for Chebyshev propagation. Experiments on ECHO-SYNTH for long-range graph prediction task show that their method outperforms LGSM and other baselines on two out of three tasks. Results on large-scale dataset (up to 569k nodes) City-Networks for node classification task show their method (with WildCat attention) is highest for one out of four cities network while remain competitive for others. Ablations examine the contributions of neighborhood information in the graph summary, hypernetwork-generated coefficients, and the feature-attention correction show hypernetwork is the most contributing component. Analysis on LRIM-16 examines the effect of the recurrence window.

Critical strengths
  • The idea of extending LGSM model with learnable hop-feature extractor is intuitive and clearly motivated.
  • Substantial improvements on two long-range prediction tasks (ECC MSE 6.57 vs 13.55, SSSP MSE 0.021 vs 0.040)
  • Detail information on the model architecture, training and hyperparameter and code available for reproducibility.
  • Theoretical results are informative, with clear proofs and derivations in the appendix.
Critical weaknesses
  • The contribution of graph conditioning is not examined in the ablation studies (removed together with the hypernetwork in no-hyper config).
  • LGSM performance is not reported in Table 2, also the highest performance on London is within the std compare to GraphSAGE, providing limited evidence for the adaptive extraction.
  • The sensitivity and spectral-preservation results concern fixed Chebyshev propagation, the paper does not establish that the learned recurrence satisfies the same stability constraint.
  • Authors mentioned in appendix B that experiments use normalized recurrence (eq 10) leaving the Theorem 4.2 and 4. 3 using the "exact" version without stating which results still hold, and which breaks.
  • Missing comparison of the number of parameters for each model, and no measured training time, inference time or memory usage, which would show if the benefits outweigh the extra cost.
Questions for authors
  • Please address the above weaknesses
  • How was the per-task learning rate in Table 6 selected?
  • NAGphormer [1] also build per-node hop sequences feeding to attention networks, should be cited and compared to.

[1] Chen, Jinsong, et al. "NAGphormer: A tokenized graph transformer for node classification in large graphs." arXiv preprint arXiv:2206.04910 (2022).

7 comments
AuthorsOpenReview ↗

Response to Reviewer 8qtd (Part 1/4)

Dear reviewer, thank you for your helpful feedback. We are glad that you found our proposed learnable hop-sequence extraction approach to be intuitive and well-motivated, and that you found our theoretical results to be informative and our experimental improvements to be substantial. We also thank you for your comments and suggestions, and would like to respond to the points you raised below.

W1. We thank the reviewer for this observation. We would like to refer to the no-neighbor ablations in Figures 2 and 4, where we ablate the contribution of neighborhood node features to the graph summary. Here we remove the Hnbr=ArwH\mathbf{H}_{\mathrm{nbr}}=\mathbf{A}_{\mathrm{rw}}\mathbf{H} from the graph-summary construction while retaining the hypernetwork and its hop-dependent coefficient generation. As a result, the propagation coefficients are still adaptive to the input graph’s node features but do not incorporate any information about the neighborhood structure through the graph summary.

We acknowledge that this ablation only produces a small, statistically insignificant performance degradation which suggests that perhaps incorporating neighborhood-aggregated features into the graph summary provides limited benefit.

To examine graph conditioning directly, we ran an additional ablation that keeps the hypernetwork but removes its dependence on the input graph. The graph summary hgraphh_{\mathrm{graph}} is replaced by a single learned vector of the same size that is shared by all graphs, so the hypernetwork still produces different coefficients for each hop, but the same coefficients for every graph. This separates graph conditioning from the hypernetwork itself, which the no-hyper ablation removes together. Everything else, along with the training procedure, is unchanged, and all runs reported below use 560 epochs as in our other DIAM ablations. Results are over three seeds.

ModelDIAM MSEDIAM MAESSSP MSESSSP MAE
HOPPER3.200 ± 0.5280.973 ± 0.0400.021 ± 0.0080.035 ± 0.002
HOPPER w/o graph conditioning4.518 ± 0.7591.262 ± 0.1090.059 ± 0.0150.070 ± 0.018

Removing graph conditioning increases DIAM MAE by 30% and MSE by 42%, and on SSSP it nearly triples the MSE and doubles the MAE. Freezing the coefficients entirely (no-hyper, Figure 4) raises DIAM MAE to about 2.3. Due to time constraints we are still running this ablation on the ECC task with initial validation MAE and MSE values pointing towards the same conclusion as the DIAM and SSSP results. We will include the full results table in the revised manuscript.

Learning per-hop coefficients therefore recovers most of the gain over fixed propagation, and conditioning them on the input graph accounts for the rest. Together with the no-neighbor ablation above, this suggests that what matters is that the coefficients depend on the graph, while the one-hop neighborhood features pooled into the summary add little. We will add this to the revised manuscript.

W2. We thank the reviewer for bringing up the original LGSM performance on the City-Networks benchmark. To address this, we have evaluated LGSM with non-backtracking (NBT) propagation on three seeds along with NAGphormer on the City-Networks benchmark. The results are summarized below:

ModelParisShanghaiLALondon
HOPPER54.8 ± 0.669.4 ± 0.561.1 ± 0.355.5 ± 0.2
LGSM (NBT)51.91 ± 0.237.0 ± 0.355.63 ± 0.234.01 ± 0.04
NAGphormer36.72 ± 0.144.47 ± 0.0737.83 ± 0.430.24 ± 0.46

HOPPER substantially outperforms both LGSM (NBT) and NAGphormer across all cities. These additional comparisons provide stronger empirical evidence for the effectiveness of HOPPER relative to existing fixed-propagation LGSMs and alternative graph sequence models.

Regarding HOPPER's performance being within one standard deviation of GraphSAGE on London, we would like to clarify that our intention is to demonstrate that HOPPER is more generally performant across a wider variety of city networks at capturing long-range dependencies as compared to existing MPNNs and Graph Transformers. In light of the additional LGSM (NBT) and NAGphormer results, we believe there is empirical evidence for the benefits of learnable hop extraction, particularly on Shanghai and London, where both baselines substantially underperform HOPPER. These results are especially interesting given the sparse, low-clustering, and large-diameter topology of the City-Networks graphs, where fixed propagation mechanisms may struggle to preserve task-relevant structural information across multiple hops. In particular, the substantial underperformance of LGSM (NBT) on Shanghai and London suggests that non-backtracking propagation may not be well suited to these graph structures, whereas HOPPER's adaptive, hop-dependent extraction offers greater flexibility in learning appropriate propagation rules.

AuthorsOpenReview ↗

Response to Reviewer 8qtd (Part 2/4)

W3. We thank the reviewer for raising this important distinction. We agree that the sensitivity and spectral-preservation results (Theorem 4.4 and 4.5 respectively) pertain to the fixed Chebyshev propagation rather than establishing these properties uniformly over the coefficients produced by our learned hypernetwork. Our theoretical motivation is to indeed demonstrate that HOPPER is able to represent propagation mechanisms that can achieve improved long-range sensitivity while preserving spectral stability. In particular, our analysis in Theorem 4.3 shows that HOPPER can recover Chebyshev propagation which we additionally prove with Theorem 4.4 and 4.5 is able to improve long-range sensitivity and preserve spectral stability compared to adjacency propagation i.e. S(ℓ)=AℓH\mathbf{S}^{(\ell)} = \mathbf{A}^{\ell} \mathbf{H} for fixed H∈Rn×d\mathbf{H} \in \mathbb{R}^{n \times d} where A∈Rn×n\mathbf{A} \in \mathbb{R}^{n \times n} is the adjacency matrix. We are also able to recover the propagation mechanisms used in [1]. We note that establishing stability and spectral preservation for the learned recurrence would require additional assumptions and possibly explicit constraints on the learned coefficients which in practice may be hard to enforce and theoretically conservative which is why we have taken the theoretical route illustrated in the current manuscript.

We will clarify this in the revised manuscript and we hope that this helps the reviewer understand the goal of the theoretical results and that HOPPER indeed can recover propagation mechanisms which subsequently improve long-range sensitivity and preserve spectral stability.

[1] Mathys, J., Rohner, B., Peltonen, S., & Wattenhofer, R. (2026). From Message-Passing to Linearized Graph Sequence Models. arXiv preprint arXiv:2605.12358.

W4. We thank the reviewer for this question. Indeed, Eq. (6) is the "exact" version of the recurrence we use for the main theorems, whereas Eq. (10) is the normalized recurrence we use for the experiments. We would like to note that we highlight the relationship between the exact and normalized propagation operators in Lines 285–290. Specifically, Arw=D−1/2AsymD1/2\mathbf{A}_{\mathrm{rw}} = \mathbf{D}^{-1/2}\mathbf{A}_{\mathrm{sym}}\mathbf{D}^{1/2}, so under the change of coordinates U~(k)=D1/2U(k)\widetilde{\mathbf{U}}^{(k)} = \mathbf{D}^{1/2}\mathbf{U}^{(k)}, propagation under Arw\mathbf{A}_{\mathrm{rw}} is equivalent to propagation under Asym\mathbf{A}_{\mathrm{sym}}.

With the normalized recurrence, several theoretical properties still hold. In particular, Theorem 4.1 (permutation equivariance) still holds, and Theorem 4.2 extends simply by taking P=D−1A\mathbf{P} = \mathbf{D}^{-1}\mathbf{A} and R=I−D−1\mathbf{R} = \mathbf{I} - \mathbf{D}^{-1}. Importantly, Chebyshev propagation is still recoverable by the normalized recurrence. Taking P=D−1A\mathbf{P} = \mathbf{D}^{-1}\mathbf{A} and selecting the coefficients to realize U(k)=2PU(k−1)−U(k−2)\mathbf{U}^{(k)} = 2\mathbf{P}\mathbf{U}^{(k-1)} - \mathbf{U}^{(k-2)}, with U(0)=H\mathbf{U}^{(0)} = \mathbf{H} and U(1)=PH\mathbf{U}^{(1)} = \mathbf{P}\mathbf{H}, yields U(k)=Tk(P)H\mathbf{U}^{(k)} = T_k(\mathbf{P})\mathbf{H}. Since P=D−1/2AsymD1/2\mathbf{P} = \mathbf{D}^{-1/2}\mathbf{A}_{\mathrm{sym}}\mathbf{D}^{1/2}, Chebyshev propagation remains non-expansive with respect to the degree-weighted norm ∥H∥D,F=∥D1/2H∥F\lVert \mathbf{H} \rVert_{\mathbf{D},F} = \lVert \mathbf{D}^{1/2}\mathbf{H} \rVert_{F}. Thus the long-range sensitivity and spectral preservation results also hold for the normalized recurrence under this norm.

We will make this explicit in the revised manuscript by adding a remark and additional proof details in the appendix. We hope this clarifies the relationship between the normalized and the "exact" recurrences and shows there is not a large disconnect between the experimental setup and the theoretical results established for the "exact" recurrence.

AuthorsOpenReview ↗

Response to Reviewer 8qtd (Part 3/4)

W5. We thank the reviewer for this suggestion. The tables below report the number of parameters, training time per epoch, inference time, and peak GPU memory. On ECHO-Synth, every model was measured alone on a single NVIDIA A10 GPU on the DIAM task, with its own training batch size. LGSM is measured with the same backbone as HOPPER and only the propagation rule changed, so the difference between these two rows is the cost of adaptive extraction.

ECHO-Synth (DIAM, one A10 GPU)

ModelParamsBatch sizeTrain time/epochTest inference (2,160 graphs)Peak GPU memory
MP-SSM12k2561.4 s0.43 s0.17 GiB
GSM++188k2566.2 s0.84 s*1.67 GiB
LGSM (NBT)418k32110 s8.3 s8.9 GiB
HOPPER807k32173 s9.9 s11.5 GiB

*plus a one-time all-pairs shortest-path preprocessing step for its hierarchical positional encoding.

HOPPER and LGSM are the most expensive models per epoch on ECHO-Synth as both build a 40-hop sequence for every node, process it with Mamba, and use a smaller batch size. Relative to LGSM with the same backbone, adaptive extraction costs 1.6x the training time per epoch, 1.3x the memory, and 1.2x the inference time. In return, HOPPER roughly halves LGSM’s MSE on ECC (6.571 vs 13.549) and SSSP (0.021 vs 0.040). MP-SSM and GSM++ are much cheaper per epoch, but MP-SSM has far higher error than HOPPER on all three tasks. GSM++’s advantage comes from a precomputed all-pairs shortest-path encoding, which needs memory quadratic in the number of nodes. The MP-SSM and GSM++ rows use our re-implementations (see our response to Reviewer mBfT, W2).

City-Networks (London)

ModelParamsGPUTrain time/epochValidation/Test inferencePeak GPU memory
NAGphormer2,133,964A100 80GB (SXM4 / PCIe)2.08 s8.09 s2.86 GiB
LGSM (NBT)1,501,179A100 80GB PCIe28.01 s3.62 s56.37 GiB
HOPPER2,688,665H200 NVL15.57 s2.06 s73.86 GiB

The results show an accuracy–memory trade-off. NAGphormer’s precomputed hop tokens and minibatched Transformer support inexpensive training, consistent with its London runtime of 2.08 s/epoch and 2.86 GiB memory footprint, although preprocessing is excluded. LGSM (NBT) processes topology-defined non-backtracking sequences with a learned Mamba backbone; it improves accuracy over NAGphormer on three cities but underperforms on Shanghai, suggesting that this propagation bias is not uniformly effective. HOPPER generalizes fixed hop extraction through graph and hop-conditioned propagation and feature attention, achieving the highest accuracy across all four cities. On London, HOPPER improves accuracy from 34.01% to 55.5%, while increasing peak memory by approximately 31% and parameters from 1.50M to 2.69M. HOPPER therefore offers stronger predictive performance at a higher memory cost.

Q1. We thank the reviewer for this point. The per-task learning rate was selected via a grid search across learning rates from 11–6×10−46 \times 10^{-4}. This range was determined based on a small interval around the learning rates used by the original LGSM on this benchmark. We then chose the learning rate that led to the lowest validation MSE. We will clarify this in the revised manuscript.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Summary of our rebuttals

We sincerely thank all reviewers for their thoughtful feedback and suggestions. We are glad that the reviewers found HOPPER intuitive and well-motivated, our theoretical analysis informative, and our experimental improvements on long-range graph learning tasks meaningful.

In response to the reviews, we have substantially expanded our experimental evaluation, provided additional ablation studies and baseline comparisons, and clarified the theoretical scope and methodological contributions of our work. In particular we have addressed the following points:

  • We conducted an additional ablation study isolating the contribution of graph conditioning, demonstrating that removing graph conditioning increases DIAM MAE by 30% and nearly triples SSSP MSE (see Reviewer 8qtd W1 and Reviewer Nuo4 W3).

  • We expanded our experimental comparisons to include LGSM and NAGphormer on City-Networks and Exphormer, MP-SSM, and GSM++ on ECHO-Synth. These results provide stronger evidence for the benefits of adaptive hop extraction while clarifying the role of structural positional encodings and the settings in which HOPPER is most effective (see Reviewer 8qtd W2/Q2, Reviewer mBfT W1/W2, and Reviewer Nuo4 W3/W4).

  • We clarified the scope of our theoretical guarantees, particularly the distinction between fixed Chebyshev propagation and learned coefficients, and provided additional derivations showing how our theoretical results extend to the normalized recurrence used in our experiments (see Reviewer 8qtd W3/W4 and Reviewer Nuo4 W2).

  • We further explained the methodological contributions of learnable hop-sequence extraction relative to existing graph sequence models and how adaptive sequence extraction could potentially extend beyond LGSMs to other graph learning architectures (see Reviewer Nuo4 W1/W2 and Reviewer mBfT W2).

  • We provided additional computational comparisons, clarified the scope and limitations of our empirical evaluation, will improve figure readability, and include further analysis of learned propagation coefficients in the revised manuscript (see Reviewer 8qtd W5/Q1, Reviewer mBfT Q1/Q2/Q3/W3, and Reviewer Nuo4 W4).

We believe these additional experiments and clarifications substantially strengthen the manuscript and provide a more complete understanding of the theoretical and practical implications of our work. We will incorporate these improvements into the revised manuscript. We sincerely thank the reviewers again for their time, careful consideration, and valuable suggestions and hope they can consider raising their scores in light of our responses.

We would also like to sincerely thank the Area Chair for handling our submission and overseeing the review process. We hope that the additional results and clarifications provided in our responses will be taken into consideration in the final evaluation, and we would be grateful for the Area Chair's support of our work.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.