Title: Graph WaveNet for Deep Spatial-Temporal Graph Modeling

时空图建模是分析系统中组件的空间关系和时间趋势的一项重要任务。假设实体之间的底层关系是预先确定的，现有方法大多捕获对固定图结构的空间依赖性。但是，显式的图结构（关系）不一定反映真正的依赖关系，并且由于数据中的不完整连接，可能会丢失真正的关系。此外，现有方法无法有效捕捉时间趋势，因为这些方法中使用的 RNN 或 CNN 无法捕捉远程时间序列。为了克服这些限制，我们在本文中提出了一种新颖的图神经网络架构 Graph WaveNet，用于时空图建模。通过开发一种新颖的自适应依赖矩阵并通过节点嵌入来学习它，我们的模型可以精确地捕获数据中隐藏的空间依赖关系。使用堆叠扩张的一维卷积组件，其感受野随着层数的增加呈指数增长，Graph WaveNet 能够处理非常长的序列。这两个组件无缝集成在一个统一的框架中，整个框架以端到端的方式学习。在两个公共交通网络数据集 METR-LA 和 PEMS-BAY 上的实验结果证明了我们算法的优越性能。

引言

随着图神经网络的发展，时空图建模受到越来越多的关注。 它旨在通过假设连接节点之间的相互依赖来对动态节点级输入进行建模，如图 1 所示。时空图建模在解决交通速度预测等复杂系统问题方面具有广泛的应用， 出租车需求预测、人类行为识别和驾驶员机动预期。 举一个具体的例子，在交通速度预测中，城市道路上的速度传感器形成一个图，其中边缘权重由两个节点的欧几里德距离来判断。 由于一条道路上的交通拥堵会导致其进入道路的车速降低，因此在对车速时间序列数据进行建模时，很自然地将交通系统的底层图结构视为节点之间相互依赖关系的在每条路上先验知识。

时空图建模背后的一个基本假设是，节点的未来信息取决于其历史信息以及其邻居的历史信息。 因此，如何同时捕获空间和时间依赖性成为主要挑战。 最近对时空图建模的研究主要遵循两个方向。 他们要么将图卷积网络 (GCN) 集成到递归神经网络 (RNN) 或卷积神经网络 (CNN) 。 虽然已经展示了将数据的图结构引入模型的有效性，但这些方法面临两个主要缺点。

首先，这些研究假设数据的图结构反映了节点之间真正的依赖关系。 但是，也存在连接不包含两个节点之间的相互依赖关系，以及两个节点之间存在相互依赖关系但缺少连接的情况。 为了给每种情况举个例子，让我们考虑一个推荐系统。 在第一种情况下，两个用户有联系，但他们可能对产品有不同的偏好。 在第二种情况下，两个用户可能有相似的偏好，但他们没有联系在一起。 张等人使用注意力机制通过调整两个连接节点之间的依赖权重来解决第一种情况，但他们没有考虑第二种情况。

其次，目前对时空图建模的研究对于学习时间依赖性是无效的。 基于 RNN 的方法在捕获长距离序列时遇到耗时的迭代传播和梯度爆炸/消失。 相反，基于 CNN 的方法具有并行计算、梯度稳定和内存要求低的优势。 然而，这些工作需要使用许多层来捕获非常长的序列，因为它们采用标准的 1D 卷积，其感受野大小随着隐藏层数量的增加而线性增长。

在这项工作中，我们提出了一种名为 Graph WaveNet 的基于 CNN 的方法，它解决了我们前面提到的两个缺点。 我们提出了一个图卷积层，其中可以通过端到端的监督训练从数据中学习自适应邻接矩阵。 通过这种方式，自适应邻接矩阵保留了隐藏的空间依赖关系。 受 WaveNet 的启发，我们采用堆叠扩张的随机卷积来捕获时间依赖性。 堆叠扩张的随机卷积网络的感受野大小随着隐藏层数量的增加呈指数增长。 在堆叠扩张的随机卷积的支持下，Graph WaveNet 能够有效地处理具有远程时间序列的时空图数据。 这项工作的主要贡献如下：

