《Multi-Range Attentive Bicomponent Graph Convolutional Network for Traffic Forecasting》

论文题目：用于交通预测的多范围注意力双组分图卷积网络

摘要

  1. 存在的问题：路网复杂的时空依赖性和基本的不确定性
  2. 目前的研究集中解决通过在整个固定加权图中利用图卷积网络（GCN）来建模空间依赖性，但是存在问题：边缘，即成对节点之间的相关性，要复杂得多并且彼此相互作用。

本文的解决方法：本文提出了多范围注意力双组分GCN（MRA-BGCN），这是一种用于交通预测的新型深度学习模型。

  • 首先根据路网距离构建节点图，并根据各种边缘交互模式构建边缘图
  • 然后，我们使用双分量图卷积实现节点和边的交互。
  • 引入了多范围注意力机制来聚合不同邻域范围内的信息，并自动了解不同范围的重要性。

在两个现实世界的道路网络交通数据集METR-LA和PEMSBAY上进行的广泛实验表明，MRA-BGCN达到了最新水平。

介绍

交通预测的任务：根据历史交通数据预测道路网络的未来交通。

存在的挑战：

  1. 不规则的基础道路网络导致交通数据之间的复杂关联。（复杂的时空依赖性）
  2. 由于各种不可预测的交通状况，交通数据固有地不确定。（基本的不确定性）

早期的交通预测：

  • 主要对单个观测节点或少数观测节点采用浅层机器学习，这受到捕获非线性的能力的限制。在交通数据中忽略或几乎没有利用空间依赖性。

CNN、RNN
CNN将模型限制为处理网格结构（例如，图像和视频），并且不考虑由不规则道路网络主导的非欧几里得相关性。

为了解决这个问题，将图卷积网络（GCN）高效地处理非欧氏相关性，并与RNN（Li等人，2018）或CNN（Yu等人，2018）集成以嵌入道路的先验知识 网络并捕获成对节点之间的相关性。

引入GCN的结果不错，但是忽略了两个方面，即存在的两个问题：

  1. 这些方法主要致力于通过在整个固定加权图中利用GCN来对空间依赖性进行建模。 然而，边缘，即成对节点之间的相关性，要复杂得多并且彼此相互作用。

image.png

如图1（a）所示，传感器1和3以及传感器2和3通过道路链接相互关联。 显然，这些相关性随当前交通状况而变化，并且彼此交互。
如图1（b）所示，现有方法根据路网距离构建加权图，并使用GCN来实现节点的交互，而成对节点之间的相关性则由邻接矩阵中的固定标量表示， 忽略了边的复杂性和相互作用。

  1. 这些方法通常使用在给定的邻域范围内（即，𝑘-hops）聚集的信息，而忽略多个范围信息。 但是，不同范围的信息显示出不同的流量属性。 较小的邻域范围表示本地依赖性，而较大的范围倾向于揭示相对较大区域中的总体流量模式。 此外，不同范围内的信息并非在所有情况下都具有同等作用。 例如，由于交通事故，一个节点主要受其最近邻居的影响，在该节点上，模型应引起更多关注，而不是平等地考虑𝑘-hops的所有邻居。

为了解决上面提出的问题，本文提出了一种称为 Multi-Range Attentive Bicomponent GCN（MRA-BGCN） 的深度学习模型，该模型不仅考虑节点相关性，还将边缘视为彼此交互的实体，并利用多个范围信息。见图1（c）

本文的贡献：

  1. 本文提出了MRA-BGCN，它引入了双成分图卷积来显式地建模节点和边的相关性。根据路网距离建立节点向图，同时考虑流连通性和竞争关系两种边界相互作用模式建立边向图。
  2. 本文提出了双成分图卷积的多范围注意机制，它可以聚合不同邻域范围内的信息，并了解不同范围的重要性。
  3. 本文在两个真实的交通数据集(metro - la和PEMS-BAY)上进行了广泛的实验，提出的模型获得了最先进的结果。

