---
abstract: 'Traffic forecasting has emerged as a core component of intelligent transportation systems. However, timely accurate traffic forecasting, especially long-term forecasting, still remains an open challenge due to the highly nonlinear and dynamic spatial-temporal dependencies of traffic flows. In this paper, we propose a novel paradigm of Spatial-Temporal Transformer Networks (STTNs) that leverages dynamical directed spatial dependencies and long-range temporal dependencies to improve the accuracy of long-term traffic forecasting. Specifically, we present a new variant of graph neural networks, named spatial transformer, by dynamically modeling directed spatial dependencies with self-attention mechanism to capture real-time traffic conditions as well as the directionality of traffic flows. Furthermore, different spatial dependency patterns can be jointly modeled with multi-heads attention mechanism to consider diverse relationships related to different factors (e.g. similarity, connectivity and covariance). On the other hand, the temporal transformer is utilized to model long-range bidirectional temporal dependencies across multiple time steps. Finally, they are composed as a block to jointly model the spatial-temporal dependencies for accurate traffic prediction. Compared to existing works, the proposed model enables fast and scalable training over a long range spatial-temporal dependencies. Experiment results demonstrate that the proposed model achieves competitive results compared with the state-of-the-arts, especially forecasting long-term traffic flows on real-world PeMS-Bay and PeMSD7(M) datasets.'
author:
- 'Mingxing Xu, Wenrui Dai, Chunmiao Liu, Xing Gao, Weiyao Lin, Guo-Jun Qi, Hongkai Xiong'
bibliography:
- 'STTN.bib'
title: 'Spatial-Temporal Transformer Networks for Traffic Flow Forecasting'
---

traffic flow predictions, spatial-temporal dependencies, dynamcial graph neural networks, transformer.

Introduction
============

  -----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
        ![(a) Traffic forecasting models with joint spatial temporal dependencies. (b) Evolution of the traffic conditions spatial distribution. []{data-label="fig0"}](model.pdf "fig:"){width="1\columnwidth" height="0.25\columnwidth"}
                                                                                                                        (a)
   ![(a) Traffic forecasting models with joint spatial temporal dependencies. (b) Evolution of the traffic conditions spatial distribution. []{data-label="fig0"}](Dynamical_spatial.pdf "fig:"){width="1\columnwidth" height="0.6\columnwidth"}
                                                                                                                        (b)
  -----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

  ----------------------------------------------------------------------- --------------------------------------------------------------------------------
   ![image](Shortv.pdf){width="1\columnwidth" height="0.75\columnwidth"}   ![image](Longv_full_loss.pdf){width="1\columnwidth" height="0.75\columnwidth"}
                                    (a)                                                                         (b)
  ----------------------------------------------------------------------- --------------------------------------------------------------------------------

the deployment of affordable traffic sensor technologies over the last few years, the exploding traffic data have been bringing us to the era of big data of transportation. Intelligent Transportation System (ITS) [@mori2015review] is thus developed to leverage transportation big data for efficient urban traffic controlling and planning. As a core component of ITS, accurate traffic forecasting in a timely fashion has attracted increasing attentions.

In traffic forecasting, the future traffic conditions (e.g. speeds, volumes and density) of a node are predicted from its historical traffic data as well as its neighbors. Thus, it is important for a forecasting model to effectively and efficiently capture the spatial and temporal dependencies. Generally, traffic forecasting can be classified into two scales: short-term ($\leq 30$ min) and long-term ($\geq 30$ min). Previous approaches such as time-series models [@liu2011discovering] and Kilman filtering models [@lippi2013short] are mostly focus on short-term forecasting and perform quiet well. However, these models are typically based on the stationary assumption which is commonly impractical in long-term forecasting as the traffic flows are naturally highly dynamical. Furthermore, they fail to jointly capture the spatio-temporal correlations in the traffic flows. So that these model fail to effectively forecast long-term traffic flows.

Naturally, traffic networks can be represented as graphs in which the nodes represent traffic sensors and the edges together with its weights are determined by the connectivity as well as Euclidean distances among sensors. Thus traffic flows can be viewed as graph signals evolving with time. As graph neural networks [@atwood2016diffusion] [@defferrard2016convolutional] [@kipf2017semi] have show its power in processing graph-represented data, recent works tend to combine graph neural networks with sequence-learning model to jointly capture spatio-temporal correlations and improve the performance in both short-term and long-term forecasting. [@yu2018spatio] and [@li2018dcrnn_traffic] are the first two graph-based traffic forecasting models. They largely improve the model performance by introducing the inherent graph topology of a traffic network into sequence-learning models. They integrate spatial-based [@atwood2016diffusion] or spectral-based [@defferrard2016convolutional] Graph Convolutional Networks (GCNs) with convolution-based [@gehring2017convolutional] or Recurrent-neural-networks (RNNs)-based sequence learning models to jointly capture the spatial and temporal dependencies.

However, they have some significant limitations that could be further improved especially for long-term forecasting.

From the perspective of spatial dependencies, the spatial dependencies are dynamical and the dynamics result from two aspects. On one hand, the spatial dependencies between two sensors are influenced by their connectivity and distance. The former one indicates that whether there may be dependencies between them, while the latter one together with the real-time speed determines when the dependencies will be evoked, thus the spatial dependencies should be evolving with time. In fact, this kind of dynamic is a characteristic of traffic forecasting task. As shown in Fig.1 (a), for simplicity, we assume the traffic speeds keep the same across different time steps and all connected sensors are interacted with each other. Taking the central purple node for example, the spatial dependencies between the central node with its neighbor nodes are evolving with time, and the influence of remote nodes will provoked after several time steps while it is short for the nearest nodes to influence it. On the other hand, in real-world traffic networks, the spatial dependencies are inherently dynamical which are influenced by many factors such as traffic accidents, weather conditions as well as rush hours. As shown in Fig.1(b), the spatial patterns of traffic flows change significantly as time goes by. Thus we argue that an effective traffic forecasting model should be able to model dynamical spatial dependencies. Furthermore, the influence of upstream and downstream traffic flows is also quite different, thus the spatial dependencies should be modeled as directed.

To address this limitation, we propose a novel paradigm of self-attention based graph neural network, named [*spatial transformer*]{} to dynamically learn directed spatial dependencies by considering the real-time traffic conditions, connectivity and distance among sensors as well as traffic flow directions. We first enhance the node features with spatial and temporal positional embedding to incorporate the connectivity, distance as well as time information into each node, then several latent high-dimensional subspace are learned, in which spatial dependencies are dynamically computed to reflect the time-varying directed dependencies among nodes. Furthermore, through the self-attention mechanism, we can capture both local and global dependencies beyond adjacent nodes, thereby reflecting the hidden long-range patterns evolving over time, which enable our model to better capture sharp traffic flow changes. To further incorporate fixed spatial dependencies among sensors into our model, we employ fixed graph convolutions in each spatial transformer and balance it with the learned dynamical spatial dependencies through a gate mechanism.

