PaperlayerView exact revision on arXiv

Source-linked AI summary

DiffSTG: Probabilistic Spatio-Temporal Graph Forecasting with Denoising Diffusion Models

Haomin Wen, Youfang Lin, Yutong Xia, Huaiyu Wan, Qingsong Wen, Roger Zimmermann, Yuxuan Liang

arXiv:2301.13629v4cs.LG

TL;DR

Existing deterministic STGNNs capture spatial-temporal correlations but do not model prediction uncertainty, while diffusion forecasting models lack spatial modeling and face efficiency problems on STGs. DiffSTG generalizes diffusion models to spatio-temporal graphs with UGnet and non-autoregressive sampling, combining STG learning with uncertainty measurement and improving practical viability.

  • Problem

    Deterministic STGNNs capture spatial-temporal correlations but fail to model prediction uncertainty, while diffusion-based forecasters cannot capture spatial dependencies and face efficiency problems on STGs.

  • Method

    DiffSTG generalizes denoising diffusion probabilistic models to spatio-temporal graphs, using UGnet to model multi-scale temporal and spatial dependencies and non-autoregressive prediction.

  • Results

    DiffSTG provides probabilistic STG forecasting and accelerates training and inference through non-autoregressive prediction and a sample acceleration strategy.

  • Takeaways & Limitations

    The efficiency improvements make diffusion-based methods for STG forecasting more viable and appealing for practical applications.

  • Takeaways & Limitations

    DiffSTG remains inferior to state-of-the-art deterministic methods for deterministic forecasting, particularly when data samples are insufficient for accurate posterior learning.

Abstract

from arXiv · show

Spatio-temporal graph neural networks (STGNN) have emerged as the dominant model for spatio-temporal graph (STG) forecasting. Despite their success, they fail to model intrinsic uncertainties within STG data, which cripples their practicality in downstream tasks for decision-making. To this end, this paper focuses on probabilistic STG forecasting, which is challenging due to the difficulty in modeling uncertainties and complex ST dependencies. In this study, we present the first attempt to generalize the popular denoising diffusion probabilistic models to STGs, leading to a novel non-autoregressive framework called DiffSTG, along with the first denoising network UGnet for STG in the framework. Our approach combines the spatio-temporal learning capabilities of STGNNs with the uncertainty measurements of diffusion models. Extensive experiments validate that DiffSTG reduces the Continuous Ranked Probability Score (CRPS) by 4%-14%, and Root Mean Squared Error (RMSE) by 2%-7% over existing methods on three real-world datasets.

1 INTRODUCTION

STG forecasting predicts future graph signals from historical observations and graph structure, but deterministic approaches do not represent uncertainty. Diffusion-based time-series models address uncertainty yet fail to capture spatial dependencies and can be inefficient for STGs, motivating DiffSTG.

  • STG forecasting predicts future graph signals from historical observations and graph structure in applications such as traffic, weather, and taxi demand estimation.
  • Deterministic STGNNs model spatial correlations with GNNs and temporal dependencies with TCNs or RNNs, but cannot quantify prediction uncertainty for decision-making.
  • Diffusion probabilistic models generate future samples by gradually transforming noise into plausible predictions conditioned on historical readings.
  • Existing probabilistic time-series models overlook spatial correlations between nodes and face efficiency problems when applied to STGs.
  • DiffSTG generalizes DDPMs to STGs, combining STGNN spatio-temporal learning with diffusion-based uncertainty measurement through UGnet and non-autoregressive prediction.

2 DENOISING DIFFUSION PROBABILISTIC MODELS

DDPMs learn data distributions through a fixed forward noising process and a learnable reverse denoising process. Training teaches a denoising function to remove noise, after which samples are generated by reversing the process from Gaussian noise.

  • DDPMs are latent-variable generative models that learn a tractable distribution pθ(x0) approximating the data distribution q(x0).
  • Forward Process: The forward process is a Markov chain that progressively adds Gaussian noise according to an increasing variance schedule.
  • Forward Process: The fixed approximate posterior q(x1:N|x0) distinguishes diffusion models from latent-variable models with trainable posteriors.
  • Forward Process: The reparameterization x_n = √α_n x_0 + √(1 − α_n) ε allows direct sampling at any noise level instead of stepping through the entire forward chain.
  • Reverse Process: The reverse process recurrently denoises x_N to recover x_0 through learnable Gaussian transitions initialized from N(x_N; 0, I).
  • Training and Sampling: A trainable denoising function determines how much noise to remove at each denoising step and is optimized using the training objective.
  • Training and Sampling: After training, sampling starts from Gaussian noise and reduces the noise scale step by step until reaching the smallest noise level.

3 DIFFSTG FORMULATION

