何 媛, 吳 樂

(合肥工業(yè)大學 計算機與信息學院,安徽 合肥 230601)

隨著在線社交應(yīng)用迅速發(fā)展,產(chǎn)生了海量呈現(xiàn)網(wǎng)絡(luò)結(jié)構(gòu)的數(shù)據(jù)。以微信、微博為代表的大型在線社交網(wǎng)絡(luò)擁有巨量用戶,產(chǎn)生大量節(jié)點交互信息。網(wǎng)絡(luò)數(shù)據(jù)最大特點是數(shù)據(jù)極其稀疏且結(jié)構(gòu)極其復雜。傳統(tǒng)鏈接預測算法[1]不能很好地從原始數(shù)據(jù)中學習有價值的信息,從而不能很好適應(yīng)大數(shù)據(jù)時代對鏈接預測任務(wù)在算法效率和精度方面的更高要求。最近,研究者們探索從原始數(shù)據(jù)中學習出節(jié)點特征向量,從而可以將復雜網(wǎng)絡(luò)中的節(jié)點表示為低維、稠密的向量,進而可以將這些節(jié)點特征向量有效應(yīng)用在傳統(tǒng)網(wǎng)絡(luò)分析任務(wù)中。

網(wǎng)絡(luò)表示學習[2](network representation learning)也稱為網(wǎng)絡(luò)嵌入(network embedding),目標是將高維、稀疏的網(wǎng)絡(luò)編碼到低維、稠密的空間中,為網(wǎng)絡(luò)中的每一個節(jié)點學習一個低維的向量表示。學習到的節(jié)點特征向量蘊含了該節(jié)點的網(wǎng)絡(luò)結(jié)構(gòu)信息以及其他異構(gòu)信息,并且可以用來進行進一步的網(wǎng)絡(luò)分析任務(wù),如網(wǎng)絡(luò)節(jié)點分類[3]、鏈接預測[4]、推薦系統(tǒng)[5]等。

屬性網(wǎng)絡(luò)表示學習模型如圖1所示。屬性網(wǎng)絡(luò)是由大量節(jié)點、節(jié)點屬性以及節(jié)點之間復雜鏈接關(guān)系共同構(gòu)成的網(wǎng)絡(luò)結(jié)構(gòu),如圖1左側(cè)所示。網(wǎng)絡(luò)特征學習是將網(wǎng)絡(luò)中每一個節(jié)點都映射到一個低維向量空間,并且在此空間內(nèi)保持原有圖的結(jié)構(gòu)信息或?qū)傩孕畔?。有鏈接關(guān)系和屬性相似的點映射到特征向量空間中距離較近,如圖1所示。相反,如果2個節(jié)點之間不存在關(guān)系,那么對應(yīng)的特征向量相似度較低。關(guān)系越緊密的節(jié)點對存在鏈接關(guān)系的概率越大,在特征空間中距離越近,因此網(wǎng)絡(luò)特征學習可以有效地應(yīng)用于鏈接預測任務(wù)中。

圖1 含有鏈接關(guān)系和屬性信息的網(wǎng)絡(luò)特征學習簡化模型

近年來,網(wǎng)絡(luò)表示學習引起了大量研究者的關(guān)注。文獻[6]提出了DeepWalk算法,先采用截斷隨機游走模型將圖結(jié)構(gòu)采樣成線性節(jié)點序列,然后利用skip-gram模型從大量的線性節(jié)點序列中學習網(wǎng)絡(luò)節(jié)點的特征向量表示；文獻[7]提出的(large-scale informotion netwrok embedding,LINE)算法,設(shè)計了一個新的優(yōu)化目標函數(shù)，可以很好地學習出圖結(jié)構(gòu)中的一階信息和二階信息。近年來,考慮到網(wǎng)絡(luò)中的節(jié)點本身包含豐富的屬性信息,文獻[8]提出了TADW(text-associated DeepWalk),該框架基于矩陣分解將文本信息以一個子矩陣方式加入,學習到更為豐富的網(wǎng)絡(luò)節(jié)點特征向量。近年來,深度學習在圖像處理、視頻處理以及自然語言處理方向上取得了很好的效果,也吸引了許多學者將其用于網(wǎng)絡(luò)節(jié)點特征向量的學習。基于深度學習的模型SDNE(structural deep network embedding)[9],通過取自編碼模型的中間層作為節(jié)點二階相似性的向量表示,通過平衡有連邊的點的向量距離來考慮節(jié)點的一階相似性。SDNE良好的實驗效果驗證了深度學習模型在學習網(wǎng)絡(luò)節(jié)點特征向量時的強大能力。然而,上述模型并沒有具體研究如何將學習出的節(jié)點特征向量有效應(yīng)用于鏈接預測任務(wù)中。

