GRAMA : Adaptive Graph Autoregressive Moving Average Models

Moshe Eliasof, Alessio Gravina, Andrea Ceni, Carola-Bibiane Schönlieb · 2025

Read GRAMA : Adaptive Graph Autoregressive Moving Average Models by Moshe Eliasof, Alessio Gravina, Andrea Ceni, Carola-Bibiane Schönlieb (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2501-12732.txt.

Introduction

Moshe Eliasof and co-authors introduced GRAMA in a 2025 paper, a graph learning method for long-range information flow. Graph neural networks struggle to pass messages across distant nodes. Recent state space designs help, but they either break a key symmetry of graph data or handle pairs instead of sequences. GRAMA rebuilds the classic autoregressive moving average model as a learnable graph method, working on data turned into sequences.

A selective attention step learns the model's coefficients on the fly, letting information travel far while respecting node order symmetry. The authors also tie GRAMA formally to selective state space models. Across fourteen synthetic and real datasets, the method consistently beat its backbone models and rivaled the best published results. Long-range graph tasks are the target throughout.

Catalog record

CREATORMoshe Eliasof, Alessio Gravina, Andrea Ceni, Carola-Bibiane Schönlieb
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE103 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2501-12732

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

GRAMA : Adaptive Graph Autoregressive Moving Average Models Moshe Eliasof, Alessio Gravina, Andrea Ceni, Carola-Bibiane Schönlieb Abstract Graph State Space Models (SSMs) have recently been introduced to enhance Graph Neural Networks (GNNs) in modeling long-range interactions. Despite their success, existing methods either compromise on permutation equivariance or limit their focus to pairwise interactions rather than sequences. Building on the connection between Autoregressive Moving Average (ARMA) and SSM, in this paper, we introduce GRAMA , a Graph Adaptive method based on a learnable Autoregressive Moving Average (ARMA) framework that addresses these limitations. By transforming from static to sequential graph data, GRAMA leverages the strengths of the ARMA framework, while preserving permutation equivariance. Moreover, GRAMA incorporates a selective attention mechanism for dynamic learning of ARMA coefficients, enabling efficient and flexible long-range information propagation. We also establish theoretical connections between GRAMA and Selective SSMs, providing insights into its ability to capture long-range dependencies. Extensive experiments on 14 synthetic and real-world datasets demonstrate that GRAMA consistently outperforms backbone models and performs competitively with state-of-the-art methods. 1 Introduction Neural graph learning has become crucial in handling graph-structured data across various domains, such as social networks ( Kipf & Welling, 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 oversquashing ( Alon & Yahav, 2021 ; Di Giovanni et al., 2023 ) , that hinders their ability to 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 ( Gravina et al., 2023 ; Gravina et al., 2024a ) , 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. However, the quadratic computational cost of full attention limits their scalability, and in some cases, they were found to underperform on long-range benchmarks when compared to standard MPNNs ( Tönshoff et al., 2023 ) . 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 selection, 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 challenge lies in the fundamental question of “how to transform a graph into a sequence?” . To this end, several approaches were proposed, from a graph-to-sequence heuristic in Wang et al. (2024a) , to studying the relationship between SSMs and spectral GNNs by pairwise interactions ( Huang et al., 2024 ) , as well as sample-based random walk sequencing of the graph ( Behrouz & Hashemi, 2024 ) . However, as we discuss later, some of them lose the permutation-equivariance property 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-processing capabilities, especially for addressing oversquashing in GNNs. To resolve these issues, we propose, instead, a complementary approach – transforming a static input graph into a sequence of graphs, combined with an adaptive neural autoregressive moving-average (ARMA) mechanism, called GRAMA . We show that GRAMA is theoretically equivalent 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 to graph transformers, while maintaining backbone properties, such as permutation-equivariance. Main Contributions. Our Adaptive Gr aph A utoregressive M oving A verage ( GRAMA ) model offers several advancements in 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 permutation 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. • 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 et al., 2022 ) ) and show the compelling performance by GRAMA on 14 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 & Welling, 2016 ) , GraphSAGE ( Hamilton et al., 2017 ) , and GIN ( Xu et al., 2019 ) face challenges such as over-smoothing ( Nt & Maehara, 2019 ; Oono & Suzuki, 2020 ; Cai & Wang, 2020 ; Rusch et al., 2023 ) and over-squashing ( Alon & Yahav, 2021 ; Topping et al., 2022 ; Di Giovanni et al., 2023 ) , which hinder long-range information propagation—critical in applications like bioinformatics ( Baek 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 ) , weight space regularization ( Gravina et al., 2023 ; Gravina et al., 2024a ) , 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 structural encodings (RWSE) ( Dwivedi et al., 2022a ) , to encode graph structure. However, the quadratic complexity of full attention

Read the complete text