Title: Adaptive Graph Convolutional Recurrent Network for Traffic Forecasting

在相关的时间序列数据中建模复杂的空间和时间相关性对于理解交通动态和预测不断发展的交通系统的未来状态是必不可少的。最近的工作重点是设计复杂的图神经网络架构，以借助预定义的图来捕获共享模式。在本文中，我们认为学习特定于节点的模式对于流量预测至关重要，而预定义的图是可以避免的。为此，我们提出了两个自适应模块，用于增强具有新功能的图卷积网络 (GCN)：1) 节点自适应参数学习 (NAPL) 模块，用于捕获特定于节点的模式； 2）一个数据自适应图生成（DAGG）模块，用于自动推断不同流量系列之间的相互依赖关系。我们进一步提出了一种自适应图卷积循环网络（AGCRN），以基于两个模块和循环网络自动捕获交通序列中细粒度的空间和时间相关性。我们在两个真实世界交通数据集上的实验表明，在没有关于空间连接的预定义图的情况下，AGCRN 的性能明显优于最先进的技术。

引言

快速的城市化带来了城市人口的增长，并带来了重大的流动性和可持续性挑战。 在这些挑战中，智能交通系统 (ITS) 已成为一个活跃的研究领域，因为它具有促进系统效率和决策制定的潜力。 作为实现 ITS 的重要一步，交通预测旨在预测城市交通系统的未来状态（例如交通流量和速度，以及乘客需求）。 它在交通调度和管理中起着至关重要的作用，近年来引起了机器学习研究界的极大关注。

由于从不同来源（例如，不同的环路检测器/交通流量和车速预测的交叉路口，以及乘客需求预测的各个站点/区域。传统方法简单地部署时间序列模型，例如自回归综合移动平均 (ARIMA) 和向量自回归 (VAR)，用于交通预测。它们无法捕捉大规模交通数据之间的非线性相关性和复杂的时空模式。最近，研究人员转向基于深度学习的方法，并专注于设计新的神经网络架构，以捕捉所有交通系列共享的显着时空模式。他们通常使用循环神经网络（例如，长短期记忆和门控循环单元）或时间卷积模块对时间依赖性进行建模。关于空间相关性，他们通常使用基于 GCN 的方法来模拟非结构化交通序列及其相互依赖关系。

虽然最近基于深度学习的方法取得了可喜的成果，但它们偏向于所有流量序列中的突出和共享模式——共享参数空间使得当前方法在准确捕获细粒度数据源特定模式方面表现不佳。 事实上，流量序列呈现出多样化的模式（如图 1 所示），由于跨各种数据源的不同属性，它们可能看起来相似、不同甚至矛盾。 此外，现有的基于 GCN 的方法需要通过相似性或距离测量预先定义互连图以捕获空间相关性。 这进一步需要大量的领域知识并且对图形质量很敏感。 以这种方式生成的图表通常是直观的、不完整的，并且不直接特定于预测任务； 它们可能包含偏见，并且在没有适当知识的情况下无法适应领域。

我们没有设计更复杂的网络架构，而是通过修改当前方法（即 GCN）的基本构建块来分别解决上述问题，提出了两种简洁而有效的机制。具体来说，我们建议使用两个用于交通预测任务的自适应模块来增强 GCN：1）一个节点自适应参数学习（NAPL）模块，用于学习每个交通系列的节点特定模式——NAPL 分解传统 GCN 中的参数并生成节点特定根据节点嵌入，来自所有节点共享的权重池和偏差池的参数； 2) 数据自适应图生成 (DAGG) 模块，用于从数据中推断节点嵌入（属性）并在训练期间生成图。 NAPL 和 DAGG 是独立的，可以单独或联合地适应现有的基于 GCN 的流量预测模型。模块中的所有参数都可以通过端到端的方式轻松学习。此外，我们将 NAPL 和 DAGG 与循环网络相结合，提出了一个统一的流量预测模型——自适应图卷积循环网络（AGCRN）。 AGCRN 可以捕获流量序列中细粒度的节点特定空间和时间相关性，并将修改后的 GCN 中的节点嵌入与 DAGG 中的嵌入统一起来。因此，训练 AGCRN 可以为每个交通序列源（例如，交通速度/流量的道路、乘客需求的车站/区域）生成一个有意义的节点表示向量。学习到的节点表示包含有关道路/区域的有价值信息，并且可以潜在地应用于其他任务。

