# Graph-Mamba: Towards Long-Range Graph Sequence Modeling with Selective State Spaces

arXiv: https://arxiv.org/abs/2402.00789 · HTML: https://mlsanity.com/paper/2402.00789/

## Key facts

- Cited by 134 papers in the map (data through 14 Oct 2026).
- Placed in Video, motion and generative Mamba models, one of 10 directions in State-space sequence models (S4, Mamba).
- Builds on 36 of its 40 references that are in the map.
- First posted on arXiv 1 Feb 2024.

## Placed in

- State-space sequence models (S4, Mamba) / [Video, motion and generative Mamba models](https://mlsanity.com/ssm/video-motion-and-generative-mamba-models/)

## Builds on (most cited first, 30 of 36)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [An Image is Worth 16x16 Words: Transformers for Image Recognition at Scale](https://mlsanity.com/paper/2010.11929/) (2020)
- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [Mamba: Linear-Time Sequence Modeling with Selective State Spaces](https://mlsanity.com/paper/2312.00752/) (2023)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Efficiently Modeling Long Sequences with Structured State Spaces](https://mlsanity.com/paper/2111.00396/) (2021)
- [Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering](https://mlsanity.com/paper/1606.09375/) (2016)
- [Big Bird: Transformers for Longer Sequences](https://mlsanity.com/paper/2007.14062/) (2020)
- [Rethinking Attention with Performers](https://mlsanity.com/paper/2009.14794/) (2020)
- [Vision Mamba: Efficient Visual Representation Learning with Bidirectional State Space Model](https://mlsanity.com/paper/2401.09417/) (2024)
- [VMamba: Visual State Space Model](https://mlsanity.com/paper/2401.10166/) (2024)
- [RWKV: Reinventing RNNs for the Transformer Era](https://mlsanity.com/paper/2305.13048/) (2023)
- [Graph Neural Networks for Social Recommendation](https://mlsanity.com/paper/1902.07243/) (2019)
- [Recipe for a General, Powerful, Scalable Graph Transformer](https://mlsanity.com/paper/2205.12454/) (2022)
- [Benchmarking Graph Neural Networks](https://mlsanity.com/paper/2003.00982/) (2020)
- [A Generalization of Transformer Networks to Graphs](https://mlsanity.com/paper/2012.09699/) (2020)
- [On the Bottleneck of Graph Neural Networks and its Practical Implications](https://mlsanity.com/paper/2006.05205/) (2020)
- [Graph Transformer Networks](https://mlsanity.com/paper/1911.06455/) (2019)
- [Hungry Hungry Hippos: Towards Language Modeling with State Space Models](https://mlsanity.com/paper/2212.14052/) (2022)
- [ConViT: Improving Vision Transformers with Soft Convolutional Inductive Biases](https://mlsanity.com/paper/2103.10697/) (2021)
- [Understanding over-squashing and bottlenecks on graphs via curvature](https://mlsanity.com/paper/2111.14522/) (2021)
- [Rethinking Graph Transformers with Spectral Attention](https://mlsanity.com/paper/2106.03893/) (2021)
- [U-Mamba: Enhancing Long-range Dependency for Biomedical Image Segmentation](https://mlsanity.com/paper/2401.04722/) (2024)
- [Residual Gated Graph ConvNets](https://mlsanity.com/paper/1711.07553/) (2017)
- [Do Transformers Really Perform Bad for Graph Representation?](https://mlsanity.com/paper/2106.05234/) (2021)
- [Long Range Language Modeling via Gated State Spaces](https://mlsanity.com/paper/2206.13947/) (2022)
- [Long Range Graph Benchmark](https://mlsanity.com/paper/2206.08164/) (2022)
- [Representing Long-Range Context for Graph Neural Networks with Global Attention](https://mlsanity.com/paper/2201.08821/) (2022)
- [Structure-Aware Transformer for Graph Representation Learning](https://mlsanity.com/paper/2202.03036/) (2022)

## Built on by (most cited first, 30 of 134)

- [Parallelizing Linear Transformers with the Delta Rule over Sequence Length](https://mlsanity.com/paper/2406.06484/) (2024)
- [VideoMamba: State Space Model for Efficient Video Understanding](https://mlsanity.com/paper/2403.06977/) (2024)
- [PointMamba: A Simple State Space Model for Point Cloud Analysis](https://mlsanity.com/paper/2402.10739/) (2024)
- [EfficientVMamba: Atrous Selective Scan for Light Weight Visual Mamba](https://mlsanity.com/paper/2403.09977/) (2024)
- [The Hidden Attention of Mamba Models](https://mlsanity.com/paper/2403.01590/) (2024)
- [Graph Mamba: Towards Learning on Graphs with State Space Models](https://mlsanity.com/paper/2402.08678/) (2024)
- [ZigMa: A DiT-style Zigzag Mamba Diffusion Model](https://mlsanity.com/paper/2403.13802/) (2024)
- [Mamba-360: Survey of State Space Models as Transformer Alternative for Long Sequence Modelling: Methods, Applications, and Challenges](https://mlsanity.com/paper/2404.16112/) (2024)
- [State Space Model for New-Generation Network Alternative to Transformers: A Survey](https://mlsanity.com/paper/2404.09516/) (2024)
- [FreqMamba: Viewing Mamba from a Frequency Perspective for Image Deraining](https://mlsanity.com/paper/2404.09476/) (2024)
- [Dual-path Mamba: Short and Long-term Bidirectional Selective Structured State Space Models for Speech Separation](https://mlsanity.com/paper/2403.18257/) (2024)
- [Hamba: Single-view 3D Hand Reconstruction with Graph-guided Bi-Scanning Mamba](https://mlsanity.com/paper/2407.09646/) (2024)
- [On Vanishing Gradients, Over-Smoothing, and Over-Squashing in GNNs: Bridging Recurrent and Graph Learning](https://mlsanity.com/paper/2502.10818/) (2025)
- [LongMamba: Enhancing Mamba's Long Context Capabilities via Training-Free Receptive Field Enlargement](https://mlsanity.com/paper/2504.16053/) (2025)
- [A Survey of Mamba](https://mlsanity.com/paper/2408.01129/) (2024)
- [SSAMBA: Self-Supervised Audio Representation Learning with Mamba State Space Model](https://mlsanity.com/paper/2405.11831/) (2024)
- [MambaLRP: Explaining Selective State Space Sequence Models](https://mlsanity.com/paper/2406.07592/) (2024)
- [MambaVC: Learned Visual Compression with Selective State Spaces](https://mlsanity.com/paper/2405.15413/) (2024)
- [Can Classic GNNs Be Strong Baselines for Graph-level Tasks? Simple Architectures Meet Excellence](https://mlsanity.com/paper/2502.09263/) (2025)
- [STG-Mamba: Spatial-Temporal Graph Learning via Selective State Space Model](https://mlsanity.com/paper/2403.12418/) (2024)
- [NetMamba: Efficient Network Traffic Classification via Pre-training Unidirectional Mamba](https://mlsanity.com/paper/2405.11449/) (2024)
- [Mamba-FETrack: Frame-Event Tracking via State Space Model](https://mlsanity.com/paper/2404.18174/) (2024)
- [MTMamba: Enhancing Multi-Task Dense Scene Understanding by Mamba-Based Decoders](https://mlsanity.com/paper/2407.02228/) (2024)
- [The Interpretable and Effective Graph Neural Additive Networks](https://mlsanity.com/paper/2406.01317/) (2024)
- [DMM: Disparity-guided Multispectral Mamba for Oriented Object Detection in Remote Sensing](https://mlsanity.com/paper/2407.08132/) (2024)
- [Learning Graph Quantized Tokenizers](https://mlsanity.com/paper/2410.13798/) (2024)
- [Learning Long Range Dependencies on Graphs via Random Walks](https://mlsanity.com/paper/2406.03386/) (2024)
- [DyG-Mamba: Continuous State Space Modeling on Dynamic Graphs](https://mlsanity.com/paper/2408.06966/) (2024)
- [Text-controlled Motion Mamba: Text-Instructed Temporal Grounding of Human Motion](https://mlsanity.com/paper/2404.11375/) (2024)
- [SST: Multi-Scale Hybrid Mamba-Transformer Experts for Time Series Forecasting](https://mlsanity.com/paper/2404.14757/) (2024)

## Abstract (arXiv)

Attention mechanisms have been widely used to capture long-range dependencies among nodes in Graph Transformers. Bottlenecked by the quadratic computational cost, attention mechanisms fail to scale in large graphs. Recent improvements in computational efficiency are mainly achieved by attention sparsification with random or heuristic-based graph subsampling, which falls short in data-dependent context reasoning. State space models (SSMs), such as Mamba, have gained prominence for their effectiveness and efficiency in modeling long-range dependencies in sequential data. However, adapting SSMs to non-sequential graph data presents a notable challenge. In this work, we introduce Graph-Mamba, the first attempt to enhance long-range context modeling in graph networks by integrating a Mamba block with the input-dependent node selection mechanism. Specifically, we formulate graph-centric node prioritization and permutation strategies to enhance context-aware reasoning, leading to a substantial improvement in predictive performance. Extensive experiments on ten benchmark datasets demonstrate that Graph-Mamba outperforms state-of-the-art methods in long-range graph prediction tasks, with a fraction of the computational cost in both FLOPs and GPU memory consumption. The code and models are publicly available at https://github.com/bowang-lab/Graph-Mamba.