|更精确地预估到达时间，滴滴新研究提出异质时空图卷积网络

机器之心发布
机器之心编辑部
「师傅，还有多长时间能到啊？」在打的赶往目的地时，我们经常会问这样一个问题。但如果我们打的是滴滴，这个问题就不用开口问了。因为，滴滴的研究者正不断挑战更加精确的到达时间预估结果，相关结果被 KDD 2020 接收为Oral论文。
第 26 届 ACM SIGKDD 知识发现和数据挖掘会议（KDD 2020）正以线上形式召开。今年 KDD 应用数据科学方向 (Applied Data Science Track) 共收到 756 篇论文投稿，收录 121 篇，接收率约为 16.0% ，其中 Oral 论文 44 篇、Poster 论文 77 篇；KDD 研究方向 (Research Track) 有 1279 篇论文投稿，收录 216 篇，接收率约为 16.9% 。
在本届大会中，滴滴的《HetETA: Heterogeneous Information Network Embedding for Estimating Time of Arrival》被接收为 Oral 论文。在这篇论文中，滴滴 AI Labs 技术团队针对预估到达时间任务构建了一个异质时空图，并提出了 HetETA 框架来挖掘时空图中的丰富语义信息，有效提升了预估到达时间任务的精确度。本文是对这篇论文的详细解读。

本文插图
论文地址：https://dl.acm.org/doi/pdf/10.1145/3394486.3403294
代码地址：https://github.com/didi/heteta
研究背景与挑战
随着人们与日俱增的出行需求，智慧交通系统已成为城市建设中不可或缺的角色。预估到达时间（Estimated Time of Arrival ， ETA）是智慧交通系统中尤为关键的一项任务，根据给定的出发时间，精确地预估出从起点到终点所需时长，有助于节省用户的出行时间，优化车辆调度和路径规划等。 ETA 任务与道路交通速度预测密切相关，即当道路的交通速度（或道路拥堵程度）已知时，可通过道路长度将道路的交通速度转化为通过该道路所需的时间。
当前大多数工作致力于建立丰富的特征系统来提高 ETA 任务的准确性，然而这些特征系统很少考虑到空间信息的构建与挖掘。如图 1 所示，地图中的道路网络实际上是一种含有多个链接关系的异质图，而这些道路之间的链接关系（即空间信息）对于道路交通速度预测至关重要。例如图 1 中的路段 1 如果是拥堵的，那么路段 1 的前方直行道路 2 大概率也会是拥堵的。

本文插图
图表 1：地图数据到异质图的转换
又比如在高速上直行的车辆速度一般高于向右驶出闸道的车辆。然而地图中的道路网络是一个大规模的稀疏网络，以包含了 7 万多个主干道的沈阳市为例，其道路网络的平均度数为 2.52 ，即一条道路路段一般只链接 2～3 条道路。这样的大规模稀疏网络难以直接使用需要充足邻居信息的图神经网络（Graph Neural Network ， GNN）进行网络的表示学习（representation learning／network embedding）。
除了地图数据中的道路网络，车辆轨迹信息也是一种描述道路之间链接关系的空间信息。例如图 2 中青年大街的车辆大部分流向了太原街（沈阳市具有火车站和客运站的交通枢纽）和中街（沈阳市著名购物街）。大量的车辆轨迹组成了车流信息，隐含了城市的交通模式以及驾驶经验、偏好信息，这些信息很难直接从地图数据中的道路网络中得到，因此需要对道路网络和车流信息进行联合建模。

本文插图
图表 2：沈阳车流示意图
此外， ETA 任务也与道路交通速度的时序信息息息相关。直观来说，若某路段在当前时刻为拥堵状态，则下一时刻该路段大概率仍为拥堵状态，即道路下一时刻的交通状态与近期时刻的交通状态（近期路况）相关。分页标题
图 3 描述了沈阳某道路路段交通状况在 2 周内的变化趋势，从中可观察到周一到周五工作日有明显近似的高峰时段（早上 8 点左右以及晚上 6 点左右），而周六日的高峰时段则从早 8 点持续到晚上 6 点左右，即交通路况呈一定程度的周期性与规律性。因此，道路下一时刻的交通状态除了与其近期路况相关，还与其近几日的相同时段路况相关，同时也与近几周相同星期的相同时段路况相关。

