Research map / Graph learning / Knowledge and temporal graphs
DG-Mamba: Robust and Efficient Dynamic Graph Structure Learning with Selective State Space Models
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes DG-Mamba, a dynamic graph structure learning framework that combines kernelized linear-time message passing, a selective state space model over cross-snapshot structures, and a self-supervised Principle of Relevant Information regularizer, evaluated for robustness against adversarial attacks on link prediction.
Problem
Dynamic graph neural networks are fragile to structural incompleteness, noise, redundancy and adversarial attacks, and existing dynamic graph structure learning methods have quadratic complexity in both spatial and temporal dimensions and rely on local Markov assumptions.
Approach
Replace softmax edge-weighting with positive random feature kernel attention to make message passing linear, model the snapshot sequence as an SSM (Mamba-style selective scan) whose discretization is driven by learned inter-graph adjacency to capture long-range dependencies, and regularize learned structures with a PRI-based loss.
Key results
- Under targeted NETTACK attacks, DG-Mamba has the lowest average AUC drop: 17.6% (COLLAB evasion), 22.1% (Yelp evasion), 17.5% (ACT evasion), versus the next best around 22.4-23.0%.
- On COLLAB clean future link prediction, DG-Mamba reaches 93.60 AUC vs 92.68 for DGIB-Cat and 88.77 for DySAT.
- Under structure attack on COLLAB, DG-Mamba achieves 92.60 AUC vs 84.16 for DGIB-Cat.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Add long-range selective modeling (ablation) | DG-Mamba · clean datasets | AUC | Helped |
| Add PRI regularization (ablation) | DG-Mamba · clean datasets | AUC | Helped |
| Replace kernelized message-passing with vanilla attention-based message-passing (ablation) | DG-Mamba · clean datasets | AUC | Helped |
| Use kernelized message-passing instead of vanilla attention-based message-passing (ablation) | DG-Mamba · dynamic graph scaling | training time and GPU usage: 71.3%; 45.8%; 38.4%; 28.9% | Helped |
| Use DG-Mamba rather than DGIB-Cat | future link prediction · Yelp structure attack | AUC: 77.72 vs 77.40 | Hurt |
| Use DG-Mamba rather than DGIB-Cat | future link prediction · COLLAB and ACT clean; all three structure attacks | AUC | Helped |
| Use DG-Mamba rather than other competitive baselines | future link prediction · targeted evasion and poisoning attacks | average relative AUC decrease | Helped |
Surprising findings
- DGIB-Cat or DGIB-Bern slightly outperform DG-Mamba on a few non-targeted feature-attack settings, as the authors acknowledge.
- The authors report that the kernelized variant without the kernel trick (w/o KMP) performs better than DG-Mamba on accuracy, accepting an effectiveness-for-efficiency tradeoff.
Limitations
- Gains on non-targeted feature attacks are not uniform; DGIB sometimes wins.
- Inter-graph structure initialized via cosine similarity of initial embeddings and top-k with k=|E|, a heuristic choice.
- Theoretical kernel approximation bound is loose and the empirical argument relies on vanishing tau and epsilon.
Experimental setup
Datasets: COLLAB Yelp ACT
Benchmarks: COLLAB Yelp ACT
Metrics: AUC relative AUC decrease (Δ%) training time per epoch GPU peak memory
Baselines: GAE VGAE GAT GCRN EvolveGCN DySAT SpoT-Mamba RDGSL TGSL RGCN WinGNN DGIB
Builds on: Mamba positive random features (FAVOR+) Gumbel-Softmax DGIB Principle of Relevant Information
Closest papers by meaning
- DyG-Mamba: Continuous State Space Modeling on Dynamic Graphs (NeurIPS 2025 · similarity 0.91)
- Learning Long Range Spatio-Temporal Representations over Continuous Time Dynamic Graphs with State Space Models (ICML 2026 · similarity 0.88)
- TMetaNet: Topological Meta-Learning Framework for Dynamic Link Prediction (ICML 2025 · similarity 0.88)
- State Space Models on Temporal Graphs: A First-Principles Study (NeurIPS 2024 · similarity 0.88)
- When Graph Neural Networks Meet Dynamic Mode Decomposition (ICLR 2025 · similarity 0.88)
- A Deep Probabilistic Framework for Continuous Time Dynamic Graph Generation (AAAI 2025 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.