1、文章信息
《Spatial-Temporal Fusion Graph Neural Networks for Traffic Flow Forecasting》。这是北大发表在计算机顶级会议AAAI2021上的一篇文章。
2、摘要
交通流的时空数据预测是一项具有挑战性的任务，因为复杂的空间依赖性和不同道路之间的时空模式的动态趋势。现有框架通常利用给定的空间邻接图和复杂的机制来对空间和时间相关性进行建模。但是，具有不完整相邻连接的给定空间图结构的有限表示可能会限制那些模型的有效时空依赖性学习。此外，在处理复杂的时空数据时，现有方法难以解决以下几个问题：它们通常使用单独的模块进行时空相关性，或者它们仅使用捕获局部或全局异构依赖项的独立组件。为了克服这些局限性，论文中提出了一种新颖的时空融合图神经网络（STFGNN）进行交通流量预测。首先，提出了一种生成“时间图”的数据驱动方法，以补偿空间图可能无法反映的几种现有相关性。SFTGNN可以通过对各种时空图进行并行处理的新颖融合操作，有效地学习隐藏的时空依赖性。同时，通过将该融合图模块和新颖的门控卷积模块集成到一个统一的网络层中，SFTGNN可以通过学习更多的时空相关性来处理长序列，并将这些层堆叠在一起。在几个公开交通数据集上的实验结果表明，与其他基准相比，新的方法能够实现最佳的性能。
3、动机
近年随着图神经网络的发展，时空数据的图建模成为大家关注的焦点。尽管在将图结构纳入时空数据预测模型方面已取得了显着改进，但这些模型仍然面临以下一些缺陷：
第一个限制是缺乏信息图的构造。例如，城市中一些遥远的节点可能具有某些相关性，即它们将共享相似的“时间模式”。例如，在高峰时段，办公楼附近（从商业区出发）的大多数道路在同一时期都会遇到交通拥堵。但是大多数现有模型仅将给定的空间邻接矩阵用于图建模，而在对邻接矩阵建模时忽略节点之间的时间相似性。此外，当前的时空预测研究不足以捕捉局部和全局相关性之间的依存关系。基于RNN / LSTM的模型非常耗时，并且在捕获远程序列时可能会遇到梯度消失或爆炸的情况。Transformer的学习过程可能仍然很耗时。基于CNN的方法则需要堆叠层以捕获长序列的全局相关性。
为了捕获局部和全局复杂的空间时间相关性，论文中提出了一种基于CNN的新颖框架，称为时空融合图神经网络（STFGNN）。受动态时间弯曲算法的启发，作者提出了一种新颖的数据驱动的图构建方法：基于时间序列之间的相似性学习的时间图。然后，可以将几个图集成为时空融合图，以获得隐藏的时空依赖性。此外，为了打破局部和全局相关权衡，引入了门控扩张卷积模块，其较大的扩张率可以捕获远距离依赖性。
4、模型
论文中图3介绍了时空融合图神经网络的框架。它由（1）输入层，（2）堆叠的时空融合图神经层和（3）输出层组成。输入和输出层是一层和两层全连接层，其后分别是激活函数层。每个时空融合图层由几个并行的时空融合图神经模块（STFGN模块）和一个门控CNN模块构成，后者包括两个并行的一维扩张卷积模块。
文章图片
(1)时空融合图的构建
生成时间图的目的是获得比空间图更准确的依赖关系和真实关系的特定图结构。然后，将时间图合并到新颖的时空融合图中，这可以使深度学习模型更轻巧，因为该融合图已经具有每个节点与其（1）空间邻居，（2）具有类似时间模式的节点的相关信息，以及（3）沿时间轴的前一个或后一个的状态。
但是，利用DTW根据时间序列的相似性生成时间图并不容易，它是一种典型的具有复杂性的动态规划算法。因此，对于许多应用来说这可能是难以接受的，因为现实世界的时间序列通常很长。为了降低DTW的复杂度，论文中限制了它的“搜索长度”T为12个时间步。关于DTW的算法原理这里不再赘述，有兴趣可以自行查找文献了解细节，关于时间图和空间距离图的构建在以往的交通预测的文献里均有体现，这里可以参考文献。
论文中图3（b）是时空融合图的示例。它由三种N×N矩阵组成：由数据集提供的空间距离图ASG，由DTW算法生成的时间图ATG和元素为非零的时间连接图ATC（如果上一个和下一个时间步是同一节点）。给定时空融合图ASTFG∈R 3N×3N，并在图3（b）的红色圆圈内取ATG。它表示同一节点之间在相邻时间步长：2到3之间的连接。
(2)时空融合图神经网络模块
这篇论文中的基础GCN单元使用了基于矩阵相乘的空间方法代替了谱方法，从而无需计算邻接矩阵的拉普拉斯矩阵。LSTM / RNN中的门控机制也用于图乘法块中。在STFGN模块中，门控线性单元通过其非线性激活用于图形乘法。图乘法模块的公式如下：
文章图片
其中hl表示某些STFGN模块的第l个隐藏状态。A ?是时空融合图的简写。
文章图片
都是GLU模型的一些可训练参数。
通过堆叠L个图乘法块，可以聚合更复杂的非局部空间相关性。直观地，还将为每个块引入残差连接。MaxPooling操作将在每个隐藏状态h的串联上进行操作：
文章图片
。最后，对应于中间时间步骤的此串联将被裁剪保存：
文章图片
图3（b）显示此裁剪的特征包含复杂的异质性。在每个矩阵乘法中，对角线中间的ASG（对应于串联的裁剪位置）从空间邻居传输信息。ATC在水平和垂直方向上沿时间轴为每个节点提供自己的自连接信息。角落中的ATG可增强来自具有相似时间模式的节点的信息。
(3)门控卷积模块
尽管ASTFG可以通过ATG的集成来提取全局时空相关性，但是它包含的相关性更多来自遥远的节点。节点本身的长期时空依赖性也很重要，这对许多基于CNN的工作都是非常具有挑战性的，因为CNN的固有结构几乎无法胜过类似Transformer的自回归模型。与以前的GraphWaveNet和STGCN等不同，扩张率较大的卷积操作在本文中介绍。门控卷积的公式如下所示：
文章图片
其中φ（·）和σ（·）分别是tanh和sigmoid函数。Θ1和Θ2是两个独立的1D卷积运算，扩张率为 K -1。它可以扩大沿时间轴的感受野，从而增强模型性能，以提取顺序依存关系。
本文中Huber损失作为整个模型训练的损失函数。
5、实验结果
论文中使用METR-LA, PEMS-BAY, PeMSD7 (M) , PeMSD7(L), PEMS03, PEMS04, PEMS07和 PEMS08数据集将STFGNN与几种baseline方法进行了比较。论文中使用包括绝对绝对百分比误差（MAPE），平均平均误差（MAE）和均方根误差（RMSE）的三个指标来评估所有方法。
文章图片
文章图片
文章图片
除此之外，论文中还进行了消融实验，验证了每一个模块的重要性。
6、创新点
本文提出了一种用于时空交通数据预测的新颖框架。我们的模型可以通过时序数据驱动的相关图及其与给定空间距离图的进一步融合来有效捕获隐藏的空间依赖性。通过STFGN模块和新型的Gated CNN模块集成，该模块可以扩大时域上的感受野并将其堆叠，STFGNN可以同时学习局部时空异质性和全局时空同质性。
本文中的一些操作，比如时空信息融合邻接矩阵的构建，图卷积中的最大池化以及cropping操作可以参考STSGCN的文献：
Song, Chao, et al. "Spatial-Temporal Synchronous Graph Convolutional Networks: A New Framework for Spatial-Temporal Network Data Forecasting." Proceedings of the AAAI Conference on Artificial Intelligence. Vol. 34. No. 01. 2020.
关于这篇文献我也写过相关的解读推送：
时空同步图卷积网络：时空网络数据预测的新框架
Attention
【算法|AAAI2021（面向交通流预测的时空融合图神经网络）】如果你和我一样是轨道交通、道路交通、城市规划相关领域的，可以加微信：Dr_JinleiZhang，备注“进群”，加入交通大数据交流群！希望我们共同进步！
推荐阅读
- 算法|图神经网络（01）-图与图学习(上)
- 神经网络|干货！图神经网络及其自监督学习
- ML学习分享系列|ML学习分享系列3_计算广告小窥[下]要啥自行车！
- 神经网络|神经网络究竟干了一件什么事（）
- 数据结构|数据结构学习笔记（第六章 图）
- C数据结构|C数据结构（哈夫曼树算法实现与应用）
- 生产系统中的机器学习工程|模型结构设计
- 深度学习|李宏毅机器学习2021——Optimization（最优化）
- 机器学习|Graph Neural Network学习笔记-Day2