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

长期以来，建模多变量时间序列一直是吸引来自不同领域的研究人员的主题，包括经济、金融和交通。多变量时间序列预测背后的一个基本假设是其变量相互依赖，但仔细观察，可以公平地说，现有方法未能充分利用成对变量之间的潜在空间依赖性。与此同时，近年来，图神经网络（GNN）在处理关系依赖方面表现出了很高的能力。 GNN 需要明确定义的图结构来进行信息传播，这意味着它们不能直接应用于事先不知道依赖关系的多变量时间序列。在本文中，我们提出了一个专门为多变量时间序列数据设计的通用图神经网络框架。我们的方法通过图形学习模块自动提取变量之间的单向关系，可以轻松地将变量属性等外部知识集成到其中。进一步提出了一种新颖的混合跳传播层和扩张的初始层来捕获时间序列内的空间和时间依赖性。图学习、图卷积和时间卷积模块在端到端框架中联合学习。实验结果表明，我们提出的模型在 4 个基准数据集中的 3 个上优于最先进的基线方法，并在两个提供额外结构信息的交通数据集上实现了与其他方法相当的性能。

引言

现代社会受益于各种传感器来记录温度、价格、交通速度、用电量和许多其他形式的数据的变化。 来自不同传感器的记录时间序列可以形成多元时间序列数据，并且可以相互关联。 例如，日常温度的升高可能会导致用电量增加。 为了捕捉一组动态变化变量的系统趋势，多变量时间序列预测问题已经研究了至少 60 年。 它在经济、金融、生物信息学和交通等领域得到了巨大的应用。

多元时间序列预测方法固有地假设变量之间的相互依赖关系。换言之，每个变量不仅取决于其历史值，还取决于其他变量。然而，现有方法并没有有效地利用变量之间潜在的相互依赖关系。统计方法，例如向量自回归模型 (VAR) 和高斯过程模型 (GP)，假设变量之间存在线性相关性。统计方法的模型复杂度随着变量的数量呈二次方增长。他们面临着大量变量过拟合的问题。最近开发的基于深度学习的方法，包括 LSTNet 和 TPA-LSTM，对于捕获非线性模式非常有效。 LSTNet 使用一维卷积神经网络将短期局部信息编码为低维向量，并通过递归神经网络对向量进行解码。 TPA-LSTM 通过循环神经网络处理输入，并采用卷积神经网络跨多个步骤计算注意力分数。 LSTNet 和 TPA-LSTM 没有显式地对变量之间的成对依赖关系进行建模，这削弱了模型的可解释性。

最适合多变量时间序列的图神经网络类型是时空图神经网络。 时空图神经网络以多变量时间序列和外部图结构作为输入，旨在预测多变量时间序列的未来值或标签。 与不利用结构信息的方法相比，时空图神经网络取得了显着的改进。 然而，由于以下挑战，这些方法仍然无法对多变量时间序列进行建模：

• 挑战 1：未知的图结构。 现有的 GNN 方法严重依赖预定义的图结构来执行时间序列预测。 在大多数情况下，多变量时间序列没有明确的图结构。 变量之间的关系必须从数据中发现，而不是作为基本事实知识提供。
• 挑战 2：图学习和 GNN 学习。 尽管图结构可用，但大多数 GNN 方法只关注消息传递（GNN 学习），而忽略了图结构不是最优的并且应该在训练期间更新的事实。 那么问题是如何在端到端框架中同时学习图形结构和时间序列的 GNN。

在本文中，我们提出了一种新的方法来克服这些挑战。 如图 1 所示，我们的框架由三个核心组件组成——图学习层、图卷积模块和时间卷积模块。 对于挑战 1，我们提出了一种新颖的图学习层，它基于数据自适应地提取稀疏图邻接矩阵。 此外，考虑到由图学习层计算的邻接矩阵，我们开发了一个图卷积模块来解决变量之间的空间依赖关系。 这是专门为有向图设计的，避免了图卷积网络中经常出现的过度平滑问题。 最后，我们提出了一个时间卷积模块，通过修改后的一维卷积来捕获时间模式。 它既可以发现具有多个频率的时间模式，也可以处理非常长的序列。

