基于異質(zhì)網(wǎng)絡(luò)表征學(xué)習(xí)的鏈路預(yù)測算法

蔣宗禮，管戈

（北京工業(yè)大學(xué)信息學(xué)部，北京100124）

0 引言

隨著人工智能和數(shù)據(jù)科學(xué)的發(fā)展，網(wǎng)絡(luò)建模分析成為網(wǎng)絡(luò)研究中一個熱點方向。早期研究通常把網(wǎng)絡(luò)建模成同質(zhì)信息網(wǎng)絡(luò)。然而我們現(xiàn)實中遇到的大多數(shù)系統(tǒng)并不是只有一種相同單元節(jié)點組成的，而是包含了多種相互關(guān)聯(lián)、類型不同的單元節(jié)點組成。使用同質(zhì)網(wǎng)絡(luò)模型抽象系統(tǒng)的方法很難處理復(fù)雜多樣的網(wǎng)絡(luò)，這樣做會導(dǎo)致網(wǎng)絡(luò)的信息缺失。尤其近些年各種社交網(wǎng)絡(luò)、購物網(wǎng)絡(luò)的涌現(xiàn)使得同質(zhì)網(wǎng)絡(luò)無法處理多類型關(guān)系網(wǎng)絡(luò)的問題日益凸顯。為了解決這些問題，研究人員提出了異質(zhì)信息網(wǎng)絡(luò)的建模方式。與同質(zhì)網(wǎng)絡(luò)相比，異質(zhì)網(wǎng)絡(luò)包含了更豐富對象類型和更復(fù)雜的連接關(guān)系。異質(zhì)網(wǎng)絡(luò)所蘊含的更加豐富的語義信息對網(wǎng)絡(luò)的挖掘、分析有著重要意義。

在大數(shù)據(jù)時代網(wǎng)絡(luò)科學(xué)發(fā)展迅速，鏈路預(yù)測成為數(shù)據(jù)挖掘的一個重要研究方向。它不僅對研究網(wǎng)絡(luò)演化有著重要意義，也在實際問題處理中被廣泛應(yīng)用。但是，當(dāng)前多數(shù)鏈路預(yù)測方法主要針對于同質(zhì)網(wǎng)絡(luò)，異質(zhì)網(wǎng)絡(luò)因為其網(wǎng)絡(luò)結(jié)構(gòu)和蘊含信息的復(fù)雜性無法將同質(zhì)網(wǎng)絡(luò)的研究方法直接應(yīng)用在它身上。所以研究異質(zhì)網(wǎng)絡(luò)的鏈路預(yù)測對復(fù)雜網(wǎng)絡(luò)本身的研究有著深刻意義。

1 國內(nèi)外研究現(xiàn)狀

近幾年網(wǎng)絡(luò)科學(xué)的快速發(fā)展，為鏈路預(yù)測的研究提供了廣闊的平臺。鏈路預(yù)測作為數(shù)據(jù)挖掘的一個重要研究方向已產(chǎn)出許多研究成果。在同質(zhì)網(wǎng)絡(luò)中的鏈路預(yù)測主要基于網(wǎng)絡(luò)相似性分析，可以分為以下三類：基于局部信息相似性、基于路徑相似性和基于隨機游走相似性。根據(jù)局部信息相似性判斷的方法有很多，例如 CN（Common Neighbors）指標(biāo)[1]，通過兩點共同鄰居的數(shù)量來判斷產(chǎn)生連接的概率。與之相似的還有Salton等人提出的余弦相似性指標(biāo)[2]以及Jaccard指標(biāo)[3]和Sorenson指標(biāo)[4]。這些指標(biāo)都是從公共鄰居的角度出發(fā)預(yù)測連接可能性。在此基礎(chǔ)上，Adamic等人考慮到共同鄰居節(jié)點的度信息，認(rèn)為度小的共同鄰居貢獻更大，并根據(jù)度的大小賦予一個權(quán)重提出了AA（Adamic Adar）指標(biāo)[5]。還有通過路徑相似性來預(yù)測連接概率，例如Lu等人提出的局部路徑指標(biāo)LP（Local Path）[6]這種方法與局部信息相似性指標(biāo)類似，又考慮了三階鄰居的影響；還有Katz等人提出的Katz指標(biāo)[7]主要是對路徑賦予權(quán)重，路徑越長權(quán)重越小?；陔S機游走的相似性指標(biāo)中常見的有Klein等人提出的平均通勤時間即ACT（Average Commute Time）指標(biāo)[8]；Brin 等人提出了一種 RWR（Random Walk with Restart）指標(biāo)[9]，這種方法本質(zhì)上是在網(wǎng)頁排序中常用的重啟隨機游走算法的擴展。

