How to Build a Graph-Based Deep Learning Architecture in Traffic Domain: A Survey

这篇综述性论文介绍图神经网络在交通领域的应用。

• 1. 摘要
• 2. 前言
• 3. 研究方向
• 4. 问题定义
  • 4.1. 构建图
  • 4.2. 构造邻接矩阵
• 5. 前人的模型
  • 5.1. GNN
  • 5.2. RNN
  • 5.3. TCN
  • 5.4. Seq2Seq
  • 5.5. GAN
• 6. 挑战
  • 6.1. 空间依赖
  • 6.2. 时间依赖
  • 6.3. 时空依赖
  • 6.4. 外部因素
• 7. 未来方向

1. 摘要

在交通数据中，有很多数据以图的形式存在，为了充分利用其中的空间信息，很多模型使用图神经网络来处理交通图数据。本文针对交通领域的图网络模型进行总结。

2. 前言

在交通预测领域，（1）早期采用的方法有：ARIMA,VAR,Kalman过滤器等，然而，这些方法通常需要一些前提假设，例如数据是静态且线性相关，不能应用在实际数据中。（2）机器学习方法例如SVM，K近邻可以建模交通数据中的非线性相关性，但是模型结构较浅，且需要人工构造和选择特征，不能满足大量交通数据的应用需求。（3）深度学习方法，例如RNN无法捕获空间相关性，CNN无法应用在图数据中，并且CNN更关注local相关性，忽略了global相关性。（4）图神经网络，使用图神经网络来解决交通领域的预测问题。
贡献总结如下：

• 第一篇介绍图神经网络在交通领域应用的综述
• 系统地列出交通领域的研究方向和挑战
• 针对4种交通领域数据，介绍如何构建图
• 分析了5种应用在图交通领域的技术，介绍了它们的优缺点，以及变体
• 讨论了基于图网络的交通任务中4种常见的挑战，并总结对应的解决方案
• 收集数据集，开源代码

3. 研究方向

给出了交通领域的一些研究问题

1. 交通拥堵
2. 交通需求
   出租车、自行车、公共交通的需求预测，像滴滴，Uber等线上打车平台经常做这一类问题。
3. 交通安全
   预测交通事故的风险，严重程度
4. 交通监控
   主要通过监控的图像和视频检测车辆，行人检测。
5. 自动驾驶
   自动驾驶要求检测树木，道路，行人，一般和CV领域相关。

图神经网络在交通领域的应用

1. 交通状态预测
   交通状态：交通流量、速度、时间ETA、密度等。
2. 交通需求预测
   预测将来用户对出租车、自行车的需求
3. 交通信号预测
   减低用户在交叉路口的等待时间，避免交通拥堵
4. 司机行为分类

交通事故预测还没有用到图模型。

4. 问题定义

基于图的交通预测问题，首先需要构件图G。

• 图：无权图，有权图，无向图，有向图，取决于具体的任务。
• 节点：传感器sensor，路段，道路交叉口，GPS交叉点。
• 邻接矩阵A：非0即1，浮点数（表示2个节点的关系，例如相似性，距离）

给定历史P个时间段所有节点的信息，维度是$\left[\mathcal{X}_{1}, \cdots, \mathcal{X}_{i}, \cdots, \mathcal{X}_{\mathbf{P}}\right] \in \mathbb{R}^{\mathbf{P} \times \mathbf{N} \times \mathbf{F}_{1}}$预测未来Q个时间段的$\mathcal{Y}=\left[\mathcal{Y}_{1}, \cdots, \mathcal{Y}_{j}, \cdots, \mathcal{Y}_{\mathrm{Q}}\right] \in \mathbb{R}^{\mathbf{Q} \times \mathbf{N} \times \mathrm{F}_{\mathrm{O}}}$

• 预测的特征只有1个，即$F_O=1$，预测特征有多个，即$F_O>1$
• 预测未来时间段只有1个，单步预测，即$Q=1$，预测未来时间段有多个，多步预测，即$Q>1$
• 多步预测问题中，一般使用FC（将输出reshape成需要的维度，ASTGCN,T-GCN,），Seq2Seq（使用RNN循环输出预测结果,DCRNN,GMAN），空洞技术（WaveNet）

4.1. 构建图

在构建图时，一般使用3类数据：传感器，GPS轨迹，打车订单数据，

1. 传感器数据
   最常用的加州PEMS数据，图中的每个节点表示一个传感器，同一条路上的传感器有边相连。
