基于循环采样聚合邻居信息的动态网络表征方法

高亚男， 刘 勇，惠 丽

(黑龙江大学 计算机科学技术学院，哈尔滨 150080)

0 引 言

信息网络是信息的重要表达形式，随着大数据和深度学习技术的突飞猛进，人工智能研究正面临新一轮的爆发式发展，能否对信息网络做出有效合理的数据分析是当今学术研究的热门话题。从宏观意义上讲，基于网络的特征学习目的是寻找一种途径可以有效探索整合网络结构。基于图的特征学习旨在将图表示为微观意义上的低维向量，同时保持图结构。图形分析旨在从图形数据中挖掘有用的信息。表示学习了获取数据表示。在构建分类器和其他预测变量时，容易提取有用的信息。有效的特征学习分析对于许多应用程序(例如节点分类和链接预测)很有用。通过分析社交网络的用户交互(例如微博中的评论/关注)情况，可以为用户推荐朋友。

关于信息网络的研究大都是在静态网络基础上，而现实生活中不仅网络拓扑会变化，网络中的节点也会发生交互动作，这两种动态的变化过程对网络的表示学习有很重要意义，动态信息网络表示学习问题近来越来越受关注。网络的拓扑结构随时间而变化，不断建立新的关系，生成新的内容，并反映在节点属性中[1]。同时，节点之间可能会频繁发生交互，例如在社交网中节点之间通过边的交互可理解为一次信息的传达。生活中还有其他的很多交互模式，而这些动态的变化以及特征和属性是静态网络不曾包含的，相比之下动态网络更切合于实际，并且包含更多的网络信息以及特性，更有力于模型的学习。因此，如何有效地建模和分析这些动态信息网是一个非常重要的研究课题。

基于动态信息网提出一种新颖的方法RSage，将RNN与GCN相结合，通过GCN对邻居节点采样、聚合来学习网络的拓扑结构，而后利用RNN来学习网络的时间序列属性。得到的表征结果在3个真实数据集上实验，得到较优越的结果。

1 相关工作

深度学习浪潮引入了大量未经监督和监督的表征学习方法。动态表征方法的热门之一是时间点过程，它利用时序点建模来学习动态网络的时间属性。Know-Evolve和DyRep将边缘建模为点，使用神经网络将节点作为输入嵌入并参数化强度函数[2-3]。HTNE通过Hawkes时序点过程对网络中节点进行时序建模，利用历史节点对当前影响作用，来预测当前节点的表征，距离当前节点越远的历史节点影响力越小[4]。同时，它使用注意力机制来学习归纳历史节点对当前节点的影响，该方法具有时间上的连续性，更有利于动态网络表征学习。另一个动态表征方法的热门类别是图神经网络(GNN)和循环神经网络(RNN)的组合，利用GNN捕获网络拓扑结构，用RNN学习网络中的时序特征。GNN通常使用的是图卷积神经网络(GCN)。GCRN提出两种模型:①将网络作为GCN输入，得到初步节点表征，然后将其送入长短期记忆网络(LSTM)中得到最终表征；②将GCN、LSTM进行融合，利用GCN来扩展LSTM，用GCN替换完全连接层，通过该方法直接得到最终结果[5]。在WD-GCN/CD-GCN和RgCNN中类似地探索了第一个想法[6-7]。STGCN提出由ST-Conv块组成的复杂架构。这种结构被应用在时空交通数据(命名为STGCN和ST-Conv)上，其中使用图卷积处理空间信息[8]。

2 预备知识

2.1 基本定义

动态网络G可以表示为一组快照，既{G1,…,GT}，Gt=(V,Et,At)(t∈[1,T]) 为t时刻的快照，V为所有节点的集合且|V|=n，Et为t时的边集合，At∈Rn×n为Gt在t时的邻接矩阵，At(i,j)=1为vi和vj在t时刻有边相连，反之At(i,j)=0为没有边。为了更好计算，默认本文所有动态网络均为无向图。

2.2 目标

给定一个动态网络G，通过捕获网络的结构和演化来获取动态网络表征，即在得到低维节点表征向量ht：V→Rdh，ht∈Rn×dh。将ht向量用于节点分类、链路预测等任务。

2.3 图卷积神经网络

GraphSAGE[9]方法是在GCN基础上扩展并改进，解决了GCN的局限性，并具有归纳性，它主要利用采样邻居节点信息、聚合邻居节点信息来更新相应节点的表征，随着周边节点的改变，表征结果也可以学习到相应的变化。

算法 1: GraphSAGE 表征生成算法Input:图Gt=V,Et,At ;深度K; 权重矩阵Wk,∀k∈1,…,k ;非线性函数σ; 可微聚合函数AGGREGATEk,∀k∈1,…,K ;邻域函数N:v→2vOutput:表征向量 xv,所有v∈V1z0v←At,∀v∈V;2fork =1…K do3forv∈V do4z0Nv ←AGGREGATEk zk-1u,∀u∈Nv 5zkv←σWk·CONCATzk-1v,zkNv 6end7 zkv←zkv/zkv2,∀∈V8end9 xv←zKv,∀v∈V

