基于改進(jìn)隨機(jī)游走的網(wǎng)絡(luò)表示學(xué)習(xí)算法

王文濤 黃燁 吳淋濤 柯璇 唐菀

摘 要：現(xiàn)有的基于Word2vec的網(wǎng)絡(luò)表示學(xué)習(xí)（NRL）算法使用隨機(jī)游走（RW）來生成節(jié)點(diǎn)序列，針對隨機(jī)游走傾向于選擇具有較大度的節(jié)點(diǎn)，生成的節(jié)點(diǎn)序列不能很好地反映網(wǎng)絡(luò)結(jié)構(gòu)信息，從而影響表示學(xué)習(xí)性能的問題，提出了基于改進(jìn)隨機(jī)游走的網(wǎng)絡(luò)表示學(xué)習(xí)算法。首先，使用RLP-MHRW算法生成節(jié)點(diǎn)序列，它在生成節(jié)點(diǎn)序列時(shí)不會(huì)偏向大度節(jié)點(diǎn)，得到的節(jié)點(diǎn)序列能更好地反映網(wǎng)絡(luò)結(jié)構(gòu)信息;然后，將節(jié)點(diǎn)序列投入到Skip-gram模型得到節(jié)點(diǎn)表示向量;最后，利用鏈路預(yù)測任務(wù)來測度表示學(xué)習(xí)性能。在4個(gè)真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集上進(jìn)行了實(shí)驗(yàn)。在論文合作網(wǎng)絡(luò)arXiv ASTRO-PH上與LINE和node2vec算法相比，鏈路預(yù)測的AUC值分別提升了8.9%和3.5%，其他數(shù)據(jù)集上也均有提升。實(shí)驗(yàn)結(jié)果表明，RLP-MHRW能有效提高基于Word2vec的網(wǎng)絡(luò)表示學(xué)習(xí)算法的性能。

關(guān)鍵詞：網(wǎng)絡(luò)表示學(xué)習(xí);隨機(jī)游走;鏈路預(yù)測;無偏采樣;機(jī)器學(xué)習(xí)

中圖分類號： TP391; TP18

文獻(xiàn)標(biāo)志碼：A

文章編號：1001-9081（2019）03-0651-05

Abstract： Existing Word2vec-based Network Representation Learning （NRL） algorithms use a Random Walk （RW） to generate node sequence. The RW tends to select nodes with larger degrees， so that the node sequence can not reflect the network structure information well， decreasing the performance of the algorithm. To solve the problem， a new network representation learning algorithm based on improved random walk was proposed. Firstly， RLP-MHRW （Remove self-Loop Probability for Metropolis-Hastings Random Walk） was used to generate node sequence. This algorithm would not favor nodes with larger degrees while forming a node sequence， so that the obtained sequence can efficiently reflect the network structure information. Then， the node sequence was put into Skip-gram model to obtain the node representation vector. Finally， the performance of the network representation learning algorithm was measured by a link prediction task. Contrast experiment has been performed in four real network datasets. Compared with LINE （Large-scale Information Network Embedding） and node2vec on arXiv ASTRO-PH， the AUC （Area Under Curve） value of link prediction has increased by 8.9% and 3.5% respectively， and so do the other datasets. Experimental results show that RLP-MHRW can effectively improve the performance of the network representation learning algorithm based on Word2vec.

Key words： Network Representation Learning （NRL）; Random Walk （RW）; link prediction; unbiased sampling; Machine Learning （ML）

0 引言

