一种基于时序图神经网络的节点表示方法及增量学习方法

摘要

本发明公开一种基于时序图神经网络的节点表示方法及增量学习方法，属于图表示学习技术领域。预处理操作后用带有双重注意力机制的GCN模型分别处理不同时刻的时序图快照，进行图卷积计算，求得任一时刻任一节点的结构嵌入表示；将在每一时刻任一节点的结构嵌入表示作为一个序列输入到t‑GRU时序网络中进行串行计算，求得任一时刻任一节点的最终的嵌入表示；针对T时刻的新数据，先将T时刻之前的中间结果存储起来；只利用一个带有双重注意力机制的GCN模型处理T时刻的增量图数据；将中间结果以及T时刻结果合成一个序列输入到t‑GRU时序网络中进行串行计算得到T时刻任一节点的嵌入表示。适用多种时序图场景，节点表示信息更丰富且准确，模型迭代收敛速度快。

说明书

技术领域

本发明涉及图神经网络、图表示学习技术领域，尤其涉及一种基于时序图神经网络的节点表示方法及增量学习方法。

背景技术

尽管传统的深度学习方法在提取欧式空间数据的特征上取得了巨大的成功，但许多实际应用场景中的数据是从非欧式空间中生成的，这使得传统的深度学习方法在处理非欧式空间数据上的表现很难令人满意。而且，由于图的复杂性以及结构不规则的性质，使得现有的深度学习方法很难捕获图节点之间的相互依赖关系。近些年，随着人们对深度学习方法在图上的扩展越来越感兴趣，在多方面因素的成功推动下，研究人员借鉴了卷积神经网络CNN、循环神经网络RNN和深度自编码器Autoencoder的思想，定义和设计了用于处理图数据的神经网络结构——图神经网络。目前，比较主流的图神经网络有GCN(GraphConvolutional Network，图卷积神经网络)、GraphSAGE(Graph Sample and Aggregate，图采样和聚合)、GAT(Graph Attention Network，图注意力网络)等等。通常用做基线或者模型改进的图神经网络是GraphSAGE和GAT，因为这两个图神经网络是利用聚合函数来聚合局部邻居信息，能通过聚合函数使得模型学习到一个节点的信息是如何通过其邻居节点特征聚合来的。

然而，现实世界中的许多应用里的图都是动态的，也就是说图的结构会随着时间不断演化。尽管，GraphSAGE和GAT模型都具有泛化能力，可以处理一小部分的未知数据，但是对于动态图尤其是时序图这种规模，传统的图神经网络很难学习到节点的时序信息。为解决这个问题，一些人提出了处理动态图的图表示学习方法。其中，基于深度学习的处理方法有DynGEM、DynamicTriad、LSTM-Node2Vec等，但是这类方法在捕获图结构信息时表现出的性能并不理想。基于图神经网络的处理方法有DySAT、EvolveGCN等，这类方法主要都是由两部分堆叠而成，一部分为GNN(Graph Neural Network，图神经网络)，另一部分为RNN(Recurrent Neura1Network，循环神经网络)。通过GNN捕获结构信息，再利用RNN捕获时序信息，但是，由于现有的这类方法在这两部分上的设计相对简单，比如，GNN部分一般为GCN或者GAT模型，而RNN部分为传统的LSTM(Long Short-Term Memory，长短期记忆网络)，这导致每一部分都没办法学习到节点的丰富信息。

对时序图来说，当新增数据不断到来时，一方面，由于时序图数据量不断增大，导致无法在内存中存储大量图快照数据；另一方面，由于图数据量的增大，导致从头重新更新模型参数的开销增大。

发明内容

针对现有技术存在的不足，本发明提供一种基于时序图神经网络的节点表示方法及增量学习方法，旨在改善现有时序图节点表示方法的不足，提高节点表示的质量，提升下游节点分类、链路预测等任务的准确率，并通过增量学习方法加快增量数据的处理速度。

为解决上述技术问题，本发明提供的技术方案是：

