一种基于深度RTRBM的动态网络链路预测方法

潘嘉琪，邹俊韬

(南京航空航天大学 计算机科学与技术学院，江苏 南京 211106)

0 引 言

链路预测不仅能够帮助人们挖掘网络内部的结构模式和分析网络动态演化的规律，而且还在学术推荐、犯罪治安监控、基因交互研究等诸多领域中体现出了实际的应用价值。

Sarkar等人[1]将非参数方法运用到动态网络的链路预测问题中，并使用局部敏感哈希加速了贝叶斯推断过程。Zhai和Zhang[2]试图通过结合矩阵分解和自动编码机来处理链路预测问题，并同时利用Dropout技术来进行模型的训练以防止过拟合现象。Zhu等人[3]通过矩阵分解来对动态网络进行链路预测，并且通过理论分析，提出了一种局部块坐标下降的优化策略。Zhang等人[4]提出了一种基于卷积神经网络的链路预测模型，该模型首先提取目标节点对的k步局部子图，然后再通过标签传播算法对子图内的每个节点进行哈希编码，最后将编码后的特征用于卷积神经网络进行有监督的分类学习。Keikha等人[5]提出了一种基于深度学习的链路预测框架，该框架利用网络表征学习来构建节点对间的特征，然后利用分类器进行链路预测。Zhang等人[6]利用堆叠自动编码机对引文网络进行链路预测，取得了不错的预测结果。

传统的关于动态网络链路预测的方法都是在单个时态下执行网络的特征提取，然后通过加权组合进行预测，这很可能会导致同一节点对在特征空间中的位置在两个邻近的时态间出现较大的波动，从而造成误差。为了解决动态网络链路预测中节点对的时序特征提取面临的问题，文中提出一种基于深度RTRBM的动态网络链路预测方法。通过使用网络嵌入学习算法构建动态网络的时序特征，再结合深度学习理论将多个改进后的RTRBM纵向堆叠以构成深度学习结构，最后结合Logistic回归分类器对动态网络中的链路进行分类和预测。

问题定义：动态网络链路预测是指根据网络前T个时间快照{G1,G2,…,GT}对应的结构信息来预测网络在T+1时刻中的链路状态。其中Gt=(Vt,Et)表示网络在t时刻的状态，Vt表示t时刻网络中的节点集合，Et表示t时刻网络中的边集合，T为网络的时间快照个数。为了便于分析网络拓扑结构的演化机制，文中暂不考虑节点随时间变化的情况，即Vt保持不变。

1 改进的循环时序受限玻尔兹曼机

1.1 改进的循环时序受限玻尔兹曼机

循环时序玻尔兹曼机(recurrent temporal restricted Boltzmann machine，RTRBM)[7]是由一系列条件受限玻尔兹曼机(conditional restricted Boltzmann machine，CRBM)[8]组成的链式结构，其主要作用是对带有时序关系的数据进行建模，其结构如图1所示。

图1 RTRBM结构示意图

在图1中，上面用虚线框住的部分是一个基本的RBM结构，其作用是提取数据的隐含特征，而下面虚线框住的部分是一个循环链式结构，其目的是对数据的时序特性进行建模表达。其中，vt∈RNv和ht∈RNh分别为样本对应于t时刻的数据和隐含特征。令θ={W,U,b,c}为RTRBM的模型参数，W∈RNh×Nv为可见层和隐含层之间的连接权重，U∈RNh×Nh为隐含层在时间链上彼此之间的连接权重，b∈RNv和c∈RNh分别为可见层和隐含层的偏置，rt∈RNh表示输入样本数据在时间链上关于t时刻的隐含特征，它作为传递项捆绑了输入样本的时间属性。

RTRBM考虑了前一时刻样本在时间通道上的期望输出，并以此作为条件得到可见层变量和隐含层变量的条件联合概率分布。对于任意时刻t(t>1)，给定样本前一时刻在时间通道上的期望输出rt-1，RTRBM关于可见层变量和隐含层变量的条件联合分布定义为：

(1)

其中，Zrt-1为归一化因子，它依赖于rt-1，而E(vt,ht|rt-1)为RTRBM对应于t时刻的能量函数，其定义为：

(2)

rt是一个时间变量，并且依赖于rt-1。在时间链上给定一组时序样本数据{v1,v2,…,vT}，rt的定义如下：

(3)

从形式上可以看出，rt本质上就是关于第t个RBM在隐含层上的概率输出期望，即rt=[ht|vt]。对于时间链长度为T的RTRBM，假定时间链上的每个单元之间彼此独立，则其所有可见层和隐含层的联合条件概率分布可以表述为：

(4)

其中Z为第一个RBM的归一化因子，且有：

(5)

给定rt-1(t>1)，则第t个RBM在隐含层和可见层上的采样概率变为：

p(ht,j=1|vt,rt-1)=sigm(Wj.vt+cj+Uj.rt-1)

(6)

(7)

在r1,r2,…,rT-1已知的情况下，RTRBM结构中的所有RBM都可以看成是相互独立的，因此，对于每个RBM而言，可以单独地执行分块Gibbs采样来近似求解模型参数的梯度。

