基于密集連接卷積神經(jīng)網(wǎng)絡(luò)的鏈路預(yù)測模型

王文濤 吳淋濤 黃燁 朱容波

摘 要：現(xiàn)有的基于網(wǎng)絡(luò)表示學(xué)習(xí)的鏈路預(yù)測算法主要通過捕獲網(wǎng)絡(luò)節(jié)點(diǎn)的鄰域拓?fù)湫畔?gòu)造特征向量來進(jìn)行鏈路預(yù)測，該類算法通常只注重從網(wǎng)絡(luò)節(jié)點(diǎn)的單一鄰域拓?fù)浣Y(jié)構(gòu)中學(xué)習(xí)信息，而對多個網(wǎng)絡(luò)節(jié)點(diǎn)在鏈路結(jié)構(gòu)上的相似性方面研究不足。針對此問題，提出一種基于密集連接卷積神經(jīng)網(wǎng)絡(luò)（DenseNet）的鏈路預(yù)測模型（DenseNet-LP）。首先，利用基于網(wǎng)絡(luò)表示學(xué)習(xí)算法node2vec生成節(jié)點(diǎn)表示向量，并利用該表示向量將網(wǎng)絡(luò)節(jié)點(diǎn)的結(jié)構(gòu)信息映射為三維特征數(shù)據(jù);然后，利用密集連接卷積神經(jīng)網(wǎng)絡(luò)來捕捉鏈路結(jié)構(gòu)的特征，并建立二分類模型實(shí)現(xiàn)鏈路預(yù)測。在四個公開的數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果表明，相較于網(wǎng)絡(luò)表示學(xué)習(xí)算法，所提模型鏈路預(yù)測結(jié)果的ROC曲線下方面積（AUC）值最大提高了18個百分點(diǎn)。

關(guān)鍵詞：鏈路預(yù)測;網(wǎng)絡(luò)表示學(xué)習(xí);節(jié)點(diǎn)表示;卷積神經(jīng)網(wǎng)絡(luò);深度學(xué)習(xí)

中圖分類號： TP391;TP18

文獻(xiàn)標(biāo)志碼：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 引言

真實(shí)世界的復(fù)雜系統(tǒng)通常都可以構(gòu)建為網(wǎng)絡(luò)形式，其節(jié)點(diǎn)代表系統(tǒng)中不同的實(shí)體，邊代表這些實(shí)體之間的聯(lián)系。鏈路預(yù)測是指通過已知的網(wǎng)絡(luò)結(jié)構(gòu)和屬性等信息，預(yù)測網(wǎng)絡(luò)中尚未產(chǎn)生連接的兩個節(jié)點(diǎn)間產(chǎn)生連接的可能性[1]。在電商網(wǎng)絡(luò)中，可以為用戶推薦感興趣的商品;在科學(xué)家合作網(wǎng)絡(luò)中，可以對科學(xué)家之間潛在的合作關(guān)系進(jìn)行預(yù)測;在社交網(wǎng)絡(luò)中，可以幫助用戶推薦他們感興趣的用戶;在生物領(lǐng)域的蛋白質(zhì)作用網(wǎng)絡(luò)中，可以挖掘那些潛在的相互作用。毫無疑問，鏈路預(yù)測的廣泛應(yīng)用已使其成為了復(fù)雜網(wǎng)絡(luò)研究中的熱點(diǎn)領(lǐng)域之一。