一种基于时序图神经网络的节点表示方法及增量学习方法，包括：对时序图快照中节点的特征向量进行预处理的步骤，还包括：为预处理后的时序图快照中节点生成带有结构信息和时序信息的节点嵌入表示的步骤。

进一步地，根据所述的基于时序图神经网络的节点表示方法，所述的为预处理后的时序图快照中节点生成带有结构信息和时序信息的节点嵌入表示的步骤，包括以下步骤：

步骤I，用每一个带有双重注意力机制的GCN模型分别处理不同时刻的时序图快照，进行图卷积计算，求得在任一时刻的任一节点的结构嵌入表示；

步骤II，将在每一时刻的任一节点的结构嵌入表示作为一个序列输入到t-GRU时序网络中进行串行计算，求得在任一时刻的任一节点的最终的带有结构信息和时序信息的嵌入表示。

进一步地，根据所述的基于时序图神经网络的节点表示方法，所述步骤I包括如下步骤：

步骤I-1，对于时序图中任一时刻的图快照，计算任一节点与其所有邻居节点的特征注意力系数；

步骤I-2，利用RWR算法计算该任一节点与其两跳邻居节点所构成的子图中的其它节点的结构注意力系数；

步骤I-3，对得到的特征注意力系数及结构注意力系数进行加权求和求得该任一节点与其邻居节点最终的注意力系数；

步骤I-4，利用图注意力网络GAT中的聚合方法对图中任一节点的嵌入向量及其邻居节点的嵌入向量进行聚合及拼接得到最终的节点结构嵌入表示。

进一步地，根据所述的基于时序图神经网络的节点表示方法，所述步骤I-2中，按照以下公式计算任一节点i与其两跳邻居节点所构成的子图中的节点j的结构注意力系数β

其中，V

进一步地，根据所述的基于时序图神经网络的节点表示方法，所述步骤I-3中，按照以下公式计算节点i与其邻居节点j之间的注意力系数c

其中，α

进一步地，根据所述的基于时序图神经网络的节点表示方法，所述步骤II中所述的t-GRU时序网络是基于对任一时刻t的GRU网络单元的输入h

进一步地，采用上述任一所述的基于时序图神经网络的节点表示方法的增量学习方法，对于某一时刻T到来的增量数据，首先，将T时刻之前所有时刻处的任一节点的结构嵌入表示作为中间结果进行存储，然后，按照步骤I的方法，只利用一个带有双重注意力机制的GCN模型处理T时刻的增量图数据，得到T时刻图节点的结构嵌入表示。最后，按照步骤II的方法，将T时刻得到的结构嵌入表示与存储的中间结果合成一个序列输入到t-GRU网络中进行串行计算，得到T时刻图中任一节点的最终嵌入表示。

进一步地，根据所述的基于时序图神经网络的节点表示方法，所述对时序图快照中节点的特征向量进行预处理的步骤，包括：针对图节点的初始特征向量进行降维处理步骤和对时序图快照进行图池化处理步骤。

进一步地，根据所述的基于时序图神经网络的节点表示方法，在所述针对图节点的初始特征向量进行降维处理步骤中，将维度为D的图节点特征向量输入到双层特征自编码器的输入层，将其映射为一个维度为d的低维嵌入表示，并通过隐藏层得到输出的低维嵌入表示，其中d＜D。

进一步地，根据所述的基于时序图神经网络的节点表示方法，所述对时序图快照进行图池化处理步骤中，利用图池化自编码器Graph U-Nets对每一张图快照进行图池化操作。

与现有技术相比，本发明具有如下有益效果：本发明的基于时序图神经网络的节点表示方法及增量学习方法适用于多种时序图场景，如引文网络、通信网络和社交网络等，充分利用了节点的拓扑结构信息及时序信息，能够使节点表示获得更丰富的信息，同时为下游节点分类、链路预测等任务提供更准确的节点表示，提高任务的准确率。同时，通过减少大量的重新计算来处理增量数据，加速模型迭代收敛的速度。

附图说明

图1为本发明的基于时序图神经网络的节点表示方法流程图；

