Graph Adaptive Autoregressive Moving Average Models
Authors: Moshe Eliasof
Alessio Gravina
Andrea Ceni
Claudio Gallicchio
Davide Bacciu
Carola-Bibiane Schönlieb
Venue: ICML 2025 spotlightposter (2025)
Keywords: Graph Neural Networks
Auto-regressive Moving Average
Primary area: deep_learning->graph_neural_networks
TL;DR: We introduce GRAMA, an ARMA-based framework that preserves permutation equivariance,  and adapts coefficients via selective attention for long-range propagation. Experimental results on 22 datasets demonstrate its effectiveness.

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 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. Experiments on 26 synthetic and real-world datasets demonstrate that GRAMA consistently outperforms backbone models and performs competitively with state-of-the-art methods.

Graph Adaptive Autoregressive Moving Average Models
Moshe Eliasof' Alessio Gravina? ? Andrea Ceni²
Claudio Gallicchio? 2 Davide Bacciu² Carola-Bibiane Schönlieb
Abstract
2016; Hamilton et al., 2017), molecular interactions (Xu et al., 2019; Bouritsas et al., 2022), and more (Khemani et al., 2024). The most popular framework of neural graph learning is that of Message Passing Neural Networks (MPNNs). Some prominent examples are GCN (Kipf & Welling, 2016), GAT (Veličković et al., 2018), GIN (Xu et al., 2019), and GraphConv (Morris et al., 2019). However, many MPNNS suffer from a critical shortcoming of over- squashing (Alon & Yahav, 2021; Di Giovanni et al., 2023), that hinders their ability model long-range interactions. To address this limitation, several proposals were made, from graph rewiring (Topping et al., 2022; Di Giovanni et al., 2023; Karhadkar et al., 2023), to multi-hop MPNNs (Gutteridge et al., 2023), weight space regularization (Grav- ina et al., 2023; 2025), as well as Graph Transformers (GTs) (Yun et al., 2019; Dwivedi & Bresson, 2022; Kreuzer et al., 2021b). Specifically, GTs became popular because of their theoretical and often practical ability to capture long-range node interactions through the attention mechanism. How- ever, the quadratic computational cost of full attention limits their scalability, and in some cases, they were found to un- derperform on long-range benchmarks when compared to standard MPNNs (Tönshoff et al., 2023).
Graph State Space Models (SSMs) have recently been introduced to enhance Graph Neural Net- works (GNNs) in modeling long-range interac- tions. Despite their success, existing methods either compromise on permutation equivariance or limit their focus to pairwise interactions rather than sequences. Building on the connection be- tween Autoregressive Moving Average (ARMA) and SSM, in this paper, we introduce GRAMA, Graph Adaptive method based on a learnable ARMA framework that addresses these limita- tions. By transforming from static to sequential graph data, GRAMA leverages the strengths of the ARMA framework, while preserving permuta- tion equivariance. Moreover, GRAMA incorpo- rates 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 dependen- cies. Experiments on 26 synthetic and real-world datasets demonstrate that GRAMA consistently outperforms backbone models and performs com- petitively with state-of-the-ar methods.
At the same time, State Space Models (SSMs), such as S4 (Gu et al., 2021c) and Mamba (Gu et al., 2023), have emerged as promising, linear-complexity alternatives to Transformers. SSMs leverage a recurrent and convolutional structure to efficiently capture long-range dependencies while maintaining linear time complexity (Nguyen et al., 2023). Contemporary models like Mamba develop selective filters that prioritize context through input-dependent se- lection, offering compelling advantages in processing long sequences with reduced computational demands compared to transformers (Gu et al., 2023). Despite these benefits, adapting SSMs to the non-sequential structure of graphs remains a significant challenge. Perhaps the biggest chal- lenge in applying SSMs to graph learning tasks, lies in the fundamental question of "how transform a graph into a sequence?" ? To this end, several graph SSM approaches were proposed, from graph-to-sequence heuristic in Wang et al. (2024a), to studying the relationship between SSMs and spectral GNNs by pairwise interactions (Huang et al., 2024b), as well as sample-based random walk sequencing of
1. Introduction
Graph learning (Scarselli et al., 2008; Micheli, 2009; Bruna et al., 2013; Defferrard et al., 2016; Kipf & Welling, 2016; Veličković et al., 2018) has become crucial in handling graph-structured data across various domains (Gravina & Bacciu, 2024), such as social networks (Kipf& & Welling,
'Department of Applied Mathematics, University of Cam- bridge. Cambridge, United Kingdom 'Department of Com- puter Science, University of Pisa, Pisa, Italy. Correspon- dence to: Moshe Eliasof Eme5332cam..ccukk Alessio Gravina <alessio grassii.rrviiaaeeee diiiaaddddiiiii........... Andrea Ceni <an- wia..ceiiuuiiiiit>>......
Proceedings of the 42nd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Graph Adaptive Autoregressive Moving Average Models
the graph (Behrouz & Hashemi, 2024). More broadly, this question has also been studied in other, non-SSM related works, discussed in Appendix A. However, we discuss later, some of them lose the permutation- permutation-equivarianne prop- erty desired in GNNs, while others do not take advantage of the sequence processing ability of SSMs. These limitations hinder their ability to fully leverage sequence- sequence-processing ca- pabilities, especially for addressing oversquashing in GNNs. To resolve these issues, we propose, instead, a complemen- tary approach transforming a static input graph into sequence of graphs, combined with an adaptive neural au- toregressive moving-average (ARMA) mechanism, called GRAMA. We show that GRAMA is theoretically equiva- lent to an SSM on graphs. Our GRAMA allows us to enjoy the benefits of sequential processing mechanisms like SSMs, coupled with any GNN backbone, from MPNNs graph transformers, while maintaining backbone properties, such as permutation-equivariance
& Welling, 2016), GraphSAGE (Hamilton al., 2017), and GIN (Xu et al., 2019) face challenges such over- smoothing (Nt & Machara, 2019; Oono & Suzuki, 2020; Cai & Wang. 2020; Rusch et al., 2023), over-squashing (Alon & Yahav, 2021; Topping et al., 2022; Di Giovanni et al., 2023) and more generally vanishing gradients (Arroyo et al., 2025), which hinder long-range information propa- gation critical in applications like bioinformatics (Back et al., 2021; Dwivedi et al., 2022b) and heterophilic settings (Luan et al., 2024; Wang et al., 2024b). To address these limitations, various methods have emerged, including graph rewiring (Topping et al., 2022; Karhadkar et al., 2023), adap- tive message passing (Errica et al., 2024; Finkelshtein et al., 2024), weight space regularization (Gravina et al., 2023; 2024b; 2025), exploitation of nort-Hamiltonian dynamies (Heilig et al., 2025), and Graph Transformers (GTs). GTs, which capture both local and global interactions, have been particularly promising, as demonstrated by models like SAN (Kreuzer et al., 2021c), Graphormer (Ying & Leskovec, 2021), and GPS (Rampášek et al., 2022). These models often incorporate positional encodings, such as Laplacian eigenvectors (Dwivedi et al., 2021) or random-walk struc- tural encodings (RWSE) (Dwivedi et al., 2022a), to encode graph structure. However, the quadratic complexity of full attention in GTss presents scalability challenges. Recent innovations like sparse attention mechanisms (Zaheer et al., 2020; Choromanski et al., 2020), Exphormer (Shirzad et al., 2023), and linear graph transformers (Wu et al., 2023; Deng et al., 2024) address these bottlenecks, improving efficiency and scalability for long-range propagation.
Main Contributions. Our Adaptive Graph Autoregressive Moving Average (GRAMA) model offers several advance- ments the conjoining of dynamical systems theory into GNNs:
Principled Integration of SSMs in GNNs. We enable the use of sequence-based models (like ARMA) coupled with virtually any GNN backbone, by transforming graph inputs into temporal sequences without sacrificing permu- tation invariance.
Theoretical Understanding of the coupling of SSMs and GNNs, We demonstrate that augmenting GNNs with ARMA via our GRAMA has an equivalent SSM model.
State Space Models (SSMs). SSMs, traditionally used for time series analysis (Hamilton, 1994b; Aoki, 2013), process sequences through latent states. However, clas- sic SSMs struggle with long-range dependencies and lack parallelism, limiting their computational efficiency. Re- cent advances. such as the Structured State Space Sequence model (S4) (Gu et al., 2021c; Fu al., 2023), mitigate these issues by employing linear recurrence as structured convolutional kernel, enabling parallelization on GPUs. De- spite this, simple SSMs still underperform compared to attention models in natural language tasks. Mamba (Gu et al., 2023) improves the ability of SSMs to capture long- range dependencies by selectively controlling which se- quence parts influence model states. Mamba has shown promising results, outperforming Transformers in several benchmarks (Gu et al., 2023; Liu et al., 2024) while be- ing more computationally efficient. The combination of SSMs with graph models presents challenges, particularly in transforming the articulated connectivity of graphs into sequences. For instance, Graph-Mambe (Wang et al., 2024a) orders nodes by degree, but this heuristic approach sacrifices a desirable property in GNNs. Similarly, Behrouz& & Hashemi (2024) propose generating
Mitigation of the oversquashing problem. We provide the theoretical foundation that our GRAMA effectively addresses the oversquashing phenomenon in GNNs and improves the long-range interaction modeling capabilities.
Strong Practical Performance. We demonstrate our GRAMA on three popular backbones (GCN (Kipf & Welling, 2016). GatedGCN (Bresson & Laurent, 2018), and GPS (Rampášek al., 2022)) and show the com- pelling performance by GRAMA on 26 synthetic and real-world datasets.
2. Related Work
We now provide an overview and discussion of related topics and works to our GRAMA. In Appendix A, we discuss additional related works.
Long-Range Interactions on Graphs. GNNs rely on message-passing mechanisms to aggregate information from neighboring nodes, which limits their ability to capture long-range dependencies, as highlighted by Alon & Yahav (2021); Di Giovanni et al. (2023). Models like GCN (Kipf
permutation-equivaiini
2

---

Graph Adaptive Autoregressive Moving Average Models
sequences via random walks, which improves performance but also sacrifices permutation-eqqivariinn non-determinism to the model. Also, turning a graph into a sequence based on a policy, such as sorting nodes by degree, limits direct use of the input graph, as multiple graphs can share the same node degrees and thus be indis- tinguishable. Huang et al. (2024b) explored links between spectral GNNs and graph SSMs. focusing on pairwise inter- actions; however, this design choice may not fully exploit the sequence-handling capacity of SSMs and may reach the state of oversquahsing earlier because of the use of powers of the adjacency matrix (Di Giovanni et al., 2023). In this work, we harness the potential of SSMs by adopt- ing a structure inspired by the connection between SSMs and ARMA models. By transforming static graphs into sequences, GRAMA maintains permutaton--qquivaraance desired property in GNNs (Bronstein et al., 2021), also useful for pro-pprpagttion (Pan & Kondor, 2022; Schatzki et al., 2024), while enabling effective learnable and selective long-range propagation.
dering its direct conversion into an SSM, while we show that our GRAMA has an equivalent SSM, providing deeper theoretical understandings.
while adding
3. GRAMA
Although a graph is a static structure, the process of message passing introduces a dynamic element. In message passing, information is propagated through the graph, allowing nodes to update their states based on the states of their neighbors. This dynamic behavior can be viewed through the lens of dynamical systems, where the state of each node evolves according to certain aggregating rules, as discussed in Sec- tion 2. This perspective is instrumental Recurrent Neural Networks (RNNs), which are designed to handle sequential data and capture temporal dependencies. By treating the message- pargsengg process leverage the strengths of RNNs to model the evolution of node states over time. The model we propose, GRAMA, takes inspiration from the architectural structure of the latest generation of sequential models, like S4 (Gu et al., 2021a), Mamba (Gu al., 2023), LRU (Orvieto et al., 2023b), and XLSTM (Beck et al., 2024). To import these powerful se- quential models to graph learning, we first translate static input graphs into sequences of graphs. Then, the GRAMA block transforms such graph sequence into another graph sequence, while considering the structure of the graph. Each GRAMA block is linear, and non-lineat activations are ap- plied between GRAMA blocks to increase the flexibility of the overall model. Below, we discuss in detail the different aspects of our GRAMA- from its initialization to the graph sequence processing blueprint by ARMA, to the learning of ARMA coefficients in graph adaptive manner. The overall design of GRAMA is illustrated in Figure 1.
dynamical system, we can
Autoregressive Moving Average Models (ARMA). ARMA models, introduced by Whittle (1951), combine an autoregressive (AR) component, modeling dependencies on previous time steps, with moving average (MA) com- ponent, considering residuals. Widely applied in stationary time series analysis (Box et al., 1970), ARMA models are equivalent to state space models (SSMs) (Hamilton, 1994a). An ARMA(p, 9) model considers previous p states and q residuals 5(-), and is governed by the following equation:
P
((1) = Σ So - + Σ 0,5(1 - 5) +(),, (1)
1=1
1=1
where (d.))=1 (0:)3-1 are the autoregressive and moving average coefficients, respectively.
Notations. We denote a graph by = (V, with [V|- = n nodes and F = m edges. A node v is associated with input node features fo E IRS The node features are then denoted by f E R=ee.
Although ARMA models are traditionally used for process- ing sequences, they have also been studied for classical graph filtering (Isufi et al., 2016) and more recently for- mulated as an MPNN in Bianchi et al. (2021). The Graph ARMA model (Bianchi al., 2021) introduced a learn- able ARMA version for GCNs, using recursive 1-hop fil- ters to create structure resembling ARMA methods. In this paper, we introduce GRAMA, a method that lever- ages neural ARMA models by transforming a static input graph into a graph sequence. Different than Bianchi et al. (2021), which uses the static input graph and formulates a recursive ARMA model through spectral convolution per- spective, our GRAMA incorporates selective and graph adaptive mechanism that leams ARMA coefficients along the graph sequence. This dynamic adjustment of coefficients directly addresses oversquashing by preserving long-range dependencies and enabling adaptive control over feature propagation. Additionally, Bianchi et al. (2021) uses an ARMA(1, 1) model with non- ooneaiiaassi between steps, hin-
Initialization. Processing information with ARMA or SSM frameworks, by design, requires a sequence. As discussed in Section 2, previous studies on graph SSMs have cho- sen to transform the graph into a sequence by means of heuristic node ordering, random walk sampling, or by con- sidering pairwise interactions (edges) as sequences of length 2. While these choices are valid, and show strong perfor- mance in practice, they also introduce challenges compared to common graph learning approaches, or may not fully uti- lize the underlying sequence processing framework. Specif- ically, the first two approaches (node ordering and walk sampling) do not maintain the permutation equivariance desired in GNNs, and the third (pairwise interactions) con- siders only very short sequences, while one key benefit of the ARMA and SSM frameworks is their ability to cap-
3

---

Graph Adaptive Autoregressive Moving Average Models
GRAMA A Block
F
f (())
(()
f
f
(()
((Z+)
((2-11) 1)
GNN
(0)
(0)
8(4)
8
8(E-1)
((L)
8(L+1)
8(26-1)
Instialization
GRAMA
GRAMA
Block 1
Block S
F A (1)
F(S) A (8)
Figure 1: An illustration of the GRAMA framework with L recurrences. We embed static input graph into a sequence of graphs. This sequence is the input for the first GRAMA block. Here, a GRAMA block is composed of neural ARMA(L, L) layer with adaptive autoregressive Ø = foi and moving average = {0, د coefficients, that weigh previous states {fi)(-o and residuals {ōi and graph-informed residual update via GNN backbone. A GRAMA block yields two updated state and residual sequences F(*), A for the = I...., block. Each GRAMA block is linear system, and non-linearities are applied between GRAMA blocks, in Equation (8).
ture long-range dependencies in long sequences (Gu et al., 2021b). To address these challenges, we propose to trans- form static graph into sequence of graphs, such that each node is equipped with sequence of input node feature vectors rather than single input node feature vector. By following this idea, we can employ sequence processing frameworks such as ARMA on data beyond pairwise in- teractions, while maintaining cummuaation-qquvvriinn we discuss later. Specifically, we first stack the input node features f for L times, where 0 hyperparameter that determines the length of the sequence process, followed by the application of set of MLPs, {9x H-= one for each k O,..., L 1, that embed the original e node features into d channels:
to exchange information between nodes, as shown in Sec- tion 3.1, thus rendering our GRAMA a drop-in mechanism.
3.1. Graph Neural ARMA
Autoregressive (AR) Layers. An AR, captures the relation- ship between current node features and their p > 0 previous historical values, through the learnable coefficients { discussed in Section 3.2. Formally, given sequence of node features of length L [f(9) ..... f((+.-1)) (f.))....((++.....))
as
assuming
S L,, the node features at step l + I. read:
(E+L) (R (( = of f((+ AR,
(2) where (()) E RLxaxd We refer to the sequence encoded by (()) as the initial input sequence, and to work with an ARMA model, we also define the residuals sequence as follows:
[(0)_ = [0(0) (()-1) = (9.
Moving Average (MA) Layers. Given residuals sequence [((0) ..... ((()L-))((+L1)) MA, layer with {0,}}=1 learnable
coefficients, captures the dependency of the latest q S L residuals:
q 0, g((
(L+L)
MA, (8(4) ..... (((+L-1)) -
(0)
(0))
8 ((1-1)]
A (0) E RR Ixxxd
(3)
MAG
(5)
where ((0) f(++)) f(() for t= 0, O, L 2. Note that by subtracting subsequent elements in the input sequence choose the last residual term in A (0) (that is 8(4-1)) to be matrix of zeros at the initialization step.
GRAMA Recurrence. Combining AR, and MA, layers,
leads the ARMA(P, 9) recurrence:
F(0), are left with L - elements. Therefore,
p((+L)
p(e+L) MMA
+ (((+L)
(6)
We note that via this approach, we can perform sequence modeling using ARMA on the sequence dimension (L) while retaining the ability to use any desired backbone GNN
where g(++L) is the residual of the last step, which is given by a GNN backbone that is optimized jointly with the ARMA coefficients, that is, (f+4) GNN(f(+L-[)) G)

---

Graph Adaptive Autoregressive Moving Average Models
Here, we apply the GNN backbone without non-linearity so that each recurrence step within GRAMA block is linear function. In particular, note that the GNN can be any graph neural network, because at each recurrence, GRAMA pro- cesses a sequence of graphs by updating each node feature based on its sequence via the terms p(++L)
3.2. Learning Adaptive Graph ARMA Coefficients
We now introduce our graph adaptive approach for learning the ARMA coefficients, which is a key component in our approach to allow flexible and selective GRAMA.
_ coupled ARR MMA,
Naive ARMA Learning. The most straightforward way to learn the AR and MA coefficients, { Yi=1 and (0, 1 is to consider them as parameters of the neural network and learn them via gradient descent. However, this yields coeffi- cients that are identical for all inputs, thereby not adaptive. This approach is directly linked to non-selective weights in SSM models (Gu et al., 2021c), which were shown to be less effective compared to selective coefficients (Gu et al., 2023).
with GNN in the term (f++L) Moreover, the structure ((++L) p((++)
of the terms AR, .MM,, includes multiple residual con- nections, which can implement standard skip-connections, retaining the expressiveness of the backbone GNN. Sec- tion 5 showcases GRAMA with various GNN backbones, from MPNNs to graph transformers.
GRAMA Block. Equation (6) describes a single recurrence step within a GRAME block. Similar to other recurrent mechanisms, we apply R recurrences, where R > 1 is hy- perparameter. Thus, given the initial states O and residu- als A (0), after It recurrences according to Equation (6), we obtain updated states [F(L). fl R[]+ and residuals (8()) ..... ((L+R-1)] sequences, followed by an element- wise application of non-linearity a:
Selective ARMA Learning. To allow selective ARMA coefficient learning similarly to Mamba (Gu et al., 2023), we use an attention mechanism (Vaswani et al., 2017) ap- plied over the state and residual sequences F(+), A (+) at each GRAMA block = 1, ...... S. The rationale behind this construction is that an attention layer assigns scores between elements within the sequence. Formally, we obtain two scores matrices A E [0, 1] The last row in each matrix represents the predicted coefficients for our GRAMA, { and respectivivl However, the SoftMax normalization in standard attention layers yields non nog-nngttive pairwise values, which is not consistent with the usual choice of ARMA coefficients. Therefore, we fol- low the self-attention implementation (Vaswani et al., 2017) up to the SoftMax step, and we normalize the scores to be in [-1, 1] while complying with a sum-to-on constraint. We note that, this procedure facilitates learning stability, such that ARMA coefficients do not explode or vanish, and its design is guided by the insights from Theorems 4.3 and 4.4. We also note that this overall construction yields two- fold adaptivity in the predicted ARMA coefficients: First, the attention mechanism allows selectivity with respect to inputs, which are the sequences F(*), A (s)) Second, be- cause these sequences are coupled with a GNN backbone, as shown in Equation (6). it implies that the input node fea- tures and the graph structure influence the coefficients. We provide further implementation details in Appendix C, and comparison between naive and selective ARMA learning in Appendix F.4.
F()_ [o(P(")) ((P.).........RRRRR-... ((((RR-)))] (1) (0(8()) of (8(LRR-D))
(7)
In practice, as discussed in Appendix D.6, R is chosen such that p- = Q = R = I, and the obtained updated se- quences are F(1) = (o((()) ((f()) ((((2 1)), A
Deep GRAMA. In Equation (7), we describe the action of a single, first GRAMA block. Overall, each block per- forms It recurrence steps. As such, the first GRAMA block yields R new states and residuals encoded in F(I) and A (1), respectively, that can then be processed by subse- quent GRAMA blocks. That is, we can stack S > GRAMA blocks, each block with its own parameters, form- ing a deep GRAMA network, where the updated sequences at the s-th GRAMA block are:
(+) = [ of (f(LtaR-1)]]
(8)
A (+) (0(
(
for 8 1. 1.....,, S. Note that the depth of a GRAMA net- work is therefore equivalent to the number of systems S to be learned, multiplied by the number of recurrent steps R. The outputs of the GRAMA network are then the final state and residual sequences F(S), A (5). We illustrate this process in Figure 1. Because in our experiments we are in- terested in static graph learning problems, we feed the latest state matrix within the sequence F(S) a readout layer to obtain the final prediction, as elaborated in Appendix C.2. The additional processing in GRAMA introduces some computational overhead, as detailed in Section 3.3. How- ever, this cost remains reasonable compared to other meth- ods and yields significant performance improvements, as detailed in Section 5.
3.3. Time and Space Complexity of GRAMA
We discuss the theoretical complexity of our method, show- ing its reduced computational complexity compared with other models, c.g., transformers. We note that, overall, our GRAMA retains the asymptotic complexity of the under- lying GNN backbone, assuming that the number of recur- rences is a constant, or smaller than the number of nodes and edges within the graph. We report empirical runtimes in Appendix E.3, demonstrating that GRAMA offers better
5

---

Graph Adaptive Autoregressive Moving Average Models
scalability and performance compared to other approaches
GRAMA block is fundamentally an ARMA model. In Theorem 4.1, we formalize the equivalence between ARMA models and linear SSMs. This allows us to interpret our GRAMA model as stack of graph-informed SSMs through the backbone GNN encoded in Equation (6).
such graph transformers.
Time Complexity. We analyze the case where we use an MPNN that is linear in graph size (nodes and edges) such as GCN is used within GRAMA. Our GR GMAMA is comprised of L initial MLPs, S GRAMA blocks, each with L recurrent steps, and final readout layer. Note that L is the sequence length, which is hyperparameter and does not exceed the value of 50 in our experiments. The initial MLPs operate the input E Rx and embed them to a hidden dimension d. Therefore, their time complexity is OLL n c d). Each GRAMA block is comprised of two attention layers- one for the pooled states sequence and the other for the residual pooled sequence, and a GNN layer for predicting the current step residual, which operates on graph node features. The attention layer time complexity is O(L'd dd²) because the pooled (across the graph nodes) sequence is of shape I. x d, and the GNN layer complexity is O(n + m.) where n is the number of nodes and m is the number of edges in the graph. Note that usually m > n, so the GNN complexity can be rewritten as (m)) We note that, in the case of a graph-transformer based GNN, like GPS, we have that m = n²2 In the following, we consider the more general case. In total, we have S GRAMA blocks, where S is hyperparameter, and is typically small, up to 4. The final readout layer is a standard MLP and, therefore, has the time complexity of (n--d-o) for mose tasks, and (d-o) for graph-level tasks. Therefore, the overall time complexity (including initial MLPs and readout) of our GRAMA is O (L. n. c. d + ST. (n + + T.2 d2) + n d..)
Theorem 4.1 (Equivalence between ARMA models and State Space Models), For every ARMA model, there exists an equivalent State Space Model (SSM) representation. and conversely, for every linear SSM, there exists an equivalent ARMA model representation.
Stability. Representing an ARMA system SSM in- volves the description of a linear recurrence equation as f(L) = =E==1 0. + Σ 0,0(1-)) + +8(1) or, alter- natively, in matrix form as (() = AX + Bo
with X(=-1) = [((.-)),... p(0), 8
80)) see
Appendix B for more details.' ! In the SSM literature, the A matrix is called the state matrix. The state matrix cor- responding a GRAMA block is entirely determined by the set of autoregressive and moving average coefficients. Thus, each GRAMA block is characterized by an adaptive state matrix, which is especially important since it directly governs the evolution of the node features f. In particular, the stability of this evolution can be established by analyz- ing the powers of the state matrix, as widely studied in the context of RNN and SSM theory (Pascanu, 2013; Gu et al., 2021 Hence, the stability of GRAMA block can be characterized by the following Lemma 4.2.
Lemma 4.2 (Stability of GRAMA). The linear SSM cor- responding to a GRAMA block with autoregressive co- efficients { is stable if and only if the spectral ru- dius of its state matrix is less than for at most equal to) 1. In particular, this happens if and only if the polynomial P(A) = X2 E'=10,h 0,X0-3 has all its roots inside (or at most on) the unit circle.
Space Complexity. We analyze the case where linear in graph size (nodes and edges) complexity MPNN (such as GCN) is used within GRAMA. The space complexity of the initial MLPs is OLL c. d). The space complexity for each GRAMA block is (dP) for the GNN layer, and similarly (d2) for the two attention layers. Overall, we have S such blocks. The readout layer space complexity is O(d o). Thus, the overall space complexity (including initial MLPs and readout) of GRAMA is ( c d + S S.d d² + d. d)).
We now give sufficient condition for the stability of the SSM corresponding to GRAMA block.
Theorem 4.3 (Sufficient condition for GRAMA stability).
If Σ 10 S 1, then the GRAMA block with autore- gressive coefficients (o: corresponds to a stable linear SSM.
4. Theoretical Properties of GRAMA
We now formally cast common knowledge formulated in the context of RNNs, control theory, and SSMs (Yu al., 2019; Slotine et al., 1991; Khalil, 2002: Aoki, 2013) to the realm of GNNs, aiming to adapt foundational results from non- non-graph settings of SSMs and ARMA models into a graph-learning framework. We discuss the main theoretical properties of our GRAMA: (i) its representation as an SSM model, (ii) its stability, and (iii) its ability to model long- range interactions in graphs. All the proofs are provided in Appendix B.
Long- Lang-Range Interactions. A key distinction between stan- dard MPNNs and our GRAMA lies in its neural selective se- quential mechanism, which uses learned ARMA coefficients to operate across two domains: the spatial graph domain via GNN backbone, and the sequence domain via the ARMA mechanism, enabling selective state updates. Remarkably,
'Note that, following the notation of Section 3. we can write the state X(L-1) as the concatenation of p(0) and A A i.e., (L--1) = [F(0) A [00]] For simplicity of notations, we analyze
Connection to SSM. As discussed in Section 3, each
the case where R =
6

---

Graph Adaptive Autoregressive Moving Average Models
the state matrices of each GRAMA block play significant role in the propagation of the information from the first sequence of node features, F(()
classification datasets from Platonov al. (2023), ZINC- 12k, OGBG-MOLHIV, Cora, CiteSeer, Pubmed, MNIST CIFARIO, PATTERN, and CLUSTER. In Appendix E.3, we discuss the runtimes of GRAMA, and compare with other methods. In Appendix E,4, we report ablation stud- ies and additional comparisons to provide a comprchensive understanding of our GRAMA, while in Appendix E.6 we include an evaluation on temporal setting. Notably, the performance of GRAMA is compared with popular and state-of-the-art methods, such as MPNN-based models, DE- GNNs, higher-order GNNs, and graph transformers, and shows consistent improvements over its baseline models, with competitive results to state-of-thh-ar methods (see Appendix F). We note that, in the main text, we report mod- els and variants that are state-of-the-art on the individual benchmarks, which may lead differences between the tables, while more variants are explored in the appendix. Additional details on baseline methods are presented in Ap- pendix D.I, and the explored grid of hyperparameters in Appendix D.6. We demonstrate GRAMA on three widely used backbones- GCN (Kipf & Welling, 2016), GatedGCN (Bresson & Laurent, 2018), and GPS (Rampášek et al., 2022), highlighting its versatility across different backbone types, including linear MPNNs and graph transformers, and its consistently strong performance regardless of the un- derlying backbone architecture. We release our code at https: /ttts:///tt thub. aooom//osheell1 o
....., ((..),,,,__)), to the last sequence of node features after S GRAMA blocks, F(S) = -[((_S), ..... " (( especially for large I. and S. In fact, if the entries of the k-th power of the state ma- trix of a GR AR block vanish, then for a stable GRAMA is impossible to model rangge dependencies of k hops, in the sequence, as we show in Lemma B.I.
This fact relates to a broadly acknowledged problem in the RNN literature, the vanishing gradient issue (Hochreiter et al., 2001; Bengio et al., 1994; Orvieto et al., 2023a): the entries of the powers of matrix with a spectral radius less than 1 can quickly vanish, making it challenging for gradient-based algorithms to effectively long-range patterns. Therefore, to bias the long-tern propagation of the informa- tion of GRAM AMA block, we can initialize the state matrix to have its eigenvalues close enough to the unitary circle, following the footsteps of recent RNN methodologies (Orvi- eto et al., 2023b; Arjovsky et al., 2016; De et al., 2024). In fact, the closer the eigenvalues are to the unitary circle, the slower the powers of the state matrix vanish (Horn & John- son, 2012). The following Theorem 4.4 provides criterion to control the long-range interaction of GRAMA.
Theorem 4.4 (GRAMA allows long-range interactions). Let us be given a GRAMA block with autoregressive co- efficients ) Assume the roots of the polynomial P(A) = >P- -E 35x003 are all inside the unit circle. Then, the closer the roots P()) are the unit circle, the longer the range propagation of the linear SSM correspond- ing to such a GRAMA block.
5.1. Graph Feature Transfer
Setup. We consider three graph feature transfer tasks based on (Gravina et al., 2025). The objective is to transfer a label from a source to a target node, placed at a distance & in the graph. By increasing e, we increase the complexity of the task and require longer-range information. Moreover, due to oversquashing, the performance is expected to degrade as l increases. We initialize nodes with random valued feature, and we assign values "1" and "0" to source and target nodes, respectively. We consider three graph distributions, i.e., line, ring, crossed-ring, and four different distances e = {3, 5, 10, 50). Appendix D.2 provides additional details about the dataset and the task.
The results derived in this section provide the theoretical foundation and motivation for the employment of GRAMA as a method to address the oversquashing phenomenon in GNNs, and to enhance long-range interaction modeling capabilities, as we show in our experiments in Section 5.
5. Experiments
We present the empirical performance of our GRAMA on suite of benchmarks similar to previous graph SSM studies. Specifically, we show the efficacy in performing long-range propagation, thereby mitigating oversquashing. To this end, we evaluate GRAMA on a graph transfer task (Gravina et al., 2025) in Section 5. In a similar spirit, we assess GRAMA on synthetic benchmarks that require the exchange of messages large distances over the graph, called graph property prediction from Gravina et al. (2023), in Section 5.2. We also verify GRAMA on real-world datasets, including the long-range graph bench- mark (Dwivedi et al., 2022b) in Section 5.3, and additional GNN benchmarks in Appendix E. where we consider MalNet- Tiny (Freitas et al., 2021), the heterophilic node
Results. Figure 2 reports the test mean-squared error (and standard deviation) of GRAMA compared to well-known models from the literature. Results show that traditional MPNNs (GCN, GAT, GraphSAGE, and GIN) struggle to propagate information effectively over long distances, with their performance deteriorating significantly as the source- target distance l increases. This is evident across all graph types. In contrast, GRAMA coupled with GCN achieves low error even when the source-target distance is 50. Among the models, A-DGN, SWAN, and GPS come closest to GRAMA performance, as they are a non-dissipative ap- proach and a transformer based model, respectively. How-
7

---

Graph Adaptive Autoregressive Moving Average Models
GCN
GraphSAGE
A-DGN
SWAN
GRAMA
Mean Squared Error
Mean Squared Error
Mean Squared Error
10-1
10-2
10"
10"3
10-1
10-4
10-1
10-3
35 10
50
35 10
50
35 10
50
hource-larget distance (#hops)
Source- distance (#hops)
Source- larget distance (#hops)
(a) Line
(b) Ring
(c) Crossed-Ring
Figure 2: Feature transfer performance on (a) Line, (b) Ring, and (c) Crossed-Ring Baased-Ring graphs.
ever, GRAMA still outperforms all baselines across all graph structures, especially as the propagation distance in- creases, thereby offering solid empirical evidence of its ability transfer information across long distances, as sup- ported by theoretical understanding from Section 4.
Table I: Mean test set logio (MSE)(() and std averaged 4 random weight initializations Graph Property Prediction tasks. The lower, the better. First, second, and third best results for each task are color-coded; we consider only the best configuration of GRAMA for coloring purposes.
5.2. Graph Property Prediction
Model
Diameter
SSSP
Eccentrccity
MPNNS
Setup. We consider the three graph property prediction tasks presented in (Gravina al., 2023), investigating the performance of GRAMA in predicting graph diameters, single source shortest paths (SSSP), and node eccentricity on synthetic graphs. To effectively address these tasks, it is essential to propagate information not only from direct neighbors but also from distant nodes within the graph. As a result, strong performance in these tasks mirrors the ability facilitate long-range interactions. We provide more details on the setup and task in Appendix D.3. For the GPS results, we use a basic GPS with no additional components (c.g., encodings), to quantify the contribution of GRAMA.
GaledGCN
0.134810.030
-3.2610
0.6995 0302
GCN
0.7424=0.0466
0.9499 0001
0.8468 -.0.0000
GAT
0.8221+0.0762
0.6951+0.1400
0.7909
GriphSAGE
0.8645.0.0400
0.2863g0.184:
0.7863
GIN
0.6131+0.0950
+0.5408++..4198
0.9504+0.0000
0007
GCNI
0.5287=0.0050
-1.1329:4..0ss
0.7640 0388
ARMA
0.781920.1729
0.043220.00m:
0.2605
1::00....000 10000110
DE-GNNs
DGC
0.6028.0.000 -0,1483.1o.022
0.8261 0.8261 0032
GRAND
0.671520.040
-0,0942.0.3ee
0.6602
GraphCON
0.0964+0.0522 -00-000
-1.3836++0.009
0.6833+0.0074
A-DGN
+0.5188
1812
3.2441.10.075
0.4296 1003
SWAN
-0.5981 +0 1145
+3.5425 #0.0830
-0.0739 20.210
Graph Transformers GPS
0.5121
+0.00 0426
4.5990
0.6077
Our
GRAMAGGN
0.1577 40.0665
0.0095
0.6193 0441
Results. Table reports the mean test log1o (MSE), com- paring our GRAMA with various MPNNs, DE-GNNs, and transformer-basee models. The results highlight that GRAMAGPS consistently achieves the best performance across all tasks, demonstrating significant improvements over baseline models. For example, in the Eccentricity task, GRAMA reduces the error score by over 1.2 points com- pared to SWAN and by over 1.7 points compared to A-DGN, which are models designed to propagate information over long radii effectively. Compared to ARMA (Bianchi al., 2021), our method demonstrates average improvement of 2.4 points, highlighting the empirical difference between the methods, besides their major qualitative differences.
GRAMAGa ARAMAAXHOON
-0,5485 0.5445+0..148 +0.1489
-.1289+ +0.098s
-..1289
0.5523
GRAMAGES
-0.8663 0514 -3,9349 20.0999 -1.3012:20.12b4
works. This demonstrates that method effectively leverage the strengths of simple models while overcoming their limitations in long-range propagation.
5.3. Long-Range Benchmark
Setup. We assess the performance of our method the real- world long-range graph benchmark (LRGB) from (Dwivedi et al., 2022b), focusing on the Peptides-func and Peptides- struct datasets. We follow the experimental setting in (Dwivedi et al., 2022b), including the 500K parameter bud- get. All transformer baselines include Laplacian positional encodings, for fair evaluation. Our GRAMA does not use additional encodings. The datasets consist of large molec- ular graphs derived from peptides, where the structure and function of a peptide depend on interactions between distant parts of the graph. Therefore, relying on short-range inter- actions, such as those captured by local message passing in GNNs, may not be insufficient to excel this task. More
Overall, these results further validate the effectiveness of our GRAMA in modeling long-range interactions and mit- igating oversquashing. Furthermore, GRAMA not only surpasses strong models like GPS, but also strengthens the performance of simple MPNN backbones like GCN. For example, GCN augmented with GRAMA consistently delivers better results than the baseline GCN, highlighting its ability to enhance traditional message-passing frame-
8

---

Graph Adaptive Autoregressive Moving Average Models
Table 2: Results for Peptides-func and Peptides-struct av- eraged over 3 training seeds. Baselines are taken from (Dwivedi et al., 2022b) and (Gutteridge et al., 2023). All MPNN-based methods include structural and positional en- coding. The first, second, and third best scores are colored, and we color only the best configuration of GRAMA.
any GNN backbone. We draw a theoretical link between SSM models and GRAMA, to build solid groundwork and understanding of the qualitative behavior of GRAMA. Com- pared with several existing Graph SSMs, our GRAMA al- lows to benefit from long-range interaction modeling abili- ties, while maintaining permutation equivariance. Through a series of extensive experiments on 26 synthetic and real- world datasets, we demonstrated that GRAMA consistently offers competitive performance with well-established base- line models, from classical MPNNs to more complex ap- proaches such as Graph Transformers and Graph SSMs. Overall, GRAMA offers a theoretically grounded, pow- erful, and flexible solution that bridges the gap between contemporary sequential models and existing graph learn- ing methods, stepping forward towards new family of graph machine learning models.
Peptides-tune AP
Peptides-struct MAE
Model
MPNNs
GCN
59.30
10.001
GatedGCN
58.64 77
0,3420 0,342010.0013
ARMA
0..62
00.004
Multi-hop GNNs
DIGL+MPNN+LapPE
68.30
0,2616:2.0018
HCstHop-CCN+LLappt
68.43
01261420.0023
DRew GCN+LapPE
71.50 44
0.2536.10.0013
69.77+0.20
0,2539 +0.0077
Graph Transformers
TransoomerrLapptE
63.26++1.20 1666+11200
0,2529 +0.0000
SAN+LapPE
63.84 21
0,2683 00.3
GaphGPS-Lapph apPF.
65.35
0,2500=0.0000
Impact Statement
DE-GNNs
GRAND
57.89 0.66
0.3418
000001
This paper aims to contribute to the field of Machine Learn- ing, specifically focusing on advancing Graph Neural Net- works (GNNs). It proposes a theoretically grounded and flexible solution that bridges the gap between contempo- rary sequential models and existing graph learning methods, paving the way for new family of graph machine learning models. The research presented herein has positive im- pact on the ongoing exploration and applications of GNNs coupled with State Space Models (SSMs).
GraphCOON
60.22++0.08
0,2778 00.008
A-DGN
59.75-20.44
00.021
SWAN
67.51 0.339
0,2485
1. 0000
Graph SSMs
Graph-Mamhe
67.39
0,2478 00106
GMN
70.71 + 8.3
0.2473 20.025
Ours
GRAMAGON
70.93..077
0.2439 00.007
GRAMAGaaarrS
70.49
0.2459 0000
GRAMAGES
69.8 69.83 0.800.
0.2436 20000020
In this work, we do not release any datasets or models that could pose significant risk of misuse. We believe our re- search does not have any direct or indirect negative societal implications or harmful consequences, as we do not utilize sensitive, privacy-related data, nor do we develop methods that could be applied for harmful purposes. As far as we are aware, this study does not raise any ethical concerns or potential negative impacts. Furthermore, our research does not involve human subjects, nor does employ crowdsoure- ing methods. We confirm there no potential conflicts of interest or sponsorship influences affecting the objectivity or outcomes of this study.
details on the setup and tasks can be found in Appendix D.4.
Results. Table 2 provides a comparison of our GRAMA model with a wide range of baselines. A broader comparison is presented in Table 8. The results indicate that GRAMA outperforms standard MPNNs, waasformer-based GNNs, DE-GNNs, SSM-based GNNs, and most Multi-hop GNNs. Such a result highlights the competitiveness of our method and its ability to propagate information effectively. More- over, its empirical advantage over existing Graph SSMs em- phasizes the strength of GRAMA in modeling long-range interactions while maintaining permutation equivariance and processing sequences that go beyond pairwise inter- actions. Similarly to Section 5.2, our results show that AMA strengthens the abilities of simple GNN back- bones. Specifically, our method boosts GCN and GatedGCN by more than 11 AP points on the Peptide-func task.
A Acknowledgements
The work has been partially supported by EU-EIC EMERGE (Grant No. 101070918), and by NEURONE, project funded by the European Union Next Genera- tion EU, M4C1 CUP 153D230036000066, under program PRIN 2022 (prj code 20229JRTZA). M.E. is funded by the Blavatnik- Caabbidga fellowship, the Cambridge Acceler- ate Programme for Scientific Discovery, and the Maths4DL EPSRC Programme.
6. Conclusion
We introduced GRAMA, novel sequence-based frame- work that enhances the long-range interaction modeling abil- ity and feature update selectivity of Graph Neural Networks (GNNs) through the integration of adaptive neural Autore- gressive Moving Average (ARMA) models with potentially
9

---

Graph Adaptive Autoregressive Moving Average Models
References
Bevilacqua, B., Frasca, E,, Lim, D., Srinivasan, B., Cai, C., Balamurugan, G., Bronstein, M. M., and Maron, H. Equivariant subgraph aggregation networks. In International Conference on Learning Representations, 2022. URL https::/t///....... http:////eeeeeeeeeeeeeeemeeeeeee net. .et.///reeee/t forum?
Abboud, R., Ceylan, i. I., Grohe, M., and Lukasiewicz, T. The surprising power of graph neural networks with ran- dom node initialization. In Proceedings of the Thirtieth International Joint Conference on Artifical Intelligence (IJCAT), 2021.
id-dFbKQaRk15w
Bevilacqua, B., Eliasof, M. Meirom, E., Ribeiro, B., and Maron, H. Efficient subgraph GNNs by learning effective selection policies. In The Twelfth International Confer- ence on Learning Representations, 2024. URL https: / //openreview.. net/ wwwrumiiddgpplgaaaa
Abujal-Haija, S., Perozzi, B., Kapoor, A., Alipourfard, N., Lerman, K., Harutyunyan, H., Ver Steeg, G., and Gal- styan, A. Mixhop: Higher-order graph convolutional architectures via sparsified neighhorhood mixing. In In- ternational Conference Machine Learning, pp. 21-29. PMLR, 2019.
Bianchi, F. M., Grattarola, D., Livi, L., and Alippi, C. Graph neural networks with convolutional arma filters. IEEE Iransactions on pattern analysis and machine intelligence, 44(7):349-33077, 2021.
Alon, U. and Yahav, E. On the bottleneck of graph neural networks and its practical implications. In In- ternational Conference on Learning Representations, 2021. URL
wwwppeeeewwwneeeeeeeooeeee 1d=1800PhocvH2.
Bo, D., Wang, X., Shi, C., and Shen, H. Beyond low- frequency information in graph convolutional networks. Proceedings of the AAAI Conference on Artificial Intel- ligence, 35(5):3950-3957) May 2021. doi: 10.1609/ aaai.v35is. 16514. URL /ttL:ttts://ossaaatt index. php/ AAAI /AAa///atttllleeeee///////
Aoki, M. State Space Models: A Unifying Framework. Springer, Berlin, Germany, 2013. ISBN 978-3-642- 35040-6.
Arjovsky, M., Shah, A., and Bengio, Unitary evolution recurrent neural networks. In International conference on machine learning, pp. 1120-1128 128. PMLR, 2016.
Bouritsas, G., Frasca, F., Zafeiriou, S., and Bronstein, M. M. Improving graph neural network expressivity via sub- graph isomorphism counting. IEEE Transactions on Pat- tern Analysis and Machine Intelligence, 45(1):657-668, 2022.
Arroyo, A., Gravina, A., Gutteridge, B., Barbero, F., Gal- licchio, C., Dong, X., Bronstein, M., and Vandergheynst, P. On vanishing gradients, over-smoothing, and over- squashing in gnns: Bridging recurrent and graph learning. arXiv preprint arXiv:2502. 2025.
Box, G. E., Jenkins, G. M., and Reinsel, G. C. Time Series Analysis: Forecasting and Control. Holden-Day, 1970.
Back, M., DiMaio, F., Anishchenko, I., Dauparas, J., Ovchinnikov, S., Lee, G. R., Wang, J., Cong, Q., Kinch, L. N., Schaeffer, R. D., et al. Accurate prediction of pro- tein structures and interactions using a three-track neural network. Science, 373(655))8711-866 2021.
Bresson, X. and Laurent, T. Residual Gated Graph Con- vNets. arXiv preprint arXiv:1711.07533 2018.
Bronstein, M. M., Bruna, J., Cohen, T., and Veličković, P. Geometric deep learning: Grids, groups, graphs, geodesics, and gauges. arXiv preprint arXiv:2104.134 2021.
Bai, J., Zhu, J., Song, Y., Zhao, L., Hou, Z., Du, R., and Li, H. A3T-GCN: Attention Temporal Graph Convolutional Network for Traffic Forecasting. ISPRS International Journal of Geo- -noommffom,noon, 10(7), 2021. ISSN 2220- 9964. doi: 10.3390/igi100700443
Bruna, J., Zaremba, W., Szlam, A., and LeCun, Spec- tral networks and locally connected networks on graphs. arXiv preprint
2013.
Beck, M., Pöppel, K., Spanring, M., Auer, A., Prudnikova, O., Kopp, M., Klambauer, G., Brandstetter, J., and Hochreiter, S. xlstm: Extended long short-term mem- ory. arXiv preprint arXiv:2405.0457 2024.
Cai, and Wang, Y. A note on over-smoothing for graph neural networks. arXiv preprint arXiv:2006.133: 2020.
Chamberlain, B. P., Rowbottom, J., Gorinova, M., Webb, S., Rossi, E., and Bronstein, M. M. GRAND: Graph neural diffusion. In International Conference on Machine Learning (ICML), pp. 1407-1418, PMLR, 2021.
Behrouz, A. and Hashemi, F. Graph Mamba: Towards Learning on Graphs with State Space Models, 2024. URL patps://arxxrr
org/ abs 22022402222 08678.
Chen, M., Wei, Z., Huang, Z., Ding, B., and Li, Y. Simple and Deep Graph Convolutional Networks. In III, H. D. and Singh, A. (eds.), Proceedings of the 37th Interna- tional Conference on Machine Learning, volume 1 119 of
Bengio, Y. Simard, P., and Frasconi, P. Learning long-term dependencies with gradient descent is difficult. IEEE transactions on neural networks, 5(2):157-166, 1994.
10

---

Graph Adaptive Autoregressive Moving Average Models
Proceedings of Machine Learning Research, pp. 1725- 1735. PMLR, 13-18 Jul 2020.
Di Giovanni, F., Giusti, L., Barbero, F., Luise, G., Liò, P., and Bronstein, M. On over-squashing in message passing neural networks: the impact of width, depth, and topology. In Proceedings of the 40th International Conference on Machine Learning, ICML'23. JMLR.org, 2023.
Chen, Q., Wang, Y., Wang, Y., Yang, J., and Lin, Z. Optimization-inuuer -nnduced graph implicit nonlinear diffusion. In International Conference on Machine Learning, pp. 3648-360 31683366..110 PMLR, 2022.
Ding, Y. Orvieto, A., He, B., and Hofmann, T. Recurrent distance filtering for graph representation learning. In Forty-first International Conference on Machine Learn- ing, 2024.
Chen, T. Q.. Rubanova, Y., Bettencourt, J., and Duvenaud, D. K. Neural ordinary differential equations. In Ad- vances in Neural Information Processing Systems, pp- 6571-6583, 2018.
Du, I.., Shi, X., Fu, Q. Ma, X., Liu, H., Han, S., and Zhang. D. Gbk-gnn: Gated bi-kernel graph neural net- works for modeling both homophily and heterophily. In Proceedings of the ACM Web Conference 2022, WWW '22. pp. 1550-1558, New York, NY, USA, 2022. Associa- tion for Computing Machinery. ISBN 9781 9781450390965. doi: 10.1 10.1144534854473552221 URL https: /doi.
Chien, E., Peng, J., Li, P., and Milenkovic, O. Adaptive universal generalized pagerank graph neural network. In International Conference on Learning Representations, 2021. URL hwtpshtt////..... http://peneeeeeeeeeeeeeeeeeeeeee id=n6j17fLxx
Choi, J., Hong, S., Park, N., and Cho, S.-B. Gread: Graph neural praction-diffusion networks. In ICML, 2023.
org 10. 1145/ 001111//345544 0T1154447..1121.11.1
Dwivedi, V. and Bresson, X. Benchmarking graph trans- formers. Journal of Machine Learning Research, 23: 1-32, 2022.
Choromanski, K., Kuczynski, M., Cieszkowski, J., Belet- sky, P. L., Smith, K. M., Gajewski, W., Masson, G. D., Broniatowski, T. Z., Gorny, A. B., Kaczmarek, L. M., and Andrzejewski, S. K. Performers: A new approach to scaling transformers. Proceedings of the 37th In- teraational Conference on Machine Learning (ICML), pp. 2020-20311 2020. URL abs/2009 14743.
Dwivedi, V., Bresson, X., and Wolf, L. Benchmarking graph neural networks. Proceedings of the International Conference on Learning Representations (ICLR), 2021.
/rrg/
Dwivedi, V. P. and Bresson, X. A Generalization of Trans- former Networks to Graphs. AAAI Workshop on Deep Learning on Graphs: Methods and Applications, 2021.
Choromanski. K., Lin, H., Chen, H., Zhang, T., Sehanobish, A., Likhosherstov, V., Parker-Holded J., Sarlos, T., Weller, A., and Weingarten, T. From block-toeplitz matrices to differential equations on graphs: towards general theory for scalable masked transformers. In Proceedings of the 39th International Conference on Machine Learning, volume 162, pp. 3962-3983. PMLR, 2022.
Dwivedi, V. P., Luu, A. T., Laurent, T., Bengio, Y., and Bres- son, X. Graph neural networks with learnable structural and positional representations. In International Confer- ence on Learning Representations, 2022a. URL https: / opeeneeview. net forum? wtwprrummmidwwTTTTnnaac
Dwivedi, V. P., Rampášck, L., Galkin, M., Parviz, A., Wolf, G., Luu, A. T., and Beaini, D. Long Range Graph Bench- mark. In Advances in Neural Information Processing Sys- tems, volume 35, pp. Inc., 2022b.
De, S., Smith, L., Fernando, A., Botev, A., Cristian- Muraru, G., Gu, A., Haroun, R., Berrada, L., Chen, Y., Srinivasan, S., et al. Griffin: Mixing gated linear recur- rences with local attention for efficient language models. arXiv preprint 240. 2024.
Curran Associates,
Dwivedi, V. P., Joshi, C. K., Luu, T. Laurent, T., Bengio, Y., and Bresson, X. Benchmarking graph neural net- works. Journal of Machine Learning Research, 24(43): 48, 2023. URL http:// /jjmrr famlr.org//oooo...moom.mom.ooooo httg:/aprrs///// /v24/ 22 0567-567770 .tmll
de Jong, P. and Penzer, J. The arma model in state space form. Statistics & probability leteer,, 70(1):119-125, 2004.
Defferrard, M., Bresson, X., and Vandergheynst, P. Con- volutional neural networks on graphs with fast localized spectral filtering. Advances in neural information pro- cessing systems, 29, 2016.
Eliasof, M., Haber, E., and Treister, E. PDE-GCN: Novel ar- chitectures for graph neural networks motivated by partial differential equations. Advances in Neural Information Processing Systems, 34:3836-388 08066,339,,0- 2021.
Deng, C., Yue, Z., and Zhang, Z. Polynormer: Polynomial- expressive graph transformer in linear time. In The Twelfth International Conference on Learning Represen- tations, 2024. URL bttpp:://ppnnaee hptp///ppeeeeeece////e/ net./ forum? d=Nmv1
Eliasof, M., Haber, E., and Treister, E. pathgen: Learning general graph spatial operators from paths. In Interna- tional conference on machine learning, pp. 5878-5891. PMLR, 2022.

---

Graph Adaptive Autoregressive Moving Average Models
Eliasof, M., Frasca, F., Bevilacqua, B., Treister, E., Chechik, G., and Maron, H. Graph positional encoding via ran- dom feature propagation. In International Conference Machine Learning, pp. 9202-9223, PMLR, 2023a.
Gravina, A., Bacciu, D., and Gallicchio, C. Anti-Symmetric DGN: a stable architecture for Deep Graph Networks. In The Eleventh International Conference Learning Representutions, 2023. URL https: /openrevie.... net htt./formm?ici fow.fofmmmm-3333cgaaaaaaa
Eliasof, M., Haber, E., and Treister, E. Adr-gnn: advection- diffusion-reacttin graph neural networks. arXiv preprint arXiv:2307.16092, 108, 2023b.
Gravina, A., Gallicchio, C.,, and Bacciu, D. Non- Dissipative Propagation by Randomized Anti-Symmetric Deep Graph Networks. In International Workshops of ECML PKDD 2023, Turin, Italy, September 18-22, 2023, Revised Selected Papers, Part V, 2024a.
Eliasof, M., Bevilacqua, B., Schönlieb, C.-B., and Maron, H. GRANOLA: Adaptive normalization for graph neural net- works. In The Tiirty-eighth Annual Conference on Neural Information Processing Systems, 2024a. URL https: //openreview, net forum? id=dddbbc00000...
Gravina, A., Lovisotto, G., Gallicchio, C., Bacciu, D., and Grohnfeldt, C. Long Range Propagation on Continuous-Time Dynamic Graphs. In Proceed- ings of the 41st International Conference on Machine Learning, volume 235 of Proceedings of Machine Learning Research, pp. 16206-16223 PMLR, 21-27 Jul 2024b. URL https: / http///oooedicceeoooooooo ngs. .mlr. press/v235 http////////aaaaaaa...a. html.
Eliasof, M., Haber, E.,, and Treister, E. Graph neural reaction diffusion models. SIAM Journal on Scientific Computing, 46(4):C399-C48 C420, 2024b.
Eliasof, M., Haber, E., Treister, E., and Schönlieb, C.-B. B. On the temporal domain of differential equation inspired graph neural networks. In Internationall Conference on Ar- rificial Intelligence and Statistics, pp. 1792-1800. PMLR, 2024c.
Gravina, A., Zambon, D., Bacciu, D., and Alippi, Temporal graph odes for rregularly-sapplee time se- ries. In Larson, K. (ed.), Proceedings of the Thirty- Third International Joint Conference on Artificial Intel- ligence, IJCAI-24, pp. Conferences on Artificial Intelligence Organization, 8 2024c. doi: 00.249633jjccai.22244444 URL https: 2024/444 445. Main
Errica, F, Christiansen, H., Zaverkin, V., Maruyama, T.,
Niepert, M., and Alesiani, F. Adaptive message pass- ing: A general framework to mitigate oversmoothing, oversquashing, and underreaching, 2024. URL https: //arxiv. org/ www./a///300 2212233122222 16560.
International Joint
/ l/dpi.org///oooo /ttrg//1.2299333.. Track.
Finkelshtein, B., Huang, X., Bronstein, M. M., and Ceylan, I. Cooperative Graph Neural Networks. In Forty- first International Conference on Machine Learning, net. forum?
Gravina, A., Eliasof, M., Gallicchio, C., Bacciu, D., and Schönlieb, C.-B. On Oversquashing in Graph Neural Networks Through The Lens of Dynamical Systems. In The 39th Annual AAAI Conference on Artificial Intelli- gence, volume 39, pp. 16906-16914, Apr. 2025. doi: 10. 10.6/6a/aaii.no http://aai.v991666... 39116.3388..
2024. URL id 2d=20ogXCUXXD.
Freitas, S., Dong, Y., Neil, J., and Chau, D. H. A large-scale database for graph representation learning. In Vanschoren, J. and Yeung, S. (eds.), Proceedings of the Neural Infor- mation Processing Systems Track on Datasets and Bench- marks, volume 1, 2021.
Gu, A., Goel, K., and Ré, Efficiently modeling long sequences with structured state spaces. arXiv preprint arXiv:2111.00396, 2021a.
Fu, D., Ma, Y., and Qian, Y. S4: Structured state space for scalable and efficient sequence modeling. Proceedings of the 41 International Conference on Machine Learning (ICML), 2023.
Gu, A., Johnson, I., Goel, K., Saab, K., Dao, T., Rudra, A., and Ré, C. Combining recurrent, convolutional, and continuous-tin models with linear state space layers. Advances neural information processing systems, 34: 572-585, 2021b.
Gasteiger, J., WeiB enberger, S., and Günnemann, S. Diffu- sion Improves Graph Learning. In Advances in Neural Information Processing Systems, volume 32. Curran As- sociates, Inc., 2019.
Gu, A., Fu, Y., and Liu, E. J. Mamba: flexible mecha- nism for long-range dependencies in state space models. NeurIPS, 2023.
Gravina, A. and Bacciu, D. Deep Learning for Dynamic Graphs: Models and Benchmarks. IEEE Transactions on Neural Networks and Learning Systems, pp. 1-14, 2024. doi: 10. 1109/NNN.S 2024.3379735.
Gu, F., Chang, H., Zhu, W., Sojoudi, S., and El Ghaoui, L. Implicit graph neural networks. Advances in neural information processing systems, 33:1 1994-119993 2020.
12

---

Graph Adaptive Autoregressive Moving Average Models
Gu, S., Yu, X., and Chao, V. K. Structured state space models for efficient sequence modeling. Proceedings of the 38th International Conference Machine Learning (ICML), 2021c.
Hu, W., Liu, B., Gomes, J., Zitnik, M., Liang, P., Pande, V., and Leskovec, J. Strategies for Pre-training Graph Neural Networks. In International Conference on Learning Rep- resentations, 2020b. URL https:: https://openzevier. net/ forum? ? d=HJ] WWJSFDH.
Gutteridge, B., Dong, X., Bronstein, M. M., and Di Gio- vanni, F. Drew: Dynamically rewired message pass- ing with delay. In International Conference on Machine Learning, pp. 12252-12677. PMLR, 2023.
Huang, G., Liu, Z.,, Van Der Maaten, L.,, and Weinberger, K. Q. Densely comnected convolutional networks. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 4700-4708, 2017.
Hamilton, J. D. Time Series Analysis. Princeton University Press, 1994a.
Huang, Y., Lu, W., Robinson, J., Yang. Y., Zhang, M.. Jegelka, S., and Li, P. On the stability of expressive positional encodings for graphs. In The Twelfth In- lernational Conference on Learning Representations, 2024a. URI.https. id Ad=xAqcJ9X6TT.
Hamilton, D. State-space models. Handbook of econo- metrics, 4:3039-3000 -080, 1994b.
wtt.hhtpss:/opeeeevieeeee /tpp///pppeeeeeeeeee/ee/ee net.///wweeeeeeeeeeeeeeeeeeeeeee forum?
Hamilton, W. L., Ying. R., and Leskovec, J. Inductive representation learning on large graphs. In Proceedings of the 31st International Conference on Neural Information Processing Systems, NIPS' 17, pp. 1025-1035 Curran Associates Inc., 2017. ISBN 9781510860964.
Huang, Y., Miao, S., and Li, P. What can we learn from state space models for machine learning on graphs? arXiv 2024b.
preprint urXiv:2406.0580
Huang, Z., Wang, Y., Li, C., and He, H. Going deeper into permutation-sensiitve graph neural networks. In confete conference on machine learning, pp. 9377- International
He, K., Zhang, X., Ren, S., and Sun, J. Deep residual learn- ing for image recognition. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 770-778, 2016.
9409. PMLR, 2022.
Hussain, M. S., Zaki, M. and Subramanian, D. Global self-attention as replacement for graph convolution. arXiv preprint ar.ii:2108.003:44 2021.
Heilig, S., Gravina, A., Trenta, A., Gallicchio, C., and Bac- ciu, D. Hortttamiltonian Architectural Bias for Long- Range Propagation Deep Graph Networks. In The Thir- teenth International Conference on Learning Represen- tations, 2025. URL https: //te:://oooeee wpw.revieeeeeeeeeeeeeeeeee.eeeee net./ forum? Lrruummiddd3EESSCCUU
Isufi, E.,, Loukas, A., Simonetto, A., and Leus, G. Autore- gressive moving average graph filtering. IEEE Transac- tions Signal Processing, 65(2):274 288, 2016.
Hirst, H. P. and Macey, W. T. Bounding the roots of polyno- mials. The College Mathematics Journal, 28(4):292-295, 1997.
Kang, Q. Zhao, K., Ding, Q., Ji, F., Li, X., Liang, W., Song, Y., and Tay, W. Unleashing the potential of fractional calculus in graph neural networks with FROND. In The Twelfth International Conference Learning Representations, 2024. URL https: httpthtt////eeeeeeee/e /op.neeeee.ee.eeee/eeee net
Hochreiter, S., Bengio. Y., Frasconi, P., Schmidhuber, J., et al. Gradient flow in recurrent nets: the difficulty of learning long-term dependencies, 2001.
Karhadkar, K., Banerjee, P. K., and Montufar, G. FoSR: First-order spectral rewiring for addressing oversquash- ing in GNNs. In The Eleventh International Confer- ence on Learning Representations, 2023. URL https: / //openrevien ew net. forum? (ow.rrrmmmnnooooooooooo j0
Horn, R. A. and Johnson, C. R. Matrix analysis. Cambridge university press, 2012.
Hu, W., Fey, M., Zitnik, M., Dong, Y., Ren, H., Liu, B., Catasta, M., and Leskovec, J. Open graph benchmark: Datasets for machine learning on graphs. In Larochelle, H. Ranzato, M. Had- sell, R., Balcan, M., and Lin, H. (eds.), Advances in Neural Information Processing Systems, vol- ume 33, pp. 22118-22133. Curran Associates, Inc., 2020a. URL httpss:/pprcceedigggs.. rew.reeeeeddii....e............ cc/ httpppee__fllsssppprr/////////// 2200411aacct/223e443322256663333 Papee.
Khalil, H. K. Nonlinear Systems. Prentice Hall, Upper Sad- dle River, NJ, 3rd edition, 2002. ISBN 978-0130673893,
Khemani, B., Patil, S., Kotecha, K., and Tanwar, review of graph neural networks: concepts, architectures, techniques, challenges, datasets, applications, and future directions. Journal of Big Data, 11(1):18, 2024.
Kipf. T. and Welling, M. Semi-supervised classification with graph convolutional networks. Proceedings of the
pdf.
13

---

Graph Adaptive Autoregressive Moving Average Models
International Conference on Learning Representations, 2016.
Learning Research, pp. 23321-23337. PMLR,, 23-29 Jul 2023. URL http.ttttpppppprreeediooo ml press/ v202 mammmm222h.hm
Kong, K., Chen, J., Kirchenbauer, J., Ni, R., Bruss, C. B., and Goldstein, T. GOAT: A global transformer large- scale graphs. In Krause, A., Brunskill, E., Cho, K., Engelhardt, B., Sabato, S., and Scarlett, J. (eds.), Pro- ceedings of the 40th International Conference on Ma- chine Learning, volume 202 of Proceedings of Machine Learning Research, pp. 17375-17390. PMLR, 23-29 Jul 2023. URL https: http//prreeeeng..eeee// mlr. press/ 1202/kong22 html.
Mantri, K. S. I., Wang, X., Schönlieb, C.-B., Ribeiro, B., Bevilacqua, B., and Eliasof, M. DiGRAF: Diffeomorphic graph-adaptive activation function. In The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024. URL httpsttp///t....t. openreview net./ forum?id-zzow/ 231e4.
Maskey, S., Paolino, R., Bacho, A., and Kutyniok, G. A fractional graph laplacian approach to oversmoothing. In Thirty-seventh Conference on Neural Information Pro- cessing Systems, 2023. URL https: http:////ppeeeiiieeeeeeee net/ httt/forrmmidd=s770 7eE74.
Kreuzer, D., Beaini. D., Hamilton, W., Létourneau, V., and Tossou, Rethinking graph transformers with spectral attention. Advances in Neural Information Processing Systems, 11:21618-21622 2021a.
Maurya, S. K., Liu, X., and Murata, T. Simplifying approach to node classification in graph neural networks. Journal of Computational Science, 62:101695, 2022. ISSN 1877- 7503. doi: http::/dbbiorr//000011..eee00000 URL
Kreuzer, M. et al. Positional encodings in graph transform- ers. IEEE Transactions on Patlern Analysis and Machine Intelligence, 43:345-356, 2021b.
Kreuzer, S., Reiner, M., and Villiers, S. D. D. D. Sant: Structural attention networks for graphs. Proceedings of the 38th International Conference on Machine Learning (ICML), 2021c.
Micheli, A. Neural Network for Graphs: A Contextual Constructive Approach. IEEE Transactions on Neural Networks, 20(3)499-511, 2009.
Li, X., Zhu, R., Cheng, Y., Shan, C., Luo, S., Li, D., and Qian, W. Finding global homophily in graph neural Chaudhuri, K., Jegelka, S., Song. L., Szepesvari, C., Niu, G., and Sabato, S. (eds.), Proceedings of the 39th International Confer- ence on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pp. 13252-13256. PMLR, 17-23 Jul 2022. URL https::/pp/oo....tt. http:///poceeedi.....o mlrr. press/ v1 62. / i 22ad. html.
Morris, C., Ritzert, M., Fey, M., Hamilton, W. L.., Lenssen, J. E., Rattan, G., and Grohe, M. Weisfeiler and leman go neural: Higher-order graph neural networks. In Pro- ceedings of the AAAI conference artificial intelligence, volume 33, pp. 4602 4609, 2019.
networks when meeting heterophily.
Müller, L., Galkin, M., Morris. C., and Rampášek, L. Attending to graph transformers. Transactions on Machine Learning Research, 2024. ISSN 2835- 8856. URL httptp:::// /pppnrvveeeeeeeeeeeoeeeeee / i Hd-HhbgHBBrfZ.
net/ forum?
Likhobaba, D., Pavlichenko, N., and Ustalov, D. Toloker Graph: Interaction of Crowd Annotators, Febru- ary 2023. URL https://doi. /10g/10.00 5281/ zenodo. 7620796.
Murphy, R., Srinivasan, B., Rao, V., and Ribeiro, B. Re- lational pooling for graph representations. In Interna- tional Conference on Machine Learning, pp. 4663-4673, PMLR, 2019a.
Liu, C., Li, H., and Xu, T. Mamba: Beyond long sequences. Proceedings of the Conference on Computer Vision and Pattern Recognition (CVPR), 2024.
Murphy, R. L., Srinivasan, B., Rao, V., and Ribeiro, B. Janossy pooling: Learning deep cnnpuuttaiionnnvvriann functions for variable-size inputs. In International Confer- ence on Learning Representations, 2019b. URL https: // /ppenreview. net forumoooummmmm Bi----ddd---B--BFFFF
Luan, S., Hua, C., Lu, Q. Ma, L., Wu, L., Wang, X., Xu, M., Chang, X.-W., Precup, D.,. Ying, R., Li, S. Z., Tang, J., Wolf, G., and Jegelka, S. The heterophilic graph learning handbook: Benchmarks, models, theoret- ical analysis, applications and challenges, 2024. URL 09618.
Nguyen, H. al. Efficiency in state space models for se- quence learning. Journal of Machine Learning Research, 24:3678-3666 2023.
ht https: /arxivi..vv.////iva//aaaa//aaavv org/abs/////eoooooooo.ooo.e
Ma, L., Lin, C., Lim, D., Romero-Soriano, A., Dokania, P. K., Coates, M., Torr, P., and Lim, S.-N. Graph induc- tive biases in transformers without message passing. In Proceedings of the 40th International Conference on Ma- chine Learning, volume 202 of Proceedings of Machine
Niepert, M., Ahmed, M., and Kutzkov, K. Learning con- volutional neural networks for graphs. In International conference on machine learning, pp. 201220112200 2023. PMLR, 2016.
14

---

Graph Adaptive Autoregressive Moving Average Models
Nt, H. and Maehara, T. Revisiting graph neural net- works: All we have is low-pass filters. arXiv preprint arXiv:1905.09550 2019.
Rusch, T. K., Chamberlain, B., Rowbottom, J., Mishra, S., and Bronstein, M. Graph-coupled oscillator networks. In International Conference on Machine Learning, pp. 18888 18988. PMLR, 2022.
Oono, K. and Suzuki, T. Graph neural networks exponen- tially lose expressive power for node classification. In International Conference on Learning Representations, htttp:://ppereeeeiieett http://ppptpeeeeeeeeeepeeeeeeeet httpreewwwwwneeeeeeeeeeeeeeeeeee forum? id=s11d02EFPr:
Rusch, T. K., Bronstein, M. M., and Mishra, A Survey Oversmoothing in Graph Neural Networks. arXiv preprint arXiv:2303.1099 2023.
2020. URL https::////.
Ruthotto, L. and Haber, E. Deep neural networks motivated by partial differential equations. Journal of Mathematical Imaging and Vision, 62:352-364, 2020.
Orvieto. A., De, S., Gulcehre, C., Pascanu, R., and Smith, L. On the universality of linear recurrences followed by nonlinear projections. arXiv preprint arXiv:2307.11888 2023a.
Sato, R., Yamada, M., and Kashima, H. Random features strengthen graph neural networks. In Proceedings of the 2021 SIAM international conference on data mining (SDM), pp. 333-341. SIAM, 2021.
Orvieto, A., Smith, S. L., Gu, A., Fernando, A., Gulcehre, C., Pascanu, R., and De, S. Resurrecting recurrent neural networks for long sequences. In International Conference on Machine Learning, pp. 26670-26699 PMLR, 2023b.
Scarselli, F., Gori, M., Tsoi, A. C.,, Hagenbuchner, M., and Monfardini, G. The graph neural network model. IEEE transactions on neural networks, 20(1):61-80, 2008.
Pan, H. and Kondor, R. Permutation equivariant layers for higher order interactions. In International Conference Artificial Intelligence and Statistics, pp. 5987-6001. PMLR, 2022.
Schatzki, L., Larocca, M., Nguyen, Q. T., Sauvage, F., and Cerezo, M. Theoretical guarantees for permutation- equivariant quantum neural networks. npj Quantum In- formation, 10(1):12, 2024.
Pascanu, R.
On the difficulty of training recurrent neural networks. arXiv preprint arXiv: 1211::211.5063 2013.
Pei, H., Wei, B., Chang, K. C.-C., Lei, Y., and Yang, B. Geom-gen: Geometric graph convolutional networks. In International Conference on Learning Representations, wwwprreviiennett/oooeeeeeeeeeeee nnt//frunt
Shi, Y., Huang, Z., Feng, S., Zhong, H., Wang, W., and Sun, Y. Masked label prediction: Unified mes- sage passing model for semi-supervised classification. Zhou, Z.-H. (ed.), Proceedings of the Thirtieth In- ternational Joint Conference on Artificial Intelligence, ICCII221, pp. 1548-1554. International Joint Confer- ences Artificial Intelligence Organization, 2021. doi: /00.9663/jcai.222//211 URL https: / http///o.oooo org/ NB.24963/ijje http://jaaaa.211/12211 Main Track.
2020. URL https: id=Sle2agrFVS.
Platonov, O., Kuznedelev, D.,, Diskin, M., Babenko, A., and Prokhorenkova, I.. A critical look at the evaluation of GNNs under heterophily: Are we really making progress?
In The Eleventh International Conference on Learning Representations, 2023. URL https: opw.revien.eeeeeee net/ forum? wwt.mmittttttbttteeeeeoob 5wv.
Shirzad, H., Velingker, A., Venkatachalam, B., Sutherland, D. J., and Sinop, A. K. Exphormer: Sparse transform- ers for graphs. In International Conference Machine Learning, pp. 31613-31633 PMLR, 2023.
Poli, M.. Massaroli, S., Park, J., Yamashita, A., Asama, H., and Park, J. Graph neural ordinary differential equations. arXiv preprint arXiv: 191 arXiv:1911.072 1911.753 2019.
Slotine, J.JJ E., Li, W., al. Applied nonlinear control, volume 199. Prentice hall Englewood Cliffs, NJ, 1991.
Rampášek, L., Galkin, M., Dwivedi, V. Luu, A. T. Wolf, G., and Beaini, D. Recipe for General, Powerful, Scal- able Graph Transformer. Advances in Neurul Information Processing Systems, 35, 2022.
Sun, J., Wang, S., Han, X., Xue, Z., and Huang, Q. All in a row: Compressed convolution networks for graphs. International Conference on Machine Learning, pp. 33061 -33076. PMLR, 2023.
Rozemberezki, B., Scherer, P., He, Y., Panagopoulos, G., Riedel, A., Astefanoaci, M., Kiss, O., Beres, F., López, G. Collignon, N., and Sarkar, R. Pytorch geometric tem- poral: Spatiotemporal signal processing with neural ma- chine learning models. In Proceedings of the 30th ACM International Conference on Information & Knowledge Association for Computing Machinery, 2021. ISBN 9781450384469, doi: 10.1 11443459637.442201
Sun, J., Yang, C., Ji, X., Huang, Q., and Wang, S. Towards dynamic message passing on graphs. The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024. URL https: Forum?ide 411.111--E.......
httttss:/ppeneeiiier hwwp///veeeeeeeeeeeoeeeee .nt//
Management, CIKM '2,, pp.
Tönshoff, J., Ritzert, M., Rosenbluth, E., and Grohe, M. Where did the gap go? reassessing the long-range graph
15

---

Graph Adaptive Autoregressive Moving Average Models
benchmark. In The Second Learning on Graphs Con- ference, 2023. URL https: httphhht//ppeeeeeeeeeeeeee/e http://ppneeeeeeeeeeeeeeeeeeeeee
Wu, Y., Xu, Y., Zhu, W., Song, G., Lin, Z., Wang, L., and Liu, S. Kdlgt: A linear graph transformer framework via kernel decomposition approach. In ICCAI, pp. 2370-2378, 2023.
Topping, M., Ruder, S., and Dyer, C. Understanding over- smoothing in graph neural networks. Proceedings of the 39th International Conference on Machine Learning (ICML), 2022.
Xu, K., Li, C., Tian, Y., Sonobe, T., Kawarabayashi, K.- i., and Jegelka, S. Representation learning on graphs with jumping knowledge networks. In Dy, J. and Krause, A. (eds.), Proceedings of the 35th International Confer- ence on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pp. 5453-5461 PMLR, 10-15 Jul 2018. URL http: http::ttpp://poeeeeeeeoo /ttp//oocceeeceeeeo ngs m press/ vvB0/v/00//0 /0/ xu1 8c. html.
Vaswani, A. et al. Attention is all you need. Advances in Neural Information Processing Systems, 30, 2017.
Veličković, P. Cucurull, G., Casanova, A., Romero, A., Liô, P., and Bengio, Y. Graph attention networks. In International Conference on Learning Representations, 2018. URL
Xu, K., Hu, W., Leskovec, J., and Jegelka, S. How powerful are graph neural networks? In International Conference on Learning Representations, 2019. URL https:// openreview net wttp:/eeeeettttttteteeeeeeeeeeee 61A5kkm
id=rJXMpikCZ.
Wang, C., Tsepa, O., Ma, J., and Wang, B. Graph-mamba: Towards long-range graph sequence modeling with se- lective state spaces. arXiv preprint arXiv:2402.00789, 2024a.
Yang, Z., Cohen, W. W. and Salakhutdinov, R. Revisit- ing semi-supervised learning with graph embeddings. In Proceedings of the 33rd International Conference on In- ternational Conference on Machine Learning Volume 48, ICML' 16, pp. 40-48. JMLR.org, 2016.
Wang, K., Zhang, G., Zhang, X., Fang. J., Wu, X., Li, G., Pan, S., Huang, W., and Liang, Y. The heterophilic snowflake hypothesis: Training and empowering gnns for heterophilic graphs. In Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, KDD '24, pp. 3164-3175, New York, NY, USA, 2024b. Association for Computing Machinery. ISBN 9798400704901. doi: 10. 2211144/66772866777777
Ying, Z. and Leskovec, J. Graphormer: A transformer for graphs. Proceedings of the 43rd International ACM SIGIR Conference on Research and Development in In- formation Retrieval, 2021.
Yu, Y., Si, X., Hu, C., and Zhang, J. A review of recurrent neural networks: Lstm cells and network architectures. Neural computation, 31(77:1235-111
Wang, X. and Zhang, M. How powerful are spectral graph neural networks. In Chaudhuri, K., Jegelka, S., Song, L., Szepesvari, C., Niu, G., and Sabato, S. (eds.), Pro- ceedings of the 39th International Conference on Ma- chine Learning, volume 162 Proceedings of Machine Learning Research, pp. 23341 233662. PMLR, 17-23 Jul 2022. https: / http:/poocednnnge egge mlr .press/////// v1 62 wwng22am. html.
2019.
Yun, S. et al. Graph transformers for long-range depen- dencies. IEEE Transactions on Neural Networks, 30: 2451 2019.
Zaheer, M., prasad G. H., G., Wang. L., Wang, S. V. K. N. L., Li, Y., Konečný, J., Joshi, S., Chen, D., R., J. R., Zhang, Z., Devaraj. S., and Narayanan, S. Big- bird: Transformers for longer sequences. Proceedings of the 37th International Conference on Machine Learn- ing (ICMI.), pp. 12168-12178, 2020. URL https: //arxiv. org/ abs 220//0000011 14062.
Wang, Y., Wang, Y., Yang, J., and Lin, Z. Dissecting the Diffusion Process in Linear Graph Convolutional Net- works. In Advances in Neural Information Processing Systems, volume 34, pp. 5758-5769 Curran Associates, Inc., 2021.
Wang, Y., Yi, K., Liu, X., Wang, Y. G., and Jin, S. ACMP: Allen-cahn message passing with attractive and repul- sive forces for graph neural networks. The Eleventh International Conference on Learning Representations, 2023. URL https::////..........ttt wptp//wwewweeeeeeeeeeeee f id=4f2c_791e 79Lrqs.
Zhang, K., Hao, M., Wang, J., de Silva, C. W., and Fu, C. Linked dynamic graph cnn: Learning on point cloud via linking hierarchical features. arXiv preprint 1e0::9944.0011. 2019.
Zhao, K., Kang, Q. Song, Y., She, R., Wang. S., and Tay, W. P. Graph neural canvection-iiffsiii with heterophily. Proc. International Joint Conference on Artificial In- telligence, Macao, China, Aug 2023.
Whittle, P. Hypothesis Testing in Time Series Analysis. Statistics Uppsala universitet. Almqvist & Wiksells boktr., 1951. ISBN 9780598919823.
16

---

Graph Adaptive Autoregressive Moving Average Models
Zhao, L., Song, Y., Zhang, C., Liu, Y., Wang, P., Lin, T., Deng, M., and Li, H. T-GCN: A Temporal Graph Convo- lutional Network for Traffic Prediction. IEEE Transac- tions on Intelligent Transportation Systems, 21(9))3848- 3858, 2020. doi: 20110099TTSS.21192995111
Zhu, J., Yan, Y., Zhao, I.., Heimann, M., Akoglu, I.,, and Koutra, D. Beyond homophily in graph neural networks: Current limitations and effective designs. In Larochelle, H., Ranzato, M., Hadsell, R., Balcan, M., and Lin, H. (eds.), Advances in Neural Information Processing Sys- tems, volume 33, pp. 7793-7804, Curran Associates, Inc., 2020.
Zhu, J., Rossi, R. A., Rao, A., Mai, T., Lipka, N., Ahmed, N. K., and Koutra, D. Graph neu- ral networks with heterophily. Proceedings of the AAAI Conference on Artificial Intelligence, 35(12): 11168-11176, May 2021. doi: 10.1609/aai.vv3511.. 17332. URL https://ojs.aat org/ index. http:/AA/aaaiiclleeeee///33
Zhuang, J., Dvornek, N., Li, X., and Duncan, S. Ordinary differential equations graph networks. 2020.
17

---

Graph Adaptive Autoregressive Moving Average Models
Author Contributions
AG and AC recognized the problem of developing a principled integration of State Space Models in Graph Neural Networks. ME proposed the connection between SSMs and ARMA models, and conceptualized the methodology and method development. ME and AG conducted the empirical evaluation. The theoretical analysis was carried out by ME and AC. The original draft was written by ME, AG, and AC. DB, CG, and CBS contributed to the review and editing of the manuscript and supervised the project.
A. Additional Related Work
GNNs based on Differential Equations. Building on the interpretation of convolutional neural networks (CNNs) as discretizations of ODEs and PDEs (Ruthotto & Haber, 2020; Chen et al., 2018; Zhang et al., 2019), several works, including GCDE (Poli et al., 2019), GODE (Zhuang et al., 2020), and GRAND (Chamberlain et al., 2021), among others, view GNN layers as discretized steps of the heat equation. This framework helps manage diffusion (smoothing) and sheds light on the oversmoothing problem in GNNs (Nt & Maehara, 2019; Oono & Suzuki, 2020; Cai & Wang, 2020). In contrast, Choromanski et al. (2022) introduced an attention mechanism based on the heat diffusion kernel. Other models, such as PDE-GCNM (Eliasof et al., 2021) and GraphCON (Rusch et al., 2022), combine diffusion with oscillatory processes to maintain feature energy. Recent work has explored anti-symmetry (Gravina et al., 2023; 2024a; 2025), reaction-diffusiig dynamics (Wang et al., 2023; Choi et al., 2023; Eliasof et al., 2024b), convection (Zhao et al., 2023), advection (Eliasof et al., 2023b), port-Hamiltonian systems (Heilig et al., 2025), fractional Laplacian ODEs (Maskey al., 2023), and higher-order methods (Eliasof et al., 2024c; Kang et al., 2024). While most of the aforementioned methods works in the setting of static graphs, temporal aspects are addressed in (Gravina et al., 2024b;c). Overall, we refer to this family of models as DE-GNNs, These models are related to SSM models, which are also based on ODEs. Also, some of the DE-GNNs were shown to be effective against oversquashing as architectures, and therefore we include them in our experimental comparisons.
Multi-hop GNNs. Multi-hop GNN architectures were extensively studied in previous years, leading to several popular architectures such as JK-Net (Xu et al., 2018), MixHop (Abu-El) Bai--EE-Haaa El-Haija al., 2019), and more recently DRew (Gutteridge al., 2023). These works take inspiration from earlier works like DenseNets (Huang et al., 2017), where the main idea is to consider a combination of feature maps from multiple layers, instead of only considering the last layer feature map as in ResNets (He et al., 2016). We now distinguish our GRAMA from JK-Net, MixHop, and DRew. First, these methods do not stem from a dynamical system perspective that allows the construction of models like ARMA or SSM. Second, methods like JK-Net can become computationally expensive if many layers are used within a network, as it considers all previous layers, and is only used within the final layer in a GNN, rather than an architecture that considers multiple past values at each layer of the network. Third, in GRAMA we propose a selective attention mechanism to ARMA coefficients, as described in Section 3.2. Compared with MixHop, which performs dense, non-recurrent projections, GRAMA uses a recurrent, non-dense aggregation inspired by dynamical systems and modern RNNs. A deeper theoretical and empirical comparison with MixHop is discussed in Appendix F.5.
Transforming Graphs to Sequences. In recent years, there has been growing interest in transforming graphs into sequences, with a substantial body of work addressing this problem. The motivation behind this transformation is to leverage well- established sequential learning mechanisms, such as 1D convolutions (Niepert et al., 2016; Eliasof et al., 2022; Sun et al., 2023), RNNs (Murphy et al., 2019a; Huang et al., 2022), and GRUs and LSTMs (Murphy et al., 2019b). Overall, these works propose various methods for converting graphs into sequences, often accompanied by theoretical insights into permutation equivariance, typically achieved in expectation under such transformations. In contrast, our GRAMA, adopts different perspective: rather than mapping a graph to a single sequence, we construct a sequence of graphs. This design preserves permutation equivariance and enables the modeling of long-range interactions through our neural ARMA framework.
Adaptivity in Graph Learning. In recent years, it has been increasingly recognized that adaptivity plays a crucial role in graph learning, both in improving downstream performance and addressing fundamental limitations of classical GNNs, such as oversmoothing and oversquashing. Notably, adaptive mechanisms have proven effective in graph normalization (Eliasof et al., 2024a) and activation layers (Mantri et al., 2024), enhancing theoretical expressiveness and functional flexibility, respectively. Adaptivity has also been applied to message-ppssingg schemes by enabling selective updates to node features, as explored from various perspectives in Sun et al. (2024); Errica et al. (2024). In this work, we take a different approach by introducing selectivity through learned ARMA coefficients. Specifically, our method, GRAMA, adaptively weighs previous states and residuals based on the input, allowing the model to dynamically modulate states and residuals dependencies.
18

---

Graph Adaptive Autoregressive Moving Average Models
Expressiveness of GNNs. The expressiveness of graph neural networks (GNNs) is a central aspect of graph representation learning, with much of the theoretical understanding framed through the Weisfeiler-Lehmmnn (WL.) test. Seminal works by Xu et al. (2019); Morris et al. (2019) established that the representational capacity of standard message-passing neural networks (MPNNs) is bounded by the power of the 1-WL test. This insight has motivated a broad line of research aimed at overcoming these limitations, including the use of random node initializations (Sato et al., 2021; Abboud et al., 2021), positional encodings (Eliasof et al., 2023a; Huang et al., 2024a), and subgraph- bbsed architectures (Bevilacqua et al., 2022; 2024), among other approaches and methods. Within this theoretical landseape, our GRAMA is constructed to at least match the expressiveness of its underlying GNN backbone. This is achieved through its recurrent structure, which updates representations by aggregating both current and past hidden states along with residual correction terms. When the recurrence is simplified to use only the current state p(4) while discarding residuals g() S f, the resulting computation reduces to the forward pass of the backbone GNN, thereby preserving its expressiveness. Importantly, GRAMA allows more diverse behaviors by learning data-dependent combinations of historical states and residuals, it expands the space of representable functions. Empirical results demonstrate that this enhanced flexibility consistently leads to improved performance over backbone models. Understanding if, and which extent, our GRAMA improves expressiveness beyond 1-WL., presents promising avenue for future theoretical investigation.
Distinguishing GRAMA from other GNNs. We now further distinguish our GRAMA from other types of existing GNNs. compared with other graph SSMs, the main differences are (i) GRAMA can process sequences which are beyond pairwise interactions, different from the graph SSM in (Huang et al., 2024b); and (ii) GRAMA is cenrmutation-equivriiii other graph SSMs like in (Behrouz & Hashemi, 2024; Wang et al., 2024a), are not permutation -equivvriniiiviiiintt and are based on heuristics that order the graph nodes to obtain a sequence. Compared Ding et al. (2024), which uses an LRU-based mechanism without selective control, GRAMA incorporates selective mechanism, which our results in Tables 9, 11 and 12 show to be impactful. Compared with transformers like GRIT (Ma et al., 2023), we differ in both computational cost and operation. GRIT emphasizes expressive positional encodings and is more resource-intensive than GPS, whereas GRAMA is efficient, perrutation-eqqivariine
while
and designed for long-range propagation. Compared with implicit GNNs such as IGNN (Gu et al., 2020) and GIND (Chen et al., 2022), which model graph representations as fixed points of nonlinear equilibrium equations over static graphs, leveraging global aggregation through learned diffusion or optimization- based formulations, our GRAMA instead views graph modeling by constructing sequenee of graphs. This enables GRAMA to perform explicit, state- and residual-dependee aggregation via learned adaptive ARMA dynamics, which also equivalent to SSMs, as we prove in Appendix B.
B. Proofs
We now provide proof to all Theorems and Lemmas shown in the paper. Without loss of generality, we analyze GRAMA in the case of single channel. However, note that the ARMA coefficients are shared among channels. Therefore, in the case of multiple input channels, the proof is trivially extended by applying the same ARMA system to each channel independently. Moreover, we will state theoretical results considering general sequences indexed with t, which in particular can be thought of as neural sequences of GRAMA, but, for the sake of simplicity, without involving the hyperparameters R and S, and focusing on the dynamics of a single GRAMA block.
B.1. Proof of Theorem 4.1
Proof. We start by recapping the definition of the ARMA and linear SSM models. Then, we show how to derive an SSM representation of an ARMA model, and vice versa, an ARMA model from a linear SSM.
ARMA Models. The ARMA(p. q) model for a univariate time series is given by:
ft = d1/t-1 + 62/1-2 +... + őplt p + 8, + 0,ō,-1 + 0200 + +...+
+ 0g0
(9)
where (Ø: Ko are the autoregressive coefficients, and (0, 11 are the moving average coefficients.
State Space Model (SSM): A linear SSM system mapping univariate input, 5, into univariate output, ft, is defined by the following equations:
x; = Ax + Bd,
(10a)
ft = Cx2 + Do,,
(10b)
19

---

Graph Adaptive Autoregressive Moving Average Models
where x; is the hidden state vector at time step A is the state transition matrix, B is the control-input matrix, C the observation matrix, and D is the direct transition matrix.
Proof of ARMA - SSM. Given an ARMA(p. 9) model, we can rewrite it in an SSM form by defining a state vector x, that includes past autoregressive values and past residuals:
ff fi-1 fi-P+1 8 8e-1
de d1-o+1]
(11)
and define the SSM matrices A, B, C, D. as follows:
Φ1
01
02
0g
0
A
(12)
B =
[0
0 0]
(13)
0 0
D=
(14)
Using these definitions, the obtained state space model representation is equivalent to the operation of the ARMA model of Equation (9).
SSM > ARMA. Let us assume the hidden state dimension to be so that A E RPXp, E Rex1 C E RIxp, D E Rix1,
First, we recursively substitute the state equation into itself to express x; in terms of past states and inputs. Substituting Xt-1 into the Equation (10) yields:
Ax; Bo, A(Ax,2 + Bo;-1) + Bò:
(15)
A²x,- AB + Bo,
Therefore, unfolding steps in the past, up to the initial condition Xo. we get:
X A X0
Σ A A'xo B8, Σ A B8,
(16)
Substituting the expression in Equation (16) to obtain the SSM output from Equation (10b) yields:
A' (CA'A'
C
B8,
Σ A A
DP.
(17)
CAA'o + (CB+D)& + Σ CA'BA.
The above equation describes an ARMA(p.q) model, where p= and g 1. In fact, once defined the initial condition as X, = 1fp-1..... fo]""" the autoregressive coefficients can be found as the elements of the row vector CAP e g While, the moving average coefficients are the real numbers defined as 0g CA*B, for = 1,..., n. Finally, to get exactly the form of Equation (9), suffices to impose that D = CB.
Another proof of the equivalence between ARMA and SSM can be found in (de Jong & Penzer, 2004). We developed our own version since is more congenial to our discussion based on long-term propagation of the information on graphs.
20

---

Graph Adaptive Autoregressive Moving Average Models
B.2. Proof of Lemma 4.2
The linear SSM corresponding to a GRAMA block with autoregressive coefficients {d+] is stable if and only if the spectral radius of its state matrix is less than (or at most equal to) 1. In particular, this happens if and only if the polynomial P(A) XP د== O X has all its roots inside (or at most on) the unit circle.
Proof. We proved in Theorem 4.1 that GRAMA block can be described equivalently linear SSM of the kind of Equation (10). The discrete-time recurrence given by Equation (10) can be completely unfolded, thanks to the lack of nonlinearity. We can write Equation (10) in a closed formulation as
X A X0
+
Σ A 1=0
(18)
necessary and sufficient condition to have a bounded response for the state x, is that the powers of the state matrix A do not explode. This condition translates into a well-known inequality on the spectral radius of the state matrix, namely that the spectral radius of A is less than (or at most equal to) 1. Now, let us consider the state matrix as in Equation (12), i.c. divided in an upper triangular form of 4 blocks:
A 11: A 12: , 22 of dimensions x p. x 9,9 x p. x 4. where A21 is the null matrix of dimension q x p. Due to the triangular form, we have that det A - AI) = det(A,
XI) det(Az2 - AI) = det(A11 (-) The matrix A1 is a companion matrix. Its characteristic polynomial can be computed recursively using Laplace expansion of Therefore, the set of eigenvalues of the state matrix of the linear SSM associated with GRAMA block with autoregressive coefficients { is the set of roots of the polynomial in the indeterminate X, given by
determinants on the first row, to get that det(A, (A AI) (-1) (XP
(-1)pt X Σ )))
The spectral radius of A is the largest (in modulo) among all the complex roots of this polynomial. Thus, a GRAMA block with autoregressive coefficients {o=) stable and only if the polynomial P(A) = XP- -E oz AP- has all its roots inside (or at most on) the unit cirele.
B.3. Proof of Theorem 4.3
If E5 |, < 1, then the GRAMA block with autoregressive cofffficsiseecccffciiiint { corresponds to a stable linear SSM.
Consider the polynomial P()) = XP - 3 The Lagrange upper bound (Hirst & Macey, 1997, Theorem 1) states that all the complex roots of P(A) have modulus less or equal than max(1, Σ/=1 [0 Therefore, if E 16, < 1 then, from Lemma 4.2, conclude that the linear SSM corresponding to GRAMA block with autoregressive coefficients {o. is stable.
Proof:
B.4. Proof of Theorem 4.4
First, we prove the following Lemma B.I.
Lemma B.1 (Long-range interactions in GRAMA), the k-th power of the state matrix of GRAMA block has vanishing entries, then for stable GRAMA it is impossible to learn long-term dependencies of ie time lags in the sequence of residuals 81, .2.....5 8t.
Proof. Assuming we want to learn patterns in the input sequence 61, 82...., 8r of length k. Referring to Equation (18), we need the current hidden state X; to encode information that was present in 6 Now, if A has vanishing entries, i.c., smaller than machine precision, then the same holds for the vector ABB Ergo, it is impossible to implement a linear SSM, or cquivalently an ARMA model, to learn dependencies in the input of length k.
Now, we can prove Theorem 4.4, whose statement we report here below for ease of comprehension.
Let us be given GRAMA block with autoregressive coefficients { Assume the roots of the polynomial
21

---

Graph Adaptive Autoregressive Moving Average Models
P(A) XP - - dy are all inside the unit circle. Then, the closer the roots P()) are to the unit circle, the longer the range propagation of the linear SSM corresponding such GRAMA block.
Proof. Due to Lemma 4.2, the hypothesis of P()) having roots inside the unit circle implies that the linear SSM corre- sponding to GRAMA block with autoregressive coefficients {o is a stable system. Moreover, from the proof of Lemma 1. we know that the long-term propagation of a stable linear SSM corresponding to a GRAMA block is prevented by the pace to which the vector B converges to the zero vector, as increases. The speed of convergence is linked to the speed of convergence of A R to the null matrix, which in turn depends on the modulus of the eigenvalues of A. From Lemma 4.2, the non-zero eigenvalues of A the roots of the polynomial P(A). Therefore, the closer the moduli of the complex roots of the polynomial P()) are to the unit circle, the longer the range propagation of the GRAMA block. 7
C. Implementation Details
We provide additional implementation details of our GRAMA.
C.1. Learning Selective ARMA Coefficients
We now describe the implementation of the Selective ARMA coefficients presented in Section 3.2. Namely, to learn the dynamics between node features in different steps within the sequences (*)) and (*), we utilize a multi-head self-attention mechanism (Vaswani et al., 2017). Recall that the shape of the sequences is L x n x d, where L is the sequence length, is the number of nodes, and d is the number of hidden channels. To maintain computational efficiency, we first mean pool the sequences along the node dimension (per graph), such that the input the attention layers is of shape I. c. We denote this operation by POOL, and it is common operation in graph learning (Xu et al., 2019; Morris et al., 2019). This pooling step allows our GRAMA to offer flexible behavior in terms of ARMA coefficients per graph, property which was recently shown to be effective in graph learning (Eliasof et al., 2024a; Mantri et al., 2024) while remaining efficient in terms of computations. In what follows, we explain how to obtain the ARMA coefficients using an attention mechanism. For simplicity, we describe the process in the case of p - q = L. In any other case, the exact computation done with a truncated version of the sequence, taking the latest p sequence elements from F(*) E R R.xxx (in Python notations, [[ -p, :, :], and the last q sequence elements from A (s) (in Python notations, A (+) -q.;;)) That is, the truncated are fed to the attention layers as described below. In terms of using attention mechanism, the main difference in our implementation compared to a standard attention module as in Vaswani et al. (2017) is that we remove the SoftMax normalization step, as discussed in Section 3.2. We denote a multi-head attention score module by MHA and MHAMA. for the saltiiheaddttteettion for the AR and MA parts, respectively. Note that in our case, we are only interested in the pairwise scores computed within a transformer and that we do not use the SoftMax normalization step. Then, the output of the attention modules reads:
Apc.) = tanh (MHLAR(POOL E ERLXL
(19)
A = tanh [MHAMA((PPLL ())) E R.I
(20)
The (4,, 1-th entries in Apc) and Aao) represent the score between the 1,-th and 1y-th elements in the sequences, respectively. Specifically, the last row of these matrices represents the connection between the current element and the elements L- - in each of the respective sequences. Therefore, we define the unnormalized AR coefficients as the last row in Apt), and similarly in As
(o) for the MA coefficients. Using Python notations, this is described as:
(FR)) Apmol 1 R² EMA (A (5)) = As [1, R.
(21)
(22)
To normalize the coefficients, we follow the following strategy:
CAR(F())) (F(()()))
(23)
(CAR(F(O))
EMA (A (5)
(M (0)) = Σ ECMA( (3))
(24)
22

---

Graph Adaptive Autoregressive Moving Average Models
0.08
0.06
0.55
0.5
0.64
12
14
(a) Initialization
(b) Post-training
Figure 3: Learned coefficients of GRAMA over layers, visualized before (a) and after (b) training.
In Figure 3. present example of the learned coefficients before and after training the Questions dataset, using single GRAMA block with 16 recurrence steps. At initialization, the weights assigned to layerwise features-denoted by e for hidden states and 0 for residuals- are predominantly concentrated on the deeper layers. This initialization resembles standard residual connection, where emphasis placed on recent computations. Following training, the learned coefficients reveal a more intricate distribution. Rather than attending primarily to the most recent layer, the model highlights a diverse of layers, suggesting non-trivial dependencies.
are
C.2. Overall GRAMA architecture
Our GRAMA is illustrated in Figure and it is comprised of three main components: (i) the initial embedding, which described Equation (2). The role of this part is transform static input graph into a sequence of graph inputs. Namely, given features of shape
sequences: sequence of states F()) and sequence of residuals A (0) both of shape L X X d, where d is the embedding size of the input channels. (ii) These sequences then processed by GRAMA block, discussed in Section 3.1. (iii) A final classifier Sout d + Rº that takes the last state in the updated sequence, denoted by (L-S-1) E Raxd and projects it to the desired number of output channels. The classifier is implemented using an MIP, as is standard in graph learning (Xu et al., 2019). Note that, the last state F(L-S-1) contains node features, and therefore, the case of graph level task, we first pool the node features using mean pooling as in (Xu al., 2019), obtain a prediction vector Sout (PoOL (FLLSS()))) RR. In the case of node-level tasks, the node-wise prediction obtained by Jout (f(1-5-1)) (xx)).
it yields
D. Experimental Details
In this section, we provide additional experimental details. Compute. Our experiments are run on NVIDIA A6000 and A100 GPUs, with 48GB and 80GB of memory, respectively.
D.1. Employed baselines
In our experiments, the performance of our method is compared with various state-of-the-art GNN baselines from the literature. Specifically, we consider:
classical MPNN-based methods, i.e., GCN (Kipf & Welling, 2016), GraphSAGE (Hamilton et al., 2017), GAT (Veličković et al., 2018). GatedGCN (Bresson & Laurent, 2018), GIN (Xu et al., 2019), ARMA (Bianchi et al., 2021), GINE (Hu et al., 2020b), GCNII (Chen et al., 2020), and CoGNN (Finkelshtein et al., 2024);
heterophily-specifii models, i.e., H2GCN (Zhu et al., 2020), CPGNN (Zhu al., 2021), FAGCN (Bo al., 2021), GPR-GNN (Chien et al., 2021), FSGNN (Maurya et al., 2022), GloGNN (Li et al., 2022), GBK-GNN (Du et al., 2022). and JacobiConv (Wang & Zhang, 2022);
DE-DGNs, i... DGC (Wang al., 2021), GRAND (Chamberlain al., 2021), GraphCON (Rusch et al., 2022).
A-DGN (Gravina al., 2023), SWAN (Gravina al., 2025), and PH-DGN (Heilig al., 2025);
Graphh Transformers, i.e., Transformer (Vaswani et al., 2017: Dwivedi & Bresson, 2021), 1),, GT (Shi et al., 2021), SAN (Kreuzer et al., 2021a), EGT (Hussain et al., 2021), GPS (Rampášek et al., 2022), GOAT (Kong et al., 2023),
Exphormer (Shirzad et al., 2023), GRIT (Ma al., 2023), and Polynormer (Deng et al., 2024);
23

---

Graph Adaptive Autoregressive Moving Average Models
Higher-Order DGNs, i.e., DIGL (Gasteiger al., 2019), MixHop (Abu-El-Haija et al., 2019), DRew (Gutteridge et al., 2023), and GRED (Ding al., 2024).
SSM-based GNN, i.e., Graph-Mamba (Wang et al., 2024a), GMN (Behrouz & Hashemi, 2024), GSSM (Huang et al., 2024b), and GPS+Mamba (Behrouz & Hashemi, 2024)
D.2. Graph Transfer
Dataset. We consider the graph transfer dataset from Gravina al. (2025), which is based on the work of (Di Giovanni al., 2023). Unlike the original approach in (Di Giovanni et al., 2023), node features are randomly sampled from a uniform distribution in the range [0, 0.5). In each graph, labels of value "I" and "0" are assigned to source node and target node, respectively. Graphs were sampled from three different distributions: line, ring, and crossed-ring (see Figure 4 for visual exemplification). In ring graphs, the nodes form cycle of size n. with the source and target placed |n/2] apart. Similarly, crossed-ring graphs consisting of cycles of size n but introduced additional edges crossing intermediate nodes, while still maintaining a source- target distance of |n/ [n/ Lastly, the line graph contains a path of length n between the source and target nodes. These experiments focus on a regression task aimed at swapping the labels of the source and target nodes while keeping intermediate node labels unchanged. The input dimension is 1, and the distances between source and target nodes set to 3, 5, 10, and 50. We generated 1000 graphs for training, 100 for validation, and 100 for testing.
s
S
(a) Line
(b) Ring
(c) Crossed-Ring
Figure 4: Line, ring, and crossed-ring graphs where the distance between source and target nodes is equal to 5. Nodes marked with "S" are source nodes, while the nodes with "T" are target nodes.
Experimental Setting. We followed the experimental setting of (Gravina et al.. 2025). Therefore, we design each model as combination of three main components. The first is the encoder which maps the node input features into a latent hidden space; the second is the graph convolution (i.e., GRAMA or the other baselines); and the third is a readout that maps the output of the convolution into the output space. The encoder and the readout share the same architecture among all models in the experiments.
We perform hyperparameter tuning via grid search, optimizing the Mean Squared Error (MSE) computed on the node features of the whole graph. We train the models using the Adam optimizer for a maximum 2000 epochs and early stopping with maximal patience of 100 epochs on the validation loss. For each model configuration, we perform 4 training runs with different weight initialization and report the average of the results. We report in Table 4 the grid of hyperparameters exploited for this experiment.
D.3. Graph Property Prediction
Dataset. We adhered the data generation procedure described in (Gravina al., 2023). Graphs were randomly drawn from several distributions, e.g., Rédōs-Rényi, Barabasi-Albert, caveman, tree, and grid. Each graph contains between 25 and 35 nodes, with nodes assigned with random identifiers as input features sampled from uniform distribution in the range [0, 1). The target values represent single-source shortest paths, node eccentricity, and graph diameter. The dataset included a total of 7,040 graphs, with 5,120 for training, 640 for validation, and 1,280 for testing. The tasks in this benchmark require capturing long-term dependencies between nodes, as solving them requires computing the shortest paths within the graph. Moreover, as described in Gravina al. (2023), similar standard algorithmic approaches (c.g.. Bellman-Fort Dijkstra's algorithm), accurate solutions depend on the exchange of multiple messages between nodes, making local information insufficient for this task. Additionally, the graph distributions used in these tasks are sampled from caveman, tree, line, star, caterpillar, and lobster distributions, all of which include bottlenecks by design, which are known to be a cause of oversquashing (Topping et al., 2022).
Experimental Setting. We employ the same datasets, hyperparameter space, and experimental setting presented in Gravina al. (2023). Therefore, we perform hyperparameter tuning via grid search, optimizing the Mean Square Error (MSE),
24

---

Graph Adaptive Autoregressive Moving Average Models
training the models using Adam optimizer for maximum of 1500 epochs, and early stopping with patience of 100 epochs on the validation error. For each model configuration, we perform 4 training runs with different weight initialization and report the average of the results. We report in Table 4 the grid of hyperparameters exploited for this experiment.
D.4. Long Range Graph Benchmark
Dataset. To assess the performance real-world long-range graph benchmarks, we considered the Peptides-fum and Peptides-struct datasets (Dwivedi et al., 2022b). The graphs represent ID amino acid chains, with nodes corresponding to the heavy (non- moon-hydrogen) atoms of the peptides, and edges representing the bonds between them. Peptides-fune is multi-label graph classification dataset containing 10 classes based on peptide functions, such as antibacterial, antiviral, and cell-cell communication. Peptides-stree Seppides-structii is a multi-label graph regression dataset, focused on predicting 3D structural properties of peptides. The regression tasks involve predicting the inertia of molecules based on atomic mass and valence, the maximum atom-pate pair distance, sphericity, and the average distance of all heavy atoms from the plane of best fit. Both datasets, Peptides-func and Peptides-struct, consist of 15,535 graphs, encompassing total of 2.3 million nodes. We used the official splits from Dwivedi et al. (2022b), and reported the average and standard-deviatio performance across 3 seeds.
Experimental Setting. We employ the same datasets and experimental setting presented in Dwivedi et al. (2022b), Therefore, we perform hyperparameter tuning via grid search, optimizing the Average Precision (AP) in the Peptide-fune task and the Mean Absolute Error (MAE) in the Peptide-struct task, training the models using AdamW optimizer for a maximum of 300 epochs. For each model configuration, we perform training runs with different weight initialization and report the average of the results. Also, we follow the guidelines in (Dwivedi et al., 2022b; Gutteridge et al., 2023) and stay within the 500K parameter budget. In Table 4 we report the grid of hyperparameters exploited for this experiment.
D.5. GNN Benchmarks
Dataset. MalNettTing (Freitas et al., 2021) is a graph classification dataset consisting of 5,000 function call graphs derived from software samples in the Android ecosystem. Each graph contains at most 5,000 nodes, which represent functions. Edges correspond to calls between functions. MalNet-Tiny is graph classification dataset, comprising of 5 classification labels, including 1 benign software and 4 types of malware. We used stratified splitting, following a 70%-10%--20 10%-20% split, as in Freitas et al. (2021).
In the heterophilic setting, we consider Roman-empire, Amazon-ratings, Minesweeper, Tolokers, and Questions tasks from (Platonov et al., 2023). Goman-Fmpinn is dataset derived from the Roman Empire article in Wikipedia. Each node represents a word, and edges are formed if words either follow one another or are connected syntactically. The task involves node classification based the syntactic role of the word, with 18 classes. The graph is chain-like, has sparse connectivity, and potentially long-range dependencies. Amazon- Amazon-Ratings is based on the Amazon product s0-purchasing network. Nodes represent products, and edges connect products that are frequently bought together. The task is to predict the average product rating, which is grouped into five classes. Node features are derived from fastText embeddings of product descriptions. Minesweeper is a synthetic dataset consisting of a 100x100 grid where nodes represent cells, and edges connect neighboring cells. 20% of the nodes are randomly selected as mines. The task is to predict which nodes are mines, employing as node features the one-hot-eneoded numbers of neighboring mines. Tolokers is dataset based on the Toloka crowdsourcing platform (Likhobaba et al., 2023), where nodes represent workers (tolokers), and edges are formed if workers collaborate on the same project. The task is to predict whether worker has been banned, using features from their profile and performance statistics. Questions is based on the data from the Yandex Q question-answeriin website. Nodes represent users, and edges connect users who have interacted by answering each other's questions. The task is to predict which users remained active on the platform, with node features derived from user descriptions. We report in Table 3 a summary of the statistics of the employed heterophilic datasets.
Experimental Setting. We employ the same datasets and experimental setting presented in Freitas al. (2021) and (Platonov et al., 2023). Therefore, we perform hyperparameter tuning via grid search, optimizing the Accuracy (Acc) in the MalNet-Tiny, Roman-Emmire and Amazon-ratings tasks, and the ROC Area Under the Curve (AUC) in the Minesweeper, Tolokers, and Questions task. We trained the models using AdamW optimizer for a maximum of 300 epochs. On the heterophilic datasets, we use the official splits provided in Platonov et al. (2023) and report the average and standard deviation of the obtained performance. For MalNet-Tiny, we repeat the experiment on 4 different seeds and report the average performance alongside the standard deviation. We report in Table 4 the grid of hyperparameters considered for this experiment.
25

---

Graph Adaptive Autoregressive Moving Average Models
Table 3: Statistics of the heterophilous datasets.
Roman-empire
Amazon-ratings
Minesweeper
Tolokers
Questions
nodes
22,662
24,492
10,000
11,758
48,921
adges
32,927
93,050
39.402
519,000
153,540
Avg degree
2.91
7.60
7,88
88.28
6.28
Diameter
6,924
Node features
300
300
10
301
Classes
2
Edge homophily
0.05
0.38
0.68
0.59
0.84
D.6. Hyperparameters
In Table 4, we report the grids of hyperparameters employed in our experiments by our method. Besides typical learning hyperparameters such as learning rate and weight decay, our GRAMA introduces several possible hypermeters: the sequence length L, the autoregressive order the moving average g, the number of recurrent steps applied at each GRAMA block, and the number of GRAMA blocks S. We now describe our choices, aiming to maintain a reasonable number of hyperparameters and to obtain large prediction window, which was shown to be useful SSMs (Gu al., 2021c). Because this paper focuses on using a sequential model on static graph inputs, the sequence length is to be determined, and we consider different lengths depending on the task. The ARMA orders p and q can assume any values long they are not larger than L, and the most general case is when q L, and this was our choice, it covers other choices where L. For the number of recurrence steps R. we aim to obtain relatively large prediction window with respect to the input sequence length, and therefore we choose to set R = L in all experiments.
are smaller than
Table 4: The grid of hyperparameters employed during model selection for the graph transfer tasks (Transfer), graph property prediction tasks (GraphProp), Long Range Graph Benchmark (LRGB), and GNN benchmarks (G-Bench), i.e., MalNet- and heterophilic datasets.
Values
Hyperparameters
Transfer
GraphProp
LRGB
G-Bench
Optimizer
Adam
Adam
AdamW
AdamW
Learning rale
0.001
0,003
0.001. 0.0005, 0.0001
0,001, 0,0005 ,0.0001 0, 0.0001
Weight decay
10
0. 0.0001
Dropout
0 RcLU
0, 0.3, 0.5
0, 0.3, 0.5
Activation function (o)
ReLU
ELU, GELU, ReLU
ELU, GELU, ReLU
Embedding dim
20, 30
Soquence Length (L)
3. 5. 10, 50 1.2
1.5, 10, 20
2,4, 8, 16
2, 2,4, 8, 16 2,
Blocks (S)
1.2
1,2.4
Graph Backhone
GCN, GPS. GatedGCN
E. Additional Results And Comparisons
E.1. Additional GNN Benchmarks
Setup. To further evaluate the performance of our GRAMA, consider multiple GNN benchmarks, including MalNet-Tiny (Freitas et al., 2021), the five heterophilic tasks introduced in (Platonov et al., 2023), OGBG-MOLHIV (Hu et al., 2020a), Cora, CiteSeer. PubMed (Yang et al., 2016), ZINC-12K, 12k, MNIST, CIFARIO, PATTERN, and CLUSTER (Dwivedi et al., 2023). Specifically, MalNet -any consists of relatively large graphs (with thousands of nodes) representing function call graphs from malicious and benign software, where nodes represent functions and edges represent calls between them. Considering the scale the graphs and the fact that malware can often exhibit non-local behavior, we believe this task can further reinforce the idea that GRAMA can preserve and leverage long-range interactions between nodes.
In the heterophilic node classification setting, consider Roman-empire Amazon-ratings, Minesweeper, Tolokers, and Questions tasks, to show the efficacy of our method in capturing more complex node relationships beyond simple homophily settings.
ZINC-12K and OGBG-MOLHIV are datasets where graphs represent molecules (i.e., nodes are atoms, and edges are chemical bonds) and the objective is to predict molecular properties; while Cora, CiteSeer, and PubMed are citation networks where each node represents a paper and each edge indicates that one paper cites another one, whose objective is to predict the
26

---

Graph Adaptive Autoregressive Moving Average Models
class associated each node. MNIST and CIFARIO superpixel-basee beasiieee--bdddd-e image datasets where each image is represented as graph, and the task is to predict the digit object class of the represented in the image; while PATTERN and CLUSTER are datasets containing stochastic block model graphs and the goal is to identify is node belong to pattern and assign community labels to nodes, respectively.
We consider the experimental setting from (Freitas et al., 2021) for MaiNet-Tiny, and that from (Platonov et al., 2023) for heterophilic tasks. On the ZINC-12K, MNIST, CIFARIO, I0, PATTERN, and CLUSTER, we followed the official splits and experimental protocols from (Dwivedi et al., 2023). For OGBG-MOLHII we followed the official protocol from (Hu et al., 2020a). On Cora, CiteSeer, and PubMed, we used the splits and experimental protocols from (Pei et al., 2020). Additional details the setup and tasks are in Appendix D.5.
Results. Table 5 reports the mean test set accuracy on MalNet-Tiny, Table 6 reports the test score for the heterophilic tasks, and Table 7 the test score of the other benchmarks.
Table 5: Mean test accuracy and std averaged over 4 random weight initializations on MalNet-Tiny The higher, the better. First, second, and third best results. Baselines from (Wang et al., 2024a; Behrouz & Hashemi, 2024) include Laplacian positional encodings.
MalNet-Tiny Ace 1
Model
MPNNS
GCN
81.00
88.98 0 65
GatedGCN
92.23 133+-o.0
ARMA
91.80
Graph Transformers
GPS+ Transfommer
0OM
GPS+ Performer
92.64
GPS+BigBird
92.34 34
Exphormer
94.22
Graph SSMs
Graph-Mambb
93.40
GMN
94.15
Ours
GRAMAGCN
93.43 1:0 29
GRAM AGAMBONN
93.66
GRAMAGPS
94.37++0.36
For the heterophilic tasks we included baseline results from (Finkelshtein et al., 2024; Behrouz & Hashemi, 2024; Platonov et al., 2023; Müller et al., 2024; Luan et al., 2024; Deng et al., 2024). Among all models and tasks, GRAMA achieves competitive overall performance that often outperforms state-of-the-arr methods, demonstrating that our model not only excels at handling larger graphs than those considered in previous experiments but also under complex heterophilic scenarios. The results underscore the ability of GRAMA to capture the dependencies characterizing malware detection tasks where non-local behaviors are often prevalent. Overall, these findings confirm that GRAMA a competitive and effective solution, when compared to offe--of-the-ar models like Graph Transformers and recent Graph SSM models.
E.2. Extended LRGB Comparisons
In Table 8, we report the complete results for the LRGB tasks, including more multi-hop DGNs and ablating on the scores obtained with the original setting from (Dwivedi et al., 2022b) and the one proposed in (Tönshoff et al., 2023), which leverage added residual connections and 3-layers MIP as a decoder to map the GNN output into the final prediction. In the table, we color the top three methods. Different from the main body of the paper, here, we color the best methods, including sub-variants of methods, for an additional perspective on the results.
E.3. Complexity and Runtimes
We provide runtimes for GRAMA alongside other methods, such as Graph GPS and GCN, in Tables 9 and 10. In all cases, we use a model with 256 hidden dimensions and a varying depth (changing the sequence length L from 2 to 16 in our GRAMA with S 2 GRAMA blocks, recall that GRAMA depth is SL, and the number of layers is the backbone for other methods) and report the training and inference times, as well as the performance on the Roman Coman-Empire dataset, for
27

---

Graph Adaptive Autoregressive Moving Average Models
Table 6: Mean test set score and std averaged over 4 random weight initializations on heterophilic datasets. The higher, the better. First, second, and third best results for each task are color-coded. Baseline results are reported from (Finkelshtein al., 2024; Behrouz Hashemi, 2024; Platonov et al., 2023; Müller et al., 2024; Luan et al., 2024; Deng et al., 2024).
Roman-empire
Amazon-ratings Acc
Minesweeper AUC
Tolokers AUC
Questions AUC
Model
Acc f
(Lean et al,, 2024)
MLP-2
66.04
49.55
20.92221.2
20.78
19.97
SGC-1
44,60
40 40.69 42
82.04
73.80
71.06.0.92
MIP-1
64.12
38.60
50.59 20.59
71.89
70.33
Graph-agnostic
20.8
05.90
1..3
72.95
70.34
ResNe++SGC
73.90-0.51
50.66+-.44
70.88 70.88+0.90
80.70+0.97
75.81+0.90
ResNettadj
52,25 20.40
01.83
50.42:00.3
18.
75.77=1122
MPNNS
ARMA
17.1120.30
0 0.30
91.6
82.29
07.
GAT
-0.87-0.30
49. 49.09
92.01
83.70.0.47
17.43+1.20
GAT-sep
88.75 0..41
0..70
93.91
83.78+0.48
70.79
GAT (LapPE)
84.80
44.90
93.50.0.51
84,99 54
76.55
GAT (RWSE)
86.62 2..5a
92.53
85.02210.67
77.83
GAT (DEG)
80.51
51.65+0.co
93.04=0.62
84.22200.81
77.10=1.229
Gated-GCN
74.46
43.00+0.322
87,54+
77.31+1.14
76.61+1..15
73.69
48.70
09.75
83.64
1.277
GCN (LapPE)
83.37-0.56
44.35+0.39
94.26
84.9540.78
17.79+1.34
GCN (RWSE)
84.84
46.4020.b5
93.84
85.11
77.81
GCN (DBG)
84.21
50.01
94.14.0.50
82.51
76.96.1.21
CO GNN(E, Σ)
91.57 =0.32
51.28
11.15
83.36.0.89
80.02
CO-GNNNPp. μ))
90.37
54.17+0.37
97.31+0.41
84.45+1.17
76.54+0.96
SAGE
85.74
03.63-20.39
93.51
82.43.0.44
76.44:20.22
Graph Transformers
Exphormer
89.03 0..37
53.51
90.74
83.77.0.78
73.94
NAGphomer
74.34_0.77
51.26+0.72
84.19
78.32+0.95
68.1744..8
GOAT
71.59 -122
40.60
81.09 1.002
83.11
1..76=1.60
GPS
22.00_o..61
03.10.0..12
90.63 20.67
80.71
71.73
(LapPE)
83.96_00
48. 20,20,.
93,85
84.72.0.17
77.85
GPSocNiPatoens (RWSE)
84.72=0.05
48.08
92.88
84.81
76.45=11511
GPScCN (DEG)
83.38
48.93+
93.60+0.47
80,4940.97
74.24+1.11
GPSGAT+Poriens (LapPE)
85,93
86
00.62
84.6240.54
20.01
Pudiene (RWSE)
87.04-0.58
49.9 49.92+0.es
91.08 0..5
84,38 40.99
17.14+1.49
GPS GPSnaT-Parieme (DEG)
85.54_0.08
51.03
91.52:20.4
82.45
76.51 11.19
(LapPE)
91.82.0.41
GPS
(RWSE)
ODM
0OM
91.17
13.53
OOM
GPSGCN
GPSoCNITranfeens
(Tuasfonns
(DEG)
OOM
OOM
91.76+0.61
80.82+0.95
OOM
GPS Tnasooimme (LapPE)
OOM
0OM
92.29
04.70:0..5
OOM
GPS (Tunsfonnes
(RWSE)
00M
00M
90.82
84.01 +0.96
OOM
GPS Grnneee
(DEG)
O0M
0OM
91,58+0.58
81.89
OOM
GT
20.71
51.1710.65
91.85
83.23
77.95
GT-sep
87.32_0.39
52.18
92.29 10.47
82.52 a2
20.95
Polynormer
92.55
54.81 54.81
97,46
85.91
70.92
Heterophity-Deesigaade GNNs
CPGNN
63.96=0.62
09.7
73.36 52.03
65.96
FAGCN
65.22-0.58
44.12+0.30
88.17+0.79
77.75+1.06
77.24+1.20
ESGNN
79.92 79.92_0.50
52.74
90.0810.70
82.76
78.86
74.57
45.98
90.85+0.58
80.01
74.47 00.80
GioGNN
59.63
06.894...14
51.08
73.39:4..17
65.74=1..19
GPR-GNN
64.85 20.27
00.88
86.24
72.94.0.97
55.48 20.91
H12GCN
60.11
36.47
89.71
73.35
63.59111.44
JacobiCrov
71.14
43.55
89.66
68.6644.665
73.88
Graph SSMs
GMN
87.69
0.331
91.01
84.52++0211
GPS Mamba
83.10
45.13
89.93
83.70
Ours
GRA GRAMAGCN
88.61_0.44
53.48
95.27 20.71
86.23
11:13
GR AMAAAAGGGNN
00.82_0.39
53.71
10.19
85.42
80.47=11.00
GR GRAMAGrS
91.73
53.36+
98.33
85.71+0.98
19.11+1.10
reference. As can be seen from the results in the Table, our GRAMA is positioned as a middle ground solution in terms of computational efficiency, between linear complexity MPNNs like GCN and quadratic complexity methods like GPS. Notably, our GRAMA achieves better performance than GCN and GPS, and maintains its performance as depth increases, different than GCN. Still, in some cases, lower computational cost might a strong requirement, for example, on edge
28

---

Graph Adaptive Autoregressive Moving Average Models
Table 7: Mean test set score and std on popular GNN Benchmarks. First, second, and third best results for each task are color-coded.
OGBG- MOLHIV
ZINC-12k
Cora
CiteSeer
Pub
MNIST
CIFARIO
PATTERN
CLUSTER
Model
MAE
AUC f
Acc 1
Acc f
Acc 1
Acc 1
Acc
Acc f
Acc f
GCN
0.278 0.003
76.06=0..97
85.77
73.68+1.38
88. 13400.60
90.71
55.71 40.71 40.35
71.89
68.50-00.98
GatedGCN
0.254 .005
76.72-20.a
86.21
1.22
88.09 44
97.34220.14
67.31
85.57 20.07
73.84-20.53
GPS
0.125
77.39 21.11
85.42
73.99
88.23 88.23100.1
98.0510.13
72.3010.36
86.69100066
78.02_0.18
GPS RWSE
0.070 .044
21.00
86.67 =1.50 1.50
74.52
88.94 49
FGT
0. 108
98.17
68. 68.70+0.41
86,82+0..02
0..23
GRIT
0.059:00.0m 4.0002
98.11 +.011
76.47-00.88 40.98
87.20+00.0 +0.08
80.03-0.22
Ours
GRAMAGCE AOCN
0.142++0.0 0.000
77.47-+1.05
-1.01
+..09+1..5
90.20
97.87.+0.19
70,28++0.42
82.66-+0.18
74.29-00.60
GR PRRMAcc MMAAMGGG
0. 0.140
77.60=0.9s
77.60
88.13
77.63
90.07
98.12.t0.10
70.61
86, 86.72-10110
06.88
GR AR Aars
0.000
78.19 +1.10
87.95-1.72
1.72
77.13+1.51
39.76+0.64
98.29
75.92+0.41
87.41 +0.07
79.66-00119
GRAMAns+
0,061 003
79.21
88,37 -1.64
27.68
90.31g0.88
devices. To this end, we can use the naive learning approach of ARMA coefficients, as discussed in Section 3.2, which still utilizes our GRAMA but avoids the use of an attention mechanism for a selective ARMA coefficient learning. In this case, as we show in Table 9, it is still possible to obtain significant improvement compared with the baseline performance with lower computational time, although with less flexibility that is offered by our selective ARMA coefficient learning. In addition, for a broader comparison, we consider the best rest-performing variant of GPS (GPScxT-Periomerr (RWSE),, showing that also in this case, our GRAMA offers better performance. Furthermore, the results in Table 9 offer comparisons of GRAMA, GCN, and GPS under equivalent runtime budgets, showing that GRAMA matches exceeds the accuracy of GPS while being more efficient. Additionally, the non-selective GRAMA variant maintains high performance with further reductions in computational cost, showcasing its applicability of GRAMA constrained computational scenarios. Finally, in Table 11 we compare our GRAMA with recent taae-offthhearr methods in terms of both time and downstream performance. Our GRAMA requires similar time to other methods like GPS+Mamba and GMN, which are also selective models, while requiring significantly less time than GPS. All runtimes are measured on an NVIDIA A6000 GPU with 48GB of memory.
E.4. Ablation Studies
To provide a comprehensive understanding of the different components and hyperparameters of our GRAMA, we now present several ablations studies.
Selective vs. Naive ARMA Coefficients. In Section 3.2, we describe novel, selective way to predict the ARMA coefficients that govern GRAMA model, as described in Section 3. We now empirically check whether the added flexibility and adaptivity help in practice. To do that, we present the results with 'naively" learned ARMA coefficients, a variant denoted by GRAMA (Naive), and also report the results with our GRAMA model (these are the same results presented in the rest of our experiments). The results are presented in Table 12. The results show that (i) our GRAMA as an architecture, regardless of the use of selective ARMA coefficients or not, significantly improves the baseline (GCN), and (ii) learning selective ARMA coefficients offers further performance gains compared with naive coefficients.
Performance vs. Model Depth. We evaluate the performance of our GRAMA varying depths. The depth is influenced by the number of recurrences R and S GRAMA blocks. As discussed in Section 3, to reduce the number of hyperparameters and obtain a large prediction window with respect to the input sequence, we choose R = L. That is, the number of recurrent steps is L. Thus, the effective depth of the model is the multiplication S L. Therefore, we test the performance of GRAMA with varying depths, up to a depth of 128 layers, and maintain a constant width of 256. The results reported in Table 13 demonstrate the ability of GRAMA to maintain and improve its performance with more layers.
Hyperparameter Influence. In Table 13 we showed the performance of GRAMA under varying depths. However, note that this study also shows the influence of the number of recurrences R (which is also the length of the sequence L) and the number of GR AMA blocks S. The results show that both are beneficial as increased in terms of added performance, and that enlarging to a value larger than 4 maintains consistent results.
Furthermore, in Table 14, we show the performance of GRAMA with a varying with (i.e., number of hidden channels), when choosing the other hyperparameters to be fixed, and in particular S L = 4. From this experiment, we can see that while some configurations offer better performance than others, overall, our GRAMA consistently improves the baseline
29

---

Graph Adaptive Autoregressive Moving Average Models
Table 8: Results for Peptides-func and Peptides-struct averaged over 3 training seeds. Baseline results are taken from (Dwivedi et al., 2022b) and (Gutteridge et al., 2023). Re-evaluated methods employ the 3-layer MLP readout proposed in (Tönshoff et al., 2023). Note that all MPNN-based methods include structural and positional encoding. The first, second, and third best scores are colored. Baseline results are reported from (Gutteridge al., 2023; Tönshoff et al., 2023; Ma al., 2023; Ding al., 2024; Huang et al., 2024b; Wang al., 2024a; Behrouz & Hashemi, 2024; Gravina al., 2025; Heilig al., 2025).
means 3-layer MLP readout and residual connections are employed.
Peptides-tunc 1
Peptides-struct MAE
Model
MPNNs
GCN
59.30.0.23
0.3496.1: 0013
GINE
54.98 20
0.354711 0045
GCNII
15.4
0.3471 0010
GatedGCN
58.64 20.67
0.342010
ARMA
64.08 0.002
0.2709 0016
Mulli-hop GNNs
DIGL-MPNN
64.69 10
0.3173 0007
DIGL-MPNN-LLpPE
68.30+0.20
0.2616+0.0015
Mixllop
65.92-20.36
0.2921 000002
MixHHo-GGNNNaappe
68.4320.19
0.261411.
DRew-GCN
69.96=00.76
0.2781 0020
DRew-OCN+LapPE
71.50
0.253610 0015
DRew GIN
69.40.0.74
0.2799 10 0016
DRew-GNN+L.appP apPE
71.26=00.6
0.260640.00
DRew-GatedGGC
67.33-+0.94
0.2699+..00
DRew GatedGCN+Lappe
69.77.20.26
0.25391 0007
GRED
70.85 27
0.250310 0018
Transformers
Transfomer-LapPP
63.26 63.26-1.20
0.2529+o.omd
SAN+LapPE
63.84
0.2683 0040
GraphGPS+LLapPt
65.35 20.41
0.2500
GRIT
69.88 0.882
0.2460 0012
Modified and Re-evalunted
GCN
08.00=0.550
0.2460+a.000 p007
GINE
66,21
0.2473 0017
GaledGCN
67.65
0.2477 0006
DRew GCN+LapPE
20.45
0.2517 0011
GraphGPS+LaapP
65, 65.3440.91
0.2509
PILDGN
70.12:20.45
0.246510.0020
DE-GNNs
GRAND
57.89 10.62
0.3418 0016
GraphCON
60.22
0.2778+0.D001
A-DGN
59.75 20.44
0.287440.0002 00221
SWAN
67.51
0.2485
Graph SSMs
Graph-Mamba
20.39
0.2478 2011 0016
GMN
20.7
0.2473 0025
GSSC
70.81
0.2459
Ours
GRAMAGCN
70.93
0.2439 :.0 0017
GRAM GRAMApanocn
70.49 10.51
0.2459 0020
GRAMAGES
69.83
0.2436 0022
00222
methods compared with other baselines reported in Table 6.
E.5. Additional Comparison with MixHop
In this section, we report a deeper comparison with MixHop (Abu-El-Haija et al., 2019). While MixHop assigns learnable weights per layer and uses a dense layer with space complexity Ldd, GRAMA is more efficient. In the non-selective (naive) variant, GRAMA learns only 2L parameters per block, which is highly scalable since L < d and L < In the selective variant, parameter count depends only on d, with space complexity df; the L dependence appears only in the L22 complexity of the sequence input, as discussed in Section 3.3.
As shown in Tables and and Table 15, GRAMA outperforms MixHop. Moreover, our results in the ablation study in Table 12 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 's overall design: unlike MixHop's 's dense, non-recurrent projection,
30

---

Graph Adaptive Autoregressive Moving Average Models
Table 9: Training and Inference Runtime (milliseconds) and obtained node classification accuracy (%) on the Roman- Roman-Empire dataset. Note that in GRAMAGcN (Naive), the ARMA coefficients are learned, but not input anputaad as in GRAMAGCN.
Depth
Metrics
Method
8
Training (ms)
18.38
33.09
61.86
120.93
Inference (ms)
GCN
9.30
14.64
27.95
53.55
Accuracy (9))
73.60
61.52
56.86
52,42
Training (ms)
1139.05
2286.96
4545.46
OOM
Inference (ms)
GPS
119.10
208.26
427.89
OOM
Accuracy (%)
81.97
81.53
81.88
OOM
Training (ms)
1179.08
2304.77
4590.26
OOM
Inference (ms)
GPS PPAn (RWSE)
120.11
209.98
429.03
OOM
Accuracy (%)
84.89
87.01
86.94
OOM
Training (ms)
41.16
98.83
249.68
747. 26
Inference (ms)
GRAMAGcX (Naive)
13.03
26.83
63.61
164.87
Accuracy (%)
83.23
84.72
85.13
85.04
Training (ms)
75.75
141.79
463.76
1378.91
Inference (ms)
GRAMAGCN
40.33
70.91
240.78
702.17
Accuracy (%)
86.33
88.14
88.24
88.22
Table 10: Training Runtime (milliseconds) on the Roman-Empire dataset of GRAMA and its backbone GNNs. Note that in GRAMAGeN (Naive), the ARMA coefficients are learned, but not input-adaptive as in GRAMAGCN.
Depth
Method
8
GCN
18.38
33.09
61.86
120.93
GatedGCN
27.57
47.98
85.36
171.27
GPS
1139.05
2286.96
4545.46
OOM
GRAMAGeN (Naive)
41.16
98.83
249.68
747.26
GRAMAGCN
75.75
141.79
463.76
1378.91
GRAMA AGATERCCN
51.49
117.01
270.64
792.32
GRAMAGPS
1162.13
2346.94
4642.19
OOM
GRAMA recurrent, non-dense aggregation inspired by dynamical systems and modern RNNs.
E.6. Additional Spaato-Tempora Benchmarks
Given the inspiration of GRAMA from sequential models, by transforming graph into sequences of the graph, is interesting understand if it can be utilized for spatio-temporal datasets. In this section we preliminary results with datasets employ Chickenpox Hungary, PedalMe London, and Wikipedia Math,
from Rozemberezki et al. (2021). Specifically, where the goal is to predict future values given past values. In Table 16, we compare the MSE score of our method with two state-of-the-art approaches in the spatio-temporal domain, i.e., A3T-GCN (Bai et al., 2021) and T-GCN (Zhao et al., 2020). Our results show that our GRAMA is a promising approach for processing spatio-temporal data as well. important to note that addressing spatio-temporal datasets not the main goal of this paper. Rather, our GRAMA addresses fundamental issues in existing methods that utilize graph SSMs and the oversquashing issue in static graphs, and studying and extending GRAMA to spatio-temoporal datasets is interesting future work direction.
F. Summary of the results
In this section, we provide a summary of the results achieved by GRAMA. Specifically, we report Table 17 the performance of our GRAMA with respect to the bascline backbone GNNs (i.e., GCN, GatedGCN, and GPS)) and Table 18 the comparison with the best baseline out of all methods tables. As evidenced from both Table 17 and Table 18, our GRAMA
31

---

Graph Adaptive Autoregressive Moving Average Models
Table 11: Training runtime per epoch (milliseconds) and obtained node classification accuracy (%) on the Roman- dataset. Note that in GRAMAGcN (Naive), the ARMA coefficients are learned, but not input- as GRAMAGCN.
Training runtime per epoch (ms)
Accuracy (%)
Model
GatedGCN
18.38
73.69
GPS
1139.05
82.00
GPS Mamba
320.39
83.10.0.25
GMN
387.04
87.69
GRA.AGGN (Naive)
249.68
85.13
GRAMAGCN
362.41
88.61
Table 12: The significance of learning selective ARMA coefficients. Our GRAMA architectures improve baseline
performance, and its selective mechanism further improves performance. Note that GRAMAGCN (Naive), the ARMA coefficients are learned, but not input-adaptive as GRAMAGON.
Roman-empire Acc
Peptides-func AP1
Model
GCN
73.6910.74
59.30
GRAMAGEN (Naive)
85. 43.08
68.9840.52
GRAMAGCN
1.043
70.993
offers significant and consistent improvements over the baseline backbone GNNs well as better performance than current state-of-the-ar performing methods. Therefore, we believe that our proposed method provides a substantial improvement not only in terms of designing a principled and mathematically sound model, which is equivalent to Graph SSM model that preserves permutation-cqquivrraanet equivariance and allows long-range propagation, but also in terms of downstream performance on real-worke applications and benchmarks.
32

---

Graph Adaptive Autoregressive Moving Average Models
Table 13: The obtained node classification accuracy (%) with GRAMAGeN on the Roman -amp-e with a varying sequence length size L and blocks S. Our GRAMA improves with more layers, and maintains its performance with deep models.
Sequence Length L / Blocks
8
2
86.33
88.14
88.24
88.22
87.30
88.06
88.61
88.57
8
88.41
88.15
88.54
88.46
Table 14: Node classification accuracy (%) on Roman- Empure with varying width of GRAMA.
Model
Width
64
128
256
GRAMAGCN
87.79
88.45
88.61
GRAMA GRAMAGxI AGATIDGUN
91.79
91.66
91.68
GRAMAGPS
91.28
91.70
91.19
Table 15: Mean test score and std popular benchmarks comparing MixHop and GRAMA.
Peptides-func
Peptides-struct MAE
Noman-Empire
Amazon-Ratings Acc 1
OGBN-Arxiv
Model
AP
Ace
Acc
MCN
68.4340.49
0.261440.0022
79.16
47.95
71.2940.29
GRAMAGON
70.93
0.243920.0017
$8.61
53.48
73.86
Table 16: Mean test set MSE and std on spatio-temporal datasets. The best result for each task is color-coded.
Model
Chickenpox Hungary
PedalMe London
Wikipedia Math
Baselines
A3T-GCN
1. 1.11440.008
1.469 1.47940.012
=0.01 0.764_0.011
T-GCN
1.11720.011
Our
GRAMAGON
0.790
1.08910.049
0.608=0.019
Table 17: Summary of the performance of our GRAMA with respect to backbone GNNs. The best result for each task color-coded.
Ours
GCN
GatedGCN
GPS
GRAMAGCN
GRAMAGaruGeN
GRAMAGES
(egua(M88)
0.7424_o.oo 0404
0.1348 o 0397
0.5111 + 0426
0,2577 20.006
.0.5485 1:0 1499
0.8663-10.0114
SSSP (s
0,9499 + 18 10
-3.261
-3.599+0.194D
0.0095
-4.1289 00.9940.0000
-3.934940.000
Eec. (R
0,8468 20.0020
0.6995 10
0.6077
0.619320..0s
0.5523
-1.3012
Pept-ffue
59.30
58.6410.77
65.35
70.93
70.49
69.83_0.83
Pept. struel (MAa) ia
0.3496
0.3420 0013
0,2500 1.50000..o0 00.0000
20.3990.0017
0,2459 21.5990.0000
0.2436 22436_000222
MalNet-Tinn (se
81.00
92.23:20.65
92.64-20778
93.43
93.6610.40
94.37
Roman-cmping
73.69
74,46
82.00
88.61
91.82++0.00
91.73-p.60
Amazon-ratings Otee 1)
48.70.2o.53
43.00..0.22
53.10
53.48-20.62
53.71.20.57
53.36_0.38
Minesweeper
89,75
87.54.11.92
90.63
95.27
98.19.10
98.33_
Tolokers (AlC to
83.6440.67
77.31411.14
83.71
86.23
85. 85.4240..00
85.71 =0.08
Questions (NCCT)
1..09
76.61.1.11
71.73
79.23
80.47.1..00
79.11 1118
ZINC-122 12k SMAE MOLHIV
0.278=0.000s
0.254
0..25
0.142=00.10
0.140
0.100 8:0 008
76.06.10
76.72
77.39 11
77.47
77.60
78.19 1.
Cora cAce
85.77 1.
86.21 2.211.1..0
85,42-11.80
88.02 11.02
18.1331...00
87.9 87.95_1.72 1.772
CiteSeer
73.68.41.38
74.10+1..22
73.99 +1.57
77.09
77.63
33.13-1
PubMod (Ace
88.13 88.13
88.09
88.23 22.61
90.20 20.47
90.07 20.07:20.55
89.76
MNIST (Aor
90.71 20.22
97.34-10.14
98.05
97.87 10
98. 12.12.0.10 10
0-.14
CIFARIO (Noe
55.71 $5.71
67.3110.31
72.30
70.28 20.48
74.61 10.44
75.92
PATTERN chee 1
71.8940.53 20.33
85.57 2.0.09
86.69 20.06
82.66-20.18
86.72.0.110
87.41 37.41_0.07 -0.07
CLUSTER
68.50g0..9
73.84
78.02 18
74.29 20.00
76.88_0.39
79.66 00.18
33

---

Graph Adaptive Autoregressive Moving Average Models
Table 18: Summary of the performance of our GRAMA (best performing model out variants) with respect the best baseline of all methods in Tables. The best results for each task is color-coded. The "Improvement" column reports the difference in performance between GRAMA and the best baseline
Task / Model
Best baseline
GRAMA
Improvement
Diameter (logi(MMSE))
-0.5981 10.1145
-0.8663
10.0514
-0.2682
SSSP (o9jn(M88))))
-3.5990 19.449
-4.1289 10.0968
-0.5299
Ecc. (egu(MSE) 1)
40.2199
-1.3012::0.226
-1.2273
Pept.-fune (AP
71.50
70.93
-0.57
Pept.-struct (MAR.)
2.2059
0.2436::0.0022
0.0023
MalNet-Tiny (Ace
94.22 0.224
94.37 +0.36
0.15
Roman-empire
92.55
91.82.10.99
-0.73
(Ace
54.81 -0.49
53.71 +0.07
-1.08
Minesweeper (AUC
97.46 -0.36
98.33 98.33 40.55
0.87
Tolokers (AUC1)
85,91 -u.74
86.23 86.23 11.10
0.32
Questions (AUC
80.02
80.47 80.47:1.00 1.009
0.45
ZINC-122 12k (MAE J)
0.059 00.022
0.061
0.002
OGBG-MOLIN (AUC1)
78.80_1.01
79.21 +0.94
0.41
Cora (Ace
86.67 11533
88.37 11.64
1.7
CiteSeer (Aoc 1)
74.52 1.449
77.68 1:55
3.16
PubMed (Ace f)
88.94=o.4
90.31 1..58
1.37
MNIST (Ace 1)
98. 98.17 20.17
98.29 10.14
0.12
CIFARIO ?)
76.47 =0.88
75.92
0.55
PATTERN (Arc f)
87. 87.20_o.0s
87.4 +0.07
0.21
CLUSTER (Ace 1)
80.03 0.22
79.66
0.37
Chickenpox Hungary (MSE ()
1.114
0.790 20.001
-0.324
PedalMe London (MSE 1)
1.469
1.089
1.08940.044 40.049
-0.380
Wikipedia Math ()SB))
0.764_u.D11
0.608
-0.156
34


Reviews:
[{"review_id": "q5D9jLmXwZ", "reviewer": "Reviewer_mg6D", "summary": "This paper introduces GRAMA, which utilizes ARMA (autoregressive moving average) to design graph state space models. The paper claims this way of design can preserve permutation equivariance and enable long-range message passing with good empirical accuracy across multiple datasets.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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”**.\n\n---\n\n**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.\n\n**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.\n| Model | ZINC (our results exist in paper) | MNIST | CIFAR10 | PATTERN | CLUSTER |\n|---|:---:|:---:|:---:|:---:|:---:|\n| GCN | 0.367±0.011 | 90.705±0.218 | 55.710±0.381  | 71.892±0.334  | 68.498±0.976 |\n| GatedGCN | 0.282±0.015 | 97.340±0.143  | 67.312±0.311  | 85.568±0.088  | 73.840±0.326 |\n| GPS | 0.070±0.004 | 98.051±0.126 | 72.298±0.356  | 86.685±0.059  | 78.016±0.180 |\n| EGT | 0.108±0.009 | 98.173±0.087 | 68.702±0.409  | 86.821±0.020  | 79.232±0.348 |\n| GRIT | 0.059±0.002 | 98.108±0.111  | 76.468±0.881 | 87.196±0.076 | 80.026±0.277 |\n| GRAMA$_{GCN}$ (Ours) | 0.142±0.010 | 97.871±0.188 | 70.283±0.417 | 82.660±0.183 | 74.294±0.595 |\n| GRAMA$_{GatedGCN}$ (Ours) | 0.140±0.008 | 98.119±0.104 | 74.612±0.450 | 86.715±0.099 | 76.883±0.317 |\n| GRAMA$_{GPS}$ (Ours) | 0.061±0.003 | 98.292±0.135 | 75.917±0.408 | 87.406±0.067 | 79.659±0.194 |\n\n**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.\n\n**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: \n| Model           | Peptide Func ($\\uparrow$) | Peptide Struct ($\\downarrow$) |\n|----------------|:---------------------:|:----------------------:|\n| GRIT [1]          | 0.6988 ± 0.0082       | 0.2460 ± 0.0012        |\n| GRED  [2]         | 0.7085 ± 0.0027       | 0.2503 ± 0.0019        |\n| GRED + LapPE [2]   | 0.7133 ± 0.0011 | 0.2455 ± 0.0013        |\n| GSSC [3]          | 0.7081 ± 0.0062       | 0.2459 ± 0.0020        |\n| GRAMA (Ours, best variant)          | 0.7093 ± 0.0078       | 0.2436 ± 0.0022  |\n\n\n**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.", "claims_and_evidence": "- The paper needs to better discuss and compare with existing graph mamba works. For example, some claims may not be convincing:\n    - \"limit their focus to pairwise interactions rather than sequences\" (L16) & \"however, this design choice may not fully exploit the sequence-handling capacity of SSMs\" (L104)\n    - Why is it so important to model the input as sequences in graph learning, where things are just not natural sequences?\n\n- There are multiple standard benchmarks for evaluating the capability of capturing long-range dependencies of graph transformers, including datasets such as mnist, cifar10, pattern, cluster, malnet-tiny, PascalVOC-SP,  Peptides-Func, Peptides-Struct, zinc, zinc-full, etc. Even though the paper seems to include many benchmarks, many of them are not that widely used for evaluating graph transformer-like models. It would be better if the authors could include more widely used datasets in this domain.\n\n- The presentation could be improved to better show why ARAMA is a better graph SSM compared with existing methods. What makes ARMA so special? And more baselines should be included to justify the superiority of ARAMA, e.g., [1, 2, 3]\n\n[1] Ma, Liheng, et al. \"Graph inductive biases in transformers without message passing.\" International Conference on Machine Learning. PMLR, 2023.\n\n[2] Ding, Yuhui, et al. \"Recurrent distance filtering for graph representation learning.\" arXiv preprint arXiv:2312.01538 (2023).\n\n[3] Huang, Yinan, Siqi Miao, and Pan Li. \"What Can We Learn from State Space Models for Machine Learning on Graphs?.\" arXiv preprint arXiv:2406.05815 (2024).", "methods_and_evaluation_criteria": "See above.", "theoretical_claims": "I did not go over the appendix, but the theoretical claims in the main text look reasonable as many of them are from the SSMs.", "experimental_designs_or_analyses": "See above.", "relation_to_broader_scientific_literature": "This paper is related to graph state space models and graph transformers, which may better capture long-range dependencies in graphs. This paper is especially related to graph mamba, which finds ways to translate graphs into sequences and then apply SSMs.", "essential_references_not_discussed": "See above.", "other_strengths_and_weaknesses": "Even though some included datasets are less popular, it's good to see GRAMA can perform well on those datasets.", "other_comments_or_suggestions": "See above.", "questions_for_authors": "Another benefit that SSMs can bring compared with transformers is efficiency. There is some preliminary timing in the appendix, but how ARAMA scale to larger graphs? Can it inherit the efficiency from SSMs?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "y1fjQg2FCd", "reviewer": "Reviewer_c8Wb", "summary": "This paper introduces a novel GNN architecture based on a state-space model, proposing a new method to transform graph data into a sequence. Unlike previous approaches with similar goals, this work presents a principled approach to sequence generation, ensuring a provably permutation-invariant framework. The proposed model is designed to mitigate oversquashing. Additionally, the paper provides insightful theoretical analysis of the presented architecture.", "questions": "", "limitations": "", "rating": 5, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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.\n\n---\n\n**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.\n| Model | ZINC (exists in paper) | MNIST | CIFAR10 | PATTERN | CLUSTER |\n|---|:---:|:---:|:---:|:---:|:---:|\n| GCN | 0.367±0.011 | 90.705±0.218 | 55.710±0.381  | 71.892±0.334  | 68.498±0.976 |\n| GatedGCN | 0.282±0.015 | 97.340±0.143  | 67.312±0.311  | 85.568±0.088  | 73.840±0.326 |\n| GPS | 0.070±0.004 | 98.051±0.126 | 72.298±0.356  | 86.685±0.059  | 78.016±0.180 |\n| EGT | 0.108±0.009 | 98.173±0.087 | 68.702±0.409  | 86.821±0.020  | 79.232±0.348 |\n| GRIT | 0.059±0.002 | 98.108±0.111  | 76.468±0.881 | 87.196±0.076 | 80.026±0.277 |\n| GRAMA$_{GCN}$ (Ours) | 0.142±0.010 | 97.871±0.188 | 70.283±0.417 | 82.660±0.183 | 74.294±0.595 |\n| GRAMA$_{GatedGCN}$ (Ours) | 0.140±0.008 | 98.119±0.104 | 74.612±0.450 | 86.715±0.099 | 76.883±0.317 |\n| GRAMA$_{GPS}$ (Ours) | 0.061±0.003 | 98.292±0.135 | 75.917±0.408 | 87.406±0.067 | 79.659±0.194 |\n\n\n**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. \n\n**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. \n\n**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.\n\n**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.\n\n**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.", "claims_and_evidence": "The claimed contributions of this paper are supported by theoretical results and extensive empirical experiments.", "methods_and_evaluation_criteria": "The chosen synthetic dataset and real dataset are appropriate and sufficient in number to support the claims. They are selected to adequately demonstrate the claimed benefit of the method (ability to model long-range dependencies). Some datasets that are usually reported (e.g., Cluster, CIFAR-10, MNIST) might be missing, but sufficient results are presented.", "theoretical_claims": "I have not examined the proof of the theoretical results in detail. However, Theorem 4.1 appears to restate known results, and additional citations may be necessary. For example, see [1].\n[1] Aoki, M. (1990). State Space and ARMA Models. In M. Aoki (Ed.), State Space Modeling of Time Series (pp. 21–38)", "experimental_designs_or_analyses": "I have checked the experimental design in the main text. There are no apparent soundness or validity issues. The statistical significance of the results should be reported when possible.", "relation_to_broader_scientific_literature": "The main contribution of this work is to introduce a principled approach to integrating state-space models into a GNN framework. This is important as state-space models are gaining interest due to their attractive properties, and their integration into graph learning is meaningful, given the importance of modeling long-range dependencies in graph settings.", "essential_references_not_discussed": "The essential references seem to be included, although I am not working in the field of state-space-based GNN models, so I do not have a deep understanding of the existing work.", "other_strengths_and_weaknesses": "**Strengths**\n\n- The proposed architecture is novel and principled.\n- The work is overall well-written and has great clarity. The experimental section is detailed enough to be reproducible.\n- The experimental section is extensive and supports the stated claims.\n\n**Weaknesses**\n\n- Limitations of the proposed architecture are not discussed. One point that could be addressed is the scalability to larger graphs.", "other_comments_or_suggestions": "- Mentioning guarantees or results related to the Weisfeiler-Lehman test could strengthen this paper. I suspect that it likely retains any guarantees provided by the base GNN layer.\n\n- I would recommend expanding the discussion on complexity, particularly regarding the number of parameters, in the main text rather than relegating it to the supplementary material. While reading, I got the impression that this model would be much more expensive and slower than other GNN architectures, but this is not the case.", "questions_for_authors": "N/A", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "bnb9DXuUjp", "reviewer": "Reviewer_tuKb", "summary": "This paper introduces a Graph Adaptive method GRAMA based on a learnable ARMA framework to address limitations in existing Graph State Space Models. GRAMA preserves permutation equivariance while enabling efficient long-range information propagation via a selective attention mechanism. Theoretical connections to Selective SSMs highlight its ability to capture long-range dependencies.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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.\n\n---\n\n**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.\n\n**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. \n\n**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.\n\n**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.\n\n\n**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.", "claims_and_evidence": "yes", "methods_and_evaluation_criteria": "yes", "theoretical_claims": "no", "experimental_designs_or_analyses": "yes", "relation_to_broader_scientific_literature": "yes", "essential_references_not_discussed": "no", "other_strengths_and_weaknesses": "### Strengths:\nThe paper has a strong theoretical foundation with detailed proofs supporting the proposed method. The experimental section is exceptionally thorough, covering a wide range of benchmarks and providing comprehensive comparisons with existing methods.\n\n### Weaknesses:\n1. The proposed method relies on three specific GNN backbones: GCN, GatedGCN, and GPS. However, the rationale behind this selection is not clearly discussed. Additionally, the paper does not explore the potential advantages and disadvantages of using other backbones.\n\n2. The comparison with existing methods primarily focuses on performance improvements, but there is limited discussion on the architectural and design differences, especially regarding how the method integrates with graph neural networks.\n\n3. The choice of benchmark tasks may introduce bias, and there is a lack of comparison between graph datasets with varying structural irregularities and heterogeneity, which could affect the generalizability of the results.\n\n4. The paper lacks clear and intuitive visualizations. The method diagram is not straightforward, and there are no direct experimental visuals to illustrate the claimed oversquashing problem, making it harder to connect theory with empirical results.\n\n5. While the appendix is thorough, it is overly lengthy. The core experimental results and conclusions could be distilled more concisely for better clarity and focus.", "other_comments_or_suggestions": "see weakness.", "questions_for_authors": "see weakness.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "DmJdISav6R", "reviewer": "Reviewer_NJt1", "summary": "In this paper, the authors propose addressing the computational complexity issues in traditional graph transformers and the over-squashing problem in GNNs by converting the input graph into a sequential representation and incorporating an autoregressive moving average model with an attention selection mechanism.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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.\n\n---\n\n**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.\n\n**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.\n\n**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.\n\n|Method|Peptides Func|Peptides Struct|Roman-Empire|Amazon-Ratings|OGBN-Arxiv|\n|---|---|---|---|---|---|\n|MixHop-GCN |68.43±0.49|0.2614±0.0023 |79.16±0.70|47.95±0.65|71.29±0.29|\n|GRAMA$_{GCN}$ |70.93±0.78|0.2439±0.0017|88.61±0.43|53.48±0.62|73.86±0.21|\n\n\n**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.\n\n\n**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.\n\n|Method|Roman-empire|Amazon-ratings|Minesweeper|Tolokers|Questions|\n|---|---|---|---|---|---|\n|GOAT|71.59±1.25|44.61±0.50|81.09±1.02|83.11±1.04 |75.76±1.66|\n|Polynormer|92.55±0.3 |54.81±0.49|97.46±0.36 |85.91±0.74| 78.92±0.89|\n|Exphormer|89.03±0.37|53.51±0.46|90.74±0.53|83.77±0.78|73.94±1.06|\n|GRAMA$_{GCN}$ (Ours)|88.61±0.43 |53.48±0.62| 95.27±0.71| 86.23±1.10|79.23±1.16|\n|GRAMA$_{GatedGCN}$ (Ours)|91.82±0.39 |53.71±0.57|98.19±0.58|85.42±0.95|80.47±1.09|\n|GRAMA$_{GPS}$ (Ours) |91.73±0.59|53.36±0.38|98.33±0.55|85.71±0.98|79.11±1.19|\n\n**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.\n\n|Metho |Depth|4|8|16|32|  |\n|---|---|---|---|---|---|---|\n|GatedGCN|  |27.57|47.98|85.36| 171.27 |  |\n|GPS|  |1139.05| 2286.96  | 4545.46 | OOM |  |\n|GRAMA$_{GatedGCN}$ (Ours)|  |51.49|117.01|270.64|792.32 |  |\n|GRAMA$_{GPS}$ (Ours)|  |1162.13|2346.94|4642.19|OOM|  |", "claims_and_evidence": "The authors argue that the biggest challenge in applying sequence models to graph-structured data is `how to transform a graph into a sequential representation`. However, their discussion is limited to the scope of SSM. In fact, research on converting graph data into regular or Euclidean-structured data has long been explored in the graph community, as seen in studies R1–R6.\n\nAdditionally, the authors employ `recurrent layers and dynamical system` designs in their method. Similar approaches have also been investigated in the community, such as recurrent layer methods (R5, R7, R8) and implicit model approaches (R9, R10). \n\nThe authors should consider incorporating these works into the discussion.\n\nR1. Learning convolutional neural networks for graphs. ICML 2016\n\nR2. Janossy Pooling: Learning Deep Permutation-Invariant Functions for Variable-Size Inputs. ICLR 2019\n\nR3. Relational Pooling for Graph Representations. ICML 2019\n\nR4. pathGCN: Learning General Graph Spatial Operators from Paths. ICML 2022\n\nR5. Going Deeper into Permutation-Sensitive Graph Neural Networks. ICML 2022\n\nR6. All in a row: Compressed Convolution Networks for Graphs. ICML 2023\n\nR7. The Graph Neural Network Model. Trans. Neural Networks 2009\n\nR8. Towards Dynamic Message Passing on Graphs. NeurIPS 2024\n\nR9. Implicit Graph Neural Networks. NeurIPS 2020\n\nR10. Optimization-Induced Graph Implicit Nonlinear Diffusion. ICML 2022", "methods_and_evaluation_criteria": "- The proposed method can essentially be seen as MixHop (R11) with layer-selective attention. The authors should consider comparing a simple MixHop approach with GRAMA in the ablation study to demonstrate the effectiveness of the more complex strategy proposed in this paper.\n- Since GRAMA needs to maintain a feature matrix of size $L\\times n\\times d$, its scalability may be affected. For example, MixHop is prone to OOM issues when applied to large-scale graphs. The authors should consider incorporating more large-scale graphs as benchmarks (e.g., R12).\n\nR11. MixHop: Higher-Order Graph Convolutional Architectures via Sparsified Neighborhood Mixing. ICML 2019\n\nR12. Open Graph Benchmark: Datasets for Machine Learning on Graphs. NeurIPS 2020", "theoretical_claims": "There are no issues in this regard for now.", "experimental_designs_or_analyses": "The experiments in this paper are relatively comprehensive. In addition to the main content, the appendix provides a substantial amount of supplementary experimental results. However, there are still some issues with the experimental designs and analyses.\n- One of the motivations of this paper is to address the time consumption issue caused by global attention in graph transformers. Many subsequent GT methods have already attempted to tackle this problem (R13–R15). The authors should consider thoroughly comparing GRAMA with these methods to further substantiate its advantages.\n- GRAMA relies on multiple time steps and blocks to extract features from the input graph. However, the authors only report the time performance of GRAMA+GCN. According to the experimental results, GRAMA combined with GatedGCN or GPS often achieves better results. How do these two models perform in terms of time consumption?\n\nR13. GOAT: A Global Transformer on Large-scale Graphs. ICML 2023\n\nR14. Polynormer: PolynomialExpressive Graph Transformer in Linear Time. ICLR 2024\n\nR15. Exphormer: Sparse Transformers for Graphs. ICML 2023", "relation_to_broader_scientific_literature": "N/A", "essential_references_not_discussed": "Please refer to the claims and evidence.", "other_strengths_and_weaknesses": "The paper aims to improve the model's ability to capture long-range information with reduced computational cost. This issue has been a long-standing focus of research in the graph community.", "other_comments_or_suggestions": "**Post Rebuttal**: My concerns have been addressed. Based on the rebuttal, I am changing my score to 3. I hope the authors will incorporate the discussions from the rebuttal phase into the revised version of the manuscript.", "questions_for_authors": "N/A", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper proposes a graph state space model based on an autoregressive moving average framework. Overall, all reviewers acknowledged that the technical contributions and empirical results are solid. The main concerns raised were: (1) limited discussion of related state space models (SSMs) or sequence models for graphs, (2) missing results on some widely-used benchmarks, (3) lack of comparisons with key baselines, and (4) insufficient justification for certain architectural choices.

The authors’ rebuttal effectively addressed most of these concerns, leading to a consensus among the reviewers in favor of acceptance. After carefully reading the reviews and discussion, the AC agrees with this assessment and recommends acceptance.
Decision: Accept (spotlight poster)