GRAMA: Adaptive Graph Autoregressive Moving Average Models

Authors: Moshe Eliasof, Alessio Gravina, Andrea Ceni, Claudio Gallicchio, Davide Bacciu, Carola-Bibiane Schönlieb
Primary area: learning on graphs and other geometries & topologies
Keywords: Graph Neural Networks, Auto-regressive Moving Average, State Space Models

Abstract:
Graph State Space Models (SSMs) have recently been introduced to enhance Graph Neural Networks (GNNs) in modeling long-range interactions. Despite their success, existing methods either compromise on permutation equivariance or limit their focus to pairwise interactions rather than sequences. Building on the connection between Autoregressive Moving Average (ARMA)  and SSM, in this paper, we introduce GRAMA, a Graph Adaptive method based on a learnable Autoregressive Moving Average (ARMA) framework that addresses these limitations. By transforming from static to sequential graph data, GRAMA leverages the strengths of the ARMA framework, while preserving permutation equivariance. Moreover, GRAMA incorporates a selective attention mechanism for dynamic learning of ARMA coefficients, enabling efficient and flexible long-range information propagation. We also establish theoretical connections between GRAMA and Selective SSMs, providing insights into its ability to capture long-range dependencies. Extensive experiments on 14 synthetic and real-world datasets demonstrate that GRAMA consistently outperforms backbone models and performs competitively with state-of-the-art methods.

Decision: reject
Reviewer scores: 5, 8, 5, 6

Reviews and discussion:
<thread>
creation date:
1730105475551

thread_type:
official_review

<thread_object>
creator: reviewer_wbsy

<content>
summary:
The paper introduces an approach to enhance GNNs by modeling long-range interactions through a learnable ARMA framework. The proposed GRAMA transforms static graph data into sequential data, leveraging the strengths of ARMA while maintaining permutation equivariance. GRAMA incorporates a selective attention mechanism for dynamic learning of ARMA coefficients, enabling efficient and flexible long-range information propagation.

strengths:
- GRAMA can see further in the graph data, capturing long-range interactions that traditional methods might miss.
- GRAMA works well with various GNN backbones, enhancing their capabilities without losing their original strengths.
- The paper is well-written and easy to understand.

weaknesses:
- How does the integration of the ARMA framework with GNNs affect the model's ability to capture long-range dependencies compared to traditional GNNs?
- What insights can the authors provide on the design choices behind the selective attention mechanism for learning ARMA coefficients?
- How do the theoretical connections to SSMs influence the model's architectural decisions and performance?
- How do the results of GRAMA compare to other state-of-the-art methods in terms of accuracy and computational efficiency?

questions:
See above.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730133498525

thread_type:
official_review

<thread_object>
creator: reviewer_nrqm

<content>
summary:
The article presents GRAMA a novel framework designed to enhance Graph Neural Networks (GNNs) by addressing their limitations in handling long-range dependencies. Traditionally, GNNs struggle with issues like oversquashing, where distant node information is compressed, making it challenging to capture extensive interactions across the graph. 

GRAMA is built on the Autoregressive Moving Average (ARMA) model framework, allowing GNNs to convert static graphs into sequences of graphs, effectively enabling them to process autoregressively. GRAMA adapts SSM concepts to a graph setting while maintaining permutation invariance. GRAMA includes a selective attention mechanism that dynamically adjusts ARMA coefficients across nodes in the graph, which efficiently propagates long-range information across graph structures. 

GRAMA is built on blocks combining AR and MA framework. In these blocks, the graph representation is transform in a graph sequence. A GNN backbone is incorporated into each GRAMA block, allowing further information exchange between nodes based on graph structure.
The model stacks multiple GRAMA blocks to form a deep GRAMA network. 
GRAMA includes an attention mechanism, which adjusts the AR and MA coefficients.

The paper also present some theoretical basis about the model interpretation (equivalence between ARMA and SSM) and and its stability conditions. 
The model is evaluated on 4 datasets, including synthetic and real-world graphs, where it consistently outperforms its backbone models.

strengths:
The paper presents an innovative approach for sequential learning on graphs, specifically adapting the ARMA/SSM framework to graph data while preserving permutation equivariance.

Experimental results demonstrate that GRAMA achieves strong performance, consistently outperforming its backbone model and competing effectively with state-of-the-art methods.

