基于循环神经网络的在线动态网络嵌入算法

黄海威 何慧敏 吕胜飞

(中国科学技术大学计算机科学与技术学院 安徽 合肥 230027)

0 引 言

在日常的生活和研究中有着许多网络型的数据，例如社交网络和购物网络。但通常这些现实世界的网络规模较大且复杂，很难在相关应用中直接使用。现在通用的方法是将网络嵌入到一个可以度量和计算的稠密空间。

网络嵌入是为网络中的每个节点学习一个低维表示，其他使用节点特征作为输入的算法可直接在对应的低维空间进行。网络嵌入在一些传统的任务上有着良好的表现，例如链路预测、推荐系统及节点分类。

目前主要有两种方式来实现网络嵌入：第一种是基于矩阵分解的方法[1]，它通过分解网络的邻接矩阵或者拉普拉斯矩阵等来获取节点的低维表示；第二种是基于深度学习的方法，大部分深度学习方法都尝试去综合节点所在的结构信息来获得其低维表示[2～5]。

但上述提及的算法大多是适用于节点和边均为已知且固定的静态网络。然而，现实中许多的网络有着高度的动态特性，例如社交网络、金融交易网络和电话网络。这些网络会频繁发生改变并且在演变过程中留下丰富的历史信息。当网络发生改变时，静态网络嵌入算法需要重新在新的网络上运行一次，这通常会消耗掉大量的时间和计算资源。

动态网络通常有两类：一种是随着时间推移其拓扑图的节点和边会增加或者减少；第二类则是网络的边会包含时间信息，例如电话网络。其学习与训练属于动力学系统学习的范畴[6-7]，可以使用多种方法进行学习，如基于集成学习[6-9]和统计模型[7,10-11]的方法，以及基于静态网络嵌入的方法。它们或多或少会遇到以下几个方面的挑战：

(1) 保持网络结构特征。一些算法通过传播节点的信息[12]或者优化衡量相邻节点距离的损失函数[13-14]来学习节点表示；还有一些则是直接学习一个从节点特征到节点表示的一个映射[15]。但这些算法在生成新的节点的表示时都无法保持复杂的网络结构特征。

(2) 不断变化的网络。为保持网络结构特性，SDNE[2]和DepthLGP[16]使用了深度神经网络模型来学习网络的低维表示。但SDNE无法处理网络节点数量的变化，而DepthLGP则无法处理网络中边的变化。基于矩阵分解的算法也同样存在这种问题。增量SVD方法[17-18]可以通过先前的SVD结果来更新节点的嵌入表示，因而不需要重新运行算法。但它也只能处理网络边的变化，并且在错误累积到一定程度的时候，需要重新运行算法来消除这些错误。

(3) 网络的演化信息。DynGem[19]使用了一个可以动态扩展的自编码器来保持网络结构特征和处理变化的网络规模。然而，它只是在旧的网络参数上训练当前的网络而抛弃了网络演变过程的历史信息。

为了提高动态网络嵌入的效果，本文提出了循环网络嵌入(Recurrent Neural Network Embedding，RNNE)。该算法基于深度学习网络，其流程和结构如图1所示。针对现有算法面临的以上三点挑战，RNNE在算法的三个主要组成部分(预处理、训练窗口和训练模型)中采取如下处理方式：

(a) RNNE网络单元示意图

(b) RNNE整体结构示意图图1 RNNE的网络单元与整体结构示意图

(1) 保持网络结构。RNNE在预处理部分中使用了多步概率转移矩阵来计算节点的特征，比起仅仅使用邻接矩阵，可以保持节点更大的邻居范围的特征。并且在训练模型中，RNNE的损失函数也同时考虑节点之间的一阶和高阶相似度。一阶相似度表示节点间是否有直接的边相连,高阶相似度则表示节点的邻居的相似度。

