PaperlayerView exact revision on arXiv

Source-linked AI summary

Towards Spatio-Temporal Aware Traffic Time Series Forecasting--Full Version

Razvan-Gabriel Cirstea, Bin Yang, Chenjuan Guo, Tung Kieu, Shirui Pan

arXiv:2203.15737v3cs.LG

TL;DR

Traffic forecasting is difficult because patterns differ across locations and change over time, while many models share parameters across both dimensions. The paper generates location-specific and time-varying parameters from encoded time series and combines this with linear-complexity window attention. Across four datasets, the proposed spatio-temporal aware attention outperforms state-of-the-art methods in accuracy and efficiency.

  • Problem

    Traffic forecasting models often remain spatio-temporal agnostic despite distinct location patterns and temporal changes in traffic series.

  • Method

    The framework encodes recent sensor time series into stochastic variables that generate location-specific and time-varying parameters, using window attention to reduce complexity from O(H^2) to O(H).

  • Results

    The proposed spatio-temporal aware method achieves the best accuracy on 10 out of 12 metrics across four datasets and significantly outperforms baselines in long-term forecasting.

  • Takeaways & Limitations

    Spatio-temporal parameter generation can turn agnostic forecasting models into data-driven aware models while maintaining competitive efficiency.

Abstract

from arXiv · show

Traffic time series forecasting is challenging due to complex spatio-temporal dynamics time series from different locations often have distinct patterns; and for the same time series, patterns may vary across time, where, for example, there exist certain periods across a day showing stronger temporal correlations. Although recent forecasting models, in particular deep learning based models, show promising results, they suffer from being spatio-temporal agnostic. Such spatio-temporal agnostic models employ a shared parameter space irrespective of the time series locations and the time periods and they assume that the temporal patterns are similar across locations and do not evolve across time, which may not always hold, thus leading to sub-optimal results. In this work, we propose a framework that aims at turning spatio-temporal agnostic models to spatio-temporal aware models. To do so, we encode time series from different locations into stochastic variables, from which we generate location-specific and time-varying model parameters to better capture the spatio-temporal dynamics. We show how to integrate the framework with canonical attentions to enable spatio-temporal aware attentions. Next, to compensate for the additional overhead introduced by the spatio-temporal aware model parameter generation process, we propose a novel window attention scheme, which helps reduce the complexity from quadratic to linear, making spatio-temporal aware attentions also have competitive efficiency. We show strong empirical evidence on four traffic time series datasets, where the proposed spatio-temporal aware attentions outperform state-of-the-art methods in term of accuracy and efficiency. This is an extended version of "Towards Spatio-Temporal Aware Traffic Time Series Forecasting", to appear in ICDE 2022 [1], including additional experimental results.

I. INTRODUCTION

Traffic forecasting must account for distinct patterns across sensor locations and changing patterns across time. The paper proposes data-driven spatio-temporal awareness with generated parameters and efficient window attention.

  • Traffic forecasting supports emergency management, equipment diagnosis, and route planning, but complex spatio-temporal dynamics make accurate prediction challenging.
  • Sensors in different locations exhibit distinct traffic patterns, motivating location-specific model parameters.Sensors on one street show weekday morning and afternoon peaks, whereas sensors on another street lack an afternoon spike.
  • Traffic patterns also vary across time, motivating models that adjust parameters for weekdays, weekends, accidents, or road closures.
  • The proposed framework encodes each location’s recent time series into a stochastic variable and generates location-specific, time-varying parameters for multiple model types.It is presented as data driven and avoids requiring coordinates or prior knowledge about peak and off-peak periods.
  • Window attention reduces attention complexity from O(H^2) to O(H) by using a small constant number of proxies per temporal window.This design addresses the quadratic overhead of canonical attention while retaining competitive efficiency for spatio-temporal aware attention.
  • II. RELATED WORK: Most related deep-learning models are spatio-temporal agnostic because they share parameters across locations and time periods, assuming similar and stable patterns.The reviewed literature categorizes models by spatial and temporal awareness, with many studies occupying the spatio-temporal agnostic category.

