机器学习周记（第二十六周：文献阅读-DPGCN）2024.1.15~2024.1.21

目录

摘要

ABSTRACT

1 论文信息

1.1 论文标题

1.2 论文摘要

1.3 论文背景

2 论文模型

2.1 问题描述

2.2 论文模型

2.2.1 时间感知离散图结构估计（Time-aware Discrete Graph Structure Estimation Module，TADG Module）

2.2.2 时间卷积模块（Temporal Convolution Module，TC Module）

2.2.3 动态个性化图卷积模块（Dynamic Personalized Graph Convolution Module，DPGC Module）

2.2.4 优化目标（Optimization Objective）

---

?

摘要

? 本周阅读了一篇关于动态时空图神经网络的论文，该论文的模型（TPGCN）主要用于处理多元时间序列预测任务。TPGCN主要包含如下四个模块：时间感知离散图结构估计模块（Time-aware Discrete Graph Structure Estimation Module，TADG Module）、 时间卷积模块（Temporal Convolution Module，TC Module）、动态个性化图卷积模块（Dynamic Personalized Graph Convolution Module，DPGC Module）和识别模块（Identification Modle）。其主要优势在于，能够动态改变图结构，将图结构学习作为模型学习的一部分和预测任务放在一个框架中进行训练。

ABSTRACT

This week, We read a paper on a dynamic spatio-temporal graph neural network, and the model in the paper, TPGCN, is primarily designed for handling multivariate time series prediction tasks. TPGCN comprises four main modules: the Time-aware Discrete Graph Structure Estimation Module (TADG Module), Temporal Convolution Module (TC Module), Dynamic Personalized Graph Convolution Module (DPGC Module), and Identification Module. Its main advantage lies in its ability to dynamically alter the graph structure, treating graph structure learning as a part of the model learning process, and training the prediction task within a unified framework.

1 论文信息

1.1 论文标题

Time-aware personalized graph convolutional network for multivariate time series forecasting

1.2 论文摘要

? 使用图结构来建模多元时间序列数据中的变量依赖关系具有很大的潜力。概率图模型，从神经网络参数分布中采样离散图，已经显示出了有效性。然而，现有方法忽略了依赖关系的动态性和异构信息的约束。例如，交通数据道路之间的相互作用受到交通量和网络拓扑结构的制约。此外，现有的时空图传播机制未能考虑节点自身的演化模式对未来结果的影响。为了解决这些局限性，提出了一种新的方法：时间感知个性化图卷积网络（TPGCN），由时间感知离散图结构估计（TADG）和动态个性化图卷积（DPGC）组成。TADG模块通过将图学习构建为异构信息环境中的推理问题来应对图学习的挑战。通过动态输入，它推导出受交互性质变化影响的图结构。DPGC受个性化PageRank的启发，在考虑进化模式和外部因素的同时对可变效应进行建模。通过在每次信息聚合时动态融合这两种信息，所提出方法优于现有的最先进方法，在八个基准数据集上进行了证明。

1.3 论文背景

? 多元时间序列分析是科学和工程中一个不可或缺的研究领域，因为它在气候研究、交通控制和能源管理等领域广泛应用。精确的交通流量预测可以防止延误、缓解拥堵，并降低事故发生的可能性，有助于个人更好地管理自己的出行。同样，精确的气候预测可以更好地保护环境，有助于预防灾难性灾害，并为规划和决策提供基础。此外，精确的电力消耗预测可以为能源公司带来显著好处，使他们优化资源规划和配置。因此，精确的多元时间序列预测在许多应用中至关重要。

