基于属性网络表示学习的链接预测算法

何 媛, 吴 乐

(合肥工业大学 计算机与信息学院,安徽 合肥 230601)

随着在线社交应用迅速发展,产生了海量呈现网络结构的数据。以微信、微博为代表的大型在线社交网络拥有巨量用户,产生大量节点交互信息。网络数据最大特点是数据极其稀疏且结构极其复杂。传统链接预测算法[1]不能很好地从原始数据中学习有价值的信息,从而不能很好适应大数据时代对链接预测任务在算法效率和精度方面的更高要求。最近,研究者们探索从原始数据中学习出节点特征向量,从而可以将复杂网络中的节点表示为低维、稠密的向量,进而可以将这些节点特征向量有效应用在传统网络分析任务中。

网络表示学习[2](network representation learning)也称为网络嵌入(network embedding),目标是将高维、稀疏的网络编码到低维、稠密的空间中,为网络中的每一个节点学习一个低维的向量表示。学习到的节点特征向量蕴含了该节点的网络结构信息以及其他异构信息,并且可以用来进行进一步的网络分析任务,如网络节点分类[3]、链接预测[4]、推荐系统[5]等。

属性网络表示学习模型如图1所示。属性网络是由大量节点、节点属性以及节点之间复杂链接关系共同构成的网络结构,如图1左侧所示。网络特征学习是将网络中每一个节点都映射到一个低维向量空间,并且在此空间内保持原有图的结构信息或属性信息。有链接关系和属性相似的点映射到特征向量空间中距离较近,如图1所示。相反,如果2个节点之间不存在关系,那么对应的特征向量相似度较低。关系越紧密的节点对存在链接关系的概率越大,在特征空间中距离越近,因此网络特征学习可以有效地应用于链接预测任务中。

图1 含有链接关系和属性信息的网络特征学习简化模型

近年来,网络表示学习引起了大量研究者的关注。文献[6]提出了DeepWalk算法,先采用截断随机游走模型将图结构采样成线性节点序列,然后利用skip-gram模型从大量的线性节点序列中学习网络节点的特征向量表示；文献[7]提出的(large-scale informotion netwrok embedding,LINE)算法,设计了一个新的优化目标函数，可以很好地学习出图结构中的一阶信息和二阶信息。近年来,考虑到网络中的节点本身包含丰富的属性信息,文献[8]提出了TADW(text-associated DeepWalk),该框架基于矩阵分解将文本信息以一个子矩阵方式加入,学习到更为丰富的网络节点特征向量。近年来,深度学习在图像处理、视频处理以及自然语言处理方向上取得了很好的效果,也吸引了许多学者将其用于网络节点特征向量的学习。基于深度学习的模型SDNE(structural deep network embedding)[9],通过取自编码模型的中间层作为节点二阶相似性的向量表示,通过平衡有连边的点的向量距离来考虑节点的一阶相似性。SDNE良好的实验效果验证了深度学习模型在学习网络节点特征向量时的强大能力。然而,上述模型并没有具体研究如何将学习出的节点特征向量有效应用于链接预测任务中。

链接预测是网络分析中一个重要的应用。链接预测主要是基于已知的网络预测网络中隐藏的链路,或者基于现在的网络预测未来即将产生的链路。传统的链接预测方法主要是基于节点相似性进行的,即2个节点越相似,它们产生链接的可能性越大。基于共同邻居相似性指标主要有余弦相似性[10]、Jaccard指标[11]、Sorenson指标[12]以及Adamic指标[13]。显然,这些基于相似度的方法并不适用于复杂网络链接预测。文献[14]提出了利用矩阵分解模型实现链接预测的模型LMF(link prediction via matrix fractroization)。LMF模型首先将社交网络用户关系用稀疏矩阵表示,然后通过最大后验概率方法实现对网络邻接矩阵进行求解。随着网络表示学习的发展,研究者们开始尝试利用网络表示学习提高链接预测的精度。文献[15]提出了DeepWalk模型解决链接预测问题,首先将用户存在的链接关系映射到低维向量空间,然后通过随机游走重新定义用户在向量空间上的相似性,由此大大提高了链接预测效果。随着深度学习、神经网络在文本处理、图像理解等领域的成功应用,将神经网络应用于链接预测成为目前研究的重点。

考虑到现实网络中,除了网络结构信息,网络节点还包含丰富的属性信息。综合考虑节点属性和网络结构信息,可以缓解网络数据稀疏问题。对此,本文提出一个基于属性网络表示学习的链接预测模型(attributed network embedding based link prediction,ANE-LP),该模型基于结构信息和属性信息,通过深度自动编码器有效地学习各节点的非线性特征,从而实现精准的链接预测。主要贡献如下:

(1) 利用深度自动编码器模型对属性网络特征学习问题进行优化,相比于传统特征学习模型可以学出更丰富的节点特征。

(2) 提出一个基于属性网络表示学习的链接预测模型ANE-LP,该模型可以针对数据稀疏的特点,更好地实现链接预测。

