基于密集连接卷积神经网络的链路预测模型

王文涛 吴淋涛 黄烨 朱容波

摘 要：现有的基于网络表示学习的链路预测算法主要通过捕获网络节点的邻域拓扑信息构造特征向量来进行链路预测，该类算法通常只注重从网络节点的单一邻域拓扑结构中学习信息，而对多个网络节点在链路结构上的相似性方面研究不足。针对此问题，提出一种基于密集连接卷积神经网络（DenseNet）的链路预测模型（DenseNet-LP）。首先，利用基于网络表示学习算法node2vec生成节点表示向量，并利用该表示向量将网络节点的结构信息映射为三维特征数据;然后，利用密集连接卷积神经网络来捕捉链路结构的特征，并建立二分类模型实现链路预测。在四个公开的数据集上的实验结果表明，相较于网络表示学习算法，所提模型链路预测结果的ROC曲线下方面积（AUC）值最大提高了18个百分点。

关键词：链路预测;网络表示学习;节点表示;卷积神经网络;深度学习

中图分类号： TP391;TP18

文献标志码：A

Abstract： The current link prediction algorithms based on network representation learning mainly construct feature vectors by capturing the neighborhood topology information of network nodes for link prediction. However， those algorithms usually only focus on learning information from the single neighborhood topology of network nodes， while ignore the researches on similarity between multiple nodes in link structure. Aiming at these problems， a new Link Prediction model based on Densely connected convolutional Network （DenseNet-LP） was proposed. Firstly， the node representation vectors were generated by the network representation learning algorithm called node2vec， and the structure information of the network nodes was mapped into three dimensional feature information by these vectors. Then， DenseNet was used to to capture the features of link structure and establish a two-category classification model to realize link prediction. The experimental results on four public datasets show that， the Area Under the Receiver Operating Characteristic （ROC） Curve （AUC） value of the prediction result of the proposed model is increased by up to 18 percentage points compared to the result of network representation learning algorithm.

Key words： link prediction; network representation learning; node representation; convolutional neural network; deep learning

0 引言

真实世界的复杂系统通常都可以构建为网络形式，其节点代表系统中不同的实体，边代表这些实体之间的联系。链路预测是指通过已知的网络结构和属性等信息，预测网络中尚未产生连接的两个节点间产生连接的可能性[1]。在电商网络中，可以为用户推荐感兴趣的商品;在科学家合作网络中，可以对科学家之间潜在的合作关系进行预测;在社交网络中，可以帮助用户推荐他们感兴趣的用户;在生物领域的蛋白质作用网络中，可以挖掘那些潜在的相互作用。毫无疑问，链路预测的广泛应用已使其成为了复杂网络研究中的热点领域之一。

现有的链路预测算法可以分为：基于相似性的算法和基于学习的算法。基于相似性的算法是假设节点之间越相似则它们之间存在链接的可能性就越大[2-3]，通过定义一个函数来计算节点间的相似性，该函数可以利用某些网络信息如网络拓扑结构或节点属性来计算节点间的相似性，最后利用节点间的相似度来预测节点间产生链接的可能性，其预测精度的高低很大程度上取决于能否很好地选取网络结构特征[4]。早期的链路预测研究多使用启发式的分数来度量节点间的相似性，经典的启发式方法有共同邻居（Common Neighbors， CN）[5]、Jaccard[6]、Adamic-Adar[7]和优先偏好（Preferential Attachment， PA）等，但是它们仅利用了单一的局部结构信息，无法捕捉节点间的深层拓扑关系，对不同网络的适应性较差。基于学习的算法则构建一个能够提取网络特征的模型，用已有的网络信息来训练模型，最后利用训练好的模型来预测节点间是否会产生链接。近年來，网络表示学习模型[8]已经在多种网络处理和分析任务上验证了其有效性，网络表示学习模型将网络信息转换为低维实值向量，这些向量可用于可视化、节点分类和链路预测等任务。Perozzi等[9]提出的DeepWalk算法，通过随机游走将游走的路径当作句子，并使用Skip-gram[10]模型来学习节点的表示向量，最终在网络分析任务上取得了较大的性能提升。随后，又出现了基于简单神经网络的LINE算法[11]和改进DeepWalk的node2vec算法[12]也利用学习到的节点向量完成了链路预测任务，但是该类算法只考虑了网络全局拓扑信息，而忽略了链路结构的相似性。

