{'fraction_non_alphanumeric': 0.04066236656482215, 'fraction_numerical': 0.01388103051563502, 'mean_word_length': 4.677087794432548, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 1, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
GMAN: A Graph Multi-Attention Network for Traffic Prediction

Long-term traffic prediction is highly challenging due to the complexity of traffic systems and the constantly changing nature of many impacting factors. In this paper, we focus on the spatio-temporal factors, and propose a graph multi-attention network (GMAN) to predict traffic conditions for time steps ahead at different locations on a road network graph. GMAN adapts an encoder-decoder architecture, where both the encoder and the decoder consist of multiple spatio-temporal attention blocks to model the impact of the spatio-temporal factors on traffic conditions. The encoder encodes the input traffic features and the decoder predicts the output sequence. Between the encoder and the decoder, a transform attention layer is applied to convert the encoded traffic features to generate the sequence representations of future time steps as the input of the decoder. The transform attention mechanism models the direct relationships between historical and future time steps that helps to alleviate the error propagation problem among prediction time steps. Experimental results on two real-world traffic prediction tasks (i.e., traffic volume prediction and traffic speed prediction) demonstrate the superiority of GMAN. In particular, in the 1 hour ahead prediction, GMAN outperforms state-of-the-art methods by up to 4% improvement in MAE measure. The source code is available at https://github.com/zhengchuanpan/GMAN.


Introduction
Traffic prediction aims to predict the future traffic conditions (e.g., traffic volume or speed) in road networks based on historical observations (e.g., recorded via sensors). It plays a significant role in many real-world applications. For example, the accurate traffic prediction can help transportation agencies better control the traffic to reduce traffic congestion (Lv et al. 2018;Zheng et al. 2019).
The traffic conditions at nearby locations are expected to impact each other. To capture such spatial correlations, Convolutional neural networks (CNN) are widely used (Zhang, Zheng, and Qi 2017;Yao et al. 2018;. Meanwhile, The traffic condition at a location is also correlated with its historical observations. Recurrent neural networks (RNN) are Dynamic spatial correlations: sensors 1 and 2 are not always highly correlated, although they are close in the road network; non-linear temporal correlations: the traffic condition of sensor 3 at time step t + l + 1 may be more correlated to that of distant time steps (e.g., t − 1) rather than recent time steps (e.g., t + l).
widely applied to model such temporal correlations (Ma et al. 2015;Song, Kanasugi, and Shibasaki 2016). Recent studies formulate the traffic prediction as a graph modeling problem, since the traffic conditions are restricted on road network graphs (Li et al. 2018b;Yu, Yin, and Zhu 2018;Wu et al. 2019b). Using graph convolutional networks (GCN) (Defferrard, Bresson, and Vandergheynst 2016), these studies achieve promising results for short-term (5 ∼ 15 minutes ahead) traffic prediction. However, the longterm (up to a few hours ahead (Hou and Li 2016)) traffic prediction still lacks a satisfactory progress in the literature, mainly due to the following challenges. 1) Complex spatio-temporal correlations. • Dynamic spatial correlations. As shown in Figure 1, the correlations of traffic conditions among sensors in a road network change significantly over time (e.g., before and during peak hours). How to dynamically select relevant sensors' data to predict a target sensor's traffic conditions in long-term horizon is a challenging issue. • Non-linear temporal correlations. Also in Figure 1, the traffic condition at a sensor may fluctuate tremendously and suddenly (e.g., because of an accident), affecting the correlations between different time steps. How to adaptively model the non-linear temporal correlations when the time goes further into the future remains a challenge.
2) Sensitivity to error propagation. In the long-term horizon, small errors in each time step may amplify when predictions are made further into the future. Such error propagations make predictions into far future highly challenging.
To address the aforementioned challenges, we propose a Graph Multi-Attention Network (GMAN) to predict traffic conditions on a road network graph over time steps ahead. Here, the traffic conditions refer to observations over a traffic system that can be reported in numeric values. For illustration purpose, we focus on traffic volume and traffic speed predictions, although our model could be applied to predictions of other numerical traffic data.
GMAN follows the encoder-decoder architecture, where the encoder encodes the input traffic features and the decoder predicts the output sequence. A transform attention layer is added between the encoder and the decoder to convert the encoded historical traffic features to generate future representations. Both the encoder and the decoder are composed of a stack of ST-Attention blocks. Each ST-Attention block is formed by a spatial attention mechanism to model the dynamic spatial correlations, a temporal attention mechanism to model the non-linear temporal correlations, and a gated fusion mechanism to adaptively fuse the spatial and temporal representations. The transform attention mechanism models direct relationships between historical and future time steps to alleviate the effect of error propagation. Experiments on two real-world datasets confirm that GMAN achieves state-of-the-art performances.
The contributions of this work are summarized as follow: • We propose spatial and temporal attention mechanisms to model the dynamic spatial and non-linear temporal correlations, respectively. Moreover, we design a gated fusion to adaptively fuse the information extracted by spatial and temporal attention mechanisms. • We propose a transform attention mechanism to transform the historical traffic features to future representations. This attention mechanism models direct relationships between historical and future time steps to alleviate the problem of error propagation. • We evaluate our graph multi-attention network (GMAN) on two real-world traffic datasets, and observe 4% improvement and superior fault-tolerance ability over stateof-the-art baseline methods in 1 hour ahead prediction.