NB: These are shortly formulated but important strengths.

weaknesses:
The paper has three main weaknesses: (1) model presentation readability, (2) lack of references and attributions, and (3) limited discussion on potential model limitations.

1) Model Presentation Readability
The model presentation is challenging to follow, and improvements in clarity are necessary for readers to grasp the structure and function of GRAMA fully.
  - For instance, in the caption of Figure 1, it is stated that the blocks are linear systems; however, they contain GNN layers, which are often nonlinear. Clarification is needed on what aspects are considered linear.
  - There is a lack of clarity on the non-linearity between blocks mentioned in caption of Figure 1, as they do not appear in the model presentation.
  - In Equations (4), (5), and (6), the notation involving $L$ is ambiguous; it is unclear when $L$ represents sequence length and when it is used as a superscript for varying position (i.e., $l$ in \{L, ... , S⋅L\}).
  - The distinction between GRAMA blocks and all possible moving-window remains unclear (i.e., between $[\mathbf{f}^0, \mathbf{f}^{L-1}]$ and $[\mathbf{f}^a, \mathbf{f}^{L-1+a}]$, with $a<L$) a more ordered presentation structure could help delineate their unique aspects.

2) Lack of References and Attributions
- The theoretical properties discussed in Section 4 are primarily inherited from the ARMA/SSM framework rather than novel contributions of the paper. It is necessary to explicitly acknowledge that these inherited properties are not original contributions of the paper and to ensure all relevant references are included in Section 4.

3) Lack of Discussion on Limitations
The paper does not adequately discuss potential limitations, which would be important to understand the broader applicability of the model.
- Computational Cost: While computational cost is briefly mentioned in Appendix E, it should be addressed directly in the main text as it appears as a clear limitation of GRAMA. Since GRAMA's  may increase the parameter count and computational cost, an ablation study comparing models with equivalent computational budgets would be insightful.
- The experiments evaluate GRAMA on long-range dependency modeling, tasks for which it has been specifically designed.  It would be interesting to assess how the model performs on other types of tasks. If not, the paper should at least explicitly state that the evaluation only focus on long-range task experiments.

I still think the model is interesting and I am willing to improve (significantly) my evaluation if the authors answer my concerns

questions:
The questions relates to point (1) of 'weaknesses'

- In what blocks are linear systems, and in what they are not?

- How are implemented the non-linearity between blocks?

- More generally, what are the relations between blocks?

- More fundamentally, except to define the initiating and the readout blocks $F^{(0)}$ and $F^{(S)}$ in what blocks are relevant entities?

- In Equations (4), (5), and (6), does $L$ represents the sequence length? If not, please could you clarify. If yes, how to compute $\mathbf{f}^{L+1}$
</content>
</thread_object>

</thread>
<thread>
creation date:
1730615734914

thread_type:
official_review

<thread_object>
creator: reviewer_s9vw

<content>
summary:
This paper introduces GRAMA (Graph Adaptive Autoregressive Moving Average Models), a novel framework that enhances Graph Neural Networks (GNNs) by integrating adaptive neural Autoregressive Moving Average (ARMA) models. GRAMA addresses the limitations of existing Graph State Space Models (SSMs), which either compromise on permutation equivariance or focus only on pairwise interactions rather than sequences. The key innovation is the transformation of static graph data into sequential graph data, allowing GRAMA to leverage the strengths of the ARMA framework while preserving permutation equivariance. GRAMA also incorporates a selective attention mechanism for dynamic learning of ARMA coefficients, leading to efficient and flexible long-range information propagation.

strengths:
1. This paper introduces a new way of combining ARMA with GNNs, addressing limitations in handling long-range interactions and permutation equivariance in graph data.
2. This paper provides a theoretical foundation that establishes connections between GRAMA and SSMs.
3. The authors have tested the proposed GRAMA on a wide range of tasks and benchmarks, and the overall paper is experimentally solid.

weaknesses:
1. While I acknowledge that the authors conducted extensive experiments, several highly relevant baselines or benchmarks are notably absent. In Section 5.2, the graph property prediction datasets employed are not mainstream. Why not utilize more widely recognized real-world datasets such as ZINC or OGBG-MOLHIV/MOLPCBA? Additionally, the chosen heterophily GNNs in Table 4 do not represent the current state-of-the-art models; please refer to [1,2].