(2) 适应变化的网络。RNNE会根据网络的变化，灵活地添加虚拟点来维持网络结构。当有新的节点产生时，RNNE就用该新的节点替代掉虚拟点，当有节点被删除时，RNNE会用虚拟点来替代这些被删除的点。

(3) 储存网络的演化。训练模型的整体结构采用循环神经网络(RNN)。在该算法中，先前的节点表示会作为RNNE单元的隐藏状态被输入，因此在嵌入表示的过程中能够使用更多的网络演化信息。同时，考虑到假如一个节点的性质没有发生改变，那么其在不同时间点的表示应当是相似的，所以在训练模型的损失函数中加入了衡量网络稳定性的部分。

本文所提的RNNE算法主要有以下三方面的特点和贡献：(1) RNNE在训练的时候同时考虑了网络的一阶和高阶相似度，因此可以在嵌入空间中更好地保持网络原本的结构特征。(2) 通过添加虚拟点，RNNE可以统一网络在不同时间点的规模，并且可以很容易提取网络改变的部分。(3) RNNE使用图序列作为输入，在嵌入时能够整合不同时间点的信息，有助于消除由网络波动导致的噪声的影响。

1 RNNE算法与模型

1.1 问题定义

给定一个由节点集合V和边集合E构成的动态网络G(V,E)，及其在一段时间序列中各个时间点的状态G1(V1,E1)，G2(V2,E2)，…，Gt(Vt,Et)，对Vt中的每个节点v，学习一个映射f:v→RK，其中K是一个事先给定的正整数并且K<<|Vt|。

1.2 模型描述

网络在每个时刻的固定状态称之为快照，例如定义中的G1(V1,E1)，RNNE使用离散的网络快照序列来表达动态网络，网络的动态变化相当于不断有新的快照产生。

RNNE模型基于两个基本假设：(1) 目标网络是稳定的，也就是说，在短时间内不会有太多的节点和边的性质发生改变；(2) 网络的规模是有限的，因为任何一个系统都不能接受没有规模上限的输入。

在具体实现过程中，RNNE不会将整个网络序列作为输入，一方面是因为过旧的时间点的网络状态可能已经过时，另一方面则是太长的输入会消耗较多的计算资源。因此，RNNE利用一个固定长度的窗口来放置最新部分网络快照，同时会对极有可能发生性质改变的节点进行检测，并将其从训练节点中剔除。

仅通过一个时刻的状态来表示动态网络节点将会损失部分网络信息，因此RNNE在训练过程中会同时考虑节点的当前状态和此前的若干个状态。鉴于循环神经网络(RNN)[20]对前序信息的记忆能力，RNNE使用一个隐藏状态来表示一个节点先前的信息。

总体而言，RNNE首先会选择出合适的节点，然后使用模型的隐藏状态和节点的特征作为输入来优化节点的各项相似度。

1.3 预处理

每个节点都会预设置一个“state”属性，并且初始化为“normal”，用来表示该节点为一个普通节点。为了保持输入规模的统一，本文定义了一类虚拟节点，其为不与任何其他的点相连的孤立点，作用是为了帮助统一不同时刻网络的规模。当有新的节点产生时，RNNE就用该新的节点替代掉虚拟点，当有节点被删除时，RNNE会用虚拟点来替代这些被删除的点。虚拟点的“state”被设置为“virtual”。如果Gk的节点数目|Vk|没有达到规定的上限N，就在Gk中添加虚拟点直到|Vk|=N。

在训练之前，将需要训练的网络快照逐个添加到训练窗口中。当新的快照到达时，如果它属于第一种动态网络的类型，即随着时间推移其拓扑图的节点和边会增加或者减少的网络，可以直接将其加入训练窗口，否则将其与上一个快照的增量部分放入训练窗口。如果训练窗口达到上限，就将最早的快照移出，并且检查所有的节点来剔除那些性质可能发生改变的点。

为了在训练时更好地保持节点的高阶相似度，采用下面的方式来计算节点的特征。

