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

论文题目：基于时空多图卷积网络的网约⻋需求量预测

参考笔记：https://zhuanlan.zhihu.com/p/76978929

摘要

ST-MGCN 是滴滴出行 AI Lab 发表于 AAAI 2019 的一种基于时空多图卷积网络的网约⻋需求量预测模型。区域级需求预测是网约车服务的关键技术。准确的网约车需求量预测可以指导车辆的调度，提高车辆的利用率，减少等待时间，以及缓解交通拥堵。区域之间所存在复杂的时空依赖关系使得这个问题具有很大挑战。已有方法主要关注于建模相邻区域在空间上的欧式相关性（Euclidean correlations），而作者发现距离较远区域之间的非欧相关性也对预测至关重要。本文提出了时空多图卷机网络 spatiotemporal multi-graph convolution network (ST-MGCN)，一个新的用于网约车需求预测的深度学习模型。作者首先将区域间的非欧相关性建模到多个图，然后用多图卷积（multi-graph convolution）来建模其相关性。用全局上下文信息（global contextual information）来建模时序信息，并进一步提出了上下文门控循环神经网络模型（contextual gated recurrent neural network），给历史数据分配权重。在两个数据集上表现强于已有算法的 10% 以上。

介绍

时空预测是城市计算中的一项关键任务，它在自动驾驶汽车操作，能源和智能电网优化，物流和供应链管理等领域都有广泛的应用。 在本文中，我们研究了一项重要任务：区域级乘车需求预测，这是智能交通系统的重要组成部分之一。 区域级别的叫车需求预测的目的是根据历史观察结果预测城市中各个区域的未来需求。 准确的乘车需求预测可以帮助组织车队，提高车辆利用率，减少等待时间并减轻交通拥堵（Yao等人，2018b）。 主要由于复杂的时空相关性，该任务具有挑战性。 一方面，在不同区域之间观察到复杂的依赖性。比如说，一个区域的需求通常受到其空间相邻邻居的影响，同时又与具有相似语境的远距离区域相关联。另一方面，不同时间观测值之间也存在非线性相关性。 通常与一小时前，一天前甚至一周前的各种历史观察结果相关。

深度学习的最新进展为基于区域的时空预测中的复杂时空关系建模提供了令人鼓舞的结果。 使用卷积神经网络和递归神经网络，在（Shi等人2015; Yu等人2017; Shi等人2017; Zhang，Zheng和Qi 2017; Zhang等人2018a ； Ma等人，2017； Yao等人，2018b； 2018a）。 尽管取得了可喜的结果，但我们认为在建模时空相关性时，两个重要方面被大大忽略了。 首先，这些方法主要关注于建模不同区域之间的欧几里得相关性，但是，我们观察到非欧几里德成对相关性对于准确预测也至关重要。
image.png
对于区域1，除了邻近区域2外，它还可能与共享相似功能的远距离区域3相关，即它们都在学校和医院附近。 此外，区域1也可能会受到区域4的影响，区域4通过高速公路直接连接到区域1。 其次，在这些方法中，当使用RNN对时间相关性进行建模时，每个区域都是独立处理或仅基于本地信息进行处理。 但是，我们认为全局和上下文信息也很重要。 例如，全球乘车需求的增加/减少通常表明某些事件的发生会影响未来的需求。

为了解决这些挑战，我们提出了一种新颖的深度学习模型，称为时空多图卷积网络（ST-MGCN）。在ST-MGCN中，我们建议将区域之间的非欧氏相关性编码为多个图形。与（Yao等人2018b）不同，后者使用图嵌入作为每个区域的额外恒定特征，我们利用图卷积显式地建模区域之间的成对关系。图卷积能够在执行预测时聚集邻域信息，而这是传统图嵌入难以实现的。此外，为了在建模时间相关性时合并全局上下文信息，我们提出了上下文门控递归神经网络（CGRNN）。它通过学习门控机制来增强RNN，该门控机制是根据汇总的全局信息计算得出的，以重新加权不同时间戳中的观测值。在两个现实世界的大规模乘车需求数据集上进行评估时，ST-MGCN始终以最先进的方式始终领先于最先进的基准。总而言之，本文做出了以下贡献：

  • 我们在乘车需求预测中确定区域之间的非欧几里得相关性，并建议使用多个图形对它们进行编码。 然后，我们进一步利用提出的多图卷积对这些相关性进行显式建模。
  • 我们建议使用上下文门控RNN（CGRNN）在对时间依赖性进行建模时合并全局上下文信息。
  • 我们在两个大规模的真实世界数据集上进行了广泛的实验，与用于叫车需求预测的最新基准方法相比，该方法可将相对误差减少10％以上。

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

