# Incorporating Reachability Knowledge into a Multi-Spatial Graph Convolution
Based Seq2Seq Model for Traffic Forecasting

Jiexia Ye, Furong Zheng, Juanjuan Zhao*, Kejiang Ye, IEEE Member, Chengzhong
Xu, IEEE Fellow
*Corresponding author: Juanjuan Zhao Jiexia Ye, Furong Zheng, Juanjuan Zhao, Kejiang Ye are with Shenzhen Institutes of Advanced Technology, Chinese Academy of Sciences, China (E-mail: {jx.ye, fr.zheng, jj.zhao, kj.ye}@siat.ac.cn). Chengzhong Xu is with State Key Lab of IOTSC, Department of Computer Science, University of Macau, Macau SAR, China (E-mail: czxu@um.edu.mo).

###### Abstract

Accurate traffic state prediction is the foundation of transportation control
and guidance. It is very challenging due to the complex spatiotemporal
dependencies in traffic data. Existing works cannot perform well for multi-
step traffic prediction that involves long future time period. The
spatiotemporal information dilution becomes serve when the time gap between
input step and predicted step is large, especially when traffic data is not
sufficient or noisy. To address this issue, we propose a multi-spatial graph
convolution based Seq2Seq model. Our main novelties are three aspects: (1) We
enrich the spatiotemporal information of model inputs by fusing multi-view
features (time, location and traffic states) (2) We build multiple kinds of
spatial correlations based on both prior knowledge and data-driven knowledge
to improve model performance especially in insufficient or noisy data cases.
(3) A spatiotemporal attention mechanism based on reachability knowledge is
novelly designed to produce high-level features fed into decoder of Seq2Seq
directly to ease information dilution. Our model is evaluated on two real
world traffic datasets and achieves better performance than other competitors.

###### Index Terms:

Graph Neural Networks, Graph, Deep Learning, Traffic Forecasting, Seq2Seq

##  I Introduction

Traffic forecasting is a key component of advanced traffic management systems,
aiming to predict the future traffic states (e.g. traffic flow [1], traffic
speed [2], traffic time [3]) in the traffic network. Accurate prediction can
contribute to control traffic flow, allocate traffic resources, and ease
traffic congestion[4].

Multi-step traffic forecasting is a typical spatial-temporal forecasting
problem and its has two main challenges. The first challenge is the complex
spatiotemporal dependencies. The future traffic state of a region is
influenced by many factors, such as its historical observation, the
correlation with other regions, external factors (e.g. holiday, special
events) and so on [5]. The correlations among regions are quiet complex.
Although prior knowledge such as distance or travel time between regions might
help to capture the spatial correlation, there are still some hidden patterns
that need to be detected by data-driven methods. In addition, compared with
one-step prediction task, long-term spatiotemporal correlation between input
and output steps in multi-step scenario is more complex for that it changes as
region, step and time gap between steps change [6]. The second challenge is
the model performance deterioration with insufficient qualified traffic data.
Although we can collect more traffic data due to the update of transportation
infrastructures, in many cases, the collected data is low quality with noise
and some key features are missing. The available qualified traffic data is
still insufficient. To the best of our knowledge, the traffic data used in
most previous studies are less than one year [7, 8, 9], even one or two months
[10].

Recently, various deep learning based methods have been successfully applied
to traffic prediction due to their superior capacities to capture complex
traffic patterns. Graph neural networks (GNNs) are popular in extracting
spatial dependency in traffic network [8, 11, 5, 12]. Recurrent neural
networks (RNNs) [13, 14, 15] and Temporal convolution networks (TCNs) [16, 8,
17] are often adopted to capture the temporal dependency. Seq2Seq model is
widely utilized in multi-step forecasting [18, 19, 20]. However, these
previous works have the following limitations.

First, most existing works didn’t capture the complex spatial correlations
sufficiently. Many researchers pre-defined a matrix to reflect spatial
correlation based on prior knowledge such as geometrical proximity, function
similarity, transportation connectivity [21, 5, 22]. However, any prior
knowledge is limited and is not able to reflect some hidden traffic
correlations among traffic regions. Some works designed an adaptive matrix to
dig out spatial correlation on a data-driven basis [16, 23, 12]. However, when
the data is not sufficient or noisy, the efficiency of data-driven method is
deprecated and accurate prior knowledge might enhance the model performance in
such situation. But most works only focus either pre-defined correlation or
data-driven correlation for prediction.

Secondly, Seq2Seq model generally adopted in multi-step prediction has the
information dilution problem [6, 18, 19]. When the original information on
each input step arrives at a given output step, it has been diluted several
times by both the encoder and decoder cell in Seq2Seq. Sufficient data might
ease the dilution problem while insufficient data might amplify the dilution
severity and decrease prediction performance. Therefore, modeling the long-
term temporal correlation of traffic state between input and output steps to
releviate dilution is particularly important.

In addition, each observed traffic feature (e.g. traffic speed, traffic flow)
has both spatial attribute (i.e. its location) and temporal attributes (e.g.
its time slot and week attribute). Most works [24, 25, 26, 10, 27, 9]
extracted the spatiotemporal patterns purely from traffic feature without
making full use of its spatiotemporal attributes. However, such attributes can
directly help model better identify spatiotemporal correlation among traffic
states. They can also enrich the available spatiotemporal information when
feature data is insufficient.

To overcome the challenges and limitations above, this paper proposes a model
MSGC-Seq2Seq, which mainly leverages the graph convolution and GRU based
Seq2Seq to learn the complex spatiotemporal dependency from traffic data.
Specifically, we fuse the traffic feature with its spatial attribute and
temporal attribute to augment the spatiotemporal information of model input.
To capture spatial correlation sufficiently, we first pre-define a matrix
based on prior knowledge (i.e. geographical proximity and feature trend
similarity) to extract the spatial correlation. Then, inspired by self-
attention mechanism in transformer [28], we calculate dynamic semantic
attention between any two locations in the network on a data-driven basis.To
tackle the dilution in Seq2Seq, we novelly design a attention mechanism based
on reachability knowledge to model the cross-step spatial correlation. The
high-level features produced are fed into the decoder at given output step
directly without dilution by encoder. In addition, we integrate a multi-head
temporal attention mechanism into Seq2Seq to allow the decoder to focus on the
most relevant input steps related with the predicted output step, augmenting
the useful input information for each output step prediction.

The main contributions of this paper are as follows:

  * •

We enrich the spatiotemporal information of model inputs by integrating the
traffic state with its explicit spatiotemporal attributes via graph embedding
methods.

  * •

We capture spatial correlations sufficiently from prior knowledge perspective
(i.e. geographical proximity and feature trend similarity) and data-driven
perspective (i.e. semantic similarity related with flow pattern).

  * •

We novelly design a reachability based attention mechanism to construct output
step related high-level features and feed them directly into the decoder to
avoid the dilution by the encoder in Seq2Seq.

  * •

Our MSGC-Seq2Seq model is evaluated on two real-world traffic datasets and
performs better than other baselines, especially when data is insufficient and
noisy. Our codes and datasets are public in https://github.com/start2020/MSGC-
Seq2Seq.

Figure 1: The architecture of our model MSGC-Seq2Seq. The circles represent
regions in the traffic network and the various shapes in the circles refer to
various features. GRU refers to Gated Recurrent Unit.

##  II Preliminaries

####  II-1 Traffic Network as Graph

Traffic network is modeled as a graph
$\mathbf{G}=(\mathbf{V},\mathbf{E},\mathbf{A})$ , which can be weighted or
unweighted, directed or undirected. Each node in the graph represents a
traffic region, such as a road sensor [5], a road segment [14], a road
intersection[11]. $\mathbf{V}=\left\\{v_{1},\ldots,v_{\text{N}}\right\\}$
refers N traffic nodes on the traffic network. $\mathbf{E}$ is the edges set
and each edge refers the connectivity between regions, which reflects some
kind of spatial correlation, e.g. geographical proximity, semantic
connectivity and reachability correlation.

####  II-2 Traffic Prediction Formulation

Assume that we can observe $\text{F}_{\text{I}}$ features of each node in the
traffic graph during each given time period. The features of the whole network
at time slot $p$ can be represented by a matrix
$X_{p}=[x_{p}^{1},x_{p}^{2},\cdots,x_{p}^{\text{N}}]\in\mathbb{R}^{\text{N}\times\text{F}_{\text{I}}}$.
Further, the historical features of the whole network over the past P time
periods can be denoted as
$[X_{1},X_{2},\cdots,X_{\text{P}}]\in\mathbb{R}^{\text{P}\times\text{N}\times\text{F}_{\text{I}}}$.
In this paper, we aim to predict the future status of the whole network over Q
time period, denoted as
$[Y_{1},Y_{2},\cdots,Y_{\text{Q}}]\in\mathbb{R}^{\text{Q}\times\text{N}\times\text{F}_{\text{O}}}$,
where
$Y_{q}=[y_{q}^{1},y_{q}^{2},\cdots,y_{q}^{\text{N}}]\in\mathbb{R}^{\text{N}\times\text{F}_{\text{O}}}$
and $y^{j}_{q}\in\mathbb{R}^{\text{F}_{\text{O}}}$ represents the ground truth
of region $j$ at future time period $q$. $\text{F}_{\text{O}}$ is the number
of output features. We focus on multi-step prediction, therefore $\text{Q}>1$.
This paper aims to find a function $f$ mapping the historical observations of
the graph-based traffic network over past P time slices to its future
observations over Q time slices as follows:

$[\hat{Y}_{1},\cdots,\hat{Y}_{q},\cdots,\hat{Y}_{\text{Q}}]=f([X_{1},\cdots,X_{p},\cdots,X_{\text{P}}])$
(1)

where $\hat{Y}_{q}$ is the prediction output and its ground truth is $Y_{q}$.

Figure 2: Figure (a) is the spatial graph of the traffic network where a node
represents a traffic region. Figure (b) is a temporal graph of a week where a
node represents a time slot. Each day is divided equally into T time slots,
denoted as $[1,\dots,\text{T}]$. All time slots are connected sequentially as
a line.

##  III Model

###  III-A Overview

Our model MSGC-Seq2Seq (Multi-Spatial Graph Convolution based Sequence to
Sequence) (as shown in Figure 1) can be roughly divided into three stages. The
first stage is to construct the model input with rich spatiotemporal
information. We fuse the traffic feature with the spatiotemporal information
extracted from its spatial attribute and temporal attribute via graph
embedding methods. The second stage is to capture spatial correlations from
multiple perspectives. We pre-define a spatial matrix based on geographical
proximity and feature trend and we also develop a global spatial matrix on a
data-driven basis. Both of them are both one-step correlation. In addition, a
cross-step spatial correlation based on reachability knowledge is designed.
Three graph convolution networks are leveraged to extract spatial correlations
based on these spatial matrices. The third stage is to learn temporal
dependency from the high-level features produced by graph convolution
networks. High-level features based on one-step spatial correlations are
merged and projected into the encoder of a Seq2Seq model to capture the
temporal properties from these features. In addition, high-level features
based on cross-step spatial correlation (i.e. reachability correlation) are
fed into decoder directly to alleviate the information dilution problem. A
temporal attention mechanism with multiple heads is integrated into Seq2Seq to
enable the model focus on the most relevant input information. The details of
our model is elaborated in the following sections.

###  III-B Spatiotemporal Attributes Fusion

The traffic conditions in a traffic network have both spatial attribute and
temporal attribute. The former refers to where the traffic data is observed
(e.g. a sensor) and the latter refers to when the traffic data is collected
(e.g. time of day, day of week). Such spatiotemporal attributes of traffic
data carry spatiotemporal information explicitly and are obviously valuable
for traffic state prediction. In this paper, we want to enrich the model input
by considering not only the traffic features but also their spatial and
temporal attributes. We utilize the graph embedding methods to encode the
spatial and temporal attributes and fuse them with traffic features.

Spatial Embedding. Following [19]’s work, we utilize node2vec [29] to learn
spatial embedding vector for each node in the traffic network based on its
adjacent matrix as follows:

$\text{SP}=\text{Node2vec}(\mathbf{A})$ (2)

where $\mathbf{A}$ is the adjacent matrix representing the topology of traffic
network. $\text{SP}\in\mathbb{R}^{\text{N}\times\text{F}_{\text{S}}}$ and
$\text{SP}_{i}\in\mathbb{R}^{\text{F}_{\text{S}}}$ is the spatial embedding
for traffic node $i$ and it has preserved the local structure information of
this traffic node.

Temporal Embedding. Some works [19] utilized one-hot embedding to learning
temporal vector for each time slot. However, one-hot embedding method can only
distinguish time slots but overlooks the sequential correlation between time
slots. Different from previous works, we novelly flatten the time slots in a
week and connect them sequentially as a line graph (as shown in Figure 2). We
utilize DeepWalk [30] to learn embedding for each node (i.e. time slot) in the
line graph. In this way, the temporal correlations among time slots are
reserved in the embedding vector. The embedding method is as follows:

$\text{TP}=\text{DeepWalk}(\mathbf{A}_{\text{T}})$ (3)

where $\mathbf{A}_{\text{T}}\in\mathbb{R}^{\text{7T}\times\text{7T}}$ is the
matrix of temporal line graph and T is the number of total time slots in one
day. 7 refers to seven days in a week.
$\text{TP}\in\mathbb{R}^{\text{7T}\times\text{F}_{\text{T}}}$ is the embedding
matrix for all the time slots in a week.
$\text{TP}_{\text{dT+i}}\in\mathbb{R}^{\text{F}_{\text{T}}}$ is the temporal
embedding for time slot $i$ in $d_{th}$ day of a week which carries the
sequential temporal information.

Features Fusion. For each traffic node $i$ in time slot $t$, we can observe
its traffic states $X_{t}^{i}\in\mathbb{R}^{\text{F}_{\text{I}}}$. The spatial
attribute of traffic node $i$ is represented by $\text{SP}_{i}$ and the time
slot $t$ has been assigned a temporal vector $\text{TP}_{t}$ according to its
time of day and day of week attributes. We align them to the same dimension
space through three fully connected layers respectively and then concatenate
them together to get the fusion of all features as follows:

$\text{XST}_{t}^{i}=\rho(W_{x}X_{t})\|\rho(W_{t}\text{TP}_{t})\|\rho(W_{i}\text{SP}_{i})$
(4)

where $\text{XST}_{t}^{i}\in\mathbb{R}^{3\text{F}_{\text{ST}}}$ is the fused
features of traffic node $i$ at $t$.
$\text{XST}_{t}=[\text{XST}_{t}^{1},\dots,\text{XST}_{t}^{\text{N}}]\in\mathbb{R}^{\text{N}\times
3\text{F}_{\text{ST}}}$ is the fused matrix for the whole traffic network.
$\rho$ is the activation function (e.g. ReLu).
${W_{x}\in\mathbb{R}^{\mathbf{F_{\text{ST}}}\times\text{F}_{\text{I}}},W_{t}\in\mathbb{R}^{\text{F}_{\text{ST}}\times\text{F}_{\text{T}}},W_{i}\in\mathbb{R}^{\text{F}_{\text{ST}}\times\text{F}_{\text{S}}}}$
are trainable parameters shared by all the traffic nodes.

###  III-C Multi-view Spatial Graph Convolutions

Figure 3: The visualization of three spatial attention scores.
$[1,\cdots,p,\cdots,P]$ are the input steps and $q$ is an output step.
$a^{ij}$ describes the spatial correlation between traffic node $i$ and
traffic node $j$ based on geographical proximity and feature trend similarity.
$a^{ij}$ is static and local. $a^{ij}_{p}$ represents the semantic correlation
of node pair $ij$ based on their flow patterns on time slot $p$. $a^{ij}_{p}$
is dynamic and global. $a^{ij}_{qp}$ extracts the reachability based spatial
correlation determining by the travel time $m_{ij}$ of node pair and their
time slot gap. $a^{ij}_{qp}$ is cross space and time.

The fused features contain rich spatiotemporal information for each traffic
node. However, the future traffic condition of a target traffic node is
influenced not only by its own historical information but also by historical
observations of other traffic nodes. The fact that traffic objects (e.g.
passengers, vehicles) keep moving from one traffic node to another traffic
node results in the spatial correlations between traffic nodes and such
correlations are complex. Different from most previous works only capturing
one kind of spatial correlation, we model the complex spatial dependency in
the traffic network comprehensively from multiple perspectives, i.e. adjacency
correlation, semantic correlation and reachability correlation. Following
previous works [21, 8, 11, 5, 12], we leverage graph convolutional network to
extract each spatial correlation respectively.

####  III-C1 Graph Convolution Network

Graph Convolution generalizes convolution operation from regular grid data to
graph data. It models influence from related nodes on the target node through
aggregating the features of related nodes [31, 32, 33]. Such aggregation is
usually achieved by the matrix multiplication of feature matrix and spatial
matrix. The aggregated features are fed into fully connected layers to produce
high-level features. The graph convolution layer adopted in this paper can be
denoted as follows:

$Y^{l}=\rho(W\text{L}X^{l-1})=\text{GCN}(A,X^{l-1})$ (5)

where $X^{l-1}$ is the input and $Y^{l}$ is the output of $l_{th}$ graph
convolution layer. $\rho$ is activation function and $W$ is trainable
parameter. $\text{L}=I_{N}-D^{-\frac{1}{2}}AD^{-\frac{1}{2}}$ is the
normalized version of spatial matrix $A$ which represents spatial correlation
in the traffic network. Different spatial correlation is represented by
different spatial matrix. Next, we introduce the construction of spatial
matrix for each kind of spatial correlation in this paper.

####  III-C2 Semantic Spatial Correlation

If two traffic nodes share similar flow patterns, they might have similar
traffic conditions, such as traffic congestion, functional similarity and
owning similar POIs. Therefore, they can learn from each other. Such spatial
correlation based on current flow patterns of traffic nodes is defined as
semantic correlation.