DiffSTG extends DDPMs into conditional probabilistic STG forecasting by using historical signals and graph structure, masking future values, and denoising the combined sequence. Its generalized formulation supports efficient multihorizon prediction and related STG tasks.

  • 3 DIFFSTG FORMULATION: STG forecasting maps historical graph signals and graph structure to future signals, while probabilistic forecasting estimates their future distribution.
  • 3 DIFFSTG FORMULATION: DiffSTG addresses the complementary limitations of deterministic STGNNs and probabilistic time-series models by combining spatio-temporal learning with diffusion uncertainty.
  • 3.1 Conditional Diffusion Model: The conditional diffusion model incorporates historical signals x_h and graph structure G into the reverse process to generate future signals.
  • 3.2 Generalized Conditional Diffusion Model: DiffSTG represents history and future as x_all, masks future time steps, and conditions denoising on the masked sequence and graph structure.
  • 3.2 Generalized Conditional Diffusion Model: The generalized loss unifies reconstruction of history with future estimation and supports prediction, generation, and interpolation within one STG framework.
  • 3.2 Generalized Conditional Diffusion Model: DiffSTG trains by constructing masked signals, corrupting the combined sequence with noise, and optimizing the denoising function under the generalized objective.
  • 3.2 Generalized Conditional Diffusion Model: At inference, the trained denoising function repeatedly samples the combined sequence under masked-history and graph conditions, then extracts the forecast target.
  • 3.2 Generalized Conditional Diffusion Model: Unlike TimeGrad, DiffSTG uses one reverse diffusion process for the full forecasting horizon, while UGnet combines Unet-based temporal modeling with GNN spatial modeling.

4 DIFFSTG IMPLEMENTATION

DiffSTG implements a diffusion-based STG forecasting framework centered on UGnet, which combines temporal modeling with graph-based spatial modeling. Its sampling strategy accelerates reverse diffusion by using a subset of diffusion steps and treating late reverse states as additional samples.

  • UGnet Architecture: UGnet is DiffSTG’s denoising network, combining an Unet-like temporal architecture with GNN-based spatial modeling for STG data.The temporal U-structure captures dependencies at different granularities, while the GNN models spatial correlations.
  • UGnet Architecture: The denoising network receives masked and noisy graph signals, the diffusion noise level, and graph G, then outputs denoised noise.
  • UGnet Architecture: UGnet first concatenates noisy and masked signals temporally, projects them into a higher-dimensional representation, and processes them through spatio-temporal residual blocks.Each block captures temporal and spatial dependencies, with temporal length potentially changing across blocks.
  • Temporal Dependency Modeling: Temporal dependencies are modeled with a 1D gated causal TCN whose sigmoid gate filters useful information into the next layer.
  • Spatial Dependency Modeling: Spatial dependencies are extracted using graph convolution networks, with the implementation adopting the vanilla GCN aggregation form.The normalized adjacency matrix uses the graph adjacency matrix, the identity matrix, and the diagonal degree matrix.
  • 4.2 Sampling Acceleration: Sampling accelerates reverse diffusion by selecting M steps from N and can reduce the required reverse-process sample count from S to S/k using late-step states.A large N improves the Gaussian approximation but makes sequential sampling inefficient; the reduced trajectory addresses this cost.
  • Model Comparison: DiffSTG differs from deterministic STGNNs, unconditional DDPMs, and TimeGrad by incorporating graph conditioning into diffusion-based STG forecasting.

5 EXPERIMENTS

Experiments on three real-world datasets compare DiffSTG with probabilistic and deterministic forecasting baselines, including accuracy, inference speed, ablations, and hyperparameter effects. DiffSTG performs strongly in probabilistic forecasting, accelerates diffusion inference, and benefits from spatial, temporal, and multi-scale components, while retaining a deterministic-performance gap.

  • Experimental Setup: Experiments use PEMS08 traffic-flow data and AIR-BJ and AIR-GZ air-quality data, covering two application domains.PEMS08 contains sensor readings on a road network; AIR-BJ and AIR-GZ contain PM2.5 readings from monitoring stations in Beijing and Guangzhou.
  • Performance Comparison: DiffSTG reduces CRPS by 5.6%, 4.3%, and 14.3% versus the strongest probabilistic baseline on the three datasets.It outperforms all probabilistic baselines and achieves the best performance in both probabilistic and deterministic metrics in Table 2.
  • Performance Comparison: 40× speed-up over TimeGrad is achieved by DiffSTG with M=100 and k=1, while accelerated sampling adds a further 3∼4× speed-up.The speed advantage stems from DiffSTG’s non-autoregressive architecture; increasing k can improve efficiency without performance loss when S is large.
  • Ablation Study: Removing spatial learning, temporal learning, or the Unet-based structure causes substantial performance degradation across evaluation metrics.The Unet-based structure supports capturing spatio-temporal dependencies at different granularities.
  • Hyperparameter Study: Five or ten generated samples are sufficient for good distributions, with improvements becoming marginal beyond 32 samples.For S>32, k=2 has nearly the same performance as k=1 and samples 1.5 times faster.
  • Limitations: DiffSTG remains behind current state-of-the-art STGNNs on deterministic forecasting, despite strong probabilistic performance.The authors attribute this gap to possible inaccuracy of the learned posterior distribution when data samples are insufficient.