相比于同質(zhì)網(wǎng)絡(luò)，針對異質(zhì)網(wǎng)絡(luò)鏈路預(yù)測的研究成果較少。Davis等人提出了一種多關(guān)系的鏈路預(yù)測算法 MRLP（Multi-Relational Link Prediction）[10]，作為AA指標(biāo)在異質(zhì)網(wǎng)絡(luò)上的一種擴展，通過概率加權(quán)不同鏈接類型來定義連接概率。Yang等人提出的MRIP（Multi-Relational Influence Propagation）[11]方法通過節(jié)點間的相互影響力來預(yù)測連接概率。黃立威等人[12]根據(jù)元路徑的質(zhì)量權(quán)重建立預(yù)測模型，構(gòu)建出一種基于元路徑的鏈路預(yù)測方法。

2 基于異質(zhì)網(wǎng)絡(luò)表征學(xué)習(xí)的鏈路預(yù)測模型

通過對過往研究的分析，我們發(fā)現(xiàn)多數(shù)鏈路預(yù)測方法都是基于節(jié)點相似度，所以如何量化網(wǎng)絡(luò)節(jié)點的相似度是問題的關(guān)鍵。與同質(zhì)網(wǎng)絡(luò)不同，異質(zhì)網(wǎng)絡(luò)不同類型的節(jié)點和鏈接關(guān)系給量化節(jié)點間的相似度增加了難度。為解決這一問題，我們選擇網(wǎng)絡(luò)表征學(xué)習(xí)來降維表示網(wǎng)絡(luò)，在提取網(wǎng)絡(luò)特征的同時也量化了網(wǎng)絡(luò)節(jié)點。我們提出一種基于異質(zhì)網(wǎng)絡(luò)表征學(xué)習(xí)的鏈路預(yù)測模型 RLLP（Representation Learning Link Prediction）。

2.1 問題定義

定義1：異質(zhì)信息網(wǎng)絡(luò)

給定一個信息網(wǎng)絡(luò)G=(V,E)，其中，V是節(jié)點集合，E是連接集合（邊集合）。對任意節(jié)點v，存在節(jié)點類型Ai∈A滿足v→Ai，A是所有節(jié)點類型的集合;對任意邊e，存在邊類型Ri∈R滿足e→Ri，R是所有邊類型的集合。如果滿足A＞1或者R＞1，則該網(wǎng)絡(luò)定義為異質(zhì)信息網(wǎng)絡(luò)，反之定義為同質(zhì)信息網(wǎng)絡(luò)。

定義2：元路徑

元路徑是定義在網(wǎng)絡(luò)概要圖TG=(A,R)上的路徑，可 以 表 示 成，其中，A1,A2,…,Ai+1表示的是不同類型的節(jié)點，R1,R2,…,Ri表示的是不同類型節(jié)點之間的復(fù)合關(guān)系即網(wǎng)絡(luò)中的邊，箭頭符號表示在關(guān)系上的綜合操作。

定義3：網(wǎng)絡(luò)表征學(xué)習(xí)

表征學(xué)習(xí)學(xué)習(xí)通常也被稱為網(wǎng)絡(luò)嵌入或者網(wǎng)絡(luò)表示。給定一個信息網(wǎng)絡(luò)G=(V,E)，網(wǎng)絡(luò)表征學(xué)習(xí)通過一系列學(xué)習(xí)訓(xùn)練生成一個目標(biāo)函數(shù)f:v→rv∈Rd，通過這個函數(shù)可以將節(jié)點轉(zhuǎn)換為低維向量表示，其中rv表示為節(jié)點v的表示向量，d為轉(zhuǎn)換后的向量維度。

定義4：鏈路預(yù)測

給定一個異質(zhì)信息網(wǎng)絡(luò)G=(V,E)，鏈路預(yù)測的任務(wù)是預(yù)測G中兩個節(jié)點未來是否會產(chǎn)生連接或者存在連接的可能。鏈路預(yù)測的目標(biāo)是通過計算找到并學(xué)習(xí)一個預(yù)測函數(shù)f:( )V,E,vi,vj,l→P，通過函數(shù)可以計算出給定兩個節(jié)點vi和vj之間產(chǎn)生連接即可能存在或未來會產(chǎn)生的邊l概率，其中P表示兩個節(jié)點是否會產(chǎn)生關(guān)系的描述值。

2.2 基于元路徑隨機游走

