PaperlayerView exact revision on arXiv

Source-linked AI summary

Diffusion Convolutional Recurrent Neural Network: Data-Driven Traffic Forecasting

Yaguang Li, Rose Yu, Cyrus Shahabi, Yan Liu

arXiv:1707.01926v3cs.LGstat.ML

TL;DR

Traffic forecasting must account for complex, directional road-network dependencies and changing temporal dynamics. DCRNN models traffic flow as diffusion on a directed graph and combines it with recurrent sequence-to-sequence forecasting and scheduled sampling. On two real-world traffic datasets, the authors report significantly better predictions than baselines.

  • Problem

    Traffic forecasting must handle complex spatial correlations and changing temporal dynamics that make long-term prediction difficult.

    Source: §1 · p. 1

  • Method

    DCRNN models traffic flow as diffusion on a directed graph and combines diffusion convolution with recurrent sequence-to-sequence learning and scheduled sampling.

    Source: §1 · p. 2, §2.3 · p. 3

  • Results

    DCRNN achieved the best performance across all reported metrics and forecasting horizons on both datasets.

    Source: §4.2 · p. 6

  • Takeaways & Limitations

    The authors state that DCRNN is readily applicable to spatiotemporal forecasting tasks beyond transportation.

    Source: §1 · p. 2

    METR-LA was treated as the default dataset for later experiments because it is more challenging than PEMS-BAY.

    Source: §4.2 · p. 6

Abstract

from arXiv · show

Spatiotemporal forecasting has various applications in neuroscience, climate and transportation domain. Traffic forecasting is one canonical example of such learning task. The task is challenging due to (1) complex spatial dependency on road networks, (2) non-linear temporal dynamics with changing road conditions and (3) inherent difficulty of long-term forecasting. To address these challenges, we propose to model the traffic flow as a diffusion process on a directed graph and introduce Diffusion Convolutional Recurrent Neural Network (DCRNN), a deep learning framework for traffic forecasting that incorporates both spatial and temporal dependency in the traffic flow. Specifically, DCRNN captures the spatial dependency using bidirectional random walks on the graph, and the temporal dependency using the encoder-decoder architecture with scheduled sampling. We evaluate the framework on two real-world large scale road network traffic datasets and observe consistent improvement of 12% - 15% over state-of-the-art baselines.

1 INTRODUCTION

Traffic forecasting predicts future sensor speeds from historical observations and road networks, but traffic has complex spatial and temporal dependencies. DCRNN models these dependencies with diffusion on a directed graph and a sequence-to-sequence framework, and the authors report improvement over state-of-the-art baselines.

1 INTRODUCTION

  • Traffic forecasting predicts future traffic speeds from historic sensor speeds and the underlying road network.Source: §1 · p. 1
  • Traffic forecasting is difficult because road-network correlations are non-Euclidean and directional, while changing conditions make long-term temporal patterns hard to predict.Nearby roads can behave differently, and future speed is influenced more by downstream than upstream traffic.Source: §1 · p. 1, Figure 1 · p. 1
  • Earlier deep-learning methods omitted spatial structure, used Euclidean CNNs, or applied graph convolution only to undirected graphs.Traditional time-series models also rely on stationarity, an assumption often violated by traffic data.Source: §1 · pp. 1–2
  • DCRNN combines diffusion convolution, sequence-to-sequence learning, and scheduled sampling, and outperforms state-of-the-art baselines on two real-world datasets.The paper describes the improvement as significant and consistent.Source: §1 · p. 2

2 METHODOLOGY

The methodology represents traffic as graph signals on a weighted directed sensor network, modeling spatial dependencies with diffusion convolution and temporal dependencies with recurrent sequence-to-sequence forecasting. Bidirectional walks and scheduled sampling support the model’s spatial and multi-step temporal modeling.

2.1 TRAFFIC FORECASTING PROBLEM

  • Traffic forecasting maps T′ historical graph signals from a weighted directed sensor network to T future signals.The graph’s weighted adjacency matrix represents sensor proximity, for example through road-network distance.Source: §2.1 · p. 2

2.2 SPATIAL DEPENDENCY MODELING

  • A random walk with restart models traffic as diffusion; its stationary distribution combines information from infinitely many graph walks.Each stationary-distribution row represents the likelihood of diffusion from a sensor and its proximity profile.Source: §2.2 · p. 2
  • Diffusion convolution uses trainable weights over finite K-step walks in both directions to capture upstream and downstream influence.For sparse graphs, recursive sparse-dense multiplication computes the convolution in O(K|E|) time.Source: §2.2 · pp. 2–3
  • On undirected graphs, spectral graph convolution is equivalent to diffusion convolution up to a similarity transformation.The paper presents spectral graph convolution, including ChebNet, as a special case of diffusion convolution on undirected graphs.Source: §2.2 · p. 3