链路预测最直观的假设是，如果两个节点之间越相似，则它们之间最有可能产生连边。基于网络表示学习的方法，仅利用了节点的特征向量去度量节点间的相似性，而不能有效地捕捉到链路结构的相似性特征，即产生链路的两个节点的局部结构相似性。深度神经网络因其强大的特征学习与表达能力，近年来在图像分类、目标检测与目标识别等应用中取得了极大的进展[13]。卷积神经网络的核心思想是构造不同的感受野抽取图像的局部特征，而卷积神经网络高效的原因就是局部特征提取能力。一般来说，网络越深所能学到的东西就越多，但是简单地加深网络层数会导致网络能力的退化。CVPR2016（the 2016 IEEE Conference on Computer Vision and Pattern Recognition）上提到的残差网络（Residual Network， ResNet）[14]通过在原网络的结构上加上一个恒等映射解决了网络层数进一步加深带来的退化问题，但是由于恒等映射和非线性变化的输出通过相加的方式结合，会妨碍信息在整个网络的传播。密集连接卷积神经网络（Densely Connected Convolutional Network， DenseNet）[15]受GoogLeNet[16]启发，DenseNet是将上一层得到的特征图通过串联的方式结合，这样对特征的极致利用达到了更好的效果，更有利于信息在整个网络的传播。

现有的基于节点相似性的算法采用简单的一阶、多阶邻居信息，导致该类方法在扩展性方面受到了严重的挑战[17];基于学习的算法采用随机游走策略或者改进的随机游走策略来获得节点的邻域结构信息，例如DeepWalk算法的随机游走策略就存在很大的随机性;node2vec算法采样策略虽然在深度和广度取了一个平衡值，但是依然不能够提取到有效的链路的结构。LINE和node2vec等算法都可归类到浅层神经网络，而浅层神经网络并不能捕捉到高度非线性的网络结构从而导致产生非最优的网络表示结果。

因此，现有研究存在如下两个问题：①基于随机游走的链路预测算法，随机游走采样策略具有一定的盲目性[4]，因此不能够有效地获得节点的邻域结构信息;②浅层的神经网络算法不能够有效地捕捉高度非线性结构[17]，例如链路结构特征。为此，本文作了如下改进：

1）针对问题①提出通过提取网络节点的子图作为节点的邻域结构信息，因为子图中包含了一些复杂的非线性模式，而这些模式实际上决定了链路的形成。

2）针对问题②提出利用深度卷积神经网络去捕捉链路结构的相似性，因为深度神经网络能够学习一种深层的非线性网络结构，具有更强的表征能力。例如深度卷积神经网络的局部特征提取能力很强，尤其是在网格数据上的表现，因此将两个节点的子图信息构造为矩阵形式，并通过深度卷积神经网络来提取。

1 相关工作

1.1 node2vec算法

node2vec算法与DeepWalk相同，也是类比word2vec模型[10]实现的，只是在随机游走的算法上与DeepWalk不同。DeepWalk是完全随机的，而node2vec算法给出了一個计算式，式（1）中起主要作用的是p和q两个参数。

1.2 DenseNet模型

相比ResNet， Huang等[15]提出的DenseNet是一个更激进的密集连接机制：即互相连接所有层，具体来说就是每个层都会接受其前面所有层作为其额外的输入。其网络结构主要由Dense Block （密集连接块）和Transition（过渡层，Conv（卷积）+Pooling（池化））组成，如图1所示。

在传统的卷积神经网络中，第l层的输出作为第l+1层的输入，简单地理解，从输入到输出是单连接，即网络有l层（输入层不考虑），那么就是l个连接;ResNet网络模型中，网络的某层与前面的某层（一般是2～3层）除了从输入到输出的连接外，还有一个从输入到输出的短路连接（恒等映射）在一起，连接方式是通过元素相加;而在DenseNet中，网络模型的某层与前面某层有l（l+1）/2个连接，可参考图1，相比ResNet这是一种密集连接。DenseNet是直接连接来自不同层的特征图，这可以实现特征重用，提升效率。