对于一般的复杂网络，虽然网络内部的节点数量较多，但是节点对之间的连接却很少，这一方面表现出了网络的稀疏性，另一方面反映了除非特殊事件或异常情况的发生，大部分节点在网络中的状态应该基本保持不变，也就是说随着时间的推移，大部分节点对应的特征向量在潜层空间中所处的位置相对保持稳定[9]。基于这一假设，文中在RTRBM的能量函数中加入了对时序样本的平滑处理，即

(8)

1.2 RTRBM模型的学习过程

RTRBM模型的学习过程涉及到输入数据的对数似然概率logp(v1,v2,…,vT)关于模型参数θ求梯度的过程，而在使用CD算法求解模型该近似梯度时，又涉及到了式(8)中能量函数关于参数θ求梯度的过程。为了方便描述具体的梯度推导过程，文中将式(8)中的能量函数改写为E=-H-Q2-β·L的形式，其中

(9)

基于分块K-CD算法的RTRBM模型参数θ的梯度为：

Δθ=Eh1,…,hT|v1,…,vT;r1,…,rT-1[-θE]-

Ev1,…,vT;h1,…,hT|r1,…,rT-1[-θE]=

(10)

(1)H关于参数θ的梯度θH。

H关于参数θ的梯度求解比较简单，就相当于在每个RBM上分别对参数θ进行求导，即

(11)

(2)Q2关于参数θ的梯度θQ2。

由于Q2关于参数θ的梯度都依赖于rt，所以在计算梯度时，需要先计算rt关于参数θ的梯度，而rt关于参数θ的梯度可以通过时序反向传播算法(back propagation through time，BPTT)[10]来进行递归式的求解。

(12)

其中⊙为元素对乘积。由于Qt+1不是关于r1,r2,…,rt-1的函数，故有rtQ2=rtQt+1，因此Q2关于rt(t≥1)的偏导数可以通过递归的形式逐一求解。

同理，Q2关于参数U的偏导数可以根据链式法则递归求解，即

(13)

根据式(10)和式(13)，可以求出RTRBM模型关于参数U的梯度。令Dt=〈rtQt+1〉0-〈rtQt+1〉K，2≤t≤T+1，且DT+1=0，则

ΔUQ2=

(14)

Dt=UT[Dt+1⊙rt+1⊙(1-rt+1)+

〈ht+1〉0-〈ht+1〉K]

(15)

其中1≤t≤T-1。

同理，RTRBM模型关于参数W,b,c的梯度分别为：

(16)

(17)

(18)

(3)L关于参数θ的梯度θL。

L关于参数θ的梯度需要先计算L关于rt的梯度，其计算过程可以根据链式法则进行求解，即：

(19)

而

(20)

其中rT=0。所以L关于参数W,U,b,c的梯度分别为：

(21)

(22)

(23)

(24)

RTRBM具体的实现如算法1所示：

算法1：基于分块CD-K的RTRBM训练流程。

输入：时序样本数据v1,v2,…,vT,最大训练迭代次数maxIter，学习速率η,CD算法执行步长K，惩罚项系数β，以及每个RBM共享的模型参数：可见层神经元个数n_visible，隐含层神经元个数n_hidden

输出：RTRBM模型的最优参数θ*={W*,U*,b*,c*}

1.随机初始化模型参数W,U,b,c;

2.for iter=1 to maxIter do

3.根据式(3)计算出第t个RBM在时间链上的输出期望rt;

4.fort=1 toTdo

5.fork=1 toKdo

8.end for

9.根据式(15)计算Dt(2≤t≤T)

10.end for

11.根据式(11)计算出H关于参数W,U,b,c的梯度WH,UH,bH,cH

12.根据式(14)、(16)、(17)和(18)计算模型在Q2上关于参数W,U,b,c的梯度ΔWQ2,ΔUQ2,ΔbQ2,ΔcQ2

14.根据式(21)～式(24)计算L关于参数W,U,b,c的梯度WL,UL,bL,cL

15.根据式(10)计算参数的梯度Δθ

16.利用随机梯度下降法更新参数θ(iter+1)=θ(iter)+η·Δθ

17.end for

2 基于深度RTRBM的动态网络链路预测方法

2.1 基于深度RTRBM的动态网络链路预测模型框架

如图2所示，基于深度RTRBM模型的动态网络链路预测框架总共分为数据预处理和模型训练两个部分。数据预处理部分主要负责样本集的构建和训练测试集的划分，而模型训练部分则主要负责训练深度RTRBM模型。具体的预测流程为：

步骤1：对原始网络数据进行预处理得到时序样本集，其中样本属性由t1～tT-1时刻的节点对特征组成，样本标签由节点对在tT时刻的状态构成，有连边则为1，否则为0；然后再采用随机抽样或十折交叉验证法对样本集进行划分，得到训练集trainSet和测试集testSet；

步骤2：将训练集trainSet输入至深度RTRBM模型，通过横向BPTT算法逐层训练，获得第n层的隐含特征；

步骤3：将第n层的隐含特征作为Logistic回归模型的输入，通过随机梯度下降和反向传播(back propagation，BP)对第n层的模型参数进行微调；

