Spatio-Temporal Graph Convolutional Networks: A Deep Learning Framework for Traffic Forecasting

问题背景：交通流量预测忽略时空依赖性。

提出模型：Spatio-Temporal Graph Convolutional Networks (STGCN)。instead of 常规卷积和递归单元，本文在图上公式化问题，并使用完整的卷积结构构建模型，使得以更少的参数实现更快的训练速度。

流量预测分为：短期（5-30min)，中长期（>30min）。

RNN迭代训练会累积误差，并且难训练，计算量大。为了解决RNN内在这个问题，本文提出了在时间轴上用全卷积结构。

Preliminary

1.在t时刻，图 $G_t=(V_t,E,W)$ 。

2.CNN通常处理regular grids和图像。将CNN泛化到数据形式的方法：1.扩展卷积的空间定义：将顶点重新排列为某些网格形式，可以通过常规卷积运算对其进行处理。2.使用图傅立叶变换在光谱域中进行操作，通常称为光谱域卷积。

本文基于谱域卷积，引入 $\star_G$ 表示信号 $x∈R^n$ 和核 $\Theta$ 的乘积。

$\Theta \star_G x=\Theta(L)x=\Theta(U\Lambda U^T)x=U\Theta(\Lambda )U^Tx$

图傅里叶基 $U∈R^{n*n}$ 是归一化拉普拉斯矩阵 $L=I_ n-D^{-1/2}WD^{-1/2}=U\Lambda U^T∈R^{n*n}$ 的特征向量（ $D∈R^{n*n}$ 是对角矩阵， $D_{ii} = \sum\nolimits_{j} W_{ij}$ ）， $\Lambda ∈R^{n*n}$ 是L特征值的对角矩阵，滤波器 $\Theta (\Lambda )$ 也是对角矩阵。所以，图信号x在一个 $\Theta$ 和图傅里叶变换 $U^Tx$ 相乘的内核 $\Theta$ 过滤。

模型

STGCN由2个时空卷积块组成，每一块都有2门时序卷积层+1空间图卷积组成的三明治结构。

图CNN提取空间特征

用图傅里叶基计算较复杂，本文采用两种近似算法。

Chebyshev多项式近似：为了局部化滤波器且减少参数， $\Theta (\Lambda )为\Lambda$ 的多项式： $\Theta (\Lambda )=\sum_{k=0}^{K-1}\theta_k\Lambda^k$ , $\theta∈R^K$ 为多项式系数，K为图卷积的核大小，确定了从中心节点开始的卷积的最大半径。

$\Theta \star_Gx=\Theta(L)x\approx \sum_{k=0}^{K-1}\theta_kT_k(\tilde{L})x$

一阶近似：

$\Theta \star_G x\approx \theta_0 x +\theta_1(2/\lambda_{max}-I_n)x\approx \theta_0 x+\theta_1 (D^{-1/2}WD^{-1/2})x$

$\Theta \star_G x=\theta (I_n+(D^{-1/2}WD^{-1/2})x =\theta(\tilde{D}^{-1/2} W \tilde{D}^{-1/2})x$

门CNN提取时间特征

RNN循环训练耗时，CNN训练快速，结构简单。本文在时间轴上采用卷积捕捉时间特征。这种特定的设计允许通过形成为分层表示形式的多层卷积结构进行并行和可控的训练过程。

时序卷积层包含一个内核宽度为 $K_t$ 的1D因果卷积causal conv，后面接一个门控线性单元(gated linear unit,GLU)组成非线性。

$\Gamma *_T Y=P\odot \sigma(Q)∈R^{(M-K_t+1)\times C_o}$ ,

P,Q是GLU的输入， $\odot$ 是逐元素的Hadamard 积。

时空卷积块

为了融合时域和空间的特征，构造了时空卷积块（ST-Conv块）以共同处理图结构的时间序列。块可以根据情况的规模和复杂性进行堆叠或扩展。

如上图，中间的spatial层是连接两个temporal层，这两个时间层可以实现从图卷积到时间卷积的快速空间状态传播。 “三明治”结构还有助于网络充分应用瓶颈策略，以通过图卷积层对通道C进行按比例缩小/放大来实现比例压缩和特征压缩。此外，在每个ST-Conv块内利用层归一化来防止过度拟合。

ST-Conv块的输入和输出都是3D Tensor，输入 $v^l∈R^{M\times n \times C^l}$ ,输出 $v^{l+1}∈R^{(M-2K_t-1) \times n \times C^{l+1}}$ .

$v^{l+1}=\Gamma _1^l*_T ReLU(\Theta ^l *_G(\Gamma ^l_0*_Tv^l))$

$\Gamma _0^l,\Gamma _1^l$ 是块 $l$ 内的上下的时序核。 $\Theta ^l$ 是图卷积的谱核。

两个ST-Conv块后接一个全连接的时序卷积层，得到最终的输出 $Z∈R^{n \times c}$ ,在c个通道上用线性计算n个节点速度预测 $\hat{v}= Zw+b, w∈R^c$ 。

实验

1.数据集

BJER4：12条road。交通数据每5分钟汇总一次。 2014.7.1-8.31。第一个月为训练集，其余分别用作验证和测试集。

PeMSD7：中型数据源PeMSD7(M)228个站和大型数据源PeMSD7(L)1026个站。数据集从30秒的样本汇总到5分钟。2012年5、6月的工作日。

2.数据预处理

两个数据集time interval 设为5min。因此，每个节点288个points/day。线性插值法填充缺失值。另外，数据输入通过Z-Score方法标准化。

BJER4是四环，转换为有向图。

PeMSD7，根据站点间的距离计算图的邻接矩阵。加权邻接矩阵W： $\begin{equation} w_{ij} = \begin{cases} exp(\frac{d^2_{ij}}{\sigma^2})\geq \epsilon, & i\neq j ,\\ 0, &otherwise. \end{cases}\end{equation}$