# Graph Mamba: Towards Learning on Graphs with State Space Models

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

## Key facts

- Cited by 86 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 73 of its 114 references that are in the map.
- First posted on arXiv 13 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 73)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Swin Transformer: Hierarchical Vision Transformer using Shifted Windows](https://mlsanity.com/paper/2103.14030/) (2021)
- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [Layer Normalization](https://mlsanity.com/paper/1607.06450/) (2016)
- [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)
- [A Comprehensive Survey on Graph Neural Networks](https://mlsanity.com/paper/1901.00596/) (2019)
- [Efficiently Modeling Long Sequences with Structured State Spaces](https://mlsanity.com/paper/2111.00396/) (2021)
- [Open Graph Benchmark: Datasets for Machine Learning on Graphs](https://mlsanity.com/paper/2005.00687/) (2020)
- [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)
- [Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networks](https://mlsanity.com/paper/1810.02244/) (2018)
- [Large Language Models Can Be Easily Distracted by Irrelevant Context](https://mlsanity.com/paper/2302.00093/) (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)
- [On the Bottleneck of Graph Neural Networks and its Practical Implications](https://mlsanity.com/paper/2006.05205/) (2020)
- [Combining Recurrent, Convolutional, and Continuous-time Models with Linear State-Space Layers](https://mlsanity.com/paper/2110.13985/) (2021)
- [HiPPO: Recurrent Memory with Optimal Polynomial Projections](https://mlsanity.com/paper/2008.07669/) (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)
- [Rethinking Graph Transformers with Spectral Attention](https://mlsanity.com/paper/2106.03893/) (2021)
- [MixHop: Higher-Order Graph Convolutional Architectures via Sparsified Neighborhood Mixing](https://mlsanity.com/paper/1905.00067/) (2019)
- [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)
- [A critical look at the evaluation of GNNs under heterophily: Are we really making progress?](https://mlsanity.com/paper/2302.11640/) (2023)

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

- [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)
- [ZigMa: A DiT-style Zigzag Mamba Diffusion Model](https://mlsanity.com/paper/2403.13802/) (2024)
- [Point Cloud Mamba: Point Cloud Learning via State Space Model](https://mlsanity.com/paper/2403.00762/) (2024)
- [TimeMachine: A Time Series is Worth 4 Mambas for Long-term Forecasting](https://mlsanity.com/paper/2403.09898/) (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)
- [Hamba: Single-view 3D Hand Reconstruction with Graph-guided Bi-Scanning Mamba](https://mlsanity.com/paper/2407.09646/) (2024)
- [MambaMixer: Efficient Selective State Space Models with Dual Token and Channel Selection](https://mlsanity.com/paper/2403.19888/) (2024)
- [MambaLRP: Explaining Selective State Space Sequence Models](https://mlsanity.com/paper/2406.07592/) (2024)
- [Can Classic GNNs Be Strong Baselines for Graph-level Tasks? Simple Architectures Meet Excellence](https://mlsanity.com/paper/2502.09263/) (2025)
- [Matten: Video Generation with Mamba-Attention](https://mlsanity.com/paper/2405.03025/) (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)
- [Contrastive Graph Representation Learning with Adversarial Cross-view Reconstruction and Information Bottleneck](https://mlsanity.com/paper/2408.00295/) (2024)
- [Mambular: A Sequential Model for Tabular Deep Learning](https://mlsanity.com/paper/2408.06291/) (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)
- [QuadMamba: Learning Quadtree-based Selective Scan for Visual State Space Model](https://mlsanity.com/paper/2410.06806/) (2024)
- [Spatio-Spectral Graph Neural Networks](https://mlsanity.com/paper/2405.19121/) (2024)
- [DyG-Mamba: Continuous State Space Modeling on Dynamic Graphs](https://mlsanity.com/paper/2408.06966/) (2024)
- [Beyond Message Passing: Neural Graph Pattern Machine](https://mlsanity.com/paper/2501.18739/) (2025)
- [Text-controlled Motion Mamba: Text-Instructed Temporal Grounding of Human Motion](https://mlsanity.com/paper/2404.11375/) (2024)
- [State Space Models on Temporal Graphs: A First-Principles Study](https://mlsanity.com/paper/2406.00943/) (2024)
- [MambaTS: Improved Selective State Space Models for Long-term Time Series Forecasting](https://mlsanity.com/paper/2405.16440/) (2024)
- [DyGMamba: Efficiently Modeling Long-Term Temporal Dependency on Continuous-Time Dynamic Graphs with State Space Models](https://mlsanity.com/paper/2408.04713/) (2024)
- [DepMamba: Progressive Fusion Mamba for Multimodal Depression Detection](https://mlsanity.com/paper/2409.15936/) (2024)
- [A Survey of Graph Transformers: Architectures, Theories and Applications](https://mlsanity.com/paper/2502.16533/) (2025)
- [What Can We Learn from State Space Models for Machine Learning on Graphs?](https://mlsanity.com/paper/2406.05815/) (2024)

## Abstract (arXiv)

Graph Neural Networks (GNNs) have shown promising potential in graph representation learning. The majority of GNNs define a local message-passing mechanism, propagating information over the graph by stacking multiple layers. These methods, however, are known to suffer from two major limitations: over-squashing and poor capturing of long-range dependencies. Recently, Graph Transformers (GTs) emerged as a powerful alternative to Message-Passing Neural Networks (MPNNs). GTs, however, have quadratic computational cost, lack inductive biases on graph structures, and rely on complex Positional/Structural Encodings (SE/PE). In this paper, we show that while Transformers, complex message-passing, and SE/PE are sufficient for good performance in practice, neither is necessary. Motivated by the recent success of State Space Models (SSMs), such as Mamba, we present Graph Mamba Networks (GMNs), a general framework for a new class of GNNs based on selective SSMs. We discuss and categorize the new challenges when adapting SSMs to graph-structured data, and present four required and one optional steps to design GMNs, where we choose (1) Neighborhood Tokenization, (2) Token Ordering, (3) Architecture of Bidirectional Selective SSM Encoder, (4) Local Encoding, and dispensable (5) PE and SE. We further provide theoretical justification for the power of GMNs. Experiments demonstrate that despite much less computational cost, GMNs attain an outstanding performance in long-range, small-scale, large-scale, and heterophilic benchmark datasets.