現(xiàn)有的鏈路預(yù)測算法可以分為：基于相似性的算法和基于學(xué)習(xí)的算法。基于相似性的算法是假設(shè)節(jié)點(diǎn)之間越相似則它們之間存在鏈接的可能性就越大[2-3]，通過定義一個函數(shù)來計(jì)算節(jié)點(diǎn)間的相似性，該函數(shù)可以利用某些網(wǎng)絡(luò)信息如網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)或節(jié)點(diǎn)屬性來計(jì)算節(jié)點(diǎn)間的相似性，最后利用節(jié)點(diǎn)間的相似度來預(yù)測節(jié)點(diǎn)間產(chǎn)生鏈接的可能性，其預(yù)測精度的高低很大程度上取決于能否很好地選取網(wǎng)絡(luò)結(jié)構(gòu)特征[4]。早期的鏈路預(yù)測研究多使用啟發(fā)式的分?jǐn)?shù)來度量節(jié)點(diǎn)間的相似性，經(jīng)典的啟發(fā)式方法有共同鄰居（Common Neighbors， CN）[5]、Jaccard[6]、Adamic-Adar[7]和優(yōu)先偏好（Preferential Attachment， PA）等，但是它們僅利用了單一的局部結(jié)構(gòu)信息，無法捕捉節(jié)點(diǎn)間的深層拓?fù)潢P(guān)系，對不同網(wǎng)絡(luò)的適應(yīng)性較差?；趯W(xué)習(xí)的算法則構(gòu)建一個能夠提取網(wǎng)絡(luò)特征的模型，用已有的網(wǎng)絡(luò)信息來訓(xùn)練模型，最后利用訓(xùn)練好的模型來預(yù)測節(jié)點(diǎn)間是否會產(chǎn)生鏈接。近年來，網(wǎng)絡(luò)表示學(xué)習(xí)模型[8]已經(jīng)在多種網(wǎng)絡(luò)處理和分析任務(wù)上驗(yàn)證了其有效性，網(wǎng)絡(luò)表示學(xué)習(xí)模型將網(wǎng)絡(luò)信息轉(zhuǎn)換為低維實(shí)值向量，這些向量可用于可視化、節(jié)點(diǎn)分類和鏈路預(yù)測等任務(wù)。Perozzi等[9]提出的DeepWalk算法，通過隨機(jī)游走將游走的路徑當(dāng)作句子，并使用Skip-gram[10]模型來學(xué)習(xí)節(jié)點(diǎn)的表示向量，最終在網(wǎng)絡(luò)分析任務(wù)上取得了較大的性能提升。隨后，又出現(xiàn)了基于簡單神經(jīng)網(wǎng)絡(luò)的LINE算法[11]和改進(jìn)DeepWalk的node2vec算法[12]也利用學(xué)習(xí)到的節(jié)點(diǎn)向量完成了鏈路預(yù)測任務(wù)，但是該類算法只考慮了網(wǎng)絡(luò)全局拓?fù)湫畔?，而忽略了鏈路結(jié)構(gòu)的相似性。

鏈路預(yù)測最直觀的假設(shè)是，如果兩個節(jié)點(diǎn)之間越相似，則它們之間最有可能產(chǎn)生連邊?；诰W(wǎng)絡(luò)表示學(xué)習(xí)的方法，僅利用了節(jié)點(diǎn)的特征向量去度量節(jié)點(diǎn)間的相似性，而不能有效地捕捉到鏈路結(jié)構(gòu)的相似性特征，即產(chǎn)生鏈路的兩個節(jié)點(diǎn)的局部結(jié)構(gòu)相似性。深度神經(jīng)網(wǎng)絡(luò)因其強(qiáng)大的特征學(xué)習(xí)與表達(dá)能力，近年來在圖像分類、目標(biāo)檢測與目標(biāo)識別等應(yīng)用中取得了極大的進(jìn)展[13]。卷積神經(jīng)網(wǎng)絡(luò)的核心思想是構(gòu)造不同的感受野抽取圖像的局部特征，而卷積神經(jīng)網(wǎng)絡(luò)高效的原因就是局部特征提取能力。一般來說，網(wǎng)絡(luò)越深所能學(xué)到的東西就越多，但是簡單地加深網(wǎng)絡(luò)層數(shù)會導(dǎo)致網(wǎng)絡(luò)能力的退化。CVPR2016（the 2016 IEEE Conference on Computer Vision and Pattern Recognition）上提到的殘差網(wǎng)絡(luò)（Residual Network， ResNet）[14]通過在原網(wǎng)絡(luò)的結(jié)構(gòu)上加上一個恒等映射解決了網(wǎng)絡(luò)層數(shù)進(jìn)一步加深帶來的退化問題，但是由于恒等映射和非線性變化的輸出通過相加的方式結(jié)合，會妨礙信息在整個網(wǎng)絡(luò)的傳播。密集連接卷積神經(jīng)網(wǎng)絡(luò)（Densely Connected Convolutional Network， DenseNet）[15]受GoogLeNet[16]啟發(fā)，DenseNet是將上一層得到的特征圖通過串聯(lián)的方式結(jié)合，這樣對特征的極致利用達(dá)到了更好的效果，更有利于信息在整個網(wǎng)絡(luò)的傳播。