Long-range temporal dependencies also play an indispensable role traffic forecasting which are usually ignored by previous models. As illustrated in Fig.1(a), in different time steps, there are different spatial dependencies that will be evoked, thus limited range of temporal dependencies will result in significant information loss, leading to poor performance. Furthermore, most existing methods forecast traffic flows in an auto-regressive fashion. Thus, the error-prone predictions are incorporated into the inputs along with previous observations to make further predictions, resulting in an quick error accumulation especially for long-term forecasting. As demonstrated in Fig.2 (a), short-range dependencies may not severely influence the performance of short-term forecasting, as all the observations used for predictions are error-free. However, the long-term forecasting will be significantly degraded, as predictions can only made based on error-prone previous predictions through short-range dependencies, thus resulting in the quick propagation of prediction errors. In this paper, we proposed to address this problem with an effective modeling of long-range temporal dependencies as well as predicting multi-step results at the same time, as shown in Fig.2(b). One one hand, more information is utilized to make predictions. On the other hand, past temporal context instead of error-prone predictions can be directly leveraged to make multi-step predictions, bypassing the auto-regressive manner, the error of earlier predictions will not be propagated to further predictions.

Inspired by the newly proposed transformer [@NIPS2017_7181] for efficiently and efficiently modeling long-range dependencies. We develop a temporal transformer to capture dynamical long-range temporal dependencies in traffic flows to directly forecast multi-steps traffic conditions, bypassing the auto-regressive process. Specifically, on one hand, in each temporal transformer layer, each step in a sequence can attend to the context of all other steps to customize its long-range dependencies in a time-varying fashion. Thus, we can model long-range temporal dependencies in each layer. In contrast to the RNNs-based or convolution-based models, it also enables more parallelization of long-range dependencies, facilitating a more efficient model training. One the other hand, we can directly scaled to long-sequence without increasing model depth and complexity.

In this paper, we seek to address several challenges facing the traffic forecasting problem, and propose a novel paradigm of Spatial Temporal Transformer Networks (STTNs). Our contributions are summarized below.

-   We propose a novel paradigm of Spatial Temporal Transformer Networks (STTNs) that can dynamically model long-range spatial-temporal dependencies.

-   A new variant of graph neural network named [*spatial transformer*]{} is developed to model the time-varying directed spatial dependencies by dynamically attending to hidden spatial patterns of traffic flows.

-   A temporal transformer that enables an efficient parallelization of long-range temporal dependencies is also developed.

This paper is structured as follows. In section II, we briefly review the existing spatial and temporal dependencies modeling approaches. In section III, we formally formulate the traffic forecasting problem as a spatial-temporal graph prediction problem. Then, in section IV, we present the proposed Spatial temporal networks for traffic forecasting, and elaborate the components. In Section V, we conduct extensive experiments on real-world traffic datasets and make comparison with state-of-the-arts. Finally, we conclude our paper and present our further work in section VI.

Related Work
============

In traffic flows forecasting, how to effectively and efficiently model spatial and temporal dependencies is the core problem. In this section, we briefly review the existing approaches for spatial and temporal dependencies modeling in traffic flow forecasting.

Spatial dependencies modeling
-----------------------------

The earliest traffic flows forecasting models are statistic-based or neural-network-based models. For statistic-based model, such as autoregressive integrated moving average (ARIMA)[@min2011real] and Bayesian networks [@wang2014new], spatial dependencies are modeled from a probabilistic view.Although they help to analyze the uncertainty within traffic flows, their linear natures impedes them to effectively model the highly-nonlinearity within traffic flows. Neural networks based models are more capable to capture the nonlinearity of traffic flows, however, their fully connected structures are expensive in both computational and memory. Furthermore, the lack of assumptions make it impossible to capture the complicated spatial patterns in traffic flows.

With the development of convolutional neural networks (CNNs), they have shown powerful feature extraction abilities in many applications[@gehring2017convolutional] [@Krizhevsky:2012:ICD:2999134.2999257] [@long2015fully], thus attracting much interests to apply them into traffic forecasting area. [@ma2017learning] [@zhang2017deep] adopt CNNs to extract the spatial features in which traffic networks are converted to regular grids. However, traffic networks are inherently irregular, so the conversion will loss the inherent topology information within traffic networks. Graph neural networks (GNNs) [@scarselli2008graph] [@gilmer2017neural] are latter proposed to generalize the deep learning to non-Euclidean domain. As a variant of GNNs, Graph convolution networks (GCNs) [@atwood2016diffusion] [@defferrard2016convolutional] [@kipf2017semi] generalize classical convolutions to the graph domain, attracting increasing interests from both researchers and practitioners. Recently, GCNs are applied to model the spatial dependencies of traffic flows to explore the inherent traffic topology. For example, STGCN [@yu2018spatio] models spatial dependencies with spectral graph convolutions defined on an undirected graph, while [@li2018dcrnn_traffic] employs diffusion graph convolutions on a directed graph to incorporate the influence of traffic flow directions. However, they both have drawback that their spatial dependencies are fixed once trained, ignoring the dynamic changes of traffic conditions (e.g. rush hours and traffic accidents). Most recently, [@guo2019attention] also proposed to generate dynamical spatial dependencies but their spatial dependencies are not evolving time but the depth of spatial and temporal blocks. [@pan2019urban] models dynamical spatial dependencies by adopting a extra meta learner to summarize the geo-graph features and then the embedded geo-graph features together with GATs [@velivckovic2017graph] are used to generate dynamical spatial dependencies, however, their spatial dependencies are still limited to $k$ nearest neighbors of predefined graph topology that cannot discover hidden patterns of dependencies at various scales beyond local nodes. [@wu2019graph] capture hidden spatial patterns beyond predefined graph topology through a learnable embedding for each nodes in graph, which largely improve the forecasting accuracy but their spatial dependencies are still fixed once trained. Unlike these approaches, the proposed model provide a effective and efficient mechanism to model dynamical directed spatial dependencies. We could discover richer hidden dependencies beyond predefined graph structures and local nodes by dynamically computing spatial dependencies in different latent high-dimensional subspace.

Temporal dependencies modeling
------------------------------

