Spatio-Temporal Graph Convolutional Networks: A Deep Learning Framework for Traffic Forecasting

1 Introduction

Transportation plays a vital role in everybody's daily life. According to a survey in 2015, U.S. drivers spend about 48 minutes on average behind the wheel daily. 1 Under this circumstance, accurate real-time forecast of traffic conditions is of paramount importance for road users, private sectors and governments. Widely used transportation services, such as flow control, route planning, and navigation, also rely heavily on a high-quality traffic condition evaluation. In general, multiscale traffic forecast is the premise and foundation of urban traffic control and guidance, which is also one of main functions of the Intelligent Transportation System (ITS).

In the traffic study, fundamental variables of traffic flow, namely speed, volume, and density are typically chosen as indicators to monitor the current status of traffic conditions and to predict the future. Based on the length of prediction, traffic forecast is generally classified into two scales: short-term (5 ⇠ 30 min), medium and long term (over 30 min). Most prevalent statistical approaches (for example, linear regression) are able to performwell on short interval forecast. However, due to the uncertainty and complexity of traffic flow, those methods are less effective for relatively long-term predictions.

⇤Equal contributions.

Corresponding author.

1 https://aaafoundation.org/american-driving-survey-2014-2015/

Previous studies on mid-and-long term traffic prediction can be roughly divided into two categories: dynamical modeling and data-driven methods. Dynamical modeling uses mathematical tools (e.g. differential equations) and physical knowledge to formulate traffic problems by computational simulation [Vlahogianni, 2015]. To achieve a steady state, the simulation process not only requires sophisticated systematic programming but also consumes massive computational power. Impractical assumptions and simplifications among the modeling also degrade the prediction accuracy. Therefore, with rapid development of traffic data collection and storage techniques, a large group of researchers are shifting their attention to data-driven approaches.

Classic statistical and machine learning models are two major representatives of data-driven methods. In timeseries analysis, autoregressive integrated moving average (ARIMA) and its variants are one of the most consolidated approaches based on classical statistics [Ahmed and Cook, 1979; Williams and Hoel, 2003]. However, this type of model is limited by the stationary assumption of time sequences and fails to take the spatio-temporal correlation into account. Therefore, these approaches have constrained representability of highly nonlinear traffic flow. Recently, classic statistical models have been vigorously challenged by machine learning methods on traffic prediction tasks. Higher prediction accuracy and more complex data modeling can be achieved by these models, such as k-nearest neighbors algorithm (KNN), support vector machine (SVM), and neural networks (NN).

Deep learning approaches have been widely and successfully applied to various traffic tasks nowadays. Significant progress has been made in related work, for instance, deep belief network (DBN) [Jia et al., 2016; Huang et al., 2014], stacked autoencoder (SAE) [Lv et al., 2015; Chen et al., 2016]. However, it is difficult for these dense networks to extract spatial and temporal features from the input jointly. Moreover, within narrow constraints or even complete absence of spatial attributes, the representative ability of these networks would be hindered seriously.

To take full advantage of spatial features, some researchers use convolutional neural network (CNN) to capture adjacent relations among the traffic network, along with employing recurrent neural network (RNN) on time axis. By combining long short-term memory (LSTM) network [Hochreiter and Schmidhuber, 1997] and 1-D CNN, Wu and Tan [2016] presented a feature-level fused architecture CLTFP for shortterm traffic forecast. Although it adopted a straightforward strategy, CLTFP still made the first attempt to align spatial and temporal regularities. Afterwards, Shi et al. [2015] proposed the convolutional LSTM, which is an extended fullyconnected LSTM (FC-LSTM) with embedded convolutional layers. However, the normal convolutional operation applied restricts the model to only process grid structures (e.g. images, videos) rather than general domains. Meanwhile, recurrent networks for sequence learning require iterative training, which introduces error accumulation by steps. Additionally, RNN-based networks (including LSTM) are widely known to be difficult to train and computationally heavy.