現(xiàn)有的基于節(jié)點(diǎn)相似性的算法采用簡單的一階、多階鄰居信息，導(dǎo)致該類方法在擴(kuò)展性方面受到了嚴(yán)重的挑戰(zhàn)[17];基于學(xué)習(xí)的算法采用隨機(jī)游走策略或者改進(jìn)的隨機(jī)游走策略來獲得節(jié)點(diǎn)的鄰域結(jié)構(gòu)信息，例如DeepWalk算法的隨機(jī)游走策略就存在很大的隨機(jī)性;node2vec算法采樣策略雖然在深度和廣度取了一個平衡值，但是依然不能夠提取到有效的鏈路的結(jié)構(gòu)。LINE和node2vec等算法都可歸類到淺層神經(jīng)網(wǎng)絡(luò)，而淺層神經(jīng)網(wǎng)絡(luò)并不能捕捉到高度非線性的網(wǎng)絡(luò)結(jié)構(gòu)從而導(dǎo)致產(chǎn)生非最優(yōu)的網(wǎng)絡(luò)表示結(jié)果。

因此，現(xiàn)有研究存在如下兩個問題：①基于隨機(jī)游走的鏈路預(yù)測算法，隨機(jī)游走采樣策略具有一定的盲目性[4]，因此不能夠有效地獲得節(jié)點(diǎn)的鄰域結(jié)構(gòu)信息;②淺層的神經(jīng)網(wǎng)絡(luò)算法不能夠有效地捕捉高度非線性結(jié)構(gòu)[17]，例如鏈路結(jié)構(gòu)特征。為此，本文作了如下改進(jìn)：

1）針對問題①提出通過提取網(wǎng)絡(luò)節(jié)點(diǎn)的子圖作為節(jié)點(diǎn)的鄰域結(jié)構(gòu)信息，因?yàn)樽訄D中包含了一些復(fù)雜的非線性模式，而這些模式實(shí)際上決定了鏈路的形成。

2）針對問題②提出利用深度卷積神經(jīng)網(wǎng)絡(luò)去捕捉鏈路結(jié)構(gòu)的相似性，因?yàn)樯疃壬窠?jīng)網(wǎng)絡(luò)能夠?qū)W習(xí)一種深層的非線性網(wǎng)絡(luò)結(jié)構(gòu)，具有更強(qiáng)的表征能力。例如深度卷積神經(jīng)網(wǎng)絡(luò)的局部特征提取能力很強(qiáng)，尤其是在網(wǎng)格數(shù)據(jù)上的表現(xiàn)，因此將兩個節(jié)點(diǎn)的子圖信息構(gòu)造為矩陣形式，并通過深度卷積神經(jīng)網(wǎng)絡(luò)來提取。

1 相關(guān)工作

1.1 node2vec算法

node2vec算法與DeepWalk相同，也是類比word2vec模型[10]實(shí)現(xiàn)的，只是在隨機(jī)游走的算法上與DeepWalk不同。DeepWalk是完全隨機(jī)的，而node2vec算法給出了一個計(jì)算式，式（1）中起主要作用的是p和q兩個參數(shù)。

1.2 DenseNet模型

相比ResNet， Huang等[15]提出的DenseNet是一個更激進(jìn)的密集連接機(jī)制：即互相連接所有層，具體來說就是每個層都會接受其前面所有層作為其額外的輸入。其網(wǎng)絡(luò)結(jié)構(gòu)主要由Dense Block （密集連接塊）和Transition（過渡層，Conv（卷積）+Pooling（池化））組成，如圖1所示。

