Graph Adaptive Autoregressive Moving Average Models

We thank the Reviewer for the thorough and constructive feedback. We have carefully addressed all concerns and believe the revisions have strengthened our paper. We hope our responses are satisfactory and that you will consider updating your score.

Regarding R1-R6: The Reviewer is correct that prior works have studied converting graphs into sequences, which we now cite in the revised paper. However, as noted, our focus is on Graph State Space Models, making those works only tangentially related. Our aim is to design a graph SSM that enables long-range processing while preserving permutation equivariance. For instance, methods like R3–R4 are only equivariant in expectation, and works like R4–R6 treat graphs strictly as sequences. In contrast, we highlight that a key challenge in applying SSMs to graphs is that graphs are not inherently sequential. To clarify this distinction, we have revised our paper to include this discussion. Thank you.

Regarding R5-R10: We refer the Reviewer to Appendix A, where we discuss GNNs as dynamical systems and recent graph recurrent methods. Following your suggestion, we now cite and highlight the differences with R5–R10 in the revised paper.

Regarding MixHop: We refer the Reviewer to the related works section, where we discuss multi-hop architectures like JKNet and DRew. In the revised paper, we added a discussion on MixHop. As shown in Tables 2 and 8, GRAMA outperforms MixHop, and our ablation studies (Tables 9–11) show that even without the selective mechanism, GRAMA still performs better. This highlights that the gain comes not only from selectiveness but also from GRAMA’s overall design: unlike MixHop’s dense, non-recurrent projection, GRAMA uses a recurrent, non-dense aggregation inspired by dynamical systems and modern RNNs. We have added this discussion and further comparisons, including non-selective GRAMA, to the revised paper. The original results are also summarized in the table below.

Regarding complexity: The Reviewer is correct that GRAMA maintains a feature matrix of size $R \\times n \\times d$, with $R = L$. However, unlike MixHop—which assigns learnable weights per layer and uses a dense layer with space complexity $L \\cdot d^2$—GRAMA is more efficient. In the non-selective (naive) variant, GRAMA learns only $2L$ parameters per block, which is highly scalable since $L \\ll d$ and $L \\ll n$. In the selective variant, parameter count depends only on $d$, with space complexity $d^2$; the $L$ dependence appears only in the $L^2$ complexity of the sequence input, as discussed in Appendix E.3. We have clarified this distinction in the revised paper and, following your suggestion, added a MixHop comparison on OGBN-Arxiv, further demonstrating GRAMA’s effectiveness.

Regarding R13-R15: In the original paper, we compare GRAMA with GOAT and Exphormer in Tables 5 and 6, where GRAMA outperforms both. We appreciate the reviewer's suggestion and now include additional comparisons with Polynormer. Together, these results highlight GRAMA’s strong performance relative to other leading methods.

Regarding runtimes: As shown in Table 9, GRAMA’s runtime scales proportionally with its backbone. Designed to enhance various GNNs, GRAMA achieves strong performance, especially with backbones like GatedGCN or GPS. We recognize that in some cases, lower computational cost may be important. To address this, one can use the naive ARMA coefficient learning (Section 3.2) or a lighter backbone such as GCN—both of which reduce overhead while still benefiting from GRAMA. Our experiments show these variants maintain strong improvements over their backbones and remain competitive with other methods at lower runtime. We also report GRAMA runtimes with GatedGCN and GPS in the table below and in the revised paper. The key takeaway is that GRAMA offers a flexible and scalable trade-off between efficiency and performance.

We thank the Reviewer for acknowledging the “strong theoretical foundation” with “detailed proofs”, with an “exceptionally thorough” experimental section. We would also like to express our gratitude for the thoughtful comments and feedback, to which we have done our best efforts to respond, below. We hope that you find our responses satisfactory and that you will consider revising your score.

Regarding GNN backbones: Thank you for the comment. We selected these backbones because they are widely used and represent both linear MPNNs and graph transformers. Our aim was to demonstrate GRAMA's versatility across backbone types, which is reflected in the consistent improvements over both the GNN backbones and other methods. While linear MPNNs and graph transformers differ in computational complexity, our results show that strong performance is achievable with any of the selected backbones. Overall, our experiments with three popular backbones on 22 datasets—plus 4 more added in the rebuttal in response to Reviewers mg6D and c8Wb—highlight the effectiveness and generality of GRAMA.