鏈接預測是網(wǎng)絡(luò)分析中一個重要的應(yīng)用。鏈接預測主要是基于已知的網(wǎng)絡(luò)預測網(wǎng)絡(luò)中隱藏的鏈路,或者基于現(xiàn)在的網(wǎng)絡(luò)預測未來即將產(chǎn)生的鏈路。傳統(tǒng)的鏈接預測方法主要是基于節(jié)點相似性進行的,即2個節(jié)點越相似,它們產(chǎn)生鏈接的可能性越大?；诠餐従酉嗨菩灾笜酥饕杏嘞蚁嗨菩訹10]、Jaccard指標[11]、Sorenson指標[12]以及Adamic指標[13]。顯然,這些基于相似度的方法并不適用于復雜網(wǎng)絡(luò)鏈接預測。文獻[14]提出了利用矩陣分解模型實現(xiàn)鏈接預測的模型LMF(link prediction via matrix fractroization)。LMF模型首先將社交網(wǎng)絡(luò)用戶關(guān)系用稀疏矩陣表示,然后通過最大后驗概率方法實現(xiàn)對網(wǎng)絡(luò)鄰接矩陣進行求解。隨著網(wǎng)絡(luò)表示學習的發(fā)展,研究者們開始嘗試利用網(wǎng)絡(luò)表示學習提高鏈接預測的精度。文獻[15]提出了DeepWalk模型解決鏈接預測問題,首先將用戶存在的鏈接關(guān)系映射到低維向量空間,然后通過隨機游走重新定義用戶在向量空間上的相似性,由此大大提高了鏈接預測效果。隨著深度學習、神經(jīng)網(wǎng)絡(luò)在文本處理、圖像理解等領(lǐng)域的成功應(yīng)用,將神經(jīng)網(wǎng)絡(luò)應(yīng)用于鏈接預測成為目前研究的重點。

考慮到現(xiàn)實網(wǎng)絡(luò)中,除了網(wǎng)絡(luò)結(jié)構(gòu)信息,網(wǎng)絡(luò)節(jié)點還包含豐富的屬性信息。綜合考慮節(jié)點屬性和網(wǎng)絡(luò)結(jié)構(gòu)信息,可以緩解網(wǎng)絡(luò)數(shù)據(jù)稀疏問題。對此,本文提出一個基于屬性網(wǎng)絡(luò)表示學習的鏈接預測模型(attributed network embedding based link prediction,ANE-LP),該模型基于結(jié)構(gòu)信息和屬性信息,通過深度自動編碼器有效地學習各節(jié)點的非線性特征,從而實現(xiàn)精準的鏈接預測。主要貢獻如下:

(1) 利用深度自動編碼器模型對屬性網(wǎng)絡(luò)特征學習問題進行優(yōu)化,相比于傳統(tǒng)特征學習模型可以學出更豐富的節(jié)點特征。

(2) 提出一個基于屬性網(wǎng)絡(luò)表示學習的鏈接預測模型ANE-LP,該模型可以針對數(shù)據(jù)稀疏的特點,更好地實現(xiàn)鏈接預測。

(3) 基于TensorFlow開源工具實現(xiàn)ANE-LP模型,并在Flickr和Email-Eu-core 2個真實數(shù)據(jù)集上進行實驗,實驗結(jié)果表明ANE-LP模型取得較好效果。

1 ANE-LP模型

對于屬性網(wǎng)絡(luò)G=(V,E,X),其中，V為網(wǎng)絡(luò)節(jié)點集,且V={v1,v2,…,v|V|},|V|為節(jié)點總數(shù)；E為網(wǎng)絡(luò)中鏈接集,且ei,j∈E表示節(jié)點vi與節(jié)點vj之間鏈接關(guān)系。對于網(wǎng)絡(luò)G中每個節(jié)點vi∈V都伴隨著一個n維的屬性向量xi,向量矩陣X={x1,x2,…,x|V|}∈Rn×|V|包含所有節(jié)點屬性信息。

ANE-LP模型結(jié)構(gòu)如圖2所示。主要包括基于網(wǎng)絡(luò)結(jié)構(gòu)的節(jié)點特征學習、基于節(jié)點屬性的節(jié)點特征學習、融合節(jié)點結(jié)構(gòu)特征及屬性特征進行特征向量訓練,最后將學到的特征向量應(yīng)用于鏈接預測任務(wù)中。

圖2 ANE-LP模型

1.1 基于網(wǎng)絡(luò)結(jié)構(gòu)的節(jié)點特征學習

深度自動編碼器[16]是一種無監(jiān)督模型,訓練過程可以簡單分為編碼和解碼。通過反向傳播算法訓練網(wǎng)絡(luò),使得模型輸出數(shù)據(jù)盡可能等于輸入數(shù)據(jù)。

(1) 編碼?；诘趍-1層隱含層的輸出Hm-1(S),計算第m層隱含層的輸出Hm(S)，具體公式為：

(1)

其中,σ(·)為激活函數(shù);當m=1時,令

Hm-1(S)=S。

(2)

(3) 損失函數(shù)LS。計算公式為:

(3)

1.2 基于節(jié)點屬性的節(jié)點特征學習

