时空序列

ST-GDN (AAAI 2021)

Traffic Flow Forecasting with Spatial-Temporal Graph Diffusion Network

pdf:http://urban-computing.com/pdf/AAAI2021TrafficFlow.pdf

前言前言前言

历史的车轮又往前挪了一年，这次要介绍的是2021年AAAI上发表的一篇交通流量预测的文章。怎么说呢，这篇论文的总体阅读体验并不好，整篇论文从图和公式上来看很杂乱，包括在总体结构图里加入了很多公式，这样使得图片看起来非常乱，反而不能起到一个帮助梳理脉络的作用。还有一个问题是不知道是不是我理解不到位，公式里的一些符号我觉得没有表达清楚，导致了一些公式在理解上不是特别容易。

Fine，总而言之我还是按着我的理解，系统的往下梳理一遍吧。交通流量预测的基本概念不再赘述，直接过渡到简介里提出的问题吧：

1、首先，文章认为，交通流量模式通常是复杂并有多时间跨度的，不同时间跨度的能反映不同的交通流量模式，现有的RNN类模型只能在短期、平滑的序列上获得较好的效果，但在高阶多维度的时间维度上效果不佳。

2、很多现有的预测方法只聚焦于临近的位置联系而忽略了全局信息下的相关性。举例来说，两个具有相似城市功能的地区（商场、运输站），他们虽然在地理位置上相差很远，但在交通流量的属性上具有一定的相似性，在表征上也有一定的相似性。

为了解决上面的两个问题，该模型设计了一个多跨度的自注意力网络以捕获不同时间跨度的交通流量模式，同时为了学习到局部和全局的空间依赖，设计了一个阶梯式的图神经网络。

本文的主要贡献为（无情的翻译机器！）：

1、强调了多跨度时间模式及全局、局部空间依赖对交通流流量预测的的重要性。

2、设计了交通流量预测框架ST-GDN，能有效地利用多跨度自注意力网络和层级时间聚合层提取不同跨度的时间信号。

3、通过层级图神经网络提取局部和全局空间依赖，层级图神经网络包括（图注意力网络和基于卷积机制的图扩散机制）

4、在四个真实世界数据集上效果优秀。

文章在写作上没有单独辟出一块来介绍相关工作，所有的相关工作都只是穿插在问题介绍里，不知道是不是篇幅受限的问题，这样的写法我感觉在方法的递进改进角度上来看不是很好。

那在介绍模型之前，还是先看一下问题定义叭：

空间区域

论文将城市划分为$I\times J$个不相交的区域，每个区域以$r_{i,j}$表示。这也是正片论文预测的基本单元。

交通流向量

基于上面的区域划分，交通流向量可以用$X\in\mathbb{R}^{I\times J\times T}$表示，其中$x_{i,j}^{t}$表示区域$r_{i,j}$在第t个时间步的流量数据。同时，模型为了同时在输入输出上进行预测，分别定义了$X^{\alpha}$和$X^{\beta}$来表示输入和输出。（每个区域有流量流入和流量输出）。

于是，模型的任务可以被定义为找到一个映射函数，能将输入$X^{\alpha}$和$X^{\beta}$映射到未来的交通流量。

时间跨度（Temporal Resolution）

