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

• URL: http://arxiv.org/abs/2406.00943v2
• Date: Tue, 29 Oct 2024 11:32:15 GMT
• Title: State Space Models on Temporal Graphs: A First-Principles Study
• Authors: Jintang Li, Ruofan Wu, Xinzhou Jin, Boqun Ma, Liang Chen, Zibin Zheng,
• Abstract summary: Research on deep graph learning has shifted from static graphs to temporal graphs in response to real-world complex systems that exhibit dynamic behaviors. Sequence models such as RNNs or Transformers have long been the predominant backbone networks for modeling such temporal graphs. We develop GraphSSM, a graph state space model for modeling the dynamics of temporal graphs.
• Score: 30.531930200222423
• License:
• Abstract: 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.

Related papers

• DyG-Mamba: Continuous State Space Modeling on Dynamic Graphs [59.434893231950205]
  Dynamic graph learning aims to uncover evolutionary laws in real-world systems. We propose DyG-Mamba, a new continuous state space model for dynamic graph learning. We show that DyG-Mamba achieves state-of-the-art performance on most datasets.
  arXiv  Detail & Related papers  (2024-08-13T15:21:46Z)
• On The Temporal Domain of Differential Equation Inspired Graph Neural Networks [14.779420473274737]
  We show that our model, called TDE-GNN, can capture a wide range of temporal dynamics that go beyond typical first or second-order methods. We demonstrate the benefit of learning the temporal dependencies using our method rather than using pre-defined temporal dynamics on several graph benchmarks.
  arXiv  Detail & Related papers  (2024-01-20T01:12:57Z)
• TimeGraphs: Graph-based Temporal Reasoning [64.18083371645956]
  TimeGraphs is a novel approach that characterizes dynamic interactions as a hierarchical temporal graph. Our approach models the interactions using a compact graph-based representation, enabling adaptive reasoning across diverse time scales. We evaluate TimeGraphs on multiple datasets with complex, dynamic agent interactions, including a football simulator, the Resistance game, and the MOMA human activity dataset.
  arXiv  Detail & Related papers  (2024-01-06T06:26:49Z)
• Backbone-based Dynamic Graph Spatio-Temporal Network for Epidemic Forecasting [3.382729969842304]
  Accurate epidemic forecasting is a critical task in controlling disease transmission. Many deep learning-based models focus only on static or dynamic graphs when constructing spatial information. We propose a novel model called Backbone-based Dynamic Graph Spatio-Temporal Network (BDGSTN)
  arXiv  Detail & Related papers  (2023-12-01T10:34:03Z)
• Dynamic Causal Explanation Based Diffusion-Variational Graph Neural Network for Spatio-temporal Forecasting [60.03169701753824]
  We propose a novel Dynamic Diffusion-al Graph Neural Network (DVGNN) fortemporal forecasting. The proposed DVGNN model outperforms state-of-the-art approaches and achieves outstanding Root Mean Squared Error result.
  arXiv  Detail & Related papers  (2023-05-16T11:38:19Z)
• Dynamic Graph Representation Learning via Edge Temporal States Modeling and Structure-reinforced Transformer [5.093187534912688]
  We introduce the Recurrent Structure-reinforced Graph Transformer (RSGT), a novel framework for dynamic graph representation learning. RSGT captures temporal node representations encoding both graph topology and evolving dynamics through a recurrent learning paradigm. We show RSGT's superior performance in discrete dynamic graph representation learning, consistently outperforming existing methods in dynamic link prediction tasks.
  arXiv  Detail & Related papers  (2023-04-20T04:12:50Z)
• Space-Time Graph Neural Networks with Stochastic Graph Perturbations [100.31591011966603]
  Space-time graph neural networks (ST-GNNs) learn efficient graph representations of time-varying data. In this paper we revisit the properties of ST-GNNs and prove that they are stable to graph stabilitys. Our analysis suggests that ST-GNNs are suitable for transfer learning on time-varying graphs.
  arXiv  Detail & Related papers  (2022-10-28T16:59:51Z)
• Continuous Temporal Graph Networks for Event-Based Graph Data [41.786721257905555]
  We propose Continuous Temporal Graph Networks (CTGNs) to capture the continuous dynamics of temporal graph data. Key idea is to use neural ordinary differential equations (ODE) to characterize the continuous dynamics of node representations over dynamic graphs. Experiment results on both transductive and inductive tasks demonstrate the effectiveness of our proposed approach.
  arXiv  Detail & Related papers  (2022-05-31T16:17:02Z)
• Multivariate Time Series Forecasting with Dynamic Graph Neural ODEs [65.18780403244178]
  We propose a continuous model to forecast Multivariate Time series with dynamic Graph neural Ordinary Differential Equations (MTGODE) Specifically, we first abstract multivariate time series into dynamic graphs with time-evolving node features and unknown graph structures. Then, we design and solve a neural ODE to complement missing graph topologies and unify both spatial and temporal message passing.
  arXiv  Detail & Related papers  (2022-02-17T02:17:31Z)
• Efficient Dynamic Graph Representation Learning at Scale [66.62859857734104]
  We propose Efficient Dynamic Graph lEarning (EDGE), which selectively expresses certain temporal dependency via training loss to improve the parallelism in computations. We show that EDGE can scale to dynamic graphs with millions of nodes and hundreds of millions of temporal events and achieve new state-of-the-art (SOTA) performance.
  arXiv  Detail & Related papers  (2021-12-14T22:24:53Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.