2. GPS数据
   GPS轨迹数据，需要将GPS匹配到最近的路段上，以路段为节点创建图，或者以交叉路口为节点创建图。这里的图可以是有向，也可以无向。

1. 订单数据
   将城市划分为网格，每个节点表示一个网格，边表示连通性。可以根据不同的特征来构件图，例如下图使用邻近区域、道路连通性、功能相似区域分别构建3个图。

1. 公共交通数据
   • 地铁图：每个地铁站表示一个节点，如果一条线上的2个地铁站相邻则有边。图信号矩阵是inflow和outflow
   • 公交车图：每个公交站是一个节点，如果一条线上的2个公交站相邻则有边。图信号矩阵进站记录

4.2. 构造邻接矩阵

1. 静态邻接矩阵
   邻接矩阵不会随着时间变化。可以根据节点之间的特征构建多个邻接矩阵，例如功能相似，道路相通，时间相似。邻接矩阵中的值可以是非0即1，也可以表示节点间距离或者相似性。一般通过阈值来定义邻接矩阵，通过调整阈值来控制邻接矩阵的稀疏性。 $$\mathbf{a}_{i j}=\left\{\begin{array}{l} \exp \left(-\frac{\mathbf{d}_{i j}^{2}}{\sigma^{2}}\right), i \neq j \text { and } \mathbf{d}_{i j} \geq \epsilon \\ 0 \quad, i=j \text { or } \mathbf{d}_{i j}<\epsilon \end{array}\right.$$

1. 动态邻接矩阵
   有2种情况：1. 邻接矩阵不随着时间变化，但是邻接矩阵不是预先定义好的，而是模型先动态学习节点嵌入，然后根据学习到的节点嵌入构造邻接矩阵。2. 邻接矩阵随着时间变化。

5. 前人的模型

分析图神经网络在交通领域的应用，发现GNN通常和其他组件一起用，类似RNN,Seq2Seq，TCN等。

5.1. GNN

GNN在交通领域的应用主要有3个：谱图卷积for无向图，扩散卷积for有向图。

1. 谱图卷积

   $$\begin{aligned} Y_{j} &=\rho\left(\Theta_{j} *_{\mathcal{G}} X\right) \\ &=\rho\left(\sum_{i=1}^{\mathbf{F}_{\mathrm{I}}} \theta_{i, j} \tilde{\mathbf{D}}^{-\frac{1}{2}} \tilde{\mathbf{A}} \tilde{\mathbf{D}}^{-\frac{1}{2}} X_{i}\right), 1 \leq j \leq \mathbf{F}_{\mathbf{O}} \\ Y &=\rho\left(\tilde{\mathbf{D}}^{-\frac{1}{2}} \tilde{\mathbf{A}} \tilde{\mathbf{D}}^{-\frac{1}{2}} X W\right) \end{aligned}$$

   谱图卷积要求对称的拉普拉斯矩阵，来实现特征值分解。

2. 扩散卷积
   谱图卷积要求对称的拉普拉斯矩阵，来实现特征值分解。但是对于有向图来说，拉普拉斯矩阵不是对称的。扩散卷积对图的结构，邻接矩阵，拉普拉斯矩阵没有任何限制。扩散卷积可以看做是转移矩阵的幂次，表示从节点i到节点j的转移概率。

   $$y=\Theta *_{\mathcal{G}} x=\sum_{k=0}^{\mathrm{K}-1}\left(\theta_{k, 1}\left(\mathrm{D}_{\mathrm{O}}^{-1} \mathrm{A}\right)^{k}+\theta_{k, 2}\left(\mathrm{D}_{\mathrm{I}}^{-1} \mathrm{A}^{T}\right)^{k}\right) x$$

总结：谱图卷积和扩散卷积的不同：谱图卷积的邻接矩阵揭示中心节点和它直接邻近的节点更相关。而扩散卷积揭示空间依赖是随机且动态的。扩散卷积比谱图卷积更复杂。扩散卷积可以适用在任何交通网络上，而谱图卷积只能用在对称的图上，即无向图中。

有些工作在使用SGC和DGC使用以下tricks

• 使用SGC时，引入attention机制
  S表示图信号矩阵，使用切比雪夫多项式计算图卷积时，对S求attention，计算节点之间的影响程度。

$$\Theta *_{\mathcal{G}} x \approx \sum_{k=0}^{K-1} \theta_{k}\left(T_{k}(\tilde{\mathbf{L}}) \odot \mathbf{S}\right) x$$ $$\mathbf{S} = W_{1} \odot \rho\left(\left(X W_{2}\right) W_{3}(W_{4} X)^{T}+b\right) \in \mathbb{R}^{N \times N}$$

• 直接使用邻接矩阵，FFR表示道路特征

  $$\Theta *_{\mathcal{G}} x=\left(W \odot \tilde{\mathbf{A}}^{\mathrm{K}} \odot \mathcal{F} \mathcal{F} \mathcal{R}\right) x$$

• 在邻接矩阵中引入地理位置信息

  $$\mathbf{S}=\mathbf{A} \odot \omega$$$$Y=\rho\left(\tilde{\mathbf{Q}}^{-\frac{1}{2}} \tilde{\mathbf{S}} \tilde{\mathbf{Q}}^{-\frac{1}{2}} X W\right)$$

5.2. RNN

交通任务预测中很多都是时间序列数据，适用RNN来捕获时间相关性。这里包括三类：RNN,LSTM,GRU

• RNN：输入层，隐藏层，输出层
• LSTM：为了解决RNN的梯度消失和梯度爆炸问题，引入输入门，遗忘门，输出门。
• GRU：LSTM结构复杂，参数更多，用更简单的GRU来代替，只有2个门：重置门

在交通预测领域中，很少用RNN，大部分都是用GRU，少数用LSTM。在用GRU或LSTM时，有很多小tricks，例如attention，门控机制，残差机制。
在使用RNN所用到的tricks

• 在RNN中引入空间信息 $$\mathbf{H}_{t} = R N N\left(\left[\mathbf{H}_{t-1}, \mathbf{X}_{t}\right] \odot S\right)$$
• 引入外部因素 $$\mathbf{H}_{t}=G R U\left(\left[\mathbf{H}_{t-1}, \mathbf{X}_{t}\right], \mathbf{E}_{t}\right)+\mathbf{H}_{t-1} W$$
• 使用空洞RNN $$\mathbf{H}_{t}=G R U\left(\mathbf{H}_{t-s}, \mathbf{X}_{t}\right)$$
• RNN和图卷积结合 $$\begin{aligned} r_{t} &=\sigma\left(\left[\mathbf{H}_{t-1}, \mathbf{X}_{t}\right] *_{\mathcal{G}} W_{r}+b_{r}\right) \\ u_{t} &=\boldsymbol{\sigma}\left(\left[\mathbf{H}_{t-1}, \mathbf{X}_{t}\right] *_{\mathcal{G}} W_{u}+b_{u}\right) \\ \tilde{\mathbf{H}}_{t} &=\tanh \left(r_{t} \odot\left[\mathbf{H}_{t-1}, \mathbf{X}_{t}\right] *_{\mathcal{G}} W_{h}+b_{h}\right) \\ \mathbf{H}_{t} &=u_{t} \odot \mathbf{H}_{t-1}+\left(1-u_{t}\right) \odot \tilde{\mathbf{H}}_{t} \end{aligned}$$

5.3. TCN

虽然RNN可以捕获时间的相关性，但是其不能并行计算，耗时。与之对比，1D卷积运行更快，同样也可以捕获时间相关性。然后1D卷积与RNN相比应用更少，由于1D卷积缺少长期建模的memory机制。后来提出空洞卷积，在长期时间建模上，比RNN效果更好。之后，TCN被广泛应用在时间建模上。

在使用TCN时，有一些小traick

• 堆叠不同的TCN层，每层使用不同的dilation rate

  $$\mathcal{Y}^{(l+1)}=\sigma\left(\Theta^{l} *_{\mathcal{T} \mathrm{d}^{l}} \mathcal{Y}^{(l)}\right)$$

• 残差，原始输入+TCN的输出

  $$\mathcal{Y}^{(l+1)}=\mathcal{Y}^{(l)}+\boldsymbol{\operatorname { R e }} \boldsymbol{L} \boldsymbol{U}\left(\Theta_{1}^{l} *_{\mathcal{T}^{\mathrm{d}}}\left(\boldsymbol{\operatorname { R e }} \boldsymbol{L} \boldsymbol{U}\left(\Theta_{0}^{l} *_{\mathcal{T}^{\mathrm{d}}} \mathcal{Y}^{(l)}\right)\right)\right)$$

• 使用门控机制

  $$\mathcal{Y}=\rho\left(\Theta_{1} *_{\mathcal{T}^{\mathrm{d}}} \mathcal{X}+b_{1}\right) \odot \sigma\left(\Theta_{2} *_{\mathcal{T}^{\mathrm{d}}} \mathcal{X}+b_{2}\right)$$

5.4. Seq2Seq

原始的Seq2Seq模型为对输入进行建模，得到一个隐变量$C$,然后将$C$输入到解码器中，进行预测。

对Seq2Seq的改进主要有2点：

• 改变隐变量C
  原先输入到decoder的C是固定的，对decoder中所有的时间步来说都一样，然后输入中的值对不同的输出影响程度不同，这里引入attention机制，动态改变C

  $$\begin{array}{l} \mathbf{H}_{i}=\operatorname{Encoder}\left(\mathbf{X}_{i}, \mathbf{H}_{i-1}\right) \\ \mathbf{C}_{j}=\sum_{i=1}^{\mathbf{P}}\left(\theta_{j i} \mathbf{H}_{i}\right), \mathbf{S}_{0}=\mathbf{H}_{\mathbf{P}} \\ \mathbf{S}_{j}=\operatorname{Decoder}\left(\mathbf{C}_{j}, \mathbf{Y}_{j-1}, \mathbf{S}_{j-1}\right) \\ \mathbf{Y}_{j}=\mathbf{S}_{j} W \end{array}$$

• 采样
  在decoder在训练阶段和测试阶段的输入是不同的。在训练阶段，decoder的不同时间步输入的真实的label，而在测试阶段，因为不知道label，输入的是上一个时间步预测的结果，这样可能会造成错误累积的问题。为了解决这个问题，可以在训练阶段进行采样，即并不总是输入真实的label，以$\epsilon_{j}$输入真实babel，以$1-\epsilon_{j}$输入上个时间步的预测结果。

交通领域中的多步预测通常采用Seq2Seq架构。Seq2Seq中的encoder和decoder架构通常采用RNN，但是也不一定相同。

5.5. GAN

这一模块看的论文较少，以后补充

6. 挑战

尽管交通领域有很多研究方向，但它们都有一些共同的挑战，如下所示，主要分为三类：空间依赖，时间依赖，外部因素。

6.1. 空间依赖

在一个双向的道路中，R1只受R2的影响，R3对R1的影响较小。如果采用网格的形式，R3和R2对R1的影响相同，这不符合实际。如果采用图的形式，R2对R1的影响较大，R3对R1的影响较小，符合实际。

交通网络中空间依赖十分复杂，可以分成三类：空间局部性，多元关系，全局连通性。

1. 空间局部性
   空间局部性表示邻近区域比较远的区域更相关。K阶局部谱图卷积SGCN可以聚合0~K-1跳的邻居信息。还有一些其他工作可以捕获空间局部相关性。比如动态计算邻接矩阵
2. 多元关系
   目标区域也可能与距离较远的区域相关。例如功能相似的区域，交通连通的区域。根据这些不同的相似性来创建不同的图。
3. 全局连通性
   以上2点更关注网络部分，而忽略了整体的结构。全局连通性表示不同区域的交通情况在整个网络上互相影响。使用扩散卷积、pooling层、self-adaptive邻接矩阵可以捕获到这种全局连通性。

6.2. 时间依赖

使用RNN或TCN来捕获时间依赖

1. 多粒度
   时间有不同的周期性，例如recent，daily，weekly。
2. 不同的权重
   历史信息对目标时间段的影响权重不同。使用Attention机制计算权重分数。

6.3. 时空依赖

以上对时间和空间依赖分别建模，如果对时空依赖同时建模，预测效果可能会更好。例如STSGCN

6.4. 外部因素

天气（雨/温度/空气质量），时间（节假日/周几/几点），特殊时间，POI等信息都会影响交通预测。
对于外部因素的处理通常有2种方法：

1. 和其他因素拼接，输入到模型中
2. 设计外部因素处理模块，对外部因素单独处理。通常是2个FCN，第一个FCN提取重要信息，第二个FCN从低维特征映射到高维特征

7. 未来方向

1. 在司机行为分类，车辆/人们轨迹预测，交通事故预测使用图模型。
2. 大多使用SGCN和DGCN，很少使用GAT,GAE,RNN+GCN，可以使用以上模型解决交通问题
3. 交通问题大多是回归问题，很少有分类问题，可以使用图模型研究分类问题
4. 现有模型对外部因素处理比较简单，可以设计更复杂的模型捕获外部因素信息。