基于改進隨機游走的網絡表示學習算法

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

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

關鍵詞：網絡表示學習;隨機游走;鏈路預測;無偏采樣;機器學習

中圖分類號： TP391; TP18

文獻標志碼：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 引言

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

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

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

這些基于Word2vec的網絡表示學習算法，使用隨機游走（RW）或其改進算法來得到節點序列，然而，RW算法在采樣時會偏向大度節點，會導致采樣樣本不能正確反映完整的網絡拓撲信息[9];所以，使用RW算法生成節點序列的網絡表示學習算法，其性能也會受到節點采樣的影響。

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

1 相關問題

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

1.1 Word2vec模型

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

1.2 網絡表示學習

網絡表示學習（NRL）定義：給定網絡G（V，E），對任意節點v∈V，學習低維向量表示rv∈Rd，rv是一個稠密的低維實數向量，并且滿足d遠小于|V|。

傳統機器學習結果的好壞極度依賴人工特征設計，這一過程繁瑣且精度不高。信息化時代導致數據量激增，在龐雜的數據中尋找有價值的特征無疑是一項耗時耗力的工作，最終還很難找到令人滿意的特征。表示學習的出現就解決了這一問題，它的目標是從原始數據中自動地學習到有意義的特征表示。

網絡表示學習算法負責從網絡數據中學習得到網絡中每個節點的向量表示，之后這些節點表示就可以作為節點的特征應用于后續的網絡應用任務，如節點分類、鏈接預測和可視化等[4]。

1.3 基于Word2vec的網絡表示學習

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

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

1.4 RW及其有偏性

RW算法的思想是從當前節點出發以等概率選取其鄰居節點作為下一個采樣節點。經典的隨機游走采樣的轉移概率表達式如式（1）：

對于RW算法，G（V，E）中任意節點v被采樣到的概率是πv=kv2E[11]，其中|E|是目標采樣圖的邊數，很容易看出RW采樣時會偏向于大度節點。

2 本文方法

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

2.1 MHRW

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

MHRW算法就是在RW采樣的基礎上引入MH算法，從RW的概率密度函數中采樣，構建一個平穩分布狀態為均勻分布的馬爾可夫鏈。結合式（2）就得到了MHRW算法的轉移概率表達式如式（3）：

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

2.2 RLP-MHRW

MHRW在節點采樣時會有一定概率停留在當前節點，為了更好地理解這個停留概率這里用自環率Ci來表示節點的停留概率即Ci=Pi，i∈[0，1），MHRW導致自環率如圖3所示。

圖3中節點上的數字表示節點的度，邊上的數字（沒有畫出全部的邊）表示利用式（4）計算出來的節點間的轉移概率，為了表示自環率圖3在節點自身上加了一條自環邊?？梢钥闯龉濣cx和節點z的自環率高達0.74，節點e的自環率更是高達0.983，這意味著當游走到這些節點時將會長時間地停留在這些節點，導致采樣算法收斂慢。

在網絡表示學習中，節點序列的采樣希望能盡可能地發現節點的鄰域結構信息，類似與圖3的高自環率會導致采樣算法有限的采樣步長內丟失較多的鄰域節點;并且，轉移概率的嚴格對稱也并不合理，例如，圖3中節點e的度為1，只有一個鄰居節點f，那么從節點e只能轉移到節點f，轉移概率應該為1，而不是與f到e對等的0.017。

所以，本文進一步將MHRW算法產生的自環率去掉，得到RLP-MHRW（Remove self-Loop Probability for MHRW），并且將轉移概率變為有向，同時在去自環率的過程中保持MHRW算法原有的節點轉移概率分布比例，并且保證轉移概率矩陣行和為1。具體做法是先用MHRW算法計算出各節點轉移概率，然后將節點u的自環率Cu（非0）按照其轉移到鄰居節點的概率Pu，v的比例劃分，并將劃分得到的概率對應追加給Pu，v，數學化定義如式（5）：

2.3 算法實施

針對RW算法在圖采樣上偏向于大度節點的缺點，使用本文提到的MHRW算法和RLP-MHRW算法來進行網絡采樣生成節點序列，然后，分別利用Skip-gram模型訓練得到節點表示向量，算法定義如下。

算法2里的Sample（）函數會依據給定的概率來選擇返回的節點，利用式（4）計算P表示該算法為MHRW，利用式（5）則為RLP-MHRW。在給定網絡G=（V，E）和相關的參數后，算法1將會計算出G中所有節點的表示向量。

3 仿真與性能分析

3.1 實驗數據及數據處理

本文實驗數據為4個不同大小、不同領域、具有代表性的真實網絡數據集，均為無向無權網絡，細節分別如下：

Facebook[12] 一個美國的社交網絡，數據中節點表示用戶，邊表示用戶間的朋友關系，網絡中有4039個節點，88234條邊;

arXiv ASTRO-PH[12]（arXiv Astro Physics collaboration network） 一個從arXiv電子出版論文中生成的論文合作網絡，其中節點表示科學家，邊表示科學家合作過論文，網絡中有18722個節點，198110條邊;

USAir（http：//vlado.fmf.uni-lj.si/pub/networks/data/） 一個航空路線網絡，其中節點表示機場，邊表示機場間的航線，網絡中有332個節點，2126條邊;

Metabolic（http：//www.linkprediction.org/index.php/link/resource/data/） 一個生物代謝網絡，其中節點表示線蟲代謝物，表示代謝物之間能直接參與酶催化反應，網絡中有453個節點，2025條邊。

為了評估算法，本文將數據集隨機地劃分為訓練集和測試集，50%的邊被抽取作為訓練集，50%的邊作為測試集。在隨機劃分過程中要保證訓練集網絡的連通性，數據集的標簽依據原網絡中邊的有無來定，原網絡中存在的邊標簽為1，其他為0。

3.2 基準方法

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

DeepWalk 該方法是第一個將深度學習使用到網絡表示學習中的算法，它使用均勻隨機游走來生成節點序列，利用Skip-gram模型來學習節點向量表示;

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

node2vec node2vec是一個半監督的NRL模型，它由p、q兩個超參數來分別控制隨機游走的深度和廣度，這兩個超參數需要額外的訓練。當p=q=1時，node2vec等價于DeepWalk。

3.3 算法評價

本文網絡表示學習算法得到的是節點表示向量，要利用鏈路預測任務來測度算法的性能就需要得到邊的特征表示向量，這里直接引用文獻[2]中的映射操作，如表1所示。

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

3.4 實驗環境及參數設置

實驗硬件環境為：Intel Core i7-4790 （3.6GHz*8） CPU，32GB內存;

軟件環境為：Ubuntun16.04系統，使用python 2.7版本，主要python第三方包及版本有：用于科學計算的numpy 1.12.1版，處理網絡數據的networkx 1.11版和包含Word2vec的gensim 2.2.0版;

實驗參數：采樣迭代次數r=10，節點序列長度l=80，Skip-gram模型窗口設為10，節點向量維度為d=128。

3.5 實驗及結果分析

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