? 由于图结构可以有效地建模变量之间的依赖关系，时空图神经网络（GNNs）被广泛采用。首先，研究人员依赖于基于先验知识（如道路连接距离）人为制作的图邻接矩阵。然而，这种方法的可行性往往受到隐私问题和缺乏必要的先验知识的限制。在没有任何先验指导的情况下，从数据本身中发现潜在空间关系进行努力已经成为一个充满活力的研究方向。现有方法主要是通过测量成对的节点嵌入之间的相似性来计算边权重，这些嵌入作为可训练参数。虽然像DGCRN和ASTGNN这样的方法适合捕捉数据中的动态相互依赖关系，但它们需要预定义的图结构。相比之下，DMSTGCN、ESG 和SDGL等方法能够根据节点特征和学习到的节点嵌入来推断图结构。值得注意的是，完全基于节点嵌入的方法学习了一个密集的依赖结构，这可能会导致错误的关联。通过将问题构建为图分布学习，概率图模型展现出了巨大的潜力。这种模型独立地计算每个节点对的边存在概率，而不对关系的存在进行约束。LDS-GNN将图结构学习视为一个双层优化问题，其中变量之间的边从伯努利分布中采样。为了降低计算成本，GTS提出了一种联合优化公式，将图学习和模型参数一起优化，简化了优化问题，并为建模者提供了更大的灵活性来设计参数化。

? 尽管上述讨论的方法取得了显著的成功，但仍有几个重大挑战尚未解决。当前概率图方法的一个关键问题是不能理解异构信息存在时变量的动态相关性。GTS通过优化训练集的平均性能来参数化图分布，即学习与时间无关的图分布。然而，重要的是要认识到动态性是时间序列数据的固有特征，表现为受一系列异构因素同时影响的变量之间的依赖关系。例如，在交通数据的背景下，不同路段之间的相互关系不仅受底层路网结构的影响，还受交通模式的流动性的影响。如图1(a)所示，用从传感器收集的交通流数据来举例说明这个概念。值得注意的是，在图1(b)中，传感器1和2以及传感器3和4表现出类似的交通流趋势，从而表明这些传感器之间存在明显的相关性。此外，变量之间的关联是时间感知的（动态）。这方面在图1(b)中可以看出，其中黑框表示强大的相关性，传感器之间的共享交通流模式证明了这一点。相反，红框表示8月15日13:00至18:00期间传感器3和4之间的相关性较弱，表示不同甚至冲突的交通流量行为。

图1.PeMSED8数据集中的交通流示意图

? 随后的关键问题围绕着时间序列的复杂性，不仅受到其固有演化模式的影响，还受到外源性序列的影响，这是目前在时空GNNs背景下被忽视的一个关键方面。必须注意的是，时空GNNs的现有操作方法遵循消息传递范式，从根本上类似于拉普拉斯平滑。这种方法倾向于同质化节点表示，过度分层可能会导致节点失去其内在独特性（过平滑）的现象。尽管由于时空GNNs的浅层结构，这种现象可能不会立即显现，但跨多个变量的潜在异质性是不可否认的。如图1(c)的圆形框所示，交通流模式呈现固定的演化模式，例如，传感器对2和130表现出早高峰，而传感器90则表现出晚高峰。常用的消息传递机制利用了变量之间的相互依赖关系，但无意中削弱了这些变量的内在演化模式。现有的时空图神经网络已经对扩散卷积和mix-hop传播技术进行了实验，前者捕捉数据随机性，后者对抗过平滑。然而，这些方法主要改进了消息传递范式，而没有深入研究变量本身的内在属性，特别是它们的演化模式。相比之下，多层感知器（MLP）网络最近在多元时间序列预测中引起了关注。研究STID在没有探索变量之间的潜在依赖关系的情况下，在多个交通数据集上取得了最先进的性能。这项工作颠覆了时空GNNs背后的假设，即利用变量之间的潜在相互依赖关系可以提高预测性能。在我们看来，建模多元时间序列的最优方法需要找到单变量演化模式和变量间依赖关系之间的微妙平衡。

??解决上述挑战需要克服两个主要挑战：(1)需要跨越相互限制和固有噪声从异构信息中发现时间感知的图结构；(2)有效建模外源序列和节点演化模式对未来结果的动态影响。为了应对这些挑战，本文提出了时间感知个性化图卷积网络（TPGCN），该网络包括两个关键组成部分：时间感知离散图结构估计（TADG）和动态个性化图卷积（DPGC）。TADG使用两种不同类型的信息来推断时间感知的图结构：模拟稳定结构信息的可训练节点嵌入和包含数据动态模式的节点级输入。为了自适应地融合两种形式的信息，并从异质信息中有效地推断边权重，利用了门控机制和通道注意力。将边权重作为特征向量输出链接概率，学习变量之间离散且稀疏的依赖关系。虽然论文的方法使用了节点嵌入，但最终结果是一个概率图，并不强制节点之间存在关联。