首先，定义函数normalized表示矩阵A中每一个元素都会除以所在行的最大值，以此得到矩阵元素的规范化表示,其表达式为：

(1)

基于normalized函数，假设Pk∈RN×N是Gk的单步概率转移矩阵，矩阵网络的特征矩阵Xk计算如下：

(2)

1.4 模型训练

假设在训练窗口中已经有n个网络快照，分别为Ga+1,Ga+2,…,Ga+n，表1展示了下文出现的符号的含义。

表1 符号解释

RNNE单元的整体结构是一个自编码器。其中编码器E由多层非线性全连接层组成，用于将输入数据映射到嵌入空间。解码器D也同样由多层非线性全连接层组成，用于将节点的表示进行重构。给定输入数据后，每个RNNE单元将会进行如下计算：

(3)

自编码器的目标是为了最小化输入和输出的重构误差，其损失函数计算如下：

(4)

正如文献[23]里描述的，虽然最小化重构误差不能确保样本在嵌入后的相似度，但其可以让嵌入过程的数据流型更加平滑，而这一点可以有助于保持样本嵌入后的相似度。也就是说，对于相似的输入会容易有相似的输出，即两个节点拥有相似的特征，那么其嵌入表示也会相似。同时，如果自编码器可以有效地从节点嵌入表示重构节点的特征，则可以说明嵌入表示中含有代表节点特征的足够信息。

尽管在Mk和xui,k中有大量的0元素，但实际上更关心的是其中的非0元素。因为0元素不一定表示两个节点之间没有关联，而非0元素以明确表示两个节点确实有一定程度的关联，在学习过程中过度关注0元素可能会导致隐含的节点关系难以被挖掘。因此，本文借鉴SDNE的方法，在计算重构误差时，赋予0元素和非0元素不同的权重。得到新的损失函数如下所示：

(5)

式中：⊙表示哈德玛积;Wui,k={wui,j,k}j=1N+d，如果mui,j,k∈Mk=0,wui,j,k=1,否则wui,j,k=β>1。通过最小化损失函数，拥有相似邻居结构的节点得到的表示结果在嵌入空间中会更加靠近。

除了考虑节点的邻居结构，也对节点之间直接相连的边予以关注。由边直接相连的节点，其联系也更紧密，在嵌入空间中的距离应该更接近。使用一阶相似度来衡量这种关系，其计算方式如下：

(6)

如果mui,uj,k>0，表示节点vui,k和vuj,k有相连的边。

在上面的部分中只考虑了每个网络快照各自的特征。假如网络中的一个节点在演化过程中性质没有发生改变，倾向于将它映射到嵌入空间的同一个位置。在选取训练样本节点时，所有样本的“state”属性均为“normal”，即这些点的性质大概率没有发生改变，所以这些点的在不同时刻的表示应尽量接近。其损失函数为：

(7)

综上所述，为了保持节点的一阶相似度、高阶相似度和稳定性，结合式(5)-式(7)得到了最终的损失函数为：

(8)

式中：α、γ、Wui,k中的β均为模型的超参数。

最后整个模型的参数θ可以通过梯度下降法来更新，即：

(9)

式中：η为模型的学习率。

1.5 复杂度分析

通过式(8)可知，在一次迭代中，RNNE的训练时间复杂度是O(nb(N+d)D)，其中n为训练窗口的容量，b为批(batch)的大小，N是网络节点规模上限，d为嵌入空间的维数，D是模型中间层规模的最大值。通常n、b和d为预设的常数值，N与网络的实际规模线性相关，D取决于d而与节点数目无关。由此可将RNNE在一次迭代训练的时间复杂度表示为O(N)，其与网络的实际规模线性相关。

2 实验过程

2.1 数据集

