基于CBOW模型的鏈路預測方法

趙宇紅，張 政

(內蒙古科技大學 信息工程學院，內蒙古 包頭 014010)

1 引 言

在網絡理論研究中，復雜網絡是由數量眾多的節點和節點之間錯綜復雜的關系共同構成的網絡[1].復雜網絡擁有眾多形式，既不是完全規則，也不是完全隨機.現實世界中存在的網絡一般都是復雜網絡，比如常見的電力網絡、航空網絡、計算機網絡以及社交網絡等.復雜網絡的研究是網絡研究中的一大熱點，而鏈路預測能夠對復雜網絡中的缺失信息或隱含信息進行預測，從而有效挖掘和呈現內在的信息與規則，因此吸引著越來越多研究者的關注.

鏈路預測的目標體現在對于網絡中實際存在但是還沒有被探測到的鏈路的預測或對網絡中目前不存在，但應該存在或者是未來有可能存在的鏈路的預測[2].復雜網絡中的鏈路預測是指通過已知的網絡節點信息以及網絡結構信息等，預測網絡中尚未產生連邊的兩個節點之間產生連接的可能性，在實際應用中有著巨大的價值.例如，在蛋白質相互作用網絡中通過鏈路預測結果指導試驗，提高試驗的成功率從而降低試驗成本[3]；在社交網絡中通過鏈路預測方法對用戶進行好友推薦[4]，提高相關網站在用戶心中的地位和用戶對網站的忠誠度；在電子商務網絡中，通過對用戶歷史行為和購買記錄進行分析，為用戶推薦相應產品或者電影，在吸引用戶、推廣產品等方面具有重要的作用[5].

隨著計算機硬件技術的進步，計算機運算能力得到巨大提升，人工神經網絡算法得以高效率運行，深度學習得到前所未有的發展，使深度學習成為熱門的研究方向，其在圖像處理、音頻處理以及自然語言處理等領域的成功運用為解決鏈路預測問題帶來了啟發.文獻[6]提出兩種模型架構—CBOW(Continuous Bag of Words)和skip-gram，用來計算大規模數據集中的連續詞向量表示.對計算得出的結果通過詞相似性任務進行評估.兩種模型分別通過上下文對中心詞進行評估以及通過中心詞對上下文進行評估，在自然語言處理中應用十分廣泛，且計算成本相對較小.

近年來，鏈路預測方法僅僅考慮節點自身屬性信息或者僅僅考慮節點所處的網絡結構信息，這兩類方法都只考慮復雜網絡中的部分信息.

本文從概率語言模型訓練產生的詞向量得到啟發，向量作為原生信息在空間中的呈現，是信息本質特征的內在表現.網絡中的節點可以看作是自然語言處理過程中的詞，在網絡演化中，節點本身的特性與結構關聯將形成節點的上下文信息.為了有效、全面地獲取網絡中的節點序列信息，將節點序列看作是具有意義的句子，考慮每一個節點出現在節點序列某一位置的概率，提出基于連續詞帶模型(Continuous Bag of Words，CBOW)的鏈路預測方法.使用深度優先搜索(DFS)獲得包含網絡結構信息的節點路徑，再結合使用廣度優先搜索(BFS)獲得的節點n階鄰居信息的節點序列，可以獲取節點序列的完整信息.使用CBOW模型通過中心節點的上下文節點序列訓練產生節點對應的向量表示.向量的方向與大小是向量的原生信息，因此提出一種節點向量相似性指標—向量自量趨向性(Self-measurement Tendency of Vector，SMTV)，以此指標完成度量并進行鏈路預測.通過在3個真實網絡數據集中進行的對比試驗，本文提出的方法相比其他經典算法在預測精確度方面表現更好.

2 相關工作

2.1 基于相似性的鏈路預測方法

基于相似性的鏈路預測方法從度量角度不同分為基于節點相似性的預測方法和基于網絡結構相似性的預測方法.

2.1.1 基于節點相似性的鏈路預測

