LSGCN: Long Short-Term Traffic Prediction with Graph Convolutional Networks

1 Introduction

Traffic prediction is a classical spatial-temporal prediction problem whose purpose is to predict the traffic conditions (e.g. vehicle speed) of several future times based on the historical traffic observations (e.g. recorded via sensors of traffic network). The problem has been found useful in many real-world applications such as intelligent route planning, dynamic traffic management, and smart location-based applications [Wu and Tan, 2016]. In general, there are two kinds of traffic prediction tasks according to the length of prediction time, namely the short-term (5∼30 minutes) and long-term (30∼60 minutes) [Ostring and Sirisena, 2001; Vlahogianni et al., 2005]. The traditional methods often adopt the queuing theory, computational simulation and statistics [Ahmed and Cook, 1979; Williams and Hoel, 2003]. Since these methods rely on the stationarity assumption, they fail to capture complex spatial-temporal features for the prediction tasks.

∗Yubao Liu is the corresponding author.

Due to the high nonlinearity and complexity of traffic data, deep learning approaches have attracted much interest in recent years such as convolutional neural network (CNN) and recurrent neural networks(RNN) [Wu and Tan, 2016; Ma et al., 2017; Hochreiter and Schmidhuber, 1997; Xingjian et al., 2015]. In particular, graph convolution networks(GCN) and its variants have been used to traffic prediction tasks and often obtain promising prediction results [Yu et al., 2018; Li et al., 2018; Guo et al., 2019]. However, few methods are satisfied with both long and short-term prediction tasks. For example, STGCN [Yu et al., 2018] adopts the mechanism of iterative prediction. The traffic conditions predicated in the previous iterations are used as the historical observations for the next iterations. Since the historical traffic observations may be not real values, there are errors accumulated for the prediction task. In general, the more network structure layers, the more errors accumulated, especially for the long-term task. On the other hand, ASTGCN [Guo et al., 2019] and DCRNN [Li et al., 2018] adopt the mechanism of non-iterative prediction, where all prediction values for multiple time steps are obtained by one unified evaluation instead of multiple iterations. So, it is hard to give considerations to both long and short-term tasks.

Target at the shortcomings of existing studies, we propose a novel deep learning framework called Long Short-term Graph Convolutional Networks (LSGCN) to tackle both traffic prediction tasks. Intuitively, the mechanism of iterative prediction is good for the simulation of dynamic traffic conditions over time.

So, we also adopt the mechanism of iterative prediction for LSGCN. We try to enhance the performance of LSGCN from two aspects. On the one hand, we construct a simplified network structure with fewer layers and reduce the accumulated errors in each iteration. On the other hand, we design some new network layers to efficiently capture complex spatial-temporal features. Specifically, we propose a spatial gated block in which a new graph attention network called cosAtt and graph convolution networks (GCN) are integrated by the gated form. By cosAtt and GCN, the spatial gated block can precisely extract the spatial location adjacency and similar road conditions of traffic networks. For example, Figure 1 shows an application scenario can be captured by the spatial gated block. Moreover, the graph attention cosAtt enables more stable prediction results.

Our contributions are summarized as follows. (1) We propose a novel deep learning framework LSGCN for both long and short-term traffic prediction tasks. In LSGCN, we adopt the spatial gated block and gated linear units convolution (GLU) to capture the spatial and temporal features, respectively. We propose a new graph attention network cosAtt and integrate both GCN and cosAtt into the spatial gated block. (2) We evaluate our LSGCN on three real-world traffic datasets and the experimental results show that LSGCN outperforms state-of-the-art baselines.

2 Preliminary

2.1 Traffic Prediction Problem

Traffic Network. Traffic network is defined as an undirected graph G = (V,E,W), where V is the set of nodes, E is the set of edges between two nodes, and W ∈ RN×N corresponds to the adjacency matrix of G. In practice, a node may represent a sensor located at the corresponding road of the traffic networks. Each node records some traffic features, such as traffic flow, vehicle speed, and road occupancy, etc.