As stated in [@ma2015long] [@wu2016short], previous models for temporal dependencies modeling especially RNNs suffer from two main limitations. On one hand, RNNs are limited in capture the long-range dependencies due to gradients exploding or vanishing in model training, resulting in their poor performance when the input sequences are long. On the other hand, the temporal dependencies are also highly dynamical so that it is difficult to determine the optimal sequence length for accurate traffic forecasting. To alleviate these drawbacks, Gated Recurrent Units (GRUs) [@chung2014empirical] [@pan2019urban] or Long-Short Term Memory (LSTM) [@Hochreiter:1997:LSM:1246443.1246450] are thus developed to model long-range dependencies and applied to traffic forecasting [@guo2019attention] [@ma2015long] [@wu2016short]. Unfortunately, they still suffer from their inherent sequential nature, making the training process time-consuming and limiting their scalability to model long sequences. Alternatively, [@yu2018spatio] [@guo2019attention] adopted Convolution-based sequence learning models [@gehring2017convolutional], however, the limited size of receptive fields requires multiple hidden layers to cover a sufficiently large context. [@wu2019graph] adopted WaveNet with dilation convolution to increase the receptive field to cover the whole sequence with smaller layers. However, the number of layers still increase linearly with input sequence length, thus limiting the model scalability to explore long input sequence. Furthermore, deep layers increases the length of the path between two components, and degrades its efficiency in capturing long-range dependencies [@hochreiter2001gradient] [@NIPS2017_7181]. The model needs to be redesigned if the input sequence length are changed, thus making it expensive to search for optimal input sequence length. In contrast, transformers [@NIPS2017_7181] are a newly proposed efficient sequence learning model that relies on a self-attention mechanism that is highly parallelizable. It enables to effectively and efficiently capture long-range dependencies over time with single layers and can be easily adapted for different input sequence length.

The Formulation
===============