模型中定义了$p$以指示两次采样区块之间的间隔，用来指示上文中所说的不同时间跨度。具体来说，两次的时间可以被定义为$x^t_{i,j}$以及$x^{t^{'}}_{i,j}$,那么$p=t^{'}-t$可以是一个小时，一天或是一周。

模型模型模型

老规矩，先拍一张结构图叭：

st-gdn

试着分解一下，我们可以按着竖着的虚线把这模型分成四个，一个一个来看叭：

Temporal Hierarchy Modeling

根据上面的定义3，给定一个时间跨度$p$，我们可以产生一个对应于该时间跨度的序列$X_{i,j}^{T_p}$。这部分模型的目的是为了提取时间序列信息，把时空序列图压缩到一张图上，具体的方法就是使用自注意力机制。自注意力机制是个老朋友了，不再具体介绍，大致就是对本身做三次不同的线性变化，然后弄个$Q$,$K$,$V$，这里我只放几个原文中的公式：
$\left [ \begin{matrix} Q\\ K\\ V\\ \end{matrix}\right] = E^p\left [ \begin{matrix} W_Q\\ W_K\\ W_V\\ \end{matrix}\right];Y^{p}=\sigma(\frac{QK^T}{\sqrt{d}})V$其中$y_{i,j}^{p}\in{\mathbb{R}^d}$表示学习到的与时间跨度相关的在区域$r_{i,j}$上的潜在向量表征，$\sigma(\cdot)$为softmax。

Traffic Dependency Learning with Global Context

第二部分的目的是提取全局范围的空间相关性。在这部分模型中，论文首先定义了一个区域图$G=(R,E)$,其中，$R$表示区域集合，$E$表示不同区域之间的联系。具体的算法非常类似于GAT，按着论文里的公式来吧：
$m^{p}_{(i,j)\leftarrow(i^{'},j^{'})} = \underset{h=1}{\overset{H}{\Vert}}{\omega^{h}_{(i,j);(i^{'},j^{'})}}\cdot Y^p\cdot W^p$这里面的$m^{p}_{(i,j)\leftarrow(i^{'},j^{'})}$表示特征信息从区域$r_{i^{'},j^{'}}$聚合到$r_{i,j}$,$H$表示使用了多头注意力机制，$W^p$是一个可学习的参数，$\omega^{h}_{(i,j);(i^{'},j^{'})}$是一个潜在相关性得分。可以表示为：
$\omega^{h}_{(i,j);(i^{'},j^{'})}=\frac{exp(LeakyReLU(\alpha^T[\hat{y}^{p}_{i,j}||\hat{y}^{p}_{i^{'},j^{'}}]))}{\sum_{(i^{'},j^{'}\in\mathcal{N}(i,j))}exp(LeakyReLU(\alpha^T[\hat{y}^{p}_{i,j}||\hat{y}^{p}_{i^{'},j^{'}}]))}$公式里对$\hat{y}^{p}_{i,j}$和$\hat{y}^{p}_{i^{'},j^{'}}$是拼接起来的，得到的潜在相关性得分实际上就是一个注意力得分，这边的操作实际上就是目标节点邻居节点的加权求和。这部分获得的表征可以表示为：
$z^p_{i,j}=f(\sum_{r_{i^{'},j^{'}}\in\mathcal{N}_{i,j}}m^{p}_{(i,j)\leftarrow(i^{'},j^{'})})$当然这只是一阶的特征聚合，要想获得高阶的特征聚合，需要叠加这个图注意力层。
$z_{i,j}^{p,(l+1)}\leftarrow\underset{i\in{\mathcal{N}_u(j);j^{'}\in\mathcal{N}_v(j)}}{Aggregate}(Propagate(z_{i,j}^{p,(l)},G))$最后，全局的空间依赖性通过这N阶的输出相加而得，即$z^p_{i,j}=z_{i,j}^{p,(l)}\oplus...\oplus z_{i,j}^{p,(L)}$

Region-wise Relation Learning with GraphDiffusion Paradigm

除了全局空间相关性之外，模型同样加入了局部区域间的相关性信息。为了实现这个目的，这部分模型设计了一个图扩散网络从上面介绍的图注意力网络中学习局部相关性。为了更方便介绍，我们首先要定义一个区域相关性图$G_s=(R_s,E_s,A)$。其中$A$是由顶点距离函数赋权的邻接矩阵。$D_o=A\cdot I$原文中说这个$D_o$定义为出度矩阵，但我觉得邻接矩阵和单位矩阵没法得出出入度矩阵，除非整一个全是1的矩阵，这里存疑， 我们后面暂时就按出入度看。之后这个图扩散网络可以被定义为：
$f(z_{i,j}^{p})_{\Theta}=\sum_{k=0}^{K-1}{(\theta_{k,1}(D_o^{-1}A)^k+\theta_{k,2}(D_i^{-1}A)^k)z_{i,j}^p}$其中，$\theta_{k,1},\theta_{k,2}\in\mathbb{R}^{K\times 2}$,这里我们可以把它们理解为调节输入、输出的系数，后面的$D_o^{-1}A$和$D_i^{-1}A$表示出入度，这其中，$D_o$和$D_i$可以类似表示为：
$\begin{pmatrix} \frac{1}{a} & 0 & \cdots & 0 \\ 0 & \frac{1}{b}&\cdots& 0 \\ \vdots& \vdots &\ddots&\vdots\\ 0 & 0 & \vdots &\frac{1}{z} \end{pmatrix}$那么$D_o^{-1}A$可以认为是用出入度对邻接矩阵做个初始化,这里的$A$在我的理解里不只是只有0/1的邻接矩阵了，而是上面提到的带权重的邻接矩阵。0/1邻接矩阵的k次方可以理解为k跳后两个节点之间的路径数量，带权重邻接矩阵可以认为是k跳后两节点间路径中节点权重的和，整体$(D_o^{-1}A)^k$可以被理解为k跳之后的出入度处理。

之后，这一层的输出要过一个激活函数，得：
$\varLambda^p_q=LeakyReLU(\sum_{d^{'}=1}^df(Z_{d^{'}}^p)_{\Theta_{q,d^{'}}})$一开始我没看懂这里得sum是干嘛用的，后来发现在上面d的扩散里涉及到每一个区域，所以我合理推测这里的操作时为了在每一维上把所有区域的表征相加。

在之后就是把hourly、daily、weekly的表征合起来，生成最后的表征:
$\varLambda_{i,j}=W^h\circ\varLambda^h_{i,j}+W^d\circ\varLambda^d_{i,j}+W^w\circ\varLambda^w_{i,j}$

Traffic Prediction Phase

图中还有最后一个虚线部分，这是最后的预测层，可以看到，除了时空信息之外，该模型还引入了别的额外特征，处理后通过拼接加入预测层。同时，该模型的损失函数可以表示为：
$\mathcal{L}=\sum_{i=0}^{I-1}\sum_{j=0}^{J-1}{\lambda[(\bar{x}^{\alpha}_{i,j,t})-x^{\alpha}_{i,j,t}]^2+(1-\lambda)[bar{x}^{\beta}_{i,j,t})-x^{\beta}_{i,j,t}]^2}$其中，$\bar{x}^{\alpha}_{i,j,t}$和$\bar{x}^{\beta}_{i,j,t}$分别表示预测出来的输入输出。

总结总结总结

以下文字仅代表个人观点。首先，从文章结构来看，我觉得最大的不同在于该模型先处理了时间信息，再处理了空间信息，不同于之前模块化时空图模型先GNN后GRU的常用结构。但问题在于我不是很确定第二层GAT和第三层扩散图神经网络的差异在结构上的差异是不是能表示出全局和局部，当然后面的消融实验证明了这两个结构都是起到作用的。暂时先想到这些，Over。