在網絡中單純考慮節點之間屬性的相似程度就可以判斷兩個節點是否相似，屬性相似的節點之間更容易連接[7].在網絡中刻畫節點屬性的相似性，最簡單直接的方法就是利用節點的標簽.比如，網絡虛擬身份中的職業、地區、教育程度、興趣愛好、性別等，利用上述屬性在社交網絡中進行好友推薦，就可能找到潛在的好友.但是，由于網絡自由性和監管問題，在很多情況下，獲取網絡節點的真實屬性信息是不現實的，例如，在社交網絡中，個人用戶注冊的信息可能是虛假的，因此將虛假信息作為節點的屬性進行鏈路預測就變得不可信.

2.1.2 基于網絡結構相似性的鏈路預測

在網絡中難以獲得真實節點屬性信息的時候，一種可行的方法是根據網絡結構來計算節點的相似性.如果在網絡中兩個節點所處的網絡結構越相似，那么它們之間存在連邊的可能性越大.

基于網絡結構信息的相似性預測方法最經典的就是共同鄰居(CommonNeighbors，CN)[8]，即兩個節點如果有更多的共同鄰居，則它們的相似性越高，越有可能產生連邊.其公式如公式(1)所示:

(1)

CN方法認為每個共同鄰居對于這兩個節點的貢獻度是相同的，但是，通常共同的鄰居節點對于節點的貢獻度可能是不同的.一般情況下我們認為度大的共同鄰居比度小的共同鄰居貢獻度小.基于兩節點共同鄰居的度的信息的Adamic-Adar(AA)指標[9]，根據共同鄰居節點的度為每個節點賦予一個權重值，該權重等于節點的度的對數分之一.其公式如公式(2)所示:

(2)

其中kz代表節點z的度.如果節點a和節點b共同鄰居節點的度越大，那么該指標分數值越低.

基于共同鄰居的相似性指標的優勢在于計算復雜度較低，但是由于使用的信息非常有限，預測精度受到限制.例如在Internet路由器網絡中，由5000多個節點構成的一千多萬節點對中有超過99%的節點對之間的CN相似性分數都是0，剩下的節點對中也有超過90%的節點對分數是1，只有不到5%的分數是2，導致的結果是相似性分數過于集中，節點對之間的區分度太低，鏈路預測的精度受限[10].周濤等人[11，12]在共同鄰居的基礎上考慮三階路徑的因素，提出基于局部信息相似性的Local Path(LP)指標.即在考慮共同鄰居的基礎上，繼續考慮兩個節點之間通過三條路徑即兩個節點進行連接的路徑條數，結合兩者計算兩節點之間的相似性，計算公式如公式(3)所示:

(3)

其中α為可調參數，A表示網絡的鄰接矩陣，(A3)xy表示節點vx和vy之間長度為3的路徑數目.

2.2 基于機器學習的鏈路預測方法

機器學習鏈路預測方法使用較多的是隨機游走算法.文獻[13]提出一種基于隨機游走的DeepWalk方法，該方法首先在網絡上等概率隨機采樣產生大量的隨機游走序列，之后使用模型對隨機游走序列中每個局部窗口內的節點對進行概率建模.隨機游走就是從某一特定的節點出發，每次游走都從當前節點連接的邊集合中選擇一條，沿著選定的邊移動到下一個節點的過程.利用流式的、短的隨機游走，提出了一個通用的語言模型用來探究圖結構，根據隨機游走中包含的頂點來估計下一個頂點出現的概率，如公式(4)所示：

Pr(vi|(v1，v2，…，vi-1))

(4)

文獻[14]提出一種與度分布一致的初始資源分布方法，此方法只考慮有限步長的隨機游走過程.從某一節點x出發之后開始進行隨機游走，定義πxy(t)為t+1步正好游走到的節點y的概率，得到基于t步隨機游走的相似性指標，如公式(5)所示：

sxy(t)=qxπxy(t)+qyπyx(t)

(5)

其中q表示節點的初始化資源分布.通過大量實驗比較得出由于此方法采用有限步長的隨機游走，因此算法復雜度較低，對于規模較大甚至較稀疏的網絡都很適用.