2.3 TEMPORAL DYNAMICS MODELING

  • The Diffusion Convolutional Gated Recurrent Unit (DCGRU) replaces GRU matrix multiplications with diffusion convolution to model temporal dependencies.Its recurrent gates use the diffusion-convolution operation.Source: §2.3 · p. 3
  • For multi-step forecasting, a DCGRU encoder’s final states initialize a DCGRU decoder, while scheduled sampling gradually shifts decoder inputs from ground truth to predictions.The ground-truth input probability decreases toward zero during training to reduce the discrepancy with testing, when the decoder receives its own predictions.Source: §2.3 · pp. 3–4, Figure 2 · p. 4

3 RELATED WORK

Prior traffic-forecasting approaches include time-series, recurrent, grid-based convolutional, and graph-convolutional methods. DCRNN uses a weighted directed graph and bidirectional walks within sequence-to-sequence forecasting, and the reported comparison favors it across forecasting horizons.

3 RELATED WORK

  • Earlier traffic forecasters include queuing and simulation, time-series, recurrent, and grid-based CNN approaches.Grid-based CNNs convert road networks to regular two-dimensional grids.Source: §3 · p. 4
  • Spectral graph convolutions generally require undirected graphs, while prior graph-convolution models cited here do not address temporal dynamics (Defferrard et al., 2016; Atwood & Towsley, 2016; Hechtlinger et al., 2017).DCRNN instead models a weighted directed sensor graph and combines bidirectional walks with sequence-to-sequence learning and scheduled sampling.Source: §3 · pp. 4–5
  • DCRNN achieves the best performance on all three metrics at every forecasting horizon, with its advantage increasing at longer horizons.Table 1 compares approaches for traffic speed forecasting.Source: Table 1 · p. 5

4 EXPERIMENTS

DCRNN achieves the best performance across all reported metrics and forecasting horizons on both datasets. The experiments examine its settings, spatial and temporal modeling, and learned filters and predictions.

4 EXPERIMENTS

  • The evaluation uses METR-LA with 207 sensors over four months and PEMS-BAY with 325 sensors over six months, using five-minute readings and a 70/10/20 train/validation/test split.Sensor graphs use pairwise road-network distances and a thresholded Gaussian kernel.Source: §4 · p. 5

4.1 EXPERIMENTAL SETTINGS

  • With roughly equal parameter counts, removing diffusion convolution raises validation error, while bidirectional random walks achieve the lowest validation error.The baselines include statistical, linear, and neural approaches; neural models are trained with Adam and validation-selected hyperparameters.Source: §4.1 · pp. 5–6, Figure 3 · p. 6, §4.3 · p. 7

4.2 TRAFFIC FORECASTING PERFORMANCE COMPARISON

  • DCRNN achieves the best performance on all three metrics across all forecasting horizons on both datasets.The metrics are MAE, MAPE, and RMSE; the comparison covers 15-minute, 30-minute, and 1-hour forecasts.Source: §4.2 · p. 6

4.3 EFFECT OF SPATIAL DEPENDENCY MODELING

  • On METR-LA, DCRNN consistently outperforms GCRNN, which uses an undirected graph and ChebNet convolution.The authors attribute the advantage to directed graphs better capturing asymmetric correlations between sensors.Source: Table 2 · p. 7, §4.3 · p. 7

4.4 EFFECT OF TEMPORAL DEPENDENCY MODELING

  • Across forecasting horizons, sequence-to-sequence DCRNN with scheduled sampling achieves the lowest MAE, with its advantage growing at longer horizons.The authors report that scheduled sampling trains the model to handle its own prediction mistakes, reducing error propagation in multi-step forecasting.Source: Figure 5 · p. 7, §4.4 · p. 8

4.3 EFFECT OF SPATIAL DEPENDENCY MODELING

  • Increasing K broadens the filter's spatial receptive field but increases learning complexity; validation error first decreases, then rises, with similar behavior for unit count.K corresponds to receptive-field width, and the number of units corresponds to the number of filters.Source: Figure 4 · p. 6, §4.3 · p. 7

4.5 MODEL INTERPRETATION

  • On METR-LA with K = 3, learned filter weights are localized around their center nodes and diffuse along road-network distances.Figure 7 marks each center with a star and represents weights with colors.Source: Figure 7 · p. 8, §4.5 · p. 8
  • For one-hour-ahead forecasts, DCRNN produces smooth predictions amid small oscillations and more accurately predicts peak-hour starts and ends than FC-LSTM.The authors connect its peak-hour predictions to using speed changes from neighboring sensors.Source: Figure 6 · p. 7, §4.5 · p. 8

5 CONCLUSION

The conclusion presents DCRNN as a model of traffic prediction that captures spatial and temporal dependencies, and reports better predictions than baselines on two large-scale real-world traffic datasets.