相关工作

城市计算的时空预测

图卷积网络

Channel-wise attention

Region-level ride-hailing demand forecasting

问题定义

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

方法

我们将时空乘车需求预测的学习问题形式化，并描述如何使用提出的时空多图卷积网络（ST-MGCN）对时空依赖进行建模。

区域级网约车需求预测（Region-level ride-hailing demand forecasting ）

  • 将城市划分为大小相等的网格，每个网格定义为区域v∈V，其中V表示城市中所有不相交区域的集合。
  • 令X（t）表示在第t个间隔的所有区域中的订单数。
  • 将区域级乘车需求预测问题公式化为给定具有固定时间长度的输入的单步时空预测，即，学习函数f：R | V |×T→R | V | 将所有区域的历史需求映射到下一个时间步的需求。
    问题的数学表述如下，输入连续 T 个时刻的格点集合 X（格点的值为订单数），输出下一时刻的订单数，通过训练学习得到该映射函数 f。
    $$
    [X^{(t-T+1)},…,X^{(t)}] \xrightarrow{f(\cdot)} X^{(t+1)}
    $$
    这里的多模态可以理解为多重维度的关系。

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

时空数据预测的相关工作可以分为两类：

  1. 将数据建模成为 2d image 上的格点，使用 CNN 的方法进行预测；
  2. 将数据建模到 graph 的节点上，基于图的方法进行预测。建模称为 2d image 的方法无法处理非欧数据（CNN 所处理的规整的网格是欧式空间）。

假如就这个问题而言，我们建模为 1km*1km 的网格，那么整个城市不同区域使用的分辨率都是相同的，如果我们希望在市中心用更高的分辨率，郊区用更低的分辨率，或者加入某些兴趣点，这种方法是无法实现的。而现有基于 graph 的方法，虽然在区域建模上具有很高灵活性，但是无法建模上述区域间多模态的相关性。

框架概览

ST-MGCN的系统架构：
image.png

  • 将多个区域之间的相关性的不同方面表示为多个图，其顶点表示区域，并且边缘编码区域之间的成对关系。

  • 首先，我们使用提议的上下文门控递归神经网络（CGRNN）来考虑全球上下文信息来汇总不同时间的观察结果。

  • 然后，使用多图卷积来捕获区域之间的不同类型的相关性。

  • 最后，使用完全连接的神经网络将特征转换为预测。

主要分为三个部分：

  1. 将每一帧的数据建模成为三张 graph。每张 graph 上的节点相同，即城市的网格化划分。连边通过如下图所示的规则进行构建。根据不同维度的相关性（邻域信息、功能相似度、交通连通性）确定节点之间的连边值。
  2. 时间维度的预测：将T个历史时间步的信息融合到一张图上。
  3. 空间维度的预测：将一个时刻的不同的相关性的图合成一个图。这就是论文题目中所说的多图卷积。

    Spatial dependency modeling

在本节中，我们将展示如何使用多个图来编码区域之间不同类型的相关性，以及如何使用建议的多图卷积来对这些关系进行建模。

我们使用图形对区域之间的三种相关类型进行建模，包括

  1. 邻域图$\mathcal{G}_N =(V，A_N)$，它编码空间接近度，
  2. 函数相似度图$\mathcal{G}_F =(V，A_F)$，它编码区域周围兴趣点（POI）的相似度，
  3. 运输连通性图$\mathcal{G}_T =(V，A_T)$，它编码远处区域之间的连通性。
    请注意，我们的方法可以很容易地扩展为通过构造相关图来建模新类型的相关性。