A traffic network can naturally be represented as a graph ${\mathcal G}=({\mathcal V, \mathcal E }, A)$, where ${\mathcal V}$ is the set of nodes representing the sensors with $|{\mathcal V}|=N$, ${\mathcal E}$ is the set of edges reflecting the physical connectivity between sensors, and $A\in {\mathbb R^{N\times N}}$ is the adjacent matrix that is constructed based on Euclidean distances between sensors. Traffic forecasting is a classic spatial-temporal prediction problem. Formally, given the past $T'$ observed traffic conditions $[v^{\tau-T'+1},\cdots, v^\tau]$ from $N$ sensors and a traffic network $\mathcal G$, traffic forecasting seeks to predict $T$ future traffic conditions $[{\hat v}^{\tau+1},\cdots,{\hat v}^{\tau+T}]$ as shown in Fig. 2. In this paper, we focus on forecasting traffic speeds where $v^\tau\in {\mathbb R^N}$, and it can be easily adapted to forecast volume and density. The traffic forecasting problem can generally be formulated as $${\hat v}^{\tau+1},\cdots,{\hat v}^{\tau+T}={\mathcal F}(v^{\tau-T'+1},\cdots, v^\tau;{\mathcal G})$$ where ${\mathcal F}$ is the model we wish to learn. In this paper, we learn dynamical spatial dependencies for forecasting traffics as shown in Fig.1b(ii), where the spatial dependencies $S^\tau\in {\mathbb R^{N\times N}}$ change over time and are learned at each time $\tau$.

The Proposed Model
==================

In this section, we introduce the proposed spatial-temporal transformer network. Specifically, we first describe the overall architectures of the proposed model, and then elaborate its main components: [*spatial transformer*]{}, [*temporal transformer*]{} and prediction layer, respectively.

The Overall Architectures
-------------------------

The overall structures of the proposed spatial-temporal transformer network are demonstrated in  Fig.3, which consists of stacked spatial-temporal blocks and a prediction layer which consists of two $1\times 1$ convolution layers. More specifically, a spatial-temporal block contains a spatial transformer and a temporal transformer to jointly learn spatial-temporal features in the context of dynamically changing dependencies. Several blocks can be stacked to form deep models for more complicated spatial-temporal features. Then, the prediction layer aggregates the learned deep spatial-temporal features for final predictions. Previous models usually make predictions in an auto-regressive fashion and output single-step prediction each time. There are usually two quite different schemes to train the model. In STGCN, only the single-step prediction error is adopted to train the model, while multi-step predictions are made in test. It ignores the dynamic of traffic flows, thus its performance is relatively limited especially in long-term predictions. In contrast, DCRNN adopted encoder-decoder scheme to incorporate multi-step prediction errors into the final loss and random sampling scheme is further adopted to alleviate the error accumulation problem in long-term predictions. As GraphWaveNet. we argue that multi-step results can be directly predicted with the powerful deep models without predicting in an auto-regressive manner. By make multi-step predictions directly, both short-term and long-term predictions can be predicted with the true observations without using the error-prone predictions. Thus error accumulation problem can be well addressed. Here, we output multi-step predictions with the the learned deep spatial-temporal features, and use the multi-step errors to train the model.

![image](Framework_big_v2.pdf){width="2\columnwidth" height="1.1\columnwidth"}

Spatial Transformer
-------------------

In this subsection, we first elaborate the four components of the proposed spatial transformer: spatial position-temporal embedding layer, graph convolution layer, dynamical graph convolution layer as gate mechanism for information fusion. More specifically, the spatial-temporal embedding layer is learned to incorporate spatial-temporal position information (e.g. topology, connectivity, timesteps.) into each node. The graph convolution layer is adopted to explore the road topology information for some fixed spatial dependency patterns, and the dynamical graph convolution layer is used to capture dynamical directed spatial dependencies evolving with time. In final, the learned fixed spatial and dynamical features are fused with gate mechanism. We further present that the proposed spatial transformer can be viewed as a general message passing graph neural network for dynamical graph construction and feature learning.

### Spatial-temporal Position Embedding

As the transformer contains only fully feed-forward structures, and there is no convolutional or recurrent operation, thus the spatial position information of nodes as well as the temporal information of each observations are inherently lost. As a matter of fact, they both play an important role in modeling spatial dependencies, as illustrated in Fig 1(a), the distance and time determine whether a spatial dependency between two node should be utilized for future predictions. In transformer [@NIPS2017_7181], prior positional embedding is adopted to inject ’position’ information into the input sequences. Here, we adopt learnable spatial and temporal positional embedding layer to learn spatial temporal embedding into each node feature. Specifically, a dictionary ${\mathcal D}^{\mathcal S}\in {\mathcal R^{N\times N}}$ and ${\mathcal D}^{\mathcal T}\in {\mathcal R^{N\times T}}$ is learned as spatial position embedding matrix and temporal position embedding matrix respectively. We initialize the dictionaries with the graph adjacent matrix and one-hot time encode,respectively, as graph adjacent matrix contains the connectivity as well as distance information which is important for spatial dependencies modeling while one hot time encode can well inject the time step information into each node. The dictionaries are then updated during training. The input features are concatenated with the dictionaries as $X^{i}=[X^{\mathcal S}, {\mathcal D}^{\mathcal S}, {\mathcal D}^{\mathcal T}]$ before feeding into following graph convolution layers, where $X^{\mathcal S}$ is the input features to spatial-temporal blocks.

### Fixed Graph Convolution Layer

Graph convolution is a generalization of classical convolution to graph domain. It learns node features by aggregating its neighbors information according to the learned weights and predefined graph, thus it is effective to learn the structure-aware node features. In this paper, we adopt the chebyshev-based graph convolution to capture the fixed spatial dependencies from the prior road topology. Formally, we denote $A \in {\mathbb R^{N\times N}}$ as the adjacent matrix that are calculated via gaussian kernel according to the distances among sensors. Let $ X\in {\mathbb R}^{N\times d}$ denote the input node features that contain real-time traffic conditions of $N$ sensors, and $T_k$ is the order-$k$ Chebyshev polynomials. Also, $D$ is the degree matrix with $D_{ii}=\sum_i{A_{ij}}$, $L=I_n-D^{-1/2}AD^{-1/2}$ is the normalized Laplacian matrix, and ${\mathcal {\widetilde L}}=2L/\lambda_{max} -I_n$ is the scaled Laplacian matrix for chebyshev polynomials, where $\lambda_{max}$ is the largest eigenvalues of $L$.

Then, the structure-aware node features $X^{{\mathcal G}}\in {\mathbb R}^{N\times d^{{\mathcal G}}}$ can be obtained with $K$ order chebyshev-polynomial approximation graph convolution as $$X^{{\mathcal G}}_{:,j}=\sum\limits_{i=1}^{d}\sum\limits_{k=0}^K \theta_{ij,k}T_k({\mathcal {\widetilde L}})X_{:,i} \quad  0 \leq j \leq d_{{\mathcal G}}$$ where $X^{\mathcal G}_{:,i}$ is the $i$-th channel of node features and $\theta_{ij,k}$ is the learned parameters.

Note that we naturally use the physical connectivity and distances among sensors to construct graph, so that we can explicitly explore the road topology information through graph convolution.

### Dynamical Graph Convolution Layer

Previous GCNs-based models such as [@yu2018spatio] [@li2018dcrnn_traffic] can only model fixed spatial dependencies. To capture the hidden spatial dependencies evolving time, here, we propose a novel dynamical graph convolution network to dynamically calculate spatial dependencies in learned latent high-dimensional subspaces. Specifically, we learn linear mappings to project input features of each node to latent high-dimensional subspaces and then the spatial dependencies are dynamically computed by a self-attention mechanism between the projected features. Through such mechanism, we can efficiently model the dynamical spatial dependencies according to the changing input graph signals. Notably, the learned dependencies are directed and we can also learn multiple linear mappings to model spatial dependencies in various representation subspaces as to reveal more hidden spatial dependencies influenced by different relationships factors.

Here, we adopt the self-attention to dynamically model the spatial dependencies among sensors. Self-attention mechanism is widely used in computer vision and natural language processing tasks. It proves powerful to model the relationships among individual items. In GAT, self-attention mechanism is also adopted to calculate the weights among nodes, however, their graph topology are predefined, thus they only model the edges weights dynamically. In traffic networks, there are some hidden spatial dependencies that are not fully reflected by the road topology, thus the graph should also be dynamical constructed as well as the edge weights. The self-attention mechanism we adopted in this paper is shown in Fig.4.

Formally, the input features (e.g traffic condition together with spatial-temporal position information) are first projected into latent high dimensional subspaces with learnable mappings which are realized with feed-forward neural networks. Basically, for single-head attention model which model one relationship pattern, three subspaces are obtained for each node, namely, query subspace $Q^{\mathcal S}\in {\mathbb R}^{N\times d^{\mathcal S}_q}$, key subspace $K^{\mathcal S}\in {\mathbb R}^{N\times d^{\mathcal S}_k}$ and value subspace $V^{\mathcal S}\in {\mathbb R}^{N\times d^{\mathcal S}_v}$. And the latent subspace learning process can be formulated as $$\begin{array}{lcr}
       Q^{\mathcal S}=X^{{\mathcal S}}W^{\mathcal S}_q\\
       K^{\mathcal S}=X^{{\mathcal S}}W^{\mathcal S}_k\\
       V^{\mathcal S}=X^{{\mathcal S}}W^{\mathcal S}_v
       \end{array}$$ where $W^{\mathcal S}_q, W^{\mathcal S}_k, W^{\mathcal S}_v$ are the weight matrices for $Q^{\mathcal S}, K^{\mathcal S}, V^{\mathcal S}$, respectively.

After obtaining the three latent high dimensional subspaces, dynamical spatial dependencies $S^{\mathcal S}\in {\mathbb R^{N\times N}}$ are further calculated by dot-product as $$S^{\mathcal S}=\text{softmax}(\frac{Q^{\mathcal S}(K^{\mathcal S})^T}{\sqrt{d^{\mathcal S}_k}})$$ where $S^{\mathcal S}$ is the learned dynamical dependencies matrix among nodes. Then, new node features $M^s\in{\mathbb R^{N\times d^{\mathcal S}_v}}$ are further updated with $$M^s=S^{\mathcal S}V_{\mathcal S}$$ Note that we adopt dot product to calculate dependencies between nodes as it is much fast and space-efficient in practice. The softmax is then applied to normalize the dependencies. Scaling by $\sqrt{d^{\mathcal S}_k}$ is to avoid the softmax from reaching the saturation when gradients are extremely small. Multiple dependencies can be learned with multi-heads attention mechanism by learning multiple subspace pairs, thereby revealing different hidden spatial dependencies from various latent subspaces.

To further improve the prediction ability of learned node features, a shared three-layer feed-forward neural network with nonlinear activation is applied on each node to explore the interactions among features channels and update the node features as $Y^s\in {\mathbb R}^{N \times d^s_o}$. $$U^{\mathcal S}=\text{ReLu}(\text{ReLu}(M^{\mathcal S}W^{\mathcal S}_0)W^{\mathcal S}_1)W^{\mathcal S}_2$$ where $W^{\mathcal S}_0, W^{\mathcal S}_1, W^{\mathcal S}_2$ are the weight matrices, and $U^{\mathcal S}=X^{\mathcal S}+M^{\mathcal S}$ is the residual connection for stable training.

To model more complicated spatial dependencies, we can stack several dynamical graph convolution layers for deep model to improve the model capacity.

### Gate mechanism for features fusion

There are two kind of spatial features, one is obtained with fixed spatial dependencies while the other is calculated with dynamical dependencies. To fuse the two kind of features, a gate mechanism is adopted. We first learn the gate $g$ as $$g=\text{Sigmoid}(f_s(U^{\mathcal S})+f_g(X^{\mathcal G})+b)$$ where $f_s$ and $f_g$ are fully connected layer and $b$ is the bias term. The final output of spatial transformer is $$Y^{\mathcal S}=gU^{\mathcal S}+(1-g)X^{\mathcal G}$$

### General Dynamical Graph Neural Networks

As we have mentioned above, previous graph convolutional networks include spectral-based and spatial-based models, all rely on predefined graph structure, and can not adapt to input graph signal. Here, we demonstrate the entire spatial transformer can be formulated as a general message passing dynamical graph neural network. Formally, we denote $x_v$ as the input features of node $v$. The whole spatial feature learning process can be rewritten as $$m_v=\sum_{w\in \mathcal V }F(x_v, x_w)$$ $$y_v=G(m_v ,x_v)$$ where $\mathcal V$ is the set of nodes in the traffic network, $F$ is the message-passing function that computes the spatial dependencies and passes message $m$ among nodes (Eq.4$-$Eq5), $G$ is the shared position-wise feed forward network to update the node features as $y$ (Eq.6).

Then, the whole spatial transformer can be summarized as $$Y^{\mathcal S}={\mathcal S}(X, A)$$

In summary, the proposed spatial transformer has the following properties. 1) Dynamical hidden spatial dependencies are calculated in the learned high-dimensional latent subspaces, and prior graph structure information can be incorporated via residual structures. 2)The learned hidden spatial dependencies are not restricted to local nodes but can be globally, and multiple spatial dependencies can be explored in different latent relationship spaces. 3)It is fully feed-forward, thus computations can be performed in parallel in a fast and scalable fashion, in other words, we can easily scale our model to large-scale traffic forecasting with proper distribution computation scheme.

