一种基于时空图神经网络的出行时间估计解决方案

1、文章信息

《ConSTGAT: Contextual Spatial-Temporal Graph Attention Network for Travel Time Estimation at Baidu Maps》。这是百度AI实验室发表在计算机顶级会议KDD2020上的一篇文章。

2、摘要

给定出发时间和路线，预估行程时间在智能交通系统中发挥着重要的作用。首先，预测的准确性和各路段中的速度密切相关。现有的很多工作采用了时空图神经网络来提高交通预测的准确性，但是大部分的时空信息是分开使用的。这样的模型的缺点是没有充分利用时间和空间的相关性。其次，路线中的上下文信息，即路线中相邻的路段是影响车速的必要原因。先前的工作使用顺序编码模型来解决这个问题，但是很难将顺序模型扩展到大规模实际应用。在本文中，提出了ConSTGAT框架，该框架集成了流量预测和上下文信息以解决这两个问题。具体来说，首先提出一种时空图神经网络，该网络采用一种新颖的图注意力机制，旨在充分利用时空信息的联合关系。然后，为了有效利用上下文信息，该模型在局部窗口上采用卷积操作以捕获路线的上下文信息，并进一步采用多任务学习来提高性能。以此方式，可以并行并预先计算每个路段的行驶时间。最后在真实世界数据集上进行的大量实验证明了ConSTGAT的优越性。此外，ConSTGAT已经在百度地图上进行了部署，它每天成功地满足数百亿个请求。这证实了ConSTGAT是针对大型现实世界TTE服务的实用且强大的解决方案。

3、问题定义

图定义为，括号左边的是路段（Link）,右边的元素是边（Edge）如果两个路段之间有交界处，边就表示这个交界处。

路线定义，实际就是多个路段组成的有序序列：

请求定义，路线和出发时间的pair：，r代表路径s代表出发时间

样本定义，y是真实的到达时间：

模型中主要考虑了以下三种特征：

道路网：道路网描述了路段之间的关系。提取每个路段的以下信息作为要使用的特征：id，长度，宽度，车道数量，类型，速度限制，交叉口类型和交通信号灯类型。此外，路网的图形结构用于描述地理关系。

历史交通状况：由于历史交通状况会对交通预测产生重大影响，因此将不同时间段的几种交通速度作为特征。例如，从数据集中的交通记录推导出给定路段 l 在时间段 t 的行进速度中位数和平均行进速度，在该论文中将时间间隔设置为5分钟。

背景信息：TTE可能会受到许多背景信息的影响。出发时间是最重要的因素之一。高峰时间，工作日和其他与时间相关的信息也被提取为特征。将路线中第 i 个路段的背景信息表示为

4、模型

如论文图2所示，展示了提出的框架CONSTGAT的构成，该体系结构由三个模块组成：上下文信息，流量预测和集成模块。交通量预测模块采用一种时空图注意力网络来捕获交通状况的时空信息的联合关系。上下文信息模块和集成模块专注于解决路线的上下文信息问题，其中上下文信息模块利用卷积结构来捕获相邻路段的关系，集成模块利用多任务学习来提高性能。接下来对于每个模块都进行详细的介绍。

(1)交通量预测模块

为了充分利用时空信息的联合关系，该论文中提出了一种新颖的时空图注意力网络，该网络同时处理交通状况的地理信息和时间信息。时空图注意力网络模型的框架图如文中图3所示：

该模型的输入主要由如下三部分组成：

时空输入（ST）：。这里考虑的是路段节点的邻居特征，NB(Li)是路段 i 邻居的数量，T历史时间段的个数，d是Embedding的维度。具体的，实际是当前路段的相邻路段在历史时间段内的路况状态。

空间输入（S）：。邻居路段的静态特征输入，特征包括id，车道号等等。每个时间片段的空间静态特征相同。

时间输入（T）：。时间间隔的特征，具体没明确说，大概就是时间段直接embedding。每个节点的时间embedding也是相同的。

整理好三部分特征后进行然后是concat和reshape，再得到合并后的特征：

如图3中间部分所示，将其转换为三维的张量，三个维度分别是时间轴，邻居轴和embedding。

三维注意力机制：用上下文信息（下一小节具体说明）和背景信息作为query，则作为key和value，注意力计算式如下所示：