Problem Definition. For a traffic network, let xit ∈ R represents the traffic feature value of the ith node at time step t, and xt ∈ RN represents the traffic feature values of all nodes at time step t. Given history traffic data X = (x1, x2, ..., xτ)T ∈ RN×τ , the purpose of traffic prediction is to predict the traffic features of all nodes in future Tp time steps, namely Y ∗ = (y1, y2, ..., yTp )T ∈ RN×Tp . Without loss of generality, we consider the feature of vehicle speed in the following.

2.2 Attention on Graphs

The input to graph attention networks (GAT) is a set of node features, Q = {⃗ q1, ⃗ q2, ..., ⃗ qN}, where ⃗ q′i ∈ RF and N is the number of nodes, and F is the number of features in each node. The output is also a new set of node features (of potentially different cardinality F ′ ), Q′ = {⃗ q′1 , ⃗ q′2 , ..., ⃗ q′N }, where

⃗ q′i ∈ RF ′ . The attention coefficient for any pair of ⃗ qi and ⃗ qj is given as follows.

where wi and wj are weight matrix components, and A(·) is the attention mechanism operation function. Then, we normalize the attention coefficient eij among node neighborhoods and achieve the output as follows.

where Ni is the set of neighbours of node i in the graph and σ is an activation function [Velickovic et al., 2017].

3 ProposedModel

3.1 Network Architecture

LSGCN is composed of five layers, namely two gated linear units convolutional layers (GLUs), spatial gated block, convolution-unified layer and fully connection layer. The spatial gated block is between two GLUs as shown in Figure 2. Our network structure has fewer layers compared with STGCN [Yu et al., 2018]. LSGCN adopts the mechanism of iterative prediction as follows. In each iteration, we first obtain H′ = (h′1 , h′2 , ..., h′τ-KT+1 )T ∈ RN×(τ-KT+1)×C1 by the first GLU layer, where KT is the width of 1D convolution kernel and C1 is the channel numbers. Then, we can obtain H′′ = (h′′ 1 , h′′ 2 , ..., h′′ τ-KT+1 )T ∈ RN×(τ-KT+1)×C1 by spatial gated block, which is based on H′ and the adjacency matrix W. Next, H′′ is processed by the second GLU, and we can obtain H′′′ = (h′′′ 1 , h′′′ 2 , ..., h′′′ τ-2×(KT-1) )T ∈ RN×(τ-2×(KT -1))×C2 , where C2 is the second channel numbers. Finally, the output is achieved by the convolution unified layer and fully connection layer, namely Y = (y1)T ∈ RN×1×1 . Note that the obtained Y is added into the input for next iteration. For example, the input for the second iteration is {x2, ..., xi, ..., xτ , y1}. The iteration process is halted after Tp iterations. The adjacent road conditions are important in short-term task, the similar road conditions more so in longterm task. They can be captured by GCN and cosAtt of the network model, respectively.

3.2 Spatial Gated Block for Extracting Spatial Features

We consider two main spatial features, namely spatial location adjacency and road condition similarity. We use GCN to extract the spatial location adjacency and a new graph attention network cosAtt to extract road condition similarity.

Inspired by the sequential gate structure, such as LSTM [Hochreiter and Schmidhuber, 1997] and GRU [Chung et al., 2014], we adopt the gate structure to integrate both components. We use the sigmoid function to map the results of GCN to the interval (0, 1) and control the output of cosAtt. Intuitively, GCN determines how much information generated by cosAtt can flow into the next layer based on the topological structure (i.e., spatial location adjacency) of traffic networks.

As shown in Figure 2, the spatial gated block works as follows. First, we pass the Hl+1 generated by the first GLU and the adjacency matrix W into GCN. The results of GCN then go through the sigmoid activation function. On the other hand, we make a copy of Hl+1 and pass it to cosAtt. Finally, Hl+2 is achieved by the element-wise Hadamard product on the results generated before.

GraphAttention cosAtt. Based on the observation that the roads adjacent to each other in a traffic network often have similar road conditions as shown in Figure 1. We design a new graph attention cosAtt to extract the similar road conditions of traffic networks. In cosAtt, we adopt global graph attention networks to learn the similar conditions of any two roads of traffic network instead of neighbours in graph attention networks (GAT).

Initially, node H = {h1, ..., hi, ..., hN}, hi ∈ RN×T×Ci is passed into cosAtt, where T represents time steps and Ci is input channels. We define cosAtt as follows.

