【时空序列】AAAI2021| 利用时空融合图神经网络进行交通流量预测

转载：时空实验室

在城市交通流量预测任务中，如何合理地建模城市交通数据中复杂的时空关系一直是一个富有挑战性的问题。传统方法中将城市空间格网化，并利用卷积神经网络（CNN）进行特征提取的方式存在一定的局限性，因此基于图神经网络（GNN）的时空数据建模成为了目前研究的焦点。现有的基于GNN的方法通常是利用一些先验信息（例如交通路网，空间距离等）构造图的结构，并在给定的图结构上进行训练。然而城市交通数据具有复杂的时空依赖关系，同时该依赖关系具有动态变化的特点。因此在给定的图结构上训练会限制模型对于时空动态依赖的学习。另一方面，类似的图构造方法通常只考虑了时间或空间单方面的特性，从而割裂了时间和空间的关联性。针对上述问题，来自北京大学的研究人员在AAAI2021上发表了论文《Spatial-Temporal Fusion Graph Neural Networks for Traffic Flow Forecasting》。该论文巧妙地利用动态时间归整（DTW）算法，根据历史数据实现了动态、自适应的时间图构建。结合论文提出的融合方法，该论文中的模型在多个公开数据集上取得了领先的成绩。

图 1 论文信息

一、背景介绍

作者认为GNN在时空数据预测中的应用已经有了显著的进步，然而现有的模型仍然存在以下的局限性：

1、图的构建过程缺乏丰富的信息作为支撑

大多数现有模型仅仅利用给定的空间邻近性进行图的构建，并忽略了节点之间在时间上的相似性。而一些空间距离遥远的节点同样可能在时间上具有很高的相关性，例如相隔遥远的商业区在早晚高峰时段同样会遇到交通拥堵。针对这个问题，已经有一些研究提出了一些解决方法，例如使用可学习的邻接矩阵[1,2]，或使用Transformer模型[3,4]。然而作者认为基于可学习邻接矩阵的方法缺乏对复杂时空依赖关系的表征能力，同时基于Transformer的模型则容易产生过拟合，且在长期预测时受到累积误差的影响较大。

2、无法有效地捕捉全局和局部相关性之间的关系

基于循环神经网络（RNN）的模型非常耗时，并且在处理长序列时可能会遇到梯度消失或爆炸的情况；Transformer的推断过程同样耗时；而基于CNN的方法则需要堆叠多层以捕获长序列的全局相关性。另一方面，作者认为现有的基于GNN的模型[1,2,5]只能考虑到全局和局部性其中之一，而无法兼顾。

针对上述问题，作者提出了名为STFGNN的模型。特别地，针对第一个问题，作者提出使用DTW算法计算节点的历史时间序列相似度，根据结果动态地构建时间图，并将时间图与其它图进行融合来帮助模型抽取隐藏的时空特征。同时，针对第二个问题，作者利用门限扩散卷积模块来综合考虑全局和局部相关性之间的关系。

二、方法介绍

1、问题定义

首先作者将城市路网表示为图，其中节点V表示观测数据来源（路段或传感器），且节点数，而空间邻接矩阵表示节点之间的邻近性或距离。同时，作者用表示t时刻节点的观测数据，则本文中的问题定义为学习一个函数f，对于参考时刻t，该函数通过包含时刻t在内的前T个时刻的观测数据，来预测t时刻后的个时刻的观测数据（如图 2所示）。

图 2 问题定义

2、模型架构

本文提出的模型结构如图 3所示。它包括（1）由一个全连接层组成的输入层，（2）堆叠的多个时空融合图神经网络层（STFGN层），和（3）由两个全链接层组成的输出层构成。其中每个STFGN层由多个并行的时空融合图神经模块（STFGN模块）和一个门控CNN模块构成，后者包括两个并行的一维扩张卷积模块。

图3 模型架构

2.1 时空融合图（STFG）的构建

为了在图的构建过程中尽可能地考虑更多的信息，作者提出在传统的给定空间图（spatial graph）的方法的基础上，动态地构建时间图（temporal graph），并将该图与空间图融合的方法。动态构建时间图的目的是获得比单独使用给定的空间图更准确的依赖关系和真实关系的特定图结构。这种方法可以使深度学习模型更轻巧，因为该融合图已经具有每个节点（1）与其空间邻居节点的相关信息，（2）与具有类似时间模式的节点的相关信息，以及（3）节点自身沿时间轴的状态信息。