Related Work
Traffic Prediction Traffic prediction has been extensively studied in past decades. Deep learning approaches (e.g., long short-term memory (LSTM) (Ma et al. 2015)) show more superior performance in capturing temporal correlations in traffic conditions, compared with traditional timeseries methods (e.g., auto-regressive integrated moving average (ARIMA) (Makridakis and Hibon 1997)) and machine learning models (e.g., support vector regression (SVR) (Wu, Ho, and Lee 2004), k-nearest neighbor (KNN) (Zheng and Su 2014)). To model spatial correlations, researchers apply convolutional neural networks (CNN) to capture the dependencies in Euclidean space (Zhang, Zheng, and Qi 2017;Yao et al. 2018;. Recent studies formulate the traffic prediction on graphs and employ graph convolutional networks (GCN) to model the non-Euclidean correlations in the road network (Li et al. 2018b;Lv et al. 2018). These graphbased models generate multiple steps ahead predictions via a step-by-step approach and may suffer from error propagation between different prediction steps.
Deep Learning on Graphs Generalizing neural networks to graph-structured data is an emerging topic (Bronstein et al. 2017;Wu et al. 2019a). A line of studies generalize CNN to model arbitrary graphs on spectral (Defferrard, Bresson, and Vandergheynst 2016;Kipf and Welling 2017;Li et al. 2018a) or spatial (Atwood and Towsley 2016;Hamilton, Ying, and Leskovec 2017;Chen, Ma, and Xiao 2018) perspective. Another line of studies focus on graph embedding, which learns low-dimensional representations for vertices that preserve the graph structure information (Grover and Leskovec 2016;Cui et al. 2019). (Wu et al. 2019b) integrates WaveNet (van den Oord et al. 2016) into GCN for spatiotemporal modeling. As it learns static adjacency matrices, this method faces difficulties in capturing dynamic spatial correlations.
Attention Mechanism Attention mechanisms have been widely applied to various domains due to their high efficiency and flexibility in modeling dependencies (Vaswani et al. 2017;Shen et al. 2018;Du et al. 2018). The core idea of attention mechanisms is to adaptively focus on the most relevant features according to the input data (Cheng et al. 2018). Recently, researchers apply attention mechanisms to graph-structured data (Veličković et al. 2018) to model spatial correlations for graph classification. We extend the attention mechanism to graph spatio-temporal data prediction.

Preliminaries
We denote a road network as a weighted directed graph G = (V, E, A). Here, V is a set of N = |V| vertices representing points (e.g., traffic sensors) on the road network; E is a set of edges representing the connectivity among vertices; and A ∈ R N ×N is the weighted adjacency matrix, where A vi,vj represents the proximity (measured by the road network distance) between vertex v i and v j . The traffic condition at time step t is represented as a graph signal X t ∈ R N ×C on graph G, where C is the number of traffic conditions of interest (e.g., traffic volume, traffic speed, etc.).
Problem Studied Given the observations at N vertices of historical P time steps X = (X t1 , X t2 , ..., X t P ) ∈ R P ×N ×C , we aim to predict the traffic conditions of the next Q time steps for all vertices, denoted asŶ = (X t P +1 ,X t P +2 , ...,X t P +Q ) ∈ R Q×N ×C . L ST-Attention blocks (STAtt Block) with residual connections (He et al. 2016). Each ST-Attention block is composed of spatial and temporal attention mechanisms with gated fusion. Between the encoder and the decoder, a transform attention layer is added to the network to convert the encoded traffic features to the decoder. We also incorporate the graph structure and time information into multi-attention mechanisms through a spatio-temporal embedding (STE). In addition, to facilitate the residual connection, all layers produce outputs of D dimensions. The modules are detailed next.

Spatio-Temporal Embedding
Since the evolution of traffic conditions is restricted by the underlying road network (Lv et al. 2018), it is crucial to incorporate the road network information into prediction models. To this end, we propose a spatial embedding to encode vertices into vectors that preserve the graph structure information. Specifically, we leverage the node2vec approach (Grover and Leskovec 2016) to learn the vertex representations. In addition, to co-train the pre-learned vectors with the whole model, these vectors are fed into a two-layer fully-connected neural network. Then, we obtain the spatial embedding, represented as e S vi ∈ R D , where v i ∈ V. The spatial embedding only provides static representations, which could not represent the dynamic correlations among traffic sensors in the road network. We thus further propose a temporal embedding to encode each time step into a vector. Specifically, let a day be with T time steps. We encode the day-of-week and time-of-day of each time step into R 7 and R T using one-hot coding, and concatenate them into a vector R T +7 . Next, we apply a two-layer fully-connected neural network to transform the time feature to a vector R D . In our model, we embed time features for both historical P and future Q time steps, represented as e T tj ∈ R D , where t j = t 1 , ..., t P , ..., t P +Q .
To obtain the time-variant vertex representations, we fuse the aforementioned spatial embedding and temporal embedding as spatio-temporal embedding (STE), as shown in Figure 2(b). Specifically, for vertex v i at time step t j , the STE is defined as e vi,tj = e S vi + e T tj . Therefore, the STE of N vertices in P + Q time steps is represented as E ∈ R (P +Q)×N ×D . The STE contains both graph structure and time information, and it will be used in spatial, temporal and transform attention mechanisms.

ST-Attention Block
As shown in Figure 2(c), the ST-Attention block includes a spatial attention, a temporal attention and a gated fusion. We denote the input of the l th block as H (l−1) , where the hidden state of vertex v i at time step t j is represented as h vi,tj , respectively. After the gated fusion, we obtain the output of the l th block, represented as H (l) .
For illustration purpose, we denote a non-linear transformation as: where W, b are learnable parameters, and ReLU (Nair and Hinton 2010) is the activation function.

Spatial Attention
The traffic condition of a road is affected by other roads with different impacts. Such impact is highly dynamic, changing over time. To model these properties, we design a spatial attention mechanism to adaptively capture the correlations between sensors in the road network. The key idea is to dynamically assign different weights to different vertices (e.g., sensors) at different time steps, as shown in Figure 3. For vertex v i at time step t j , we compute a weighted sum from all vertices: where V denotes a set of all vertices, α vi,v is the attention score indicating the importance of vertex v to v i , and the summation of attention scores equals to 1: v∈V α vi,v = 1. At a certain time step, both the current traffic conditions and the road network structure could affect the correlations between sensors. For example, a congestion on a road may significantly affect the traffic conditions of its adjacent roads. Motivated by this intuition, we consider both traffic features and the graph structure to learn the attention score. Specifically, we concatenate the hidden state with the spatiotemporal embedding, and adopt the scaled dot-product approach (Vaswani et al. 2017) to compute the relevance between vertex v i and v:  where represents the concatenation operation, •, • denotes the inner product operator, and 2D is the dimension of h (l−1) vi,tj e vi,tj . Then, s vi,v is normalized via softmax as: After the attention score α vi,v is obtained, the hidden state can be updated through Equation 2.
To stabilize the learning process, we extend the spatial attention mechanism to be multi-head ones (Vaswani et al. 2017). Specifically, we concatenate K parallel attention mechanisms with different learnable projections: where f When the number of vertices N is large, the time and memory consumption is heavy as we need to compute N 2 attention scores. To address this limitation, we further propose a group spatial attention, which contains intra-group spatial attention and inter-group spatial attention, as shown in Figure 4.  Figure 5: The temporal attention mechanism models the non-linear correlations between different time steps.
We randomly partition N vertices into G groups, where each group contains M = N/G vertices (padding can be applied if necessary). In each group, we compute the intragroup attention to model the local spatial correlations among vertices through Equations 5, 6 and 7, where the learnable parameters are shared across groups. Then, we apply the max-pooling approach in each group to obtain a single representation for each group. Next, we compute the inter-group spatial attention to model the correlations between different groups, producing a global feature for each group. The local feature is added to the corresponding global feature as the final output.
In the group spatial attention, we need to compute GM 2 + G 2 = N M + (N/M ) 2 attention scores at each time step. By letting the gradient to zero, we know when M = 3 √ 2N , the number of attention scores reaches its minimum 2 −1/3 N 4/3 N 2 .

Temporal Attention
The traffic condition at a location is correlated with its previous observations, and the correlations vary over time steps non-linearly. To model these properties, we design a temporal attention mechanism to adaptively model the non-linear correlations between different time steps, as illustrated in Figure 5. Note that the temporal correlation is influenced by both the traffic conditions and the corresponding time context. For example, a congestion occurring in morning peak hours may affect the traffic for a few hours. Thus, we consider both traffic features and time to measure the relevance between different time steps. Specifically, we concatenate the hidden state with the spatiotemporal embedding, and adopt the multi-head approach to compute the attention score. Formally, considering vertex v i , the correlation between time step t j and t is defined as: where u (k) tj ,t denotes the relevance between time step t j and t, β two different learnable transforms, N tj denotes a set of time steps before t j , i.e., only considers information from time steps earlier than the target step to enable causality. Once the attention score is obtained, the hidden state of vertex v i at time step t j is updated as follows: t,3 (•) represents a non-linear projection. The learnable parameters in Equations 8, 9 and 10 are shared across all vertices and time steps with paralleled computing.

Gated Fusion
The traffic condition of a road at a certain time step is correlated with both its previous values and other roads' traffic conditions. As shown in Figure 2(c), we design a gated fusion to adaptively fuse the spatial and temporal representations. In the l th block, the outputs of the spatial and temporal attention mechanisms are represented as H T are fused as: where W z,1 ∈ R D×D , W z,2 ∈ R D×D and b z ∈ R D are learnable parameters, represents the element-wise product, σ(•) denotes the sigmoid activation, z is the gate. The gated fusion mechanism adaptively controls the flow of spatial and temporal dependencies at each vertex and time step.

Transform Attention
To ease the error propagation effect between different prediction time steps in the long time horizon, we add a transform attention layer between the encoder and the decoder. It models the direct relationship between each future time step and every historical time step to convert the encoded traffic features to generate future representations as the input of the decoder. As shown in Figure 6, for vertex v i , the relevance between the prediction time step t j (t j = t P +1 , ..., t P +Q ) and the historical time step t (t = t 1 , ..., t P ) is measured via the spatio-temporal embedding: With the attention score γ (k) tj ,t , the encoded traffic feature is transformed to the decoder by adaptively selecting relevant features across all historical P time steps: Equations 13, 14, and 15 can be computed in parallel across all vertices and time steps, sharing the learnable parameters.

Encoder-Decoder
As shown in Figure 2(a), GMAN is an encoder-decoder architecture. Before entering into the encoder, the historical observation X ∈ R P ×N ×C is transformed to H (0) ∈ R P ×N ×D using fully-connected layers. Then, H (0) is fed into the encoder with L ST-Attention blocks, and produces an output H (L) ∈ R P ×N ×D . Following the encoder, a transform attention layer is added to convert the encoded feature H (L) to generate the future sequence representation H (L+1) ∈ R Q×N ×D . Next, the decoder stacks L ST-Attention blocks upon H (L+1) , and produces the output as H (2L+1) ∈ R Q×N ×D . Finally, the fully-connected layers produce the Q time steps ahead predictionŶ ∈ R Q×N ×C . GMAN can be trained end-to-end via back-propagation by minimizing the mean absolute error (MAE) between predicted values and ground truths: where Θ denotes all learnable parameters in GMAN.

Experiments Datasets
We evaluate the performance of GMAN on two traffic prediction tasks with different road network scales: (1) traffic volume prediction on the Xiamen dataset (Wang et al. 2017), which contains 5 months of data recorded by 95 traffic sensors ranging from August 1st, 2015 to December 31st, 2015 in Xiamen, China; (2) traffic speed prediction on the PeMS dataset (Li et al. 2018b)), which contains 6 months of data recorded by 325 traffic sensors ranging from January 1st, 2017 to June 30th, 2017 in the Bay Area. The distributions of sensors in two datasets are visualized in Figure 7. Data Preprocessing We adopt the same data preprocessing procedures as in (Li et al. 2018b). In both datasets, a time step denotes 5 minutes and the data is normalized via the Z-Score method. We use 70% of the data for training, 10% for validation, and 20% for testing. To construct the road network graph, each traffic sensor is considered as a vertex and we compute the pairwise road network distances between sensors. Then, the adjacency matrix is defined as: where d vi,vj is the road network distance from sensor v i to v j , σ is the standard deviation, and (assigned to 0.1) is the threshold to control the sparsity of the adjacency matrix A.

