# State Space Models on Temporal Graphs: A First-Principles Study

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

## Key facts

- Cited by 16 papers in the map (data through 14 Oct 2026).
- Builds on 39 of its 56 references that are in the map.
- First posted on arXiv 3 Jun 2024.

## Builds on (most cited first, 30 of 39)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [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)
- [Mamba: Linear-Time Sequence Modeling with Selective State Spaces](https://mlsanity.com/paper/2312.00752/) (2023)
- [Learning Phrase Representations using RNN Encoder-Decoder for Statistical Machine Translation](https://mlsanity.com/paper/1406.1078/) (2014)
- [Efficiently Modeling Long Sequences with Structured State Spaces](https://mlsanity.com/paper/2111.00396/) (2021)
- [Fast Graph Representation Learning with PyTorch Geometric](https://mlsanity.com/paper/1903.02428/) (2019)
- [Open Graph Benchmark: Datasets for Machine Learning on Graphs](https://mlsanity.com/paper/2005.00687/) (2020)
- [node2vec: Scalable Feature Learning for Networks](https://mlsanity.com/paper/1607.00653/) (2016)
- [DeepWalk: Online Learning of Social Representations](https://mlsanity.com/paper/1403.6652/) (2014)
- [Relational inductive biases, deep learning, and graph networks](https://mlsanity.com/paper/1806.01261/) (2018)
- [Vision Mamba: Efficient Visual Representation Learning with Bidirectional State Space Model](https://mlsanity.com/paper/2401.09417/) (2024)
- [Simplified State Space Layers for Sequence Modeling](https://mlsanity.com/paper/2208.04933/) (2022)
- [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)
- [Hungry Hungry Hippos: Towards Language Modeling with State Space Models](https://mlsanity.com/paper/2212.14052/) (2022)
- [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)
- [On the Parameterization and Initialization of Diagonal State Space Models](https://mlsanity.com/paper/2206.11893/) (2022)
- [Resurrecting Recurrent Neural Networks for Long Sequences](https://mlsanity.com/paper/2303.06349/) (2023)
- [Diagonal State Spaces are as Effective as Structured State Spaces](https://mlsanity.com/paper/2203.14343/) (2022)
- [Representation Learning for Dynamic Graphs: A Survey](https://mlsanity.com/paper/1905.11485/) (2019)
- [Inductive Representation Learning in Temporal Networks via Causal Anonymous Walks](https://mlsanity.com/paper/2101.05974/) (2021)
- [Theoretical Analysis of Self-Training with Deep Networks on Unlabeled Data](https://mlsanity.com/paper/2010.03622/) (2020)
- [ROLAND: Graph Learning Framework for Dynamic Graphs](https://mlsanity.com/paper/2208.07239/) (2022)
- [Graph Mamba: Towards Learning on Graphs with State Space Models](https://mlsanity.com/paper/2402.08678/) (2024)
- [What's Behind the Mask: Understanding Masked Graph Modeling for Graph Autoencoders](https://mlsanity.com/paper/2205.10053/) (2022)
- [Graph Neural Networks for temporal graphs: State of the art, open challenges, and opportunities](https://mlsanity.com/paper/2302.01018/) (2023)

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

- [DyG-Mamba: Continuous State Space Modeling on Dynamic Graphs](https://mlsanity.com/paper/2408.06966/) (2024)
- [DyGMamba: Efficiently Modeling Long-Term Temporal Dependency on Continuous-Time Dynamic Graphs with State Space Models](https://mlsanity.com/paper/2408.04713/) (2024)
- [Message-Passing State-Space Models: Improving Graph Learning with Modern Sequence Modeling](https://mlsanity.com/paper/2505.18728/) (2025)
- [Unifying Text Semantics and Graph Structures for Temporal Text-attributed Graphs with Large Language Models](https://mlsanity.com/paper/2503.14411/) (2025)
- [OdysseyArena: Benchmarking Large Language Models For Long-Horizon, Active and Inductive Interactions](https://mlsanity.com/paper/2602.05843/) (2026)
- [Self-Evolving Agents as Dynamic Graph Transformation: A Survey and New Perspective](https://mlsanity.com/paper/2608.18104/) (2026)
- [A Comparative Study on Dynamic Graph Embedding based on Mamba and Transformers](https://mlsanity.com/paper/2412.11293/) (2024)
- [Exploring Graph Mamba: A Comprehensive Survey on State-Space Models for Graph Learning](https://mlsanity.com/paper/2412.18322/) (2024)
- [Dynamic Graph Condensation](https://mlsanity.com/paper/2506.13099/) (2025)
- [World-as-Graph: Relational World Modeling Through Latent Space Graphs](https://mlsanity.com/paper/2609.38927/) (2026)
- [DyGSSM: Multi-view Dynamic Graph Embeddings with State Space Model Gradient Update](https://mlsanity.com/paper/2505.09017/) (2025)
- [Spatiotemporal graph neural process for reconstruction, extrapolation, and classification of cardiac trajectories](https://mlsanity.com/paper/2509.12953/) (2025)
- [Coden: Efficient Temporal Graph Neural Networks for Continuous Prediction](https://mlsanity.com/paper/2602.12613/) (2026)
- [Learning Long Range Spatio-Temporal Representations over Continuous Time Dynamic Graphs with State Space Models](https://mlsanity.com/paper/2606.04672/) (2026)
- [HoT-SSM:Higher-order Temporal Knowledge Graph Reasoning with State Space Models for Health Care](https://mlsanity.com/paper/2606.05994/) (2026)
- [Physics-Refined Spatiotemporal Forecasting on Open-Boundary Hydrologic Graphs](https://mlsanity.com/paper/2610.01765/) (2026)

## Abstract (arXiv)

Over the past few years, research on deep graph learning has shifted from static graphs to temporal graphs in response to real-world complex systems that exhibit dynamic behaviors. In practice, temporal graphs are formalized as an ordered sequence of static graph snapshots observed at discrete time points. Sequence models such as RNNs or Transformers have long been the predominant backbone networks for modeling such temporal graphs. Yet, despite the promising results, RNNs struggle with long-range dependencies, while transformers are burdened by quadratic computational complexity. Recently, state space models (SSMs), which are framed as discretized representations of an underlying continuous-time linear dynamical system, have garnered substantial attention and achieved breakthrough advancements in independent sequence modeling. In this work, we undertake a principled investigation that extends SSM theory to temporal graphs by integrating structural information into the online approximation objective via the adoption of a Laplacian regularization term. The emergent continuous-time system introduces novel algorithmic challenges, thereby necessitating our development of GraphSSM, a graph state space model for modeling the dynamics of temporal graphs. Extensive experimental results demonstrate the effectiveness of our GraphSSM framework across various temporal graph benchmarks.