在傳統(tǒng)的卷積神經(jīng)網(wǎng)絡(luò)中，第l層的輸出作為第l+1層的輸入，簡單地理解，從輸入到輸出是單連接，即網(wǎng)絡(luò)有l(wèi)層（輸入層不考慮），那么就是l個連接;ResNet網(wǎng)絡(luò)模型中，網(wǎng)絡(luò)的某層與前面的某層（一般是2～3層）除了從輸入到輸出的連接外，還有一個從輸入到輸出的短路連接（恒等映射）在一起，連接方式是通過元素相加;而在DenseNet中，網(wǎng)絡(luò)模型的某層與前面某層有l(wèi)（l+1）/2個連接，可參考圖1，相比ResNet這是一種密集連接。DenseNet是直接連接來自不同層的特征圖，這可以實(shí)現(xiàn)特征重用，提升效率。

其中：Hl（·）代表的是非線性轉(zhuǎn)換函數(shù)，它是一個組合的操作，其包括一系列的BN（Batch Normalization）[18]、修正線性函數(shù)（Rectified Linear Unit， ReLU）、Pooling及Conv操作。需要注意的是，這里的l和l-1層之間可能實(shí)際包含多個卷積層。[x0，x1，…，xl-1]表示將0到l-1層的輸出特征圖作深度級聯(lián)，即在深度上作通道的合并。

因此，DenseNet所做的工作就是在保證網(wǎng)絡(luò)中層與層之間最大限度的信息傳輸前提下，直接將所有層連接起來。密集連接網(wǎng)絡(luò)的這種Dense Block設(shè)計(jì)，使得這個塊中每個卷積層的輸出特征圖的數(shù)量都很小，Transition模塊是連接兩個相鄰的Dense Block，并且通過Pooling使得特征圖的大小降低，同時這種連接方式使得特征和梯度的傳遞更加有效，網(wǎng)絡(luò)也就更加容易訓(xùn)練。

2 基于DenseNet的鏈路預(yù)測方法

本文將鏈路預(yù)測問題轉(zhuǎn)化為二分類問題，并使用DenseNet網(wǎng)絡(luò)模型來處理二分類問題。首先，通過網(wǎng)絡(luò)表示學(xué)習(xí)算法得到網(wǎng)絡(luò)的節(jié)點(diǎn)表示向量，同時對網(wǎng)絡(luò)中的每個節(jié)點(diǎn)提取一個子圖;然后，利用節(jié)點(diǎn)表示向量來對子圖中的節(jié)點(diǎn)序列進(jìn)行排序，并將排好序的節(jié)點(diǎn)序列映射為一個矩陣，將相應(yīng)的兩個節(jié)點(diǎn)對應(yīng)的矩陣整合為三維數(shù)據(jù);最后，將三維數(shù)據(jù)輸入到DenseNet模型，判斷是否存在連邊。另外，為了敘述方便，提出的方法描述為基于子圖表示學(xué)習(xí)的鏈路預(yù)測方法，整體流程如圖2所示。

2.1 子圖提取算法

圖中包含了一些復(fù)雜非線性的模式，而這些實(shí)際上決定了鏈路的形式[19]。為了學(xué)習(xí)圖的結(jié)構(gòu)特征，本文提出的基于密集連接卷積神經(jīng)網(wǎng)絡(luò)（DenseNet）的鏈路預(yù)測模型（Link Prediction model based on DenseNet， DenseNet-LP）為每個節(jié)點(diǎn)提取一個對應(yīng)的子圖，從而獲得每個節(jié)點(diǎn)的局部結(jié)構(gòu)。

定義1 給定一個無向圖G=（V，E），其中V={v1，v2，…，vn}是節(jié)點(diǎn)集合，EV×V是邊的集合，對于節(jié)點(diǎn)xV，節(jié)點(diǎn)x對應(yīng)的h-hop子圖Ghx是從圖G的節(jié)點(diǎn)結(jié)合{y|d（y，x）≤h}及其對應(yīng)的邊構(gòu)造而成，其中，d（y，x）表示節(jié)點(diǎn)x到節(jié)點(diǎn)y的最短路徑。

2.2 節(jié)點(diǎn)排序算法