步骤4：将测试集testSet输入至已训练好的预测模型，得出最后的预测结果。

图2 基于深度RTRBM的动态网络链路预测框架

2.2 深度RTRBM模型结构

图3 两层RTRBM结构示意图

2.3 时序样本集的构建

给定一组网络的时间快照{G1,G2,…,GT}，文中首先利用Node2Vec算法[11]提取各个网络快照状态下的节点特征，然后在此基础上构建节点对的特征，并且为了保证样本集拥有足够的区分度，还添加了CN、RA、AA相似性度量指标得分作为扩充属性集，最后将每个时间快照的样本数据合并为最终的时序样本集。

3 实验仿真与结果分析

3.1 实验设置

3.1.1 数据集

实验部分使用的数据集全部来源于Koblenz Network Collection(http://konect.uni-koblenz.de/)和Stanford Large Network Dataset(http://snap.stanford.edu/data/),其中包含2个人际关系网络和5个邮件传递网络，其相关统计信息如表1所示。

表1 动态网络的相关统计信息

3.1.2 对比算法

为了验证提出方法的有效性，使用两种动态网络链路预测方法与之进行对比实验，即基于相似性度量的方法和基于深度学习的方法。

(1)基于相似性度量的方法。

对于给定的一组网络时间快照序列{G1,G2,…,GT}，基于相似性度量的方法首先将前T-1个网络快照{G1,G2,…,GT-1}压缩成对应的概念图G1,T-1，然后在G1,T-1上做静态网络链路预测，预测GT的链路情况[12]。G1,T-1的邻接矩阵A1,T-1定义如下：

(25)

其中Ak为图Gk的邻接矩阵。文中采用的度量指标为CN、RA和AA。

(2)基于深度学习的方法。

基于深度学习的方法主要区别在于所使用的学习模型，文中采用的学习模型有：条件时序受限玻尔兹曼机(conditional temporal Restricted Boltzmann Machine，ctRBM)[13]和深度条件置信网(conditional Deep Belief Network，cDBN)[14]。

3.1.3 超参数设置

在模型参数的设置上，RBM作为DRTRBM和cDBN的基本单元，其权重矩阵W采用文献[15]中的方式进行随机初始化，学习速率η设为0.01，CD算法的执行步长K设为1，最大训练次数maxIter设为100。另外，DRTRBM的惩罚项系数β设为0.001。

在实验结果上，文中采用十折交叉验证法，对每个网络分别重复实验30次，并取平均值作为最终的实验结果。

3.2 实验结果

文中使用AUC指标来评估各个算法在不同数据集上的预测性能，实验结果如图4所示。

图4 算法关于动态网络链路预测的AUC得分

对于Email数据集，DRTRBM的平均AUC得分最高，相对于CN、RA、AA、ctRBM、cDBN和RTRBM分别将基准线提高了26.70%、31.14%、31.36%、2.54%、5.84%和5.46%。此外，改进后的RTRBM(ImRTRBM)性能比未改进的RTRBM提高了3.32%，说明Email网络在短时间间隔内节点对之间的关联相对较为稳定。DRTRBM的平均AUC得分比ImRTRBM提高了近2.08%，说明通过堆叠多个RTRBM提取动态网络的深度时序特征能够有效地提高链路预测的精度。

对于Email-D1数据集，ctRBM、cDBN、RTRBM、ImRTRBM和DRTRBM的平均AUC得分都在0.85以上，而CN、RA和AA的平均AUC得分都在0.65左右。其中DRTRBM的平均AUC得分最高，相比于ctRBM、cDBN、RTRBM和ImRTRBM分别将基准线提高了2.04%、5.49%、2.68%和2.39%。ImRTRBM的平均AUC得分比RTRBM只提高了0.28%，说明对于RTRBM的时间平滑处理效果并不是很明显。另外，ctRBM的平均AUC得分次高，说明网络前一时刻的状态对于后一时刻的状态影响很大。

此外，在Email-D2～D4、Haggle、Infection数据集上，ImRTRBM和DRTRBM的平均AUC得分都比其他算法要高。

总的来说，基于机器学习的方法在AUC指标上均比基于相似性度量的方法要高；其次，文中提出的基于深度RTRBM的动态网络链路预测方法不仅可以有效地提取动态网络的深度时序特征，而且可以处理节点对特征随时间演化而发生的骤变问题，进而提高链路预测的准确性。

4 结束语

将RTRBM应用于动态网络的链路预测，对RTRBM模型的能量函数和训练过程进行了改进。在所提出的动态网络链路预测框架中，首先利用Node2Vec算法提取网络节点的嵌入特征，并基于该特征构建用于后续学习分类的时序样本集，然后结合深度学习理论将多个改进后的RTRBM纵向堆叠以构成深度学习结构来提取网络的深度时序特征，最后结合Logistic回归分类器对动态网络中的链路进行分类和预测。实验结果表明，该方法相比于其他方法有着明显的性能提升。然而，深度RTRBM模型中的超参数需要根据网络类型和规模而决定，因此如何高效地选择模型的超参数是今后要研究的主要问题。