Research map / Graph learning / Knowledge and temporal graphs
DyG-Mamba: Continuous State Space Modeling on Dynamic Graphs
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 DyG-Mamba, a timespan-informed continuous state space model for continuous-time dynamic graph link prediction and node classification, using learnable timespan-driven forgetting and input-dependent B/C with spectral norm constraints.
Problem
Existing continuous-time dynamic graph models struggle to capture long-term temporal dependencies efficiently, ignore irregular timespans, and are not robust to noisy events.
Approach
Redefines Mamba's SSM parameters for dynamic graphs: the step size Δt is a monotonically increasing learnable function of irregular timespans (forgetting-curve inspired), A is initialized with negative-real-part eigenvalues, and B and C are input-dependent with spectral norm constraints (review-cycle inspired) for noise robustness.
Key results
- On transductive dynamic link prediction with random negatives (AP), DyG-Mamba achieves the best average rank of 2.42 across 12 datasets, ahead of DyGFormer (2.92 for second place).
- Against DyGFormer at sequence length 2,048, DyG-Mamba is reported as 8.9x faster and uses 77.2% less GPU memory.
- On dynamic node classification, DyG-Mamba reaches the best average rank of 1.50 (vs. 3.50 for DyGFormer) on Wikipedia and Reddit.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use DyG-Mamba instead of DyGFormer | dynamic link prediction · Wikipedia, transductive rnd | AP: 99.03$\pm$0.02 -> 99.06$\pm$0.01 | No clear effect |
| Use DyG-Mamba instead of TGN | dynamic link prediction · MOOC, transductive rnd | AP: 89.15$\pm$1.60 -> 90.17$\pm$0.19 | Helped |
| Use DyG-Mamba instead of TGN | dynamic link prediction · US Legis., transductive rnd | AP: 75.99$\pm$0.58 -> 74.11$\pm$2.32 | Hurt |
| Use DyG-Mamba instead of DyGFormer | dynamic link prediction · Can. Parl., inductive rnd | AP: 87.74$\pm$0.71 -> 96.64$\pm$0.04 | Helped |
| Replace timespan control with input-sample control signals (ablation) | DyG-Mamba · Can. Parl. | AP: 96.90$\pm$0.18 -> 98.37$\pm$0.07 | Helped |
| Remove absolute temporal encoding (ablation) | DyG-Mamba · Can. Parl. | AP: 97.80$\pm$0.43 -> 98.37$\pm$0.07 | Helped |
| Remove timespan control and absolute temporal encoding (ablation) | DyG-Mamba · Can. Parl. | AP: 96.87$\pm$0.18 -> 98.37$\pm$0.07 | Helped |
| Use input- and timespan-independent S4-style parameters (ablation) | DyG-Mamba · Can. Parl. | AP: 96.32$\pm$0.16 -> 98.37$\pm$0.07 | Helped |
| Make B and C timespan-dependent instead of data-dependent, without spectral norm constraints (ablation) | DyG-Mamba · Can. Parl. | AP: 79.24$\pm$0.58 -> 98.37$\pm$0.07 | Helped |
| Replace the proposed Δt function with a linear function (ablation) | DyG-Mamba · Can. Parl. | AP: 94.64$\pm$0.18 -> 98.37$\pm$0.07 | Helped |
| Remove co-occurrence frequency encoding (ablation) | DyG-Mamba · UCI | AP: 93.09$\pm$1.31 -> 96.79$\pm$0.08 | Helped |
| Remove the SSM skip connection (ablation) | DyG-Mamba · UCI | AP: 95.37 $\pm$ 0.06 -> 96.79 $\pm$ 0.08 | Helped |
Surprising findings
- On the US Legis. dataset under transductive random negative sampling, DyG-Mamba (74.11) is below TGN (75.99), and it also trails on several historical/inductive settings such as UN Vote and UCI inductive.
- On Can. Parl., removing the data-dependent B and C drops AP from 98.37 to 79.24, a much larger drop than other ablations.
Limitations
- Only edge addition interactions are considered; node addition/deletion, edge deletion and feature transformations are not handled.
- Evaluated only on relatively small-scale benchmarks, so generalization to larger or more complex real-world scenarios is unclear.
- Generalization to other domains beyond dynamic link prediction and node classification is untested.
Experimental setup
Datasets: Wikipedia Reddit MOOC LastFM Enron Social Evo. UCI Can. Parl. US Legis. UN Trade UN Vote Contact
Benchmarks: Wikipedia Reddit MOOC LastFM Enron Social Evo. UCI Can. Parl. US Legis. UN Trade UN Vote Contact
Metrics: AP AUC-ROC running time GPU memory training time per epoch trainable parameters
Baselines: JODIE DyRep TGN CAWN TGAT EdgeBank GraphMixer TCL
Builds on: Mamba DyGFormer DyGLib S4
Closest papers by meaning
- DG-Mamba: Robust and Efficient Dynamic Graph Structure Learning with Selective State Space Models (AAAI 2025 · similarity 0.91)
- A Deep Probabilistic Framework for Continuous Time Dynamic Graph Generation (AAAI 2025 · similarity 0.89)
- State Space Models on Temporal Graphs: A First-Principles Study (NeurIPS 2024 · similarity 0.88)
- TMetaNet: Topological Meta-Learning Framework for Dynamic Link Prediction (ICML 2025 · similarity 0.87)
- Continuous-Time Graph Representation with Sequential Survival Process (AAAI 2024 · similarity 0.87)
- TGB-Seq Benchmark: Challenging Temporal GNNs with Complex Sequential Dynamics (ICLR 2025 · similarity 0.86)
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.