For overcoming these issues, we introduce several strategies to effectively model temporal dynamics and spatial dependencies of traffic flow. To fully utilize spatial information, we model the traffic network by a general graph instead of treating it separately (e.g. grids or segments). To handle the inherent deficiencies of recurrent networks, we employ a fully convolutional structure on time axis. Above all, we propose a novel deep learning architecture, the spatio-temporal graph convolutional networks, for traffic forecasting tasks. This architecture comprises several spatio-temporal convolutional blocks, which are a combination of graph convolutional layers [Defferrard et al., 2016] and convolutional sequence learning layers, to model spatial and temporal dependencies. To the best of our knowledge, it is the first time that to apply purely convolutional structures to extract spatio-temporal features simultaneously from graph-structured time series in a traffic study. We evaluate our proposed model on two realworld traffic datasets. Experiments show that our framework outperforms existing baselines in prediction tasks with multiple preset prediction lengths and network scales.

2 Preliminary

2.1 Traffic Prediction on Road Graphs

Traffic forecast is a typical time-series prediction problem, i.e. predicting the most likely traffic measurements (e.g. speed or traffic flow) in the next H time steps given the previous M traffic observations as,

where vt 2 Rn is an observation vector of n road segments at time step t, each element of which records historical observation for a single road segment.

In this work, we define the traffic network on a graph and focus on structured traffic time series. The observation vt is not independent but linked by pairwise connection in graph. Therefore, the data point vt can be regarded as a graph signal that is defined on an undirected graph (or directed one) G with weights wij as shown in Figure 1. At the t-th time step, in graph Gt = (Vt↪ E↪W), Vt is a finite set of vertices, corresponding to the observations from n monitor stations in a traffic network; E is a set of edges, indicating the connectedness between stations; while W 2 Rn⇥n denotes the weighted adjacency matrix of Gt.

2.2 Convolutions on Graphs

A standard convolution for regular grids is clearly not applicable to general graphs. There are two basic approaches currently exploring how to generalize CNNs to structured data forms. One is to expand the spatial definition of a convolution [Niepert et al., 2016], and the other is to manipulate in the spectral domain with graph Fourier transforms [Bruna et al., 2013]. The former approach rearranges the vertices into certain grid forms which can be processed by normal convolutional operations. The latter one introduces the spectral framework to apply convolutions in spectral domains, often named as the spectral graph convolution. Several followingup studies make the graph convolution more promising by reducing the computational complexity fromO(n2 ) to linear [Defferrard et al., 2016; Kipf and Welling, 2016].

We introduce the notion of graph convolution operator "⇤G" based on the conception of spectral graph convolution, as the multiplication of a signal x 2 Rn with a kernel ⇥,

⇥ ⇤G x = ⇥(L)x = ⇥(U⇤U T )x = U⇥(⇤)U T x↪ (2) where graph Fourier basis U 2 Rn⇥n is the matrix of eigenvectors of the normalized graph Laplacian L = In - D- 12WD- 12 = U⇤U T 2 Rn⇥n (In is an identity matrix, D 2 Rn⇥n is the diagonal degree matrix with Dii = ⌃jWij ); ⇤ 2 Rn⇥n is the diagonal matrix of eigenvalues of L, and filter ⇥(⇤) is also a diagonal matrix. By this definition, a graph signal x is filtered by a kernel ⇥ with multiplication between ⇥ and graph Fourier transform U T x [Shuman et al., 2013].

3 ProposedModel

3.1 Network Architecture

In this section, we elaborate on the proposed architecture of spatio-temporal graph convolutional networks (STGCN). As shown in Figure 2, STGCN is composed of several spatiotemporal convolutional blocks, each of which is formed as a "sandwich" structure with two gated sequential convolution layers and one spatial graph convolution layer in between. The details of each module are described as follows.

t

Figure 2: Architecture of spatio-temporal graph convolutional networks. The framework STGCN consists of two spatio-temporal convolutional blocks (ST-Conv blocks) and a fully-connected output layer in the end. Each ST-Conv block contains two temporal gated convolution layers and one spatial graph convolution layer in the middle. The residual connection and bottleneck strategy are applied inside each block. The input vt-M+1↪ ▷▷▷↪ vt is uniformly processed by ST-Conv blocks to explore spatial and temporal dependencies coherently. Comprehensive features are integrated by an output layer to generate the final prediction ˆ v.

3.2 Graph CNNs for Extracting Spatial Features