2. The baselines selected by the authors across various tables exhibit significant variation. For instance, in Tables 2 and 3, despite both being graph-level tasks, the baseline choices for the graph transformer differ. Furthermore, Table 1 includes only a single GPS, contrasting sharply with the diverse graph transformer baselines in other tables. Figure 2 does not specify which GNN is combined with GRAMA, and Table 1 appears to lack results for GRAMA+GatedGCN. Such inconsistencies may confuse readers; I believe the authors should standardize baseline selections or provide detailed explanations in the main text.

3. (I am a non-expert of SSMs, and the following comment may be somewhat amateurish) My understanding is that the sequence of $L$ node features $\mathbf{F}^{(0)}$ is generated by MLPs, which somewhat artificially constructs a dynamic graph sequence where node features evolve over time. However, I fail to see how this leads to a performance gain; generating a length-$L$ node feature sequence seems equivalent to performing $L$ transformations on node embeddings in MPNN. Even with GRAMA block, it appears to be somewhat equivalent to MPNN's ego-node update. I feel (though I may be incorrect; please correct me if so) that this approach is better suited for real-world dynamic graph sequence modeling.

Minor:
1. I would appreciate it if the authors could clarify in Table 7 which attention implementation is combined with GPS. If vanilla attention is used, this comparison is somewhat unfair.



[1] The Heterophilic Snowflake Hypothesis: Training and Empowering GNNs for Heterophilic Graphs

[2] The Heterophilic Graph Learning Handbook: Benchmarks, Models, Theoretical Analysis, Applications and Challenges

questions:
see weaknesses
</content>
</thread_object>

</thread>
<thread>
creation date:
1731376228811

thread_type:
official_review

<thread_object>
creator: reviewer_frxb

<content>
summary:
This paper shows a design that applies SSM model through ARMA to graph domain, and claims that it can solve the long-range interaction problem in graph domain. The author designs a simple deep ARMA framework with GNN backbone inside, to store many state representations for higher order long-range information. In experiments, the author shows certain improvement to baselines.

strengths:
1. I agree that using more states that used in SSM can preserve more higher-order informations in long-range problem setting, which can be helpful for certain long-range multi-polynomial regression problems. Extending SSM to graph domain can be a good attemp. 
2. Overall the design is easy to follow.

weaknesses:
1. The paper is like a naive design of a new model without clear motivation. It appears to just extend SSM/ARMA to graph domain for a new model or a new paper, without clear motivation from the graph problem side. While long-range problem is an issue in graph domain, adapting an existing model to this domain without domain-specific designs and motivations is not helpful for the domain. This is just like a "combine A and B" paper. 

2. While the presented framework "claims" supporting any GNN backbone, it does not give particular support/explanation of what kind of functions/graph informations that can be obtained with adding this framework. Clearly, there should be a discussion about GNN backbone vs GNN + proposed framework, in terms of their computational cost, memory requirement, function approximation ability, long-range regression error analysis and so on. Without these, this paper does not provide good content/guidance for the development of this domain. 

3. When looking at the result, I don't see a dramatic improvement comparing to simple baselines, although the proposed framework clearly use much more representations, memory, and computation.

questions:
I suggest the author focus on what problem you want to solve, and clearly demonstrate why this can solve the graph problem you want to solve, with solid theoretical support.
</content>
</thread_object>

</thread>
<thread>
creation date:
1732188262745

thread_type:
official_comment

<thread_object>
creator: authors

<content>
comment:
# Rebuttal Summary:


We sincerely thank the reviewers for their thoughtful and detailed feedback, as well as for recognizing the key strengths of our work. Reviewer **fRxB** appreciated that GRAMA **"preserves more higher-order information in long-range problem settings"** and found the extension of SSM to the graph domain to be "a good attempt." Reviewer **s9vW** highlighted that GRAMA introduces a **"new way of combining ARMA with GNNs,"** noting its ability to address **"long-range interactions and permutation equivariance" with "solid experimental evidence."** Similarly, Reviewer **WBsY** acknowledged that GRAMA **"captures long-range interactions that traditional methods might miss"** and is **"well-written and easy to understand."** Finally, Reviewer **nRqm** described our theoretical foundation as **innovative** and appreciated GRAMA's strong experimental performance, stating that it **"achieves strong performance, consistently outperforming its backbone models."**