由于所有参数都可以通过梯度下降来学习，因此所提出的框架能够对多变量时间序列数据进行建模，并以端到端的方式同时学习内部图结构（对于挑战 2）。 为了降低解决高度非凸优化问题的难度并减少处理大图时的内存占用，我们提出了一种学习算法，该算法使用课程学习策略找到更好的局部最优值，并在训练期间将多变量时间序列拆分为子组。 这里的优点是我们提出的框架通常适用于小型和大型图，短时间和长时间序列，有和没有外部定义的图结构。 总之，我们的主要贡献如下：

• 据我们所知，这是对多变量时间序列数据的第一次研究，通常是从基于图的角度使用图神经网络进行的。
• 我们提出了一种新颖的图学习模块来学习变量之间隐藏的空间依赖关系。 我们的方法为 GNN 模型打开了一扇新的大门，可以在没有显式图结构的情况下处理数据。
• 我们提出了一个用于建模多变量时间序列数据和学习图结构的联合框架。 我们的框架比任何现有的时空图神经网络都更通用，因为它可以处理有或没有预定义图结构的多变量时间序列。
• 实验结果表明，我们的方法在 4 个基准数据集中的 3 个上优于最先进的方法，并在两个提供额外结构信息的交通数据集上实现了与其他 GNN 相同的性能。

研究背景

多变量时间序列预测

时间序列预测已经研究了很长时间。大多数现有方法都遵循统计方法。自回归综合移动平均 (ARIMA) 概括了一系列线性模型，包括自回归 (AR)、移动平均 (MA) 和自回归移动平均 (ARMA)。向量自回归模型 (VAR) 扩展了 AR 模型以捕获多个时间序列之间的线性相互依赖关系。类似地，向量自回归移动平均模型（VARMA）被提出作为 ARMA 模型的多元版本。高斯过程 (GP) 作为贝叶斯方法，对多元变量在函数上的分布进行建模。 GP 可以自然地应用于对多变量时间序列数据进行建模。尽管统计模型因其简单性和可解释性而被广泛用于时间序列预测，但它们对平稳过程做出了强有力的假设，并且不能很好地扩展到多变量时间序列数据。基于深度学习的方法没有固定假设，它们是捕捉非线性的有效方法。赖等人和 Shih 等人是为多元时间序列预测设计的前两个基于深度学习的模型。他们使用卷积神经网络来捕获变量之间的局部依赖关系，并使用递归神经网络来保持长期的时间依赖关系。卷积神经网络将变量之间的交互封装到全局隐藏状态中。因此，它们不能充分利用成对变量之间的潜在依赖关系。

图神经网络

图神经网络在处理网络中实体之间的空间依赖关系方面取得了巨大成功。图神经网络假设节点的状态取决于其邻居的状态。为了捕捉这种类型的空间依赖性，已经通过消息传递、信息传播和图卷积开发了各种图神经网络。它们共享相似的角色，本质上是通过将信息从节点的邻居传递到节点本身来捕获节点的高级表示。最近，我们看到了一种称为时空图神经网络的图神经网络的出现。最初提出这种形式的神经网络是为了解决交通预测和基于骨架的动作识别的问题。时空图神经网络的输入是具有外部图结构的多元时间序列，该结构描述了多元时间序列中变量之间的关系。对于时空图神经网络，节点之间的空间依赖关系由图卷积捕获，而历史状态之间的时间依赖关系由循环神经网络或一维卷积保留。尽管与不使用图结构的方法相比，现有的时空图神经网络取得了显着的进步，但由于缺乏预定义的图和缺乏通用框架，它们无法有效地处理纯多变量时间序列数据。

问题形式化定义