有在現(xiàn)實(shí)世界中，網(wǎng)絡(luò)可以很好地描述一些關(guān)系系統(tǒng)，比如社會(huì)、生物和信息系統(tǒng)。系統(tǒng)中的每個(gè)實(shí)體都映射到網(wǎng)絡(luò)中的一個(gè)節(jié)點(diǎn)，實(shí)體之間的關(guān)系被映射到網(wǎng)絡(luò)中的邊。網(wǎng)絡(luò)結(jié)構(gòu)有助于更直觀地了解現(xiàn)實(shí)世界中的事物關(guān)系，例如，利用網(wǎng)絡(luò)結(jié)構(gòu)表示的微博數(shù)據(jù)，能很清楚地表示微博用戶的關(guān)注和被關(guān)注信息;在蛋白質(zhì)相互作用網(wǎng)絡(luò)里連邊展示了蛋白質(zhì)間能否相互反應(yīng)。但是，想要進(jìn)一步了解網(wǎng)絡(luò)的深層信息就需要用到網(wǎng)絡(luò)分析和數(shù)據(jù)挖掘的技術(shù)。網(wǎng)絡(luò)分析任務(wù)通常涉及節(jié)點(diǎn)和邊的信息預(yù)測，在一個(gè)典型的鏈路預(yù)測任務(wù)中，通常試圖根據(jù)觀察到的鏈接和節(jié)點(diǎn)的屬性來預(yù)測兩個(gè)節(jié)點(diǎn)之間是否有連接[1]。鏈路預(yù)測被廣泛地應(yīng)用于各個(gè)領(lǐng)域[2]，越來越多的國內(nèi)外學(xué)者開始研究復(fù)雜網(wǎng)絡(luò)中的鏈接預(yù)測問題[3]。

隨著機(jī)器學(xué)習(xí)算法的盛行，越來越多的機(jī)器學(xué)習(xí)算法被設(shè)計(jì)出來，其性能也遠(yuǎn)超傳統(tǒng)算法。但是，網(wǎng)絡(luò)結(jié)構(gòu)數(shù)據(jù)不能直接作為機(jī)器學(xué)習(xí)算法的輸入，一個(gè)直觀的想法就是將網(wǎng)絡(luò)結(jié)構(gòu)特征提取出來并嵌入到向量中，將這個(gè)特征向量作為機(jī)器學(xué)習(xí)算法的輸入實(shí)現(xiàn)網(wǎng)絡(luò)分析任務(wù)。這個(gè)向量必須要盡可能地包含原始網(wǎng)絡(luò)結(jié)構(gòu)的信息，且維度不能太大，網(wǎng)絡(luò)表示學(xué)習(xí)（Network Representation Learning， NRL）就正好滿足了這一需求。網(wǎng)絡(luò)表示學(xué)習(xí)算法將網(wǎng)絡(luò)信息轉(zhuǎn)換為低維實(shí)值向量[4]，在學(xué)習(xí)到低維向量之后，就可以使用現(xiàn)有的機(jī)器學(xué)習(xí)方法來簡單高效地執(zhí)行網(wǎng)絡(luò)分析任務(wù)，這不僅避免了傳統(tǒng)方法的復(fù)雜計(jì)算，還提高了算法性能[5]。

Mikolov等在文獻(xiàn)[6]中提出的Word2vec神經(jīng)網(wǎng)絡(luò)語言模型在詞表示上取得良好效果，Perozzi等受此文啟發(fā)在文獻(xiàn)[7]提出DeepWalk算法，第一次將深度學(xué)習(xí)中的技術(shù)引入到網(wǎng)絡(luò)表示學(xué)習(xí)領(lǐng)域，文中作者利用隨機(jī)游走（Random Walk， RW）從網(wǎng)絡(luò)中生產(chǎn)節(jié)點(diǎn)序列類比于“句子”，將節(jié)點(diǎn)類比于“詞”投入到Word2vec模型中得到節(jié)點(diǎn)表示向量，在網(wǎng)絡(luò)分析任務(wù)上取得較大的性能提升。隨后又出現(xiàn)了基于簡單神經(jīng)網(wǎng)絡(luò)的LINE（Large-scale Information Network Embedding）[8]和改進(jìn)DeepWalk的node2vec[2]等算法。LINE算法沒有延用DeepWalk的思想，而是對所有的第一級相似度和第二級相似度節(jié)點(diǎn)對進(jìn)行概率建模，最小化概率分布和經(jīng)驗(yàn)分布的距離來得到表示結(jié)果，有著較好的表示效果;node2vec算法在生成節(jié)點(diǎn)序列時(shí)沒有像DeepWalk那樣均勻地隨機(jī)選取下一節(jié)點(diǎn)，而是引入p、q兩個(gè)超參數(shù)來均衡采樣過程的采樣深度和寬度，提升了算法的擴(kuò)展性，同時(shí)還提高了節(jié)點(diǎn)表示的性能。