為了把卷積神經(jīng)網(wǎng)絡(luò)應(yīng)用于網(wǎng)絡(luò)結(jié)構(gòu)表示學(xué)習(xí)，關(guān)鍵問題是如何在網(wǎng)絡(luò)結(jié)構(gòu)上定義感受野。因此，算法的第一步就是把每個節(jié)點(diǎn)的局部結(jié)構(gòu)作為感受野的輸入，關(guān)于如何獲得節(jié)點(diǎn)的局部結(jié)構(gòu)在2.1節(jié)已經(jīng)作了說明。由于卷積操作對數(shù)據(jù)輸入的順序是敏感的，對于無序數(shù)據(jù)則較難提取到有效的特征，而節(jié)點(diǎn)的局部網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)是無序的，因此算法的第二步是把每個節(jié)點(diǎn)的局部結(jié)構(gòu)變成一個有序的序列。

為了對節(jié)點(diǎn)進(jìn)行排序，就需要度量每個節(jié)點(diǎn)的重要程度，因此利用node2vec算法生成網(wǎng)絡(luò)中每個節(jié)點(diǎn)的向量表示，假定X=[x1，x2，…，xd]表示任意x節(jié)點(diǎn)的d維向量表示，Y=[y1，y2，…，yd]表示任意節(jié)點(diǎn)y的d維向量表示。由于余弦距離被廣泛采用度量多維空間中兩點(diǎn)之間的相關(guān)性，所以本文也利用各節(jié)點(diǎn)在多維空間上的余弦距離來表征各節(jié)點(diǎn)在網(wǎng)絡(luò)結(jié)構(gòu)上的相似度。在此，以相似度作為判別重要程度的指標(biāo)，并給出定義2。

2.3 節(jié)點(diǎn)對維度轉(zhuǎn)化

為了完成鏈路預(yù)測的任務(wù)，就需要預(yù)測兩節(jié)點(diǎn)間的關(guān)系。將網(wǎng)絡(luò)節(jié)點(diǎn)對中的節(jié)點(diǎn)所對應(yīng)的節(jié)點(diǎn)序列映射為鄰接矩陣，矩陣大小為k×k×2，2代表的是兩個節(jié)點(diǎn)。具體流程見算法3。

算法3 節(jié)點(diǎn)序列到矩陣的映射。

2.4 模型預(yù)測方法

如2.1～2.3節(jié)所述，利用目標(biāo)節(jié)點(diǎn)的鄰域生成對應(yīng)子圖，然后將節(jié)點(diǎn)對的兩個子圖映射為兩個子圖的鄰接矩陣并整合為三維特征數(shù)據(jù)形式，若節(jié)點(diǎn)對之間存在鏈接就將對應(yīng)的標(biāo)簽設(shè)為1，否則為0。密集連接卷積神經(jīng)網(wǎng)絡(luò)的特點(diǎn)是對特征的極致利用，因此，網(wǎng)絡(luò)可以學(xué)到更為豐富的內(nèi)容，即更加豐富的節(jié)點(diǎn)鄰域結(jié)構(gòu)信息，即使是在深層的網(wǎng)絡(luò)層次，也能夠?qū)W到豐富的信息。在鏈路預(yù)測中，通常感興趣的是節(jié)點(diǎn)對，而不是單個節(jié)點(diǎn)。例如，在網(wǎng)絡(luò)中預(yù)測的是兩個節(jié)點(diǎn)之間是否存在連邊的可能性，通過將網(wǎng)絡(luò)數(shù)據(jù)轉(zhuǎn)換，這樣將鏈路預(yù)測問題轉(zhuǎn)化為二分類問題，并使用分類效果較好的密集連接卷積神經(jīng)網(wǎng)絡(luò)模型來實(shí)現(xiàn)鏈路預(yù)測任務(wù)。

3.2 基準(zhǔn)方法

本文所提模型是一種基于網(wǎng)絡(luò)結(jié)構(gòu)的鏈路預(yù)測模型。除了DeepWalk、node2vec和LINE網(wǎng)絡(luò)表示學(xué)習(xí)算法外，本文還選取4種常用的傳統(tǒng)經(jīng)典方法作為基準(zhǔn)方法進(jìn)行性能對比，即CN、Jaccard、Adamic-Adar（AA）和PA指標(biāo)。下面分別對其作簡要介紹。