在本文中，我们专注于多元时间序列预测的任务。 令 $z_t \in \mathbb{R}^{N}$ 表示 $N$ 维多变量在时间步 t 的值，其中 $z_t [i] \in \mathbb{R}$ 表示第 $i$ 个变量在时间步 $t$ 的值。 给定对多变量时间序列 $X = \{z_{t_1}, z_{t_2}, ..., z_{t_P} \}$ 的一系列历史 $P$ 时间步长观察，我们的目标是预测 $Y = \{z_{t_{P+Q} }\}$ 的 $Q$步距值， 或一系列未来值 $Y = \{z_{t_{P+1}}, z_{t_{P+2}},... , z_{t_{P+Q}} \}$。 更一般地，输入信号可以与其他辅助特征相结合，例如一天中的时间、一周中的一天和季节中的一天。 将输入信号与辅助特征连接起来，我们假设输入是 $X = \{S_{t_1}, S_{t_2}, ..., S_{t_P} \}$ 其中 $S_{t_i} \in \mathbb{R}^{N \times D}$, $D$ 是特征维度，$S_{t_i}$ 的第一列等于 $z_{t_i}$ ，并且 其余的都是辅助功能。 我们的目标是通过使用 $l2$ 正则化最小化绝对损失来构建从 $X$ 到 $Y$ 的映射 $f (\cdot)$。

图描述了网络中实体之间的关系。 我们在下面给出了与图相关的概念的正式定义。

定义 1 图： 图被表述为 $G = (V , E)$，其中 $V$ 是节点集，$E$ 是边集。 我们使用 $N$ 来表示图中的节点数。

定义 2 邻接节点： 设 $v \in V$ 表示一个节点， $e = (v,u) \in E$ 表示一条从 $u$ 指向 $v$ 的边。节点 $v$ 的邻域定义为 $N (v) = \{u \in V |(v, u) \in E\}$。

定义 3 邻接矩阵： 邻接矩阵是图的数学表示，表示为 $A \in \mathbb{R}^{N \times N}$，如果 $(v_i,v_j) \in E$ 则 $A_{ij} = c > 0$，如果 $(v_i,v_j) \notin E$ 则 $A_{ij} = 0$。

从基于图的角度来看，我们将多元时间序列中的变量视为图中的节点。 我们使用图邻接矩阵来描述节点之间的关系。 在大多数情况下，图邻接矩阵不是由多元时间序列数据给出的，而是由我们的模型学习的。

MTGNN 框架

模型结构

我们首先详细说明我们模型的一般框架。如图2所示，最高层的MTGNN由一个图学习层、m个图卷积模块、m个时间卷积模块和一个输出模块组成。为了发现节点之间的隐藏关联，图学习层计算图邻接矩阵，该矩阵随后用作所有图卷积模块的输入。图卷积模块与时间卷积模块交错以分别捕获空间和时间依赖性。图 3 演示了时间卷积模块和图卷积模块如何相互协作。为了避免梯度消失的问题，将残差连接从时间卷积模块的输入添加到图卷积模块的输出。在每个时间卷积模块之后添加跳过连接。为了获得最终输出，输出模块将隐藏的特征投影到所需的输出维度。更详细地说，我们模型的核心组件如下所示：

图学习层

图学习层自适应地学习图邻接矩阵以捕获时间序列数据之间的隐藏关系。 为了构建图，现有研究通过距离度量来测量节点对之间的相似性，例如点积和欧几里得距离。 这不可避免地导致了 $O(N^2)$ 的高时间和空间复杂度问题。 这意味着计算和内存成本随着图形大小的增加呈二次方增长。 这限制了模型处理更大图的能力。 为了解决这个限制，我们采用了一种抽样方法，它只计算节点子集之间的成对关系。 这切断了每个 minibatch 中计算和内存的瓶颈。

另一个问题是现有的距离度量通常是对称的或双向的。 在多变量时间序列预测中，我们期望一个节点状态的变化会引起另一个节点状态的变化，例如交通流量。 因此，学习到的关系应该是单向的。 我们提出的图学习层专门设计用于提取单向关系，如下所示：