Temporal Transformers
---------------------

![image](dependencies.pdf){width="2\columnwidth" height="1\columnwidth"}

We also develop a temporal transformer to efficiently and effectively capture long-range temporal dependencies [@NIPS2017_7181] over time. Compared with RNNs and the variants, it can not only capture long-range dependencies but also allow parallel calculations so that it can be easily scaled to long sequences. The structures are illustrated in the bottom right of Fig.3.

### Self-attention Layer for Long-range Modeling

Similar to temporal position adopted in spatial transformer, we first concatenate the learned spatial features in each time step with temporal embedding which is also initialized with one-hot encode and updated during training as ${X^{\mathcal T}=[Y^{\mathcal S}, D^{\mathcal T'}]}$.

And then self-attention mechanism is also adopted to model temporal dependencies. The input to the temporal transformer is a temporal sequence $X^{\mathcal T}\in {\mathbb R}^{M\times d^{\mathcal T}}$ with a slide window of length $M$ and $d^{\mathcal T}$ channels. Similar to spatial transformer, temporal dependencies are dynamically computed in high-dimensional subspaces. The three subspaces, the queries $Q^ {\mathcal T}\in {\mathbb R}^{M\times d^{\mathcal T}_q}$, the keys $K^{\mathcal T}\in {\mathbb R}^{M\times d^{\mathcal T}_k}$, and the values $V^{\mathcal T}\in {\mathbb R}^{M\times d^{\mathcal T}_v}$, can be computed as $$\begin{array}{lcr}
       Q^ {\mathcal T}=X^{{\mathcal T}}W^{\mathcal T}_q\\
       K^{\mathcal T}=X^{\mathcal T}W^{\mathcal T}_k\\
       V^{\mathcal T}=X^{\mathcal T}W^{\mathcal T}_v
       \end{array}$$ where $W_q\in {\mathbb R}^{d^{\mathcal T}\times d^{\mathcal T}_q}$,$W_k\in {\mathbb R}^{d^{\mathcal T}\times d^{\mathcal T}_k}$ and $W_v\in {\mathbb R}^{d^{\mathcal T}\times d^{\mathcal T}_v}$ are the learned liner mappings.

Unlike RNNs-based models which temporal dependencies are limited to previous time steps, we learn bidirectional temporal dependencies with scaled dot-product function as $$S^{\mathcal T}=\text{softmax}(\frac{Q^{\mathcal T}(K^{\mathcal T})^T}{\sqrt{d^{\mathcal T}_k}})$$ Then, the temporal features are obtained by aggregating the values $V^{\mathcal T}$ weighted by the bidirectional temporal dependencies. $$M^{\mathcal T}=S^{\mathcal T}V^{\mathcal T}$$ The temporal dependencies modeling process is illustrated in Fig.4. To explore the interactions among latent features, they are further processed with a shared three-layer feed-forward neural network $$Y^{\mathcal T}=\text{ReLu}(\text{ReLu}(U^{\mathcal T}W^{\mathcal T}_0)W^{\mathcal T}_1)W^{\mathcal T}_2$$ where $U^{\mathcal T}=M^{\mathcal T}+X^{\mathcal T}$ is the residual connection for stable training.

As Eq. 11, the temporal transformer can be formulated as $$Y^{\mathcal T}={\mathcal T}(X^{\mathcal T})$$

It is worth noting that the in each temporal transformer layer, each time step can attend to all other time steps, thus long-range bidirectional temporal can be efficiently captured in each temporal layer. Furthermore, temporal transformer can be easily scaled to long sequence by increasing the slide window length $M$ without much sacrifice in computation efficiency. While RNNs-based models can not deal with long sequences due to the gradients vanishing/exploding. As for convolution-based model, for different sequences length, more layers are need and the filters windows and number of layers require explicitly designed to ensure that the whole sequence are covered to capture long-range dependencies.

Model Structures
----------------

### Spatial-temporal Blocks

The future traffic flow conditions of one location are determined by the traffic conditions of its neighbor locations, and the time when the influence will happen as well as some sudden changes (e.g traffic accidents, weather condition s). Thus to make accurate predictions, the spatial and temporal dependencies of the traffic networks should be jointly modeled, so we integrate the proposed spatial and temporal transformer as a spatial-temporal transformer block, and residual connections are adopted among them as well. The structure of spatial-temporal block is illustrated in Fig. 3.

The input to the $l$-th spatial-temporal block is a 3D tensor $X^l\in {\mathbb R}^{M\times N\times d^l}$ with $M$ time steps of observations from $N$ nodes. Let ${\mathcal T}$ and $\mathcal S$ be the spatial and temporal transformers as aforementioned. Then the output $X^{l+1}\in {\mathbb R}^{M\times N\times d^{l+1}}$ can be formulated as $$X^{l+1}=X^l+{\mathcal S}(X^l,A)+{\mathcal T}(X^l+{\mathcal S}(X^l,A))$$ For simplicity, we denote $\mathcal S$ as spatial transformer and $\mathcal T$ as temporal transformer. Multiple spatial-temporal blocks can be stacked to improve the model capacity according tasks at hand.

### Prediction Layer

In the prediction layer, final time steps spatial-temporal features from the last spatial-temporal block are feed as input. And two stacked classical convolutional layers are then adopted to make multisteps predictions.

Formally, the input to the prediction layer is a 2D tensor $X^{\mathcal {ST}}\in {\mathbb R}^{N\times d^{{\mathcal {ST}}}}$, which is the last time step spatial-temporal features extracted by stacked spatial-temporal blocks. The final multi-steps prediction is $$Y=\text{Conv}(\text{Conv}(X^{\mathcal {ST}}))$$ where $Y\in {\mathbb R}^{N\times T}$. Mean absolute loss are then adopted to train the model which can be formulated as $$L=\|Y-Y^{gt}\|_1$$

Experiments
===========

In this section, we evaluate the proposed model by conducting extensive experiments on two real-world datasets, PeMSD7(M) and PEMS-BAY. In particular, we will demonstrate the state-of-the-art performances especially in making long-term predictions. To validate effectiveness of the proposed spatial and temporal transformers as well as verify some arguments we have proposed above, extensive ablation studies will be further conducted. Specifically, we will first show that direct prediction can alleviate the error propagation problem encounted in auto-regressive prediction, and then we will validate the effectiveness of dynamical spatial dependencies as well as the proposed spatial transformer. Next, we demonstrate that long-range temporal dependencies are important for accurate predictions, thus should be well utilized and the proposed temporal is efficient and effective in model long-range temporal dependencies. Finally, we analyze the influence of different model configurations as well the model complexity.

Dataset and Data preprocessing
------------------------------

**PEMS-BAY** [@li2018dcrnn_traffic] contains $6$ months traffic information collected from $325$ sensors in the Bay Area of California, starting from Jan $1$st 2017 through May $31$th 2017. **PeMSD7(M)** [@yu2018spatio] collects traffic information from $228$ monitoring stations in the California state highway system during the weekdays from May through June of 2012. Traffic speeds are aggregated every five minutes, and normalized with $Z$-Score as inputs.

The road topology information is represented by a graph adjacent matrix. The graph of PeMS-BAY dataset is prior designed as a directed graph to differentiate the influence of different directions, thus forward and backward diffusion graph convolutions can be adopted to model the directed spatial dependencies [@li2018dcrnn_traffic]. However, it is difficult to metric the influence of direction with manually, resulting in difficulty in constructing the directed graph. In this paper, we use self-attention mechanism to model the directed spatial dependencies in a data-driven manner, bypassing the heavy burden on differentiating the influence of directionality. In our model, a simple undirected graph adjacent matrix which can reveal the distance and connectivity among sensors are required. For PeMS-bay dataset, the undirected graph is constructed by adopting the maximum weight on the two directed edges between each pair of nodes as undirected edge, and use the undirected graph to represent the road topology information. For the PeMSD7 dataset, the adjacent matrix is already symmetric based on the road distances between sensors, thus can be directed adopted.

Experiment Settings
-------------------

All experiments are conducted on a NVIDIA 1080 Ti GPU. The proposed model is trained with the mean absolute error loss using the RMSprop optimizer for $50$ epochs with a batch size of $50$. The initial leaning rate is set to $10^{-3}$, and it decays at a rate of $0.7$ every five epochs. We independently perform the same experiments on each dataset five times, and report the average results in Table 1. To demonstrate the performance of the proposed model, we compare with the results reported in [@li2018dcrnn_traffic][@yu2018spatio], where the current $12$ observations ($60$ minutes) are used to predict the traffic conditions in the next $15, 30, 45$ minutes on PeMSD7(M) and $15,30,60$ minutes on PEMS-BAY, respectively. For GraphWaveNet, we trained the public code released by the author on PeMSD7(M) dataset and the best performance is reported.

\[table1\]

  -------------------------------------------------------------------------------- ----------------------------------------------------------------------------------
   ![image](STTN_average_v4.pdf){width="1\columnwidth" height="0.6\columnwidth"}    ![image](Wavenet_average_v4.pdf){width="1\columnwidth" height="0.6\columnwidth"}
                                        (a)                                                                               (b)
   ![image](STGCN_average_v4.pdf){width="1\columnwidth" height="0.6\columnwidth"}    ![image](DCRNN_average_v4.pdf){width="1\columnwidth" height="0.6\columnwidth"}
                                        (c)                                                                               (d)
  -------------------------------------------------------------------------------- ----------------------------------------------------------------------------------

Evaluation Metrics and Baselines
--------------------------------

Three widely used metrics are adopted for evaluation – Mean Absolute Errors (MAE), Mean Absolute Percentage Errors (MAPE), and Root Mean Squared Errors (RMSE).

We mainly compared with STGCN, DCRNN and GraphWaveNet. STGCN [@yu2018spatio] and DRCNN [@li2018dcrnn_traffic] are the two most representative deep learning methods for traffic forecasting, while GraphWaveNet is the the latest model which has achieved state-of-the-art performance. In addition, the other methods we will compare with include 1) Historical Average (HA); 2) Linear Support Vector Regression (LSVR); 3) Auto-Regressive Integrated Moving Average (ARIMA); 4) Feed-forward Neural Network (FNN); 5) Fully-Connected LSTM (FC-LSTM) are reported in STGCN [@yu2018spatio] and DRCNN [@li2018dcrnn_traffic].