我们在两个真实世界的数据集上评估 AGCRN 的多步交通预测任务，并将其与几个代表性的交通预测模型进行比较。 实验结果表明，AGCRN 以显着的优势优于最先进的技术。 我们还进行消融研究并证明 NAPL 和 DAGG 的有效性。

相关工作

相关时间序列预测 交通预测属于相关时间序列分析 (或多变量时间序列分析)，已经研究了几十年。 近年来，深度学习凭借其在复杂函数建模和自动从数据中学习相关性的卓越能力，主导了相关时间序列预测。 大多数此类研究依赖 LSTM 或 GRU 对时间序列数据中的时间动态进行建模。 一些努力采用时间卷积网络来使模型能够以更少的时间处理非常长的序列。 然而，这些研究没有明确地模拟不同时间序列之间的相互依赖关系。 最近的一项工作使用 transformers 进行相关时间序列预测。 由于大量可训练参数，此类工作通常需要大量训练样本。

基于GCN的交通预测 与一般的相关时间序列预测不同，交通预测研究除了时间相关性外，还更加关注不同来源（空间/区域/传感器）的交通序列之间的空间相关性。这些研究的一部分基于交通序列是从网格划分的城市生成的假设，利用 CNN 来捕获附近区域之间的空间相关性，但这并不总是成立。为了开发更通用和广泛使用的交通预测方法，研究人员近年来正在转向基于 GCN 的模型。这些努力在图上制定了交通预测问题，并利用中开发的光谱 GCN 来捕捉不同交通系列之间的显着空间交互. DCRNN将流量的空间依赖性重新表述为扩散过程，并将先前的 GCN 扩展到有向图。在 DCRNN 之后，Graph Wavenet 将 GCN 与扩张的因果卷积网络相结合，以节省处理长序列的计算成本，并提出了一种自适应的自适应邻接矩阵作为预定义邻接矩阵的补充，以捕获空间相关性。最近的工作，如 ASTGCN、STSGCN 和 GMAN 进一步添加了更复杂的 GCN 空间和时间注意机制，以捕获动态空间和时间相关性。然而，这些方法只能捕获所有交通序列之间的共享模式，并且仍然依赖于预定义的空间连接图

Graph Convolutional Networks GCN 是一种针对图结构化数据泛化的特殊 CNN，广泛用于节点分类、链接预测和图分类。 这些工作中的大多数都集中在图表示上，它通过基于给定的图结构整合来自节点本地邻居的特征来学习节点嵌入。 为了更准确地操纵邻居的信息，GAT 学习使用多头自注意力机制学习的注意力分数来加权来自不同邻居的信息。 DIFFPOOL 通过节点聚类增强了 GCN，以生成分层图表示。 与这些处理静态特征的工作不同，我们的工作处理动态演变的流，并且在没有给定图形结构的情况下在空间和时间维度上运行。

Methodology

问题定义

我们针对多步流量预测问题。 考虑包含 $N$ 个相关单变量时间序列的大量交通序列，表示为 $X=\{X_{:,0},X_{:,1},...,X_{:,t},...\}$，其中 $X_{:,t} = \{x_{1,t},x_{2,t},...,x_{i,t},...,x_{N,t}\}^{\intercal}\in \mathbb{R}^{N\times1}$ 是 $N$ 个源在时间步 $t$ 的记录，我们的目标是根据观察到的历史值来预测相关交通序列的未来值。 在时间序列预测的实践中，我们将问题表述为根据过去的 $T$ 步历史数据找到一个函数 $F$ 来预测接下来的 $\tau$ 步数据：

$$\tag{1} \{X_{:,t+1},X_{:,t+2},...,X_{:,t+\tau}\} = F_{\theta}(X_{:,t},X_{:,t-1},...,X_{:,t-T+1})$$

其中 $\theta$ 表示模型中的所有可学习参数。 为了准确操纵不同交通序列之间的空间相关性，将问题进一步表述在图 $G = (V, E, A)$ 上，其中 $V$ 是一组节点代表交通序列的来源，$|V| = N$，$E$ 是一组边，$A \in \mathbb{R}^{N\times N}$ 是图的相邻矩阵，表示节点或交通序列之间的接近度（例如，交通网络距离或交通序列相似度的函数）。 因此，问题被修改为：

$$\tag{2} \{X_{:,t+1},X_{:,t+2},...,X_{:,t+\tau}\} = F_{\theta}(X_{:,t},X_{:,t-1},...,X_{:,t-T+1}; G)$$

