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 