GG-SSMs: Graph-Generating State Space Models
Nikola Zubić, Davide Scaramuzza · 2024
Read GG-SSMs: Graph-Generating State Space Models by Nikola Zubić, Davide Scaramuzza (2024) 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-2412-12423.txt.
Introduction
Nikola Zubić and Davide Scaramuzza introduce Graph-Generating State Space Models in a 2024 paper, a new take on the sequence models used in vision and time series work. Standard state space models process data along a fixed one-dimensional path, which limits how they capture links between distant parts of an input. Even flexible scanning variants follow preset paths.
Their framework instead builds a graph from the data itself, linking features by their relationships with a minimum spanning tree method, and passes information along that graph. Tested on eleven datasets, from ImageNet classification to optical flow and eye tracking, the models set new best results on every task. They also used fewer parameters than rivals on some tasks.
Catalog record
| CREATOR | Nikola Zubić, Davide Scaramuzza |
|---|---|
| YEAR | 2024 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 43 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2412-12423
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
GG-SSMs: Graph-Generating State Space Models Nikola Zubić, Davide Scaramuzza Abstract State Space Models (SSMs) are powerful tools for modeling sequential data in computer vision and time series analysis domains. However, traditional SSMs are limited by fixed, one-dimensional sequential processing, which restricts their ability to model non-local interactions in high-dimensional data. While methods like Mamba and VMamba introduce selective and flexible scanning strategies, they rely on predetermined paths, which fails to efficiently capture complex dependencies. We introduce Graph-Generating State Space Models (GG-SSMs), a novel framework that overcomes these limitations by dynamically constructing graphs based on feature relationships. Using Chazelle’s Minimum Spanning Tree algorithm, GG-SSMs adapt to the inherent data structure, enabling robust feature propagation across dynamically generated graphs and efficiently modeling complex dependencies. We validate GG-SSMs on 11 diverse datasets, including event-based eye-tracking, ImageNet classification, optical flow estimation, and six time series datasets. GG-SSMs achieve state-of-the-art performance across all tasks, surpassing existing methods by significant margins. Specifically, GG-SSM attains a top-1 accuracy of 84.9% on ImageNet, outperforming prior SSMs by 1%, reducing the KITTI-15 error rate to 2.77%, and improving eye-tracking detection rates by up to 0.33% with fewer parameters. These results demonstrate that dynamic scanning based on feature relationships significantly improves SSMs’ representational power and efficiency, offering a versatile tool for various applications in computer vision and beyond. Multimedial Material: For GitHub code, poster and other details visit https://github.com/uzh-rpg/gg_ssms . Figure 1 : Illustration of the Graph-Generating State Space Model (GG-SSM). Given an input feature set \{\mathbf{x}_{i}\}_{i=1}^{L} , we construct a graph based on feature dissimilarities and apply an efficient algorithm to generate a minimum spanning tree \mathcal{T} . SSM state propagation is then performed along this tree to obtain improved feature representations. 1 Introduction Modeling complex, long-range dependencies in high-dimensional data is a fundamental challenge in computer vision and time series analysis. Accurately capturing these dependencies is crucial for understanding intricate structures and relationships within data, directly impacting the performance of machine learning models in real-world applications. Traditional models like Convolutional Neural Networks (CNNs) He et al. 2016 excel at capturing local patterns but struggle with global context due to their limited receptive fields. Transformers Vaswani et al. 2017 address this limitation by employing self-attention mechanisms to model global relationships; however, they suffer from quadratic computational complexity with respect to input size, making them less practical for high-resolution images or long sequences. State Space Models (SSMs) have emerged as efficient alternatives for sequential data modeling, demonstrating the ability to capture long-range dependencies with linear computational complexity concerning sequence length Gu et al. 2021 ; Gu et al. 2022 . SSMs process sequences using state transitions, making them suitable for tasks requiring memory of previous inputs. However, traditional SSMs are constrained by fixed, one-dimensional sequential processing, which limits their ability to model non-local interactions inherent in high-dimensional visual data Nguyen et al. 2022 . This limitation hampers their effectiveness in capturing complex spatial dependencies critical for comprehensive visual understanding. Recent methods like Mamba Gu and Dao 2023 and VMamba Liu et al. 2024 have attempted to overcome these constraints by introducing selective and flexible scanning strategies. Mamba Gu and Dao 2023 introduces a selective mechanism to improve context awareness, while VMamba Liu et al. 2024 extends this approach with more scanning paths to achieve global context. Despite these advancements, they rely on predetermined 1D scanning trajectories unrolled in a few directions (e.g., on an image grid) and struggle to adapt to the diverse and complex structures found in data. Consequently, they fail to efficiently capture intricate dependencies and long-range interactions not aligned with the predefined paths. The core challenge remains: designing models that can adaptively and efficiently capture complex, non-local dependencies in high-dimensional data without incurring prohibitive computational costs. Fixed scanning strategies cannot accommodate the diverse structures in data. While graph-based models naturally represent complex relationships Kipf and Welling 2017 , they often face high computational complexity when constructing and processing large graphs. This paper introduces Graph-Generating State Space Models (GG-SSMs) , a novel framework that overcomes these limitations by dynamically constructing graphs based on feature relationships within the data. By utilizing Chazelle’s Minimum Spanning Tree (MST) algorithm Chazelle 2000 , which operates with near-linear time complexity, GG-SSMs adapt to the inherent data structure, enabling robust feature propagation across dynamically generated graphs. This approach efficiently models complex, long-range dependencies by moving beyond fixed scanning paths and capturing intrinsic relationships between features. The key idea behind GG-SSMs is integrating dynamic graph construction into the state space modeling framework, allowing the model to naturally adapt its processing pathways based on the data’s structure. GG-SSMs efficiently identify the most significant connections among data elements by constructing an MST over the data features. This dynamic graph is the backbone for state propagation, enabling the model to capture long-range dependencies and complex interactions without significant computational overhead. Our contributions can be summarized as follows: 1. Dynamic Graph-Based State Space Modeling : We propose a method for integrating dynamic graph structures into SSMs, enabling the capture of complex spatial and temporal dependencies in high-dimensional data. 2. Efficient Computation with MSTs : Leveraging Chazelle’s MST algorithm Chazelle 2000 , GG-SSMs construct optimal graphs with minimal computational overhead, ensuring scalability to large datasets and high-resolution inputs. 3. State-of-the-Art Performance : GG-SSMs consistently outperform existing methods, including Mamba Gu and Dao 2023 and VMamba Liu et al. 2024 , across multiple benchmarks, achieving higher accuracy with fewer parameters and lower computational costs. We validate GG-SSMs on 11 diverse datasets, covering various computer vision and time series tasks. Specifically: - On the ImageNet classification benchmark Deng et al. 2009 , GG-SSM achieves a top-1 accuracy of 84.9% , outperforming prior SSM-based models by 1% . - In optical flow estimation on the KITTI-15 dataset Geiger et al. 2012 , GG-SSM reduces the error rate to 2.77% , the lowest reported to date. - For event-based eye-tracking datasets (INI-30 Bonazzi et al. 2023 and Event-based LPW Chen et al. 2023 ), GG-SSM improves detection rates by up to 0.33% while using fewer parameters. - Across six renowned time series datasets , GG-SSMs achieve superior forecasting accuracy, demonstrating versatility beyond traditional vision tasks. These results demonstrate that dynamic scanning based on feature relationships significantly improves SSMs’ representational power and efficiency, offering a versatile tool for various applications in computer vision and beyond. 2 Related Work 2.1 Challenges with Sequential-Only SSMs Data naturally exhibit multi-dimensional structures with complex spatial or spatiotemporal relationships in many computer vision applications and event-based data processing Zubić et al. 2023 ; Zubić and Lio 2021 . Traditional State Space Models (SSMs) process signals in a strictly one-dimensional sequence, which makes them ill-suited to capture non-local interactions. For instance, images and event streams include spatial dependencies that span two or more dimensions, but standard SSMs restrict the flow of information along predetermined scanning paths. While these 1D-sequential SSMs excel in tasks such as NLP, their inability to adapt to more complex data topologies leads to poor performance on high-dimensional or multi-variate inputs. Such limitations are particularly pronounced in tasks that demand a global understanding of spatial patterns, such as image classification, optical flow, and dynamic vision sensing. 2.2 Approaches for High-Dimensional Visual SSMs Researchers have proposed specialized architectures for