State Space Models on Temporal Graphs: A First-Principles Study
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.
Code (1)
Tasks
Graph LearningState Space ModelsSimilar Papers 제목 키워드 기반
Learning Long Range Spatio-Temporal Representations over Continuous Time Dynamic Graphs with State Space Models
Continuous-time dynamic graphs (CTDGs) provide a richer framework to capture fine-grained temporal patterns in evolving relational data. Long-range information propagation is a key challenge while learning representation…
Dynamic Link PredictionNode ClassificationSpatial ReasoningObject Agnostic 3D Lifting in Space and Time
We present a spatio-temporal perspective on category-agnostic 3D lifting of 2D keypoints over a temporal sequence. Our approach differs from existing state-of-the-art methods that are either: (i) object agnostic, but can…
ObjectMessage-Passing State-Space Models: Improving Graph Learning with Modern Sequence Modeling
The recent success of State-Space Models (SSMs) in sequence modeling has motivated their adaptation to graph learning, giving rise to Graph State-Space Models (GSSMs). However, existing GSSMs operate by applying SSM modu…
Computational EfficiencyGraph LearningGraph Property PredictionNode Classification+2Learning and Clustering on Temporal Graphs: Principles, Primitives, and Pooling
This work focuses on the problem of learning on temporal graphs, with particular emphasis on the task of clustering: obtaining coarse-grained representations by aggregating information from nodes, edges, and temporal dyn…
Community DetectionGraph LearningTemporal Event Knowledge Acquisition via Identifying Narratives
Inspired by the double temporality characteristic of narrative texts, we propose a novel approach for acquiring rich temporal "before/after" event knowledge across sentences in narrative stories. The double temporality s…
General ClassificationRelation ClassificationTemporal Relation Classification