3.3 評估指標(biāo)

為了評估算法的準(zhǔn)確性，實(shí)驗(yàn)將數(shù)據(jù)集隨機(jī)且獨(dú)立地劃分為訓(xùn)練集和測試集，90%用作訓(xùn)練集，10%用作測試集，同時保證訓(xùn)練集和測試集中的網(wǎng)絡(luò)具有連通性。常見的評判算法準(zhǔn)確率的指標(biāo)有受試者工作特征（Receiver Operating Characteristic， ROC）曲線下方面積（Area Under the ROC Curve， AUC）和Precision。其中，AUC是從整體上衡量算法的準(zhǔn)確度;Precision只考慮對排在前L位的邊是否預(yù)測準(zhǔn)確。因此，本文選用AUC和Precision兩個值進(jìn)行算法精度的評價。

1）在鏈路預(yù)測算法計(jì)算出所有節(jié)點(diǎn)間存在邊的分?jǐn)?shù)值之后，AUC指標(biāo)可以描述為在測試集中隨機(jī)選取一條存在連邊的分?jǐn)?shù)值比隨機(jī)選取一條不存在連邊的分?jǐn)?shù)值高的概率。通常，AUC值最少大于0.5，AUC值越高，則算法的精度就越高，最高不超過1。計(jì)算式定義如下：

3.4 實(shí)驗(yàn)環(huán)境和設(shè)置

為模擬鏈路預(yù)測任務(wù)，從原網(wǎng)絡(luò)G=（V，E）中隨機(jī)地移除10%的邊，記作Ep，在移除邊的同時保證網(wǎng)絡(luò)的連通性，生成新的網(wǎng)絡(luò)G′=（V，E′），其中，Ep∩E′=，E′、Ep分別是訓(xùn)練集和測試集中的正類，然后分別添加與正類等量不存在的邊作為負(fù)類，添加負(fù)類時保證訓(xùn)練集和測試集交集為空。

實(shí)驗(yàn)硬件環(huán)境：Intel Core i3-8100（3.6GHz×4） CPU，16GB內(nèi)存，GTX 1060（3GB）顯卡。

實(shí)驗(yàn)軟件環(huán)境：Windows 10操作系統(tǒng)，DeepWalk、node2vec和LINE模型算法采用Python2.7實(shí)現(xiàn)，所提算法是在Python3.5上實(shí)現(xiàn)。

實(shí)驗(yàn)參數(shù)設(shè)置如下：

1）子圖提取算法h-hop數(shù)：一般設(shè)定h∈{2，3}， 實(shí)驗(yàn)中h=3取得較好的效果，因此，本文設(shè)置h=3。

2）子圖映射為鄰接矩陣：實(shí)驗(yàn)時設(shè)定k∈{32，64，128}，通過實(shí)驗(yàn)對比，如圖4所示，k=64，AUC預(yù)測精度相對較好，因此選擇64×64大小。

3）DeepWalk和node2vec模型算法參數(shù)：滑動窗口大小w=10，重新隨機(jī)游走遍歷次數(shù)γ=10，每次隨機(jī)游走遍歷步長l=80，向量空間維度d=128，node2vec的超參數(shù)p，q∈{0.25，0.50，1，2，4}。另外兩個模型生成的節(jié)點(diǎn)表示向量按式（12）計(jì)算相應(yīng)的邊特征向量，邊特征向量由文獻(xiàn)[15]提到的哈達(dá)瑪積（Hadamard product， Hadamard）計(jì)算，然后建立邏輯回歸模型進(jìn)行鏈路預(yù)測。

3.5 結(jié)果分析

將本文所提方法在3.1節(jié)中所提到的4個數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)，為了更加準(zhǔn)確呈現(xiàn)預(yù)測結(jié)果，在所有數(shù)據(jù)集上重復(fù)獨(dú)立實(shí)驗(yàn)20次，并計(jì)算這20次實(shí)驗(yàn)的AUC平均值作為最后的預(yù)測結(jié)果。在4個數(shù)據(jù)集上的預(yù)測精度AUC值的實(shí)驗(yàn)結(jié)果如圖4所示。同眾基準(zhǔn)算法進(jìn)行對比的結(jié)果如表3所示。