III. PRELIMINARIES

The preliminaries formulate multivariate traffic forecasting from multiple sensors and describe canonical self-attention as a shared-parameter baseline. They then motivate generated location- and time-specific projections to enable spatio-temporal awareness without a parameter explosion.

  • The input is X ∈ R^N×T×F, representing F attributes observed across T timestamps for N sensors.x^(i) denotes one sensor’s time series, while x_t denotes attributes from all sensors at timestamp t.
  • Forecasting uses the past H timestamps from all sensors to predict their attributes over the next U timestamps.
  • B. Spatio-temporal Agnostic Attention based Forecasting: Stacked attention layers feed a predictor that produces future forecasts, while the same projection parameters remain shared across sensors and time.
  • B. Spatio-temporal Agnostic Attention based Forecasting: Canonical self-attention projects each sensor’s input into query, key, and value matrices, then combines values using pairwise timestamp attention scores.
  • Using separate projection matrices for every sensor and time period would create excessive parameters, computation, memory use, convergence time, and over-fitting risk.
  • An encoder-decoder network instead generates location-specific and time-varying projection matrices, enabling spatio-temporal aware attention without parameter explosion.

IV. METHODOLOGY

The method converts spatio-temporal agnostic models into aware models by generating location-specific and time-varying parameters from stochastic latent variables derived from traffic series. It is data-driven, model-agnostic, and supports attention and recurrent architectures.

  • A. Spatio-Temporal Aware Modeling: The framework generates location-specific and time-varying model parameters to transform spatio-temporal agnostic models into aware models.It is designed as a data-driven and model-agnostic mechanism.
  • 1) Design Considerations:: Only the time series themselves are used, avoiding additional location or time features such as sensor coordinates, points of interest, or known peak-hour schedules.
  • 1) Design Considerations:: The method can generate parameters for different model types, and the experiments apply it to attentions and RNNs to support its model-agnostic design.For attention, the generated parameters are location-specific and time-varying projection matrices.
  • 1) Design Considerations:: Each location and time period receives a stochastic latent variable Θ_t^(i), formed by summing a spatial-aware variable and a temporal adaption variable.The spatial variable captures prominent location-specific patterns, while the temporal variable captures deviations that change over time.
  • 1) Design Considerations:: Stochastic variables are used because the authors state that they generalize better and have stronger representational power than deterministic variables.The latent variables are assumed to follow multivariate Gaussian distributions, enabling analytical KL divergence and reparameterization-based gradient computation.
  • 1) Design Considerations:: The spatial-aware variable represents general patterns for each time series, while the temporal adaption variable captures changes relative to those patterns at particular times.The temporal variable is conditioned on recent observations through a variational encoder.

3) Decoding to Spatio-Temporal Aware Model Parameters:

A decoder maps sampled stochastic latent variables to model parameters, such as attention projection matrices, thereby producing spatio-temporal aware attention. The approach also reduces parameter growth relative to directly learning separate matrices for every sensor.

  • 3) Decoding to Spatio-Temporal Aware Model Parameters:: The decoder maps sampled stochastic latent variables to model parameters for a chosen forecasting architecture, including attention projection matrices.The reparameterization trick enables end-to-end training through the stochastic variables.
  • 3) Decoding to Spatio-Temporal Aware Model Parameters:: Using location-specific and time-varying projection matrices turns spatio-temporal agnostic attention into spatio-temporal aware attention.
  • 3) Decoding to Spatio-Temporal Aware Model Parameters:: Directly learning separate projection matrices for every sensor requires O(N × d^2) parameters and can increase memory use, over-fitting, and poor scalability.
  • 3) Decoding to Spatio-Temporal Aware Model Parameters:: Window attention divides the input into windows and replaces the full Query with a small number of proxies for each window.In the example, H = 12 is split into W = 2 windows, each using p = 2 proxies.
  • 3) Decoding to Spatio-Temporal Aware Model Parameters:: The shared decoder instead uses O(N × k) parameters for spatial latent means and covariances plus O(k×m1+m1×m2+m2×d^2) decoder parameters for a two-layer MLP.The decoder is shared across sensors, decoupling sensor count from the decoder parameter count.