這些基于Word2vec的網(wǎng)絡(luò)表示學(xué)習(xí)算法，使用隨機(jī)游走（RW）或其改進(jìn)算法來得到節(jié)點(diǎn)序列，然而，RW算法在采樣時(shí)會(huì)偏向大度節(jié)點(diǎn)，會(huì)導(dǎo)致采樣樣本不能正確反映完整的網(wǎng)絡(luò)拓?fù)湫畔9];所以，使用RW算法生成節(jié)點(diǎn)序列的網(wǎng)絡(luò)表示學(xué)習(xí)算法，其性能也會(huì)受到節(jié)點(diǎn)采樣的影響。

針對這一問題，分別使用MHRW（Metropolis-Hastings Random Walk）[10]和改進(jìn)后的MHRW代替RW生成節(jié)點(diǎn)序列，旨在使采樣得到的節(jié)點(diǎn)序列能更好地保留原網(wǎng)絡(luò)的結(jié)構(gòu)特征。為了測度網(wǎng)絡(luò)表示學(xué)習(xí)算法的性能，本文使用常見的網(wǎng)絡(luò)分析任務(wù)——鏈路預(yù)測來衡量網(wǎng)絡(luò)表示學(xué)習(xí)算法的性能。最終實(shí)驗(yàn)結(jié)果顯示，相比基準(zhǔn)對比算法，本文所提算法有更好的鏈路預(yù)測效果，即本文所提網(wǎng)絡(luò)表示學(xué)習(xí)算法有更好的表示性能。

1 相關(guān)問題

本章主要介紹與本文工作相關(guān)的定義、模型和問題。

1.1 Word2vec模型

Mikolov在文獻(xiàn)[6]中提出Word2vec神經(jīng)網(wǎng)絡(luò)語言模型，該模型能通過給定文本快速地學(xué)習(xí)詞向量表示。Word2vec中包含CBOW（Continuous Bag-Of-Words model）和Skip-gram（continuous skip-gram model）兩種語言模型。前者利用詞的上下文來預(yù)測中間詞;后者則利用當(dāng)前詞來預(yù)測其上下文。在使用Word2vec時(shí)可以通過設(shè)置相應(yīng)的參數(shù)來選擇所要使用的模型。這兩個(gè)模型都是包含輸入層、投影層和輸出層的三層神經(jīng)網(wǎng)絡(luò)，如圖1所示。

1.2 網(wǎng)絡(luò)表示學(xué)習(xí)

網(wǎng)絡(luò)表示學(xué)習(xí)（NRL）定義：給定網(wǎng)絡(luò)G（V，E），對任意節(jié)點(diǎn)v∈V，學(xué)習(xí)低維向量表示rv∈Rd，rv是一個(gè)稠密的低維實(shí)數(shù)向量，并且滿足d遠(yuǎn)小于|V|。

傳統(tǒng)機(jī)器學(xué)習(xí)結(jié)果的好壞極度依賴人工特征設(shè)計(jì)，這一過程繁瑣且精度不高。信息化時(shí)代導(dǎo)致數(shù)據(jù)量激增，在龐雜的數(shù)據(jù)中尋找有價(jià)值的特征無疑是一項(xiàng)耗時(shí)耗力的工作，最終還很難找到令人滿意的特征。表示學(xué)習(xí)的出現(xiàn)就解決了這一問題，它的目標(biāo)是從原始數(shù)據(jù)中自動(dòng)地學(xué)習(xí)到有意義的特征表示。

網(wǎng)絡(luò)表示學(xué)習(xí)算法負(fù)責(zé)從網(wǎng)絡(luò)數(shù)據(jù)中學(xué)習(xí)得到網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)的向量表示，之后這些節(jié)點(diǎn)表示就可以作為節(jié)點(diǎn)的特征應(yīng)用于后續(xù)的網(wǎng)絡(luò)應(yīng)用任務(wù)，如節(jié)點(diǎn)分類、鏈接預(yù)測和可視化等[4]。

1.3 基于Word2vec的網(wǎng)絡(luò)表示學(xué)習(xí)

