导语

据 Uber 统计，2018年，全年的网约车使用次数达180亿次，超过全球人口的两倍。准确的网约车订单预测，能够更好的调度车辆，提高车辆的利用率，减少等待时间，从而缓解交通拥堵，具有重要的经济和社会意义。近年来大火的图神经网络 GNN 相当于提供了一种新的建模和解决时空数据预测的手段。

ST-MGCN 是滴滴出行 AI Lab 发表于 AAAI 2019 的一种基于时空多图卷积网络的网约车需求量预测模型。区域级需求预测是网约车服务的关键技术。准确的网约车需求量预测可以指导车辆的调度，提高车辆的利用率，减少等待时间，以及缓解交通拥堵。区域之间所存在复杂的时空依赖关系使得这个问题具有很大挑战。已有方法主要关注于建模相邻区域在空间上的欧式相关性（Euclidean correlations），而作者发现距离较远区域之间的非欧相关性也对预测至关重要。

论文题目：

Spatiotemporal Multi-Graph Convolution Network for Ride-hailing Demand Forecasting

论文地址：

http://www-scf.usc.edu/~yaguang/papers/

aaai19_multi_graph_convolution.pdf

本文提出了时空多图卷机网络 spatiotemporal multi-graph convolution network (ST-MGCN)，一个新的用于网约车需求预测的深度学习模型。作者首先将区域间的非欧相关性建模到多个图，然后用多图卷积（multi-graph convolution）来建模其相关性。用全局上下文信息（global contextual information）来建模时序信息，并进一步提出了上下文门控循环神经网络模型（contextual gated recurrent neural network），给历史数据分配权重。在两个数据集上表现强于已有算法的 10% 以上。

论文背景

据 Uber 统计，2018年，全年的网约车使用次数达180亿次，超过全球人口的两倍。准确的网约车订单预测，能够更好的调度车辆，提高车辆的利用率，缓解交通拥堵，具有重要的经济和社会意义。

网约车需求量预测问题可以通过其数据建模方式来理解。以1小时为时间单位，1km*1km 的网格为空间单位，某城市某个小时订单量可以用如下所示的2d格点图片来表示，每个格点的数值是在该时间段内该区域所产生的滴滴打车的订单数的总和。那么所谓网约车需求量预测，就是已知过去几个小时每个格点的订单数，预测未来的订单数。

基于 grid 建模数据的示意图

实际上，直接做网约车需求量预测的文章并不多，但这个问题可以归结为交通流预测，并且本文的对比算法也是交通流预测模型，在同一网约车数据集上的表现。此外，交通流预测属于城市计算问题（urban computing）Yu Zheng. 2014. Urban Computing Concepts, Methodologies, and Applications。这个概念由当时还在微软亚洲研究院的郑宇提出。与我们生活息息相关的很多问题都可以归结为城市计算问题。比如车辆调度问题，输电网优化，物流及供应链管理，雾霾预测等。它们的特点是同时具有时间和空间两个维度的信息。近年来大火的图神经网络 GNN 相当于提供了一种新的建模和解决时空数据预测的手段。

问题定义

本文要解决的问题是，如何能够更好的建模多个区域之间所存在的非欧且多模态的时间和空间相关性，以实现高准确率的网约车需求量预测。

问题的数学表述如下，输入连续 T 个时刻的格点集合 X（格点的值为订单数），输出下一时刻的订单数，通过训练学习得到该映射函数 f。

这里的多模态可以理解为多重维度的关系。如下图所示，图中区域1和区域2在空间上是相邻关系，他们可能会有相似的约车量。区域1和区域3在功能上是相似的，可能在用车的 pattern 上存在比较高的相似性。区域4与区域1在同一条路旁边，同理，他们也会存在某种约车的相似性。

此外，订单数还与时间紧密相关，比如早晚高峰，节假日等，会对用车数产生比较大的影响，且会呈现某种周期性。所以，作者总结了这个问题所面临的两个挑战。空间上，需要学习区域间存在的多模态非欧相关性。时间上，需要学习复杂的多个时刻的时间依赖关系。