相关工作

早期流量预测方法,例如,基于线性回归的方法(Nikovski et al ., 2005),基于卡尔曼滤波的方法(简et al ., 2003),和基于自回归综合移动平均(ARIMA)的方法(里皮et al ., 2013),主要采用浅机器学习单一观测节点或几个节点,由捕捉非线性的能力有限的交通数据和忽视或仅利用空间依赖性。

深度学习的最新进展使得交通预测中复杂的时空依赖性建模成为可能。一些尝试(Ma et al.， 2017;赵等，2017;Zhang et al. 2018)将卷积神经网络(CNNs)和递归神经网络(RNNs)用于流量预测。在这些研究中，CNNs被引入用于处理规则网格结构(如图像和视频)来捕捉空间依赖性，而没有考虑以不规则道路网络为主的非欧氏相关性。

为了解决这个问题，研究人员已经应用图卷积来建模交通预测的非欧氏相关性。Li et al.(2018)提出了扩散卷积递归神经网络(Diffusion Convolutional Recurrent Neural Network, DCRNN)，用扩散卷积算子代替了门控递归单元(GRU)中的全连通层(Chung et al.， 2014)。扩散卷积对给定图及其反图进行图卷积，同时考虑流入和流出的关系。余等。(2018)提出了时空GCN (ST-GCN)，它结合了图卷积和ID卷积。在ST-GCN中，图卷积捕捉空间依赖性，ID卷积在时间轴上捕捉时间依赖性，计算效率比RNNs高得多。

上述基于gcn的方法将路网距离编码为表示空间依赖性的固定加权图。为了进一步建模交通预测中的复杂关联，Wu等人。(2019a)提出用自适应邻接矩阵捕获给定图中看不到的隐藏空间依赖关系。该自适应邻接矩阵是通过计算节点嵌入的相似度来实现的。但是，隐藏的空间依赖关系是通过数据的方式学习的，缺乏领域知识的指导，容易出现过拟合问题。此外，现有的交通预测方法不能很好地模拟边界的相互作用和利用多范围信息。

预备知识

问题定义

交通预测的任务是对路网中N个相关交通传感器的历史交通数据进行预测。

本文定义了$N$相关流量传感器作为加权有向图$G = (V, E，A)$

  • $V$是一组$|V| = N$个节点的集合
  • $E$是一组边缘集合
  • $A \in \mathbb R^{N \times N}$是一个加权邻接矩阵,表示节点的接近性,例如,道路网络任何一对节点之间的距离。
  • $t$时刻在$G$上观测到的交通数据表示为图信号$X^{(t)} \in \mathbb R^{N \times P}$，其中$P$为每个节点的特征维数。

交通预测问题的目标是学习一个函数$f$，在给定$T’$历史图形信号和图形$G$的情况下能够预测$T$个未来图形信号:

image.png

图卷积

GCNs是学习非欧几里得结构数据(即图)的构建块(Wu et al.， 2019b)。它们被广泛应用于节点分类(Kipf和Welling, 2017)、图分类(Ying et al.， 2018)、链路预测(Zhang and Chen, 2018)等领域。

GCN方法分为两类：基于光谱的和基于空间的

图卷积的定义为图$G = (V, E，A)$
image.png
其中xe IRNXP为输入信号，8e RPXF为可学习参数矩阵，A = A + Iw为具有自连接的邻接矩阵，o为A的对角度矩阵，D-1A为归一化邻接矩阵，p为非线性激活函数。

一个图的卷积可以聚合1-hop邻居的信息。通过叠加多个图的卷积层，可以扩展接受邻域范围。

方法

模型概览（MRA-BGCN框架）

image.png

这个框架包含两个部分：

  • 双组分图卷积模块（the bicomponent graph convolution module）
    • 包含了几个节点方面的图卷积层和边方向的图卷积层
    • 可以显式地模拟节点和边的相互作用。多距离注意层。
  • 多范围注意层（the multi-range attention layer）
    • 聚合了不同邻域范围内的信息，并学习了不同范围内的重要性
  • 此外，本文将MRA-BGCN和RNN结合，建立交通预测的时间依赖性模型。