本文插图
图表 3：沈阳某道路在 2 周内的交通速度变化情况
由此，滴滴在这篇论文中主要针对以下问题提出解决方案：
如何挖掘空间信息中不同关系链接所蕴含的语义关系？
如何克服大规模道路网络的稀疏性？
如何联合道路网络信息和车流信息对 ETA 任务进行预测？
如何处理不同时序（近期的、每日的、每周的）路况信息中的模式关系？
解决方案：HetETA

本文插图
图表 4：HetETA 框架示意图
为了解决上述问题，该研究提出了 HetETA 框架，联合卷积神经网络（Convolution Neural Network ， CNN）和图神经网络（Graph Neural Network, GNN）处理时序信息和空间信息。如图 4 所示， HetETA 由三个相同结构的组件组成，每个组件分别用于处理不同时序路况（近期的、每日的、每周的）中的异质时空信息，其中，，
为当前查询时刻，为输入三个组件的时间片数量，为一天的时间片总数量。三个组件均通过双拼三明治结构进行时空卷积得到对应的低维向量表示，然后将这三个低维向量表示拼接起来作为长向量，经过一个全连接层得到预估的路段速度：
【|更精确地预估到达时间，滴滴新研究提出异质时空图卷积网络】

本文插图
双拼三明治结构（Double-stuffed sandwich layer）由 3 个卷积神经网络和 2 个 Het-ChebNet 组成，其中 2 个 Het-ChebNet 夹在两个卷积神经网络中间形成一层空间卷积层，通过对时间（CNN）和空间的（Het-ChebNet）的交替卷积使模型能够充分地挖掘时空之间的关联性。最后一层的卷积神经网络用于将时间维度压缩至一维，以便于后续全连接层的操作。为了使 CNN 达到类似 RNN 的时序处理效果，本文采用了带有门控的因果卷积神经网络（如图 5），在输入时，执行卷积操作：

本文插图
图表 5：带有门控的因果卷积神经网络层
进而得到当前层的隐含状态向量 H 。空间卷积层所包含的两个 Het-ChebNet 分别用于对道路网络和车流网络所构建的异质图进行空间信息的卷积与提取，分别由两个 Het-ChebNet 得到的隐含状态通过拼接操作输入下一层卷积神经网络（如图 6）。

本文插图
图表 6：双拼图卷积网络
车流网络所构建的异质图一定程度上缓解了道路网络的稀疏问题，为了克服基于 GCN（Graph Convolutional Network）的图卷积模型无法在稀疏的道路网络上收集充足的邻居信息的问题，该研究采用了基于谱图理论的 ChebNet 网络，通过切比雪夫多项式构成局域滤波器：

本文插图
然而，传统的 ChebNet 网络无法处理异质图中所包含的多关系信息，因此该研究基于 ChebNet 提出了一个能够捕捉多关系链接信息的 Het-ChebNet：分页标题

本文插图
即通过在滤波器上乘积一个关于邻居边的注意力评分矩阵，使得滤波器能够对不同的链接关系进行区分过滤提取信息。注意力评分矩阵存储了异质图中 z 阶邻居边的注意力评分，其计算公式为：

本文插图
在异质图中，相同的两个顶点之间可能具有多种链接关系，因此注意力评分矩阵的值为这些链接关系链接的评分之和：
最后通过 softmax 函数进行评分矩阵的归一化：

本文插图
实验效果
研究人员在滴滴平台数据集上对 HetETA 模型的有效性进行了验证，对比算法包括 GRU、DCRNN、STGCN、Graph WaveNet 以及 ASTGCN 。
如图 7 所示，相比其他模型， HetETA 在送驾数据集和接驾数据集上分别获得了 3.40%～46.67% 和 0.69%～28.33% 的实质性收益。当μ更大时， HetETA 带来的 BCR-μ 的改善变得更加明显。

本文插图
图表 7：ETA 任务 BCR 效果对比
此外，该研究还将 HetETA 与 WDR 模型联合起来，将 HetETA 最后一层的隐状态向量作为 WDR 的额外特征输入。与原来的 WDR 模型相比，加入了 HetETA 的 WDR 模型 MAPE 下降了 1.19%～1.94% ， MAE 下降了 1.57%～5.30% ， RMSE 下降了 1.67%～6.42% ， BCR 下降了 3.33%～18.50% 。这对于具有不可预测性的 ETA 任务而言，无疑是非常显著的提升，证明了 HetETA 模型的有效性。

本文插图