The proposed model is denoted as STTN in the following sections. For PeMSD7(M) dataset, only one spatial-termporal block are adopted. Two hidden layers and single attention are adopted for spatial and temproal transformer and the feature channels are all set as 64. For PeMS-BAY dataset which are much larger than PeMSD7(M) both termporally and spatially, three spatial-temporal transformer blocks are stacked to model deep spatial and temporal dependencies. For each spatial and temporal transformer in each block, one hidden layer and single attention are adopted, and the feature channels are still set as 64. In our model, residual structures are adopted for stable learning and fast convergence.

Experiments Results
-------------------

The results are shown in Table I. We can observe that 1) For PeMSD7(M) dataset, the proposed model achieves the state-of-the-art performance and we outperform STGCN and DCRNN by a large margin. The gaps are increased with prediction time gets longer. In comparsion with GraphWaveNet, we both take advantages of long-range temporal dependencies and GraphWaveNet models hidden fixed spatial dependencies while we are able to model dynamical spatial dependencies. We both consistently outperform other models by a large margin, demonstrating the effectiveness of long-range temporal dependencies and hidden spatial dependencies. It can also be observed that we perform much better than GraphWaveNet for long-term predictions while similar in short-term predictions. It is quiet reasonable as the spatial dependencies as well as temporal dependencies can be viewed as stationary in short term prediction, GraphWaveNet adopts convolutional kernels with small receptive fields perform quiet well in capturing short-range dependencies.