节点自适应参数学习

交通预测的最新工作部署 GCN 来捕获交通序列之间的空间相关性，并遵循在频谱域中提出的计算。 图卷积操作可以通过一阶切比雪夫多项式展开很好地近似，并推广到高维 GCN 为：

$$\tag{3} Z=(I_{N} + D^{-\frac{1}{2}}AD^{-\frac{1}{2}})X\Theta + b$$

其中，$A \in \mathbb{R}^{N\times N}$ 是图的邻接矩阵，$D$ 是度矩阵，$X \in \mathbb{R}^{N\times C}$ 和 $Z \in \mathbb{R}^{N\times F}$ 是GCN层的输入和输出，$\Theta \in \mathbb{R}^{C\times F}$ 和 $b \in \mathbb{R}^{F}$ 分别表示可学习的权重和偏差。从一个节点（例如节点 $i$）的角度来看，GCN 操作可以看作是将节点 $X^i \in \mathbb{R}^{1\times C}$ 的特征转换为 $Z^i \in \mathbb{R}^{1\times F}$，所有节点之间共享 $\Theta$ 和 $b$。虽然共享参数可能有助于在许多问题中学习所有节点之间最突出的模式，并且可以显着减少参数数量，但我们发现它对于交通预测问题不是最优的。除了密切相关的交通序列之间存在密切的空间相关性外，由于时间序列数据的动态性和影响交通的节点的各种因素，不同交通序列之间也存在着不同的模式。一方面，来自两个相邻节点的流量也可能由于其特定属性（例如，PoI、天气）而在某个特定时期呈现不同的模式。另一方面，来自两个不相交节点的流量序列甚至可能显示相反的模式。因此，仅捕获所有节点之间的共享模式不足以进行准确的流量预测，必须为每个节点维护一个唯一的参数空间以学习节点特定的模式。

但是，为每个节点分配参数会导致 $\Theta \in \mathbb{R}^{N\times C\times F}$ ，太大而无法优化，会导致过拟合问题，尤其是当 $N$ 很大时。 为了解决这个问题，我们建议使用节点自适应参数学习模块来增强传统 GCN，该模块从矩阵分解中汲取见解。 NAPL 不是直接学习 $\Theta \in \mathbb{R}^{N\times C\times F}$ ，而是学习两个更小的参数矩阵： 1) 一个节点嵌入矩阵 $E_G \in \mathbb{R}^{N\times d}$ ，其中 $d$ 是嵌入维度，$d \ll N$； 2) 权重池 $W_G \in \mathbb{R}^{d\times C\times F}$。 然后，可以通过 $\Theta = E_G\cdot W_G$ 生成 $\Theta$。 从一个节点（例如节点 $i$）的角度来看，这个过程根据节点嵌入 $E_G^i$ 从一个大型共享权重池 $W_G$ 中为 $i$ 提取参数 $Θ^i$，这可以解释为从发现的一组候选模式中学习节点特定模式 从所有交通系列。 同样的操作也可以用于 $b$。 最后，NAPL 增强型 GCN（即 NAPL-GCN）可以表示为：

$$\tag{4} Z=(I_{N} + D^{-\frac{1}{2}}AD^{-\frac{1}{2}})XE_GW_G + E_Gb_G$$

数据自适应图生成

另一个问题在于现有的基于 GCN 的流量预测模型，它需要一个预定义的相邻矩阵 A 来进行图卷积操作。 现有工作主要利用距离函数或相似度度量来提前计算图。 A的定义主要有两种方法：1）距离函数，根据不同节点之间的地理距离定义图； 2) 相似度函数，通过测量节点属性（例如，PoI 信息）或交通序列本身的相似度来定义节点邻近度。 但是，这些方法非常直观。 预定义的图不能包含关于空间依赖的完整信息，并且与预测任务没有直接关系，这可能会导致相当大的偏差。 此外，这些方法在没有适当知识的情况下无法适应其他领域，从而使现有的基于 GCN 的模型无效。

为了解决这个问题，我们提出了一个数据自适应图生成（DAGG）模块来自动从数据中推断出隐藏的相互依赖关系。 DAGG 模块首先为所有节点随机初始化一个可学习的节点嵌入字典 EA 2 RN×de，其中 EA 的每一行代表一个节点的嵌入，de 表示节点嵌入的维度。 然后，类似于通过节点相似度定义图，我们可以通过乘以 EA 和 EAT 来推断每对节点之间的空间依赖关系：

