# DG-Mamba: Robust and Efficient Dynamic Graph Structure Learning with Selective State Space Models

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

## Key facts

- Cited by 8 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 30 of its 48 references that are in the map.
- First posted on arXiv 11 Dec 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 30)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (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)
- [Efficient Estimation of Word Representations in Vector Space](https://mlsanity.com/paper/1301.3781/) (2013)
- [Rethinking Attention with Performers](https://mlsanity.com/paper/2009.14794/) (2020)
- [Variational Graph Auto-Encoders](https://mlsanity.com/paper/1611.07308/) (2016)
- [HiPPO: Recurrent Memory with Optimal Polynomial Projections](https://mlsanity.com/paper/2008.07669/) (2020)
- [Temporal Graph Networks for Deep Learning on Dynamic Graphs](https://mlsanity.com/paper/2006.10637/) (2020)
- [Predicting Dynamic Embedding Trajectory in Temporal Interaction Networks](https://mlsanity.com/paper/1908.01207/) (2019)
- [EvolveGCN: Evolving Graph Convolutional Networks for Dynamic Graphs](https://mlsanity.com/paper/1902.10191/) (2019)
- [Dynamic Neural Networks: A Survey](https://mlsanity.com/paper/2102.04906/) (2021)
- [Structured Sequence Modeling with Graph Convolutional Recurrent Networks](https://mlsanity.com/paper/1612.07659/) (2016)
- [Representation Learning for Dynamic Graphs: A Survey](https://mlsanity.com/paper/1905.11485/) (2019)
- [Topology Attack and Defense for Graph Neural Networks: An Optimization Perspective](https://mlsanity.com/paper/1906.04214/) (2019)
- [GNNGuard: Defending Graph Neural Networks against Adversarial Attacks](https://mlsanity.com/paper/2006.08149/) (2020)
- [Graph-Mamba: Towards Long-Range Graph Sequence Modeling with Selective State Spaces](https://mlsanity.com/paper/2402.00789/) (2024)
- [Graph Adversarial Training: Dynamically Regularizing Based on Graph Structure](https://mlsanity.com/paper/1902.08226/) (2019)
- [Graph Structure Learning with Variational Information Bottleneck](https://mlsanity.com/paper/2112.08903/) (2021)
- [Certifiable Robustness and Robust Training for Graph Convolutional Networks](https://mlsanity.com/paper/1906.12269/) (2019)
- [Certified Robustness of Graph Neural Networks against Adversarial Structural Perturbation](https://mlsanity.com/paper/2008.10715/) (2020)
- [Dynamic Graph Neural Networks for Sequential Recommendation](https://mlsanity.com/paper/2104.07368/) (2021)
- [Position-aware Structure Learning for Graph Topology-imbalance by Relieving Under-reaching and Over-squashing](https://mlsanity.com/paper/2208.08302/) (2022)
- [Hyperbolic Geometric Graph Representation Learning for Hierarchy-imbalance Node Classification](https://mlsanity.com/paper/2304.05059/) (2023)
- [RDGSL: Dynamic Graph Representation Learning with Structure Learning](https://mlsanity.com/paper/2309.02025/) (2023)
- [What Can We Learn from State Space Models for Machine Learning on Graphs?](https://mlsanity.com/paper/2406.05815/) (2024)
- [Spatio-Temporal Latent Graph Structure Learning for Traffic Forecasting](https://mlsanity.com/paper/2202.12586/) (2022)
- [SpoT-Mamba: Learning Long-Range Dependency on Spatio-Temporal Graphs with Selective State Spaces](https://mlsanity.com/paper/2406.11244/) (2024)
- [Time-aware Graph Structure Learning via Sequence Prediction on Temporal Graphs](https://mlsanity.com/paper/2306.07699/) (2023)

## Built on by (most cited first, 8 of 8)

- [GRAVER: Generative Graph Vocabularies for Robust Graph Foundation Models Fine-tuning](https://mlsanity.com/paper/2511.05592/) (2025)
- [STM3: Mixture of Multiscale Mamba for Long-Term Spatio-Temporal Time-Series Prediction](https://mlsanity.com/paper/2508.12247/) (2025)
- [Beyond Pairwise Connections: Extracting High-Order Functional Brain Network Structures under Global Constraints](https://mlsanity.com/paper/2510.09175/) (2025)
- [ChronoSpike: An Adaptive Spiking Graph Neural Network for Dynamic Graphs](https://mlsanity.com/paper/2602.01124/) (2026)
- [GLADMamba: Unsupervised Graph-Level Anomaly Detection Powered by Selective State Space Model](https://mlsanity.com/paper/2503.17903/) (2025)
- [DyGSSM: Multi-view Dynamic Graph Embeddings with State Space Model Gradient Update](https://mlsanity.com/paper/2505.09017/) (2025)
- [Versatile and Efficient Medical Image Super-Resolution Via Frequency-Gated Mamba](https://mlsanity.com/paper/2510.27296/) (2025)
- [Temporal Memory-Aware Online Test-Time Adaptation on Dynamic Graphs](https://mlsanity.com/paper/2608.27948/) (2026)

## Abstract (arXiv)

Dynamic graphs exhibit intertwined spatio-temporal evolutionary patterns, widely existing in the real world. Nevertheless, the structure incompleteness, noise, and redundancy result in poor robustness for Dynamic Graph Neural Networks (DGNNs). Dynamic Graph Structure Learning (DGSL) offers a promising way to optimize graph structures. However, aside from encountering unacceptable quadratic complexity, it overly relies on heuristic priors, making it hard to discover underlying predictive patterns. How to efficiently refine the dynamic structures, capture intrinsic dependencies, and learn robust representations, remains under-explored. In this work, we propose the novel DG-Mamba, a robust and efficient Dynamic Graph structure learning framework with the Selective State Space Models (Mamba). To accelerate the spatio-temporal structure learning, we propose a kernelized dynamic message-passing operator that reduces the quadratic time complexity to linear. To capture global intrinsic dynamics, we establish the dynamic graph as a self-contained system with State Space Model. By discretizing the system states with the cross-snapshot graph adjacency, we enable the long-distance dependencies capturing with the selective snapshot scan. To endow learned dynamic structures more expressive with informativeness, we propose the self-supervised Principle of Relevant Information for DGSL to regularize the most relevant yet least redundant information, enhancing global robustness. Extensive experiments demonstrate the superiority of the robustness and efficiency of our DG-Mamba compared with the state-of-the-art baselines against adversarial attacks.