2\) For PEMS-BaY dataset, we achieve comparable performance with state-of-the-art (GraphWaveNet) while performing much better than STGCN and DCRNN. For GraphWaveNet and DCRNN, bidirectional diffusion graph convolution are performed on explicitly designed directed matrix to consider the influence of directionality, so that they outperform STGCN by a large margin. However the influence of directionality is complicated and hard to measure. Instead, we use self-attention mechanism to capture the dynamical directed spatial dependencies in a data-driven manner and we achieve similar results with simple undirected adjacent matrix, demonstrating the effectiveness of the dynamical spatial dependencies modeling. Furthermore, compared with STGCN which also adopted three pairs of spatial and temporal units, we consistently outperform it with different prediction range. It can also validate the effectiveness of our model. To better demonstrate the superiority of our model in capturing changing spatial-temporal depedencies, we further illustrate the one-day prediction results (averaged along saptial dimension) on test dataset with different prediction time for STTN, GraphWaveNet, STGCN and DCRNN. The results are shown in Fig.5. As we can observed that compared with STGCN and DCRNN, STTN and GraphWaveNet perform much better in changing area (e.g. $[60,84]$). For STGCN and DCRNN, there are considerately large time-shift in the prediction results curve especially, and the shifts grow with the prediction steps, contributing to large prediction error in sharp changing area. Compare STTN with GraphWaveNet, we are able to capture continously sharp changes.(e.g. \[84,192\]) while GraphWaveNet cannot. We believe it is due to our superiority in capturing dynamical spatial dependencies as well as long-range temporal dependencies.

Ablation Studies
----------------

In this section, we conduct extensive experiments for through analysis of the proposed model and verify the arguments we have proposed above. Since PeMSD7(M) dataset is much more challenging than PEMS-BAY while smaller both temporally as well as spatially, e.g the standard deviation of collected speeds is much larger than that of PeMS-bay, so we take PeMS-D7 dataset for example and all the experiments below are performed on PeMSD7(M) dataset. To better demonstrate the influence of different factors, in this section, for our model, we use only one spatial-temporal block with feature dimension 64 for each spatial and temporal transformer.

### Direct multi-step prediction is better than auto-regressive prediction

\[table2\]

Most previous models make predictions in a auto-regressive fashion, in which the predicted results are adopted to make next-step prediction until all predictions are obtained. Since predictions are error-prone, thus it is inevitable to propagate errors for next predictions, resulting in poor performance in long-term predictions. To alleviate this problem, [@li2018dcrnn_traffic] DCRNN proposed a sampling scheme. We argue that it is better to directly make long-term predictions with true observations instead of the error-prone prediction results. To verify this argument, we perform experiments on both STGCN and our one-block model, and both of them make predictions directly as well as auto-regressively. The results are shown in Table II. Form Table II, we can easily observe that, by direct make predictions from previous true observations, the performance especially in long-term prediction is much significantly improved compared with that of auto-regressive predictions. Furthermore, the errors increase much slower, which firmly validates our argument.

### Effectiveness of Spatial Transformer in modeling dynamic spatial dependencies

\[table3\]

  --------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
   ![(a) Illustration of traffic predictions for short term prediction (5 min) with fixed and dynamical spatial dependencies. (b) Illustration of traffic predictions for long term prediction (60 min) with fixed and dynamical spatial dependencies.[]{data-label="fig5"}](spatial_short_v2.pdf "fig:"){width="1\columnwidth" height="0.6\columnwidth"}
                                                                                                                                                                            (a)
   ![(a) Illustration of traffic predictions for short term prediction (5 min) with fixed and dynamical spatial dependencies. (b) Illustration of traffic predictions for long term prediction (60 min) with fixed and dynamical spatial dependencies.[]{data-label="fig5"}](spatial_long_v2.pdf "fig:"){width="1\columnwidth" height="0.6\columnwidth"}
                                                                                                                                                                            (b)
  --------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

Dynamic spatial dependencies play an important role in effective traffic flow prediction. In this experiment, we validate that dynamical spatial dependencies is necessary for accurate long-term predictions as well as the effectiveness of the proposed spatial transformer in modeling dynamical spatial dependencies. To better demonstrate the influence of dynamical spatial dependencies, here, we adopt a model which has only one graph convolution layer and one convolution-base sequence modeling module (GLU layer) as our baseline, and then we replace the graph convolution layer with the proposed spatial transformer as a comparison denoted as STTN-S(a,h) in table III, where $a $ and $h$ denote the number of attention heads and hidden layers, respectively. Note that the only difference between the two models is that the baseline can only model fixed spatial dependencies that can not evolving with time while we model dynamical spatial dependencies adapt to real-time traffic-conditions. For spatial transformer, we change the number of attention heads as well as the number of hidden layers (e.g $(a,h)$) to make a through analysis of the proposed spatial transformer.

The results are shown in Table III. From Table III, we can observed that STTN-S (1,1) outperforms baseline by a large margin in each time steps, and the performance gap becomes larger as the prediction time gets longer. This demonstrates the effectiveness of dynamic spatial dependencies in long-term predictions. We further illustrate averaged one-day prediction results on test dataset with short and long-term prediction (5 min and 60 min) for Baseline and STTN-S (1,1). The results are shown in fig 6. We can observe that, for short-term predictions, the performance of dynamical and fixed spatial dependencies are similar. As the spatial dependencies can be viewed as stationary in short-term prediction, and the assumptions are usually made for traditional short term prediction models. However, for long term predictions, the spatial dependencies changes considerately. The proposed model are able to model dynamical spatial dependencies evolving with time, resulting in better performance in sharly changing area (e.g.\[48,84\] in Fig.6 (b)). Thus it validates our argument that the dynamical spatial dependencies are important for long-term predictions.

Compared with other attention-based dynamical spatial models such as GraphWaveNet [@pan2019urban] which limited their dynamical spatial dependencies in $k$-nearest neighbor nodes, we can capture long-range spatial dependencies beyond local nodes, thus can better to capture sudden changes, resultsing our excellent performance in sharp changing area. To validate this claim, we masked the dynamical dependencies matrix to restrict the learned spatial dependencies to local nodes. The model is denoted as STTN-S(local), shown in table III. As we can see that the performance are largely degraded with this constraint. We further compare the learned spatial dependencies in Figure 7. We can see that we both learn dynamical spatial dependencies evolving with time, but we are not limited to local nodes. On the other hand, from (b) and (c), we can observe the spatial dependencies in the most recent time steps are more than the earliest time steps. It is reasonable as the distances among sensors are quite small.