? DPGCN背后的基本思想是将节点表示更新从图信息聚合分离。受个性化PageRank原则的启发，该方法将单变量模式提取和变量间依赖关系统一在一个框架中，该框架明确衡量了表示更新期间每个节点的演化模式和外源序列的重要性。为了捕获时空数据固有的扩散特性，本文利用了类似于APPNP的有限迭代传播系统。在节点表示更新机制中引入了一种可训练的时空节点重启概率机制，能够量化外源序列之间的融合比例和每个节点的个性化演化模式。该设计宗旨旨在解决数据中的固有异构性。最后，将这两个模块集成到一个网络中进行联合优化。研究表明，对变量和自我进化模式之间的相互依赖关系进行建模对多元时间序列预测是必要的。

2 论文模型

2.1 问题描述

定义一（Graph）：图在数学上定义为，它由一组节点（变量）和一组边组成。边可以用一个图邻接矩阵表示，其中表示节点和之间有连接，即，表示没有边，即。节点在时刻的特征向量表示为，为特征数量。更进一步地说，表示时刻t的所有节点观测值。

定义二（Node Embedding）：节点嵌入表示为，其中表示维度。节点嵌入表示图中单个节点的浓缩和低维描述。事实上，使用可训练的节点嵌入来推断图结构方法已被证明是有效的。

定义三（Heterogeneous Information）：文中研究的节点同时受到结构信息和语义信息的影响，将这种多重信息称为异构信息。例如，在交通数据中，交通流受到路网和出行模式的双重影响。与推荐系统异构信息网络中观察到的范式不同，该研究没有得出这样的区分，其特征是存在各种节点类型和关系类型。本文使用可学习的节点嵌入来对节点的结构信息进行建模，这是传统的方法。引入来表示节点语义嵌入，来自节点级输入。

定义四（Spatial and Temporal Identities）：为了保留变量在时间和空间上的演化模式，本文使用了三个独立的可训练参数矩阵，包括、和，其中表示这些参数矩阵的维数，表示一天的样本数量，表示一周的天数。空间嵌入提供了静态表示，如区域标识，而时间嵌入和实现了多尺度时间模式的建模，这些模式不仅在天和周之间不同，而且根据使用的设置在不同的时间尺度之间不同。

定义五（Problem Formulation）：给定以表示的历史信号矩阵的过去个时间片，在多元时间序列预测中，目标是获得未来信号矩阵的序列。在单步预测中，目标是逼近真实值，而在多步预测中，预测目标扩展到下个时间片序列的未来值，用表示，即：

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?（1）

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

其中、为根据具体预测任务得到的映射函数。

2.2 论文模型

? 时间感知个性化图卷积网络（TPGCN）的架构如图2所示。TPGCN框架包含几个关键模块：时间感知的离散图结构估计（TADG）模块，k个时间卷积模块（TC）， K个动态个性化图卷积模块（DPGC），识别模块和输出模块。TADG模块、识别模块和TC模块同时将多元时间序列数据作为输入。TADG的输出产生一个时间感知的离散图结构，随后作为所有DPGC模块的输入，如图2(a)中的紫色箭头所示。识别模块通过利用三个学习到的嵌入矩阵以及多个多层感知器（MLP）层来捕获变量的内在自进化模式。获得的自进化模式的特征向量随后被导入DPGC，如图2(b)中的红色箭头所示。为避免分布偏移，在TC模块参与之前调用可逆实例归一化（RevIN）。TC模块依次与DPGC模块交替使用，提取隐藏在数据中的时间和空间信息。通过利用图2(c)所示的注意力机制，DPGC模块有效区分了更新节点状态过程中变量固有的自进化模式和外源序列的影响。此外，每个TC模块之后都有残差连接，并连接到输出模块以获得最终输出。

图2.TPGCN总体架构

2.2.1 时间感知离散图结构估计模块（Time-aware Discrete Graph Structure Estimation Module，TADG Module）

