​KDD 2020 开源论文 | 图神经网络多变量时序预测

本次分享的论文是 KDD 2020 的一篇工作，出发点是为了更好地建模 多变量时间序列数据中 成对变量之间的潜在空间依赖。作者提出了一种通用的 图神经网络 框架 MTGNN，通过图学习模块融合外部知识和变量之间的 单向关系，再使用 mix-hop 传播层和膨胀 inception 捕获空间和时序依赖。

此外，为更好地训练模型，结合课程学习提出了一种学习算法。在四个常规多变量时序数据集以及两个图数据集上的实验表明，对比现有取得 SOTA 的模型 MTGNN 具有较强的竞争力，在多个数据集上取得最优表现。

论文标题：

Connecting the Dots: Multivariate Time Series Forecasting with Graph Neural Networks

论文来源：

KDD 2020

论文链接：

https://arxiv.org/abs/2005.11650

代码链接：

https://github.com/nnzhan/MTGNN

本文将从以下方面对这篇工作进行介绍：

• 背景
• 挑战
• MTGNN框架
• 实验解读
• 个人总结

一、背景

多变量 时序预测 在经济、金融、生物信息和交通等领域有广泛应用。相较于单变量 时序预测 ，需要建模的问题更复杂，因为每个变量不仅与其历史值有关，还要考虑变量之间的依赖关系。

然而，现有的多变量 时序预测 方法并没有有效地探索变量之间的潜在空间依赖关系。 统计方法如 VAR 和 GP 假设变量之间存在线性依赖关系，随着变量的增加，模型复杂度二次方增长，容易导致 过拟合 。 深度学习 方法如 LSTNet [1] 和 TPA-LSTM [2]，虽然能够捕获非线性关系，但是无法明确地建模成对变量之间的依赖关系。

图是一种数据结构，可以描述节点之间的关系。目前， 图神经网络 由于排列不变性、局部连接以及组合性的特点，在处理图数据上取得较大的成功。多变量 时序预测 从图视角来看，变量可以当作节点，它们通过隐层依赖关系相互连接。所以， 图神经网络 可以建模多变量 时序预测 ，这也是这篇论文的主要出发点。

二、挑战

时空 图神经网络 是最适合多变量 时序预测 任务的 图神经网络 类型，因为多变量 时序预测 问题需要考虑时间维和空间维的信息表达。通常时空 图神经网络 以多变量时序数据和外部图结构作为输入，预测时序数据的未来值或标签。相较于未利用结构信息的方法，能够取得较大提升。但是，该方法仍然存在两个方面的挑战：

1. 未知的图结构 ：使用 图神经网络 建模 时序预测 任务时，大多依赖于预定义的图结构。但是，大多数情况下，多变量 时序预测 是没有明确的图结构，需要从数据中去学习变量之间的关系（图）。

2. 图结构与图神经网络 共同学习：现有方法大多专注于如何设计合适的 图神经网络 结构，却忽略了有时图结构（通常为邻接矩阵）有可能不是最优的，也需要在训练中优化。因此，对于时序问题，如何在一个 end2end 的框架下同时学习图结构和 图神经网络 是一个问题。

三、MTGNN

MTGNN 各部分之间的联系如下图所示，主要有三个模块组成 图学习模块、 图卷积模块、 时序卷积模块。

下面根据上述两个挑战，介绍下本文的解决方案。

针对挑战1，作者提出了一个图学习层，能够自适应地从数据中抽取 稀疏图邻接矩阵。此外，基于学习得到的图邻接矩阵，作者使用图卷积模块进行变量之间空间依赖学习。同时，作者对图卷积模块进行了改进，学习变量之间的单向依赖以及缓解 图神经网络 中的 过度平滑问题。

针对挑战2，图学习层和图卷积模块都是 参数 化的，两者通过后向传播（ 梯度下降 ）方法共同优化。

除上述改进之外，作者还在时序卷积以及训练优化方面进行了研究。在时序卷积方面，作者提出了膨胀 inception 层，以便处理更长序列时序数据；针对大规模图学习中的非 凸优化 问题以及内存占用问题，作者提出了基于课程学习寻找局部最优以及切分多变量时序数据为多个子片段的学习算法。

▲ MTGNN概念图

3.1 总体框架

在介绍完大概的解决方法后，下面将系统地介绍 MTGNN 整体框架。必不可少的，先来看总体框架图（如下图所示）。主要包括了图学习层、m 个图卷积模块、m 个时序卷积模块、输出模块。除主要模块外，还包括了残差连接和跳跃连接。接下来的章节，将详细介绍每一模块。

▲ MTGNN总体框架图

3.2 图学习层

图学习层是为了学习一个邻接矩阵，从时序数据中自适应地捕获变量之间的空间关系。作者认为时序书中变量之间的关系是单向的，一个节点状态的变化会引起其他节点的变化，如交通流问题。所以需要注意的是，所提图学习层学习的邻接矩阵具有非对称的属性。通过以下计算，可以实现该方法。

▲ 计算公式 

3.3 图卷积模块