如何捕獲網(wǎng)絡(luò)特征，對網(wǎng)絡(luò)表征結(jié)果影響重大。受到網(wǎng)絡(luò)表征方法Deepwalk[13]的啟發(fā)，我們選用隨機游走來獲取網(wǎng)絡(luò)的結(jié)構(gòu)特征。但異質(zhì)網(wǎng)絡(luò)因為存在不同類型的節(jié)點和邊，所以如果按照同質(zhì)網(wǎng)絡(luò)的方法進行隨機游走，那樣會忽略了節(jié)點類型信息。為了能夠在捕獲異質(zhì)網(wǎng)絡(luò)不同節(jié)點關(guān)系的同時盡可能的保證網(wǎng)絡(luò)結(jié)構(gòu)的整體性和完整性，隨機游走需要滿足兩點：一是選取的路徑盡可能多的包含不同種類的節(jié)點類型，這樣才可以采集異質(zhì)網(wǎng)絡(luò)中不同類型節(jié)點的相互關(guān)系和拓?fù)浣Y(jié)構(gòu)；二是隨機游走對下一節(jié)點的選定，需要偏向于高度可見的節(jié)點類型，即具有優(yōu)勢或主導(dǎo)數(shù)量的節(jié)點。本文借鑒了異質(zhì)網(wǎng)絡(luò)表征方法metapath2vec[14]的思想，使用了基于元路徑的隨機游走，捕獲不同類型節(jié)點之間的語義和結(jié)構(gòu)相關(guān)性。給定一個異質(zhì)網(wǎng)絡(luò)G=(V,E)和元路徑P:V1→V2→…Vt→Vt+1…→V2→V1那么第i步的轉(zhuǎn)移概率可定義為：

其中P是定義的元路徑，節(jié)點表示節(jié)點的鄰域中屬于Vt+1類型的節(jié)點集合。換而言之，隨機游走是建立在給定的元路徑P條件上的。且本文選用的元路徑均為對稱路徑：

2.3 訓(xùn)練模型網(wǎng)絡(luò)表征

完成隨機游走對網(wǎng)絡(luò)的特征采集后，我們需要使用游走序列訓(xùn)練神經(jīng)網(wǎng)絡(luò)模型，進而完成對網(wǎng)絡(luò)的表征。本文選用Skip-Gram模型對網(wǎng)絡(luò)進行表征學(xué)習(xí)。Skip-Gram[15]最早是由Tomas等人提出的一種詞嵌入模型，被廣泛應(yīng)用于自然語言處理。這個模型的基本思想是通過神經(jīng)網(wǎng)絡(luò)的學(xué)習(xí)，將文本單詞轉(zhuǎn)換到低維的實數(shù)向量空間中，以此簡化文本處理。例如在處理文本相似度時，可以通過計算向量相似度來處理文本相似性問題。

為了將其應(yīng)用在異質(zhì)網(wǎng)絡(luò)上，我們采用metapath2vec算法的處理方式，對模型參數(shù)進行一下修改。給定一個異質(zhì)網(wǎng)絡(luò)G=(V,E)，通過在節(jié)點v的鄰域上最大化條件概率來表征學(xué)習(xí)該網(wǎng)絡(luò)：

其中t∈TV，TV表示節(jié)點類型的集合，Nt(v)代表節(jié)點v的鄰域中屬于節(jié)點類型t的節(jié)點集合，p(ct|v;θ)表示為在給定節(jié)點v的情況下，節(jié)點ct的條件概率，并將其定義為Softmax函數(shù)：

其中Xv表示頂點v的嵌入向量。為了優(yōu)化參數(shù)更新效率，采用了負(fù)采樣進行參數(shù)迭代更新，給定一個負(fù)采樣的大小M，參數(shù)更新過程如下：

2.4 計算相似度矩陣

通過以上兩個步驟，我們完成對異質(zhì)信息網(wǎng)絡(luò)的表征學(xué)習(xí)，可以得到各個節(jié)點的向量表示。一般認(rèn)為，節(jié)點之間相似度越高，那他們之間產(chǎn)生鏈接的概率也就越大。所以，我們將網(wǎng)絡(luò)節(jié)點間鏈接預(yù)測問題轉(zhuǎn)化為判斷節(jié)點向量間的相似性問題。我們采用節(jié)多維向量的歐氏距離來計算節(jié)點向量間的相似性。存在維度為d的向量vx:(x1,x1,…,xd)和vy:(y1,y1,…,yd)，定義兩向量間的相似度為：