5 CONCLUSION

  • DCRNN models spatial dependency with bidirectional graph random walks and temporal dynamics with recurrent neural networks.The approach also integrates an encoder-decoder architecture and scheduled sampling for long-term forecasting.Source: §5 · p. 8
  • On two large-scale real-world traffic datasets, DCRNN obtained significantly better prediction than baselines.Source: §5 · p. 8
  • Future work will investigate applying DCRNN to other spatiotemporal forecasting tasks and modeling dependencies on evolving graph structures.The conclusion gives the K nearest neighbor graph for moving objects as an example of an evolving graph.Source: §5 · p. 8

A NOTATION

B EFFICIENT CALCULATION OF EQUATION 2

The section analyzes the computational cost of the diffusion-convolution calculation, using sparsity to express its complexity in terms of graph edges and walk length.

B EFFICIENT CALCULATION OF EQUATION 2

C RELATION WITH SPECTRAL GRAPH CONVOLUTION

The paper relates diffusion convolution to spectral graph convolution and contrasts DCRNN with other approaches to spatial modeling and traffic forecasting.

C RELATION WITH SPECTRAL GRAPH CONVOLUTION

  • ChebNet parameterizes its filter as a K-order polynomial of the normalized graph Laplacian and evaluates it using Chebyshev polynomial bases.Source: C RELATION WITH SPECTRAL GRAPH… · p. 11
  • Under the stated assumptions, the output of ChebNet convolution is similar to diffusion convolution up to a constant scaling factor.The assumptions are an undirected graph, λmax = 2, and DI = DO = D.Source: C RELATION WITH SPECTRAL GRAPH… · p. 11

D MORE RELATED WORK AND DISCUSSION

E DETAILED EXPERIMENTAL SETTINGS

The experimental settings specify historical and statistical baselines alongside neural models, with architecture and training choices detailed for the compared approaches.

E DETAILED EXPERIMENTAL SETTINGS

  • The Historical Average baseline predicts using a weighted average of prior weeks' corresponding seasonal traffic speeds.The period is one week, and the example averages the previous four Wednesdays to predict a Wednesday.Source: E DETAILED EXPERIMENTAL SETTINGS · p. 12
  • The statistical baselines are ARIMA with Kalman filtering using orders (3, 0, 1), VAR with three lags, and linear SVR with C = 0.1 and five historical observations.Source: E DETAILED EXPERIMENTAL SETTINGS · pp. 12–13
  • The FNN baseline has two 256-unit hidden layers, while FC-LSTM uses an encoder-decoder with two recurrent layers of 256 LSTM units each.Both descriptions specify batch size 64 and MAE loss; the FC-LSTM passage also specifies peephole LSTM.Source: E DETAILED EXPERIMENTAL SETTINGS · p. 13
  • DCRNN uses two encoder and decoder recurrent layers with 64 units per layer, a maximum random-walk length K = 3, and thresholded inverse sigmoid scheduled sampling.The passage specifies validation-based early stopping; the scheduled-sampling decay uses τ = 3,000 iterations.Source: E DETAILED EXPERIMENTAL SETTINGS · p. 13

E.1 DATASET

Experiments use METR-LA and PEMS-BAY traffic data, with shared five-minute aggregation, normalization, data splits, and a road-distance-based sensor graph.

E.1 DATASET

  • METR-LA comprises 6,519,002 readings from 207 Los Angeles County highway sensors collected from March 1 to June 30, 2012.The dataset covers four months.Source: §E.1 · p. 13
  • PEMS-BAY contains 16,937,179 observed traffic data points from 325 Bay Area sensors, collected by CalTrans PeMS from January 1 through May 31, 2017.Source: §E.1 · p. 13
  • Both datasets use five-minute traffic-speed windows, Z-Score normalization, and a split of 70% training, 20% testing, and 10% validation.Source: §E.1 · p. 13
  • The sensor graph uses pairwise road-network distances and a thresholded Gaussian kernel to construct its adjacency matrix.The edge weight is described in terms of road-network distance, its standard deviation, and a threshold.Source: §E.1 · p. 13

E.2 METRICS

The section defines evaluation metrics using ground-truth and predicted values over observed samples.

E.2 METRICS

  • The metric definitions take x as the ground truth and x̂ as the predicted values.Source: §E.2 · p. 14
  • The index set Ω denotes the observed samples used in the metric definitions.Source: §E.2 · p. 14
  • The evaluation metrics are Root Mean Square Error (RMSE), Mean Absolute Percentage Error (MAPE), and Mean Absolute Error (MAE).Source: §E.2 · p. 14

F MODEL VISUALIZATION

The visualizations include traffic time-series forecasts and sensor-neighborhood correlations, which are localized and generally weaken with distance.

F MODEL VISUALIZATION

  • Figure 9 estimates correlations between a center sensor and its neighborhoods using regularized VAR.Source: Figure 9 · p. 14
  • Closer neighborhoods usually have larger relevance, while correlation magnitude quickly decays as distance increases, consistent with graph diffusion.Source: Figure 9 · p. 14
  • Figures 10 and 11 visualize traffic time-series forecasting.Source: Figure 10 · p. 15, Figure 11 · p. 16
Loading 1707.01926v3…