6 RELATED WORK

Existing spatio-temporal forecasting methods largely separate deterministic and probabilistic approaches: STGNNs capture spatial and temporal patterns, while probabilistic methods quantify uncertainty but have not fully addressed graph structure.

  • STGNNs combine graph neural networks with temporal components such as TCNs and RNNs to model spatial correlations and temporal features.
  • Most existing spatio-temporal forecasting work focuses on point estimation rather than quantifying prediction uncertainty.
  • Score-based generative models learn input log-density gradients and use them to sample data through Langevin dynamics across noise levels.
  • Probabilistic time-series forecasting forms a separate stream from deterministic methods and increasingly uses diffusion models for stochastic predictions.

7 CONCLUSION AND FUTURE WORK

DiffSTG is presented as a probabilistic framework for spatio-temporal graph forecasting, pairing diffusion-based uncertainty modeling with STGNN-style spatial and temporal learning. The paper also emphasizes efficiency while identifying stronger graph networks and additional tasks as future directions.

  • Conclusion: DiffSTG generalizes DDPMs to spatio-temporal graphs and combines STGNN learning capabilities with diffusion-model uncertainty measurements.
  • Conclusion: UGnet uses an Unet architecture for multi-scale temporal dependencies and a GNN for spatial correlations in STG data.
  • Conclusion: A non-autoregressive architecture and sample acceleration strategy improve diffusion-based training and inference efficiency for STG forecasting.
  • Future Work: Future work includes replacing vanilla GCN with stronger graph neural networks and applying DiffSTG to tasks such as spatio-temporal graph imputation.

A.1 Details of DDPM

DDPMs use fixed forward noising and learnable reverse denoising processes, training their parameters through an ELBO-based negative log-likelihood objective.

  • DDPMs consist of a fixed Gaussian forward process and a learnable Gaussian reverse process.
  • The model parameters are learned by minimizing negative log-likelihood through the variational lower bound, or ELBO.
  • The ELBO can be decomposed into terms associated with the Markov-chain structure.
  • The forward-process posterior conditioned on the original sample is tractable, enabling closed-form treatment of the corresponding Gaussian KL-divergence terms.
  • The denoising loss for intermediate diffusion steps can be written in closed form and simplified by removing a coefficient.

A.2 Details of UGnet

UGnet is an Unet-like denoising network designed for STG data, combining multi-scale temporal processing with graph convolution for spatial dependence modeling.

  • Network Architecture: UGnet takes historical and masked signals together with the diffusion step and graph structure, then outputs denoised noise.
  • Temporal Dependence Modeling: UGnet gradually reduces and restores temporal resolution through down- and up-residual blocks to capture dependencies at multiple temporal granularities.This design also supports scaling to large spatio-temporal graphs.
  • Network Architecture: The network uses a Unet-like temporal structure conditioned on the noise level and graph structure.
  • Temporal Dependence Modeling: A temporal convolutional network models temporal dependence using gated causal convolutions and residual connections.
  • Temporal Dependence Modeling: The sigmoid-transformed gate filters useful temporal features before they reach the next layer.
  • Spatial Dependence Modeling: A graph convolution network extracts spatial features from node representations produced by the temporal module.
  • Spatial Dependence Modeling: The implementation uses the popular vanilla GCN aggregation rather than developing a specialized aggregation function.

A.3 Additional Prediction Examples

Additional AIR-BJ examples compare DiffSTG and TimeGrad across stations with different spatial relationships. DiffSTG generally produces reasonable probabilistic forecasts and similar estimated distributions for nearby stations.

  • The y-axis scales vary by station, so forecast distributions should be compared with station-specific scales in mind.
  • The comparison evaluates two station groups: geographically distant nodes 0, 2, 17, and 20, and nearby nodes 7, 8, 9, and 18.The station locations are shown in Figure 9, while the forecasting comparison appears in Figure 10.
  • DiffSTG produces reasonable probabilistic forecasts for most selected AIR-BJ stations, whereas TimeGrad fails to capture the data distribution.
  • DiffSTG tends to estimate similar distributions for nearby stations, consistent with the strong correlation between a station’s air quality and that of its neighbors.
  • The examples illustrate DiffSTG’s ability to learn spatial and temporal dependencies in spatio-temporal graphs.
Loading 2301.13629v4…