其中：Hl（·）代表的是非线性转换函数，它是一个组合的操作，其包括一系列的BN（Batch Normalization）[18]、修正线性函数（Rectified Linear Unit， ReLU）、Pooling及Conv操作。需要注意的是，这里的l和l-1层之间可能实际包含多个卷积层。[x0，x1，…，xl-1]表示将0到l-1层的输出特征图作深度级联，即在深度上作通道的合并。

因此，DenseNet所做的工作就是在保证网络中层与层之间最大限度的信息传输前提下，直接将所有层连接起来。密集连接网络的这种Dense Block设计，使得这个块中每个卷积层的输出特征图的数量都很小，Transition模块是连接两个相邻的Dense Block，并且通过Pooling使得特征图的大小降低，同时这种连接方式使得特征和梯度的传递更加有效，网络也就更加容易训练。

2 基于DenseNet的链路预测方法

本文将链路预测问题转化为二分类问题，并使用DenseNet网络模型来处理二分类问题。首先，通过网络表示学习算法得到网络的节点表示向量，同时对网络中的每个节点提取一个子图;然后，利用节点表示向量来对子图中的节点序列进行排序，并将排好序的节点序列映射为一个矩阵，将相应的两个节点对应的矩阵整合为三维数据;最后，将三维数据输入到DenseNet模型，判断是否存在连边。另外，为了叙述方便，提出的方法描述为基于子图表示学习的链路预测方法，整体流程如图2所示。

2.1 子图提取算法

图中包含了一些复杂非线性的模式，而这些实际上决定了链路的形式[19]。为了学习图的结构特征，本文提出的基于密集连接卷积神经网络（DenseNet）的链路预测模型（Link Prediction model based on DenseNet， DenseNet-LP）为每个节点提取一个对应的子图，从而获得每个节点的局部结构。

定义1 给定一个无向图G=（V，E），其中V={v1，v2，…，vn}是节点集合，EV×V是边的集合，对于节点xV，节点x对应的h-hop子图Ghx是从图G的节点结合{y|d（y，x）≤h}及其对应的边构造而成，其中，d（y，x）表示节点x到节点y的最短路径。

2.2 节点排序算法

为了把卷积神经网络应用于网络结构表示学习，关键问题是如何在网络结构上定义感受野。因此，算法的第一步就是把每个节点的局部结构作为感受野的输入，关于如何获得节点的局部结构在2.1节已经作了说明。由于卷积操作对数据输入的顺序是敏感的，对于无序数据则较难提取到有效的特征，而节点的局部網络拓扑结构是无序的，因此算法的第二步是把每个节点的局部结构变成一个有序的序列。

为了对节点进行排序，就需要度量每个节点的重要程度，因此利用node2vec算法生成网络中每个节点的向量表示，假定X=[x1，x2，…，xd]表示任意x节点的d维向量表示，Y=[y1，y2，…，yd]表示任意节点y的d维向量表示。由于余弦距离被广泛采用度量多维空间中两点之间的相关性，所以本文也利用各节点在多维空间上的余弦距离来表征各节点在网络结构上的相似度。在此，以相似度作为判别重要程度的指标，并给出定义2。

2.3 节点对维度转化

为了完成链路预测的任务，就需要预测两节点间的关系。将网络节点对中的节点所对应的节点序列映射为邻接矩阵，矩阵大小为k×k×2，2代表的是两个节点。具体流程见算法3。

算法3 节点序列到矩阵的映射。

2.4 模型预测方法