2.4 循环神经网络

循环神经网络(RNN)是一种经典基于时间序列建模的方法，常用在含有时序属性的各个领域的数据上建模。两种经典RNN方法为长短期记忆网络(LSTM)和门循环单元(GRU)。

2.4.1 长短期记忆网络(RNN)

LSTM是一种特殊的RNN，可以有效防止梯度爆炸和梯度消失问题，同时克服了RNN无法处理远距离依赖的问题。LSTM具体公式为

(1)

2.4.2 门循环单元(GRU)

GRU同样很大程度上解决了RNN中的梯度消失问题，是LSTM的一种变体。GRU与LSTM在许多方面效果相近，但是结构相对更加简单，具体公式为

(2)

图1 RSage模型Fig.1 RSage model

3 方 法

提出了一种新方法RSage，分为RSage-LS和RSage-GRU两个模型。由于GraphSAGE[9]的归纳性，该方法不仅适用于小规模数据，也可以应用在大规模动态网络上，RSage架构见图1。由图1所见，GCN模型指的是GraphSAGE[9](GraphSAGE模型如图中所示)，同时采用常用的LSTM、GRU两种RNN模型。在t时刻输入快照，利用GCN学习拓扑关联结构，GCN通过采样、聚合邻居信息归纳出初步表征xt，用RNN学习到快照中隐含的时间信息，得到最终表征结果ht。

3.1 RSage-LS方法

将LSTM与GraphSAGE[9]结合。LSTM见式(1)，GraphSAGE[9]模型核心算法见算法1。RSage-LS公式为

(3)

其中，邻接矩阵At为输入；x(t)为GraphSAGE[9]得到的结果，后通过LSTM模型得到最终表征ht。

3.2 RSage-GRU方法

将GRU与GraphSAGE[9]模型结合。GRU见式(2)，GraphSAGE[9]模型核心算法见算法1。RSage-GRU公式为

(4)

其中，邻接矩阵At为输入；x(t)为GraphSAGE[9]得到的结果，后经过GRU模型得到最终表征ht。

4 实 验

4.1 数据集

在3个可获得公共的真实数据集上实验(表1)。

4.1.1 Stochastic Block Model(SBM)

SBM是一种流行的随机图模型，用于模拟群落结构和进化。遵循Goyal Dyn GEM[10]模型来生成综合数据。

4.1.2 UC Irvine message

UCI是一个来自加利福尼亚大学欧文分校学生的在线社区，其中该社交网络的链接指示用户之间发送的消息。

4.1.3 Elliptic

Elliptic是比特币交易的网络，其中每个节点代表一个交易，边缘表示支付流量。 大约有20%的交易已映射到属于合法类别而非非法类别的真实实体。目的是对未贴标签的交易进行分类。

表1 数据集Table 1 Data sets

4.2 对比方法

本文将RSage方法与以下5种方法作对比。

DynGEM[10]：基于图自动编码器的无监督节点嵌入方法，可减少重建损失以及嵌入节点之间的距离空间，它的一个特点是架构的深度适应图的大小；同时利用历史学习到的参数对当前模型初始化训练。以加快学习速度。

EvolveGCN[11]：利用RNN对GCN进行了扩展。在该模型中，GCN主要用来学习网络的拓扑结构特征，RNN用来学习时序特征并对GCN的权重进行更新，同时GCN和RNN共同参与更新节点表征。

GCN-GRU[12]：GCN模型与节点嵌入的递归模型(GRU)共同训练。将这种方法称为GCN-GRU，它在概念上与文献[12]的方法1相同，只是它们的GNN是ChebNet[13],而递归模型是LSTM，用GCN、GRU分别替换原文中GNN、LSTM方法。

GCN[13]：采用没有任何时间建模的GCN。对于所有时间步长，使用一个单一的GCN模型，并且损失沿时间轴累积。

4.3 任务

4.3.1 节点分类

由表2可见，RSage-LS方法在节点分类任务上的表现略优越于其他方法，通过采样、聚合邻居信息来归纳表征，当网络规模较大时，可以采样到的信息和特征更多，效果就会更好。

表2 节点分类结果

4.3.2 链路预测

由表3可见，RSage在两个小规模数据集上的表现一般。小规模网络一般比较稀疏，对于邻居信息来说可用的信息较少，本文方法在两个小规模网络上得到的结果并非十分理想。

表3 链路预测结果Table 3 Results for link prediction

5 结 论

提出的方法主要针对边增加、边减少情况的信息网，将GCN和RNN结合，利用了2种方法各自的特点来学习节点表征，首先将动态网络分割成多个快照，以快照的形式作为输入，利用GCN捕获快照的拓扑信息，用RNN学习网络的时间维度。在3个真实数据集上实验，实验结果显示，该方法在大规模数据上具有较好的表现。