where ˜ Ni is all nodes in graph except node i.

Next, we show the key differences between cosAtt and traditional GAT. First, the weight distribution of cosAtt is used as the output, whereas the weight distribution of GAT is added into the original features. On the other hand, for any given two features hi and hj, the similarity value between them is constant (i.e., cos(hi, hj)). The value of eij is relatively stable and only adjusted by the weight matrix W (i.e., wij). In contrary to cosAtt, the value of eij in GAT may be unstable since we have to learn them by the attention function and the weight matrix W as shown in Eq.(1).

Note that we use the sigmoid instead of the softmax activation function in our model. This is because that the softmax activation function often results in denominator underflow and program crash since the number of neighbors (i.e., all nodes except the target node itself) for each node may be huge.

The details on GCN are as follows. Based on the conception of spectral graph convolution, the graph convolution operator "∗G" can be represented as the multiplication of a signal x ∈ RN with a kernel Θ.

In the equation, graph Fourier basis U ∈ RN×N corresponds to the matrix of eigenvectors of the normalized graph Laplacian L = IN -D- 12WD- 12 = UΛU T ∈ RN×N , where IN is an identity matrix and D ∈ RN×N is the diagonal degree matrix with Dii = ∑j Wij . Λ ∈ RN×N corresponds to the diagonal matrix of eigenvalues of L and filter Θ(Λ) is also a diagonal matrix [Shuman et al., 2013].

Since the computation of Eq.(7) is expensive, we adopt the Chebyshev polynomials approximation in our implementation to speed up the computation of GCN.

where θ ∈ RK is a vector of polynomial coefficients, K is the kernel size of graph convolution, and Tk(˜L) ∈ RN×N corresponds to the Chebyshev polynomial of order k evaluated at the scaled Laplacian ˜L = 2L/λmax - IN. The computation of Eq. (8) takes O(K · |E|) time [Defferrard et al., 2016].

3.3 Gated Linear Units Convolution Layer for Extracting Temporal Features

We use GLU to capture dynamic behaviors of temporal features, which is similar to STGCN [Yu et al., 2018]. As shown in Figure 2, there are two GLUs each of which consists of a 1D convolution with a width-KT kernel and a residual connection.

In general, GLU works as follows. The input is X = {x1, x2, ..., xi, ..., xN}, xi ∈ RN×τ×Ci (Ci = 1 for the first GLU). Next, we use convolutional kernels Θ ∈ RKt×Ci×2Co to obtain the convolutional result Z = [PQ] ∈ RN×(τ-KT+1)×2Co , where Co is the size of the feature set generated by GLU. Note that the number of 1D convolutional kernels is set as 2 · Co. The output through 1D convolutional layer is divided into two equal parts, namely P and Q. P is the output of the first half convolution kernels and Q is of the second half convolution kernels. Then, the element-wise Hadamard product of P and σ(Q) is computed and added into the input of the residual connection. If the number of input dimension is less than that of the output dimension, the input dimension is filled with zero, and vice versa. Finally, we can reduce the time steps to τ -2×(KT -1) (> 0) based on two GLUs.

3.4 Convolution Unified Layer

In the mechanism of iterative prediction, we need to output single prediction value for each time step in each iteration process. So, it is necessary to reduce dimension on time axis. As shown Figure 2, LSGCN adopts the convolution unified layer to merge the τ - 2 × (KT - 1) time steps into single time step with casual convolution. In general, the sequence with τ -2×(KT -1) time steps is a relatively long sequence. For a long sequence, the casual convolution fuse time steps in proportion, so we can obtain a reasonable time step as the output of this layer.

3.5 Loss Function

We use L2 loss to measure the performance of our model which is defined as follows,

where ˆ y(·) is the prediction value, xt+1 denotes the ground truth andWθ represents all trainable parameters.

4 Experiment

4.1 Dataset Description

In the experiment, we use three real-world traffic datasets, namely PeMSD4, PeMSD7 and PeMSD8, which are collected by California Performance of Transportation(PeMS) [Chen et al., 2001] and widely used in the previous studies such as STGCN and ASTGCN [Yu et al., 2018; Guo et al., 2019]. More details for the datasets are in Table 1. The PeMS sensor network is shown in Figure 3.