如2.1～2.3节所述，利用目标节点的邻域生成对应子图，然后将节点对的两个子图映射为两个子图的邻接矩阵并整合为三维特征数据形式，若节点对之间存在链接就将对应的标签设为1，否则为0。密集连接卷积神经网络的特点是对特征的极致利用，因此，网络可以学到更为丰富的内容，即更加丰富的节点邻域结构信息，即使是在深层的网络层次，也能够学到丰富的信息。在链路预测中，通常感兴趣的是节点对，而不是单个节点。例如，在网络中预测的是两个节点之间是否存在连边的可能性，通过将网络数据转换，这样将链路预测问题转化为二分类问题，并使用分类效果较好的密集连接卷积神经网络模型来实现链路预测任务。

3.2 基准方法

本文所提模型是一种基于网络结构的链路预测模型。除了DeepWalk、node2vec和LINE网络表示学习算法外，本文还选取4种常用的传统经典方法作为基准方法进行性能对比，即CN、Jaccard、Adamic-Adar（AA）和PA指标。下面分别对其作简要介绍。

3.3 评估指标

为了评估算法的准确性，实验将数据集随机且独立地划分为训练集和测试集，90%用作训练集，10%用作测试集，同时保证训练集和测试集中的网络具有连通性。常见的评判算法准确率的指标有受试者工作特征（Receiver Operating Characteristic， ROC）曲线下方面积（Area Under the ROC Curve， AUC）和Precision。其中，AUC是从整体上衡量算法的准确度;Precision只考虑对排在前L位的边是否预测准确。因此，本文选用AUC和Precision两个值进行算法精度的评价。

1）在链路预测算法计算出所有节点间存在边的分数值之后，AUC指标可以描述为在测试集中随机选取一条存在连边的分数值比随机选取一条不存在连边的分数值高的概率。通常，AUC值最少大于0.5，AUC值越高，则算法的精度就越高，最高不超过1。计算式定义如下：

3.4 实验环境和设置

为模拟链路预测任务，从原网络G=（V，E）中随机地移除10%的边，记作Ep，在移除边的同时保证网络的连通性，生成新的网络G′=（V，E′），其中，Ep∩E′=，E′、Ep分别是训练集和测试集中的正类，然后分别添加与正类等量不存在的边作为负类，添加负类时保证训练集和测试集交集为空。

实验硬件环境：Intel Core i3-8100（3.6GHz×4） CPU，16GB内存，GTX 1060（3GB）显卡。

实验软件环境：Windows 10操作系统，DeepWalk、node2vec和LINE模型算法采用Python2.7实现，所提算法是在Python3.5上实现。

实验参数设置如下：

1）子图提取算法h-hop数：一般设定h∈{2，3}， 实验中h=3取得较好的效果，因此，本文设置h=3。

2）子图映射为邻接矩阵：实验时设定k∈{32，64，128}，通过实验对比，如图4所示，k=64，AUC预测精度相对较好，因此选择64×64大小。

3）DeepWalk和node2vec模型算法参数：滑动窗口大小w=10，重新随机游走遍历次数γ=10，每次随机游走遍历步长l=80，向量空间维度d=128，node2vec的超参数p，q∈{0.25，0.50，1，2，4}。另外两个模型生成的节点表示向量按式（12）计算相应的边特征向量，边特征向量由文献[15]提到的哈达玛积（Hadamard product， Hadamard）计算，然后建立逻辑回归模型进行链路预测。

3.5 结果分析

将本文所提方法在3.1节中所提到的4个数据集上进行实验，为了更加准确呈现预测结果，在所有数据集上重复独立实验20次，并计算这20次实验的AUC平均值作为最后的预测结果。在4个数据集上的预测精度AUC值的实验结果如图4所示。同众基准算法进行对比的结果如表3所示。

图4中曲线分别为算法中矩阵维度k∈{32，64，128}对应的预测结果。当k取32时，其预测效果在USAir和King James数据集上还不如基准算法，表明k值取值较小，节点的邻域结构信息不足，对链路结构信息的捕获的帮助不大;当k取64时，其预测效果已经有了较大的提升，表明此时的节点邻域结构信息对于捕捉链路结构的相似性帮助是较大的;当k取128时，其预测结果较k取32时整体效果要好，并且均高于基准算法的精度。但是在数据集USAir和PB两个数据集上k取128的预测效果没有k取64时的效果好，表明节点的邻域结构较宽泛，容易取到一些“噪声”数据，这些数据对于链路的预测帮助不大，甚至会造成信息的冗余，最后导致预测的效果并不理想，而且k值取值越大，计算的复杂度更高。因此综合考虑各因素，在实验中设置k=64。