對于屬性網(wǎng)絡(luò)G,基于所有節(jié)點的屬性信息矩陣X,根據(jù)杰卡德相似系數(shù)可以求出節(jié)點之間的屬性關(guān)系矩陣T,節(jié)點vi與節(jié)點vj的屬性相似度Ti,j表示為：

(4)

其中，xi、xj分別為節(jié)點vi和節(jié)點vj的屬性向量,采用獨熱編碼表示。此處將屬性向量xi、xj當作0、1數(shù)據(jù)集合，以便于計算杰卡德相似系數(shù)。

類似1.1的過程,基于屬性關(guān)系矩陣B通過深度自動編碼器可以學習出節(jié)點的屬性特征向量。訓練過程與基于網(wǎng)絡(luò)結(jié)構(gòu)的節(jié)點特征學習類似,因此其最終的損失函數(shù)LT可以表示為：

(5)

1.3 節(jié)點特征融合及屬性網(wǎng)絡(luò)鏈接預測

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

(6)

其中，ei、ej分別為節(jié)點vi、vj全局特征向量。根據(jù)以上步驟,ANE-LP模型損失函數(shù)為：

(7)

其中，Lreg為正則化部分;為防止過擬合,模型訓練使用l2歸一化方法。通過隨機梯度下降法調(diào)整參數(shù)對目標函數(shù)進行優(yōu)化求解,使得L值達到最小。

2 實 驗

實驗選用Flickr[17]和Email-Eu-core[18]2個真實數(shù)據(jù)集,2個數(shù)據(jù)集具體參數(shù)見表1所列。

表1 數(shù)據(jù)集參數(shù)

對比方法選擇LINE模型[7]、DeepWalk模型[6]、AutoRec模型[5]。LINE和DeepWalk模型是經(jīng)典網(wǎng)絡(luò)表示學習模型。通過與經(jīng)典網(wǎng)絡(luò)表示學習模型對比可以發(fā)現(xiàn)，ANE-LP模型比傳統(tǒng)網(wǎng)絡(luò)表示在鏈接預測方面的效果更好。AutoRec模型[5]是一種多層網(wǎng)絡(luò)鏈接預測模型,它利用稀疏數(shù)據(jù)深入挖掘用戶信息,實現(xiàn)更好的鏈接預測。通過與基于深度學習的鏈接預測模型對比,可以發(fā)現(xiàn)網(wǎng)絡(luò)表示學習在鏈接預測任務(wù)中的有效作用。實驗過程中取數(shù)據(jù)集中80%的點作為訓練集、10%的點作為測試集、10%的點作為驗證集。采用精確度、NDCG(normalized discounted cumulative Gain)[19]2個指標來評估ANE-LP模型及對比模型在鏈接預測任務(wù)中的效果。在不同的K值情形下,ANE-LP模型與其他模型的對比結(jié)果如圖3所示。

圖3 不同數(shù)據(jù)集下不同K對應(yīng)的精確度和NDCG

實驗表明,在不同的K值情形下,相對于其他模型,ANE-LP模型在精確度和NDCG評價指標下均取得了最優(yōu)效果。其中DeepWalk和LINE表現(xiàn)效果均優(yōu)于AutoRec,且DeepWalk效果又比LINE略好。由于DeepWalk和LINE均是基于網(wǎng)絡(luò)表示模型實現(xiàn)鏈接預測的,可以有效針對網(wǎng)絡(luò)數(shù)據(jù)稀疏的特點。另外，考慮用戶之間潛在聯(lián)系使得模型表示能力更強,可以更好地學習用戶特征向量。DeepWalk、LINE相比于ANE-LP,沒有考慮用戶的個性化信息。綜上所述，融合了用戶個性化信息的模型能夠取得更優(yōu)的預測效果。

3 結(jié) 論

針對網(wǎng)絡(luò)中存在的數(shù)據(jù)集稀疏、結(jié)構(gòu)復雜等問題,本文提出了一種基于屬性網(wǎng)絡(luò)表示方法的鏈接預測模型。該模型采用了多層神經(jīng)網(wǎng)絡(luò)對稀疏數(shù)據(jù)進行深度挖掘?qū)W習網(wǎng)絡(luò)節(jié)點深度非線性特征關(guān)系,同時考慮了網(wǎng)絡(luò)節(jié)點的屬性信息,得到了精準的節(jié)點特征描述，并將學習出的節(jié)點特征向量用于鏈接預測任務(wù)中。在Flickr和Email-Eu-core 2個真實數(shù)據(jù)集上進行的實驗結(jié)果表明,基于網(wǎng)絡(luò)表示學習實現(xiàn)鏈接預測明顯提高了預測精度。

由于訓練樣本非常稀疏,采用多層神經(jīng)網(wǎng)絡(luò)容易造成訓練模型過擬合的問題，基于本文研究工作，下一步將研究充分利用網(wǎng)絡(luò)高階結(jié)構(gòu)信息提升預測精度。