Regarding architectural differences: We thank you for the comment. In our paper, we compare both the quantitative results (i.e., downstream performance) of GRAMA and existing methods, primarily focusing on graph SSMs, as well as the qualitative (i.e., architectural and theoretical) differences. We kindly note that in Section 1, Section 2, Section 3, as well as Appendix A, we state the main differences between GRAMA and other graph SSMs: (i) GRAMA can process sequences which are beyond pairwise interactions, different than the graph SSM in Huang et al. (2024); and (ii) GRAMA is permutation-equivariant, while other graph SSMs like in Behrouz & Hashemi (2024) and Wang et al. (2024a), are not permutation-equivariant and are based on heuristics that order the graph nodes to obtain a sequence. Nonetheless, following your suggestion, we have revised our paper to better reflect and highlight these differences. We also highlighted differences between other methods like GRIT and GRED, in our response to Reviewer mg6D. Regarding the integration with GNNs, we kindly note that Figure 1 illustrates our method and its ability to integrate with potentially any GNN backbone. This is also reflected by our experiments with different types of backbones such as GCN, GatedGCN, GPS. To fully accommodate your comment, we revised our paper to include and expand the discussions in our response.

Regarding datasets: Thank you for the comment. Our main goal was to evaluate GRAMA’s long-range effectiveness across multiple benchmarks, including Graph Property Prediction (GPP) and LRGB. As noted in Appendix D, GPP graphs are drawn from diverse distributions (e.g., Barabasi-Albert, tree, caveman, line), while LRGB graphs represent molecules with inherently different structures. Additionally, the five heterophilic tasks involve nodes of the same class being distantly connected. These choices ensure benchmark diversity beyond a single application domain. Following suggestions from Reviewers mg6D and c8Wb, and inspired by your comment, we also added experiments on four additional benchmarks (beyond the original 22) to further demonstrate GRAMA’s effectiveness. These results appear in our response to Reviewer c8Wb and have been added to the revised paper.

Regarding method diagram: Thank you for the comment. Figure 1 illustrates GRAMA’s overall approach, showing how a learned selective mechanism aggregates information from previous states alongside a chosen backbone GNN. This process is described in the caption and detailed in Section 3. Following your suggestion, we revised the caption for clarity. Additionally, we refer the Reviewer to Figure 2, which highlights GRAMA’s strong performance on long-range tasks. Inspired by your comment, we now include visualizations of the learned coefficients across datasets to offer further insight into the selective mechanism. Regarding the link between theory and empirical results: (i) Figure 2 shows GRAMA maintains performance as task range increases—consistent with Theorem 4.4; (ii) across long-range benchmarks, GRAMA's competitive results align with the theoretical insights discussed in Section 4. We added this discussion in the revised paper and thank you for helping us improve its clarity.

Regarding Appendix: Thank you for thoroughly reviewing our appendix and for your comment. Our goal was to provide complete details, including: (i) distinguishing GRAMA from existing methods (Appendix A, related to your comment 2); (ii) theoretical proofs; (iii) implementation details; (iv) experimental settings; (v) additional results and complexity discussion; and (vi) a summary of all results. We appreciate your suggestion and have revised the appendix to present this information more clearly. Thank you.

We sincerely thank the Reviewer for the positive feedback and assessment of our paper. We are also grateful for the actionable feedback to which we respond below. We have made our best efforts to accommodate each of your comments, and we hope you find our responses satisfactory.

Regarding benchmarks: We thank the reviewer for the suggestions for additional datasets. We followed your suggestion (as well as Reviewer mg6D) and now added more results on the mentioned datasets (Cluster, CIFAR10, MNIST, PATTERN). The results, provided in the Table below, show that our GRAMA continues to consistently offer strong performance compared to its backbone GNN as well as other leading methods. We added the results and the discussion to our revised paper.

Regarding Aoki (1990): We thank you for the careful reading of our theoretical sections of the paper. In our paper, we cite Aoki (2013) as a reference to background works on SSMs, and in our Theoretical Properties of GRAMA (Section 4), we state that our goal is to adapt findings in the world of SSMs and ARMA models into a graph-learning framework. Our intention is to credit the findings of previous works, as cited and discussed in Section 4 and Appendix B. We thank you for the reference, which we have now added and discussed in our revised paper and appendix. In particular, we have clarified that the results were developed in previous studies for non-graph models, and here we expand it such that it fits into a graph-learning framework.