实验采取了5个数据集，分别为Wiki、email-Eu-core、blogCatalog、CA-CondMat和CA-HepPh，经过调整和选取每个数据集中网络序列的长度均为14。其节点和边的范围如表2所示，由于网络的动态性，网络节点和边数可能在不断发生改变，因此使用其改变范围来进行表示：

表2 不同数据集节点和边的信息

(1) Wiki：该数据集为Wiki上的引用网络，并且每个节点都有类别信息，共有17个不同的类别。

(2) blogCatalog[24]、email-Eu-core[25]：这2个对应社交网络。其中blogCatalog网络节点有39个类别，email-Eu-core网络节点有42个类别。

(3) CA-CondMat、CA-HepPh[25]:数据集对应arXiv上的引用网络。由于其没有类别信息，所以在实验中这2个数据集不参与节点分类任务。

2.2 基准算法及参数设置

本文实验将使用以下算法作为基准算法进行对比。对于其中的静态网络嵌入算法，将会在数据集的每个快照上都执行一次计算过程。

(1) SDNE[2]：该算法使用了自编码器结构的模型，并且通过最小化一阶相似度和二阶相似度的损失函数来训练模型，将其自编码器规模设置为encoder_layer_list=[1 000,128]，一阶相似度权重设置为α=10-6，非0元素权重设置为β=5。

(2) Line[4]：与尝试学习映射规则不同，该算法直接对从节点特征到嵌入空间的一一映射进行学习，其损失函数同时考虑了一阶和二阶相似度。

(3) GraRep[26]：该算法考虑了节点的高阶相似度，然后使用SVD获得网络的嵌入表示。将其高阶相似度计算上限设置为Kstep=4。

(4) Hope[27]：该算法从邻接矩阵构造了一个非对称关系矩阵，然后通过JDGSVD[28]获得节点的低维表示。

对于本文提出的RNNE模型，自编码器的规模大小在不同数据集上有所不同。自编码器的规模由组成其的各个全连接层的规模来描述,前面的数字表示编码器的规模，最后一个数字表示输出的节点表示的维数，解码器则与编码器规模对称。例如2 128-128表示共有三层，其规模分别为2 128、128和2 128。具体设置如表3所示。其中的超参数α、β、γ通过网格搜索来调整:α∈[10-6,1],β∈[1,10],γ∈[0,10]。在搜索过程中，由于α表示损失函数中一阶相似度和高阶相似度的比重，其影响最大，故优先对α进行搜索，其次是β，最后是γ。并且先通过大步长搜索确定合适的范围，有必要的话，再通过小步长搜索优化结果，以此尽可能减少搜索次数和计算量。

表3 RNNE模型在不同数据集上的自编码器规模

2.3 评估方式

本文实验测试了算法在三种任务上的表现，分别为重构、节点分类和链路预测。

在重构和链路预测中，使用precision@k来衡量算法的效果，对于网络G(V,E)，其定义如下：

(10)

式中：index(e)表示e在预测结果中的序号。

在节点分类中，使用micro-F1和macro-F1来衡量算法的效果。对于一个给定的标签L，TP(L)、FP(L)和FN(L)分别表示样本中被正确预测为L、被错误预测为L和是L但没有被预测为L的数目，C为所有标签的集合，则micro-F1和macro-F1的计算过程如下所示：

(11)

考虑到每个数据集有14个网络快照，部分算法需要在每个快照上都运行一次，因此取precision@k、micro-F1和macro-F1在各个快照上的平均值作为最后的结果。

3 实验结果分析

3.1 重 构

重构表示试图从节点的表示中恢复原本的网络结构。本文实验通过计算节点在嵌入空间的距离来衡量它们的一阶相似度并进一步推测是否有边相连。不同方法对应的结果如图2所示。

(a) CA-Condmat

(b) CA-HepPh图2 数据集CA-Condmat和CA-HepPh上的平均precision@k

