Research map / Graph learning / Knowledge and temporal graphs
State Space Models on Temporal Graphs: A First-Principles Study
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.
Extends HiPPO/SSM theory to temporal graphs via a Laplacian-regularized online approximation (GHiPPO) and proposes GraphSSM variants (S4, S5, S6 style) with mixed discretization to handle unobserved graph mutations.
Problem
Modeling discrete-time temporal graphs (snapshot sequences) where RNNs forget long-range context and Transformers scale quadratically; it is unclear how SSM theory applies when graph structure changes between observed snapshots.
Approach
Derives GHiPPO by adding a graph Laplacian smoothness regularizer to the HiPPO online approximation objective, yielding a piecewise-LTI ODE over mutation times; because mutations are unobserved between snapshots, it uses a mixed discretization (GNN diffusion plus Conv1D or interpolation mixing of consecutive snapshot features/representations).
Key results
- GHiPPO-based model (S4 variant) reaches 85.26 Micro-F1 on DBLP-3 and 49.21 Micro-F1 on Reddit, best among compared methods on the four small datasets.
- On large-scale arXiv the method achieves 70.67 Micro-F1 versus 68.27 for the strongest baseline ROLAND; STAR and tNodeEmbed run out of memory there.
- Ablation: applying the mixing module only at the first layer generally improves results; HiPPO initialization is typically the best of the tested A-matrix initializations.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| apply GHiPPO-S4 instead of the strongest baseline | temporal node classification · Reddit and DBLP-10 | Micro-F1: average improvement of 14% | Helped |
| apply GHiPPO-S4 instead of the strongest baseline | temporal node classification · Reddit and DBLP-10 | Macro-F1: 2% | Helped |
| use GHiPPO-S4 rather than ROLAND | temporal node classification · arXiv | Micro-F1: 68.27$_{\pm1.2}$ -> 70.67$_{\pm0.7}$ | Helped |
| use GHiPPO-S4 rather than ROLAND | temporal node classification · arXiv | Macro-F1: 48.01$_{\pm1.3}$ -> 49.97$_{\pm0.5}$ | Helped |
| use GHiPPO rather than SpikeNet | temporal node classification · Tmall | Micro-F1: 66.10$_{\pm0.3}$ -> 66.29$_{\pm0.1}$ | Helped |
| use GHiPPO rather than SpikeNet | temporal node classification · Tmall | Macro-F1: 62.40$_{\pm0.6}$ -> 62.57$_{\pm0.1}$ | Helped |
| replace S4 with S5 (ablation) | GHiPPO · DBLP-3, Brain, Reddit, and DBLP-10 | Micro-F1 | Hurt |
| replace S4 with selective S6 (ablation) | GHiPPO · Reddit and DBLP-10 | Micro-F1 | Hurt |
| use feature mixing in the first layer rather than ordinary ZOH in both layers (ablation) | GHiPPO-S4 · Reddit | Micro-F1: 48.05$_{\pm 2.8}$ -> 49.06$_{\pm 1.9}$ | Helped |
| use representation mixing in the first layer rather than ordinary ZOH in both layers (ablation) | GHiPPO-S4 · DBLP-10 | Micro-F1: 75.62$_{\pm 0.5}$ -> 77.76$_{\pm 0.5}$ | Helped |
| move representation mixing from the first layer to the second layer (ablation) | GHiPPO-S4 · Reddit | Micro-F1: 49.21$_{\pm 0.5}$ -> 47.88$_{\pm 1.8}$ | Hurt |
| move representation mixing from the first layer to the second layer (ablation) | GHiPPO-S4 · DBLP-10 | Micro-F1: 77.76$_{\pm 0.5}$ -> 75.41$_{\pm 0.7}$ | Hurt |
Surprising findings
- Selective (S6-style) variant underperforms the S4 variant on graph sequences, suggesting selectivity may not suit graph data.
- Continuous-time methods HTNE and M2DNE perform poorly on discrete-time snapshot benchmarks, even below static embedding methods on some datasets.
Limitations
- Applicable only to discrete-time temporal graphs with fixed node sets in the main derivation; varying node sets handled only in appendix discussion.
- Unobserved graph mutations between snapshots are approximated heuristically via mixing rather than recovered exactly.
- Only real-valued diagonal state matrices are explored.
Experimental setup
Datasets: DBLP-3 Brain Reddit DBLP-10 arXiv Tmall
Benchmarks: DBLP-3 Brain Reddit DBLP-10 arXiv Tmall
Metrics: Micro-F1 Macro-F1
Baselines: DeepWalk Node2Vec HTNE M2DNE DynamicTriad MPNN STAR tNodeEmbed
Builds on: HiPPO S4 S5 Mamba (S6) ROLAND
Closest papers by meaning
- Deep Temporal Graph Clustering (ICLR 2024 · similarity 0.89)
- Quality Measures for Dynamic Graph Generative Models (ICLR 2025 · similarity 0.88)
- A Deep Probabilistic Framework for Continuous Time Dynamic Graph Generation (AAAI 2025 · similarity 0.88)
- DyG-Mamba: Continuous State Space Modeling on Dynamic Graphs (NeurIPS 2025 · similarity 0.88)
- DG-Mamba: Robust and Efficient Dynamic Graph Structure Learning with Selective State Space Models (AAAI 2025 · similarity 0.88)
- Supra-Laplacian Encoding for Transformer on Dynamic Graphs (NeurIPS 2024 · similarity 0.88)
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.