图2为本发明采用基于时序图神经网络的节点表示方法的增量学习方法流程图；

图3为本发明实施例节点预处理使用的自编码器结构图；

图4为本发明实施例图池化操作的框图；

图5为本发明实施例处理时序图的架构图；

图6为本发明实施例改进的t-GRU网络结构图；

图7为本发明实施例处理增量数据图的架构图。

具体实施方式

为了便于理解本申请，下面将参照相关附图对本申请进行更全面的描述。附图中给出了本申请的较佳实施方式。但是，本申请可以以许多不同的形式来实现，并不限于本文所描述的实施方式。相反地，提供这些实施方式的目的是使对本申请的公开内容理解的更加透彻全面。

在本发明提供的基于时序图神经网络的节点表示方法及增量学习方法中，对于时序图的处理来说，如图1所示，首先，对每一张时序图快照进行预处理操作，包括特征降维及图池化操作。接着，用双重注意力网络模块中每一个带有双重注意力机制的GCN模型分别处理不同时刻的时序图快照，进行图卷积计算，求得在任一时刻t的任一节点v的结构嵌入表示。最后，将在每一时刻t的任一节点v的结构嵌入表示作为一个序列输入到t-GRU时序网络中进行串行计算，求得在任一时刻t的任一节点v的最终的嵌入表示。根据本发明的基于时序图神经网络的节点表示方法编写的程序，包括对初始时序图特征降维模块、图池化模块、双重注意力网络模块和t-GRU时序网络模块。

在本发明提供的基于时序图神经网络的节点表示方法及增量学习方法中，对于增量数据处理来说，如图2所示，为了减少模型更新时不必要的重新计算，最主要的就是要减少对旧数据的使用。假设在T时刻，有一批新数据到来，即增量数据。首先，将T时刻之前所有时刻由带有双重注意力机制的GCN模型产生的中间结果存储起来。然后，只利用一个带有双重注意力机制的GCN模型处理T时刻的增量图数据。最后，将存储的中间结果以及T时刻由GCN模型生成的结果合成一个序列输入到t-GRU时序网络中进行串行计算得到T时刻任一节点的嵌入表示。这样，在反向传播时就不需要对T时刻之前的带有双重注意力机制的GCN模型进行参数更新，大大减少了重新计算带来的计算开销。

具体地，本实施方式的基于时序图神经网络的节点表示方法，包括以下步骤：

步骤1：对每一张时序图快照进行预处理操作。

该步骤中将对每一张时序图快照进行预处理，包括：特征降维和图池化处理，具体包括如下步骤：

步骤1-1：针对图节点的初始特征向量进行降维处理，将图节点的特征向量映射到低维向量空间中。

一般情况下，图节点的初始特征向量为one-hot向量，特征维度比较大，如果使用one-hot向量进行模型训练的话，可能会增加计算开销。所以需要进行降维处理，将图节点的特征向量映射到低维向量空间中。本实施方式中将维度为D的图节点特征向量输入到图3所示的双层特征自编码器的输入层，将其映射为一个维度为d(d＜D)的低维嵌入表示，并通过隐藏层2得到输出的低维嵌入表示。图3示出的是特征自编码器Autoencoder的一般结构，主要分为编码器和解码器两部分。

步骤1-2：对时序图快照进行图池化处理，将快照中不重要的节点池化掉。

由于时序图中每一个图快照的节点的数量都很大，且存在一些表示信息不够丰富的节点，所以会造成不必要的计算开销。本实施方式中利用图池化自编码器GraphU-Nets对每一张图快照进行图池化操作，将快照中不重要的节点池化掉，保留相对有用的节点。

图4示出的是本实施方式进行图池化操作的过程，它相当于卷积神经网络中的池化层，除输入输出外，还包括投影、节点选择、门控三个操作。其中，池化层的输入分别为图快照的邻接矩阵A

其中，x

接着，采用k-max池化操作从y中筛选出信息较丰富且最能表达原图信息的k个图节点的索引。最后，图池化的传播规则及新的邻接矩阵A