图卷积模块可以整合节点以及邻居节点信息 。论文所提的图卷积包含了两个 mix-hop 传播层，结构信息如下图所示。 信息传播和信息选择在图中分别对应到横向和纵向。mix-hop 的思想首先是 [3] [4] 提出，其中 [3] 采用的方式为拼接不同的 hop 信息，[4] 使用 注意力机制 整合不同的 hop 信息。

▲ 图卷积模块

两个 mix-hop 分别处理单个节点的 inflow 信息和 outflow 信息，最终将两个信息相加所谓最终的模块输出信息。

具体的 mix-hop 的结构如下图所示，包含了两个子模块： 信息传播和 信息选择。

▲ mix-hop传播层

3.4 时序卷积模块

时序卷积模块是使用多个标准的一维膨胀卷积核抽取高维的时序特征。如前文介绍，时序卷积模块主要包括了两部分 膨胀（空洞）卷积和 inception 层，这两种卷积结构在 CV 中已经经过有效性验证。其结构如下图所示，

▲ 时序卷积模块

关于膨胀卷积，这里就不过多介绍，其主要是通过引入“空洞”，在增大 感受野 的同时，不增加模型 参数 。Inception 是从卷积的宽度出发，相较于 ResNet 从深度出发，其通过拼接的方式从宽度上增加 感受野 。具体结构如下图所示，

▲ 膨胀inception层

最后，再提以下卷积核大小的选择。为了更好地抽取自然时序信号，文中没有选择常用的 1、3、5 的卷积大小，而是考虑到自然时序周期 7、12、24、60 等，所以文中选择的卷积核大小为 1x2、1x3、1x6、1x7。

3.5 跳跃连接层和输出层

跳跃连接层和输出层的作用较为直观，最终送入输出层的信息为多个模块的拼接，跳跃连接层起到一个 规范化 信息的作用，使输入到输出层的序列长度相同。输出层包括两个 1x1 的卷积层，输出指定维度值，如果单步预测维度为 1，如果多步 Q 预测，维度为 Q。

3.6 学习算法

学习算法包括了两个部分，1.子图划分（采样部分）；2.课程学习训练。具体算法描述如下图所示：

▲ 学习算法流程

着重介绍下 课程学习（Curriculum Learning），由 Benjio [5] 在 2009ICML 会议中提出。主要思想为：主张模型先学习“易样本”，再学习“难样本”。这样会带来两个好处：1. 加速模型训练，减少迭代次数；2. 达到更好的局部最优。在这个问题中，如何定义样本的难易是最关键的。

在本文的任务长期预测中，比较容易想到的是短期预测效果是肯定优于长期预测的，那么可以先学习短期的，再逐渐学习长期的。我这里介绍的比较口语化，原文从 loss 层面介绍，我理解的是如果长期预测，越长步数的预测值偏差越大，导致总 loss 会更大，即使取平均，相较于短期预测也会产生更大的 loss。

四、实验解读

实验总共分为两个部分，单步预测和多步预测，其中单步预测使用多变量 时序预测 的常规数据集，多步预测使用的含有传感器位置信息的时序数据。具体介绍如下图所示，

▲ 实验数据集

基线模型：

• LSTNet [1]
• TPA-LSTM [2]
• DCRNN [6]
• STGCN [7]
• Graph WaveNet [8]
• ST-MetaNet [9]
• GMAN [10]
• MRA-BGCN [11]

论文中做了多种实验，这里我主要介绍下与时空 图神经网络 相关的基线模型对比。从实验结果来看，MTGNN 可以取得 SOTA 或者与 SOTA 相差无几的效果。相较于对比的方法，其主要优势在于不需要预定的图。其中 Graph WaveNet 是本文作者在 IJCAI 2019 的工作，也是自适应构建邻接矩阵，但是需要结合预定图才能取得较好的效果。

▲ 多步预测对比

除此之外，还有 消融实验、个例实验、参数 实验。其中个例实验较为有意思，其对比了预定图和学习图得到的最近邻居节点，然后将其可视化，可以反应邻居节点在现实位置直接的关系。

五、个人总结

这里，笔者相对论文中涉及到的主要改进工作、对应解决的问题，进行统计。直接给出组会汇报的原文：

▲ 个人总结

参考文献

[1] Modeling long-and short-term temporal patterns with deep neural networks

[2] Temporal pattern attention for multivariate time series forecasting

[3] MixHop:Higher-Order Graph Convolutional Architectures via Sparsified Neighborhood Mixing

[4] DAGCN: Dual Attention Graph Convolutional Networks

[5] Curriculum Learning

[6] Diffusion convolutional recurrent neural network: Data-driven traffic forecasting.

[7] Spatio-Temporal Graph Convolutional Networks: A Deep Learning Framework for Traffic Forecasting

[8] Graph WaveNet for Deep Spatial-Temporal Graph Modeling.

[9] Urban Traffic Prediction from Spatio-Temporal Data Using Deep Meta Learning

[10] GMAN: A Graph Multi-Attention Network for Traffic Prediction

[11] Multi-Range Attentive Bicomponent Graph Convolutional Network for Traffic Forecasting