Spatio-Temporal Graph Convolutional Networks: A Deep ...

1 Spatio-Temporal Graph Convolutional Networks: A Deep learning Frameworkfor Traffic ForecastingBing Yu 1, Haoteng Yin 2,3, Zhanxing Zhu 3,41 School of Mathematical Sciences, Peking University, Beijing, China2 Academy for Advanced Interdisciplinary Studies, Peking University, Beijing, China3 Center for Data Science, Peking University, Beijing, China4 Beijing Institute of Big Data Research (BIBDR), Beijing, China{byu, htyin, accurate traffic forecast is crucial for ur-ban traffic control and guidance. Due to the highnonlinearity and complexity of traffic flow, tradi-tional methods cannot satisfy the requirements ofmid-and-long term prediction tasks and often ne-glect spatial and temporal dependencies. In this pa-per, we propose a novel deep learning framework, Spatio-Temporal Graph Convolutional Networks(STGCN), to tackle the time series prediction prob-lem in traffic domain.}

2 Instead of applying regu-lar Convolutional and recurrent units, we formulatethe problem on graphs and build the model withcomplete Convolutional structures, which enablemuch faster training speed with fewer show that our model STGCN effec-tively captures comprehensive Spatio-Temporal cor-relations through modeling multi-scale traffic net-works and consistently outperforms state-of-the-artbaselines on various real-world traffic IntroductionTransportation plays a vital role in everybody s daily life. Ac-cording to a survey in 2015, drivers spend about 48 min-utes on average behind the wheel this circum-stance, accurate real-time forecast of traffic conditions is ofparamount importance for road users, private sectors and gov-ernments.

3 Widely used transportation services, such as flowcontrol, route planning, and navigation, also rely heavily ona high-quality traffic condition evaluation. In general, multi-scale traffic forecast is the premise and foundation of urbantraffic control and guidance, which is also one of main func-tions of the Intelligent Transportation System (ITS).In the traffic study, fundamental variables of traffic flow,namely speed, volume, and density are typically chosen as in-dicators to monitor the current status of traffic conditions and Equal contributions. Corresponding predict the future. Based on the length of prediction, trafficforecast is generally classified into two scales: short-term (5 30 min), medium and long term (over 30 min).

4 Most preva-lent statistical approaches (for example, linear regression) areable to perform well on short interval forecast. However, dueto the uncertainty and complexity of traffic flow, those meth-ods are less effective for relatively long-term studies on mid-and-long term traffic predictioncan be roughly divided into two categories: dynamical mod-eling and data-driven methods. Dynamical modeling usesmathematical tools ( differential equations) and physi-cal knowledge to formulate traffic problems by computationalsimulation[Vlahogianni, 2015]. To achieve a steady state,the simulation process not only requires sophisticated system-atic programming but also consumes massive computationalpower. Impractical assumptions and simplifications amongthe modeling also degrade the prediction accuracy.

5 Therefore,with rapid development of traffic data collection and storagetechniques, a large group of researchers are shifting their at-tention to data-driven statistical and machine learning models are twomajor representatives of data-driven methods. In time-series analysis, autoregressive integrated moving average(ARIMA) and its variants are one of the most consolidatedapproaches based on classical statistics[Ahmed and Cook,1979; Williams and Hoel, 2003]. However, this type of modelis limited by the stationary assumption of time sequencesand fails to take the Spatio-Temporal correlation into , these approaches have constrained representabil-ity of highly nonlinear traffic flow. Recently, classic statisticalmodels have been vigorously challenged by machine learningmethods on traffic prediction tasks.

6 Higher prediction accu-racy and more complex data modeling can be achieved bythese models, such ask-nearest neighbors algorithm (KNN),support vector machine (SVM), and neural networks (NN).Deep learning approacheshave been widely and suc-cessfully applied to various traffic tasks nowadays. Sig-nificant progress has been made in related work, for in-stance, deep belief network (DBN)[Jiaet al., 2016; Huanget al., 2014], stacked autoencoder (SAE)[Lvet al., 2015;Chenet al., 2016]. However, it is difficult for these denseProceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence (IJCAI-18)3634networks to extract spatial and temporal features from the in-put jointly. Moreover, within narrow constraints or even com-plete absence of spatial attributes, the representative ability ofthese networks would be hindered take full advantage of spatial features, some researchersuse Convolutional neural network (CNN) to capture adjacentrelations among the traffic network , along with employingrecurrent neural network (RNN) on time axis.

7 By combin-ing long short-term memory (LSTM) network [Hochreiterand Schmidhuber, 1997]and 1-D CNN, Wu and Tan[2016]presented a feature-level fused architecture CLTFP for short-term traffic forecast. Although it adopted a straightforwardstrategy, CLTFP still made the first attempt to align spatialand temporal regularities. Afterwards, Shiet al.[2015]pro-posed the Convolutional LSTM, which is an extended fully-connected LSTM (FC-LSTM) with embedded convolutionallayers. However, the normal Convolutional operation appliedrestricts the model to only process grid structures ( im-ages, videos) rather than general domains. Meanwhile, recur-rent networks for sequence learning require iterative training,which introduces error accumulation by steps.

8 Additionally,RNN-based networks (including LSTM) are widely known tobe difficult to train and computationally overcoming these issues, we introduce several strate-gies to effectively model temporal dynamics and spatial de-pendencies of traffic flow. To fully utilize spatial informa-tion, we model the traffic network by a general Graph insteadof treating it separately ( grids or segments). To handlethe inherent deficiencies of recurrent networks, we employ afully Convolutional structure on time axis. Above all, we pro-pose a novel deep learning architecture, the spatio-temporalgraph Convolutional networks, for traffic forecasting architecture comprises several Spatio-Temporal convolu-tional blocks, which are a combination of Graph convolutionallayers[Defferrardet al.]

9 , 2016]and Convolutional sequencelearning layers, to model spatial and temporal the best of our knowledge, it is the first time that to ap-ply purely Convolutional structures to extract spatio-temporalfeatures simultaneously from Graph -structured time series ina traffic study. We evaluate our proposed model on two real-world traffic datasets. Experiments show that our frameworkoutperforms existing baselines in prediction tasks with multi-ple preset prediction lengths and network Traffic Prediction on Road GraphsTraffic forecast is a typical time-series prediction problem, predicting the most likely traffic measurements ( or traffic flow) in the nextHtime steps given the pre-viousMtraffic observations as, vt+1.

10 , vt+H=arg maxvt+1,..,vt+HlogP(vt+1,..,vt+H|vt M+1,..,vt),(1)wherevt2 Rnis an observation vector ofnroad segmentsat time stept, each element of which records historical obser-vation for a single road this work, we define the traffic network on a Graph andfocus on structured traffic time series. The observationvtisvt+ +1 TimeFigure 1: Graph -structured traffic data. Eachvtindicates a frameof current traffic status at time stept, which is recorded in a Graph -structured data independent but linked by pairwise connection in , the data pointvtcan be regarded as a Graph sig-nal that is defined on an undirected Graph (or directed one)Gwith weightswijas shown in Figure 1. At thet-th time step,in graphGt=(Vt,E,W),Vtis a finite set of vertices, corre-sponding to the observations fromnmonitor stations in a traf-fic network ;Eis a set of edges, indicating the connectednessbetween stations; whileW2Rn ndenotes the weightedadjacency matrix Convolutions on GraphsA standard convolution for regular grids is clearly not appli-cable to general graphs.