$$\tag{1} M_1 = \textup{tanh}(\alpha E_1\Theta_1)$$

$$\tag{1} M_2 = \textup{tanh}(\alpha E_2\Theta_2)$$

$$\tag{3} A = \textup{ReLU}(\textup{tanh}(\alpha(M_1M_2^{\intercal}-M_2M_1^{\intercal})))$$

$$\tag{4} for\;i = 1,2, ..., N$$

$$\tag{5} \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; \textup{idx} = \textup{argtopk}(A[i,:])$$

$$\tag{6} \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; A[i,-\textup{idx}]=0$$

其中 $E_1$, $E_2$ 表示随机初始化的节点嵌入，在训练期间可学习，$\Theta_1$, $\Theta_2$ 是模型参数，$\alpha$ 是控制激活函数饱和率的超参数，$\textup{argtopk}(\cdot)$ 返回TOP-K最大值的索引。 我们提出的图邻接矩阵的非对称特性由等式 3 实现。减法项和 ReLU 激活函数对邻接矩阵进行正则化，使得如果 $A_{vu}$ 为正，则其对角对应的 $A_{uv}$ 将为零。 公式 5-6 是一种使邻接矩阵稀疏的策略，同时降低了后续图卷积的计算成本。 对于每个节点，我们选择其前 k 个最近的节点作为其邻居。 在保留连接节点的权重的同时，我们将非连接节点的权重设置为零。

合并外部数据。 图学习层的输入不限于节点嵌入。 在给定每个节点属性的外部知识的情况下，我们还可以设置 E1 = E2 = Z，其中 Z 是静态节点特征矩阵。 一些工作已经考虑捕获动态空间依赖关系。 换句话说，它们根据时间输入动态调整两个连接节点的权重。 然而，当我们需要同时学习图结构时，假设动态空间依赖会使模型极难收敛。 我们方法的优点是我们可以在训练数据集期间学习稳定且可解释的节点关系。 一旦模型在在线学习版本中得到训练，我们的图邻接矩阵也可以随着新的训练数据更新模型参数而适应变化。

图卷积模块

图卷积模块旨在将节点的信息与其邻居的信息融合，以处理图中的空间依赖关系。 图卷积模块由两个mixhop传播层组成，分别处理通过每个节点的流入和流出信息。 净流入信息是通过将两个混合跳传播层的输出相加得到的。 图 4 显示了图卷积模块和混合跳传播层的架构。

混合跳传播层。 给定一个图邻接矩阵，我们提出了混合跳传播层来处理空间相关节点上的信息流。 所提出的混合跳传播层包括两个步骤——信息传播步骤和信息选择步骤。 我们首先给出这两个步骤的数学形式，然后说明我们的动机。 信息传播步骤定义如下：

$$\tag{7} H^{(k)} = \beta H_{in} + (1-\beta)\tilde{A}H^{(k-1)}$$

其中$\beta$是一个超参数，它控制保留根节点原始状态的比例。 信息选择步骤定义如下

$$\tag{8} H_{out} = \sum_{i=0}^{K}H^{(k)}W^{(k)}$$

其中 $K$ 为传播深度，$H_{in}$ 表示前一层输出的输入隐藏状态，$H_{out}$表示当前层的输出隐藏状态，$H^{(0)} = H_{in}$, $\tilde{A} = \tilde{D}^{ -1}(A + I)$, 和 $\tilde{D}_{ii} = 1 +\sum_j A_{ij}$。 在图 4b 中，我们演示了所提出的混合跳传播层中的信息传播步骤和信息选择步骤。 它首先水平传播信息，垂直选择信息。