• 我们构建了一个自适应邻接矩阵，它保留了隐藏的空间依赖关系。 我们提出的自适应邻接矩阵能够在没有任何先验知识指导的情况下自动从数据中发现看不见的图结构。 实验验证了我们的方法在已知存在但未提供空间依赖关系时改进了结果。
• 我们提出了一个有效且高效的框架来同时捕获时空依赖性。 核心思想是将我们提出的图卷积与扩张的随机卷积组装在一起，每个图卷积层处理由扩张的随机卷积层在不同粒度级别提取的节点信息的空间依赖性。
• 我们在交通数据集上评估我们提出的模型，并以低计算成本获得最先进的结果。 Graph WaveNet 的源代码可从 https://github.com/nnzhan/Graph-WaveNet 公开获得。

相关工作

图卷积网络

图卷积网络是学习图结构数据的构建块。它们广泛应用于节点嵌入、节点分类、图分类、链接预测和节点聚类。图卷积网络有两个主流，基于谱的方法和基于空间的方法。基于谱的方法使用图谱滤波器平滑节点的输入信号。基于空间的方法通过聚合来自邻域的特征信息来提取节点的高级表示。在这些方法中，邻接矩阵被认为是先验知识，并且在整个训练过程中都是固定的。蒙蒂等人通过高斯核学习节点邻居的权重。维利科维奇等人通过注意力机制更新了节点邻居的权重。刘等人提出了一个自适应路径层来探索节点邻域的广度和深度。尽管这些方法假设每个邻居对中心节点的贡献不同并且需要学习，但它们仍然依赖于预定义的图结构。李等人采用距离度量来自适应地学习图的邻接矩阵来解决图分类问题。这个生成的邻接矩阵以节点的输入为条件。由于时空图的输入是动态的，因此它们的方法对于时空图建模是不稳定的。

时空图网络

大多数时空图网络遵循两个方向，即基于 RNN 和基于 CNN 的方法。早期基于 RNN 的方法之一是通过过滤输入和使用图卷积传递给循环单元的隐藏状态来捕获时空依赖性。后来的工作采用了不同的策略，例如扩散卷积和注意力机制来提高模型性能。另一项并行工作使用节点级 RNN 和边缘级 RNN 来处理时间信息的不同方面。基于 RNN 的方法的主要缺点是它对于长序列变得低效，并且当它们与图卷积网络结合时，它的梯度更容易爆炸。基于 CNN 的方法将图卷积与标准一维卷积相结合。虽然计算效率很高，但这两种方法必须堆叠许多层或使用全局池化来扩展神经网络模型的感受野。

Methodology

在本节中，我们首先给出本文要解决的问题的数学定义。 接下来，我们描述了我们框架的两个构建块，图卷积层（GCN）和时间卷积层（TCN）。 他们一起工作以捕捉时空依赖性。 最后，我们概述了我们框架的架构。

问题定义

图由 $G = (V, E)$ 表示，其中 $V$ 是节点集，$E$ 是边集。 从图导出的邻接矩阵用 $A \in \mathbb{R}^{N\times N}$ 表示。 如果 $v_i, v_j \in V$ 和 $(vi, vj) \in E$，则 $A_{ij}$ 为 1，否则为 0。 在每个时间步 $t$，图 $G$ 有一个动态特征矩阵 $X^{(t)} \in \mathbb{R}^{N\times D}$。 在本文中，特征矩阵与图信号互换使用。 给定一个图 $G$ 和它的历史 $S$ 步图信号，我们的问题是学习一个函数 $f$，它能够预测它的下一个 $T$ 步图信号。 映射关系表示如下

$$\tag{1} [X^{(t-S):t},G] \overset{f}{\rightarrow}X^{(t+1):(t+T)}$$