Node2vec[15]對隨機游走方法進行了改進，在對網絡中的節點進行游走遍歷的時候不使用等概率的隨機游走，而是使用一種具有回溯并且非均等概率的游走的方式對網絡上的節點進行采樣.定義了兩個參數p，q指導的二階隨機游走概率，如公式(6)所示：

(6)

其中αpq(t,x)表示游走的概率，dtx表示節點x到節點t的邊數.通過3個真實世界數據集中的對比實驗結果表明Node2vec-Hadamard方法的結果要比單純使用DeepWalk-Hadamard的方法效果更好.在隨機游走過程中，只能考慮節點的某一個鄰居節點以及獲得一條包含有隨機連通信息的路徑，對于鄰居信息的提取不夠完全，對于連通信息的提取也太過隨機.

張牧涵等人[16]開發了一種γ衰減啟發式理論，將眾多鏈路預測相似性指標函數統一在一個框架中，并證明可以從局部子圖中很好地近似這些相似性指標函數，并基于此理論提出圖神經網絡從局部子圖中學習相似性算法的方法.

文獻[17]根據相似度的性能改進，提出一種基于引力的無監督鏈路預測方法，通過集成節點特征、社區信息和圖屬性來減小預測空間，從而提高局部和全局預測的準確性.

在現有相關研究中，對節點本身的屬性和網絡結構信息在鏈路預測共同作用考慮不足，且全面與準確刻畫節點的自身及空間信息仍有待改善，本文綜合考慮這些問題，提出基于CBOW的鏈路預測方法—CBOW-SMTV.利用深度優先搜索和廣度優先搜索分別獲得包含有網絡連通信息的節點序列以及節點鄰居信息的節點序列，這些節點序列共同構成訓練模型的節點序列庫.CBOW模型通過考慮節點序列的順序關系來訓練節點序列庫從而得到節點的向量表示，以向量的原生特征對節點進行刻畫，將節點自身屬性信息映射為節點向量自身的模長屬性，將兩節點的相互關系映射為節點向量之間的趨向信息，同時考慮這兩種信息，提出一種新的相似性指標來度量節點向量的相似性并進行鏈路預測.

3 模型與算法

本文算法的具體流程圖如圖1所示.首先對給定的數據集進行訓練集和測試集的劃分，在訓練集構造的網絡中分別使用DFS和BFS搜索策略獲得節點序列庫；將節點序列庫輸入CBOW模型進行訓練，得到每個節點的節點向量；使用SMTV計算邊的相似性分數，從而確定鏈路預測準確度AUC的值.

圖1 CBOW-SMTV模型框架Fig.1 CBOW-SMTV model framework

3.1 CBOW模型

CBOW是一種神經概率語言模型，廣泛應用于自然語言處理領域.該模型使用中心詞的上下文來預測中心詞概率，即在已知當前詞wt的上下文：wt-n，wt-n+1，…，wt+n-1，wt+n的前提下預測當前詞wt的概率，極大地考慮了周圍詞對于中心詞的影響.模型的結構圖如圖2所示.

圖2 CBOW模型結構圖Fig.2 CBOW model structure

圖2給出了的CBOW模型的網絡結構，包括3層：輸入層、隱藏層和輸出層.輸入層輸入中心節點的上下文節點的初始化向量，這個向量通常是獨熱表示(One-hot Representation)，或者是分散表示(Distributed Representation)，這兩種表示都可以對每個節點向量進行初始化表示，本文使用分散表示，克服維度災難的困擾[18].隱藏層將輸入層輸入的節點向量做求和累加.輸出層對應一棵哈夫曼樹，這棵哈夫曼樹對應一棵以節點序列庫中出現過的節點為葉子節點，以各節點在節點序列庫中出現的次數為權值構造出來的二叉樹，采用的編碼策略是將編碼為1的節點定義為負類，而將編碼為0的節點定義為正類.

CBOW作為基于神經網絡的語言模型，對于中心詞n，其優化的目標函數的形式如公式(7)所示：

(7)

3.2 目標函數