PeMSD4. It refers to the traffic data in San Francisco Bay Area, with 307 sensors on 29 roads. The dataset spanned from January to February in 2018. The first 47 days are used as training set, and the remaining as validation and test set.

PeMSD7. It refers to the traffic data in District 7 of California, with 228 sensors and the time range is in the weekdays fromMay to June in 2012. The first 34 days are used as training set, and the remaining as validation and test set.

PeMSD8. It refers to the traffic data in San Bernardino from July to August in 2016, with 170 detectors on 8 roads. The first 50 days are used as training set, and the remaining as validation and test set.

4.2 Data Preprocessing

We set the standard time interval as 5 minutes. Therefore, every sensor contains 288 traffic data points per day. We use linear interpolation method to fill the missing values and ZScore method to normalize the input data.

For PeMSD4 and PeMSD8, the weighted adjacency matrix W can be formed as,

where δ is the threshold to control the distribution of W and is set to be 0.1, wij is the edge weight which is related to dij (the distance between station i and j).

For PeMSD7, the weighted adjacency matrix W can be formed as,

where δ and ϵ are the thresholds to control the distribution and sparsity of W and are set to be δ = 0.1 and ϵ = 0.5, respectively. wij is the edge weight which is related to dij (the distance between station i and j).

4.3 Experimental Settings

All experiments are performed on a Linux server (CPU: Intel(R) Xeon(R) CPU E5-2620 v4 @ 2.10GHz, GPU: GeForce RTX 2080 Ti). The grid search strategy is executed to locate the best parameters on validations. All the tests adopt 60 minutes as the history time window, a.k.a. 12 observed data points (τ = 12) are used to forecast traffic conditions in the next 15, 30, 45 and 60 minutes (Tp = 3, 6, 9, 12).

EvaluationMetric &Baselines. We adopt Mean Absolute Errors (MAE), Mean Absolute Percentage Errors (MAPE), and Root Mean Squared Errors (RMSE) to measure the performance of different methods. The baselines are as follows.

• HA: Historical Average. Here, we use the average value of the last 12 times slices to predict the next value.
• ARIMA [Williams and Hoel, 2003]: Auto-Regressive Integrated Moving Average method, which is widely used in time series prediction.

• DCRNN [Li et al., 2018]: Diffusion Convolution Recurrent Neural Network, which combines graph convolution with recurrent neural networks in an encoderdecoder manner.
• STGCN [Yu et al., 2018]: Spatial-Temporal Graph Convolutional Network, which combines graph convolution with gated temporal convolution.
• ASTGCN [Guo et al., 2019]: Attention based SpatialTemporal Graph Convolution Network, which combines the spatial-temporal attention mechanism and the spatial-temporal convolution.

LSGCNModel. The batch size of PeMSD4, PeMSD7 and PeMSD8 are 32, 32 and 16, respectively. The hyperparameters are set as follows. For all datasets, the channels of the first GLU, GCN, cosAtt, the second GLU are 32, 32, 32 and 64, respectively. We set both the graph convolution kernel size K and GLU convolution kernel size Kt to 3. Our model is trained by minimizing the mean square error with RMSprop optimizer for 60 epochs. The initial learning rate is set as 10-3 with a decay rate of 0.7 after every 5 epochs.

4.4 Experiment Results

As shown in Table 2, LSGCN performs well in both longterm and short-term prediction for three evaluation metrics. In detail, in the three datasets, it performs very well, especially in the long-term prediction of PeMSD4, both long-term prediction and short-term prediction of PeMSD7 and PeMSD8. In the short-term prediction of PeMSD4, it also achieves the second best. The results show that LSGCN can efficiently capture the spatial-temporal features for the prediction tasks.

In particular, STGCN is also based on the mechanism of iterative prediction, but it causes more accumulation errors than LSGCN since it consists of more network structure layers.

We can easily observe that the traditional statistical methods (i.e., HA and ARIMA) often have poor performance since they cannot efficiently handle the complex spatial-temporal data.