圖4中曲線分別為算法中矩陣維度k∈{32，64，128}對應(yīng)的預(yù)測結(jié)果。當(dāng)k取32時，其預(yù)測效果在USAir和King James數(shù)據(jù)集上還不如基準(zhǔn)算法，表明k值取值較小，節(jié)點(diǎn)的鄰域結(jié)構(gòu)信息不足，對鏈路結(jié)構(gòu)信息的捕獲的幫助不大;當(dāng)k取64時，其預(yù)測效果已經(jīng)有了較大的提升，表明此時的節(jié)點(diǎn)鄰域結(jié)構(gòu)信息對于捕捉鏈路結(jié)構(gòu)的相似性幫助是較大的;當(dāng)k取128時，其預(yù)測結(jié)果較k取32時整體效果要好，并且均高于基準(zhǔn)算法的精度。但是在數(shù)據(jù)集USAir和PB兩個數(shù)據(jù)集上k取128的預(yù)測效果沒有k取64時的效果好，表明節(jié)點(diǎn)的鄰域結(jié)構(gòu)較寬泛，容易取到一些“噪聲”數(shù)據(jù)，這些數(shù)據(jù)對于鏈路的預(yù)測幫助不大，甚至?xí)斐尚畔⒌娜哂啵詈髮?dǎo)致預(yù)測的效果并不理想，而且k值取值越大，計(jì)算的復(fù)雜度更高。因此綜合考慮各因素，在實(shí)驗(yàn)中設(shè)置k=64。

結(jié)合表1和表3來看：本文所提出的DenseNet-LP方法比傳統(tǒng)經(jīng)典的方法表現(xiàn)要好，最高提升了36個百分點(diǎn);比網(wǎng)絡(luò)表示學(xué)習(xí)方法方法，最高提升18個百分點(diǎn)。這表明從子圖中更能夠提取到鏈路的結(jié)構(gòu)特征。傳統(tǒng)的方法，例如CN和AA在USAir和PB網(wǎng)絡(luò)上預(yù)測效果良好，是由于這兩個網(wǎng)絡(luò)結(jié)構(gòu)中平均節(jié)點(diǎn)度、平均聚類系數(shù)等網(wǎng)絡(luò)屬性較高，表明節(jié)點(diǎn)之間的緊密程度較高，因此采用此類方法能夠取得較好的結(jié)果;但在其他網(wǎng)絡(luò)上性能表現(xiàn)不佳，例如King James網(wǎng)絡(luò)的聚類系數(shù)很小，表明節(jié)點(diǎn)之間的緊密程度很低，并且它的同配系數(shù)也很低，表明網(wǎng)絡(luò)中度值相近的節(jié)點(diǎn)少，從而導(dǎo)致這一類方法的預(yù)測結(jié)果較低。結(jié)合這兩點(diǎn)說明傳統(tǒng)的鏈路預(yù)測方法的預(yù)測效果和網(wǎng)絡(luò)結(jié)構(gòu)屬性關(guān)聯(lián)性較大，方法的泛化性能不佳。

通過表3可以看出，網(wǎng)絡(luò)表示學(xué)習(xí)方法相較傳統(tǒng)的方法性能要穩(wěn)定，例如在King James上表現(xiàn)優(yōu)于傳統(tǒng)的方法，這是因?yàn)榫W(wǎng)絡(luò)表示學(xué)習(xí)方法利用隨機(jī)游走策略能發(fā)掘節(jié)點(diǎn)間的隱含關(guān)系，而傳統(tǒng)的方法只利用了共同鄰居這一單一的網(wǎng)絡(luò)信息。但是在一些特殊網(wǎng)絡(luò)中，比如說節(jié)點(diǎn)的平均度和聚集系數(shù)比較大的時候，簡單的傳統(tǒng)方法還是能夠取得較好的表現(xiàn)，這是因?yàn)樗鼈兡軌蜉^好地利用這些網(wǎng)絡(luò)特性從而得出這兩個節(jié)點(diǎn)的相似度高。然而，本文所提出的DenseNet-LP方法既能夠?qū)W習(xí)到節(jié)點(diǎn)的表示向量又能夠捕捉到鏈路結(jié)構(gòu)的相似性，所以能夠有效地提升表現(xiàn)性能。