對于節點序列庫中出現每一個節點都對應輸出的哈夫曼樹的一個葉子節點，那么任意一個葉子節點一定存在一條從根節點到葉子節點的路徑path，且這條路徑唯一存在.假設這條路徑中包含l個節點，則路徑path上存在l-1個分支，將每個分支看作一次二分類問題，每次分類都會產生一個概率，將這些分支產生的概率相乘得到公式(7)需要的p(n|Context(n)).

(8)

公式(8)中：

(9)

(10)

結合式(7)-式(10)，得到如公式(11)所示對數似然函數表達式，即為CBOW模型的目標函數：

(11)

簡記為：

(12)

由于目標函數是對數似然函數，且表示的意義是最大化在上下文出現對應節點的情況下中心節點出現的概率，所以優化目標函數的目的就是使目標函數最大化，這里使用求最大值的隨機梯度上升法.使用隨機梯度上升法得到非葉子節點對應的更新函數如下：

(13)

(14)

(15)

3.3 節點序列選取

使用CBOW訓練模型的先導步驟就是構造節點序列庫.傳統構造節點序列的方法是從某一節點出發使用隨機游走產生一條指定長度的節點序列，但是使用這一方法產生的序列隨機性太強，即便是使用有偏向的隨機游走策略[13].這種節點序列產生的是具有隨機性和帶有偏向隨機性的節點序列.例如，從網絡中的某一節點出發，為尋找下一節點而進行隨機游走時，在此節點所有鄰居節點中只隨機選取一個，沒有考慮所有鄰居節點對于這個節點的影響，對于網絡節點的采樣具有一定局限性.本文使用從某一節點出發的深度優先搜索策略(DFS)結合廣度優先搜索策略(BFS)，對網絡中的節點進行采樣.

DFS沿著網絡中的某一節點v，盡可能深的搜索網絡分支，當節點v的所在的邊都被搜索過之后，搜索算法回溯到發現節點v的那一條邊的起始點.這個過程一直進行到已發現從源節點可達的所有節點為止.深度優先搜索是圖論中的經典算法，利用深度優先搜索可以產生目標圖的相應拓撲排序表也就是本文中使用的節點序列，這個節點序列包含整個網絡中每個節點的連通路徑信息.BFS是從選定節點v開始，沿著節點v向周圍進行搜索，如果所有節點均被訪問，則算法終止.在網絡中對某一節點進行廣度優先搜索，如果搜索深度為1，則得到的是與這個節點直接相連的節點序列，也就是這個節點的一階鄰居信息；如果搜索深度為2，則搜索結果為直接與此節點相連的節點序列以及通過兩條邊間接與此節點相連的節點序列，即節點的一階鄰居信息加上二階鄰居信息.通過設定廣度優先搜索策略的搜索深度2獲得包含節點的共2階鄰居信息的節點序列.通過BFS和DFS策略，將得到的序列整合在一起，組成包含了網絡連通性信息和節點局部信息的節點序列庫，使得下一步的訓練模型更具有針對性.

以圖3所示為例，從節點1出發，使用深度優先搜索得到的節點序列為：{1,2,4,8,7,6,3}，包含了在此網絡中從節點1出發的連通信息.使用一階廣度優先搜索得到的節點序列為：{1,2,5}，包含節點的一階鄰居信息.使用二階廣度搜索得到的節點序列為：{1,2,5,4,6}，包含了節點的二階鄰居信息.使用這些節點序列，結合CBOW模型使用中心節點的上下文節點序列信息構造節點向量的特征，能夠更好的提高鏈路預測準確性.

圖3 BFS和DFS的序列搜索策略Fig.3 BFS and DFS sequence search strategy

3.4 SMTV指標

在得到包含網絡連通性信息和節點局部信息的節點序列庫之后，使用CBOW模型訓練得到每個節點對應的向量表示.網絡節點向量化表示之后，使得網絡節點具有向量本身的特征，傳統節點相似性指標在進行向量度量上不能很好表現向量的本質特性.首先，向量化的節點可以看作是在對應維度的空間中的向量，那么，兩向量的延展特性可以理解為空間趨向，其相似性就可以通過兩個向量的余弦相似性進行表示，余弦相似性計算如公式(16)所示：

(16)

其次，向量本身的模長作為衡量向量大小的原生屬性，也可以度量向量間的相似性.向量模長的計算如公式(17)所示：