Neighborhood：

  • 区域的邻域是根据空间邻近性定义的。
  • 通过将区域连接到3×3网格中的8个相邻区域来构造图形。
    $$
    A_{N,ij} = \begin{cases}
    1, &\text {$v_i$ and $v_j$ are adjacent} \
    0, &\quad otherwise
    \end{cases}
    $$

Functional similarity：

  • 在对某个区域进行预测时，直观地参考在功能方面与此区域相似的其他区域。
  • 可以使用每个类别的周围POI来表征区域功能，
  • 并且将两个顶点（区域）之间的边缘定义为POI相似性
    $$
    A_{S,i,j} = sim(P_{v_i},P_{v_j}) \in [0,1]
    $$
  • $P_{v_i}$，$P_{v_j}$分别是区域$v_i$和$v_j$的POI向量
  • 其维数等于POI类别的数量，每个条目代表该区域中特定POI类别的数量。

Transportation connectivity：
运输系统也是执行时空预测时的重要因素。
直观地，可以将那些地理上相距遥远但可方便到达的区域进行关联。 这些类型的连通性是由高速公路（如高速公路），公路或地铁（如地铁）引起的。
在这里，我们将通过这些道路直接连接的区域定义为“已连接”（connected），
相应的边定义为：
$$
A_{C,i,j} = max(0,conn(v_i,v_j)- A_{N,i,j} \in {0,1}
$$

  • $conn(u,v)$是$v_i$和$v_j$之间的连通性的指标函数。
  • 注意，将邻域边缘从连通性图中移除以避免冗余相关，并且还导致稀疏图。

Multi-graph convolution for spatial dependency modeling：

  • 用于空间依赖建模的多图卷积
  • 通过构建这些图，我们提出了多图卷积，以对等式5中定义的空间相关性进行建模。
    $$
    X_{l+1} = \sigma \big ( \bigsqcup_{A \in \mathbb A} f(A;\theta_i) X_l W_l \big )
    $$
  • $X_l \in \mathbb R ^{|V| \times P_l}$,$X_{l+1} \in \mathbb R ^{|V| \times P_{l+1}$ 是| V |的特征向量 l层和l + 1层中的两个区域。
  • σ表示激活函数，F表示聚合函数，例如求和，最大值，平均值等。
  • A表示一组图形
  • f（A;θi）∈R| V |×| V | 表示基于θi参数化的图A∈A的不同样本的聚合矩阵
  • W_l \in \mathbb R^{P_l \times P_{l+1}}表示特征变换矩阵，
    例如
  • 如果$f(A;\theta_i)$是拉普拉斯矩阵L的多项式函数，则它将在多张图中变为ChebNet（Defferrard，Bresson和Vandergheynst 2016）。
  • 如果$f(A;\theta_i) = I$，即恒等矩阵，则它将退回到完全连接的网络。
    在实现中，选择f（A;θi）作为图拉普拉斯算子L的K阶多项式函数，图3显示了通过图卷积层对集中区域进行值转换的示例。 邻接矩阵为0或1，项Lk ij 6 = 0表示vi能够以k跳达到vj。 在卷积运算方面，k定义了空间特征提取过程中接收场的大小。 使用图1中的道路连通图GC =（V，AC）进行说明。 在邻接矩阵AC中，我们有：

Temporal correlation modeling

我们提出了上下文门控递归神经网络（CGRNN）来建模不同时间戳中的观察之间的相关性。 CGRNN通过使用上下文感知门控机制增强RNN来将上下文信息纳入时间建模中，该机制的体系结构如图4所示。假设，我们有T个时间观测值，而X（t）∈R | V |×P表示第t个观测值 ，其中P是要素尺寸，如果要素仅包含订单数量，则P将为1。 然后上下文选通机制的工作流程如下。