马敏博作者西南交通大学硕士生学校命名实体识别研究方向

​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 

PaperWeekly
PaperWeekly

推荐、解读、讨论和报道人工智能前沿论文成果的学术平台。

理论​KDD 2020图神经网络
3
相关数据
深度学习技术

深度学习(deep learning)是机器学习的分支,是一种试图使用包含复杂结构或由多重非线性变换构成的多个处理层对数据进行高层抽象的算法。 深度学习是机器学习中一种基于对数据进行表征学习的算法,至今已有数种深度学习框架,如卷积神经网络和深度置信网络和递归神经网络等已被应用在计算机视觉、语音识别、自然语言处理、音频识别与生物信息学等领域并获取了极好的效果。

参数技术

在数学和统计学裡,参数(英语:parameter)是使用通用变量来建立函数和变量之间关系(当这种关系很难用方程来阐述时)的一个数量。

凸优化技术

凸优化,或叫做凸最优化,凸最小化,是数学最优化的一个子领域,研究定义于凸集中的凸函数最小化的问题。凸优化在某种意义上说较一般情形的数学最优化问题要简单,譬如在凸优化中局部最优值必定是全局最优值。凸函数的凸性使得凸分析中的有力工具在最优化问题中得以应用,如次导数等。 凸优化应用于很多学科领域,诸如自动控制系统,信号处理,通讯和网络,电子电路设计,数据分析和建模,统计学(最优化设计),以及金融。在近来运算能力提高和最优化理论发展的背景下,一般的凸优化已经接近简单的线性规划一样直捷易行。许多最优化问题都可以转化成凸优化(凸最小化)问题,例如求凹函数f最大值的问题就等同于求凸函数 -f最小值的问题。

注意力机制技术

我们可以粗略地把神经注意机制类比成一个可以专注于输入内容的某一子集(或特征)的神经网络. 注意力机制最早是由 DeepMind 为图像分类提出的,这让「神经网络在执行预测任务时可以更多关注输入中的相关部分,更少关注不相关的部分」。当解码器生成一个用于构成目标句子的词时,源句子中仅有少部分是相关的;因此,可以应用一个基于内容的注意力机制来根据源句子动态地生成一个(加权的)语境向量(context vector), 然后网络会根据这个语境向量而不是某个固定长度的向量来预测词。

梯度下降技术

梯度下降是用于查找函数最小值的一阶迭代优化算法。 要使用梯度下降找到函数的局部最小值,可以采用与当前点的函数梯度(或近似梯度)的负值成比例的步骤。 如果采取的步骤与梯度的正值成比例,则接近该函数的局部最大值,被称为梯度上升。

规范化技术

规范化:将属性数据按比例缩放,使之落入一个小的特定区间,如-1.0 到1.0 或0.0 到1.0。 通过将属性数据按比例缩放,使之落入一个小的特定区间,如0.0到1.0,对属性规范化。对于距离度量分类算法,如涉及神经网络或诸如最临近分类和聚类的分类算法,规范化特别有用。如果使用神经网络后向传播算法进行分类挖掘,对于训练样本属性输入值规范化将有助于加快学习阶段的速度。对于基于距离的方法,规范化可以帮助防止具有较大初始值域的属性与具有较小初始值域的属相相比,权重过大。有许多数据规范化的方法,包括最小-最大规范化、z-score规范化和按小数定标规范化。

过拟合技术

过拟合是指为了得到一致假设而使假设变得过度严格。避免过拟合是分类器设计中的一个核心任务。通常采用增大数据量和测试样本集的方法对分类器性能进行评价。

图神经网络技术

图网络即可以在社交网络或其它基于图形数据上运行的一般深度学习架构,它是一种基于图结构的广义神经网络。图网络一般是将底层图形作为计算图,并通过在整张图上传递、转换和聚合节点特征信息,从而学习神经网络基元以生成单节点嵌入向量。生成的节点嵌入向量可作为任何可微预测层的输入,并用于节点分类或预测节点之间的连接,完整的模型可以通过端到端的方式训练。

概念图技术

概念图(CGs)是知识表示的形式主义。 在第一篇关于CG的论文中,John F. Sowa用它们来表示数据库系统中使用的概念模式。 关于CGs的第一本书(Sowa 1984)将它们应用于人工智能、计算机科学和认知科学等广泛的主题。

节点信息机构

福建节点信息科技有限公司成立于 2009 年,是一家金融领域操作风险防控与智慧银行服务平台IT系统供应商。节点科技致力于为政府及所有企事业单位提供专业的资金风险控制和企业经营解决方案及咨询服务。提高企业管理水平,提升资金、资产安全事前防范能力,彻底杜绝案件的发生,为企业安全发展保驾护航。

http://www.cruxtek.com.cn/ProductIndex
感受野技术

一个感觉神经元的感受野是指这个位置里适当的刺激能够引起该神经元反应的区域。感受野一词主要是指听觉系统、本体感觉系统和视觉系统中神经元的一些性质。

时序预测技术

时序预测(时间序列预测)是预测时间序列未来值(以及不确定性的边界)的任务。

推荐文章
暂无评论
暂无评论~