可以看出，RNNE在这两个数据集上的表现比SDNE、Hope和Line有更好的重构效果。在k不太大的情况下，RNNE同样比Grarep表现得更好。值得注意的是，在五种算法中，RNNE、SDNE、Grarep和Line均考虑了一阶相似度或者高阶相似度，而Hope则欠缺了这方面的考量。可以看出，Hope的实验表现明显比其他四个算法更差，这说明一阶和高阶相似度对保持网络原始结构有着明显帮助。更进一步地，在考虑了节点相似度的四个算法中，RNNE和Grarep考虑节点的高阶相似度，而Line和SDNE至多只考虑到了二阶相似度，观察结果可以发现RNNE和Grarep的表现要优于Line和SDNE，在一定程度上可以说明高阶相似度的表达能力比二阶相似度的表达能力更加丰富。

3.2 节点分类

本文实验将节点的低维表示作为特征，对分类器进行训练，将分类器预测的类别和真实类别进行比较。特别地，使用LIBLINEAR[28]作为分类器，然后分别选取10%到90%的数据作为训练，其余的作为测试。不同算法在三个数据集上的分类结果如图3所示。

(a) blogCatalog

(b) Wiki

(c) email-Eu-mail图3 当训练样本比例变化时，三个数据集上的micro-F1和macro-F1

可以看出，RNNE在整体上比其他四个算法表现更优。RNNE单元采用了自编码器结构，自编码器一个重要特性即对于相似的输入会容易有相似的输出，因此对于同类节点，RNNE产生的相似低维表示也更容易让它们被分类器分成同一类。另外，RNNE和Grarep都取得了不错的表现，它们有一个很重要的共同点就是考虑了较高阶的节点相似度，很显然高阶相似度比起邻接矩阵，对节点的特征有着更为准确的刻画，也更容易区分开相似的节点和不相似的节点，对于节点分类有着非常大的帮助。

3.3 链路预测

链路预测尝试从网络中去寻找那些可能有关联但没有边相连的节点。在进行实验之前，将测试数据集中15%的网络边进行隐藏，通过节点的低维表示来预测这些被隐藏的边。在计算precision@k时，忽略那些被预测出来但已经存在于网络中的边。CA-Condmat和CA-HepPh数据集上不同算法的预测结果如图4所示。

(a) CA-Condmat

(b) CA-HepPh图4 数据集CA-Condmat和CA-HepPh上的平均precision@k

可以看出，在这两个数据集的表现中，RNNE和Grarep相比于其他三个算法有明显的优势，进一步说明了高阶相似度对于网络表示学习的重要性。在数据集CA-Condmat中，RNNE的表现要一直优于Grarep；在数据集CA-HepPh中，起初RNNE比其他算法有着更高的准确率，当k逐渐变大，Grarep的准确率超过了RNNE。但是在实际生活和研究的任务中，人们通常只会关心那些最有可能相关的结果。一方面是由于随着预测的边的增多，准确率的下降是不可避免的；另一方面，人们通常更关心的是那些最有可能存在联系的节点。所以在k较小时拥有高准确率是非常重要的。

4 结 语

本文提出了一种循环网络嵌入算法(Recurrent Neural Network Embedding，RNNE)来提高动态网络表示学习的效果。一方面，RNNE通过一阶相似度和高阶相似度维持了网络的静态特征；另一方面，为了适应动态网络的变化性，RNNE使用了虚拟点来维持网络的结构。RNNE使用循环神经网络来处理网络序列，通过传递信息来尽可能地对网络的真实状态进行嵌入，而不仅仅考虑网络在局部时间的状态。将RNNE与其他算法在不同的数据集和任务上进行了对比实验，结果说明RNNE在动态网络表示学习上能够取得较好的结果。

为了提高网络嵌入的效率，使网络状态可以得到快速的更新，在未来工作中会尝试使用注意力机制等其他方式来进行动态网络表示学习。同时，也会考虑从空间转换的角度[30-31]来解决此类问题。