表4給出了DenseNet-LP方法和幾個基準(zhǔn)算法的鏈路預(yù)測精度對比。由表4可以看出，除了King James網(wǎng)絡(luò)外，DenseNet-LP方法的精度都優(yōu)于眾基準(zhǔn)算法，是因?yàn)閺淖訄D中能夠?qū)W習(xí)到鏈路的結(jié)構(gòu)特征，從而能夠作出更為準(zhǔn)確的預(yù)測。基于啟發(fā)式的方法其預(yù)測效果較差，從表4中前4個算法的預(yù)測精度可以看出來，其預(yù)測值大部分都沒有0.5，意味著這類算法在這幾個實(shí)驗(yàn)網(wǎng)絡(luò)中預(yù)測精度還不如完全隨機(jī)預(yù)測的好。而基于網(wǎng)絡(luò)表示學(xué)習(xí)的算法是基于路徑相似性指標(biāo)的鏈路預(yù)測，并利用學(xué)習(xí)模型學(xué)習(xí)到了節(jié)點(diǎn)的潛在表示特征，所以其預(yù)測精度相較啟發(fā)式方法好很多，最高值達(dá)0.87。

x4 結(jié)語

針對現(xiàn)有的基于網(wǎng)絡(luò)表示學(xué)習(xí)方法在鏈路預(yù)測任務(wù)中考慮的是節(jié)點(diǎn)單一的鄰域拓?fù)湫畔?，而忽略了多?jié)點(diǎn)在鏈路結(jié)構(gòu)上相似性的問題，本文提出了一種基于密集連接卷積神經(jīng)網(wǎng)絡(luò)的鏈路預(yù)測模型（DenseNet-LP）。首先，針對目標(biāo)節(jié)點(diǎn)生成子圖，利用表示學(xué)習(xí)算法node2vec生成的節(jié)點(diǎn)特征表示向量輔助子圖中的節(jié)點(diǎn)進(jìn)行排序;然后，將排好序的節(jié)點(diǎn)映射為鄰接矩陣，并整合為三維信息;最后，利用密集連接卷積神經(jīng)網(wǎng)絡(luò)模型進(jìn)行鏈路預(yù)測。實(shí)驗(yàn)結(jié)果表明，本文所提模型DenseNet-LP相較現(xiàn)有眾多的鏈路預(yù)測算法有著更加準(zhǔn)確的預(yù)測結(jié)果。盡管本文對基于網(wǎng)絡(luò)結(jié)構(gòu)的鏈路預(yù)測算法研究取得了一些成果，但仍有很多問題待解決，例如在下一步可以嘗試在網(wǎng)絡(luò)結(jié)構(gòu)的基礎(chǔ)上結(jié)合節(jié)點(diǎn)屬性信息來進(jìn)行鏈路預(yù)測問題上的研究。

參考文獻(xiàn) （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] 劉思，劉海，陳啟買，等.基于網(wǎng)絡(luò)表示學(xué)習(xí)與隨機(jī)游走的鏈路預(yù)測算法[J].計(jì)算機(jī)應(yīng)用，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] 涂存超，楊成，劉知遠(yuǎn)，等.網(wǎng)絡(luò)表示學(xué)習(xí)綜述[J].中國科學(xué)：信息科學(xué)，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] 侯建華，鄧雨，陳思萌，等.基于深度特征和相關(guān)濾波器的視覺目標(biāo)跟蹤[J].中南民族大學(xué)學(xué)報(bào)（自然科學(xué)版），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] 齊金山，梁循，李志宇，等.大規(guī)模復(fù)雜信息網(wǎng)絡(luò)表示學(xué)習(xí)：概念、方法與挑戰(zhàn) [J].計(jì)算機(jī)學(xué)報(bào)，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.