The Thirty-Third AAAI Conference on Artificial Intelligence (AAAI-19)
Dynamic Spatial-Temporal Graph Convolutional Neural Networks for
Traffic Forecasting
Zulong Diao,
1
Xin Wang,
2
Dafang Zhang,
1∗
Yingru Liu,
2
Kun Xie,
1
Shaoyao He
3
1
The College of Computer Science and Electronic Engineering, Hunan University, Changsha 410082, China
2
The Department of Electrical and Computer Engineering, Stony Brook University, Stony Brook, NY, 11794
3
The College of Architecture, Hunan University, Changsha 410082
{zldiao, dfzhang, xiekun}@hnu.edu.cn, {x.wang, yingru.liu}@stonybrook.edu, syhe829@163.com
Abstract
Graph convolutional neural networks (GCNN) have become
an increasingly active field of research. It models the spatial
dependencies of nodes in a graph with a pre-defined Lapla-
cian matrix based on node distances. However, in many appli-
cation scenarios, spatial dependencies change over time, and
the use of fixed Laplacian matrix cannot capture the change.
To track the spatial dependencies among traffic data, we pro-
pose a dynamic spatio-temporal GCNN for accurate traffic
forecasting. The core of our deep learning framework is the
finding of the change of Laplacian matrix with a dynamic
Laplacian matrix estimator. To enable timely learning with
a low complexity, we creatively incorporate tensor decom-
position into the deep learning framework, where real-time
traffic data are decomposed into a global component that is
stable and depends on long-term temporal-spatial traffic rela-
tionship and a local component that captures the traffic fluc-
tuations. We propose a novel design to estimate the dynamic
Laplacian matrix of the graph with above two components
based on our theoretical derivation, and introduce our design
basis. The forecasting performance is evaluated with two real-
time traffic datasets. Experiment results demonstrate that our
network can achieve up to 25% accuracy improvement.
Introduction
Traffic forecasting is fundamental to the performance of
many components in intelligent transportation systems
(ITS). The accurate and reliable traffic forecasting can as-
sist in proactive and dynamic traffic control as well as in-
telligent route guidance, which will help alleviate the huge
congestion problem in the system. In this paper, we are in-
terested in simultaneously predicting the traffic of multiple
road segments in a road network.
Great efforts have been devoted to improve the traffic
forecasting accuracy (Diao et al. 2018). Some studies ap-
ply traditional machine learning methods, such as auto-
regressive and moving average model (ARMA) (Williams
and Hoel 2003) and support vector regression (SVR) (Chen
et al. 2015) and etc, to forecast future traffic. As most
of these methods are linear and not suitable for handling
∗
Corresponding author
Copyright
c
2019, Association for the Advancement of Artificial
Intelligence (www.aaai.org). All rights reserved.
volatile traffic data, the forecasting accuracy is often low. In
recent years, the prediction methods based on deep learn-
ing have received considerable attention. Some attempts
have been made to apply deep Recurrent Neural Networks
(RNN)(Wu and Tan 2016) and Convolution Neural Network
(CNN) (Zhang et al. 2016; Zhang, Zheng, and Qi 2016;
Ma et al. 2017) to predict traffic flow. However, these meth-
ods are not suitable to apply to the data points with ir-
regular graph relationship. As graph structure arises natu-
rally in the traffic network, Graph Convolutional Neural Net-
work (GCNN) is the appealing choice (Yu, Yin, and Zhu
2017a). GCNN with deep architectures have proven to be
very efficient in short-term traffic forecasting area (Yao et
al. 2018). By incorporating the spectral graph theory (Fan
1997), GCNN is efficient in handling signals that live on
irregular or non-Euclidean domains. Nevertheless, existing
GCNN frameworks have some limitations that make them
less efficient in traffic forecasting.
GCNN heavily depend on the Laplacian matrix of a graph,
which is defined as the difference between the diagonal ma-
trix of node degrees and the adjacency matrix. Previous
GCNN studies rely on the key assumption that the Lapla-
cian matrix is strictly unchanged and available (i,e. the ad-
jacency matrix of the input graph is constant). However, our
previous studies demonstrate that there are huge differences
between traffic patterns during different time spans. In addi-
tion, traffic accidents may occur every day, which will also
affect the relationship between road segments in the road
network. These factors will lead to the dynamic changes of
adjacency matrix thus the Laplacian matrix. Therefore, the
exact Laplacian matrix of the graph could be time-variant
and generally intractable.
To address the issues above, we propose a novel spatial-
temporal structure to more accurately forecast network-wide
traffic speed, and we call it dynamic GCNN (DGCNN).
Compared with existing GCNN-based methods, our paper
makes the following contributions:
• We creatively incorporate tensor decomposition opera-
tions into the deep learning framework to extract the
global and local components from traffic samples. From
frequency analysis, network-wide traffic samples within a
time span are composed of two components: the global
890