文章信息

《Spatial-Temporal Fusion Graph Neural Networks for Traffic Flow Forecasting》，收录于国际人工智能会议（AAAI-2021），作者是北京大学的Mengzhang Li和Zhanxing Zhu。

论文下载地址：https://arxiv.org/abs/2012.09641

GitHub代码地址：https://github.com/MengzhangLI/STFGNN

摘要

由于不同道路节点之间存在复杂的空间依赖和动态的时间趋势，因此交通流时空数据预测是一项很具有挑战性的任务。目前的大部分框架通常利用给定的空间邻接图和其它复杂的机制来建模时空关系。然而具有不完整相邻连接的给定空间图结构的有限表示可能会限制那些模型的有效时空依赖性学习。此外，现有的方法在解决复杂的时空数据时通常使用单独的模块来处理时空相关性。因此论文作者提出了一种新的时空融合图神经网络（STFGNN）。

1. 首先使用数据驱动的方法生成时间图，用来补充空间图无法充分说明的信息。
2. 其次，SFTGNN通过一种全新融合操作将多种空间图和时间图进行集成，这可以有效地学习隐藏的时空依赖关系。
3. 最后，通过将该融合图模块和一个新的门控卷积模块集成到一个统一的层中，通过层的堆叠可以在长序列中学习时空相关性。

理论概述

由于图神经网络的快速发展，主流的思路都是将图结构用于时空预测。但是目前这些模型或多或少都还有一些缺陷：

1、缺乏包含充分信息的图结构。目前已有的工作没有考虑不同节点在时间上的相似性，比如图1中的红色点商业区在同一时间内可能会有相同的交通趋势，因此可以将其连接构成新的图结构。

2、现有的工作不能够难以捕获局部和全局的空间依赖。基于RNN/LSTM的模型非常耗时，并且可能出现梯度消失或爆炸的问题。transformer之类的方法也非常耗时。基于CNN的方法则需要通过堆叠层来捕获长期序列的全局相关性。

为了同时捕获局部和全局的复杂的时空相关性，作者提出了一个新的基于CNN的框架---时空融合图神经网络（STFGNN）。同时作者受到动态时间规整算法（DTW 算法）的启发，提出了一个新的基于时间序列相似度的时间图。然后将一些空间图和时间图集成为时空融合图来获取隐藏的时空信息。另外作者还提出了一个门控扩张卷积模块，通过更大的扩张率来捕获长时间的关联性。

创新点

1. 通过DTW算法构建了新的图结构，即时间图。时间图通过计算时间序列相似度得到，然后将空间图和时间图一起融合成一个时空融合图，得到隐藏的时空关联性。
2. 设计了一个门控扩张CNN模块，与时空融合模块结合后，通过堆叠层可以捕获长期序列的时空关联性。

问题定义

路网结构用图表示为，其中为节点集合，E为边集，为表示距离的空间邻接矩阵。在t时刻对图G的观测值为。整个预测问题可以表示为。

模型介绍

如图2(c)所示为时空融合图神经网络的整体结构，它由三部分组成：1、输入层，包含一层全连接层和激活函数层；2、堆叠的时空融合图神经层，由并行的时空融合图神经模块以及门控CNN模块组成，其中多个时空融合图神经模块并行，而门控CNN模块由两个并行的1D CNN组成；3、输出层，包含两层全连接层和激活函数层。图2(a)是输入时空融合图的序列样例。

1、时空融合图的构造

生成时间图的目的是获得比空间图更加准确的依赖关系，将时间图和空间图融合成一个时空融合图后，可以让深度学习模型变得更加轻巧，因为此时该时空融合图中的信息包含了每个节点与(1)空间邻居的信息，(2)相似时间模式节点的信息，(3)前后时间片的信息。

作者生成时间图时所采用的方法是DTW算法，即动态时间规整(Dynamic Time Warping)。DTW算法最早是用于识别语音的相似性。传统方法计算两个序列的距离，是通过简单地计算两个序列各个对应点之间的距离和，而DTW允许序列的点与另一个序列的多个连续点对应，再计算对应点之间的距离之和。简单来说，DTW算法的计算步骤为：(1)计算两个序列各个点的距离矩阵，(2)在距离矩阵中寻找一条从左下角到右上角的元素和最小的路径。

由于DTW的复杂度为N2，因此当节点数N很大时，计算复杂度将会很大，因此作者使用了fast DTW对其进行限制和优化。fast DTW的主要思想就是设置一个搜索长度T对其进行限制，使得计算范围被限制在对角线周围。

图2(b)就是作者所构建的时空融合图，它是个KN*KN的矩阵，由三种不同类型的N*N矩阵构成。其中黄色的ASG矩阵是代表空间距离的邻接矩阵，绿色的ATG是通过DTW算法得到的时间图，蓝色的ATC是代表时间连通性的单位矩阵，图中红圈表示的即同一节点在t2到t3时间的连接。

2、时空融合图神经模块

为了使得计算更加简化和省时，作者使用矩阵乘法代替了谱方法，因此无需再计算拉普拉斯矩阵。在每个矩阵乘法中，对角线中间的ASG从空间邻居获取信息， 四个角落中的ATG可以增强来自具有相似时间模式的节点信息，水平和垂直方向上的ATC可以沿时间轴为每个节点提供自己的自连接信息。矩阵乘法块的公式可以表示为：

其中表示第l个隐藏层的状态，A*表示时空融合图，可以表示为：

通过多个矩阵乘法块的堆叠，可以聚合更复杂和非局部的空间依赖关系，并且每个乘法块还引入了残差连接，输出被输入到了最大池化层中。最大池化操作可以表示为：

最后，该结果将被裁剪，对应于中间时间步的将被保留下来：

3、门控CNN模块

虽然可以通过集成来提取全局时空依赖关系，但是时空相关性更多地是来自远处的节点，而且节点自身的长期时空依赖性也很重要，这对于许多基于CNN的工作来说是非常具有挑战性的，因为CNN的固有结构很难超越自回归模型。因此作者在CNN部分引入了扩张卷积，扩张率为K-1，它可以沿时间轴扩大感受野，从而增强模型性能。

总结

作者提出了一种新的时空交通预测框架STFGNN。该模型通过将时间图与给定的空间图进行进一步的融合，能够有效捕获隐藏的时空依赖关系。然后通过与STFGN模块和新的门控扩张CNN模块的集成，同时学习局部时空异质性和全局时空异质性。

这篇文章的时空融合图神经模块与之前讲过的时空同步图卷积STSGCN很像，时空融合图可以看作是在那篇文章的基础上进行的优化和修改。可以参考我之前对STSGCN的解读，STSGCN：用于交通数据预测的时空同步图卷积 。