Hybrid Spatio-Temporal Graph Convolutional Network: Improving Traffic Prediction with Navigation Data

Rui Dai, Shenkun Xu, Qian Gu, Chenguang Ji, Kaikui LiuKDD 2020 · DOI

TL;DR

This paper introduces H-STGCN, a novel deep learning model that significantly improves traffic prediction accuracy by incorporating future traffic volume data derived from online navigation services. By developing a unique "domain transformer" to convert volume into travel time and a "compound adjacency matrix" to better model road network proximity, H-STGCN achieves state-of-the-art results, particularly for predicting challenging non-recurring congestion events.

What Problem Does This Paper Address?

Accurate traffic prediction is crucial for various applications, from smart city planning to efficient navigation. However, traditional data-driven models often struggle because road traffic is inherently non-stationary and influenced by many factors that are hard to capture. Existing methods primarily rely on historical travel time data, which can be insufficient, especially when unexpected events like accidents or sudden surges in demand cause non-recurring congestion. The challenge lies in effectively integrating external, predictive information into these models to capture these dynamic changes.

Methods

The core of this paper is the Hybrid Spatio-Temporal Graph Convolutional Network (H-STGCN). Its key innovations include:

  • Future Traffic Volume Integration: The model leverages data from online navigation engines (like Amap) to predict future traffic volume on road segments. This is a significant departure from relying solely on historical traffic data.
  • Domain Transformer: To bridge the gap between traffic volume and travel time, a novel transformer architecture is proposed. It uses traffic flow theory (specifically, the flow-density relationship) to convert predicted traffic volume into an equivalent travel time signal. This transformer has two cascaded layers: a shared 1x1 convolution for universal mapping and a segment-wise 1x1 convolution for segment-specific features.
  • Compound Adjacency Matrix: Traditional graph convolutional networks use adjacency matrices based on simple distance decay. This paper argues that road network proximity is more complex. They introduce a compound adjacency matrix that combines a Dijkstra-based spatial distance matrix with a covariance matrix of travel times. This aims to better capture "innate traffic proximity," considering factors beyond just physical contiguity.
  • Hybrid Architecture: The H-STGCN combines these elements. The domain transformer processes future volume, this signal is then combined with historical travel time, and a graph convolutional network (using the compound adjacency matrix) models spatial dependencies. Temporal gated convolutions are used to capture temporal patterns.

Datasets

The experiments were conducted on two real-world regional road networks in Beijing, provided by Amap:

  • W3-715: A network around the West 3rd Ring Road with 715 segments.
  • E5-2907: A larger network around the East 5th Ring Road with 2907 segments.

Data was collected from December 24, 2018, to April 21, 2019, with holidays removed. The previous eight weeks were used for training, and the remaining two weeks for testing. The paper also defines specific test sets focusing on high-volume segments and congested/non-recurring congested periods for more targeted evaluation.

Key Insights and Ideas

  • Predictive Power of Navigation Data: The most significant insight is that future traffic volume, obtainable from navigation services, is a powerful predictor of future travel times, especially for dynamic events like congestion. This moves beyond reactive prediction based on past states.
  • Bridging Modalities is Key: The "domain transformer" is crucial for effectively integrating the "heterogeneous modality" of traffic volume into a model designed for travel time. This approach is presented as a general coupler for any neural network architecture.
  • Beyond Simple Distance: The compound adjacency matrix highlights that traffic flow and congestion propagation are not solely dictated by physical distance. Incorporating travel time covariance better reflects how traffic conditions influence each other across the network.
  • Non-Recurring Congestion is a Differentiator: The model's superior performance on non-recurring congestion (e.g., due to accidents) underscores the value of incorporating external, predictive information that can signal these sudden disruptions.

Key Results

  • State-of-the-Art Performance: H-STGCN consistently outperforms benchmark models (HA, LR, GBRT, MLP, Seq2Seq, and STGCN) across various metrics (MAE, MAPE, RMSE) on both datasets and all test set configurations.
  • Significant Improvement on Congestion: The model shows particularly strong gains on the "congested" (C) and "non-recurring congested" (NRC) test sets, demonstrating its effectiveness in predicting challenging traffic scenarios. For example, on the E5-2907 NRC test set, H-STGCN achieved an MAE of 0.09528 s/m, outperforming the next best (STGCN (Im)) by a notable margin.
  • Impact of Future Volume: Ablation studies show that incorporating future volume data (comparing H-STGCN to STGCN (Im)) significantly improves performance, especially as the forecasting horizon increases.
  • Compound Adjacency Matrix Benefits: Using the compound adjacency matrix (comparing STGCN (Im) to STGCN) also leads to improved accuracy, validating its effectiveness in modeling traffic proximity.
  • Fast Inference: The model achieves inference times of less than 100 ms, making it suitable for real-world deployment.

Limitations and Future Work

  • Ideal Future Volume Approximation: The paper uses "ideal future volume" derived from navigation data. This is an approximation of actual future volume, as navigation engines only know about trips that have already started. The authors acknowledge that actual future traffic volume might be even greater.
  • Model Scalability Strategy: For large city-wide networks, the authors propose partitioning the network into sub-networks and training separate models. While this addresses scalability, it's a practical deployment strategy rather than an inherent model scalability solution.
  • Future Work: The paper suggests that the architecture can be applied to other spatio-temporal forecasting tasks by embedding physics-based knowledge into data-driven models. Further exploration of how to better integrate diverse external data sources could also be a direction.

Summary updated

BibTeX
@inproceedings{dai2020hybrid,
  author = {Rui Dai and Shenkun Xu and Qian Gu and Chenguang Ji and Kaikui Liu},
  title = {{Hybrid Spatio-Temporal Graph Convolutional Network: Improving Traffic Prediction with Navigation Data}},
  booktitle = {ACM SIGKDD Conference on Knowledge Discovery and Data Mining},
  year = {2020},
  doi = {10.1145/3394486.3403358},
}
Figure