Bicomponent Graph Convolution

在给定图结构的情况下，图卷积是对节点间交互进行建模的一种有效操作。然而，在交通预测中，边缘，即成对节点之间的相关性，要复杂得多，并且相互作用。因此，我们提出了双成分图卷积，它可以显式地模拟节点和边的相互作用。

Chen et al.(2019)提出在模型边缘关联中引入边缘邻接线图。设$G= (V, E, A)$表示节点向图。$GL= (V_L, E_L, A_L)$为对应的线形图，则GL的节点V为E中的有序边，即$V_L= {(i→j);(i,j) \in E}$和$|V|=|E|$。$A_L$是一个非加权邻接矩阵，它编码节点图中的边邻接，定义为:$A_{L,(i-i),(j-k)} =1$，否则为0。

尽管有考虑边邻接的能力，但该线图是一个未加权图，如果目标节点与另一个源节点共享，该线图只考虑两条边的相关。然而，对交通预测中常见的各种边缘相互作用模式进行表征是无效的。如图3所示，我们定义了两种类型的边交互模式来构造沿边图$G_e= (V_e, E_e, A_e)$。注意，$V_e$的每个节点代表$E$的一条边。

image.png

Stream connectivity

流连通性:在一个交通网络中，一个道路连接可能受到其上下游道路连接的影响。如图3(a)所示，(i→j)为(j→k)的上游边，两者之间存在相关性。
直观上，如果关节节点j有大量的邻居(即j的程度较大)，则(i→j)与(j→k)的相关性是不牢固的，因为它容易受到其他邻居的影响。

本文计算A中的流连通性的边权值。使用高斯核函数:

image.png

Competitive relationship

竞争关系:共享同一源节点的道路链路可能会争夺交通资源，形成竞争关系。如图3(b)所示，共享目标节点k的两条边(i→k)和(j→k)由于竞争关系存在关联。与流连接类似，竞争关系的强度与源节点的出格程度有关。例如，如果一条边的源节点有多个输出边，则该边对于流量资源的竞争是健壮的。因此，我们将Ae中竞争关系的边权计算为:
image.png

通过构造的边向图$G_e$，如图2所示，双组分图卷积可以显式地模拟节点和边的相互作用。k-hop双组分图卷积公式为:

image.png

其中8c为参数8的图的卷积运算，Jlis串联操作,X (l - 1)是输入层的l node-wise图卷积,z (l - 1)是输入层edge-wise图卷积的l, M E RIVXEl的关联矩阵编码节点和边之间的联结,定义为:Mi(我)= M,(我)= 1和0。MZC)聚合与每个单条节点连接的边表示，MTx()聚合与每个单条节点连接的节点表示。W是一个可学习的投影矩阵，它将原始节点输入X(0)转换为原始边输入z(0)

Multi-Range Attention

我们提出了双元图卷积的多范围注意机制，以自动学习不同邻域范围的重要性，能够聚合不同邻域的信息范围,而不是给定的范围(例如,邻居在𝑘-hops)。

双成分图卷积模块得到不同邻域范围内的节点表示，x ={x(1)，x(2)， (k)， x() E RIVIXF，其中k为最大跳数(即双成分图卷积模块的层数)，F为每个节点的表示维数。X(E RF表示节点i在l层中的表示，多距离注意层的目标是捕获多个邻域范围的综合表示。为此，首先，一个由我们IRFXF参数化的共享线性变换应用于每一层的每个节点。然后通过计算W与u的相似度来测量各层的注意力系数，其中u IR为嵌入的邻域范围上下文，初始化为随机向量，在训练过程中共同学习。最后，利用SoftMax函数对系数进行归一化处理。多范围注意机制的表述为:

image.png