B. Efficient Spatio-Temporal Aware Attention

The proposed Window Attention reduces attention complexity from quadratic to linear while retaining spatio-temporal awareness through local proxies and cross-window information flow.

  • The method partitions an input of length H into W = H/S temporal windows and computes attention scores independently within each window.Each timestamp compares with the small set of proxies rather than all timestamps in the input.
  • Each window uses p learnable proxies as Query representations for its local temporal patterns, replacing the canonical Query tensor.For an example with H = 12, the method uses W = 2 windows, S = 6, and p = 2 proxies per window.
  • O(H) complexity replaces canonical O(H^2) attention by using a constant number of proxies across W windows of size S.The resulting complexity is O(W · p · S), which becomes O(H) when p is constant and W · S = H.
  • Proxy aggregation combines the p proxies into one shared window representation, shrinking the representation by a factor of p for subsequent layers.A weighting network assigns bounded proxy weights before weighted proxies are summed within each window.
  • Because local windows reduce the receptive field from H to S, outputs are fused into the next window’s proxies to preserve information flow across windows and long-term dependencies.The cross-window connection compensates for the inability of isolated windows to directly capture relationships between windows.

C. Sensor Correlation Attention

Sensor Correlation Attention models interactions between sensors using normalized embedded similarities over aggregated window representations, with sensor-specific transformations generated by the proposed parameter mechanism.

  • The attention output summarizes each window into a fixed representation for every sensor before modeling sensor correlations.The resulting representation has shape N × d, where N is the number of sensors.
  • A normalized embedded Gaussian function measures how a source sensor i relates to a target sensor j.The numerator computes transformed-sensor similarity, while the denominator normalizes scores for each target sensor.
  • Distinct transformation matrices can be generated for each sensor because one shared pair of transformations may not describe all sensor interactions.The model reuses its location-specific parameter-generation process for these sensor transformations.

D. Full Model

The full model stacks multiple Spatio-Temporal Aware Window Attention layers with location-specific and time-varying projections, while using shortcuts and a predictor to produce forecasts efficiently.

  • The full architecture consists of multiple ST-WA layers, each using location-specific and time-varying projection matrices and its own learnable proxy tensor.The output of each layer is formed by concatenating the outputs of its windows.
  • Gradient shortcuts connect each layer output directly to the predictor, with one-layer networks aligning the differing output dimensions.These skip connections address gradient propagation while layer representations decrease exponentially in size.
  • A two-layer neural-network predictor maps the combined hidden representation to future predictions.The predictor uses ReLU together with learnable weight matrices.
  • In the illustrated three-layer example, an input of H = 12 is reduced by successive window sizes, beginning with S1 = 3 and producing a second-layer input size of 4.The supplied example then specifies S2 = 2 for the next layer.
  • Stacked Window Attention retains linear complexity as layer inputs shrink through successive window operations.The complexity analysis expresses the final-layer input using the minimum window size across layers and concludes that the stacked complexity remains linear.

E. Loss Function and Optimization

The model is trained end-to-end with a forecasting loss and a regularizer that encourages the stochastic latent variables to remain close to a multivariate Gaussian prior.

  • End-to-end optimization trains the proposed spatio-temporal-aware parameter generation using the loss defined in Equation 20.The objective jointly concerns prediction quality and regularization of the latent-variable distribution.
  • The prediction term measures discrepancies between future predictions and ground-truth values, using Huber loss in the experiments because it is less sensitive to outliers.The compared sequences span the forecast horizon from t+1 through t+U.
  • A regularization term encourages the learned posterior of the stochastic latent variable to approach the prior N(0, I).The coefficient α controls the regularizer’s contribution, and the paper studies its impact empirically.
  • Unlike direct parameter optimization, the framework learns decoder and encoder parameters plus location-specific variables that generate the model parameters from a stochastic latent variable.The latent variable combines location-specific stochastic information with temporal adaptation returned by the encoder.