信息传播步骤递归地传播节点信息以及给定的图结构。图卷积网络的一个严重限制是，随着图卷积层的数量趋于无穷大，节点隐藏状态会收敛到一个点。这是因为无论初始节点状态如何，具有多层的图卷积网络都会达到随机游走的极限分布。为了解决这个问题，由 Klicpera 等人提出，我们在传播过程中保留了一部分节点的原始状态，以便传播的节点状态既可以保持局部性又可以探索深层邻域。但是，如果我们只应用公式 7，将会丢失一些节点信息。在不存在空间依赖的极端情况下，聚合邻域信息只会给每个节点添加无用的噪声。因此，引入信息选择步骤，过滤掉每一跳产生的重要信息。根据等式 8，参数矩阵 $W^{(k)}$ 用作特征选择器。当给定的图结构不包含空间依赖关系时，公式 8 仍然能够通过将所有 $k > 0$ 的 $W^{(k)}$ 调整为 0 来保留原始节点自身信息。

与现有作品的联系。卡普尔等人连接来自不同跃点的信息。 陈等人提出了一种注意力机制来对不同跳之间的信息进行加权。 他们都将 GCN 用于信息传播。 然而，由于 GCN 面临过度平滑问题，来自更高跳的信息可能不会或对整体性能产生负面影响。 为了避免这种情况，我们的方法在本地和邻域信息之间保持平衡。 此外，卡普尔等人表明他们提出的具有两个混合跳层的模型能够表示两个连续跳之间的增量差异。 我们的方法只需一个混合跳传播层就可以达到相同的效果。 假设 $K = 2$，$W^{(0)} = 0$，$W^{(1)} = -1$，并且 $W^{(2)} = 1$，那么

$$\tag{9} H_{out} = \Delta(H^{(2)},H^{(1)}) = H^2 - H^1$$

从这个角度来看，与串联方法相比，使用求和更有效地表示不同跳数的所有线性交互。

时序卷积模块

时间卷积模块应用一组标准扩张的一维卷积滤波器来提取高级时间特征。 该模块由两个扩张的初始层组成。 一个扩张的初始层后跟一个正切双曲线激活函数，用作过滤器。 另一层之后是 sigmoid 激活函数，它作为一个门来控制过滤器可以传递给下一个模块的信息量。 图 5 显示了时间卷积模块和扩张的初始层的架构。

扩张的初始层。 时间卷积模块通过一维卷积滤波器捕获时间序列数据的顺序模式。 为了提出一个能够发现具有各种范围的时间模式并处理非常长的序列的时间卷积模块，我们提出了扩张初始层，它结合了来自卷积神经网络的两种广泛应用的策略，即使用多种尺寸的滤波器并应用扩张卷积。

首先，选择正确的内核大小对于卷积网络来说是一个具有挑战性的问题。滤波器大小可能太大而无法巧妙地表示短期信号模式，或者太小而无法充分发现长期信号模式。在图像处理中，一种广泛采用的策略称为 inception，它将具有 1×1、3×3 和 5×5 三种不同内核大小的 2D 卷积滤波器的输出连接起来。从 2D 图像转移到 1D 时间序列，集合1 × 1、1 × 3 和 1 × 5 的滤波器大小不适合时间信号的性质。由于时间信号往往具有几个固有周期，例如 7、12、24、28 和 60，因此滤波器大小为 1×1、1×3 和 1×5 的初始层堆栈不能很好地包含这些周期。或者，我们提出了一个由四个滤波器大小组成的时间初始层，即。 1 × 2、1 × 3、1 × 6 和 1 × 7。上述时段都可以通过这些过滤器大小的组合来覆盖。例如，为了表示周期 12，模型可以将输入通过来自第一个时间初始层的 1×7 滤波器，然后是来自第二个时间初始层的 1×6 滤波器。

其次，卷积网络的感受野大小随着网络的深度和滤波器的内核大小呈线性增长。 考虑一个具有 m 个核大小为 c 的 1D 卷积层的卷积网络，卷积网络的感受野大小为：

$$\tag{10} R=m(c-1)+1$$

要处理非常长的序列，它需要非常深的网络或非常大的过滤器。 我们采用扩张卷积来降低模型复杂度。 扩张卷积对具有特定频率的下采样输入运行标准卷积滤波器。 例如，当膨胀因子为 2 时，它对每两步采样的输入应用标准卷积。 我们让每一层的膨胀因子以 $q$ ($q > 1$) 的速率呈指数增长。 假设初始扩张因子为1，核大小为$c$的$m$层扩张卷积网络的感受野大小为