$$\tag{5} D^{-\frac{1}{2}}AD^{-\frac{1}{2}} = \textup{softmax}(\textup{ReLU}(E_A\cdot E_A^{\intercal}))$$

其中，$\textup{softmax}$函数用于对自适应矩阵进行归一化。 这里，我们不生成 $A$ 并计算拉普拉斯矩阵，而是直接生成 $D^{-\frac{1}{2}}AD^{-\frac{1}{2}}$ 以避免迭代训练过程中不必要的重复计算。 在训练过程中，$E_A$ 会自动更新，以学习不同流量序列之间的隐藏依赖关系，并获得图卷积的自适应矩阵。 DAGG 模块更简单，学习的 $E_A$ 具有更好的解释能力。 最后，DAGG 增强型 GCN 可以表述为：

$$\tag{6} Z=(I_{N} + \textup{softmax}(\textup{ReLU}(E_A\cdot E_A^{\intercal})))X\Theta + b$$

当处理非常大的图（即 N 很大）时，DAGG 可能需要大量的计算成本。 图划分和子图训练方法可以用来解决这个问题。

自适应图卷积循环网络

除了空间相关性，交通预测还涉及复杂的时间相关性。 在这一部分中，我们介绍了一种自适应图卷积循环网络 (AGCRN)，它集成了 NAPL-GCN、DAGG 和门控循环单元 (GRU)，以捕获流量序列中节点特定的空间和时间相关性。 AGCRN 用我们的 NAPL-GCN 替换 GRU 中的 MLP 层，以学习特定于节点的模式。 此外，它使用 DAGG 模块自动发现空间依赖关系。 正式地：

$$\tag{7} \begin{aligned} \tilde{A} &=\textup{softmax}(\textup{ReLU}(EE^{\intercal})) \\ z_t &= \sigma(\tilde{A}[X_{:,t},h_{t-1}]EW_z+Eb_z) \\ r_t &= \sigma(\tilde{A}[X_{:,t},h_{t-1}]EW_r+Eb_r) \\ \tilde{h}_t &= \textup{tanh}(\tilde{A}[X_{:,t},r\odot h_{t-1}]EW_{\tilde{h}}+Eb_{\tilde{h}}) \\ h_t &= z \odot h_{t-1} +(1-z) \odot \tilde{h}_t \end{aligned}$$

其中 $X_{:,t}$ 和 $h_t$ 是时间步 $t$ 的输入和输出，$[\cdot]$ 表示串联操作，$z$ 和 $r$ 分别是重置门和更新门。 $E$、$W_z$、$W_r$、$W_{\tilde{h}}$、$b_z$、$b_r$ 和 $b_{\tilde{h}}$ 是 AGCRN 中的可学习参数。 与 GRU 类似，AGCRN 中的所有参数都可以通过反向传播进行端到端训练。 从等式中可以看出，AGCRN 将所有嵌入矩阵统一为 $E$，而不是在不同的 NAPL-GCN 层和 DAGG 中学习单独的节点嵌入矩阵。 这提供了一个强大的正则化器，以确保所有 GCN 块之间嵌入的节点一致，并为我们的模型提供更好的可解释性。

多步流量预测

为了实现多步流量预测，我们堆叠了几个 AGCRN 层作为编码器，以捕获特定于节点的时空模式，并将输入（即历史数据）表示为 $H \in \mathbb{R}^{N \times d_o}$。 然后，我们可以通过应用线性变换将表示从 $\mathbb{R}^{N \times d_o}$ 投影到 $\mathbb{R}^{N \times \tau}$，直接获得所有节点接下来 $\tau$ 步的流量预测。 在这里，我们不以顺序方式生成输出，因为它会显着增加时间消耗。

我们选择 L1 损失作为我们的训练目标，并一起优化多步预测的损失。 因此，用于多步流量预测的 AGCRN 的损失函数可以表示为：

$$\tag{8} L(W_\theta) = \sum_{i=t+1}^{i=t+\tau}|X_{:,i}-{X}'_{:,i}|$$

其中 $W_\theta$ 表示网络中所有可学习的参数，$X_{:,i}$ 是基本事实，${X}'_{:,i}$ 是时间步 $i$ 的所有节点的预测。 该问题可以通过反向传播和 Adam 优化器来解决。

论文原文