结合表1和表3来看：本文所提出的DenseNet-LP方法比传统经典的方法表现要好，最高提升了36个百分点;比网络表示学习方法方法，最高提升18个百分点。这表明从子图中更能够提取到链路的结构特征。传统的方法，例如CN和AA在USAir和PB网络上预测效果良好，是由于这两个网络结构中平均节点度、平均聚类系数等网络属性较高，表明节点之间的紧密程度较高，因此采用此类方法能够取得较好的结果;但在其他网络上性能表现不佳，例如King James网络的聚类系数很小，表明节点之间的紧密程度很低，并且它的同配系数也很低，表明网络中度值相近的节点少，从而导致这一类方法的预测结果较低。结合这两点说明传统的链路预测方法的预测效果和网络结构属性关联性较大，方法的泛化性能不佳。

通过表3可以看出，网络表示学习方法相较传统的方法性能要稳定，例如在King James上表现优于传统的方法，这是因为网络表示学习方法利用随机游走策略能发掘节点间的隐含关系，而传统的方法只利用了共同邻居这一单一的网络信息。但是在一些特殊网络中，比如说节点的平均度和聚集系数比较大的时候，简单的传统方法还是能够取得较好的表现，这是因为它们能够较好地利用这些网络特性从而得出這两个节点的相似度高。然而，本文所提出的DenseNet-LP方法既能够学习到节点的表示向量又能够捕捉到链路结构的相似性，所以能够有效地提升表现性能。

表4给出了DenseNet-LP方法和几个基准算法的链路预测精度对比。由表4可以看出，除了King James网络外，DenseNet-LP方法的精度都优于众基准算法，是因为从子图中能够学习到链路的结构特征，从而能够作出更为准确的预测。基于启发式的方法其预测效果较差，从表4中前4个算法的预测精度可以看出来，其预测值大部分都没有0.5，意味着这类算法在这几个实验网络中预测精度还不如完全随机预测的好。而基于网络表示学习的算法是基于路径相似性指标的链路预测，并利用学习模型学习到了节点的潜在表示特征，所以其预测精度相较启发式方法好很多，最高值达0.87。

x4 结语

针对现有的基于网络表示学习方法在链路预测任务中考虑的是节点单一的邻域拓扑信息，而忽略了多节点在链路结构上相似性的问题，本文提出了一种基于密集连接卷积神经网络的链路预测模型（DenseNet-LP）。首先，针对目标节点生成子图，利用表示学习算法node2vec生成的节点特征表示向量辅助子图中的节点进行排序;然后，将排好序的节点映射为邻接矩阵，并整合为三维信息;最后，利用密集连接卷积神经网络模型进行链路预测。实验结果表明，本文所提模型DenseNet-LP相较现有众多的链路预测算法有着更加准确的预测结果。尽管本文对基于网络结构的链路预测算法研究取得了一些成果，但仍有很多问题待解决，例如在下一步可以尝试在网络结构的基础上结合节点属性信息来进行链路预测问题上的研究。

参考文献 （References）

[1] LYU L Y， ZHOU T. Link prediction in complex networks： a survey [J]. Physica A： Statistical Mechanics and its Applications， 2011， 390（6）： 1150-1170.

[2] AHN M W， JUNG W S. Accuracy test for link prediction in terms of similarity index： the case of WS and BA models [J]. Physica A： Statistical Mechanics and its Applications， 2015， 429： 177-183.

[3] HOFFMAN M， STEINLEY D， BRUSCO M J. A note on using the adjusted rand index for link prediction in networks [J]. Social Networks， 2015， 42： 72-79.

[4] 刘思，刘海，陈启买，等.基于网络表示学习与随机游走的链路预测算法[J].计算机应用，2017，37（8）：2234-2239.（LIU S， LIU H， CHEN Q M， et al. Link prediction algorithm based on network representation learning and random walk [J]. Journal of Computer Applications， 2017， 37（8）：2234-2239.）