為了對鏈接類型分類并計算預(yù)測準(zhǔn)確率，本文會構(gòu)建一個相似度矩陣來存儲各個節(jié)點間的相似度也就是鏈路連接概率。正常一個節(jié)點數(shù)為N的網(wǎng)絡(luò)，兩兩計算出一個鏈接概率會產(chǎn)生一個N*N的相似度矩陣，顯然這不適用于大規(guī)模網(wǎng)絡(luò)。本文研究的是異質(zhì)網(wǎng)絡(luò)的鏈路預(yù)測，所以在預(yù)測節(jié)點鏈接時區(qū)分了鏈接類型，對不同類型的鏈接建立不同的相似度矩陣。假設(shè)存在節(jié)點類型x和節(jié)點類型y，這兩類節(jié)點建立的鏈接類型為R，那么定義節(jié)點xi和節(jié)點yj產(chǎn)生鏈接的概率為鏈接類型為R的相似度矩陣E定義如下：

3 實驗與結(jié)果

3.1 數(shù)據(jù)集

實驗使用IMDB（Internet Movie Database）數(shù)據(jù)集。該數(shù)據(jù)集包含了眾多電影、演員、導(dǎo)演、評分、出版商等電影信息。為方便使用，我們需要對數(shù)據(jù)集進行預(yù)處理。首先我們從數(shù)據(jù)集中提取出五種類型的節(jié)點：電影 M（Movie）、演員 A（Actor）、導(dǎo)演 D（Director）、電影類型 G（Genre）、電影出版國家 C（Country）。同時抽離出四種關(guān)系：演員和電影的參演關(guān)系A(chǔ)-M、導(dǎo)演和電影的指導(dǎo)關(guān)系D-M、電影和電影類型的所屬關(guān)系M-G以及電影和出版國家的出版地關(guān)系M-C。以上信息構(gòu)建出我們所需的異質(zhì)信息網(wǎng)絡(luò)。

經(jīng)驗證本文方法對于網(wǎng)絡(luò)中的隱藏關(guān)系的預(yù)測效果更好，因此，我們提取出三種不在網(wǎng)絡(luò)中直接提現(xiàn)的隱藏關(guān)系：演員之間的合作關(guān)系A(chǔ)-A、演員和導(dǎo)演之間的合作關(guān)系A(chǔ)-D以及演員和電影類型之間的參演喜好關(guān)系A(chǔ)-G作為研究對象。因元路徑的選取對網(wǎng)絡(luò)表征具有較大影響。我們對不同關(guān)系選取不同的元路徑，選用演員-電影-導(dǎo)演-電影-演員（AMDMA）作為研究AD關(guān)系的元路徑，選用演員-電影-電影類型-電影-演員（AMGMA）作為研究AA關(guān)系和AG關(guān)系的元路徑。

3.2 度量標(biāo)準(zhǔn)與基準(zhǔn)方法

為了驗證算法的準(zhǔn)確性，本文選用AUC[16]作為度量指標(biāo)。AUC是一種可以衡量算法預(yù)測準(zhǔn)確率的度量標(biāo)準(zhǔn)。具體是從測試集網(wǎng)絡(luò)中選取一條邊，按給定算法計算它分?jǐn)?shù)值代表產(chǎn)生連接的概率，然后從網(wǎng)絡(luò)中隨機選取一條不存在的邊計算分值進行比較，如果測試集中選取的邊的分值高，則累計1分；兩者相累計0.5分；而如果不存在的邊分值更高，則不計分?jǐn)?shù)。獨立比較n次，假設(shè)有n'累計1分；n''次累計0.5分，則AUC如下：

換而言之，AUC體現(xiàn)了存在鏈接的預(yù)測值比不存在的鏈接的預(yù)測值高的概率。顯然，如果通過隨機選擇進行鏈路預(yù)測，則AUC應(yīng)在0.5左后。因此，AUC越高，預(yù)測算法準(zhǔn)確率就越高且至少應(yīng)高于0.5。

同時作為對比，本文選用了四個常用指標(biāo)作為校準(zhǔn)方法，各算法相似性指標(biāo)的定義描述如下。

CN指標(biāo)：認(rèn)為兩節(jié)點公共鄰居越多，產(chǎn)生連接的概率越大。給定節(jié)點x和y，其鄰居集合分別為Γ(x)和Γ(y)，則兩個節(jié)點相似性定義為

AA指標(biāo)：與CN指標(biāo)類似，考慮了共同鄰居節(jié)點度的影響，認(rèn)為度小的共同鄰居貢獻更大，并將節(jié)點的度的對數(shù)分之一作為權(quán)重分配給該節(jié)點，即