这里的Dense代表带有激活函数的全连接层，d(H)代表注意力机制的隐藏层维度。然后，query和路段li的历史交通状况之间的关系可以编码为。同时这里还用改了mask机制，为了提升模型的鲁棒性，防止过拟合。在训练阶段，假定10%的历史路况状态是未知的，将其随机mask掉，设置为0向量。在预测阶段，使用全部的历史信息。

(2)      上下文信息模块

这篇论文中开发了一种高效计算的方法，该方法将卷积应用到上下文信息模块中以捕获上下文信息，并在Integration模块中利用多任务学习。

路段的上下文信息，例如，两个相邻路段的之间的角度，主路和辅路的关系等等，在预测行程时间中非常重要。为了很好的预测路程时间，需要用到当前路线中的路段的相邻路段的信息。为了有效地做到这一点，仅考虑路线r中的路段li的附近路段，而不考虑r中的所有路段，这是基于以下观察：远程路段的影响通常远小于附近的路段。只取一个窗口内的路段：

窗口大小为w，当w=0，相当于路段 i 的信息，只由其自身决定。如果w趋于无穷则相当于使用了全路段的信息。

卷积神经网络（CNN）是一种获取局部依赖关系的有效方法。因此，我们使用卷积层来编码局部依赖关系，其公式为

Emb代表表示网络层，路段li的编码上下文信息用作流量预测模块和集成模块的输入。

如文中图4所示，集成模块负责汇总上下文信息，交通状况和背景信息的输出。它首先采用串联层，然后采用多个完全连接的层来收集预测链接和给定路线的行进时间所需的所有信息。给定请求对req =（r，s），则路段li在路线r中的旅行时间可以通过以下方式预测：

其中，MLP表示多个完全连接的层。然后，将路线中各路段的预计行驶时间相加，得出路线的预计行驶时间：

为了进一步提高性能，我们通过利用路段和整个路线的损失函数，将基于分段的方法和全路线端到端方法相结合。

对于路段耗时预测，使用Huber loss，与平方损失相比，它可以减轻离群值的影响：

整个路线耗时的损失，使用absolute percentage error（APE）

最终的loss为：

5、实验结果

论文中使用真实世界数据集将ConSTGAT与几种baseline方法进行了比较。论文中收集了太原市，合肥市和惠州市的大量路线和道路网络。这些数据集是从2019年7月21日至2019年8月31日的百度地图日志中采样的。前四周的数据用于模型训练，而前一周的数据用于评估。

论文中使用包括绝对绝对百分比误差（MAPE），平均平均误差（MAE）和均方根误差（RMSE）的三个指标来评估所有方法，这些方法被广泛用于评估回归问题的准确性。它们被定义为：

论文中将ConSTGAT与在三个真实数据集上的几种基准方法进行比较。表2示出了实验结果。从结果来看，首先在所有数据集上，ConSTGAT的性能均明显优于其他方法。AVG是一个简单的基准，效果最差。端到端方法DeepTravel在考虑上下文信息的情况下表现更好，但并未考虑用于交通预测的路网图结构。其次，在利用图结构的基于STGNN的方法（即STANN，DCRNN，GAT + Attention和ConSTGAT）中，ConSTGAT明显优于其他方法，因为它可以充分利用空间和时间信息的联合关系。

3DGAT是一个时空神经网络，也可以部署到其他时空应用程序。为了验证3DGAT的优越性，论文中将其与其他STGNN（包括STANN，DCRNN和GAT + Attention）进行了比较。由于一般的STGNN专注于估算路段的交通量而不是路线，因此，论文中还比较了STGNN在估算路段的行驶时间方面的性能。3DGAT可以看作是ConSTGAT的特殊版本，其上下文窗口大小w =0。从表3的结果可以看出，在流量预测问题上3DGAT优于其他STGNN。

6、创新点

该论文针对旅行时间估计的任务提出了ConSTGAT的端到端框架，该框架着重于解决交通预测和上下文信息的问题。开发了一种新颖的STGNN，通过3D注意机制获得时空信息的联合关系。此外，为了有效利用上下文信息，还设计了一种计算效率高的模型，在局部窗口上应用卷积以捕获路线的上下文信息，并进一步采用多任务学习来提高性能。

Attention

如果你和我一样是轨道交通、道路交通、城市规划相关领域的，可以加微信：Dr_JinleiZhang，备注“进群”，加入交通大数据交流群！希望我们共同进步！