- 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
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. for fixed where 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.
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 , , , and 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!
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).