The traffic network generally organizes as a graph structure. It is natural and reasonable to formulate road networks as graphs mathematically. However, previous studies neglect spatial attributes of traffic networks: the connectivity and globality of the networks are overlooked, since they are split into multiple segments or grids. Even with 2-D convolutions on grids, it can only capture the spatial locality roughly due to compromises of data modeling. Accordingly, in our model, the graph convolution is employed directly on graphstructured data to extract highly meaningful patterns and features in the space domain. Though the computation of kernel ⇥ in graph convolution by Eq. (2) can be expensive due to O(n2 ) multiplications with graph Fourier basis, two approximation strategies are applied to overcome this issue.

Chebyshev Polynomials Approximation To localize the filter and reduce the number of parameters, the kernel ⇥ can be restricted to a polynomial of ⇤ as ⇥(⇤) = PK-1 k=0 ✓k⇤k , where ✓ 2 RK is a vector of polynomial coefficients. K is the kernel size of graph convolution, which determines the maximum radius of the convolution from central nodes. Traditionally, Chebyshev polynomial Tk(x) is used to approximate kernels as a truncated expansion of order K-1 as ⇥(⇤) ⇡ PK-1 k=0 ✓kTk(˜⇤) with rescaled ˜⇤ = 2⇤◁λmax - In (λmax denotes the largest eigenvalue of L) [Hammond et al., 2011]. The graph convolution can then be rewritten as,

where Tk(˜L) 2 Rn⇥n is the Chebyshev polynomial of order k evaluated at the scaled Laplacian ˜L = 2L◁λmax - In. By recursively computing K-localized convolutions through the polynomial approximation, the cost of Eq. (2) can be reduced to O(K♣E♣) as Eq. (3) shows [Defferrard et al., 2016].

1st -order Approximation A layer-wise linear formulation can be defined by stacking multiple localized graph convolutional layers with the first-order approximation of graph Laplacian [Kipf and Welling, 2016]. Consequently, a deeper architecture can be constructed to recover spatial information in depth without being limited to the explicit parameterization given by the polynomials. Due to the scaling and normalization in neural networks, we can further assume that λmax ⇡ 2. Thus, the Eq. (3) can be simplified to,

where ✓0, ✓1 are two shared parameters of the kernel. In order to constrain parameters and stabilize numerical performances, ✓0 and ✓1 are replaced by a single parameter ✓ by letting ✓ = ✓0 = -✓1; W and D are renormalized by ˜W =W + In and ˜Dii = ⌃j ˜Wij separately. Then, the graph convolution can be alternatively expressed as,

Applying a stack of graph convolutions with the 1st -order approximation vertically that achieves the similar effect as Klocalized convolutions do horizontally, all of which exploit the information from the (K-1)-order neighborhood of central nodes. In this scenario, K is the number of successive filtering operations or convolutional layers in a model instead. Additionally, the layer-wise linear structure is parametereconomic and highly efficient for large-scale graphs, since the order of the approximation is limited to one.

Generalization of Graph Convolutions The graph convolution operator "⇤G" defined on x 2 Rn can be extended to multi-dimensional tensors. For a signal with Ci channels X 2 Rn⇥Ci , the graph convolution can be generalized by,

with the Ci ⇥ Co vectors of Chebyshev coefficients ⇥i↪j 2 RK (Ci, Co are the size of input and output of the feature maps, respectively). The graph convolution for 2-D variables is denoted as "⇥ ⇤G X" with ⇥ 2 RK⇥Ci⇥Co . Specifically, the input of traffic prediction is composed of M frame of road graphs as Figure 1 shows. Each frame vt can be regarded as a matrix whose column i is the Ci-dimensional value of vt at the ith node in graph Gt, as X 2 Rn⇥Ci (in this case, Ci = 1). For each time step t of M, the equal graph convolution operation with the same kernel ⇥ is imposed on Xt 2 Rn⇥Ci in parallel. Thus, the graph convolution can be further generalized in 3-D variables, noted as "⇥ ⇤G X" with X 2 RM⇥n⇥Ci .

3.3 Gated CNNs for Extracting Temporal Features