[5] NEWMAN M E. Clustering and preferential attachment in growing networks [J]. Physical Review E： Statistical， Nonlinear， and Soft Matter Physics， 2001， 64（2 Pt 2）： 025102.

[6] JACCARD P. Etude comparative de la distribution florale dans une portion des Alpes et du Jura [J]. Bulletin de la Société Vaudoise des Sciences Naturelles， 1901， 37： 547-579.

[7] ADAMIC L A， ADAR E. Friends and neighbors on the Web [J]. Social Networks， 2003， 25（3）： 211-230.

[8] 涂存超，楊成，刘知远，等.网络表示学习综述[J].中国科学：信息科学，2017，47（8）：980-996.（TU C C， YANG C， LIU Z Y， et al. Network representation learning： an overview [J]. SCIENTIA SINICA Informationis， 2017， 47 （8）： 980-996.）

[9] PEROZZI B， AI-RFOU R， SKIENA S. DeepWalk： online learning of social representations [C] // KDD 2014： Proceedings of the 2014 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York： ACM， 2014： 701-710.

[10] MIKOLOV T， SUTSKEVER I， CHEN K， et al. Distributed representations of words and phrases and their compositionality [C] // NIPS13： Proceedings of the 26th International Conference on Neural Information Processing Systems. North Miami Beach， FL： Curran Associates Inc.， 2013： 3111-3119.

[11] TANG J， QU M， WANG M Z， et al. LINE： large-scale information network embedding [C]// WWW 2015： Proceedings of the 24th International Conference on World Wide Web. Republic and Canton of Geneva， Switzerland： International World Wide Web Conferences Steering Committee， 2015： 1067-1077.

[12] GROVER A， LESKOVEC J. Node2vec： scalable feature learning for networks [C]// SIGKDD 2016： Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York： ACM， 2016： 855-864.

[13] 侯建华，邓雨，陈思萌，等.基于深度特征和相关滤波器的视觉目标跟踪[J].中南民族大学学报（自然科学版），2018，37（2）：67-73.（HOU J H， DENG Y， CHEN S M. Visual object tracking based on deep features and correlation filter [J]. Journal of South-Central University for Nationalities （Natural Science Edition）， 2018， 37（2）： 67-73.）

[14] HE K M， ZHANG X Y， REN S Q， et al. Deep residual learning for image recognition [C]// CVPR 2016： Proceedings of the 2016 IEEE Conference on Computer Vision and Pattern Recognition. Washington， DC： IEEE Computer Society， 2016： 770-778.

[15] HUANG G， LIU Z， VAN DER MAATEN L， et al. Densely connected convolutional networks [C]// CVPR 2017： Proceedings of the 2017 IEEE Conference on Computer Vision and Pattern Recognition. Washington， DC： IEEE Computer Society， 2017： 2261-2269.

[16] SZEGEDY C， LIU W， JIA Y Q， et al. Going deeper with convolutions [C]// CVPR 2015： Proceedings of the 2015 IEEE Conference on Computer Vision and Pattern Recognition. Washington， DC： IEEE Computer Society， 2015： 1-9.

[17] 齐金山，梁循，李志宇，等.大规模复杂信息网络表示学习：概念、方法与挑战 [J].计算机学报，2018，41（10）：2394-2420.（QIN J S， LIANG X， LI Z Y， et al. Representation learning of large-scale complex information network： concepts， methods and challenges [J]. Chinese Journal of Computers， 2018， 41（10）： 2394-2420.）

[18] IOFFE S， SZEGEDY C. Batch normalization： accelerating deep network training by reducing internal covariate shift [C]// ICML 2015： Proceedings of the 2015 32nd International Conference on Machine Learning. Cambridge， MA： MIT Press， 2015： 448-456.

[19] ZHANG M H， CHEN Y X. Link prediction based on graph neural networks [EB/OL]. [2018-09-13]. https：//arxiv.org/abs/1802.09691.