In general, since there are lots of accumulated errors in STGCN for the prediction tasks, ASTGCN and DCRNN have better performance than STGCN. In detail, STGCN is not better than DCRNN in the short-term tasks and not better than ASTGCN in the long-term tasks. DCRNN adopts diffusion convolution which is beneficial to capture complex spatial topology information. Besides, it can accurately calculate the probability from the target sensor to neighbour sensors by using a finite step random walk to express the diffusion process. Thus, DCRNN has the best performance in the metrics of MAE and MAPE for the complex traffic networks of PeMSD4. But, DCRNN also adopts GRU structure for time series which often causes information loss in the long-term tasks.

ASTGCN considers the periodicity in prediction tasks and various traffic characteristics related to the tasks. So, it performs well in the long-term prediction of PeMSD4 and PeMSD8. But, ASTGCN is not better than STGCN in the long-term prediction of PeMSD7. This is because that the neighbor information is beneficial to the prediction tasks, which is removed by the threshold from PeMSD7, and saved in PeMSD4 and PeMSD8.

Test in extreme case. In particular, we test our LSGCN in some extreme cases, namely morning peak and evening rush hours. As shown in Figure 4, Due to the efficient spatial gated block, LSGCN is capable of fast response to the dynamic changes in extreme cases. The trend of rush hours captured by LSGCN is more accurate than the other methods. Besides, the ending of the rush hours detected by LSGCN is earlier than the others.

Training Efficiency and Generalization. We plot the RMSE and MAE of the test set of PeMSD4 during the training process to further investigate the performance of different deep learning models. As shown in Figure 5, it is obvious that our LSGCN can achieve faster training and easier convergence than DCRNN and ASTGCN. Specifically, LSGCN and STGCN need almost the same training time, about 1,000 seconds, whereas DCRNN and ASTGCN need about 10,000 and 25,000 seconds, respectively. This is because that more parameters are used for the training process of DCRNN and ASTGCN.

Effect of cosAtt. By replacing the proposed cosAtt of LSGCN with traditional graph attention, we can obtain a modified version called LSGCN(GAT). We compare LSGCN and LSGCN(GAT) to test the changes in prediction results. For each prediction task, both methods are executed 10 times with the same hyperparameters. Then, the maximum and minimum values among all evaluation results for each metric are reported, respectively. As shown in Table 3, the metric value changes for LSGCN are often smaller than LSGCN(GAT), so cosAtt enables more stable prediction results.

5 RelatedWork

Deep learning models. Some solutions for traffic prediction are proposed based on deep learning models. Zhang et al. [2016] convert the road network to a regular 2-D grid and apply CNN to capture adjacent relations among the traffic network. Yao et al. [2018] proposed a method to predict traffic by integrating CNN and long-short term memory (LSTM) to jointly model both spatial and temporal dependencies. Different from these methods, both GCN and GAT are integrated in our proposed model.

Graph convolutional networks(GCN). Bruna et al. [2013] propose GCN based on the spectral graph theory. Defferard et al. [2016] and Kipf et al. [2016] propose some improve methods for the computation of GCN. Based on GCN, Yu et al. [2018] propose STGCN to tackle the time series prediction problem in the traffic domain. Wu et al.[2019] propose Graph Wavenet to precisely capture the hidden spatial dependency in the data. In addition to GCN, our model contains an additional GAT which is different from these methods.

Attention mechanism. It has been widely utilized in various domains such as natural language processing, speech recognition and image caption [Vaswani et al., 2017; Shen et al., 2018]. Recently, researchers apply attention mechanism to graph [Velickovic et al., 2017; Liu et al., 2018] and traffic prediction. Liang et al. [2018] propose a novel multi-level attention-based network. Guo et al. [2019] propose ASTGCN and Zheng et al. [2019] propose GMAN. Different from these methods, our graph attention is based on the road condition similarity.

6 Conclusion

In this paper, we propose a new graph convolutional networks model LSGCN for long and short-term traffic prediction. In LSGCN, we integrate both a new graph attention network cosAtt and GCN to precisely capture the spatial features and at the same adopt the GLU to capture the temporal features. The experiments on real traffic networks verify the effectiveness of LSGCN. In the future, we will consider our proposed model for more general spatio-temporal structured sequence forecasting such as preference prediction in recommendation systems.

Acknowledgements

This paper is supported by the National Nature Science Foundation of China (61572537, U1501252).