| 论文题目 | Graph WaveNet for Deep Spatial-Temporal Graph Modeling |
|---|---|
| 作者团队 | Zonghan Wu, Shirui Pan, Guodong Long, Jing Jiang, Chengqi Zhang |
| 机构 | 澳大利亚悉尼科技大学人工智能中心 (UTS) 和 澳大利亚莫纳什大学 |
| 发表会议 | IJCAI 2019 |
| 论文链接 | https://www.ijcai.org/proceedings/2019/0264.pdf |
| 源码地址 | https://github.com/nnzhan/Graph-WaveNet |
| 关键词 | 自适应邻接矩阵, 扩张因果卷积, 图卷积网络(GCN), 时空图, 交通预测 |
摘要
空间-时间图建模是一项重要任务，用于分析系统中各组件的空间关系和时间趋势。现有方法大多在固定图结构上捕获空间依赖关系，假设实体之间的底层关系是预先确定的。然而，显式的图结构（关系）并不一定能反映真实的依赖关系，真正的关系可能因数据中连接的不完整而缺失。此外，现有方法未能有效捕获时间趋势，因为这些方法中使用的 RNN 或 CNN 无法捕获长程时间序列。
为克服这些限制，我们在本文中提出了一种新的图神经网络架构——Graph WaveNet，用于空间-时间图建模。通过开发一种新的自适应依赖矩阵并通过节点嵌入进行学习，我们的模型能够精确捕获数据中的隐藏空间依赖关系。通过堆叠的扩张型一维卷积组件，其感受野随着层数的增加呈指数增长，Graph WaveNet 能够处理非常长的序列。这两个组件在统一的框架中无缝集成，整个框架通过端到端的方式进行学习。
在两个公共交通网络数据集 METR-LA 和 PEMS-BAY 上的实验结果表明，我们的算法具有优越的性能。
Graph WaveNet
- 1 引言
- 2 相关工作
- 2.1 图卷积网络
- 2.2 空间-时间图网络
- 3 方法
- 3.1 问题定义
- 3.2 图卷积层
- 3.3 时间卷积层
- 3.4 Graph WaveNet 框架
- 4 实验
- 4.1 基线
- 4.2 实验设置
- 4.3 实验结果
- 4.3.1 自适应邻接矩阵的效果
- 4.3.2 计算时间
- 5 结论
1 引言
随着图神经网络的发展，空间-时间图建模受到了越来越多的关注。它旨在通过假设连接节点之间的相互依赖关系来对动态节点级输入进行建模，如图 1 所示。
空间-时间图建模在解决复杂系统问题中有广泛应用，如交通速度预测、出租车需求预测、人类行为识别和驾驶员操作预判等。以交通速度预测为例，城市道路上的速度传感器形成一个图，其中边权重由两个节点的欧几里得距离决定。由于某条道路上的交通拥堵可能导致其入口道路上的交通速度降低，因此在对每条道路的交通速度时间序列数据进行建模时，通常将交通系统的图结构视为节点之间相互依赖关系的先验知识。
空间-时间图建模的一个基本假设是，节点的未来信息取决于其历史信息以及其邻居的历史信息。因此，如何同时捕获空间和时间依赖性成为主要挑战。最近的空间-时间图建模研究主要遵循两个方向：将图卷积网络 (GCN) 集成到递归神经网络 (RNN) 或卷积神经网络 (CNN) 中。尽管这些方法在将数据的图结构引入模型中表现出有效性，但它们存在两个主要缺点。
首先，这些研究假设数据的图结构反映了节点之间的真实依赖关系。然而，在某些情况下，连接并不意味着两个节点之间存在依赖关系，而两个节点之间存在依赖关系时却可能缺少连接。例如在推荐系统中，两个用户可能连接在一起，但他们可能对产品有不同的偏好；反之，两个用户可能有相似的偏好，但却没有连接。Zhang 等人使用注意力机制调整连接节点之间的依赖权重来解决第一种情况，但未考虑第二种情况。
其次，目前的空间-时间图建模研究未能有效地学习时间依赖性。基于 RNN 的方法在捕获长序列时由于迭代传播耗时以及梯度爆炸/消失问题而效率低下；相反，基于 CNN 的方法具有并行计算、稳定梯度和低内存需求的优势。然而，这些方法为了捕获较长的序列需要堆叠多层或使用全局池化，因为它们采用的标准一维卷积的感受野随着隐藏层数的增加线性增长。
在本研究中，我们提出了一种基于 CNN 的方法，称为 Graph WaveNet，来解决上述两个缺点。我们提出了一种图卷积层，其中可以通过端到端的监督训练从数据中学习到一个自适应的邻接矩阵。在这种方式下，自适应邻接矩阵可以保留隐藏的空间依赖关系。受 WaveNet 启发，我们采用堆叠的扩张型因果卷积来捕获时间依赖性。堆叠的扩张型因果卷积网络的感受野随着隐藏层数的增加呈指数增长。在扩张型因果卷积的支持下，Graph WaveNet 能够高效地处理具有长序列的空间-时间图数据。本研究的主要贡献如下：
-
我们构建了一个自适应邻接矩阵，保留了隐藏的空间依赖关系。该自适应邻接矩阵能够从数据中自动发现未见的图结构，而无需任何先验知识。实验验证表明，当已知存在空间依赖性但未提供时，我们的方法可以改善结果。
-
我们提出了一个有效的框架来同时捕获空间-时间依赖性。核心思想是将我们提出的图卷积与扩张型因果卷积组合，使每个图卷积层能够在不同粒度级别上处理由扩张型因果卷积层提取的节点信息的空间依赖性。
-
我们在交通数据集上评估了我们提出的模型，并在低计算成本的情况下实现了最先进的结果。
2 相关工作
2.1 图卷积网络
图卷积网络是学习图结构数据的构建模块，广泛应用于节点嵌入、节点分类、图分类、链接预测和节点聚类等领域。图卷积网络主要有两大流派，即基于谱的方法和基于空间的方法。
- 基于谱的方法使用图谱滤波器平滑节点的输入信号。
- 基于空间的方法通过从邻居节点聚合特征信息来提取节点的高级表示。
在这些方法中，邻接矩阵被视为先验知识，并在训练过程中保持不变。
- Monti 等人通过高斯核学习节点邻居的权重。
- Velickovic 等人通过注意力机制更新节点邻居的权重。
- Liu 等人提出了一种自适应路径层来探索节点邻居的广度和深度。
尽管这些方法假设每个邻居对中心节点的贡献是不同的并且需要学习，但它们仍然依赖于预定义的图结构。Li 等人采用距离度量自适应地学习图的邻接矩阵以进行图分类问题。然而，由于空间-时间图的输入是动态的，他们的方法不适合空间-时间图建模。
2.2 空间-时间图网络
大多数空间-时间图网络遵循两大方向，即基于 RNN 和基于 CNN 的方法。
早期的基于 RNN 的方法通过对传递到循环单元的输入和隐藏状态进行图卷积过滤，捕获空间-时间依赖性。后续工作采用了扩散卷积和注意力机制等策略来提高模型性能。另一项平行工作使用节点级和边级的 RNN 处理时间信息的不同方面。
- 基于 RNN 的方法的主要缺点在于它们在处理长序列时效率低下，并且当与图卷积网络结合时，其梯度更易发生爆炸。
- 基于 CNN 的方法将图卷积与标准一维卷积结合。虽然计算效率高，但这些方法为了扩展模型的感受野需要堆叠多层或使用全局池化。
3 方法
在本节中，我们首先给出本文所要解决问题的数学定义。接下来，我们描述框架的两个构建模块，图卷积层（GCN）和时间卷积层（TCN）。它们协同工作，以捕获空间-时间依赖关系。最后，我们概述框架的架构。
3.1 问题定义
一个图可以表示为 G = ( V , E ) G = (V, E) G=(V,E)，其中 V V V是节点集合， E E E是边集合。从图导出的邻接矩阵记为 A ∈ R N × N A \in \mathbb{R}^{N \times N} A∈RN×N 。如果 v i , v j ∈ V v_i, v_j \in V vi,vj∈V 且 ( v i , v j ) ∈ E (v_i, v_j) \in E (vi,vj)∈E ，则 A i j A_{ij} Aij 为1，否则为0。在每个时间步 t t t ，图 G G G具有一个动态特征矩阵 X ( t ) ∈ R N × D X^{(t)} \in \mathbb{R}^{N \times D} X(t)∈RN×D 。在本文中，特征矩阵和图信号可以互换使用。给定图 G G G 及其历史的 S S S 步图信号，我们的问题是学习一个函数 f f f ，该函数能够预测未来 T T T 步的图信号。映射关系表示如下：
[ X ( t − S ) : t , G ] → f X ( t + 1 ) : ( t + T ) , (1) [X^{(t-S):t}, G] \xrightarrow{f} X^{(t+1):(t+T)},\tag{1} [X(t−S):t,G]fX(t+1):(t+T),(1)
其中 X ( t − S ) : t ∈ R N × D × S X^{(t-S):t} \in \mathbb{R}^{N \times D \times S} X(t−S):t∈RN×D×S 且 X ( t + 1 ) : ( t + T ) ∈ R N × D × T X^{(t+1):(t+T)} \in \mathbb{R}^{N \times D \times T} X(t+1):(t+T)∈RN×D×T 。
3.2 图卷积层
图卷积是提取节点特征的重要操作，基于其结构信息。Kipf 等人提出了切比雪夫谱滤波的首次近似。从空间角度来看，它通过聚合并转换邻域信息来平滑节点信号。该方法的优势在于它是一个组合层，其滤波器是局部化的，并支持多维输入。令 A ~ ∈ R N × N \tilde{A} \in \mathbb{R}^{N \times N} A~∈RN×N表示具有自循环的归一化邻接矩阵， X ∈ R N × D X \in \mathbb{R}^{N \times D} X∈RN×D表示输入信号， Z ∈ R N × M Z \in \mathbb{R}^{N \times M} Z∈RN×M表示输出， W ∈ R D × M W \in \mathbb{R}^{D \times M} W∈RD×M表示模型参数矩阵。在Kipf 和 Welling的定义下，图卷积层表示为
Z = A ~ X W 。 (2) Z = \tilde{A}XW。\tag{2} Z=A~XW。(2)
Li 等人提出了扩散卷积层，该层在时空建模中效果显著。他们使用 K K K阶有限步数对图信号的扩散过程建模。我们将其扩散卷积层推广为公式 (2) 的形式，得到：
Z = ∑ k = 0 K P k X W k , (3) Z = \sum_{k=0}^K P^kXW_k,\tag{3} Z=k=0∑KPkXWk,(3)
其中 P k P^k Pk表示转换矩阵的幂级数。在无向图中， P = A / r o w s u m ( A ) P = A / rowsum(A) P=A/rowsum(A)。在有向图中，扩散过程具有两个方向，即前向和后向，前向转换矩阵为 P f = A / r o w s u m ( A ) P_f = A / rowsum(A) Pf=A/rowsum(A)，后向转换矩阵为 P b = A T / r o w s u m ( A T ) P_b = A^T / rowsum(A^T) Pb=AT/rowsum(AT)。带有前向和后向转换矩阵的扩散图卷积层表示为
Z = ∑ k = 0 K P f k X W k 1 + P b k X W k 2 。 (4) Z = \sum_{k=0}^K P_f^k X W_{k1} + P_b^k X W_{k2}。\tag{4} Z=k=0∑KPfkXWk1+PbkXWk2。(4)
自适应邻接矩阵： 在我们的工作中，我们提出了一种自适应邻接矩阵 A ~ a d p \tilde{A}_{adp} A~adp。该自适应邻接矩阵不需要任何先验知识，而是通过随机梯度下降以端到端的方式学习。我们通过随机初始化两个具有可学习参数的节点嵌入字典 E 1 , E 2 ∈ R N × c E_1, E_2 \in \mathbb{R}^{N \times c} E1,E2∈RN×c来实现自适应邻接矩阵，定义如下：
A ~ a d p = S o f t M a x ( R e L U ( E 1 E 2 T ) ) 。 (5) \tilde{A}_{adp} = SoftMax(ReLU(E_1 E_2^T))。\tag{5} A~adp=SoftMax(ReLU(E1E2T))。(5)
我们将 E 1 E_1 E1称为源节点嵌入，将 E 2 E_2 E2称为目标节点嵌入。通过 E 1 E_1 E1和 E 2 E_2 E2的乘积，我们得出源节点和目标节点之间的空间依赖权重。使用ReLU激活函数来消除弱连接，并使用SoftMax函数归一化自适应邻接矩阵。因此，归一化的自适应邻接矩阵可以视为隐藏扩散过程的转换矩阵。通过结合预定义的空间依赖和自学习的隐藏图依赖关系，我们提出以下图卷积层：
Z = ∑ k = 0 K P f k X W k 1 + P b k X W k 2 + A ~ a p t k X W k 3 。 (6) Z = \sum_{k=0}^K P_f^k X W_{k1} + P_b^k X W_{k2} + \tilde{A}_{apt}^k X W_{k3}。\tag{6} Z=k=0∑KPfkXWk1+PbkXWk2+A~aptkXWk3。(6)
当图结构不可用时，我们建议仅使用自适应邻接矩阵来捕获隐藏的空间依赖性，即
Z = ∑ k = 0 K A ~ a p t k X W k 。 (7) Z = \sum_{k=0}^K \tilde{A}_{apt}^k X W_k。\tag{7} Z=k=0∑KA~aptkXWk。(7)
值得注意的是，我们的图卷积属于基于空间的方法。尽管为了一致性，我们使用图信号和节点特征矩阵互换，但公式 (7) 中的图卷积实际上被解释为从不同阶的邻域聚合转换后的特征信息。
3.3 时间卷积层
我们采用扩张型因果卷积作为时间卷积层（TCN），以捕获节点的时间趋势。扩张型因果卷积网络通过增加层深来实现指数级的感受野扩展。与基于RNN的方法相比，扩张型因果卷积网络能够以非递归的方式正确处理长序列，支持并行计算并缓解梯度爆炸问题。扩张型因果卷积通过在输入上填充零来保持时间因果顺序，以确保当前时间步的预测仅涉及历史信息。扩张型因果卷积是标准一维卷积的特例，通过以特定步长跳过输入值来滑动，如图2所示。
图 2：使用卷积核大小为 2 的扩张型因果卷积。通过扩张因子 k k k，每隔 k k k 步选择输入并对选定的输入应用标准的一维卷积。
给定一维序列输入 x ∈ R T x \in \mathbb{R}^T x∈RT和滤波器 f ∈ R K f \in \mathbb{R}^K f∈RK，则在步 t t t上 x x x和 f f f的扩张型因果卷积操作表示为：
x ∗ f ( t ) = ∑ s = 0 K − 1 f ( s ) x ( t − d × s ) , (8) x \ast f(t) = \sum_{s=0}^{K-1} f(s)x(t - d \times s),\tag{8} x∗f(t)=s=0∑K−1f(s)x(t−d×s),(8)
其中 d d d是控制跳跃距离的扩张因子。通过以递增顺序堆叠扩张型因果卷积层，模型的感受野指数级增长，能够以更少的层数捕获更长的序列，从而节省计算资源。
门控 TCN： 门控机制在递归神经网络中至关重要，已被证明能够有效地控制时间卷积网络中的信息流。一个简单的门控 TCN 仅包含一个输出门。给定输入 X ∈ R N × D × S \mathcal{X} \in \mathbb{R}^{N \times D \times S} X∈RN×D×S，其形式如下：
h = g ( Θ 1 ∗ X + b ) ⊙ σ ( Θ 2 ∗ X + c ) , (9) h = g(\Theta_1 \ast \mathcal{X} + b) \odot \sigma(\Theta_2 \ast \mathcal{X} + c),\tag{9} h=g(Θ1∗X+b)⊙σ(Θ2∗X+c),(9)
其中 Θ 1 , Θ 2 , b \Theta_1, \Theta_2, b Θ1,Θ2,b和 c c c是模型参数， ⊙ \odot ⊙是元素级乘积， g ( ⋅ ) g(\cdot) g(⋅)是输出的激活函数， σ ( ⋅ ) \sigma(\cdot) σ(⋅)是确定传递到下一层信息比例的Sigmoid函数。我们在模型中采用门控 TCN 来学习复杂的时间依赖性。
3.4 Graph WaveNet 框架
我们在图 3 中展示了 Graph WaveNet 的框架。
图 3：Graph WaveNet 的框架。它由左侧的 K K K 个时空层和右侧的输出层组成。输入首先通过一个线性层进行转换，然后传递到门控时间卷积模块（Gated TCN），随后是图卷积层（GCN）。每个时空层具有残差连接，并通过跳跃连接与输出层相连。
它包含堆叠的时空层和一个输出层。一个时空层由图卷积层（GCN）和门控时间卷积层（Gated TCN）组成，其中门控时间卷积层包含两个并行的时间卷积层（TCN-a 和 TCN-b）。通过堆叠多个时空层，Graph WaveNet 能够在不同的时间级别处理空间依赖性。例如，在底层时，GCN 接收短期的时间信息，而在顶层时，GCN 处理长期的时间信息。图卷积层的输入在实际中是尺寸为 [ N , C , L ] [N, C, L] [N,C,L] 的三维张量，其中 N N N 是节点数量， C C C 是隐藏维度， L L L 是序列长度。我们对每个 h [ : , : , i ] ∈ R N × C h[:, :, i] \in \mathbb{R}^{N \times C} h[:,:,i]∈RN×C 应用图卷积层。
我们选择使用平均绝对误差（MAE）作为 Graph WaveNet 的训练目标，其定义为
L ( X ^ ( t + 1 ) : ( t + T ) ; Θ ) = 1 T N D ∑ i = 1 T ∑ j = 1 N ∑ k = 1 D ∣ X ^ j k ( t + i ) − X j k ( t + i ) ∣ (10) L(\hat{X}^{(t+1):(t+T)}; \Theta) = \frac{1}{TND} \sum_{i=1}^T \sum_{j=1}^N \sum_{k=1}^D \left| \hat{X}_{jk}^{(t+i)} - X_{jk}^{(t+i)} \right| \tag{10} L(X^(t+1):(t+T);Θ)=TND1i=1∑Tj=1∑Nk=1∑D X^jk(t+i)−Xjk(t+i) (10)
与之前的工作不同，我们的 Graph WaveNet 将 X ^ ( t + 1 ) : ( t + T ) \hat{X}^{(t+1):(t+T)} X^(t+1):(t+T) 作为整体输出，而不是通过 T T T 步递归生成 X ^ ( t ) \hat{X}^{(t)} X^(t)。这样做解决了训练和测试之间不一致的问题，因为模型在训练过程中学习对单步进行预测，而在推理时需要对多步进行预测。为实现这一点，我们人为地设计了 Graph WaveNet 的感受野大小等于输入的序列长度，因此在最后一个时空层中，输出的时间维度恰好等于1。之后，我们将最后一层的输出通道数量设置为步长 T T T 的一个因子，以获得所需的输出维度。
4 实验
我们在两个公开的交通网络数据集 METR-LA 和 PEMS-BAY 上验证了 Graph WaveNet，这些数据集由 Li 等人发布。METR-LA 记录了洛杉矶县高速公路上 207 个传感器四个月的交通速度统计数据。PEMS-BAY 包含湾区 325 个传感器六个月的交通速度信息。我们采用与 Li 等人相同的数据预处理步骤。传感器的读数被聚合成 5 分钟的窗口。节点的邻接矩阵通过具有阈值的高斯核从路网距离构造。对输入数据应用 Z-score 归一化。数据集按时间顺序划分为 70% 用于训练，10% 用于验证和 20% 用于测试。表 1 提供了详细的数据集统计信息。
4.1 基线
我们将 Graph WaveNet 与以下模型进行比较：
- ARIMA：带卡尔曼滤波器的自回归积分滑动平均模型。
- FC-LSTM：具有全连接 LSTM 隐藏单元的循环神经网络。
- WaveNet：用于序列数据的卷积网络架构。
- DCRNN：扩散卷积循环神经网络，将图卷积网络与循环神经网络在编码器-解码器方式中结合。
- GGRU：图门控循环单元网络，在图卷积中使用注意力机制的循环方法。
- STGCN：时空图卷积网络，将图卷积与一维卷积结合。
4.2 实验设置
我们的实验在配备 Intel Core i9-7900X CPU @ 3.30GHz 和 NVIDIA Titan Xp GPU 的计算机环境中进行。为了覆盖输入序列长度，我们使用具有扩张因子序列 1 , 2 , 1 , 2 , 1 , 2 , 1 , 2 1, 2, 1, 2, 1, 2, 1, 2 1,2,1,2,1,2,1,2 的八层 Graph WaveNet。我们使用公式 (4) 作为扩散步长 K = 2 K=2 K=2 的图卷积层。我们随机初始化节点嵌入，均匀分布的大小为 10。我们使用 Adam 优化器训练模型，初始学习率为 0.001，图卷积层输出应用 dropout， p = 0.3 p=0.3 p=0.3。评估指标包括平均绝对误差（MAE）、均方根误差（RMSE）和平均绝对百分比误差（MAPE）。训练和测试中均排除缺失值。
4.3 实验结果
表 2 比较了 Graph WaveNet 和基线模型在 METR-LA 和 PEMS-BAY 数据集上的 15 分钟、30 分钟和 60 分钟预测结果。Graph WaveNet 在两个数据集上获得了优越的结果。
它在性能上显著优于 ARIMA、FC-LSTM 和 WaveNet 等时间模型。与其他时空模型相比，Graph WaveNet 明显超越了之前基于卷积的 STGCN，同时也超过了基于循环的 DCRNN 和 GGRU。在第二最佳模型 GGRU 上，Graph WaveNet 在 15 分钟预测上有小幅改进，但在 60 分钟预测上则有更大提升。我们认为这是因为我们的架构能够在每个时间阶段更有效地检测空间依赖性。GGRU 使用共享参数的循环结构，而 Graph WaveNet 则采用具有不同参数的堆叠时空层的独立 GCN 层，从而可以专注于不同时间输入的范围。
我们绘制了 Graph WaveNet 和 WaveNet 的 60 分钟预测值与真实值在测试数据上的对比图，结果表明 Graph WaveNet 生成的预测比 WaveNet 更稳定。特别是，WaveNet 生成了一个与真实值偏离较大的尖峰，而 Graph WaveNet 的曲线始终保持在真实值的中间。
图 4：在 METR-LA 测试数据的一个快照上，对 WaveNet 和 Graph WaveNet 进行 60 分钟超前预测的预测曲线对比。
4.3.1 自适应邻接矩阵的效果
为了验证自适应邻接矩阵的有效性，我们使用五种不同的邻接矩阵配置对 Graph WaveNet 进行了实验。表 3 显示了 MAE、RMSE 和 MAPE 的平均分数。
我们发现，仅使用自适应模型的 MAE 表现甚至优于仅使用前向模型。当图结构不可用时，Graph WaveNet 仍然可以实现良好性能。前向-后向-自适应模型在三个评价指标上均获得最低分数，表明如果给定图结构信息，添加自适应邻接矩阵可以为模型引入新的有用信息。在图 5 中，我们进一步研究了在 METR-LA 数据集上训练的前向-后向-自适应模型的自适应邻接矩阵。根据图 5a，一些列比其他列具有更多的高值点，例如左框中的列 9 和右框中的列 47。这表明某些节点对大多数节点影响较大，而其他节点影响较小。图 5b 证实了我们的观察。可以看到，节点 9 位于几条主干道交叉口附近，而节点 47 位于单一道路上。
4.3.2 计算时间
我们在 METR-LA 数据集上比较了 Graph WaveNet 与 DCRNN 和 STGCN 的计算成本，见图4。Graph WaveNet 在训练中比 DCRNN 快五倍，但比 STGCN 慢两倍。在推理阶段，我们测量了每个模型在验证数据上的总时间成本。Graph WaveNet 在推理阶段最为高效，因为它在一次运行中生成了 12 个预测，而 DCRNN 和 STGCN 必须基于之前的预测生成结果。
5 结论
在本文中，我们提出了一种用于时空图建模的新模型。通过将图卷积与扩张型因果卷积相结合，我们的模型能够高效地捕获时空依赖关系。我们提出了一种有效的方法，能够从数据中自动学习隐藏的空间依赖关系。这为时空图建模开辟了一个新方向，即系统的依赖结构未知但需要被发现。在两个公共交通网络数据集上，Graph WaveNet 达到了最先进的结果。在未来的工作中，我们将研究在大规模数据集上应用 Graph WaveNet 的可扩展方法，并探索学习动态空间依赖关系的方法。