Experimental Settings
Metrics We apply three widely used metrics to evaluate the performance of our model, i.e., Mean Absolute Error (MAE), Root Mean Squared Error (RMSE), and Mean Absolute Percentage Error (MAPE).
Hyperparameters Following the previous works (Li et al. 2018b;Wu et al. 2019b), we use P = 12 historical time steps (1 hour) to predict the traffic conditions of the next Q = 12 steps (1 hour). We train our model using Adam optimizer (Kingma and Ba 2015) with an initial learning rate of 0.001. In the group spatial attention, we partition the vertices into G = 19 groups in the Xiamen dataset and G = 37 groups in the PeMS dataset, respectively. The number of traffic conditions on both datasets is C = 1. Totally, there are 3 hyperparameters in our model, i.e., the number of ST-Attention blocks L, the number of attention heads K, and the dimensionality d of each attention head (the channel of each layer D = K ×d). We tune these parameters on the validation set, and observe the best performance on the setting L = 3, K = 8, and d = 8 (D = 64).
For models ARIMA, SVR, FNN, and FC-LSTM, we use the settings suggested by (Li et al. 2018b). For models STGCN, DCRNN, and Graph WaveNet, we use the default settings from their original proposals.

Experimental Results
Forecasting Performance Comparison Table 1 shows the comparison of different methods for 15 minutes (3 steps), 30 minutes (6 steps), and 1 hour (12 steps) ahead predictions on two datasets. We observe that: (1) deep learning approaches outperform traditional time series methods and machine learning models, demonstrating the ability of deep neural networks in modeling non-linear traffic data; (2) among deep learning methods, graph-based models including STGCN, DCRNN, Graph WaveNet, and GMAN generally perform better than FC-LSTM, indicating the road net- work information is essential for traffic prediction; and (3) GMAN achieves state-of-the-art prediction performances and the advantages are more evident in the long-term horizon (e.g., 1 hour ahead). We argue that the long-term traffic prediction is more beneficial to practical applications, e.g., it allows transportation agencies to have more time to take actions to optimize the traffic according to the prediction.
We also use the T-Test to test the significance of GMAN in 1 hour ahead prediction compared to Graph WaveNet. The p-value is less than 0.01, which demonstrates that GMAN statistically outperforms Graph WaveNet.
Fault Tolerance Comparison The real-time values of traffic conditions may be missing partially, due to sensor malfunction, packet losses during data transmission, etc. To evaluate the fault-tolerance ability, we randomly drop a fraction η (fault-ratio, ranging from 10% to 90%) of historical observations (i.e., randomly replace η×N ×P ×C input values with zeros) to make 1 hour ahead predictions. As shown in Figure 8, GMAN is more fault tolerant than state-of-theart methods. This shows that GMAN can capture the complex spatio-temporal correlations from the "contaminated" traffic data and adjust the dependencies from observations to future time steps.

