KDD20 | 百度地图上用于估计旅行时间的上下文时空图注意网络

2020 年 10 月 25 日 图与推荐

论文专栏： 时空图神经网络在出行时间预估问题的应用

论文解读者： 北邮GAMMA Lab 硕士生王浩

题目： 百度地图上用于估计旅行时间的上下文时空图注意网络

会议： KDD 2020

论文地址： https://dl.acm.org/doi/pdf/10.1145/3394486.3403320

推荐理由： 本文提出了一个名为ConSTGAT的计算效率高的旅行时间估计框架，联合交通预测和上下文信息。区别于滴滴在KDD2020提出的HetETA方法，在模型设计上ConSTGAT通过借鉴基于分段的方法，采用多任务学习来提高计算效率。对于大规模的现实服务来说，它是一个实用而健壮的解决方案。

1 引言

出行时间估计任务(TTE)是对给定路线和出发时间的出行时间进行估计，在导航、路线规划和叫车服务等智能交通系统中发挥着重要作用。TTE具有挑战性，因为它存在很多方面会影响估计的准确性，如交通预测和路线的上下文信息(如交通灯和弯道)。目前存在的出行时间估计主要分为基于分段的方法与端对端的方法。基于分段的方法独立估计路线中每一个路段，但是忽略了上下文信息，端对端的方法考虑了上下文信息，采用序列编码结构将路线中的所有路段作为一个整体，但是计算量过大，不满足实际应用场景的需求。

本文提出了一个名为ConSTGAT的端到端的神经网络框架，该框架集成了交通预测和上下文信息，同时还借鉴了基于路段的方法，该方法通过并行和提前计算每个路段的出行时间，保持了很高的推理效率。它已经在百度地图上投入使用，每天成功地处理数百亿的请求。

1.1 问题定义

节点的重要性推断：采用GNN方法解决出行时间预测问题首先需要将路段网络转化为图结构，将每一个路段抽象化为一个节点，节点之间的连边表示两条路段共享一个交叉点，采用这种方式将其转化为图结构。对于某一路线r的时间预测，给定其路段序列，以及出发时间s，组成一条路线时间请求req=(r,s)。预测任务为路线中所有路段的行驶时间，然后通过加和得到总体行驶时间。

1.2 特征提取

在TTE任务中路段网络，历史交通信息以及背景信息都对TTE的预测起着重要作用。在路段网络中每一个路段的ID、长、宽、车道数等被提取出来作为节点的特征。由于历史交通状况对交通预测有显著影响，因此选取不同时段的几种交通速度作为特征。同时出发的背景信息也很重要，提取出发时间、高峰时间、工作日等与时间相关的信息作为特征，该路线第i个链路的背景信息表示为。

2 方法

下图显示了提出的架构ConSTGAT，它包括三个模块:上下文信息、交通预测和集成模块。交通预测模块采用一种时空图注意力网络来获取交通状况、时空信息的联合关系。上下文信息模块和集成模块主要解决路段的上下文信息问题，其中上下文信息模块利用卷积结构来获取相邻链路的关系，集成模块采用多任务学习来提高性能，任务是预测每个路段的时间。

2.1 交通预测

路段未来的交通状况与路段本身以及相邻路段的历史交通状况密切相关。例如，一个路段上的交通拥塞很有可能在短时间内导致其邻居路段上的交通拥塞。为了充分利用时空信息的联合关系，提出了一种同时处理交通状况的结构信息和时间信息的时空图关注网络。

将当前路段与邻居路段的历史交通信息、邻居路段的基本信息、以及时间信息进行拼接成，然后将作为注意力机制的keys和values，上下文信息、和背景信息的组合作为注意力机制的query。

同时因为实际的百度地图场景中可能因为网络信号差，部分历史交通信息可能存在无法捕捉，所以在训练阶段采用掩膜机制随机屏蔽10%历史信息，提高模型鲁棒性。

2.2 上下文信息

相邻路段的信息对当前路段行驶时间起重要作用，同时远程路段的影响往往明显小于附近路段的影响，所以采用一个CNN层捕捉局部依赖关系，通过设置一个窗口，捕捉任一路段的局部依赖关系，得到该路段的上下文信息。

2.3 集成

因为背景信息，交通预测信息，上下文信息都对出行时间预测有影响，所以对 , , 进行拼接，然后使用MLP进行所有路段的时间预测，然后将所有时间加和得到完整出行时间。即预测结果包含所有路段时间以及总时间。

针对单路段时间与总行程时间分别采用不同的损失函数，针对单路段时间预测采用Huber loss。

针对总时间采用APE（absolute percentage error）作为损失函数：

完整损失函数为：

3 实验

模型在百度地图的Taiyuan，Hefei，Huizhou三个数据集上都取得较baseline更好的效果。

4 总结

这是一篇由百度地图研究人员设计的采用GNN模型解决出行时间估计问题的论文。出行时间估计任务(TTE)是对给定路线和出发时间的出行时间进行估计，在导航、路线规划和叫车服务等智能交通系统中发挥着重要作用。这项任务具有挑战性，因为有许多重要方面，如交通预测和上下文信息。现有工作主要采用时空图神经网络来提高交通预测的准确性，但是没有充分利用空间和时间的相关性。第二，路线的上下文信息，即路线中相邻路段的连接，是影响出行时间的重要因素。以前的工作主要使用顺序编码模型来解决这个问题，但是很难应用到大规模的实际服务中。在本文中，作者提出了一个名为ConSTGAT的端到端的神经网络框架，该框架集成了交通预测和上下文信息来解决这两个问题。针对交通预测问题，提出了一种时空图神经网络，该网络采用了一种新颖的图注意机制，旨在充分利用时空信息的联合关系。然后，为了有效地利用上下文信息，在局部窗口上应用卷积来捕获路段的上下文信息，并进一步采用多任务学习共性预测每个路段的时间。在大规模真实数据集上进行的大量实验证明了ConSTGAT的优越性。

本期责任编辑：杨成

本期编辑：刘佳玮

北邮 GAMMA Lab 公众号

主编：石川

责任编辑：王啸、杨成

编辑：刘佳玮

副编辑：郝燕如，纪厚业

长按下图并点击“识别图中二维码”

即可关注北邮 GAMMA Lab 公众号