Word2vec神經(jīng)網(wǎng)絡(luò)語言模型最初是用來學(xué)習(xí)詞表示向量的，Perozzi等在DeepWalk中第一次把Word2vec應(yīng)用到網(wǎng)絡(luò)表示學(xué)習(xí)中來，他們把在網(wǎng)絡(luò)中利用RW采樣得到的節(jié)點(diǎn)序列類比“句子”，把節(jié)點(diǎn)類比“詞”，投入到Word2vec模型中得到了節(jié)點(diǎn)的表示向量，并獲得了很好的表示效果。算法的整體框架如圖2所示。

圖2中，k表示節(jié)點(diǎn)序列的長度，d表示表示向量的維度。從圖2可以看出，采樣算法得到的節(jié)點(diǎn)序列是影響后續(xù)產(chǎn)生的節(jié)點(diǎn)表示特征向量的關(guān)鍵步驟之一，所以采樣算法的性能也將直接影響到整個(gè)模型的性能。

1.4 RW及其有偏性

RW算法的思想是從當(dāng)前節(jié)點(diǎn)出發(fā)以等概率選取其鄰居節(jié)點(diǎn)作為下一個(gè)采樣節(jié)點(diǎn)。經(jīng)典的隨機(jī)游走采樣的轉(zhuǎn)移概率表達(dá)式如式（1）：

對于RW算法，G（V，E）中任意節(jié)點(diǎn)v被采樣到的概率是πv=kv2E[11]，其中|E|是目標(biāo)采樣圖的邊數(shù)，很容易看出RW采樣時(shí)會(huì)偏向于大度節(jié)點(diǎn)。

2 本文方法

這一章里，首先介紹了MHRW算法的思想并在推導(dǎo)過程中說明了MHRW采樣的無偏性，隨后就MHRW算法的缺點(diǎn)進(jìn)行了討論和改進(jìn)。

2.1 MHRW

文獻(xiàn)[10]中提出的MHRW算法是一種無偏采樣算法，對于MHRW算法，G（V，E）中任意節(jié)點(diǎn)v被采樣到的概率是πv=1/|V|，即任意節(jié)點(diǎn)被采樣到的概率是相等的。MHRW算法是借鑒了MH（Metropolis-Hasting）[10]算法的思想而形成的。

MHRW算法就是在RW采樣的基礎(chǔ)上引入MH算法，從RW的概率密度函數(shù)中采樣，構(gòu)建一個(gè)平穩(wěn)分布狀態(tài)為均勻分布的馬爾可夫鏈。結(jié)合式（2）就得到了MHRW算法的轉(zhuǎn)移概率表達(dá)式如式（3）：

從式（4）可以看出，MHRW算法的節(jié)點(diǎn)轉(zhuǎn)移概率是由當(dāng)前節(jié)點(diǎn)u的度和其鄰居節(jié)點(diǎn)v的度共同決定的，當(dāng)v=u時(shí)，表示節(jié)點(diǎn)停留在當(dāng)前節(jié)點(diǎn)。從MHRW算法的公式推導(dǎo)過程容易看出，MHRW采樣算法是等概率采樣任意節(jié)點(diǎn)，即MHRW是無偏的。

2.2 RLP-MHRW

MHRW在節(jié)點(diǎn)采樣時(shí)會(huì)有一定概率停留在當(dāng)前節(jié)點(diǎn)，為了更好地理解這個(gè)停留概率這里用自環(huán)率Ci來表示節(jié)點(diǎn)的停留概率即Ci=Pi，i∈[0，1），MHRW導(dǎo)致自環(huán)率如圖3所示。

圖3中節(jié)點(diǎn)上的數(shù)字表示節(jié)點(diǎn)的度，邊上的數(shù)字（沒有畫出全部的邊）表示利用式（4）計(jì)算出來的節(jié)點(diǎn)間的轉(zhuǎn)移概率，為了表示自環(huán)率圖3在節(jié)點(diǎn)自身上加了一條自環(huán)邊?？梢钥闯龉?jié)點(diǎn)x和節(jié)點(diǎn)z的自環(huán)率高達(dá)0.74，節(jié)點(diǎn)e的自環(huán)率更是高達(dá)0.983，這意味著當(dāng)游走到這些節(jié)點(diǎn)時(shí)將會(huì)長時(shí)間地停留在這些節(jié)點(diǎn)，導(dǎo)致采樣算法收斂慢。