Effect of Each Component
To investigate the effect of each component in our model, we evaluate four variants by removing spatial attention, temporal attention, gated fusion, and transform attention from GMAN separately, which are named as GMAN-NS, GMAN-NT, GMAN-NG, and GMAN-NTr respectively. Figure 9 presents the MAE in each prediction step of GMAN and the four variants. We observe that GMAN consistently outperforms GMAN-NS, GMAN-NT, and GMAN-NG, indicating the effectiveness of spatial attention, temporal attention, and gated fusion in modeling the complex spatio-temporal correlations. Moreover, GMAN performs better than GMAN-NTr, especially in the long-term horizon, demonstrating that the transform attention mechanism effectively eases the effect of error propagation.
Computation Time We present the training time and inference time of STGCN, DCRNN, Graph WaveNet, and GMAN on the PeMS dataset in Table 2. During the training phase, GMAN has a similar speed with Graph WaveNet.   DCRNN runs much slower than other methods due to the time-consuming sequence learning in recurrent networks. STGCN is the most efficient but shows poor prediction performance (Table 1). In the inference phase, we report the total time cost on the validation data. STGCN and DCRNN is less efficient as they need iterative computation to generate the 12 prediction results. GMAN and Graph WaveNet could produce 12 steps ahead predictions in one run and thus take less time for inference. In respect of the second best model Graph WaveNet as suggested in Table 1, GMAN compares favorably to Graph WaveNet in the long-term (e.g., 1 hour ahead) traffic predictions (Table 1) with similar computation costs for both training and inference (Table 2).

Conclusion
We proposed a graph multi-attention network (GMAN) to predict traffic conditions for time steps ahead on a road network graph. Specifically, we proposed spatial and temporal attention mechanisms with gated fusion to model the complex spatio-temporal correlations. We further designed a transform attention mechanism to ease the effect of error propagation to improve the long-term prediction performance. Experiments on two real-world datasets show that GMAN achieves state-of-the-art results, and the advantages are more evident as the predictions are made into far future. In the future, we will apply GMAN to other spatio-temporal prediction tasks, such as water consumption prediction.