时空序列

STSGCN (AAAI 2020)

Traffic Flow Prediction via Spatial Temporal Graph Neural NetworkForecasting

pdf:https://ojs.aaai.org//index.php/AAAI/article/view/5438

前言前言前言

好滴时间又从2019来到了2020年，这回要将的是2020年北京交通大学在AAAI上发表的论文。主题依旧是交通流两预测，不过这回模型结构和之前的几篇都不一样，从构图的方式上就有了改变，还是很有意思的。

照例过一遍Introduction，顺便看看有没有还没开的新的时空图模型坑。不同于之前几篇论文，这篇文章以介绍时空网络开头。时空网络是时空数据挖掘中的一种重要数据结构，它能描述现实生活中很多种数据，例如交通网络，移动基站网络，城市水利系统等等。准确的时空数据预测能有效提升这些领域的服务质量。近些年图卷积神经网络发展迅猛，GCN及其变体开始被应用于时空数据预测任务中并取得了不错的成绩。但仍然没有很好的方法去同时建模时间、空间之间的相关性和异质性。所以该论文的目的就是找到这样一种模型以提升预测的准确性。（无情滴英文翻译机器）

spatial-temporal networkspatial-temporal network

上图给出的是时空网络的一个样例，以两个timestep为例。箭头表示源节点对目标节点产生影响。图中一共有三种颜色的箭头，分别表示为(以红色节点为中心节点为例）：1、（棕色）一个timestep内中心节点对邻居节点的影响；2、（蓝色）前一个timestep内中心节点对后一个timestep中对应节点的影响；3、（绿色）前一个timestep内中心节点对后一个timestep中对应节点的邻居节点的影响。抽象一定看，棕色表示空间相关性，蓝色表示时间相关性，绿色表示时间-空间相关性（需要注意的是，由于节点之间的空间距离及时间序列的范围限制，这种时间-空间相关性通常只位于局部）。现有的提取时空信息的方法有DCRNN、STGCN和ASTGCN（妙哇，新坑）。这些方法的大致框架都是采用两个模块分别捕捉时间、空间依赖性，一般是先获取空间表征喂给时间序列模型来获取时空信息。而本文则提出了一种方法同时捕获三种相关性。同时由于这种方法符合时空数据的生成模式，论文认为这将非常有利于时空数据预测。

同时，时空网络通常在时间和空间维度具有异质性，举例来说，住宅区和商业区的监测站记录在不同的时刻通常有不同的模式，而之前的研究对于不同的时间使用共享的模块(这里应该指RNN类模型共享一个Cell参数)，无法有效捕获时空网络中的异质性。

于是，论文提出了STSGCN，这种模型的主要不同在于：1、可以直接提取局部的时空关联，而不是用多个模块组合提取；2、构建了多模块层以捕获长范围的时空网络的异质性。

相关工作也就一块放在前言讲了，论文里主要讲了时空序列预测和图卷积网络两块。在时空序列预测中从ARIMA开始，提及了ConvLSTM、ST-ResNet、ST-3DNet、DCRNN、STGCN、ASTGCN、Graph WaveNet、STG2Seq（嗯，突然好多坑，我先挖为敬）。图卷积网络里主要讲了ChebNet、GCN、GraphSage、GAT，这些之前都有过整理，下回稍微理一理给放到博客上来。

问题定义!

定义1 空间图 !

空间图G=(V,E,A)\mathcal{G}=(V,E,A)表示空间维度上的一张图，∣V∣=N|V|=N表示节点集合，一共有NN个节点，EE表示边的集合，AA表示图G\mathcal{G}的邻接矩阵，在这个模型里，图是有向或无向的都可以

定义2 图信号矩阵 !

图信号矩阵XG(t)∈RN×CX_{\mathcal{G}}^{(t)}\in\mathbb{R}^{N\times{C}}，其中，CC表示属性特征的个数，tt表示timestep。

那么这个时空网络数据预测问题同样可以被抽象为学习一个映射函数ff，这个映射函数能将历史的时空序列(XG(t−T+1),XG(t−T+2),...,XGt)(X_{\mathcal{G}}^{(t-T+1)},X_{\mathcal{G}}^{(t-T+2)},...,X_{\mathcal{G}}^{t})转换成未来的时空序列(XG(t+1),XG(t+2),...,XG(t+T′))(X_{\mathcal{G}}^{(t+1)},X_{\mathcal{G}}^{(t+2)},...,X_{\mathcal{G}}^{(t+T^{'})})

OK,定义完了，康模型！

模型模型模型

还是先拍一张结构图：

stsgcn structstsgcn struct

这图不是那么那么地直观，我们边解释边看叭。首先，这个模型地介绍我们可以分为3块。
1）局部时空图（localized spatial-temporal graph)地构建方法；
2）使用空间 - 时间同步图卷积模块（Spatial-Temporal Synchronous Graph Convolutional Module）提取图中地时空关联；
3）部署多个模块以模拟空间网络序列中的异质性

一个一个来嗷，首先:
局部时空图构建

本文想要获得的模型是能直接获取节点对邻居节点的影响（这个邻居包括了相邻时间步上的邻居，可以对照开头的那张图看）的那种。要想达到这种效果，就必须要有一个数据结构能直观地表达出这个效果，最直接的方法就是将节点于所有邻居（包括相邻时间步上的）相连，如下图左。

localized spatial-temporal graphlocalized spatial-temporal graph

那要怎么做呢？定义里面提到过，我们用A∈RN×NA\in{\mathbb{R}^{N\times N}}表示空间图的邻接矩阵，用A′∈R3N×3NA^{'}\in{\mathbb{R}^{3N\times 3N}}表示三个连续时间步组成的图的邻接矩阵，也就是我们想要获得的局部时空图。对于空间图中的节点i，我们可以通过公式(t−1)N+i(t-1)N+i重新计算得到一个索引（0<t≤30<t \leq 3表示TimeStep)。之后呢，如果在局部时空图地定义中相连地两个节点，那么在A′A^{'}上的值为1。对应的公式可以表示为：
Ai,j′={1,if vi connects to vj0,otherwiseA_{i,j}^{'}= \left\{ \begin{aligned} 1,& \quad if \ v_i\ connects\ to\ v_j\\ 0,& \quad otherwise \end{aligned} \right.

在这样一张图里相当于有3N3N个节点，组成结构如上图右(里面的Ati→tjA^{t_i\to t_j}表示从时间步tit_i到时间步tjt_j的连接）。对角线表示的是3个时间点上空间图的邻接矩阵，边上的四个是跨时间步的连接。

Spatial-Temporal Embedding

介绍空间 - 时间同步图卷积模块之前，先简单介绍一下时空嵌入的构成。

上面介绍的构图方法相当于把不同时间步的节点不加区分的放到了同一个环境内，虽然把时间信息嵌入到了这个环境内，但不加区分又会对时空关联提取造成影响。所以论文引入了位置表征（position embedding）。对于时空网络序列XG∈RN×C×TX_{\mathcal{G}}\in\mathbb{R}^{N\times C\times T},作者设计了一个可学习的时间嵌入矩阵Temb∈RC×TT_{emb}\in\mathbb{R}^{C\times T}和一个可学习的空间嵌入矩阵Semb∈RN×CS_{emb}\in\mathbb{R}^{N\times C},待训练完成后，这两个嵌入向量将分别具有时间和空间信息。之后将这两个向量加到原始的时空图序列表征上以获得新的时空序列表征。公式如下：
XG+temb+Semb=XG+Temb+Semb∈RN×C×T X_{\mathcal{G}+t_{emb}+S_{emb}} = X_{\mathcal{G}}+T_{emb}+S_{emb}\in\mathbb{R}^{N\times C\times T}

空间 - 时间同步图卷积模块

模型中构建了Spatial-Temporal Synchronous Graph Convolutional Module（STSGCM）来捕获局部时空关联性。STSGCM中包括了一系列的GCN来聚合邻居节点的信息。在这个结构中，图卷积操作的输入是局部时空图的图信号矩阵及邻接矩阵。在该模型中，图卷积操作使用带激活函数的全连接层实现的。公式如下：
GCN(h(l−1))=h(l)=σ(A′h(l−1)W+b)∈R3N×C′ GCN(h^{(l-1)})=h^{(l)}=\sigma{(A^{'}h^{(l-1)}W+b)}\in{\mathbb{R}^{3N\times C^{'}}}

其中，A′∈R3N×3NA^{'}\in\mathbb{R}^{3N\times 3N}是邻接矩阵，h(l−1)∈R3N×Ch^{(l-1)}\in\mathbb{R}^{3N\times C}为第l层GCN的输入（第一层输入是三个空间图的图信号矩阵拼接而成），W∈RC×C′W\in\mathbb{R}^{C\times C^{'}}和b∈RC′b\in\mathbb{R}^{C^{'}}是两个可学习的参数，σ\sigma表示激活函数，像Relu和GLU这些。如果这里使用GLU，那么公式也可以写作：
h(′)=(A′h(l−1)W1+b1)⊗sigmoid(A′h(l−1)W2+b2) h^{(')}=(A^{'}h^{(l-1)}W_1+b_1)\otimes{sigmoid}(A^{'}h^{(l-1)}W_2+b_2)

这个激活函数引入了一个门结构，可以控制进入下一层的节点信息。

根据各个参数的维度实际计算一下，我们可以发现，上面的公式就是将与目标节点相连的邻居节点的特征聚合到目标节点上。这不是谱域的计算，不需要计算图的拉普拉斯矩阵，所以可以处理有向图。同时，模型向邻接矩阵中加入了self-loop，使得节点同时可以得到自身的特征。

之后，模型里堆叠了多个图卷积操作以扩大聚合的区域(更多跳)，这样能使得模型获得范围更大的时空相关性信息。

如下图(a),其中ACG为聚合层。同时，模型以JK-net为STSGCM的基础结构并设计了一个新的聚合层来过滤无效信息。如下图(b),(c)。

STSGCMSTSGCM

STSGCM中所有图卷积操作的输出都会被输入到聚合层中，聚合层会对这些输出进行一个精炼并形成最终输出。聚合层中主要包括两个操作：聚合和裁剪。

聚合操作：

在该模型中选用了max-pooling作为聚合操作。这里的max-pooling是element-wise的，即按每一位去找最大值，这就需要每个图卷积操作的输出维度相同。这个操作可以被表示为：
hAGG=max(h(1),h(2),...,h(L))∈R3N×Cout h^{AGG}=max(h^{(1)},h^{(2)},...,h^{(L)})\in\mathbb{R}^{3N\times C_{out}} CoutC_{out}就是每个图卷积操作后输出的维度数。

裁剪操作：

裁剪操作如上图的(C)，在裁剪操作中，我们将前一个时间步和后一个时间步的节点信息删去，仅保留当前时刻的节点信息，因为在图卷积操作之后，当前时刻的节点信息已经包含了前后两个时间步的节点信息，这时不删除会导致信息冗余，对模型性能产生影响

小总结发言：

捋一下流程啊，首先，STSGCM的输入是局部时空图的图信号矩阵h(0)∈R3N×Cinh^{(0)}\in\mathbb{R}^{3N\times C_{in}},,经过ii轮的图卷积操作，可以得到ii个中间输出h(i)∈R3N×Couth^{(i)}\in\mathbb{R}^{3N\times C_{out}}。之后聚合层先进性聚合，得到一个最大值hAGG∈R3N×Couth_{AGG}\in\mathbb{R}^{3N\times C_{out}}。最后过一个裁剪操作得到最终输出h(final)∈RN×Couth^{(final)}\in\mathbb{R}^{N\times C_{out}}。在回到最开始的时空网络示意图里，我们注意到，对于目标节点来说，最远的是一个二跳邻居，对应到STSGCM中，只需要堆叠两个图卷积操作就可以模拟上面的那个情况。

Spatial-Temporal Synchronous Graph Convolutional Layer

STSGCL是包含了很多STSGCM的一个层结构。

为了获取长范围内的时空关联性信息，模型通过滑动窗口来对原始输入序列进行了一个切分。具体来说，对于这个整个模型，输入的空间图序列为，X∈RT×N×CX\in\mathbb{R}^{T\times N \times C},为了让输入适应STSGCM，选用了长度为3的滑动窗口进行切分，获得了长度为3的局部时空图序列，一共有T-2个，每一个局部时空序列为X′∈R3×N×CX^{'}\in\mathbb{R}^{3\times N \times C}(我们可以的对他reshape一下，整成X′∈R3N×CX^{'}\in\mathbb{R}^{3N\times C},这个可以直接扔到STSGCM中作为输入了)。

之后为了解决Introduction中提到的之前方法RNN类模型共享cell参数无法处理不同场景的问题，STSGCL选用了T-2个不同的STSGCM结构对T-2个数据分别处理（不共享参数以实现区别化）。最后输出就是这T-2个STSGCM输出：M=[M1,M2,...,MT−2]∈R(T−2)×N×CoutM=[M_1,M_2,...,M_{T-2}]\in\mathbb{R}^{(T-2)\times{N}\times{C_{out}}}，这里的Mi∈RN×CoutM_i\in\mathbb{R}^{N\times{C_{out}}}就是第ii个STSGCM的输出。

额外组件

主要结构介绍完了，文中还有一部分可以增强表征效果的额外组件，我们也来一起康康：

Mask 矩阵：

从上面的图卷积操作中我们可以发现，邻居节点的聚合由邻接矩阵进行实现，如果邻接矩阵中只有0或1，那么聚合能力实际是有限的(同样由有连接的两对点，其相似性也有不同，应该聚合的信息也应该有所权衡）。为了解决这个问题，模型增加了一个可学习的Mask矩阵Wmask∈R3N×3NW_{mask}\in\mathbb{R}^{3N\times 3N}来调整聚合的权重。增加了这个矩阵之后，邻接矩阵变为：
Aadjusted′=Wmask⊗A′∈R3N×3 A_{adjusted}^{'}=W_{mask}\otimes{A^{'}}\in\mathbb{R}^{3N\times 3}

输入层：

输入层设置了一个转化层来将输入映射到一个高维空间中，来增强表征效果

输出层：

输出层是为了将STSGCL的输出转换成预测。输出层的输入可以被视作X∈RT×N×CX\in\mathbb{R}^{T\times N\times C}(理论上是T-2,不过这边就大致一估)。我们要对这玩意做个转置和reshape，变成XT∈RN×TCX^T\in\mathbb{R}^{N\times TC},之后就把这个变化后的中间变量过两个全连接层形成输出：
y^(i)=ReLU(XTW1(i)+b1(i))W2(i)+b2(i) \hat{y}^{(i)}=ReLU(X^{T}W_1^{(i)}+b_1^{(i)})W_2^{(i)}+b_2^{(i)} 其中，y^(i)\hat{y}^{(i)}表示在时刻i的预测输出，后面的WW和bb是不同的可学习参数，只有由2×T′2\times T^{'}组参数，我们就可以获得最后的输出：
Y^=[y^(1),y^(2),...,y^(T′)]∈RN×T′ \hat{Y} = [\hat{y}^{(1)},\hat{y}^{(2)},...,\hat{y}^{(T^{'})}]\in\mathbb{R}^{N\times T^{'}}

损失函数：

模型选用了Huber loss作为损失函数，Huber loss相对于squared error loss对异常点不敏感一些，公式如下：
L(Y,Y^)={12(Y−Y^)2,∣Y−Y^∣≤δδ∣Y−Y^∣−12δ2,otherwise L(Y,\hat{Y})=\left\{ \begin{aligned} &\frac{1}{2}(Y-\hat{Y})^{2}, \quad &|Y-\hat{Y}|\leq\delta\\ &\delta|Y-\hat{Y}|-\frac{1}{2}\delta^2, \quad &otherwise \end{aligned} \right. 其中δ\delta是一个阈值参数，YY和Y^\hat{Y}分别是真实值和预测值。

总给总结总结

呼，介绍完啦。这篇论文的结构和之前几篇大相径庭，结构上也更加复杂，所以介绍的篇幅一不小心就放的很长。总的来说，这种扩充邻接矩阵的想法还是很有意思的，但是实际上我认为这种前后各一时间步只获取了前后两个时间的信息（这个角度感觉可以做点手脚改进改进），获取的时间相关性只是短期的，后续的两个全连接层换成一个transformer层来捕获长期特征可能会更好一些（老缝合怪了）。其次，模型中为了体现出不同情况不同处理，用了T-2个STSGCM，这虽然有点道理，但总觉的不是很优雅，包括后面在预测的时候，也使用了大量的参数，总觉得有点怪怪的，感觉也可以想办法换一换结构。