其中，$X^{(t-S):t} \in \mathbb{R}^{N\times D \times S}$ 以及 $X^{(t+1):(t+T)} \in \mathbb{R}^{N\times D \times T}$ 。

图卷积层

考虑到节点的结构信息，图卷积是提取节点特征的必要操作。 基普夫等人提出了切比雪夫光谱滤波器的第一个近似值。 从基于空间的角度来看，它通过聚合和转换其邻域信息来平滑节点的信号。 他们的方法的优点是它是一个组合层，它的过滤器是在空间中定位的，并且它支持多维输入。 令 $\tilde{A} \in \mathbb{R}^{N \times N}$ 表示具有自环的归一化邻接矩阵，$X \in \mathbb{R}^{N\times D}$ 表示输入信号，$Z \in \mathbb{R}^{N\times M}$ 表示输出，$XW \in \mathbb{R}^{N\times M}$ 表示模型参数矩阵，图卷积层定义为

$$\tag{2} Z=\tilde{A}XW$$

李等人提出了一种扩散卷积层，该层在时空建模中被证明是有效的。 他们用 $K$ 个有限步对图信号的扩散过程进行了建模。 我们将其扩散卷积层推广为等式 2 的形式，结果为：

$$\tag{3} Z=\sum_{k=0}^{K}P^{k}XW_k$$

其中 }P^{k} 表示转移矩阵的幂级数。 在无向图的情况下，$P = A/rowsum(A)$。 在有向图的情况下，扩散过程有两个方向，前向和后向，其中前向转移矩阵 $P_f = A/rowsum(A)$ 和后向转移矩阵 $P_b = A^{\intercal}/rowsum(A^{\intercal})$。 有了前向和后向转换矩阵，扩散图卷积层写为

$$\tag{4} Z=\sum_{k=0}^{K}P_f^{k}XW_{k1}+P_b^{k}XW_{k2}$$

自适应邻接矩阵：在我们的工作中，我们提出了一个自适应邻接矩阵 $\tilde{A}_{adp}$。 这种自适应邻接矩阵不需要任何先验知识，并且通过随机梯度下降端到端学习。 在这样做的过程中，我们让模型自己发现隐藏的空间依赖性。 我们通过使用可学习参数 $E_1, E_2 \in \mathbb{R}^{N\times c}$ 随机初始化两个节点嵌入字典来实现这一点。 我们提出自适应邻接矩阵为

$$\tag{5} \tilde{A}_{adp} = \textup{SoftMax}(\textup{ReLU}(E_1E_2^{\intercal}))$$

我们将 $E_1$ 命名为源节点嵌入，$E_2$ 命名为目标节点嵌入。 通过将 $E_1$ 和 $E_2$ 相乘，我们得出源节点和目标节点之间的空间依赖权重。 我们使用 $\textup{ReLU}$ 激活函数来消除弱连接。 $\textup{SoftMax}$ 函数用于对自适应邻接矩阵进行归一化。 因此，归一化的自适应邻接矩阵可以被认为是隐藏扩散过程的转移矩阵。 通过结合预定义的空间依赖和自学习的隐藏图依赖，我们提出了以下图卷积层

$$\tag{6} Z=\sum_{k=0}^{K}P_f^{k}XW_{k1}+P_b^{k}XW_{k2} +\tilde{A}_{adp}XW_{k3}$$

当图结构不可用时，我们建议单独使用自适应邻接矩阵来捕获隐藏的空间依赖关系，即

$$\tag{7} Z=\sum_{k=0}^{K}\tilde{A}_{adp}XW_{k}$$

值得注意的是，我们的图卷积属于基于空间的方法。 尽管我们使用可互换的图信号与节点特征矩阵来保持一致性，但我们在等式 7 中的图卷积确实被解释为聚合来自不同或邻域的变换特征信息。

时序卷积层