idx＝rank(y，k) (3)

A

其中，y表示所有节点的特征向量经过投影后得到的向量；rank(·，·)表示节点的标量投影的排序操作；idx表示y中值最大的k个节点的索引；sigmoid(·)表示神经网络中的激活函数；y(idx)表示按索引idx将y中对应的值提取出来构成一个新的向量；

步骤2：为预处理后的时序图快照中节点生成带有结构信息和时序信息的节点嵌入表示。

对预处理后的时序图进行处理的程序，包括双重注意力网络模块和t-GRU时序网络模块，如图5所示，下半部分为由多个带有双重注意力机制的GCN模型构成的双重注意力网络模块的架构图，上半部分为由多个t-GRU网络单元连接成的t-GRU时序网络模块的架构图。步骤2将进一步包括如下步骤：

步骤2-1：利用双重注意力网络模块中每一个带有双重注意力机制的GCN模型分别处理不同时刻的时序图快照，进行图卷积计算，为图快照中的节点捕获其结构信息，求得在任一时刻t的任一节点v的带有结构信息的结构嵌入表示。

首先对于时序图中任一时刻t的图快照，计算任一节点i与其所有邻居节点的特征注意力系数α

其中，W表示一个共享参数矩阵；向量

接着，在求得了特征注意力系数的基础上进行结构注意力系数的计算。利用重启随机游走RWR(Random Walk with Restart)算法计算任一节点i与其两跳邻居节点所构成的子图中的其它节点的结构注意力系数β

其中，V

对得到的特征注意力系数及结构注意力系数进行加权求和求得节点i与其所有邻居节点最终的注意力系数c

其中，α

最后，利用图注意力网络GAT中的聚合方法对图中任一节点的嵌入向量及其邻居节点的嵌入向量进行聚合及拼接操作得到最终捕获结构信息的节点嵌入表示。这样，就利用了特征注意力与结构注意力相结合的这种双重注意力机制得到任一节点v在任一时刻t的结构嵌入表示

其中，

步骤2-2：将在每一时刻t的任一节点v的嵌入表示作为一个序列输入到t-GRU时序网络中进行串行计算，求得在任一时刻t的任一节点v的带有结构信息和时序信息的最终的嵌入表示。

传统的循环神经网络RNN能够捕获节点大部分的长期记忆信息与短期记忆信息。常见的RNN网络有LSTM、GRU，由于GRU网络的参数要比LSTM网络的参数少，且捕获长短期记忆信息的能力二者大致相同，所以，本实施方式中使用的是GRU网络，并在GRU网络的基础上进行改进。直观来看，时间较为久远的节点变化的长期记忆信息应该较大程度地被遗忘，而靠近当前时间点的节点变化的短期记忆信息对节点信息的更新影响更大。这样，对于一些变化不频繁的节点，节点变化的时间间隔信息Δt变得尤为重要。基于这种观点，本实施方式中通过修改GRU网络单元的输入将Δt这一关键信息引入进来。图6示出的是本发明对GRU网络输入进行改进而得到的t-GRU时序网络单元结构。具体改进内容包括：修改任一时刻t的GRU网络单元的输入h

其中，h

采用上述基于时序图神经网络的节点表示方法的增量学习方法，如图7所示，对于某一时刻T到来的增量数据，首先，将任一t时刻处的(t＜T)任一节点v的结构嵌入表示作为中间结果进行存储，对应图7中的就是虚线框中每个带有双重注意力机制的GCN模型训练后得到的任一节点v的中间结果

在本实施方式中，在无监督环境下利用基于图的交叉熵损失函数更新上述提到的模型，包括对步骤2中的双重注意力网络及t-GRU时序网络模型进行模型参数的更新，对于基于时序图神经网络的节点表示方法的增量学习方法，只需要对T时刻之前的所有双重注意力模型之外的所有模型进行更新。

应当理解的是，本领域技术人员在本发明技术构思的启发下，在不脱离本发明内容的基础上，可以根据上述说明做出各种改进或变换，这仍落在本发明的保护范围之内。