本文详细介绍了论文STGCN:Spacial Temporal Graph Convolutional Network
引言
- 实时而精准的交通预测对于交通管控非常重要。
- 由于非线性性和复杂性，传统方法没法满足中长期的预测任务并且总是忽视时空依赖关系。
- STGCN(Spatio-Temporal Graph Convolutional Networks)被提出用来解决以上两个痛点。
- 摒弃过去的常规卷积和循环单元，在图上重新构建完整的卷积结构，起到减少参数，加速训练的效果。
- 实验表明STGCN可以通过建模多规模的交通网络捕获时空关系并持续在现实世界的交通数据集上表现出state-of-the-art级别的效果。
介绍
- 随着交通需求的日益增长，交通服务例如流量控制，路线规划等高度依赖于高质量的交通情况评估。故而，多规模的交通预测是交通管控和导引的基础，且作为智能交通系统(ITS)的核心功能。
- 速度、容量、密度被选为基础的交通流量监视的指标，用以预测未来情况，但是传统的方法例如线性回归只适用于短期预测但是却不适用于具备高度不确定性和复杂性的长期交通流预测。
- 中长周期的交通预测根据方法可以被分为两个范畴——动态建模和数据驱动。
- 动态建模用微分方程和物理学方法作为工具来规划交通问题通过计算仿真。但是达到一个稳定的状态需要复杂的系统编程以及大量的算力，并且建模过程中非实践性的假设以及简化会降低预测的准确性。因此随着数据的增加，方法逐渐转向数据驱动的方法。
- 数据驱动的方法包括经典统计学方法以及机器学习建模，在时序分析中，一体化自回归均值逼近(ARIMA)方法是基于经典统计学的主要方法，但是这种方法受限于固定的时序假设且不考虑时空关联性，故而在处理高度非线性的交通流时表达效果有限
- 而基于深度学习的方法虽然被广泛采用，但这些稠密网络同时提取时空特征较为困难
- 为了充分利用空间特征，一些研究者采用卷积神经网络(CNN)捕获相邻关系，同时在时间序列上使用循环神经网络(RNN)。一种用于短期时序预测的架构CLTFP被提出。但是问题在于需要迭代训练，每一步都会积累误差且基于RNN的网络训练困难
- 提出一个新颖的深度学习框架——STGCN。包含了时空卷积块和卷积序列学习层，用于建模时空关联。首次应用纯卷积结构从图结构的时间序列中同时提取时空关系。
初步准备
道路图上的交通预测
交通预测是经典的时序预测问题，通过已有交通指标（速度或流量）根据已知的M个观测预测未来H步：
$$\hat{V_{t+1}},…,\hat{V_{t+H}}=argmax_{V_{t+1}…,V_{t+H}}logP(V_{t+1},…,V_{t+H}|V_{t-M+1},…,V_t)$$
$V_t$是在时间戳t观察到的n个路段的信息（流量），每一维度都是一个单独的路段的信息
上述表明$V_t$是t时刻的图结构，$\mathcal{G}=(\mathcal{V_t},\epsilon,W)$，$\mathcal{V_t}$是顶点集，分别代表n个路段观测站的观测数据，$\epsilon$代表边集，表明这些观测站间的联系，W则代表边的权重矩阵
图上卷积
有两个基础的方法用于泛化CNN为结构化数据形式。一种是去扩展卷积的空间定义，一种是用图傅里叶变换去操作谱域。前者重新分配顶点到特定的可以被常规卷积操作的结构中，后者引入谱框架，在谱域上应用谱图卷积。
$$\Theta \ast _\mathcal{G}x=\Theta(L)x=\Theta(U\Lambda U^T)x=U\Theta(\Lambda)U^Tx$$
一些必要的前置文章如下:
图拉普拉斯矩阵的推导
模型提出
网络架构
STGCN由顺序时空卷积块(ST块)组成，并且每个卷积块内部结构是”三明治“式的，两侧由两个门卷积层组成，中间由一个时空图卷积层共同构成。
用图CNN提取空间特征
使用卷积神经网络提取特征的过程可以看成是根据已有数据训练卷积核（特征），在图神经网络中也是如此。训练目标是卷积核$\Theta$，为了优化计算速度并减少参数，使用切比雪夫多项式逼近卷积核，可以将卷积核视为和图拉普拉斯矩阵（L）相关的函数：
$$\Theta(\Lambda)=\sum_{k=0}^{K-1}\theta_k\Lambda^k$$
其中$\theta \in \mathbb{R}^K $是矩阵多项式的系数。传统意义上来说，切比雪夫多项式$T_k(x)$用于截断膨胀估计：
$$\Theta(\Lambda)\approx\sum_{k=0}^{K-1}\theta_kT_k(\hat\Lambda)$$，其中$\hat\Lambda$是一个调整值：$$\hat\Lambda=2\Lambda/\lambda_{max}-I_n(\lambda_{max}表示L最大的特征值)$$
故而图卷积可以重写为：
$$\Theta \ast_\mathcal{G} x=\Theta(L)x\approx\sum_{k=0}^{k-1}\theta_kT_k(\hat{L})x$$
这是由于
$$\Theta \ast_\mathcal{G} x=\Theta(L)x=\Theta(U\Lambda U^T)x=U\Theta(\Lambda)U^Tx\approx U\sum_{k=0}^{K-1}\theta_k\Lambda^kU^Tx=\sum_{k=0}^{K-1}\theta_kU\Lambda^kU^Tx=\sum_{k=0}^{K-1}\theta_k(U\Lambda U^T)^kx=\sum_{k=0}^{K-1}\theta_k(L)^kx\approx\sum_{k=0}^{k-1}\theta_kT_k(\hat{L})x$$
其中$T_k(\hat{L})\in\mathbb{R}^{n\times n}$是切比雪夫多项式在重新调整过的拉普拉斯矩阵（$\hat{L}=2L/\lambda_{max}-I_n$）上的k阶值.
多层的线性表达式可以通过逐层堆积图卷积层，且每一层的卷积都只定义一阶的，并且深度学习架构可以恢复空间信息而不被限制在明确的多项式参数上，这意味着可以假设$\lambda_{max}\approx 2$，这样原式就化简为:
$$\Theta \ast_\mathcal{G} x \approx \theta_0 x+\theta_1(\frac{2}{\lambda_{max}}L-I_n)x\approx\theta_ox -\theta_1(D^{-\frac{1}{2}}WD^{\frac{1}{2}})x$$
其中$\theta_0$和$\theta_1$是卷积核的参数，为了限制参数变更且稳定算数表现，这两个参数被替代为一个$\theta=\theta_0=-\theta_1$，W和D被重新规范化为$\hat{W}=W+I_n$和$\hat{D} _{ii}=\sum_j\hat{W} _{ij}$，故而图卷积可以被写为：
$$\Theta \ast _\mathcal{G}=\theta(I_n+D^{-\frac{1}{2}}WD^{\frac{1}{2}})x=\theta(\hat{D}^{\frac{1}{2}}\hat{W}\hat{D}^{\frac{1}{2}})x$$.
自然的，图卷积操作子$\ast\mathcal{G}$可以被泛化到张量上，例如对于一个具备$C_i$个通道的信号$X\in \mathbb{R}^{n\times C_i}$，图卷积为：
$$y_j=\sum_{i=1}^{C_i}\Theta_{i,j}(L)x_i\in\mathbb{R}^n,1<=j<=C_0$$
其中$C_i$和$C_0$分别表示输入和输出的特征图的大小
用于提取时间特征的门电路CNN
虽然基于RNN的模型在时间序列分析中已经广为运用，用于交通预测的循环神经网络仍受到耗时、复杂的门机制和对于动态变化响应过慢等缺点的影响。然而反着来说，CNN有着训练快速，结构简单以及和前置步骤无关的好处。STGCN在完整的时间序列上部署卷积结构用来捕获交通流的时间动态特点，这个特定的设计允许并行并且可控的训练过程。
卷积核$\Gamma\in \mathbb{R}^{K_t\times C_i\times 2C_0}$用于匹配输入数据$Y\in \mathbb{R}^{M\times C_i}$（有$C_i个信道的长为M的时间序列$）的特征，即每次只看输入序列的后$K_t$个数据，得到两个长度为$C_0$的特征序列P和Q，时间门卷积可以被定义为:
$$\Gamma \ast_\tau Y=P\odot\sigma(Q)\in \mathbb{R}^{(M-K_t+1)\times C_0}$$
时空图卷积块
为了融合来自时域和空域的特征，时空卷积块被构建用以处理图结构的时间序列，这个块可以被作为基本单位堆叠。
联合的式子可以表述为如下形式，其中ST卷积块的输入和输出形式均为3D张量，对于块$l$的输入$v^l\in \mathbb{R}^{M\times n\times C^l}$，输出$v^{l+1} \in \mathbb{R}^{(M-2(K_t-1))\times n \times C^{l+1}}$:
$$v^{l+1}=\Gamma_1^l \ast _\tau ReLU(\Theta^l\ast _\mathcal{G}(\Gamma_0^{l} \ast _\tau v^l))$$
损失函数可以像如下定义:
$$L(\hat{v};W_{\theta})=\sum_t||\hat{v}(v_{t-M+1},..,v_t,W_\theta)-v_{t+1}||^2$$
$W_\theta$时模型中所有的可训练模型，$v_{t+1}$是ground truth，且$\hat{v}(\cdot)$表示模型的预测值
原文
如果您喜欢此博客或发现它对您有用，则欢迎对此发表评论。 也欢迎您共享此博客，以便更多人可以参与。 如果博客中使用的图像侵犯了您的版权，请与作者联系以将其删除。 谢谢 ！