在網(wǎng)絡(luò)表示學(xué)習(xí)中，節(jié)點(diǎn)序列的采樣希望能盡可能地發(fā)現(xiàn)節(jié)點(diǎn)的鄰域結(jié)構(gòu)信息，類似與圖3的高自環(huán)率會(huì)導(dǎo)致采樣算法有限的采樣步長內(nèi)丟失較多的鄰域節(jié)點(diǎn);并且，轉(zhuǎn)移概率的嚴(yán)格對稱也并不合理，例如，圖3中節(jié)點(diǎn)e的度為1，只有一個(gè)鄰居節(jié)點(diǎn)f，那么從節(jié)點(diǎn)e只能轉(zhuǎn)移到節(jié)點(diǎn)f，轉(zhuǎn)移概率應(yīng)該為1，而不是與f到e對等的0.017。

所以，本文進(jìn)一步將MHRW算法產(chǎn)生的自環(huán)率去掉，得到RLP-MHRW（Remove self-Loop Probability for MHRW），并且將轉(zhuǎn)移概率變?yōu)橛邢颍瑫r(shí)在去自環(huán)率的過程中保持MHRW算法原有的節(jié)點(diǎn)轉(zhuǎn)移概率分布比例，并且保證轉(zhuǎn)移概率矩陣行和為1。具體做法是先用MHRW算法計(jì)算出各節(jié)點(diǎn)轉(zhuǎn)移概率，然后將節(jié)點(diǎn)u的自環(huán)率Cu（非0）按照其轉(zhuǎn)移到鄰居節(jié)點(diǎn)的概率Pu，v的比例劃分，并將劃分得到的概率對應(yīng)追加給Pu，v，數(shù)學(xué)化定義如式（5）：

2.3 算法實(shí)施

針對RW算法在圖采樣上偏向于大度節(jié)點(diǎn)的缺點(diǎn)，使用本文提到的MHRW算法和RLP-MHRW算法來進(jìn)行網(wǎng)絡(luò)采樣生成節(jié)點(diǎn)序列，然后，分別利用Skip-gram模型訓(xùn)練得到節(jié)點(diǎn)表示向量，算法定義如下。

算法2里的Sample（）函數(shù)會(huì)依據(jù)給定的概率來選擇返回的節(jié)點(diǎn)，利用式（4）計(jì)算P表示該算法為MHRW，利用式（5）則為RLP-MHRW。在給定網(wǎng)絡(luò)G=（V，E）和相關(guān)的參數(shù)后，算法1將會(huì)計(jì)算出G中所有節(jié)點(diǎn)的表示向量。

3 仿真與性能分析

3.1 實(shí)驗(yàn)數(shù)據(jù)及數(shù)據(jù)處理

本文實(shí)驗(yàn)數(shù)據(jù)為4個(gè)不同大小、不同領(lǐng)域、具有代表性的真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集，均為無向無權(quán)網(wǎng)絡(luò)，細(xì)節(jié)分別如下：

Facebook[12] 一個(gè)美國的社交網(wǎng)絡(luò)，數(shù)據(jù)中節(jié)點(diǎn)表示用戶，邊表示用戶間的朋友關(guān)系，網(wǎng)絡(luò)中有4039個(gè)節(jié)點(diǎn)，88234條邊;

arXiv ASTRO-PH[12]（arXiv Astro Physics collaboration network） 一個(gè)從arXiv電子出版論文中生成的論文合作網(wǎng)絡(luò)，其中節(jié)點(diǎn)表示科學(xué)家，邊表示科學(xué)家合作過論文，網(wǎng)絡(luò)中有18722個(gè)節(jié)點(diǎn)，198110條邊;

USAir（http：//vlado.fmf.uni-lj.si/pub/networks/data/） 一個(gè)航空路線網(wǎng)絡(luò)，其中節(jié)點(diǎn)表示機(jī)場，邊表示機(jī)場間的航線，網(wǎng)絡(luò)中有332個(gè)節(jié)點(diǎn)，2126條邊;

Metabolic（http：//www.linkprediction.org/index.php/link/resource/data/） 一個(gè)生物代謝網(wǎng)絡(luò)，其中節(jié)點(diǎn)表示線蟲代謝物，表示代謝物之間能直接參與酶催化反應(yīng)，網(wǎng)絡(luò)中有453個(gè)節(jié)點(diǎn)，2025條邊。