我们采用扩张因果卷积作为我们的时间卷积层 (TCN) 来捕捉节点的时间趋势。 扩张的因果卷积网络通过增加层深度来允许指数级大的感受野。 与基于 RNN 的方法相反，扩张的随机卷积网络能够以非递归方式正确处理远程序列，这有助于并行计算并缓解梯度爆炸问题。 扩张的因果卷积通过向输入填充零来保留时间因果顺序，以便对当前时间步长的预测只涉及历史信息。 作为标准一维卷积的一个特例，扩张因果卷积操作通过以一定的步长跳过值来滑动输入，如图 2 所示。在数学上，给定一维序列输入 $x \in \mathbb{R}^T$ 和一个滤波器 f \in \mathb{R}^K， $x$ 与 $f$ 在步骤 $t$ 的扩张因果卷积运算表示为

$$\tag{8} x\star f(t) = \sum_{s=0}^{K-1}f(s)x(t-d \times s)$$

其中 $d$ 是控制跳跃距离的膨胀因子。 通过以递增的顺序堆叠具有膨胀因子的膨胀因果卷积层，模型的感受野呈指数增长。 它使扩张的因果卷积网络能够以更少的层捕获更长的序列，从而节省计算资源。

门控 TCN：门控机制在循环神经网络中至关重要。 它们已被证明在控制时间卷积网络层的信息流方面非常强大。 一个简单的门控 TCN 只包含一个输出门。 给定输入 $X \in \mathbb{R}^{N\times D\times S}$，它采用以下形式

$$\tag{9} h = g(\Theta_1 \star X+b)\odot \sigma(\Theta_2 \star X+c)$$

其中 $\Theta_1$、$\Theta_2$、$b$ 和 $c$ 是模型参数，是元素乘积，$g(\cdot)$ 是输出的激活函数，$c(\cdot)$ 是确定传递给下一个信息的比率的 sigmoid 函数 层。 我们在模型中采用门控 TCN 来学习复杂的时间依赖性。 尽管我们凭经验将正切双曲函数设置为激活函数 $g(\cdot)$，但其他形式的门控 TCN 也可以很容易地拟合到我们的框架中，例如类似 LSTM 的门控 TCN。

Graph WaveNet 框架

我们在图 3 中展示了 Graph WaveNet 的框架。它由堆叠的时空层和一个输出层组成。 时空层由图卷积层（GCN）和门控时间卷积层（Gated TCN）构成，门控时间卷积层由两个平行的时间卷积层（TCN-a 和 TCN-b）组成。 通过堆叠多个时空层，Graph WaveNet 能够处理不同时间级别的空间依赖关系。 例如，在底层，GCN 接收短期时间信息，而在顶层 GCN 处理长期时间信息。 实际上，图卷积层的输入 $h$ 是大小为 $[N,C,L]$ 的三维张量，其中 $N$ 是节点数，$C$ 是隐藏维度，$L$ 是序列长度。 我们将图卷积层应用于 $h[:, :, i] \in \mathbb{R}^{N\times C}$ 中的每一个。

我们选择使用平均绝对误差 (MAE) 作为 Graph WaveNet 的训练目标，其定义为

$$\tag{10} L(\hat{X}^{(t+1):(t+T)};\Theta) = \frac{1}{TND}\sum_{i=0}^{i=T}\sum_{j=0}^{j=N}\sum_{k=0}^{k=N}|\hat{X}_{jk}^{(t+1)}-X_{jk}^{(t+1)}|$$

与之前的作品不同，我们的 Graph WaveNet 整体输出 $\hat{X}^{(t+1):(t+T)}$，而不是通过 $T$ 个步骤递归地生成 $\hat{X}^{(t)}$。 它解决了训练和测试之间的不一致问题，因为模型在训练期间学会了对一个步骤进行预测，并期望在推理过程中产生对多个步骤的预测。 为了实现这一点，我们人为地设计了 Graph WaveNet 的感受野大小等于输入的序列长度，以便在最后一个时空层中，输出的时间维度恰好等于 1。 之后，我们将最后一层的输出通道数设置为步长 T 的因子，以获得我们想要的输出维度。

论文原文