Regarding statistical significance: We thank the Reviewer for acknowledging the soundness and validity of our experiments. Throughout our experiments, we consistently included the standard deviation of our results. In some of the ablation studies, we reported the average performance using the same evaluation settings as in other experiments. In our final version, we will also include the already computed standard deviation of these experiments.

Regarding limitations: Thank you for the suggestion. In our paper, we have discussed the complexity as well as runtimes of GRAMA, showing that compared with other methods like graph transformers, it retains better scalability. Following your suggestion below, as well as Reviewer’s mg6D comment, we have revised our paper, to better discuss this aspect in the main paper.

Regarding WL test: We welcome your suggestion. Because our model learns to selectively attend to different states, it can also learn to attend to the current state, which means it can default to the backbone GNN. Hence, it can retain at least the expressiveness of the backbone GNN. Due to space limitations, we will include a formal proof in the revised paper. Additionally, we think that an interesting future work will be to understand the exact expressiveness of methods like GRAMA and other graph SSMs in terms of the WL test.

Regarding complexity discussion: We thank the Reviewer for the thoughtful suggestion. We agree that one of the benefits of GRAMA is its reduced computational complexity compared with other models, e.g., transformers. Following your advice, as well as Reveiwer’s mg6D question, we revised our paper such that it includes a broader complexity discussion in the main paper, as well as better referring to Appendix E.3, where we provide a full analysis and runtimes comparison.

We thank the Reviewer for the thoughtful comments and the actionable feedback. We have taken significant measures to accommodate each of your comments. We hope that you will find our responses satisfactory, and that you will consider raising your score. We are also happy to read that the Reviewer acknowledges that “GRAMA can perform well”.

Regarding sequences in graph learning: Thank you for the question. Indeed, graphs are by design not sequences, as discussed in the Introduction section. However, in order to utilize mechanisms such as SSMs or ARMA methods, to capture long-range dependencies, one needs to process sequences that are longer than the length of 2 (i.e., pairwise interactions). This is also reflected in existing literature such as Behrouz & Hashemi (2024) and Wang et al. (2024a). However, as we discuss throughout the paper, their shortcoming is that they rely on heuristics of ordering the nodes, which is not data-driven, and also not permutation equivariant. Following your question, we refined the discussion to better reflect this.

Regarding benchmarks: We thank the reviewer for recognizing the large number of datasets and benchmarks considered in our paper, which covers 22 synthetic and real-world datasets. Moreover, following your suggestion, we now added results on the datasets suggested by the reviewer, from [1]. Below, we provide a table with these results, as well as a comparison with other methods. As can be seen, our GRAMA offers competitive performance, compared with other methods, while maintaining the complexity of the backbone GNN.

Regarding GRAMA and other methods: Thank you for the question. In our paper, we attribute GRAMA’s improvements over existing graph SSMs and related methods to three key differences: (i) GRAMA supports beyond-pairwise interactions while preserving permutation equivariance—unlike [3], Behrouz & Hashemi (2024), and Wang et al. (2024); (ii) [2] employs LRU without a selective mechanism, which our results (Tables 9–11) show to be impactful; and (iii) GRIT [1], a graph transformer, differs fundamentally from graph SSMs in both computational cost and operation. GRIT emphasizes expressive positional encodings and is more resource-intensive than GraphGPS, whereas GRAMA is efficient, permutation-equivariant, and designed for long-range propagation.

Regarding more baselines: We kindly note that in our comparisons, we have considered 22 datasets, as well as more than 30 baselines (i.e., different methods). In all cases, we see that our GRAMA offers similar or better performance compared with other methods, while maintaining the complexity of the backbone GNN. Nonetheless, we welcome your suggestion, and we now compare, discuss, and cite the works mentioned by the Reviewer in our revised paper. We also provide the results in the Table below, showing the competitive performance offered by our GRAMA:

Regarding efficiency: We thank you for the important question. The Reviewer is correct that one of the advantages of SSMs is their efficiency compared with transformers. In our paper, we provided the training and inference runtimes of GRAMA, including a comparison with other types of methods, from linear MPNNs (GCN and GatedGCN), to graph transformers (GPS). These results are shown in Table 9 and Table 10 in Appendix E.3. Furthermore, we have also discussed the theoretical complexity of GRAMA in Appendix E.3. Following your question, as well as Reviewer’s c8Wb suggestion, we moved the main discussion to the main paper, and we better refer to Appendix E.3 from the main paper.