时空数据预测的相关工作可以分为两类：1. 将数据建模成为 2d image 上的格点，使用 CNN 的方法进行预测；2. 将数据建模到 graph 的节点上，基于图的方法进行预测。建模称为 2d image 的方法无法处理非欧数据（CNN 所处理的规整的网格是欧式空间）。假如就这个问题而言，我们建模为 1km*1km 的网格，那么整个城市不同区域使用的分辨率都是相同的，如果我们希望在市中心用更高的分辨率，郊区用更低的分辨率，或者加入某些兴趣点，这种方法是无法实现的。而现有基于 graph 的方法，虽然在区域建模上具有很高灵活性，但是无法建模上述区域间多模态的相关性。

算法框架

作者基于对网约车需求量预测问题的理解以及先验知识，设计了如下的算法框架。

主要分为三部分。

将每一帧的数据建模成为三张 graph。每张 graph 上的节点相同，即城市的网格化划分。连边通过如下图所示的规则进行构建。根据不同维度的相关性（邻域信息、功能相似度、交通连通性）确定节点之间的连边值。

时间维度的预测：将T个历史时间步的信息融合到一张图上。

空间维度的预测：将一个时刻的不同的相关性的图合成一个图。这就是论文题目中所说的多图卷积。

Contextual Gated Recurrent

Neural Network (CGRNN)

这是算法框架中的第二步，将 T个时间步的历史数据融合为一张图，这里所谓的 Contextual Gated 是指将历史数据每一帧通过图卷积网络进行数据融合，并且通过全局 pooling 得到该小时的全局信息。这个全局信息再与原来的 T个时间步的数据做点乘，得到了带权重的历史数据。然后迭代地输入到 RNN 中进行时间维度的信息融合，最终得到一张图。这里的 RNN 是权值共享的，也就是对于图上的每个顶点都过同一个 RNN，它们的所训练的是一套参数（工程上是可以实现的）。这样的好处有两点：1. 学习更加 general 的时序维度的汇聚方法，2. 减少模型复杂程度，使得更容易训练。

pooling 操作如下所示，将 t 时刻 graph 上所有节点的值都加起来，然后除以节点的个数。

这里需要注意的点是，每一帧数据做图卷积的方法是使用 k-ordered ChebNet。这个方法与我们熟知的图卷积网络 GCN 的区别是，GCN 可以简单地认为是 1-ordered ChebNet，只是汇聚一阶邻居。如文中给出的示意图所示。黑色是中心节点，黄色是 1阶邻居，红色是 2阶邻居。通过 k-ordered ChebConv，可以实现 k 阶领域的信息交互。使用 k 层的 GCN 堆叠也可以实现 k 阶邻域信息角度，但是随着层数增加，训练难度加大。所以，这可能是作者做模型选择的考虑点之一。

下面是相关的运算公式：

对 GCN 也不太熟悉的同学可以这样通俗的理解 GCN 的作用。每个 graph，都有对应的表示节点连接关系的邻接矩阵，还有数值在主对角线上，表示节点一阶邻居个数的度矩阵。拉普拉斯矩阵是通过邻接矩阵、度矩阵，用上面图中的公式计算得到的一个方阵。

在图卷积中，拉普拉斯矩阵中的元素，用来充当节点之间信息汇聚时，邻居节点的特征向量相加中前面对应的权重。下图是算法框架中第三步的内容（这两步都用到 k-ordered ChebConv）。其中不考虑多图的汇聚，花括号中的内容就是一个图上进行卷积的操作。第一个方阵就是拉普拉斯矩阵，第二个矩阵是这本卷积层的输入的邻居节点的特征向量（维度是 V*P，V 是节点个数，编号等同于拉普拉斯矩阵中节点编号，也就是节点在行向量的排序，P 是特征向量维度）。这两个矩阵进行矩阵乘法，得到的就是每个节点汇聚了其邻居节点特征的新的特征信息。这里的邻居节点根据算法的 k-ordered 所定义的 k 而不同，而范围不同，且会体现到拉普拉斯矩阵上。第三个矩阵 W 起到的作用等价于 MLP，做特征向量维度的变换。

感兴趣的同学可以阅读下面资料获取更详细的信息：GCN 作者 Kipf 的blog Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering，回顾频谱图卷积的经典⼯工作: 从ChebNet到GCN，拉普拉斯矩阵，

Multi-Graph Conv

算法的第三步所进行的是多图的信息汇聚。下图是以单个节点的视角来看这个算法的运行。首先，每个节点先各自通过 k-ordered ChebConv，然后在进行多图汇聚，汇聚操作的单位是节点。在这里是将前面分别建模了邻居信息、功能相似度、交通连通性的三个图进行汇聚。