(17)

結合向量原生的特征即大小和其演化表現即延展趨向，本文提出了衡量向量化節點的相似性的指標—SMTV，稱為向量自量趨向性(self-measurement tendency of vector，SMTV).該指標綜合考慮節點向量的原生特征及其在空間中的相互關系，通過余弦相似性度量兩個節點向量在向量空間中的趨向情況，兩個節點向量之間的余弦相似性越大就認為兩向量的趨向性越強，兩節點的相似性越高.在考慮節點趨向性的同時，將節點自身屬性也加入到相似性度量中，即節點的“大小”—節點向量模長.如果兩個節點向量不僅在趨向性上相似，并且向量的模長也非常接近，那么可以肯定這兩個節點向量的相似性非常高.SMTV的相似性度量公式如公式(18)所示：

(18)

其中n1，n2表示節點，v1，v2表示對應的節點向量，表示可調參數，用于調節節點的趨向性和自身大小屬性在相似性度量中的程度.

4 實驗及結果分析

本文選取不同領域的3個真實網絡數據集進行仿真實驗，通過構建的CBOW模型對獲取的節點序列信息進行節點向量的學習與訓練，使用SMTV相似性指標完成鏈路預測，與一些經典鏈路預測方法如CN、AA、LP和使用帶有回溯和偏向的隨機游走方法Node2vec-Hadamard進行對比，驗證本文模型的可行性和所提出相似性指標的有效性.

4.1 數據集

本文選用3個真實網絡數據集進行實驗：

·蛋白質互作用網絡Yeast[19]：節點表示蛋白質，邊表示相互作用.該網絡包含2617個節點和11855條邊.屬于稠密網絡范疇.

·社交網絡數據集Facebook[20]：在Facebook數據集中，節點表示用戶，邊表示兩個用戶之間的好友關系，網絡中包含4039個節點和88234條邊.屬于稠密網絡范疇.

·電力網絡Power Grid[21]：美國西部電力網絡.節點表示變電站或換流站，連邊表示表示它們之間的高壓線.該網絡包含4941個節點和6594條邊.屬于稀疏網絡范疇.

表1 仿真實驗數據集的基本統計信息Table 1 Basic statistics of the simulated experimental data set

表1總結上述3個網絡的基本統計特征，其中n表示網絡中包含的節點數，e表示網絡連邊數，d表示網絡直徑，c表示網絡的聚類系數.

4.2 評價指標

本文使用衡量鏈路預測算法精確度最常用的指標—AUC(Area Under the Receiver Operating Characteristic Curve)[22]從整體上衡量算法的精確度.為了對比實驗的一致性，對于所有實驗數據集均采用抽樣比較的方法得到AUC的值.在抽樣比較的前提下，AUC的含義是在測試集中隨機選擇一條邊的分數值比隨機選擇一條不存在的邊的分數值高的概率.也就是說，每次從測試集中隨機地抽取一條邊，同時從不存在的邊中隨機抽取一條，如果測試集隨機邊的分數比不存在隨機邊的分數大，就加1分；如果相等就加0.5分，如果小于則不加分.獨立比較m次，有m′次加1分，有m″次加0.5分則AUC定義如公式(19)所示：

(19)

4.3 實驗結果

本文對實驗數據采用9：1的比例隨機劃分訓練集和測試集，共進行50次獨立實驗，每次實驗都計算相應的AUC值.將所有得到的AUC值求平均作為最終的實驗結果.每次獨立實驗進行10000次隨機抽樣比較預測邊與不存在的邊的相似性值計算AUC.

本文使用CN、AA、LP以及Node2vec-Hadamard 4種方法設置對比實驗.

通過對表2的實驗數據進行分析發現，基于CBOW的SMTV指標相比其他4種方法都有提升.

表2 各方法在不同數據集下的AUC值Table 2 AUC values for each method indifferent data sets