LP指標(biāo)：該指標(biāo)基于節(jié)點間路徑的相似性，根據(jù)連接兩節(jié)點間長度為2和3的路徑數(shù)量來定義節(jié)點相似性，即

RWR指標(biāo)：重啟隨機游走指標(biāo)，是一種網(wǎng)頁排序算法的擴展。根據(jù)轉(zhuǎn)移概率選擇走向下一節(jié)點還是返回初始節(jié)點，以此來捕獲兩節(jié)點間的相似性。qxy表示從節(jié)點x出發(fā)到達y的概率，定義兩節(jié)點連接概率為

3.3 實驗結(jié)果

本文實驗設(shè)計如下：選擇數(shù)據(jù)集90%的邊作為訓(xùn)練集，10%的邊作為測試集。分別對演員之間的關(guān)系A(chǔ)A，演員與導(dǎo)演之間的關(guān)系A(chǔ)D以及演員與電影類型之間的關(guān)系A(chǔ)G計算預(yù)測結(jié)果的AUC，取10次獨立實驗結(jié)果的平均值并與CN、AA、LP、RWR四種算法進行比較。本文使用的四種基準(zhǔn)方法主要應(yīng)用在同質(zhì)網(wǎng)絡(luò)領(lǐng)域，為使其可以應(yīng)用于異質(zhì)網(wǎng)絡(luò)，我們把不同類型的節(jié)點和邊視為相同類型，在進行劃分測試集和處理結(jié)果時再區(qū)分節(jié)點和邊的類型，進而比較在不同關(guān)系上的鏈路預(yù)測準(zhǔn)確度。實驗結(jié)果如圖1。

圖1 RLLP算法和其他四種算法的對比

圖1給出了RLLP算法和基準(zhǔn)算法的對比。圖中可以看出在AA關(guān)系和AD關(guān)系上，本文提出的RLLP算法均優(yōu)于其他基準(zhǔn)算法。其中AA關(guān)系的鏈路預(yù)測，平均預(yù)測準(zhǔn)確率提高了2.17%；AD關(guān)系中，平均預(yù)測準(zhǔn)確率提高了4.78%。雖然在AG關(guān)系的預(yù)測中，準(zhǔn)確率不及RWR方法，但差距不大且明顯優(yōu)于其他三種方法。除此之外，我們還研究了算法參數(shù)對預(yù)測結(jié)果準(zhǔn)確度的影響，實驗結(jié)果如圖2-圖3。

圖2 隨機游走的長度對預(yù)測結(jié)果的影響

圖3 節(jié)點向量的維度對預(yù)測結(jié)果的影響

圖2和圖3分別展示了隨機游走的長度和節(jié)點向量的維度對三種鏈接關(guān)系預(yù)測結(jié)果的影響。圖2可以看出AUC的值會隨著隨機游走長度的增加而增加，當(dāng)增加到一定值后會趨于穩(wěn)定。這也從側(cè)面印證了隨機游走對網(wǎng)絡(luò)結(jié)構(gòu)的采集效果，隨著游走長度的增加，對網(wǎng)絡(luò)結(jié)構(gòu)和語義信息的捕獲就愈加越完整，因此預(yù)測的準(zhǔn)確率就會升高。圖3顯示AUC的值會隨嵌入后的節(jié)點向量的維度的變化產(chǎn)生一個峰值，表征后的節(jié)點向量維度太低會因為特征向量無法表征網(wǎng)絡(luò)所蘊含的關(guān)系信息而影響預(yù)測準(zhǔn)確率，同時也表明預(yù)測結(jié)果并不會因維度越高而變現(xiàn)越好，甚至?xí)霈F(xiàn)下降。所以選取一個合適的向量維度才能產(chǎn)生更好的效果。

4 結(jié)語

本文提出了基于異質(zhì)網(wǎng)絡(luò)表征學(xué)習(xí)的鏈路預(yù)測模型。通過實驗可以看出，該模型對異質(zhì)網(wǎng)絡(luò)中某些類型的隱藏關(guān)系預(yù)測效果較好，可應(yīng)用于智能推薦、輔助決策等實際問題。對于下一步的研究，希望嘗試將該模型應(yīng)用于多網(wǎng)絡(luò)分析?？梢詫⒍鄠€同質(zhì)網(wǎng)絡(luò)通過關(guān)鍵節(jié)點整合成類似異質(zhì)網(wǎng)絡(luò)的結(jié)構(gòu)，分析多網(wǎng)絡(luò)間的鏈路預(yù)測。