? 基于各种考虑，推断时间感知的二进制矩阵，是一个多方面的挑战。主要是，时序数据中变量间依赖关系的动态特性使得关系随着时间的推移而流动。此外，这些依赖关系产生于不同信息源的合并。最后，需要开发一个可微函数，可以输出0和1的离散二进制值。解决最初的挑战需要基于动态输入的时间感知图矩阵的推理。具体公式为，，其中表示伯努利分布，表示从节点级输入中提取的动态语义信息，表示用于获取边权重的链路预测器。在这里，采用1 × 1标准卷积来获取节点的动态语义信息，即。至于第二个挑战，可以利用可训练的节点嵌入来推断图拓扑信息。因此，可以将图学习公式扩展为，，其中表示信息融合操作，是可训练的节点嵌入。解决第三个挑战涉及应用Gumbel重参数化技术来导出离散图结构。

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? （2）? ? 本文考虑了一个简化的案例，显式地集成了动态语义信息()和拓扑信息()，而不失一般性。在这种异构条件下，图学习公式由Eq.(2)所示。具体来说，第一个和第三个元素分别反映了从拓扑和节点级输入角度推断的关联。第二个元素表示两个异构信息源之间的交互。基于此框架，论文开发了时间感知离散图结构估计模块，如图2(a)所示。 ? ? ? ? ?

? 在同质信息下推导边权值：遵循Eq.(2)，根据来自拓扑结构的和来自节点级输入的定义边权重。这里，表示内积运算符。在这个公式中，考虑到和都是可训练参数，最好直接进行内积运算。

? 在异质信息下推导边权值：在实际场景中，相邻的时间戳通常具有相似（甚至相同）的关系估计，导致图结构随时间平滑变化。为了有效地改善这种情况，选择不直接采用Eq.(2)中概述的第二个项。相反，在节点级别合并异质信息，以派生出一个进化的节点表示。然后，利用这种表示推导出演进的图结构。在之前的研究的基础上，采用门控循环单元（GRU）作为捕捉进化节点表示的方法。 ? ??

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?（3）

? 在Eq.(3)中，和表示可训练的权重矩阵。表示哈达玛积，表示sigmoid函数，表示正切双曲函数，表示输入窗口中节点的进化表示。同样，对于连接节点的边权重的估计采用内积操作。为了增强学习过程的稳定性，建议采用如Eq.(4)所示的多头变化。

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?（4）

? Eq.(4)中的表达式由几个元素组成，包括表示LayerNorm的LN。非线性映射和对应第k个头的两个不同映射，而表示每个头的维度。为了考虑一般的变化模式，将应用于边权重。最后，将个子空间获得的值相加以生成最终的边权重，如Eq.(5)所示。

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? （5）

? 其中指共享的可训练权重。它由两个部分组成，第一个部分用于获取关联，第二个部分表示残差连接，以提高模型的易学性。

? 参数化：为了通过采样获得离散图结构并满足可微性，应用了Gumbel重参数化技术：，其中，，表示sigmoid，表示温度，它是一个超参数，用于管理离散分布和连续分类密度之间的插值过程，给定值为0.5。此外，表示节点和在时间窗口上的概率链接。为了推导概率，利用通道注意力（SENet）和一个链接预测器。前者自适应地确定三个学习到的边权重的比例，后者生成链路概率。具体来说，该过程的计算公式如下：。其中，和是压缩和激活操作，为通道相乘。链接预测，沿着通道尺寸进行卷积，即。链接预测器的输出一个标量，指示节点和之间的连接概率，最后激活函数可以在一个sigmoid，例如。类似于之前的研究，例如NRI和GTS，直接使用近似来代替概率。因此，最终优化方程可以表述如下：

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? （6）

2.2.2 时间卷积模块（Temporal Convolution Module，TC Module）

? 本文在时间卷积模块中采用了一种基于CNN的方法，提供了并行计算和稳定的梯度。为了促进长期依赖性，引入了空洞卷积，通过以指数方式扩展层的深度来增强感受野。更准确地说，给定输入序列，它可以在数学上定义为：

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?（7）

其中代表用于管理跳跃距离大小的膨胀因子，指大小为的卷积卷积核。为了同时捕获跨多个尺度的时间依赖性，采用了多个卷积核，每个卷积核具有不同的大小，利用扩张的inception层方法。特别地，使用了4个不同大小的卷积核来捕获不同的时间模式。扩张的inception层通过Eq.(8)表示。

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?（8）