對于網絡規模相對較小，包含較少節點但連邊較多的蛋白質相互作用網PPI-Yeast來說，五種方法表現都很好，AUC值均在0.9以上，CN和AA兩個基于共同鄰居的方法表現相對一般，都略高于0.9，Node2vec也因為序列選擇的隨機性，導致AUC值較差.但是采用了二階鄰居信息的LP方法表現突出，達到了0.96以上，證明在一階鄰居的基礎上考慮二階鄰居，能夠得到更好的效果.因為在節點序列庫中包含節點二階鄰居序列，CBOW-SMTV方法取得了和LP較為接近的結果，準確度達到了0.9637，相比效果最差的Node2vec-Hadamard方法有5.3109%的提高，比效果最好的LP方法提高了0.2497%.

在網絡規模較大，節點數量和連邊情況都較多的社交網絡Facebook中，因為連邊數量眾多，每個節點都有很多的鄰居的情況下，就近鄰居的屬性淡化了網絡連通性的影響，使用CN方法直接對網絡鏈路情況進行預測只能得到0.8513的準確度，但是在共同鄰居的基礎上考慮節點度的影響，AA方法的準確度就可以有較大程度提高.二階鄰居在一定程度上增加了局部的連通性，LP方法相比AA方法也有了一定的提升，Node2vec也因為采樣率的提高，準確度提高更加明顯.CBOW-SMTV能同時考慮網絡的連通性與鄰居信息使得準確度相比于Node2vec-Hadamard得到一定的提升.

在節點數量較多，網絡連邊較少的PowerGrid網絡中，傳統的CN，AA，LP方法表現欠佳，AUC都處在0.7以下.本文提出的方法取得較好的鏈路預測準確度，甚至相比于效果最好的Node2vec-Hadamard方法有了9.5714%的提高.對于同樣使用節點向量進行鏈路預測的Node2vec-Hadamard方法，CBOW-SMTV因為使用同時結合網絡連通信息和節點鄰居信息的節點序列，在訓練模型的過程中能得到更具有表現力的節點向量，利用向量的本質特征進行相似性度量，所以實驗結果更好.

綜上，本文提出的CBOW-SMTV方法在不同規模和類型的網絡中都能表現出相對較好的預測準確性.

4.4 參數敏感性分析

本節分析CBOW-SMTV模型中的參數，包括：節點向量表示的向量維度Dimension、訓練節點序列需要考慮的節點上下文序列的大小Contextsize和相似性指標中的可調參數.其中Dimension用來刻畫節點向量映射空間的復雜程度，Contextsize用來衡量周圍節點對中心節點的影響范圍.在PPI-Yeast、Facebook、Power Grid數據集下測試各參數對于算法效果的影響，如圖4所示.

在3個數據集中本文采用控制變量法分別測試了生成節點向量維度、訓練CBOW模型的節點上下文節點數以及相似性指標SMTV中的參數α對于鏈路預測準確性AUC的影響，默認Dimension=100，Contextsize=5，α=0.4；節點向量維度的調節步長設置為20，上下文節點窗口大小步長設置為2，比例的步長設置為0.1.

圖4 CBOW-SMTV的參數敏感性分析Fig.4 Parameter sensitivity analysis of CBOW-SMTV

5 總結與展望

本文中，我們研究使用CBOW模型在網絡中進行鏈路預測的方法，提出一種使用神經概率語言模型CBOW訓練節點向量，對準確衡量節點向量的相似性，提出了SMTV相似性指標，從而進行鏈路預測的方法.此方法可以有效結合網絡的連通信息和節點的鄰居信息，更加全面地考慮節點在網絡中的地位和作用，使向量表達節點的信息更加準確.實驗結果表明，CBOW-SMTV方法對PPI-Yeast、Facebook和PowerGrid真實數據集均表現出良好的預測效果.

當然，本文提出的方法也存在一定的不足之處，雖然使用了多線程對于模型的訓練進行了優化，但是為了使CBOW-SMTV可以適用于大部分網絡和各種類型的數據集，在對數據集進行節點重新標注索引的過程中仍然耗時較大，并且在部分計算過程中出現大量占用內存的問題，一定程度上增加了程序執行時間.

后續的研究將著眼于將方法推廣到包含時序的網絡模型中，研究適用于時序網絡的基于概率語言模型的鏈路預測方法.