在这里，作者希望利用DTW算法来计算每个节点时间序列的相关性。DTW算法是计算序列相关性的经典算法，但是利用DTW算法具有的时间复杂度。为了降低DTW的复杂度，论文中限制了它的“搜索长度”T为12个时间步。时间图的具体生成过程如图 4所示，其中k的经验取值为令与具有相似的稀疏程度。

图4时间图的生成过程

图 3（b）是STFG的示例。它由三种NxN矩阵组成：（1）由数据集提供的空间图，（2）由DTW算法生成的时间图，和（3）时间连接图。时间连接图表示了相邻两个时间步生成的中节点之间的对应关系。最终，考虑K个时间步时，会生成STFG。与其对应的节点特征构成的输入矩阵为

2.2 时空融合图神经（STFGN）模块

该论文中的基础图卷积算子使用了基于矩阵相乘的空间方法代替了基于谱分析的图卷积方法，从而无需计算邻接矩阵的拉普拉斯矩阵。通过对进行多次矩阵相乘，图中的每个节点可以从中获取空间相关性，从中获取时间相关性，以及从中获取自相关性。本文的图乘法块中还使用了LSTM中的门控机制。图乘法块的计算公式如图 5所示，其中表示STFGN的第l层隐状态，W和h均为可学习的参数。

图5图乘法块

堆叠多层图乘法块可以聚合更复杂的非局部空间相关性。作者还为每层引入了残差连接和极大池化操作。最后，保存中间时间步对应的特征作为输出。从图 3（b）可知，输出的特征包含复杂的异质性。在每次矩阵乘法中，对角线中间的通过空间邻居节点传输信息，在水平和垂直方向上沿时间轴为每个节点提供自己的自连接信息。角落的可增强来自具有相似时间模式的节点的信息。输入数据将独立并行地通过多个STFGN模块，它们地输出将被拼接并加上门控卷积模块的输出，并作为下一个STFGN层的输入。

2.3 门控卷积模块

尽管可以通过集成来提取全局时空相关性，但是它包含的相关性更多来其它节点，而节点本身的长期时空依赖性也很重要。因此本文引入了具有较大扩张率的门控卷积，其公式如图 6所示：

图6门控卷积块

其中和是激活函数，和是两个独立的1D卷积运算，扩张率为K-1。它可以扩大沿时间轴的感受野，从而增强模型性能，以提取时间序列的依赖关系。

本文使用Huber Loss作为整个模型训练的损失函数。

三、实验结果

论文在四个公开数据集上分别对模型的表现进行了评估，并选取了6种baseline方法作为比较。论文中使用MAE、MAPE和RMSE三种指标来评价模型的表现，结果如图 7所示。除此之外，论文中还进行了消融实验，验证了每一个模块的重要性，结果如图 8所示。

图7实验结果对比

图8消融实验结果

四、总结

本文的创新点在于提出使用DTW算法，通过计算节点时间序列相似度的方式动态地构建时间图并与空间图进行融合，从而补充了其它方法单纯使用空间信息构建的静态图所带来的不足，有利于模型更好地捕捉复杂的时空依赖及其动态变化。同时，本文将门控扩散卷积很好地应用在该模型中，从而解决长短时空关系的建模。

参考文献

[1] Song, C.; Lin, Y.; Guo, S.; and Wan, H.2020. Spatial-Temporal Synchronous Graph Convolutional Networks: A NewFramework for Spatial-Temporal Network Data Forecasting. In Proceedings of theAAAI Conference on Artificial Intelligence, volume 34, 914–921.

[2] Wu, Z.; Pan, S.; Long, G.; Jiang, J.; andZhang, C. 2019. Graph wavenet for deep spatial-temporal graph modeling. arXivpreprint arXiv:1906.00121 .

[3] Xu, M.; Dai, W.; Liu, C.; Gao, X.; Lin, W.;Qi, G.- J.; and Xiong, H. 2020. Spatial-Temporal Transformer Networks forTraffic Flow Forecasting. arXiv preprint arXiv:2001.02908 .

[4] Wang, X.; Ma, Y.; Wang, Y.; Jin, W.; Wang,X.; Tang, J.; Jia, C.; and Yu, J. 2020. Traffic Flow Prediction via Spatial TemporalGraph Neural Network. In Proceedings of The Web Conference 2020, 1082–1092.

[5] Yu, B.; Yin, H.; and Zhu, Z. 2017.Spatio-temporal graph convolutional networks: A deep learning framework fortraffic forecasting. arXiv preprint arXiv:1709.04875 .

公众号：AI蜗牛车

保持谦逊、保持自律、保持进步

个人微信

备注：昵称+学校/公司+方向

如果没有备注不拉群！

拉你进AI蜗牛车交流群