王文濤 吳淋濤 黃燁 朱容波
摘 要:現有的基于網絡表示學習的鏈路預測算法主要通過捕獲網絡節點的鄰域拓撲信息構造特征向量來進行鏈路預測,該類算法通常只注重從網絡節點的單一鄰域拓撲結構中學習信息,而對多個網絡節點在鏈路結構上的相似性方面研究不足。針對此問題,提出一種基于密集連接卷積神經網絡(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.