其中四个卷积核的输出被裁剪以匹配所使用的最大卷积核的长度。为了对跨网络层的信息流施加更大的控制，纳入了一种门控机制，称为门控TCN，其中包含了一个输出门。更具体地说，两个inception层的输出，和，被传递到两个不同的映射函数中。这种门控机制的数学表达式如下：

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?（9）

在门控TCN方法中，有几个模型参数，包括、、和，而表示元素乘积。门控TCN架构由两个卷积模块组成。第1层使用映射函数作为TC模块的输出，第2层通过sigmoid作为门控结构负责调整信息的输出量。

2.2.3 动态个性化图卷积模块（Dynamic Personalized Graph Convolution Module，DPGC Module）

? 本文假设多元时间序列可以表示为一个非线性的自回归外源模型，其中变量受到外源序列及其固有的演化模式的影响。然而，目前的时空图神经网络往往忽略了变量的自演化模式。此外，外源序列和自进化模式对未来结果的影响是动态的和异构的。为了解决这些限制，设计了具有时空感知节点重启概率的动态个性化图卷积（DPGC），如公式(10)所示。

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?（10）

? 其中，为节点自演化模式的影响力，为传播深度。表示过渡矩阵，其中来自Eq.(6)，表示度对角矩阵。表示识别模块在时间窗口中捕获的节点自身的演化模式。该方法在信息传播的每一步衡量自身及其邻居节点的影响力。

? 首先引入了节点的自进化模式。受STID的启发，采用了由三个不同的可训练嵌入矩阵和多个全连接层组成的识别模块，如图2(b)所示。为简洁起见，全连接层简称为。首先使用全连接层对输入进行变换，即，其中，是隐藏维度。然后，通过使用定义四中的嵌入矩阵、和，附加，其中表示包含自己的时间和空间特性的变量的表示。然后，使用提取特征，如Eq.(11)所示。

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? （11）

? 其中表示第层，。为了增强模型的可学习性，每一层都包含了残差连接。然后，将特征投影到全连接层以得到，即。

? 为了对自身模式和外部影响的集成模式的动态性和异质性进行建模，采用注意力机制来学习相应的注意力，其中表示、在第步传播时的注意力值。这里，表示所有的一个向量。以第个节点为例，其原始节点特征和聚合特征分别为和。

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? （12）

? 如Eq.(12)所示，使用原始节点特征作为query，聚合特征作为key，通过两个非线性变换(和)来提取特征。然后，将这两个特征相加，并通过激活函数得到步处的权重。类似地，可以得到步处自进化模式的权重。然后，使用softmax将权重，进行归一化，以获得最终的注意力值。

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? （13）

? 越大，表示节点对应的外部信息越重要。注意力权重的确定综合考虑了节点的自进化模式和聚合特征，以响应节点的动态时序特征和个性。结合Eq.(10)，最终的图卷积如Eq.(14)所示。?

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? （14）

2.2.4 优化目标（Optimization Objective）

? 之前的研究表明，联合优化模型参数和图学习层是有好处的。为了在一个框架内同时学习节点自身和外部关联的演化模式，研究并比较了3种方法的性能。在第一种方法中，通过平均节点的自进化模式及其外部关联的预测结果来计算最终结果。在第二种方法中，网络使用多个损失进行训练，其中基于节点自进化模式的预测结果被视为辅助任务。最后一种，通过所提出的动态个性化图卷积模块优化非常简单的优化最终输出，如图2所示。实验测试表明，第三种方案的结果最优。

? 所提出的框架利用残差连接将信息传输到由两个卷积层组成的输出模块，以将特征转换为所需的维度。该过程的数学表达式为。输出尺寸根据预测要求确定。如果预测任务专注于预测未来的特定时间步长，则将其称为单步预测任务，并将期望输出维度设置为1。另一方面，如果要预测多个未来步骤，例如对于下一个P步的未来值，必须调整期望的输出维度并将其设置为P。根据优化目标更新模型权重，本文选择平均绝对误差（MAE）作为优化目标，定义如下：

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? （15）

其中表示TPGCN的所有可训练参数。

Algorithm 1