[cc]{}\
(a)\
![We take first 50 sensors for example. (a) Illustration of adjacent matrix and only local nodes are kept. (b)(c) Illustrations of dynamical spatial dependencies for STTN-S(1,1) on time step 1 and 12. (d)(e) Illustrations of dynamcial spatial dependencies for STTN-S(local) on time step 1 and 12[]{data-label="fig7"}](spatial_50_1.pdf "fig:"){width="0.55\columnwidth" height="0.45\columnwidth"}&![We take first 50 sensors for example. (a) Illustration of adjacent matrix and only local nodes are kept. (b)(c) Illustrations of dynamical spatial dependencies for STTN-S(1,1) on time step 1 and 12. (d)(e) Illustrations of dynamcial spatial dependencies for STTN-S(local) on time step 1 and 12[]{data-label="fig7"}](spatial_50_12.pdf "fig:"){width="0.55\columnwidth" height="0.45\columnwidth"}\
(b)&(c)\
![We take first 50 sensors for example. (a) Illustration of adjacent matrix and only local nodes are kept. (b)(c) Illustrations of dynamical spatial dependencies for STTN-S(1,1) on time step 1 and 12. (d)(e) Illustrations of dynamcial spatial dependencies for STTN-S(local) on time step 1 and 12[]{data-label="fig7"}](masked_spatial_50_1.pdf "fig:"){width="0.55\columnwidth" height="0.45\columnwidth"}&![We take first 50 sensors for example. (a) Illustration of adjacent matrix and only local nodes are kept. (b)(c) Illustrations of dynamical spatial dependencies for STTN-S(1,1) on time step 1 and 12. (d)(e) Illustrations of dynamcial spatial dependencies for STTN-S(local) on time step 1 and 12[]{data-label="fig7"}](masked_spatial_50_12.pdf "fig:"){width="0.55\columnwidth" height="0.45\columnwidth"}\
(d)&(e)\

We further change the attention heads and hidden layers in spatial transformer, the results are also shown in Table III. By increasing attention heads, the performance is continuously improved in all time steps. This is because multi-heads attention can model spatial dependencies in different relationship space, thus more hidden dependenceies pattern can be further utilized. The increase of hidden layers does small benefit to the performance. As PeMSD7(M) dataset are relatively small, thus one hidden layer is able to model the spatial dependencies.

### Effectiveness of Temporal Transformer in modeling long-range dependencies.

In this subsection, we first validate the effectiveness of long-range temporal dependencies in accurate traffic flow prediction and then demonstrate the effectiveness of the proposed temporal transformer in capture long-range dependencies, thus contributing to better prediction performance.

To demonstrate the influence of long-range temporal dependencies, here, we adopt the model with one graph convolution layer and one GLU layer as our baseline (the same as last subsection). By adopting convolution-based sequence model (GLU layer) to model temporal dependencies, we can easily control the receptive fields, in other words, the temporal dependencies range the model are utilized in the experiments. In practice, we change the convolution kernel size from $3$ to $6, 9$ and $12$. With the convolution kernel size increases, the temporal dependencies utilized are increasing and all the input sequence are covered when kernel size is $12$. The results are shown in upper part of Table IV, As we can seen that, with longer temporal dependencies are utilized, the long-term prediction performance is continuously increasing, which validates that long-range temporal dependencies benefits accurate prediction results for long term predictions.

\[table4\]

To validate the effectiveness of the proposed temporal transformer, we replace the GLU layer with our temporal transformer and we further change the number of hidden layers and attention heads to better understand temporal transformer. As shown in Table VI, STTN-T (1,1) performs similar with baseline in the short-term prediction, while the performance are much better in long term prediction, which demonstrates the effectiveness of the proposed temporal transformer in capturing long-range temporal dependencies. We further illustrate some temporal transformer attention matrix during test as in Fig 8.

As we can see that for different node, the temporal attention weight are different and in some node, earliest time-steps are utilized with long-range dependencies for predicitons.

![Illustration of temporal attention matrix of the first nine sensors for the first prediction on test dataset[]{data-label="fig6"}](Temporal_attention.pdf "fig:"){width="1\columnwidth" height="0.7\columnwidth"}\

Model Configuration analysis
----------------------------

STTN enables flexible model configurations and we can adjust it according to tasks at hand, such as the number of spatial-temporal blocks, the number of hidden layers, the attention dimensions, the number of attention heads as well as the hidden units dimensions. To better understand the STTN as well as the influence of different parameters settings, in this subsection, we present the results of STTN with different parameter settings.

First, we analyze the influence of different number of spatial-temporal blocks. The results are shown in the first three rows of Table V. We can observe that by stacking multiple spatial-temporal blocks to model deep spatial-temporal dependencies jointly, the performance is increasing. We can further see that two blocks are enough to capture the complicate dependencies in PeMSD7(M) dataset, so that this is no gain by increasing another block.

Then, we investigate the influence of feature channels. In STTN, the feature channel denote the dimension of subsection where dependencies are dynamically computed, thus the dimension of output spatial and temporal features. The results are shown in the fourth and fifth rows which demonstrate that higher dimension of attention subspace can result in better performance. It is reasonable as more information can be explored with higher dimension.

Next, we analyze the influence of a single spatial or temporal transformer capacity to the final prediction performance. Increasing the capacity of temporal transformer, in other words, adding the hidden layers, benefits a little to the performance, while it is contributes to large improvement to increase the capacity of spatial transformer, especially in long-term prediction, validating the importance of dynamical spatial dependencies in long-term prediction. And increasing the capacity of spatial and temporal transformer jointly will further improve the model.

As multi-attention can be adopted in STTN, and in real-world traffic networks, the relationships among nodes may fall into different relationship space. For example, the relationship among sensors can be formed as the similarity of their traffic flow pattern, or just the influence among them. Thus, multi-heads attention may be helpful to explore more hidden relationship patterns. As shown in Table V, by adopting multi-heads attention, the performance are improved, and the gain of more spatial relationship patterns does more benefits to the model, which is conform to our prior knowledge.

Finally, we explore the importance of positional embedding in STTN. We first remove the positional embedding in spatial and temporal transformer, respectively, and then remove all the embedding. The results are reported. We can concluded that

\[table7\]

Computational Complexity
------------------------

We further compare the computational costs among DCRNN, STGCN and STTN. All the experiments are conducted on the same GPU server, and we report the average training time of one epoch. The results are shown in Table 4. STGCN adopts fully convolutional structures so that it is fastest, and DRCNN uses the recurrent structures, which are very time consuming. Furthermore, as DCRNN adopts multiple step prediction errors to train the model, the training time will proportionally increase with the prediction time gets longer. In contrast, the proposed model has a competitive efficiency compared with DCRNN, and it is more scalable to making long-term predictions without increasing computation complexity.

\[table6\]

Conclusion
==========

In this paper, we propose a novel paradigm of spatial temporal transformer architecture to improve the long-term traffic forecasting. It can dynamically model various scales of spatial dependencies as well as capture long-range temporal dependencies. Experiment results on two real-world datasets demonstrate the superior performance of the proposed model in long-term forecasting. Furthermore, the proposed spatial transformer can be generalized into dynamical graph features learning in various applications, left for future research.