(3) 基于TensorFlow开源工具实现ANE-LP模型,并在Flickr和Email-Eu-core 2个真实数据集上进行实验,实验结果表明ANE-LP模型取得较好效果。

1 ANE-LP模型

对于属性网络G=(V,E,X),其中，V为网络节点集,且V={v1,v2,…,v|V|},|V|为节点总数；E为网络中链接集,且ei,j∈E表示节点vi与节点vj之间链接关系。对于网络G中每个节点vi∈V都伴随着一个n维的属性向量xi,向量矩阵X={x1,x2,…,x|V|}∈Rn×|V|包含所有节点属性信息。

ANE-LP模型结构如图2所示。主要包括基于网络结构的节点特征学习、基于节点属性的节点特征学习、融合节点结构特征及属性特征进行特征向量训练,最后将学到的特征向量应用于链接预测任务中。

图2 ANE-LP模型

1.1 基于网络结构的节点特征学习

深度自动编码器[16]是一种无监督模型,训练过程可以简单分为编码和解码。通过反向传播算法训练网络,使得模型输出数据尽可能等于输入数据。

(1) 编码。基于第m-1层隐含层的输出Hm-1(S),计算第m层隐含层的输出Hm(S)，具体公式为：

(1)

其中,σ(·)为激活函数;当m=1时,令

Hm-1(S)=S。

(2)

(3) 损失函数LS。计算公式为:

(3)

1.2 基于节点属性的节点特征学习

对于属性网络G,基于所有节点的属性信息矩阵X,根据杰卡德相似系数可以求出节点之间的属性关系矩阵T,节点vi与节点vj的属性相似度Ti,j表示为：

(4)

其中，xi、xj分别为节点vi和节点vj的属性向量,采用独热编码表示。此处将属性向量xi、xj当作0、1数据集合，以便于计算杰卡德相似系数。

类似1.1的过程,基于属性关系矩阵B通过深度自动编码器可以学习出节点的属性特征向量。训练过程与基于网络结构的节点特征学习类似,因此其最终的损失函数LT可以表示为：

(5)

1.3 节点特征融合及属性网络链接预测

sim(vi,vj)=-‖ei-ej‖2

(6)

其中，ei、ej分别为节点vi、vj全局特征向量。根据以上步骤,ANE-LP模型损失函数为：

(7)

其中，Lreg为正则化部分;为防止过拟合,模型训练使用l2归一化方法。通过随机梯度下降法调整参数对目标函数进行优化求解,使得L值达到最小。

2 实 验

实验选用Flickr[17]和Email-Eu-core[18]2个真实数据集,2个数据集具体参数见表1所列。

表1 数据集参数

对比方法选择LINE模型[7]、DeepWalk模型[6]、AutoRec模型[5]。LINE和DeepWalk模型是经典网络表示学习模型。通过与经典网络表示学习模型对比可以发现，ANE-LP模型比传统网络表示在链接预测方面的效果更好。AutoRec模型[5]是一种多层网络链接预测模型,它利用稀疏数据深入挖掘用户信息,实现更好的链接预测。通过与基于深度学习的链接预测模型对比,可以发现网络表示学习在链接预测任务中的有效作用。实验过程中取数据集中80%的点作为训练集、10%的点作为测试集、10%的点作为验证集。采用精确度、NDCG(normalized discounted cumulative Gain)[19]2个指标来评估ANE-LP模型及对比模型在链接预测任务中的效果。在不同的K值情形下,ANE-LP模型与其他模型的对比结果如图3所示。

图3 不同数据集下不同K对应的精确度和NDCG

实验表明,在不同的K值情形下,相对于其他模型,ANE-LP模型在精确度和NDCG评价指标下均取得了最优效果。其中DeepWalk和LINE表现效果均优于AutoRec,且DeepWalk效果又比LINE略好。由于DeepWalk和LINE均是基于网络表示模型实现链接预测的,可以有效针对网络数据稀疏的特点。另外，考虑用户之间潜在联系使得模型表示能力更强,可以更好地学习用户特征向量。DeepWalk、LINE相比于ANE-LP,没有考虑用户的个性化信息。综上所述，融合了用户个性化信息的模型能够取得更优的预测效果。

3 结 论

针对网络中存在的数据集稀疏、结构复杂等问题,本文提出了一种基于属性网络表示方法的链接预测模型。该模型采用了多层神经网络对稀疏数据进行深度挖掘学习网络节点深度非线性特征关系,同时考虑了网络节点的属性信息,得到了精准的节点特征描述，并将学习出的节点特征向量用于链接预测任务中。在Flickr和Email-Eu-core 2个真实数据集上进行的实验结果表明,基于网络表示学习实现链接预测明显提高了预测精度。

由于训练样本非常稀疏,采用多层神经网络容易造成训练模型过拟合的问题，基于本文研究工作，下一步将研究充分利用网络高阶结构信息提升预测精度。