A. Experimental Setup

The experiments use four public PEMS traffic-flow datasets, standard accuracy and efficiency metrics, and multiple forecasting horizons to compare ST-WA with established baselines.

  • Datasets: Four public PEMS datasets provide traffic-flow series sampled every 5 minutes with one average-flow attribute.The data contain no personally identifiable information.
  • Forecasting Settings: Forecasting uses H = 12 and U = 12 by default, with additional settings for longer histories and a six-hour horizon.The study evaluates H = 36, 120, and H = 72 with U = 72.
  • Baselines: Baselines cover recurrent, convolutional, graph-convolutional, attention-based, spatial-aware, temporal-aware, and window-attention architectures.The comparison includes DCRNN, STGCN, STG2Seq, GWN, STSGCN, ASTGNN, LongFormer, STFGNN, EnhanceNet, AGCRN, and meta-LSTM.
  • Baselines: ST-MetaNet is excluded because it requires points-of-interest information unavailable in the datasets.Other baselines do not rely on POI information.
  • Evaluation Metrics: The evaluation reports MAE, RMSE, MAPE, runtime, and memory usage to assess accuracy and efficiency.

B. Experimental Results

Across four datasets and multiple forecasting settings, ST-WA generally improves accuracy while window attention and its design components provide efficiency and robustness benefits.

  • Overall Accuracy: ST-WA achieves the best accuracy on 10 out of 12 metrics across four datasets.Spatial-aware methods outperform most spatio-temporal-agnostic baselines, while meta-LSTM performs worst among the compared methods.
  • Long-Horizon Forecasting: ST-WA significantly outperforms AGCRN, EnhanceNet, and STFGNN when H = 72 and U = 72.EnhanceNet and STFGNN run out of memory for large sensor networks such as PEMS07 with N = 883, whereas ST-WA still works.
  • Model-Agnostic ST-Aware Model Parameter Generation: The parameter-generation framework improves both GRU and Transformer ATT models, with spatial-aware variants improving accuracy and spatio-temporal-aware variants improving it further.This supports applying the proposal to different forecasting-model types.
  • Ablation Study: On PEMS04, ST-WA has the highest accuracy among ablations, while window attention reduces cost versus canonical self-attention.WA-1 is more than 3x faster and requires 5x less memory than SA; multilayer WA improves accuracy over WA-1.
  • Impact of Long Historical Window H: Longer historical windows improve ST-WA, whereas other baselines improve little or sometimes lose accuracy.The result suggests stronger long-term dependency modeling by ST-WA.
  • Impact of Stochastic Latent Variables Size k: Latent size k = 4 reduces performance through insufficient representation, while k = 32 also drops performance because of over-fitting.The tested sizes are k ∈ {4, 8, 16, 32}.

C. Visualization of Learned Stochastic Variables

Visualization analyses indicate that learned stochastic variables distinguish location-specific traffic patterns and time-window-specific dynamics.

  • Temporal Variation: Projection matrices generated for different time windows spread across the t-SNE space, with clusters associated with upward and downward trends.This indicates that different projection matrices are used for different temporal patterns.
  • Location Specificity: Location-specific latent variables form separated t-SNE clusters, and sensors on the same road tend to share a cluster.Physically close sensors on opposite-direction roads can nevertheless have distant latent representations.
  • Conclusion and Outlook: The conclusion identifies Gaussian latent-variable learning as a limitation and suggests normalizing flows for non-Gaussian stochastic variables.The authors also identify parallelism as future work.
Loading 2203.15737v3…