$$\tag{11} R = 1+(c-1)(q^m-1)/(q-1)$$

这表明网络的感受野大小也随着隐藏层数量以 $q$ 的速率增加而呈指数增长。 因此，与没有它的情况相比，使用这种扩张策略可以捕获更长的序列。

形式上，结合 inception 和 dilation，我们提出了 dilated inception 层，如图 5b 所示。 给定一维序列输入 $z \in \mathbb{R}^T$ 和由 $f_{1\times2} \in \mathbb{R}^2$、$f_{1\times 3} \in \mathbb{R}^3$、$f_{1\times6} \in \mathbb{R}^6$ 和 $f_{1\times7} \in \mathbb{R}^7$ 组成的过滤器，我们的扩张初始层采用以下形式：

$$\tag{12} z= \textup{concat}(z \star f_{1\times2}, z \star f_{1\times3},z \star f_{1\times6},z \star f_{1\times7})$$

其中四个过滤器的输出根据最大的过滤器被截断为相同的长度，并在通道维度上连接，由 $z \star f_{1\times k}$ 表示的扩张卷积定义为

$$\tag{13} z \star f_{1\times k}(t) = \sum_{s=0}^{k-1}f_{1 \times k}(s)z(t-d\times s)$$

其中，$d$ 是扩张因子。

跳连层和输出模块

跳过连接层本质上是 $1 × L_i$ 标准卷积，其中 $L_i$ 是第 $i$ 个跳过连接层的输入的序列长度。 它将跳转到输出模块的信息标准化为具有相同的序列长度 1。输出模块由两个 $1\times1$ 标准卷积层组成，将输入的通道维度转换为所需的输出维度。 如果我们只想预测某个未来步骤，则所需的输出维度为 1。当我们要预测 $Q$ 个连续步骤时，所需的输出维度为 $Q$。

提出的学习算法

我们提出了一种学习算法来增强我们的模型处理大型图和稳定在更好的局部最优值的能力。在图上训练通常需要将所有节点中间状态存储到内存中。如果图很大，就会面临内存溢出的问题。与我们最相关的是蒋等人提出了一种子图训练算法来解决内存瓶颈。他们应用图聚类算法将图划分为子图，并在划分的子图上训练图卷积网络。在我们的问题中，基于节点的拓扑信息对节点进行聚类是不切实际的，因为我们的模型同时学习了潜在的图结构。或者，在每次迭代中，我们将节点随机分成几组，并让算法基于采样节点学习子图结构。这为每个节点提供了被分配给一组中的另一个节点的全部可能性，以便可以计算和更新这两个节点之间的相似性分数。作为附带的好处，如果我们将节点分成 $s$ 组，我们可以在每次迭代中将图学习层的时间和空间复杂度从 $O(N^2)$ 降低到 $(N/s)^2$。训练后，由于所有节点嵌入都经过良好训练，可以构建全局图以充分利用空间关系。尽管计算成本很高，但邻接矩阵可以在进行预测之前并行预先计算。

我们提出的算法的第二个考虑是促进我们的模型稳定在更好的局部最优值。在多步预测任务中，我们观察到长期预测在模型性能方面往往比短期预测取得更大的改进。我们认为原因是我们的模型完全预测了多步，长期预测产生的损失比短期预测高得多。因此，为了最大限度地减少整体损失，该模型更侧重于提高长期预测的准确性。为了解决这个问题，我们提出了多步预测任务的课程学习策略。该算法从解决最简单的问题开始，仅预测下一步。模型找到一个好的起点是非常有利的。随着迭代次数的增加，我们逐渐增加模型的预测长度，使模型可以逐步学习 hard task。涵盖所有这些，我们的算法在算法 1 中给出。我们模型的进一步复杂性分析可以在附录 A.1 中找到。

论文原文