Although RNN-based models become widespread in timeseries analysis, recurrent networks for traffic prediction still suffer from time-consuming iterations, complex gate mechanisms, and slow response to dynamic changes. On the contrary, CNNs have the superiority of fast training, simple structures, and no dependency constraints to previous steps. Inspired by [Gehring et al., 2017], we employ entire convolutional structures on time axis to capture temporal dynamic behaviors of traffic flows. This specific design allows parallel and controllable training procedures through multi-layer convolutional structures formed as hierarchical representations.

As Figure 2 (right) shows, the temporal convolutional layer contains a 1-D causal convolution with a width-Kt kernel followed by gated linear units (GLU) as a non-linearity. For each node in graph G, the temporal convolution explores Kt neighbors of input elements without padding which leading to shorten the length of sequences by Kt-1 each time. Thus, input of temporal convolution for each node can be regarded as a length-M sequence with Ci channels as Y 2 RM⇥Ci . The convolution kernel Γ 2 RKt⇥Ci⇥2Co is designed to map the input Y to a single output element [P Q] 2 R(M-Kt+1)⇥(2Co) (P , Q is split in half with the same size of channels). As a result, the temporal gated convolution can be

where P , Q are input of gates in GLU respectively; ⊙ denotes the element-wise Hadamard product. The sigmoid gate σ(Q) controls which input P of the current states are relevant for discovering compositional structure and dynamic variances in time series. The non-linearity gates contribute to the exploiting of the full input filed through stacked temporal layers as well. Furthermore, residual connections are implemented among stacked temporal convolutional layers. Similarly, the temporal convolution can also be generalized to 3-D variables by employing the same convolution kernel Γ to every node Yi 2 RM⇥Ci (e.g. sensor stations) in G equally, noted as "Γ ⇤T Y" with Y 2 RM⇥n⇥Ci .

3.4 Spatio-temporal Convolutional Block

In order to fuse features from both spatial and temporal domains, the spatio-temporal convolutional block (ST-Conv block) is constructed to jointly process graph-structured time series. The block itself can be stacked or extended based on the scale and complexity of particular cases.

As illustrated in Figure 2 (mid), the spatial layer in the middle is to bridge two temporal layers which can achieve fast spatial-state propagation from graph convolution through temporal convolutions. The "sandwich" structure also helps the network sufficiently apply bottleneck strategy to achieve scale compression and feature squeezing by downscaling and upscaling of channels C through the graph convolutional layer. Moreover, layer normalization is utilized within every ST-Conv block to prevent overfitting.

The input and output of ST-Conv blocks are all 3-D tensors. For the input vl 2 RM⇥n⇥Cl of block l, the output vl+1 2 R(M-2(Kt-1))⇥n⇥Cl+1 is computed by,

where Γl0 , Γl1 are the upper and lower temporal kernel within block l, respectively; ⇥l is the spectral kernel of graph convolution; ReLU(·) denotes the rectified linear units function. After stacking two ST-Conv blocks, we attach an extra temporal convolution layer with a fully-connected layer as the output layer in the end (See the left of Figure 2). The temporal convolution layer maps outputs of the last ST-Conv block to a single-step prediction. Then, we can obtain a final output Z 2 Rn⇥c from the model and calculate the speed prediction for n nodes by applying a linear transformation across c-channels as ˆ v = Zw + b, where w 2 Rc is a weight vector and b is a bias. We use L2 loss to measure the performance of our model. Thus, the loss function of STGCN for traffic prediction can be written as,

where W✓ are all trainable parameters in the model; vt+1 is the ground truth and ˆ v(·) denotes the model's prediction.

We now summarize the main characteristics of our model STGCN in the following,

• ÷ STGCN is a universal framework to process structured time series. It is not only able to tackle traffic network modeling and prediction issues but also to be applied to more general spatio-temporal sequence learning tasks.
• ÷ The spatio-temporal block combines graph convolutions and gated temporal convolutions, which can extract the most useful spatial features and capture the most essential temporal features coherently.
• ÷ The model is entirely composed of convolutional structures and therefore achieves parallelization over input with fewer parameters and faster training speed. More importantly, this economic architecture allows the model to handle large-scale networks with more efficiency.

4 Experiments

4.1 Dataset Description