Dynamic Semantic Score. Inspired by the transformer [28], a state-of-the-art
method to learn correlations between objects, we assign two latent semantic
spaces to each traffic node as follows:

$\displaystyle\text{K}_{t}^{i}$
$\displaystyle=W_{k2}(\text{ReLu}(W_{k1}\text{XST}_{t}^{i}))\in\mathbb{R}^{F}$
(6) $\displaystyle\text{Q}_{t}^{i}$
$\displaystyle=W_{q2}(\text{ReLu}(W_{q1}\text{XST}_{t}^{i}))\in\mathbb{R}^{F}$

where $\text{K}_{t}^{i}$, $\text{Q}_{t}^{i}$ are the embeddings in key space
and query space respectively for traffic node $i$ at time slot $t$.
$\\{W_{k1},W_{k2},W_{q1},W_{q2}\\}$ are trainable parameters shared by all
traffic nodes. Further, we can calculate the influence from traffic node $j$
on traffic node $i$ at time slot $t$ as
$a^{ij}_{t}=(\text{K}_{t}^{i})^{T}\bm{\cdot}\text{Q}_{t}^{j}\in\mathbb{R}$.
The corresponding dynamic attention matrix is as follows:

$\begin{split}A^{f}_{t}=\text{Softmax}(\left[\begin{array}[]{cccc}{a^{11}_{t}}&{...}&{a^{1\text{N}}_{t}}\\\
{...}&{...}&{...}\\\ {a^{\text{N}1}_{t}}&{...}&{a^{\text{N}\text{N}}_{t}}\\\
\end{array}\right])\end{split}$ (7)

Note that the Softmax function is operated on each row.

Semantic Correlation Extraction. The dynamic attention matrix contains dynamic
correlations between any two traffic nodes based on their flow patterns. We
capture such spatial dependency through GCN at each input step $p$ as follows:

$\text{XF}_{p}=\text{GCN}(A^{f}_{p},\text{XST}_{p})$ (8)

where $\text{XF}_{p}\in\mathbb{R}^{\text{N}\times\text{F}_{\text{F}}}$ is the
high-level output matrix of the traffic network.

####  III-C3 Adjacent Trend Spatial Correlation

Many previous works focus on capturing the influence between geographically
adjacent traffic nodes and assign different weights to different neighbors of
the target traffic node to model their different influence strength [23, 34,
18, 35]. It is argued in [36] that the correlation of two adjacent roads
depends on their historical traffic speed trends. The larger the proportion
that the speeds of two traffic nodes both rise or fall is, the higher the
correlation between two adjacent traffic node is.

Adjacent Trend Score. Following [36]’s works, we define the adjacent trend
score to present the weight between adjacent traffic nodes based on their
historical traffic states trends as follows:

$\small
a^{ij}=\frac{\sum_{f=1}^{\text{F}_{\text{I}}}[{\text{c}(v^{i}_{t,f}\geq\bar{v}^{i}_{f},v^{j}_{t,f}\geq\bar{v}^{j}_{f})}+\text{c}(v^{i}_{t,f}<\bar{v}^{i}_{f},v^{j}_{t,f}<\bar{v}^{j}_{f})]}{\text{F}_{\text{I}}*\textbf{Total}}$
(9)

where $v^{i}_{t,f}$ and $v^{j}_{t,f}$ are the $f_{th}$ traffic feature of
traffic node $i$ and traffic node $j$ at time $t$. $\bar{v}^{i}_{f}$ and
$\bar{v}^{j}_{f}$ are their average values respectively.
$\text{c}(v^{i}_{t,f}\geq\bar{v}^{i}_{f},v^{j}_{t,f}\geq\bar{v}^{j}_{f})$ and
$\text{c}(v^{i}_{t,f}<\bar{v}^{i}_{f},v^{j}_{t,f}<\bar{v}^{j}_{f})$ are the
numbers of time slots that the $f_{th}$ traffic feature of adjacent traffic
nodes both rise or fall. $\text{F}_{\text{I}}$ is the number of features and
Total is the total number of time slots in historical data. For any two
traffic nodes, if they are adjacent geographically, we calculate the adjacent
trend score as their edge weight. Otherwise, their edge weight is set as zero.
Based on the adjacent trend score, we obtain the adjacent trend matrix
$\text{A}^{a}=(a_{ij})_{\text{N}\times\text{N}}$. Then we capture the spatial
locality based on historical adjacent trend through GCN as follows:

$\text{XA}_{p}=\text{GCN}(\text{A}^{a},\text{XST}_{p})$ (10)

where $\text{XA}_{p}\in\mathbb{R}^{\text{N}\times\text{F}_{\text{A}}}$
contains local spatial dependency based on historical trends of traffic
features.

Figure 4: For the passengers/vehicles departing from traffic node $i$ at time
span $[t_{1},t_{2}]$, most of them arrive at traffic node $j$ during time span
$[t_{1}+\text{M}_{\text{ij}},t_{2}+\text{M}_{\text{ij}}]$ and
$\text{M}_{\text{ij}}$ is the average travel time between traffic node $i$ and
traffic node $j$. The time span $[t_{3},t_{4}]$ is the predicted time span.
There are four correlations between predicted time span and arriving time
span.

####  III-C4 Reachability Spatial Correlation Across Steps

The reachability correlation intends to model the spatial correlation based on
reachability knowledge between any traffic nodes from input steps to output
steps.

Reachability Knowledge. Suppose that we want to predict the traffic states
$v_{j}$ of the target traffic node $j$ during interval $[t_{3},t_{4}]$ with
the traffic states $v_{i}$ of the context traffic node $i$ during previous
interval $[t_{1},t_{2}]$. We denote the average travel time from node $i$ to
node $j$ as $\text{M}_{\text{ij}}$. For simplicity, we assume that all the
passengers spend almost the same time from $i$ to $j$. For all passengers
departing from context traffic node $i$ during $[t_{1},t_{2}]$ to target
traffic node $j$, we can observe that (as shown in Figure 4):

(1) if $t_{3}>t_{2}+\text{M}_{\text{ij}}$, nearly all passengers can’t reach
traffic node $j$ during $[t_{3},t_{4}]$. Therefore, there is little
correlation between traffic condition $v_{j}$ and $v_{i}$ from reachability
perspective.

(2) if $t_{4}>t_{2}+\text{M}_{\text{ij}}\geq t_{3}$ or
$t_{4}>t_{1}+\text{M}_{\text{ij}}\geq t_{3}$, we can infer that part of
passengers can reach traffic node $j$ during $[t_{3},t_{4}]$. For simplicity,
we assume that all passengers enter a traffic node evenly during the given
time slot, therefore the influence strength between these two traffic nodes
depends on the overlap of
$[t_{1}+\text{M}_{\text{ij}},t_{2}+\text{M}_{\text{ij}}]$ and $[t_{3},t_{4}]$.

(3) if $t_{1}+\text{M}_{\text{ij}}>t_{4}$, passenger might have already
arrived at traffic node $j$ before $t_{4}$. If passengers don’t stay, they
might leave $j$ for a long time. Therefore, we can infer that the impact from
$v_{i}$ on $v_{j}$ is critically little.

Reachability Score. To calculate the correlation between traffic nodes across
different time slots based on reachability knowledge, we novelly define the
reachability score as follows:

$a_{qp}^{ji}=\left\\{\begin{array}[]{ll}1&i=j\\\
0&p\delta+\text{M}_{\text{ij}}<(q-1)\delta,i\neq j\\\
0&p(\delta-1)+\text{M}_{\text{ij}}>q\delta,i\neq j\\\
\frac{\text{M}_{\text{ij}}+p\delta-(q-1)\delta}{\delta}&(q-1)\delta<p\delta+\text{M}_{\text{ij}},i\neq
j\\\ \frac{q\delta-\text{M}_{\text{ij}}-(p-1)\delta}{\delta}&q\delta\geq
p(\delta-1)+\text{M}_{\text{ij}},i\neq j\\\ \end{array}\right.$ (11)

where $[t_{1},t_{2}]=[(p-1)\delta,p\delta]$,
$[t_{3},t_{4}]=[(q-1)\delta,q\delta]$. Here $\delta$ is time granularity, $p$
is the input step and $q$ is the output step. $a_{qp}^{ji}\in[0,1]$ is the
attention score based on reachability indicating the importance of context
traffic node $i$ at step $p$ to target traffic node $j$ at step $q$. If there
is little correlation between traffic condition $i$ and $j$, $a_{qp}^{ji}=0$
and the importance of a traffic node to itself is defined as $a_{qp}^{ii}=1$.

With the attention score $a_{qp}^{ji}$, we can construct the reachability
matrix which represents the influence from the whole network at input step $p$
on the whole network at output step $q$, denoted as
$A^{r}_{qp}\in\mathbb{R}^{\text{N}\times\text{N}}$ as follows:

$\begin{split}A^{r}_{qp}=\left[\begin{array}[]{cccc}{a_{qp}^{11}}&{...}&{a_{qp}^{1\text{N}}}\\\
{...}&{...}&{...}\\\ {a_{qp}^{\text{N}1}}&{...}&{a_{qp}^{\text{N}\text{N}}}\\\
\end{array}\right]\end{split}$ (12)

Reachability Correlation Extraction. Based on the reachability attention
matrix, we can extract the spatial dependency from input step $p$ on output
step $q$ with graph convolution network as follows:

$\text{XR}_{qp}=\text{GCN}(A_{qp}^{r},\text{XST}_{p})$ (13)

where $\text{XR}_{qp}\in\mathbb{R}^{\text{N}\times\text{F}_{\text{R}}}$ is the
high-level features containing influence from step $p$ on step $q$. To measure
the impact from all input steps on the output step $q$, we concatenate them
together:
$\text{XR}_{q}=[\text{XR}_{q1},\dots,\text{XR}_{q\text{P}}]\in\mathbb{R}^{\text{N}\times\text{P}\text{F}_{\text{R}}}$.

We have extracted the spatial correlations by graph convolution network from
three perspectives above. In the next section, we will extract the temporal
dependency from the high-level features produced by GCN.

###  III-D Multi-Head Temporal Attention Based Seq2Seq

In this paper, we aim to predict the traffic status of the traffic network
over multiple future steps. This is a typical multi-step time series
prediction problem. We employ the Sequence to Sequence (Seq2Seq) model with an
encoder and a decoder to extract the temporal dependency [37]. Seq2Seq takes
an input sequence to generate an output sequence with different length as
follows:

$[\mathbf{X}_{1},\cdots,\mathbf{X}_{p},\cdots,\mathbf{X}_{\mathbf{P}}]\stackrel{{\scriptstyle
Seq2Seq}}{{\longrightarrow}}[\hat{\mathbf{Y}}_{1},\cdots,\hat{\mathbf{Y}}_{q},\cdots,\hat{\mathbf{Y}}_{\mathbf{Q}}]$
(14)

We leverage GRU (Gated Recurrent Units) [38] as the encoder and decoder to
learn the long-term temporal dependency in traffic data, for that GRU is a
simple yet powerful and efficient variant of RNNs.

####  III-D1 Multi-Spatial Seq2Seq

We have captured three kinds of spatial dependencies through graph convolution
networks respectively. Semantic matrix and adjacent matrix both contain the
spatial correlations among traffic nodes at the same time slot while
reachability matrix contains spatial dependency among traffic nodes at
different time slots. In other words, high-level features based on semantic
correlation and adjacent correlation only contain spatial dependency extracted
at each input step and we feed them into the encoder to learn the temporal
dependency from all the input steps. However, the reachability correlation has
already extracted the spatiotemporal dependency from all the previous input
steps. Therefore, we directly feed the high-level features based on
reachability into the decoder at each output step. The Seq2Seq taking multi-
spatial correlations as inputs is stated as follows:

$\begin{split}\text{H}_{p}&=\operatorname{GRU\\_Encoder}(W_{1}(\text{xf}_{p}\|\text{xa}_{p}),\text{H}_{p-1})\\\
\text{C}&=\text{H}_{\text{P}}\\\
\text{S}_{q}&=\operatorname{GRU\\_Decoder}(W_{2}(\text{C}\|\text{xr}_{q}\|\mathbf{Y}_{q-1}),\text{S}_{q-1})\\\
\hat{\mathbf{Y}}_{q}&=\text{ReLu}(W_{3}\text{S}_{q})\end{split}$ (15)

where $\text{H}_{p}\in\mathbb{R}^{\text{F}_{\text{H}}}$ is the hidden state of
encoder at input step $p$ and $C\in\mathbb{R}^{\text{F}_{\text{H}}}$ is the
context vector, $S_{q}\in\mathbb{R}^{\text{F}_{\text{S}}}$ is the decoder
hidden state at output step $q$.
$\mathbf{Y}_{q-1}\in\mathbb{R}^{\text{F}_{\text{O}}}$ is the ground truth at
step $q-1$ and $\hat{\mathbf{Y}}_{q}\in\mathbb{R}^{\text{F}_{\text{O}}}$ is
the prediction output at step $q$. $\\{W_{1},W_{2},W_{3}\\}$ are the trainable
parameters.
$\text{xf}_{p}\in\mathbb{R}^{\text{F}_{\text{F}}},\text{xa}_{p}\in\mathbb{R}^{\text{F}_{\text{A}}},\text{xr}_{q}\in\mathbb{R}^{\text{P}\text{F}_{\text{R}}}$
are vectors from $\text{XF}_{p},\text{XA}_{p},\text{XR}_{q}$, representing
high-level features of a traffic node based on semantic similarity, adjacent
trend and reachability respectively.

Following [6], we integrate scheduled sampling into Seq2Seq to ease the
prediction error accumulation problem, which feeds $\mathbf{Y}_{q-1}$ into the
model with $\epsilon_{i}$ probability and $\hat{\mathbf{Y}}_{q-1}$ with
$1-\epsilon_{i}$ at $i_{th}$ iteration during training process.

####  III-D2 Multi-Temporal Attention

The previous traffic conditions at different steps of the encoder can impact
each future step of the decoder differently [6]. To model such relationship, a
temporal attention allows the decoder to focus on relevant historical
observations for any given future step by assigning different attention
weights to every encoder hidden state
$[\text{H}_{1},\cdots,\text{H}_{\text{P}}]$. Inspired by [39], we calculate
the attention score between historical step $p$ and future step $q$ and
normalize it through a Softmax layer:

$\begin{split}e_{qp}&=(v)^{T}\text{tanh}(W[\text{H}_{p}\|\text{S}_{q-1}])\\\
\alpha_{qp}&=\frac{\exp(e_{qp})}{\sum_{i=1}^{\text{P}}\exp(e_{qi})}\end{split}$
(16)

where
$W\in\mathbb{R}^{\text{F}_{\text{e}}\times(\text{F}_{\text{H}}+\text{F}_{\text{S}})}$
and $v\in\mathbb{R}^{\text{F}_{\text{e}}}$. With the temporal attention
scores, the decoder hidden state $\text{S}_{q}$ can be updated as follows:

$\begin{split}\text{C}_{q}&=\sum_{p=1}^{\text{P}}\alpha_{qp}\text{H}_{p}\\\
\text{S}_{q}&=\operatorname{GRU\\_Decoder}(W_{2}(\text{C}_{q}\|\text{xr}_{q}\|\mathbf{Y}_{q-1}),\text{S}_{q-1})\end{split}$
(17)

To learn more complicated time dependency in different perspectives, we also
extend the temporal attention to H heads as follows:

$\begin{split}e_{qp}^{h}&=(v_{h})^{T}\text{tanh}(W_{h}[\text{H}_{p}\|\text{S}_{q-1}])\\\
\alpha_{qp}^{h}&=\frac{\exp(e_{qp}^{h})}{\sum_{i=1}^{\text{P}}\exp(e_{qi}^{h})}\\\
\text{C}_{q}&=\sum_{p=1}^{\text{P}}W^{C}_{h}(\|_{h=1}^{\text{H}}\alpha_{qp}^{h}\text{H}_{p})\end{split}$
(18)

where
$W_{h}\in\mathbb{R}^{\text{F}_{\text{e}}\times(\text{F}_{\text{H}}+\text{F}_{\text{S}})}$
and $v_{h}\in\mathbb{R}^{\text{F}_{\text{e}}}$,
$W^{C}_{h}\in\mathbb{R}^{\text{F}_{\text{H}}\times\text{H}\text{F}_{\text{H}}}$
.

##  IV Experiments

This paper focuses on the research questions as follows:

(1) How does our model MSGC-Seq2Seq perform at prediction accuracy and
efficiency compared with other benchmarks on different datasets?

(2) Does each component in our model make contributions for prediction?

(3) What’s the performance of our model when the traffic data is insufficient
and noisy?

(4) How does our model react to parameter sensitivity test?

To answer the research questions above, we conduct extensive experiments on
two real-world highway traffic datasets.

###  IV-A Datasets

We compare our model with baselines on the following highway traffic datasets.

METR collects traffic speed by sensors on the highway of Los Angeles County.
We utilize 207 sensors in the highway and the time period observed is from Mar
1st to Jun 30th in 2012, i.e. four months.

PEMS datasets are from California Transportation Agencies’ (CalTrans)
Performance Measurement System (PeMS). There are more than 39,000 sensors
deployed on the highway in the major metropolitan areas in California [5]. The
Geographic information about each sensor is recorded in the datasets. The
traffic measurement chosen in this experiment is the average traffic speed,
which is collected in real time every 30 seconds and aggregated in 5 minutes.
The dataset in this paper contains 6 months data ranging from Jan to May in
2017 in the San Francisco Bay Area and 325 sensors are selected.

For all the datasets, 70% data is utilized for training, 10% for validation
and the rest 10% for testing, and Z-Score normalization [6] is applied to
normalize the datasets. We follow the way in [6] to build the adjacent matrix.
The details of the datasets are shown in Table I.

TABLE I: The Details of Datasets Datasets | Date | Days | Sensors | Train | Val | Test
---|---|---|---|---|---|---
METR | 03/01-06/27(2012) | 119 | 207 | 4,966,012 | 709,430 | 1,418,860
PEMS | 01/01-06/31(2017) | 181 | 325 | 11,859,120 | 1,694,160 | 3,388,320
TABLE II: Evaluation of Various Approaches for Traffic State Prediction on Different Datasets Datasets | Steps | 3 (15min) | 6 (30min) | 12 (60min)
---|---|---|---|---
Metrics | MAE | RMSE | MAPE (%) | MAE | RMSE | MAPE (%) | MAE | RMSE | MAPE (%)
METR | HA | 4.160±0.000 | 7.800±0.000 | 13.000±0.000 | 4.160±0.000 | 7.800±0.000 | 13.000±0.000 | 4.160±0.000 | 7.800±0.000 | 13.000±0.000
ARIMA | 3.990±0.000 | 8.210±0.000 | 9.600±0.000 | 5.150±0.000 | 10.450±0.000 | 12.700±0.000 | 6.900±0.000 | 13.230±0.000 | 17.400±0.000
VAR | 4.420±0.000 | 7.890±0.000 | 10.200±0.000 | 5.410±0.000 | 9.130±0.000 | 12.700±0.000 | 6.520±0.000 | 10.110±0.000 | 15.800±0.000
SVR | 3.990±0.000 | 8.450±0.000 | 9.300±0.000 | 5.050±0.000 | 10.870±0.000 | 12.100±0.000 | 6.720±0.000 | 13.760±0.000 | 16.700±0.000
FNN | 3.990±0.110 | 7.517±0.135 | 12.088±1.052 | 4.266±0.010 | 8.581±0.033 | 12.103±0.096 | 4.490±0.000 | 9.410±0.024 | 12.497±0.070
FC-LSTM | 3.451±0.006 | 6.021±0.018 | 9.210±0.024 | 3.798±0.024 | 7.096±0.049 | 10.933±0.148 | 4.372±0.001 | 8.311±0.036 | 13.447±0.109
STGCN | 2.821±0.001 | 5.353±0.008 | 7.227±0.009 | 3.366±0.006 | 6.567±0.016 | 9.250±0.037 | 3.981±0.019 | 7.808±0.013 | 11.733±0.145
DCRNN | 2.696±0.015 | 4.994±0.005 | 6.780±0.008 | 3.092±0.065 | 5.993±0.181 | 8.150±0.144 | 3.452±0.114 | 6.904±0.235 | 9.597±0.388
GAMAN | 2.646±0.005 | 5.045±0.020 | 6.725±0.055 | 2.934±0.006 | 5.810±0.022 | 7.953±0.121 | 3.341±0.005 | 6.818±0.054 | 9.783±0.213
| MSGC-Seq2Seq | 2.503±0.011 | 4.732±0.018 | 6.247±0.061 | 2.757±0.003 | 5.470±0.027 | 7.230±0.050 | 3.088±0.010 | 6.457±0.053 | 8.700±0.078
PEMS | HA | 2.880±0.000 | 5.590±0.000 | 6.800±0.000 | 2.880±0.000 | 5.590±0.000 | 6.800±0.000 | 2.880±0.000 | 5.590±0.000 | 6.800±0.000
ARIMA | 1.620±0.000 | 3.300±0.000 | 3.500±0.000 | 2.330±0.000 | 4.760±0.000 | 5.400±0.000 | 3.380±0.000 | 6.500±0.000 | 8.300±0.000
VAR | 1.740±0.000 | 3.160±0.000 | 3.600±0.000 | 2.320±0.000 | 4.250±0.000 | 5.000±0.000 | 2.930±0.000 | 5.440±0.000 | 6.500±0.000
SVR | 1.850±0.000 | 3.590±0.000 | 3.800±0.000 | 2.480±0.000 | 5.180±0.000 | 5.500±0.000 | 3.280±0.000 | 7.080±0.000 | 8.000±0.000
FNN | 2.149±0.090 | 4.613±0.856 | 5.327±0.948 | 2.291±0.046 | 5.077±0.501 | 5.613±0.528 | 2.481±0.006 | 5.684±0.061 | 6.167±0.167
FC-LSTM | 2.196±0.003 | 4.498±0.018 | 5.045±0.039 | 2.320±0.013 | 4.809±0.014 | 5.382±0.018 | 2.451±0.003 | 5.125±0.008 | 5.813±0.029
STGCN | 1.349±0.014 | 2.770±0.007 | 2.783±0.033 | 1.768±0.030 | 3.912±0.038 | 3.960±0.110 | 2.417±0.022 | 5.429±0.064 | 5.857±0.029
DCRNN | 1.328±0.061 | 2.597±0.036 | 2.663±0.139 | 1.700±0.071 | 3.580±0.056 | 3.600±0.148 | 1.991±0.093 | 4.536±0.131 | 4.607±0.186
GAMAN | 1.264±0.010 | 2.649±0.033 | 2.584±0.048 | 1.619±0.018 | 3.627±0.044 | 3.582±0.114 | 1.816±0.011 | 4.069±0.020 | 4.217±0.056
| MSGC-Seq2Seq | 1.102±0.005 | 2.255±0.017 | 2.210±0.013 | 1.344±0.006 | 3.024±0.033 | 2.870±0.030 | 1.592±0.006 | 3.678±0.009 | 3.545±0.055

###  IV-B Experimental Settings

####  IV-B1 Evaluation Metrics

MAE (Mean Absolute Error), RMSE (Root Mean Square Error) and MAPE (Mean
Absolute Percentage Error) are the most widely utilized evaluation metrics in
traffic state prediction tasks. Following previous works [5, 19, 6], we
utilize them to evaluate the model performance.

####  IV-B2 Baselines

We compare our approach with the following baselines, which can be categorized
as traditional statistic methods (i.e. HA, VAR, ARIMA, SVR) and simple deep
learning methods (i.e. FNN, FC-LSTM), graph-based deep learning methods
(STGCN, DCRNN, GMAN).

HA: Historical Average, which predicts the future traffic conditions by
averaging the traffic conditions at historical time.

VAR: Vector Auto-Regression is extensively leveraged in time series prediction
task. It is a simple multivariate model where each variable is explained by
its own past values and the past values of all the other variables in the
system.

ARIMA [40]: Auto-regressive integrated moving average, a well known model for
predicting time series data.

SVR: Support Vector Regression is a regression method utilizing linear support
vector machine in prediction.

FNN: Feed Foward Neural Network can extract the nonlinearity in traffic data.

FC-LSTM [37]: A variant of Long Short Term Memory Network with fully connected
layer as the output layer.

STGCN [17]: Spatio-temporal graph convolutional network which consists of
graph convolutional layers and 1D convolution layers and can capture both
spatial and temporal dependencies in traffic prediction.

DCRNN [6]: Diffusion Convolutional Recurrent Neural Network, which integrates
diffusion convolution with recurrent neural network to capture the spatial and
temporal properties in traffic data.

GAMAN [19]: Graph Multi-Attention Network, which designs an encoder-decoder
architecture with multiple spatio-temporal attention mechanisms to predict
traffic conditions.

####  IV-B3 Parameter Settings

For baselines STGCN, DCRNN, GMAN, we utilize the parameter settings as
suggested by the original papers as much as possible. Following previous works
[6], the number of input steps is set the same as output steps. For instance,
we use $\text{P}=3$ steps (15 minutes) to predict the next $\text{Q}=3$ steps
(15 minutes). In terms of training, Adam optimizer [41] is utilized to
optimize all the deep learning methods. The maximum number of epochs is set as
1000 and the batch size is set as 16. The the initial learning rate is 0.001
with a learning rate decay strategy. Our model is developed using Python and
TensorFlow 1.x. Most of the experiments are run on a GPU (32GB) machine with
TESLA V100.

The hyper-parameters in our model include the spatiotemporal embedding
dimension $\text{F}_{\text{ST}}$, the number of hidden units of GRU in encoder
$\text{F}_{\text{H}}$ and decoder $\text{F}_{\text{S}}$, the number of heads
in temporal attention H, the numbers of hidden units in adjacency GCN,
semantic GCN and reachability GCN, i.e.
$[\text{F}_{\text{A}},\text{F}_{\text{F}},\text{F}_{\text{R}}]$. For
simplicity, both encoder and decoder have two layers and each layer shares the
same number of hidden units. All GCN in this paper have two layers and each
layer shares the same number of hidden units. All parameters are tuned on the
validation set and we get the best model performance on the setting
$\text{F}_{\text{A}}=\text{F}_{\text{F}}=\text{F}_{\text{R}}=64,\text{F}_{\text{ST}}=256,\text{F}_{\text{H}}=\text{F}_{\text{S}}=64,\text{H}=5$.

(a) METR

(b) PEMS

Figure 5: Model Performances of Graph Deep Learning Methods at Each Output
Step on Two Datasets For 12 Steps Prediction.

###  IV-C Experimental Analysis

To reduce the randomness of deep learning based methods in Table II, we repeat
the related experiments five times to get more stable and convincing results.
We present their model performances with the means and standard errors of all
metrics. In addition, the experiment results of traditional methods (i.e. HA,
ARMIA,VAR, SVR) are from previous work [6]. The best performance on each
dataset is highlighted in bold font.

####  IV-C1 Approaches Comparison

In this subsection, we compare our model with other benchmarks in the overall
model performance, efficiency, and visualization.

Figure 6: The Fault Tolerance Test of All the Deep Learning Models on METR
Dataset for 3 Steps with Fault Ratio Ranging from $[0\%,\cdots,90\%]$ Figure
7: The Data Sparsity Test of Graph-based Deep Learning Models on METR Dataset
for 3 Steps with Data Propotion Ranging from $[10\%,\cdots,100\%]$

(a) Weekday

(b) Weekend

Figure 8: The Comparison between Ground Truth and Predictions of All the Deep
Learning Models on METR Dataset on One Day.

Model Performance. As shown in Table II, the graph-based deep learning methods
(STGCN, DCRNN, GMAN, MSGC-Seq2Seq) perform significantly better than the
simple deep learning methods (i.e. FNN, FC-LSTM) and statistic methods. It
proves the effectiveness of extracting spatial correlation based on a traffic
graph. When the predicted time period is short (i.e. 3 steps), some statistic
method even has a better performance than the simple deep learning methods.
For example, ARIMA performs better than FNN and FC-LSTM at PEMS dataset on 3
steps. However, as the output steps become longer, the deep learning methods
show their superiority over statistic methods, probably because the
spatiotemporal correlation become more complex in a long time prediction.
Among the graph-based deep learning approaches, our model has the best
performance on two datasets at all the metrics. On METR dataset, compared with
STGCN, it has increased nearly 1% in MAPE on 3 steps. When the predicted
period become longer, the MAPE gap between these two models becomes larger,
i.e. 2% on 6 steps, 3% on 12 steps. On PEMS dataset, the differences on MAPE
between MSGC-Seq2Seq and STGCN become more obvious, i.e. 0.5%, 1%, 2.3% on 3,
6, 12 steps respectively. It proves that our model can handle long outsteps
better than STGCN, perhaps due to its mechanisms to ease information dilution
in a long term prediction.

TABLE III: Efficiency Per Epoch of Deep Learning Models Models | FNN | FC-LSTM | STGCN | DCRNN | GMAN | MSGC-Seq2Seq
---|---|---|---|---|---|---
train | 15.4 | 19 | 57.8 | 54.5 | 123.7 | 70.7
test | 3.2 | 3.2 | 8.2 | 9.6 | 20 | 11.4
total | 19.5 | 23 | 68.1 | 66.6 | 147.4 | 84.9

Multiple Prediction Steps Analysis. We analyze the model performance at each
output step of the graph-based deep learning methods which have a
significantly better performance than other methods. As shown in Figure 5,
nearly all models achieve the best performance at the first output step. As
the time gap between input steps and output steps increases, the model
performance become worse and worse. The deterioration rates of different
models are different. The deterioration rate of DCRNN is the fastest while
that of GMAN is the slowest. As to our model, it has a suboptimal
deterioration rate.

Efficiency. Table III shows the average time per epoch of all the deep
learning based models on METR dataset for 3 steps prediction. FNN and FC-LSTM
require the least time to finish an epoch, around 20 seconds for that they
have the simplest structures and the fewest trainable parameters. Both STGCN
and DCRNN need less than 60 seconds to finish training. GMAN has the longest
time per epoch, nearly 400 seconds probably because it has the largest number
of trainable parameters. Our model MSGC-Seq2Seq takes less than half of the
time required by GMAN while it has the best performance on both datasets. Note
that the reachability attention matrix in our model is calculated during the
data preprocess.

Visualization. In order to visualize the prediction results of all the deep
learning models, we randomly choose a node in the traffic network (i.e. a
sensor) of METR dataset to observe the prediction values of its traffic speed
on one day of weekday and weekend (also chosen randomly). Note that we choose
the first output step prediction as the observed prediction values because the
prediction at the first output step is the most accurate. As shown in Figure
8, our model seems to have a better prediction at the peek hour in afternoon.

####  IV-C2 Model Ablation

TABLE IV: The Degraded Model in METR Dataset (3 STEPS) Model | MAE | RMSE | MAPE
---|---|---|---
No Temporal Embedding | 2.57±0.007 | 4.84±0.006 | 6.46±0.030
No Spatial Embedding | 2.74±0.003 | 5.12±0.008 | 6.91±0.030
No Spatiotemporal Embedding | 2.74±0.001 | 5.11±0.004 | 6.84±0.010
No Adjacent Correlation | 2.52±0.002 | 4.71±0.010 | 6.28±0.015
No Semantic Correlation | 2.70±0.001 | 5.08±0.011 | 6.81±0.010
No Reachability Correlation | 2.54±0.021 | 4.78±0.052 | 6.34±0.110
No Temporal Attention | 2.56±0.007 | 4.79±0.007 | 6.41±0.010
MSGC-Seq2Seq | 2.50±0.011 | 4.73±0.020 | 6.24±0.064

We integrate spatial attribute embedding, temporal attribute embedding, three
kinds of spatial correlations and multi-head temporal attention mechanism into
our model MSGC-Seq2Seq. To evaluate the effect of these mechanisms, we remove
them from the original model to observe the performance of the corresponding
degraded models. We conduct the experiments on METR dataset for 3 steps
prediction. The results in Table IV show that the prediction performance
decreases no matter which mechanism to remove, indicating that all mechanisms
make contributions to improve the model performance. However, as we can see in
Table IV, their contributions are different. When the Spatiotemporal Embedding
or the Semantic Correlation are removed, the model performance becomes worst,
referring that they play more important roles than other mechanisms.

####  IV-C3 Fault-tolerance Test

In real world traffic scenarios, we might collect the low-quality data with
missing or wrong values due to the limited data collection methods and tools.
In addition, mistakes brought by some data processing methods also decrease
the data reliability. Therefore, the robustness of an approach to process
noisy data is important for real world application. In this subsection, we
want to test the effectiveness of our model and compare it with other
benchmarks. We choose a set of fault-ratio from 10% to 90% to replace the
traffic data values with noise of zero values. As we can see from Figure 6,
the performances of all models on all metrics deteriorate quickly as the
proportion of noise increases, however, in different speed. Among the graph
deep learning methods, performance of STGCN becomes worse more quickly than
others which refers that its robustness is the worst. Surprisingly, FC-LSTM
has the lowest rate of deterioration among all the deep learning methods. When
the fault-ratio is 90%, FC-LSTM has the suboptimal performance while STGCN has
the worst performance. The relative performance of ANN also becomes better as
the data becomes noisier. This implicates that simple deep learning models
have better capacity to combat noise. However, our model also has a slower
deteriorated rate and its performance evaluated by MAE and MAPE are the best
on all the fault-ratio settings. This proves that MSGC-Seq2Seq is effective
and robust in the cases where the data is noisy. The mechanisms we design to
enhance the spatiotemporal information in the model might play a key role
against noisy data.

####  IV-C4 Data Sparsity Test

We want to test the effectiveness of graph deep learning models in sparse data
scene.We randomly sample several subdatasets from METR at a proportion ranging
from 10% to 100% and conduct experiments for 3 steps prediction. As shown in
Figure 7, as the data scale decreases, most models generally have worse
performances but in different speeds. The performance of our model decreases
steadily while GMAN performance has a slight fluctuation. Note that our model
performs better than other methods in all data scale, proving the
effectiveness of our model and such effectiveness is more obvious when data
size is smaller.

(a) Spatiotemporal Embedding Dimension (b) The Number of GCN Units (c) The
Number of GRU Units (d) The Number of Heads

Figure 9: Sensitivity Test on Different Hyper Parameters on METR Dataset for 3
Steps.

####  IV-C5 Parameter Sensitivity Analysis

In this section, we choose several important hyper-parameters to analyze the
parameter sensitivity of our model on METR dataset for 3 steps prediction as
follows:

Spatiotemporal Embedding Dimension. We conduct experiments on different
embedding dimensions, i.e. [16, 32, 64, 128, 256, 512]. As shown in Figure 9,
when the number of dimension units increases, the MAE decreases. When the
dimension is 256, our model has the best performance at MAE. When it keeps
increasing, the model performance decreases, perhaps due to overfitting
problem.

GCN Units. We choose [8, 16, 32, 64, 128] GCN units to conduct the
experiments. The smallest MAE is achieved at 64 units.

GRU Units. [16, 32, 64, 128, 256] GRU units are chosen to conduct the
experiments. The smallest MAE is also achieved at 64 units.

The Multiple Heads. The head list test in the experiment is [1, 2, 3, 4, 5].
Figure 9 shows that the best performance achieves at 5 heads. If there are
only 1 or 2 heads, the model might be unable to capture more complex
correlation in traffic data. However, more heads might lead to more
parameters, resulting in overfitting.

##  V Related Work

Traffic prediction has been extensively researched for many years. Compared
with statistic methods in early stage (e.g. ARIMA [42], VAR [43], Kalman
filtering [44]), which can only capture linear correlation in traffic data,
and traditional machine learning (e.g. Support Vector Machine [45], K-Nearest
Neighbors [46]) which requires handcrafted feature engineering, deep learning
based methods provide an end-to-end learning and have the superior capacity to
capture the complex traffic pattern. The main ideas of most deep learning
frameworks in traffic tasks can be summarized as: first aggregate the spatial
dependencies between nodes at the same input step, then treat the aggregated
traffic features over multiple input steps as a high-dimensional time series
and extract the temporal dependency in the time series.

To capture the spatial dependency, CNNs [47] decompose the network into grids
while many traffic networks are graph based naturally. Recently, GNNs [5, 12]
are used to aggregate features from neighbors based on the adjacent matrix or
data-driven matrix [5, 12]. These models have extracted the spatial
information of the network in each input step and achieved better performance
than previous works. However, they can not work well to extract complex
spatio-temporal dependencies in multi-step forecasting for that the spatial
correlation between nodes across different time steps is not well considered.

To extract the temporal dependency, LSTM and GRU are often adopted for one
step prediction [48, 49, 14]. For multi-step forecasting, Seq2Seq model with
an encoder and a decoder is commonly utilized [50, 6]. To distinguish the
different impact of each input step on a given future step, a temporal
attention mechanism, which can help a model make decisions by focusing on the
important parts of input data [51, 52, 53, 54], is added to the decoder [55,
20, 19, 5]. However, few works pay attention to differentiate the contribution
of different feature dimensions for prediction, which is important to help a
model focus on the important input features.

##  VI Conclusion

In this paper, we focus on traffic network level multi-step traffic
prediction. Compared with one-step traffic prediction, multi-step traffic
prediction is more challenging because it requires to fully model the dynamic
correlations among traffic nodes across time and space in a longer period. To
address this problem, we design a novel deep learning model called MSGC-
Seq2Seq. We first use the traffic features and their spatiotemporal attributes
via graph embedding methods to enrich the spatiotemporal information of model
input. Afterward, we extract spatial correlations based on both data-driven
knowledge (i.e. semantic similarity) and prior knowledge (geographical
proximity and feature similarity). The former can dig out hidden traffic
patterns while the latter can provide more valuable spatial information,
especially in insufficient or noisy data cases. Then we extract the temporal
dependency by utilizing a GRU-based Seq2Seq model. We novelly develop a cross-
step attention mechanism based on reachability to ease the dilution problem in
Seq2Seq. In addition, we employ a multi-head temporal attention to distinguish
the impact from different historical steps on each future step. We conduct
experiments on two real-world traffic datasets. The experiments demonstrate
that our model outperforms other baselines.

## References

  * [1] P. Xie, T. Li, J. Liu, S. Du, X. Yang, and J. Zhang, “Urban flow prediction from spatiotemporal data using machine learning: A survey,” _Information Fusion_ , 2020.
  * [2] X. Ma, Z. Tao, Y. Wang, H. Yu, and Y. Wang, “Long short-term memory neural network for traffic speed prediction using remote microwave sensor data,” _Transportation Research Part C: Emerging Technologies_ , vol. 54, pp. 187–197, 2015.
  * [3] D. Wang, J. Zhang, W. Cao, J. Li, and Y. Zheng, “When will you arrive? estimating travel time based on deep neural networks,” in _AAAI_ , 2018.
  * [4] J. Ye, J. Zhao, K. Ye, and C. Xu, “How to build a graph-based deep learning architecture in traffic domain: A survey,” _IEEE Transactions on Intelligent Transportation Systems_ , pp. 1–21, 2020.
  * [5] S. Guo, Y. Lin, N. Feng, C. Song, and H. Wan, “Attention based spatial-temporal graph convolutional networks for traffic flow forecasting,” in _AAAI_ , 2019, pp. 922–929.
  * [6] Y. Li, R. Yu, C. Shahabi, and Y. Liu, “Diffusion convolutional recurrent neural network: Data-driven traffic forecasting,” in _ICLR_ , 2018.
  * [7] X. Zhou, Y. Shen, and L. Huang, “Revisiting flow information for traffic prediction,” _arXiv:1906.00560_ , 2019.
  * [8] L. Ge, H. Li, J. Liu, and A. Zhou, “Temporal graph convolutional networks for traffic speed prediction considering external factors,” in _MDM_ , 2019, pp. 234–242.
  * [9] J. Sun, J. Zhang, Q. Li, X. Yi, and Y. Zheng, “Predicting citywide crowd flows in irregular regions using multi-view graph convolutional networks,” _IEEE Transactions on Knowledge and Data Engineering_ , 2020.
  * [10] S. Fang, Q. Zhang, G. Meng, S. Xiang, and C. Pan, “Gstnet: Global spatial-temporal network for traffic flow prediction,” in _Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence, IJCAI 2019_ , 2019, pp. 2286–2293.
  * [11] J. J. Q. Yu and J. Gu, “Real-time traffic speed estimation with graph convolutional generative autoencoder,” _IEEE Transactions on Intelligent Transportation Systems_ , vol. 20, no. 10, pp. 3940–3951, 2019.
  * [12] Z. Diao, X. Wang, D. Zhang, Y. Liu, K. Xie, and S. He, “Dynamic spatial-temporal graph convolutional neural networks for traffic forecasting,” in _AAAI_ , 2019, pp. 890–897.
  * [13] B. Yu, H. Yin, and Z. Zhu, “St-unet: A spatio-temporal u-network for graph-structured time series modeling,” _arXiv:1903.05631_ , 2019.
  * [14] C. Chen, K. Li, S. G. Teo, X. Zou, K. Wang, J. Wang, and Z. Zeng, “Gated residual recurrent graph neural networks for traffic prediction,” in _AAAI_ , 2019, pp. 485–492.
  * [15] J. Li, Z. Han, H. Cheng, J. Su, P. Wang, J. Zhang, and L. Pan, “Predicting path failure in time-evolving graphs,” in _KDD_ , 2019, pp. 1279–1289.
  * [16] Z. Wu, S. Pan, G. Long, J. Jiang, and C. Zhang, “Graph wavenet for deep spatial-temporal graph modeling,” in _IJCAI_ , 2019.
  * [17] B. Yu, H. Yin, and Z. Zhu, “Spatio-temporal graph convolutional networks: A deep learning framework for traffic forecasting,” in _IJCAI_ , 2018, pp. 3634–3640.
  * [18] Y. Zhang, S. Wang, B. Chen, and J. Cao, “GCGAN: generative adversarial nets with graph CNN for network-scale traffic prediction,” in _IJCNN_ , 2019, pp. 1–8.
  * [19] C. Zheng, X. Fan, C. Wang, and J. Qi, “Gman: A graph multi-attention network for traffic prediction,” in _AAAI_ , 2020.
  * [20] Z. Zhang, M. Li, X. Lin, Y. Wang, and F. He, “Multistep speed prediction on traffic networks: A deep learning approach considering spatio-temporal dependencies,” _Transportation Research Part C: Emerging Technologies_ , vol. 105, pp. 297–322, 2019.
  * [21] X. Geng, Y. Li, L. Wang, L. Zhang, Q. Yang, J. Ye, and Y. Liu, “Spatiotemporal multi-graph convolution network for ride-hailing demand forecasting,” in _AAAI_ , vol. 33, 2019, pp. 3656–3663.
  * [22] K. Guo, Y. Hu, Z. Qian, H. Liu, and e. Zhang, “Optimized graph convolution recurrent neural network for traffic prediction,” _IEEE Transactions on Intelligent Transportation Systems_ , pp. 1–12, 2020.
  * [23] J. Hu, C. Guo, B. Yang, and C. S. Jensen, “Stochastic weight completion for road networks using graph convolutional networks,” in _ICDE_ , 2019, pp. 1274–1285.
  * [24] J. Zhang, X. Shi, J. Xie, H. Ma, I. King, and D. Yeung, “Gaan: Gated attention networks for learning on large and spatiotemporal graphs,” in _UAI_ , 2018, pp. 339–349.
  * [25] B. Yu, M. Li, J. Zhang, and Z. Zhu, “3d graph convolutional networks with temporal graphs: A spatial information free framework for traffic forecasting,” _arXiv:1903.00919_ , 2019.
  * [26] C. Zhang, J. J. Q. Yu, and Y. Liu, “Spatial-temporal graph attention networks: A deep learning approach for traffic forecasting,” _IEEE Access_ , vol. 7, pp. 166 246–166 256, 2019.
  * [27] J. Ye, J. Zhao, K. Ye, and C. Xu, “Multi-stgcnet: A graph convolution based spatial-temporal framework for subway passenger flow forecasting,” in _2020 International Joint Conference on Neural Networks (IJCNN)_ , 2020, pp. 1–8.
  * [28] A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. N. Gomez, L. Kaiser, and I. Polosukhin, “Attention is all you need,” _arXiv preprint arXiv:1706.03762_ , 2017.
  * [29] A. Grover and J. Leskovec, “node2vec: Scalable feature learning for networks,” in _Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2016_ , 2016, pp. 855–864.
  * [30] B. Perozzi, R. Al-Rfou, and S. Skiena, “Deepwalk: online learning of social representations,” in _The 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining 2014_ , 2014, pp. 701–710.
  * [31] J. Bruna, W. Zaremba, A. Szlam, and Y. LeCun, “Spectral networks and locally connected networks on graphs,” in _ICLR_ , 2014.
  * [32] M. Defferrard, X. Bresson, and P. Vandergheynst, “Convolutional neural networks on graphs with fast localized spectral filtering,” in _NIPS_ , 2016, pp. 3837–3845.
  * [33] T. N. Kipf and M. Welling, “Semi-supervised classification with graph convolutional networks,” in _ICLR_ , 2017.
  * [34] Q. Zhang, Q. Jin, J. Chang, S. Xiang, and C. Pan, “Kernel-weighted graph convolutional network: A deep learning approach for traffic forecasting,” in _ICPR_ , 2018, pp. 1018–1023.
  * [35] J. Li, H. Peng, L. Liu, G. Xiong, B. Du, H. Ma, L. Wang, and M. Z. A. Bhuiyan, “Graph cnns for urban traffic passenger flows prediction,” in _SmartWorld_ , 2018, pp. 29–36.
  * [36] H. Hu, G. Li, Z. Bao, Y. Cui, and J. Feng, “Crowdsourcing-based real-time urban traffic speed estimation: From trends to speeds,” in _32nd IEEE International Conference on Data Engineering, ICDE 2016_ , 2016, pp. 883–894.
  * [37] I. Sutskever, O. Vinyals, and Q. V. Le, “Sequence to sequence learning with neural networks,” in _NIPS_ , 2014, pp. 3104–3112.
  * [38] J. Chung, C. Gulcehre, K. Cho, and Y. Bengio, “Empirical evaluation of gated recurrent neural networks on sequence modeling,” in _NIPS Workshop_ , 2014\.
  * [39] T. Luong, H. Pham, and C. D. Manning, “Effective approaches to attention-based neural machine translation,” in _EMNLP_ , 2015, pp. 1412–1421.
  * [40] B. M. Williams and L. A. Hoel, “Modeling and forecasting vehicular traffic flow as a seasonal arima process: Theoretical basis and empirical results,” _Journal of Transportation Engineering_ , vol. 129, no. 6, pp. 664–672, 2003\.
  * [41] D. P. Kingma and J. Ba, “Adam: A method for stochastic optimization,” _arXiv preprint arXiv:1412.6980_ , 2014.
  * [42] G. Yu and C. Zhang, “Switching ARIMA model based forecasting for traffic flow,” in _ICASSP_ , 2004, pp. 429–432.
  * [43] S. R. Chandra and H. Al-Deek, “Predictions of freeway traffic speeds and volumes using vector autoregressive models,” _IEEE Transactions on Intelligent Transportation Systems_ , vol. 13, no. 2, pp. 53–72, 2009.
  * [44] Y. Xie, Y. Zhang, and Z. Ye, “Short-term traffic volume forecasting using kalman filter with discrete wavelet decomposition,” _Comput. Aided Civ. Infrastructure Eng._ , vol. 22, no. 5, pp. 326–334, 2007.
  * [45] H. Fu, H. Ma, Y. Liu, and D. Lu, “A vehicle classification system based on hierarchical multi-svms in crowded traffic scenes,” _Neurocomputing_ , vol. 211, pp. 182–190, 2016.
  * [46] M. May, D. Hecker, C. Körner, S. Scheider, and D. Schulz, “A vector-geometry based spatial knn-algorithm for traffic frequency predictions,” in _ICDM Workshops_ , 2008, pp. 442–447.
  * [47] J. Zhang, Y. Zheng, and D. Qi, “Deep spatio-temporal residual networks for citywide crowd flows prediction,” in _Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence,AAAI_ , 2017, pp. 1655–1661.
  * [48] R. Yu, Y. Li, C. Shahabi, U. Demiryurek, and Y. Liu, “Deep learning: A generic approach for extreme condition traffic forecasting,” in _Proceedings of the 2017 SIAM International Conference on Data Mining_ , 2017, pp. 777–785.
  * [49] Z. Cui, K. Henrickson, R. Ke, and Y. Wang, “Traffic graph convolutional recurrent neural network: A deep learning framework for network-scale traffic learning and forecasting,” _IEEE Transactions on Intelligent Transportation Systems_ , 2019.
  * [50] W. Chen, L. Chen, Y. Xie, W. Cao, Y. Gao, and X. Feng, “Multi-range attentive bicomponent graph convolutional network for traffic forecasting,” _AAAI_ , 2020.
  * [51] D. Bahdanau, K. Cho, and Y. Bengio, “Neural machine translation by jointly learning to align and translate,” in _ICLR_ , 2015.
  * [52] T. Shen, T. Zhou, G. Long, J. Jiang, S. Pan, and C. Zhang, “Disan: Directional self-attention network for rnn/cnn-free language understanding,” in _Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence,AAAI_ , 2018, pp. 5446–5455.
  * [53] V. Mnih, N. Heess, A. Graves, and K. Kavukcuoglu, “Recurrent models of visual attention,” in _Annual Conference on Neural Information Processing Systems, NIPS_ , 2014, pp. 2204–2212.
  * [54] J. Feng, M. Huang, Y. Yang, and X. Zhu, “GAKE: graph aware knowledge embedding,” in _26th International Conference on Computational Linguistics, COLING_ , 2016, pp. 641–651.
  * [55] L. Bai, L. Yao, S. S. Kanhere, X. Wang, and Q. Z. Sheng, “Stg2seq: Spatial-temporal graph to sequence model for multi-step passenger demand forecasting,” in _IJCAI_ , 2019, pp. 1981–1987.

|  Jiexia Ye received the Bachelor’s degree in Economics from Sun Yat-sen
University in 2012 and M.S. degree in Engineering in Shenzhen Institutes of
Advanced Technology, Chinese Academy of Sciences in 2021. Her research
interests include graph neural networks / graph embedding in traffic and
finance domain.
---|---
|  FuRong Zheng received his Bachelor’s degree in Automation from Wuyi
University in 2018. He is currently working toward M.S. degree in Computer
Science in Shenzhen Institutes of Advanced Technology, Chinese Academy of
Sciences. His principal research interest covers the data science and machine
learning, in particular, the following areas: traffic analysis; crowd flow
prediction and sequential pattern mining.
---|---
|  Juanjuan Zhao received her Ph.D degree from Shenzhen College of Advanced
Technology, University of Chinese Academy of Sciences in 2017, and received
the M.S. degree from the Department of Computer Science, Wuhan University of
Technology in 2009. She is an Assistant Professor at Shenzhen Institutes of
Advanced Technology, Chinese Academy of Sciences. Her research topics include
data-driven urban systems, mobile data collection, cross-domain data fusion,
heterogeneous model integration.
---|---
|  Kejiang Ye received his BSc and Ph.D degree in Computer Science from
Zhejiang University in 2008 and 2013 respectively. He was also a joint Ph.D
student at The University of Sydney from 2012 to 2013. After graduation, he
worked as Post-Doc Researcher at Carnegie Mellon University from 2014 to 2015
and Wayne State University from 2015 to 2016. He is currently a Professor at
Shenzhen Institutes of Advanced Technology, Chinese Academy of Science. His
research interests include cloud computing, big data and network systems.
---|---
|  Chengzhong Xu received his Ph.D degree from the University of Hong Kong,
China in 1993. He is the Dean of the Faculty of State Key Lab of IOTSC,
Department of Computer Science, University of Macau, Macao SAR, China and a
Chair Professor of Computer Science of UM. He was a Chief Scientist of
Shenzhen Institutes of Advanced Technology (SIAT) of Chinese Academy of
Sciences and the Director of Institute of Advanced Computing and Digital
Engineering of SIAT. He was also in the faculty of Wayne State University, USA
for 18 years. Dr. Xu’s research interest is mainly in the areas of parallel
and distributed systems, cloud and edge computing, and data-driven
intelligence. He has published over 300 peer-reviewed papers on these topics
with over 10K citations. Dr. Xu served in the editorial boards of leading
journals, including IEEE Transactions on Computers, IEEE Transactions on Cloud
Computing, IEEE Transactions on Parallel and Distributed Systems and Journal
of Parallel and Distributed Computing. He is the Associate Editor-in-Chief of
ZTE Communication. He is IEEE Fellow and the Chair of IEEE Technical Committee
of Distributed Processing.
---|---