We are also thankful for the actionable and constructive feedback, which has significantly improved the clarity, presentation, and scope of our paper. Specifically:

 **Additional Experiments**:
1. We have expanded our experiments to include new datasets, such as ZINC-12k, OGBG-MOLHIV, Cora, CiteSeer, and PubMed, to assess GRAMA's performance in more diverse scenarios. These experiments demonstrate that GRAMA consistently enhances baseline backbones across a range of tasks, including those not solely focused on long-range dependencies.

2. To address computational cost concerns, we conducted ablation studies comparing GRAMA and baseline models under equivalent parameter budgets and runtime constraints. These results confirm GRAMA’s ability to maintain superior performance with minimal additional computational overhead.
   


3. Inspired by Reviewer **WBsY**’s suggestion, we tested GRAMA on dynamic graph datasets. Results on Chickenpox Hungary, PedalMe London, and Wikipedia Math further show GRAMA’s potential for spatio-temporal applications.

**Revisions to the Paper**:
1.  In Section 3, we clarified the role of linearity and non-linearity in GRAMA blocks, explicitly addressing ambiguities in Equation (6) and Figure 1. We also clarified the relationship between moving windows and GRAMA blocks.

2.  We improved the presentation of the experimental results.

3.  We improved Section 4 by explicitly attributing inherited theoretical properties to ARMA/SSM frameworks while emphasizing GRAMA’s novel contributions, such as maintaining permutation equivariance and addressing oversquashing in GNNs.

4. We expanded discussions on GRAMA’s computational cost in the main text, linking it to results in Appendix E. Additionally, we highlighted GRAMA’s applicability to both long-range and more general tasks, offering a balanced view of its strengths and limitations.

5. We incorporated all added results and discussion from the rebuttal into the paper.

------

We hope these revisions address the reviewers' concerns and highlight the significance and robustness of our contributions, and that you will consider revising your scores. Thank you again for your constructive feedback.
</content>
</thread_object>

</thread>
<thread>
creation date:
1732372151712

thread_type:
official_comment

<thread_object>
creator: area_chair_namx

<content>
comment:
Dear Reviewers,

The authors have uploaded their rebuttal. Please take this opportunity to discuss any concerns you may have with the authors.

AC
</content>
</thread_object>

</thread>


Metareview:
metareview:
The paper introduces a novel and innovative framework, GRAMA, which adapts the ARMA/SSM model for sequential learning on graphs. This approach addresses key challenges in graph data, particularly permutation equivariance and long-range interactions, effectively. However, several concerns remain unresolved after the rebuttal:

1. While the paper demonstrates that GRAMA can capture long-range interactions, it has not sufficiently explained why combining ARMA/SSM with GNNs offers clear improvements over existing methods. The paper's contribution of transforming a graph into a sequence to address long-range interactions lacks a strong, domain-specific motivation. Given that SSMs have not significantly outperformed other methods, such as Transformers, in other domains, the paper does not convincingly justify the adaptation of SSMs to graph learning. The theoretical results in Theorem 4.4 provide some insight into GRAMA’s ability to capture long-range dependencies, but they do not sufficiently explain how this improves existing models or how the assumptions are met in the graph setting. The theoretical connection between GRAMA and previous methods needs to be more explicit and substantiated with concrete evidence.

2. The introduction of GRAMA increases computational costs and memory usage significantly. While the paper compares the performance of GARMA_GCN and past methods, it fails to compare more advanced models like GARMA_GATEDGCN and GARMA_GPS, which are expected to perform better. These models, based on more complex backbones, are likely to have higher computational costs and running times, which could make them less practical for large graphs. Without comparisons with these better-performing variants, it is difficult to assess the real impact of GRAMA's added complexity on its scalability and applicability to large-scale graph data.

3. The paper's presentation needs further refinement. Despite revisions, the excessive changes made during the rebuttal period have not been adequately organized, which hinders clarity. Additionally, Theorem 4.4 could benefit from a more formal, academic presentation to enhance its clarity and rigor, making it more accessible to readers. Improving the organization of the theoretical and model sections will help ensure the framework is clearly understood.

Consequently, while the paper presents an interesting framework, the authors have not fully addressed key concerns related to the model’s motivation, scalability, and clarity. Further evidence to support the motivation and a more structured presentation of the model and theoretical aspects will strengthen the paper's contribution.