We verify our model on two real-world traffic datasets, BJER4 and PeMSD7, collected by Beijing Municipal Traffic Commission and California Deportment of Transportation, respectively. Each dataset contains key attributes of traffic observations and geographic information with corresponding timestamps, as detailed below.

BJER4 was gathered from the major areas of east ring No.4 routes in Beijing City by double-loop detectors. There are 12 roads selected for our experiment. The traffic data are aggregated every 5 minutes. The time period used is from 1st July to 31st August, 2014 except the weekends. We select the first month of historical speed records as training set, and the rest serves as validation and test set respectively.

PeMSD7 was collected from Caltrans Performance Measurement System (PeMS) in real-time by over 39, 000 sensor stations, deployed across the major metropolitan areas of California state highway system [Chen et al., 2001]. The dataset is also aggregated into 5-minute interval from 30-second data samples. We randomly select a medium and a large scale among the District 7 of California containing 228 and 1, 026

stations, labeled as PeMSD7(M) and PeMSD7(L), respectively, as data sources (shown in the left of Figure 3). The time range of PeMSD7 dataset is in the weekdays of May and June of 2012. We split the training and test sets based on the same principles as above.

4.2 Data Preprocessing

The standard time interval in two datasets is set to 5 minutes. Thus, every node of the road graph contains 288 data points per day. The linear interpolation method is used to fill missing values after data cleaning. In addition, data input are normalized by Z-Score method.

In BJER4, the topology of the road graph in Beijing east No.4 ring route system is constructed by the deployment diagram of sensor stations. By collating affiliation, direction and origin-destination points of each road, the ring route system can be digitized as a directed graph.

In PeMSD7, the adjacency matrix of the road graph is computed based on the distances among stations in the traffic network. The weighted adjacency matrix W can be formed as,

where wij is the weight of edge which is decided by dij (the distance between station i and j). σ2 and ✏ are thresholds to control the distribution and sparsity of matrix W, assigned to 10 and 0▷5, respectively. The visualization of W is presented in the right of Figure 3.

4.3 Experimental Settings

All experiments are compiled and tested on a Linux cluster (CPU: Intel(R) Xeon(R) CPU E5-2620 v4 @ 2.10GHz, GPU: NVIDIA GeForce GTX 1080). In order to eliminate atypical traffic, only workday traffic data are adopted in our experiment [Li et al., 2015]. We execute grid search strategy to locate the best parameters on validations. All the tests use 60 minutes as the historical time window, a.k.a. 12 observed data points (M = 12) are used to forecast traffic conditions in the next 15, 30, and 45 minutes (H = 3↪ 6↪ 9).

Evaluation Metric & Baselines To measure and evaluate the performance of different methods, Mean Absolute Errors (MAE), Mean Absolute Percentage Errors (MAPE), and Root Mean Squared Errors (RMSE) are adopted. We compare our framework STGCN with the following baselines: 1). Historical Average (HA); 2). Linear Support Victor Regression (LSVR); 3). Auto-Regressive Integrated Moving Average (ARIMA); 4). Feed-Forward Neural Network (FNN); 5). Full-Connected LSTM (FC-LSTM) [Sutskever et al., 2014]; 6). Graph Convolutional GRU (GCGRU) [Li et al., 2018].

STGCN Model For BJER4 and PeMSD7(M/L), the channels of three layers in ST-Conv block are 64, 16, 64 respectively. Both the graph convolution kernel size K and temporal convolution kernel size Kt are set to 3 in the model STGCN(Cheb) with the Chebyshev polynomials approximation, while the K is set to 1 in the model STGCN(1st ) with the 1st -order approximation. We train our models by minimizing the mean square error using RMSprop for 50 epochs with batch size as 50. The initial learning rate is 10-3 with a decay rate of 0.7 after every 5 epochs.

4.4 Experiment Results

Table 1 and 2 demonstrate the results of STGCN and baselines on the datasets BJER4 and PeMSD7(M/L). Our proposed model achieves the best performance with statistical significance (two-tailed T-test, ↵ = 0▷01, P < 0▷01) in all three evaluation metrics. We can easily observe that traditional statistical and machine learning methods may perform well for short-term forecasting, but their long-term predictions are not accurate because of error accumulation, memorization issues, and absence of spatial information. ARIMA model performs the worst due to its incapability of handling complex spatio-temporal data. Deep learning approaches generally achieved better prediction results than traditional machine learning models.