為了評估算法，本文將數(shù)據(jù)集隨機(jī)地劃分為訓(xùn)練集和測試集，50%的邊被抽取作為訓(xùn)練集，50%的邊作為測試集。在隨機(jī)劃分過程中要保證訓(xùn)練集網(wǎng)絡(luò)的連通性，數(shù)據(jù)集的標(biāo)簽依據(jù)原網(wǎng)絡(luò)中邊的有無來定，原網(wǎng)絡(luò)中存在的邊標(biāo)簽為1，其他為0。

3.2 基準(zhǔn)方法

為了展示算法性能，本文選用以下算法作為對比：

DeepWalk 該方法是第一個(gè)將深度學(xué)習(xí)使用到網(wǎng)絡(luò)表示學(xué)習(xí)中的算法，它使用均勻隨機(jī)游走來生成節(jié)點(diǎn)序列，利用Skip-gram模型來學(xué)習(xí)節(jié)點(diǎn)向量表示;

LINE 該方法將學(xué)習(xí)d維的特征表示分為兩部分：第一部分，在直接鄰居節(jié)點(diǎn)上模擬BFS（Breadth-First Search）來學(xué)習(xí)d/2維的特征;第二部分，嚴(yán)格的從距離源節(jié)點(diǎn)2-hop的節(jié)點(diǎn)中采樣學(xué)習(xí)剩下的d/2為特征;

node2vec node2vec是一個(gè)半監(jiān)督的NRL模型，它由p、q兩個(gè)超參數(shù)來分別控制隨機(jī)游走的深度和廣度，這兩個(gè)超參數(shù)需要額外的訓(xùn)練。當(dāng)p=q=1時(shí)，node2vec等價(jià)于DeepWalk。

3.3 算法評價(jià)

本文網(wǎng)絡(luò)表示學(xué)習(xí)算法得到的是節(jié)點(diǎn)表示向量，要利用鏈路預(yù)測任務(wù)來測度算法的性能就需要得到邊的特征表示向量，這里直接引用文獻(xiàn)[2]中的映射操作，如表1所示。

鏈路預(yù)測的結(jié)果度量使用AUC（Area Under the receiver operating characteristic Curve）值作為算法評價(jià)指標(biāo)，AUC是常用的二值分類評價(jià)標(biāo)準(zhǔn)，從整體上評價(jià)算法精度。利用預(yù)測算法計(jì)算出所有節(jié)點(diǎn)間邊存在的分值，AUC值可以看作是在測試集中隨機(jī)選取一條存在邊的分值大于隨機(jī)一條不存在的邊分值的概率。一般AUC值會(huì)大于0.5，值越高算法精度越高，最大不超過1。公式化的定義如下：

3.4 實(shí)驗(yàn)環(huán)境及參數(shù)設(shè)置

實(shí)驗(yàn)硬件環(huán)境為：Intel Core i7-4790 （3.6GHz*8） CPU，32GB內(nèi)存;

軟件環(huán)境為：Ubuntun16.04系統(tǒng)，使用python 2.7版本，主要python第三方包及版本有：用于科學(xué)計(jì)算的numpy 1.12.1版，處理網(wǎng)絡(luò)數(shù)據(jù)的networkx 1.11版和包含Word2vec的gensim 2.2.0版;

實(shí)驗(yàn)參數(shù)：采樣迭代次數(shù)r=10，節(jié)點(diǎn)序列長度l=80，Skip-gram模型窗口設(shè)為10，節(jié)點(diǎn)向量維度為d=128。

3.5 實(shí)驗(yàn)及結(jié)果分析

為了更方便地將本文方法與相關(guān)基線進(jìn)行比較，本文將鏈接預(yù)測作為所有方法的下游任務(wù)。對于所有的模型，使用邏輯回歸來預(yù)測。為了減弱隨機(jī)性，將本文所提算法在3.1節(jié)提到的數(shù)據(jù)集上獨(dú)立重復(fù)實(shí)驗(yàn)20次，以20次實(shí)驗(yàn)的AUC平均值作為最終結(jié)果。表2為各算法在預(yù)測結(jié)果上AUC值的對比，表3為MHRW和RLP-MHRW生成節(jié)點(diǎn)序列的執(zhí)行時(shí)間的對比。