Benefits of Spatial Topology

Previous methods did not incorporate spatial topology and modeled the time series in a coarse-grained way. Differently, through modeling spatial topology of the sensors, our model STGCN has achieved a significant improvement on short and mid-and-long term forecasting. The advantage of STGCN is more obvious on dataset PeMSD7 than BJER4, since the sensor network of PeMS is more complicated and structured (as illustrated in Figure 3), and our model can effectively utilize spatial structure to make more accurate predictions.

To compare three methods based on graph convolution: GCGRU, STGCN(Cheb) and STGCN(1st ), we show their predictions during morning peak and evening rush hours, as shown in Figure 4. It is easy to observe that our proposal STGCN captures the trend of rush hours more accurately than other methods; and it detects the ending of the rush hours earlier than others. Stemming from the efficient graph convolution and stacked temporal convolution structures, our model is capable of fast responding to the dynamic changes among the traffic network without over-reliance on historical average as most of recurrent networks do.

Training Efficiency and Generalization

To see the benefits of the convolution along time axis in our proposal, we summarize the comparison of training time between STGCN and GCGRU in Table 3. In terms of fairness, GCGRU consists of three layers with 64, 64, 128 units respectively in the experiment for PeMSD7(M), and STGCN uses the default settings as described in Section 4.3. Our model STGCN only consumes 272 seconds, while RNN-type of model GCGRU spends 3, 824 seconds on PeMSD7(M). This 14 times acceleration of training speed mainly benefits from applying the temporal convolution instead of recurrent structures, which can achieve fully parallel training rather than exclusively relying on chain structures as RNN

do. For PeMSD7(L), GCGRU has to use the half of batch size since its GPU consumption exceeded the memory capacity of a single card (results marked as "*" in Table 2); while STGCN only need to double the channels in the middle of ST-Conv blocks. Even though our model still consumes less than a tenth of the training time of model GCGRU under this circumstance. Meanwhile, the advantages of the 1st -order approximation have appeared since it is not restricted to the parameterization of polynomials. The model STGCN(1st ) speeds up around 20% on a larger dataset with a satisfactory performance compared with STGCN(Cheb).

In order to further investigate the performance of compared deep learning models, we plot the RMSE and MAE of the test set of PeMSD7(M) during the training process, see Figure 5. Those figures also suggest that our model can achieve much faster training procedure and easier convergences. Thanks to the special designs in ST-Conv blocks, our model has superior performances in balancing time consumption and parameter settings. Specifically, the number of parameters in STGCN (4▷54 ⇥ 105 ) only accounts for around two third of GCGRU, and saving over 95% parameters compared to FC-LSTM.

5 RelatedWorks

There are several recent deep learning studies that are also motivated by the graph convolution in spatio-temporal tasks. Seo et al. [2016] introduced graph convolutional recurrent network (GCRN) to identify jointly spatial structures and dynamic variation from structured sequences of data. The key challenge of this study is to determine the optimal combinations of recurrent networks and graph convolution under specific settings. Based on principles above, Li et al. [2018] successfully employed the gated recurrent units (GRU) with graph convolution for long-term traffic forecasting. In contrast to these works, we build up our model completely from convolutional structures; The ST-Conv block is specially designed to uniformly process structured data with residual connection and bottleneck strategy inside; More efficient graph convolution kernels are employed in our model as well.

6 Conclusion and FutureWork

In this paper, we propose a novel deep learning framework STGCN for traffic prediction, integrating graph convolution and gated temporal convolution through spatio-temporal convolutional blocks. Experiments show that our model outperforms other state-of-the-art methods on two real-world datasets, indicating its great potentials on exploring spatiotemporal structures from the input. It also achieves faster training, easier convergences, and fewer parameters with flexibility and scalability. These features are quite promising and practical for scholarly development and large-scale industry deployment. In the future, we will further optimize the network structure and parameter settings. Moreover, our proposed framework can be applied into more general spatiotemporal structured sequence forecasting scenarios, such as evolving of social networks, and preference prediction in recommendation systems, etc.