基于節點映射與標簽數據構建的鏈接預測方法

周 婭，楊 邦

(桂林電子科技大學 計算機與信息安全學院，廣西 桂林 541004)

0 引 言

網絡鏈接預測主要是研究如何使用已知的網絡信息對未知和缺失鏈接進行預測[1]。社會網絡在近些年互聯網的發展過程中也得到了巨大的發展，并已經成為各種信息傳播和關系承載的重要媒介。憑借著這些規模日趨龐大的社會網絡，人們構建更加廣闊的鏈接關系成為可能，隨之而來的是社會網絡的日趨復雜和龐大。另一方面，當我們對復雜系統中的關系構建網絡結構來近似模擬研究時，數據缺失或者鏈接信息不足等問題時有發生，而且對于關系網絡，其中的關系鏈接往往又是動態變化的，具體說來就是，網絡中某些暫時不存在的關系鏈接可能會出現[2]。因此，從網絡拓撲結構中預測和發掘隱藏的鏈接就顯得很有意義了。鏈接預測在很多研究和應用領域中都有重要應用，比如說生物網絡中的疾病-基因網絡、蛋白質-蛋白質相互作用網絡[3]，除了生物網絡領域之外，在學術網絡中用以推斷論文的合作關系網絡，在電子商務中用于對客戶的商品推薦，在移動網絡中預測移動網絡用戶是否有切換運營商的傾向。在犯罪監控網絡中，可以利用鏈接預測方法來發現犯罪分子間隱藏的聯系[4]。

對于網絡鏈接預測問題，從使用方法的層面來說，主要有基于相似性計算的方法、基于統計學似然估計的方法以及基于概率模型的方法等。基于節點相似性計算的方法是通過對網絡節點的某些維度的相似性進行計算，如果兩個節點的相似度計算結果越大，那么它們之間鏈接存在的概率就越大。基于此種假設前提，發展出了不同的相似性計算指標。

基于統計學似然估計的方法一般是將網絡的結構看作是具有某些層次結構或者是隨機分塊模型結構。所以此類方法主要分為兩類：基于層次結構模型和基于隨機分塊模型。分層次模型在呈現層次結構的網絡中能有較好的效果，但是這類方法每次計算都需要生成若干臨時網絡樣本，這個過程會使模型復雜度大大增加，對于大規模的網絡，這類方法的綜合性能就不是很好了。而基于隨機分塊模型的鏈路預測方法能夠較好的彌補這方面的缺點，其不僅可以預測缺失的鏈接，而且能夠預測某些異常鏈接。例如在生物作用網絡中糾正蛋白質相互作用關系之間的錯誤鏈接[4]。

基于概率模型的方法主要步驟是在特有的網絡中構建一個帶有多個待調優變參的數學模型，然后通過對原網絡上節點之間的連接關系以及連接上的權重關系的表示方法進行轉換并作采樣處理，將節點上的網絡信息轉換成與節點為中心的特征值表示的形式，最后是不斷迭代進行參數調整和模型優化，最終得到誤差值允許范圍內的最優參數解。網絡中未知鏈接關系的存在性就可以通過計算節點對在當前最優參數模型中的條件概率[4]得到。

近年來，機器學習與深度學習技術也得到了迅猛的發展，也得到了廣泛的應用，其中深度學習已經在包括計算機視覺、自然語言處理等領域取得了較大的成果[5]。在自然語言處理領域，基于神經網絡方法的語義空間模型和文本分布式表達等模型得到了較為充分的研究。詞語特征的分布式表達主要思想是將詞語的語法或者語義特征映射到一個固定維度的連續向量空間，以此解決原有方法中存在的詞語矩陣所包含的稀疏性問題以及計算的維數災難[1]。

本文提出了基于節點特征構建的鏈接分類預測框架(classification method for link prediction based on node vector building，Net2Vec-CLP)，下文記作Net2Vec-CLP。框架分為兩個子部分，即Net2Vec部分和CLP部分。在Net2Vec子部分使用node2vec方法獲得網絡在低維度下關于節點的向量表達，在使用隨機游走方法獲得節點周圍環境節點序列時，對于普通隨機游走策略未考慮節點游走概率的情況，采用改進的具有重啟機制的隨機游走方式生成節點環境向量集合，在對node2vec超參的更新過程中，創新性地使用改進的牛頓下降法達到更快的收斂速度。此過程將輸出節點向量。對于傳統的直接對節點向量對計算相似度來評估鏈接存在性的方法做出改變，本文對獲得的節點向量，根據原網絡中存在鏈接邊的節點對以及無鏈接的節點對構造帶標簽的組合向量元數據，全部的有鏈接節點對、無鏈接節點對構成新的帶標簽數據集，針對此新數據集設計使用采用了Sigmoid核函數的SVM的分類算法得到針對原網絡的預測結果。

1 相關工作

在基于節點相似性的方法中，主要有基于局部信息相似性指標的共同鄰居(CN)指標，Salton指標，Jaccard指標[1]，TAES(time-aware actor-level evolution similarity)指標[6]，LDAcosin指標[7]，TBS(topology-based similarity)指標[8]，Scop指標[9]，LP-SSN指標[10],基于路徑相似性的節點路徑聯合指標[11]方法(PNC)等。在基于節點相似性的方法集合中，還有一些使用隨機游走理論的方法，比如SimRank指標，平均通勤時間(average commute time)指標[1]等。

在對有節點內容屬性的網絡鏈接預測方法中，張昱等[12]提出了一種方法，該方法為網絡中不同類型的連邊分配邊權重，最后通過隨機游走的方法進行網絡鏈接的預測。

機器學習與深度學習思想的方法在網絡鏈接預測問題中的應用，最早是Grover A等[13]提出Node2Vec算法，首先將所有節點初始化成指定特征數的向量化表示，通過對網絡節點進行基于邊連通的游走，生成節點環境節點集合，通過BP神經網絡參數回退更新策略，通過參數學習和更新過程，同步完成節點向量表示的更新，直到游走序列結束和參數收斂，得到保留了網絡性質的節點向量化表示。然后節點之間連邊存在的概率值可以通過兩節點之間的相似度來評估。

同時，基于網絡表示學習的方法也被一些研究者運用到了鏈接預測工作中來，網絡表示學習方法將原網絡中的信息轉換成以節點實體為中心的低維向量表示，以這種方式盡可能完整保留原網絡的拓撲信息和屬性信息。在獲得網絡的低維向量表示之后，使用機器學習以及統計分析的方法對向量數據集進行分析和預測[14,15]。

在數據分類方法的研究領域，SVM模型有了很多的應用，也達到了較好的效果。汪生等[16]提出了基于模糊SVM模型的入侵檢測分類方法，能夠較好地適用于入侵檢測問題中的訓練樣本少的問題，提高了分類準確率。曲蘊慧等[17]提出了將SVM模型運用于工業中紙病檢測分類的方法，有效解決了以前的方法中存在的實時性差、難以適應生產線在線檢測要求等問題。SVM模型方法在數據分類，特別是二分類數據集上，有著運用范圍廣，準確率較高，可擴展性強，適用領域廣泛等優勢。

2 問題與符號定義

2.1 基礎符號定義

本節會給出所涉及到的基本問題的定義(見表1)，主要是模型涉及到的一些概念以及對應的簡稱表示。

表1 基礎符號定義

2.2 節點N的周邊環境節點Env(N)

與鄰居節點不同的是，Env(N)不僅僅包含N的鄰居節點，還有可能包含非直接相連的節點。另外，周邊環境節點是通過隨機游走產生的，所以在每一次的運算過程中，甚至是同一次運算的不同游走序列中，其結果都是動態變化的。

2.3 Windows(N)

環境窗口Windows(N)用于表示每一個待預測的節點的周邊節點的個數。對于當前節點N，其Windows(N)數值大小就是Env(N)中節點數目。

2.4 節點結構特征表達嵌入矩陣M

節點結構特征表達嵌入矩陣M是由節點特征向量構成的矩陣，在Node2Vec框架體系中[14]，一個重要概念就是節點結構特征向量，即網絡的向量化，對于原網絡，Node2Vec過程之后，轉變成 |V|×m型矩陣數據，即我們此節所表述的M，而M中的行數據即為每個節點的特征向量表示。對于矩陣M的更新，會在算法開始之前的初始階段進行隨機初始化賦值，在映射層階段對節點特征向量進行迭代更新，當訓練數據運算完畢時，M矩陣中所有節點向量更新完畢。

2.5 節點Huffman樹

在Net2Vec-CLP算法中，節點Huffman樹是為了提升節點查找效率，降低算法的復雜度而做出的一個設計，其是按照節點度的大小為關鍵信息指標，構建Huffman樹。此樹基于這樣一種假設：度較大的節點在游走數據集中更大概率出現，所以會涉及到更多次數的節點信息訪問，正好可以結合Huffman樹的特點進行網絡節點重構存儲。且此Huffman樹的分支可以看作一個個分類器。原網絡結構中的所有節點保存在Huffman樹的葉子節點，所以此Huffman樹存在 |V| 個葉子結點。在每次對網絡節點的查找過程中，會經過若干個非葉子節點，每一個非葉節點都存在待學習更新的m維參數向量。

3 基于節點特征構建的鏈接分類預測模型(Net2Vec-CLP)

3.1 模型流程概述

如圖1所示，Net2Vec-CLP框架主要分為映射層和學習層。本章后續內容會對整個流程作更詳細的介紹。

圖1 Net2Vec-CLP架構流程

3.2 映射層

3.2.1 映射層模型構造

此階段主要是對網絡進行節點向量化轉換。首先是使用隨機游走的方式對網絡進行多輪采樣，多輪隨機采樣之后獲得網絡關于節點集的序列化表示。此過程中需要仔細考慮的是對節點游走的策略合理性，較好的游走策略會對原網絡信息有較好的覆蓋性，能夠較充分表達原網絡的拓撲信息和屬性信息。本文使用帶重啟機制的隨機游走方法來實現序列化過程。重啟機制應用于度為1的網絡節點，在這種情況下，當前節點游走完畢后下一游走起始節點是從已有的序列中隨機選擇一個節點(非當前節點)作為重啟后的新的游走起始節點，如圖2所示。

圖2 網絡游走序列化示例

圖2中MAX_LENGTH表示每個游走序列的最大長度，WALK_TIMES表示整個游走過程所需要的游走總次數。Windows(N) 根據經驗值取為8，得到節點的Env(N)。則整個網絡的游走過程的輸出訓練集為式(1)

Training set={(N,Env(N))},N∈V

(1)

然后，在游走產生節點N的周邊環境節點之后，參數優化的最終目標函數為式(2)

(2)

式(2)表示模型的最終目標是通過對游走得到的Env訓練集進行參數更新迭代運算，使得模型在某套參數解的條件下出現當前訓練集的概率p取到最大。

圖3表示了對節點的周邊環境節點取樣策略的示例。我們以節點A為例，示例中節點A的向量序列表示由 {H,D,B,H,G} 5個節點聚合運算結果來表示，本文采用線性求和聚合策略，此聚合操作輸出Env(VA)。在對每個節點向量的處理過程中，借助構造的節點Huffman樹進行快速查詢。從根節點到每一個葉子節點會經歷若干個分類節點。每一個分類節點相當于一個二分類器角色。分類節點上的決策激活函數采用Sigmoid函數。

圖3 節點向量映射

我們使用VEnv(N)表示葉子節點N關于周圍環境節點的向量表示，式(3)表示在節點Huffman樹查找的過程中，此葉子節點被按照正常路徑正確分類的聯合概率

(3)

其中

(4)

所以需要優化的最終目標函數式(2)即為

(5)

3.2.2 模型參數更新過程

(6)

為了方便閱讀，記Φ(N,i) 為式(7)

(7)

(8)

(9)

(10)

(11)

3.3 學習層

3.3.1 標簽化數據集構建

映射層進行迭代更新，最終輸出網絡節點構特征矩陣M，已有的方案是直接對此節點向量矩陣進行相似度計算，并根據相似度值高低給出鏈接存在性預測結果。但是由于很多網絡中節點相關信息比較少，可能簡單到只有稀疏的度信息，簡單進行相似度計算的方式難免會存在數據稀疏，數據分布不均，算法穩定性較差的問題。文獻[1]采用余弦相似性指標計算節點間的相似程度。從原網絡中的邊集中選擇部分邊集，對每一條邊的兩個端點計算相似度，并與網絡中隨機的兩沒有鏈接關系的節點對之間的相似度進行比較，如果鏈接預測準確，則前者值大于后者。文獻[16]是根據DeepWalk算法得到向量矩陣Φ，然后根據節點之間的轉移概率矩陣計算得到節點的相似度矩陣。

本文對節點特征向量進一步進行處理，通過對節點特征向量進行標簽化訓練數據集構建，將兩個節點向量對構成的新向量分為兩個明確類別：鏈接存在和鏈接不存在。并在此基礎上訓練二分類模型，從而在劃分的測試集上對鏈接存在與否進行計算驗證。具體的構建策略如下：其中式(12),式(13)分別為節點a,b的特征向量。Eab表示a,b構成的邊。

Va=(a1,a2,…,am)

(12)

Vb=(b1,b2,…,bm)

(13)

通過向量聚合方式，a,b構成的邊向量表示為式(14)

(14)

其中，邊向量的標簽劃分參考式(15)

(15)

選擇數量為0.3*|E| 的無鏈接節點對作為分類標簽為-1的數據。加上鏈接存在的數據，數據集總共有 (1+0.3)|E|條。

3.3.2 SVM二分類器設計

圖4 SVM超平面與決策邊界

除此之外，對于線性不可分的數據集，SVM方法引入核函數的概念，其具體操作是將原數據映射到更高維度以使得轉換后的數據在新的維度能夠線性可分。這個過程中的數據映射方法即前文提到的核函數概念，基于此，svm二分類優化問題可以表示為式(16)

(16)

式(16)所對應的拉格朗日對偶問題可表示為式(17)

(17)

(18)

3.4 算法小結

Net2Vec-CLP框架主要流程主要分為3個子部分：第一部分是Net2Vec子過程，完成網絡節點的向量化過程，輸出網絡節點特征向量表示矩陣；第二部分是標簽化數據集構建；第三部分是對第二部分輸出的標簽化數據集，采用Sigmoid核作為映射函數的SVM模型訓練過程。

4 實驗與結果分析

4.1 實驗數據集介紹

本文實驗使用了4個公開的社會關系數據集,以下是相關數據集的簡要介紹。

(1)Facebook社交網絡，其中包含4039個節點和 88 234 條邊。

(2)Email-Enron 電子郵件通信網絡，其中包含36 692個節點和183 831條邊。

(3)CA-HepTh科學家合作網絡，其中包含9877個節點和51 971條邊。

(4)Epinions 用戶信任關系數據網絡，其中包括 49 290 個頂點和487 182條邊。這4個數據集的網絡拓撲結構如表2所示。其中N表示節點數，E表示邊數，表示平均度，表示平均聚集系數。

表2 各數據集拓撲結構特征

4.2 基準方法

(1)CN指標：如果NBx與NBy分別表示節點x與y的鄰居節點，則基于CN指標的相似性可表示為Sx,y=|NBx∩NBy|。

(2)Node2Vec：主要還是網絡結構向量化映射的思想，不過在隨機游走序列生成過程時增加p，q兩個超參來平衡隨機游走的深度和廣度。此方法在獲得網絡節點的向量化表示之后，借助余弦相似度指標來衡量節點之間相似度，并以此為判斷鏈接存在性的根據。

(3)ACT指標：平均通勤時間相似度指標(average commute time，ACT)是基于這樣一個理論假設：假設有一個隨機粒子從節點x到達節點y平均要走的步數為m(x,y)， 在此基礎上，節點x與節點y的平均通勤時間定義為式(19)

n(x,y)=m(x,y)+m(y,x)

(19)

(20)

4.3 評價指標

算法的結果評估采用AUC(area under curve)和平均準確率(average precision，AP)兩個常用指標。AP指標能夠很好展現Precision-Recall曲線下面積，能較好反映算法整體性能。AUC方法能較好評估方法的準確程度，鏈接預測問題中的準確率定義為在網絡中存在鏈接的節點對鏈接存在可能性高于不存在鏈接節點對的概率。假設進行了n次評估實驗，其中有n′次結果存在鏈接節點對得分較高，其中n″次的結果中兩類節點對得分相同。則AUC結果的計算公式如式(21)

(21)

4.4 實驗結果

第一部分實驗是AUC指標下的結果評估，此過程中還考察了數據集分類比例對算法以及基準方法的結果的影響，實驗數據集總共進行了4種不同比例測試數據集的劃分方案，分為10%，20%，30%，40%，每種方案運行50次，最終取值取多次結果的平均值。如圖5的幾組柱狀圖中可以觀察到：本文提出的方法在測試集的比例為20%和30%時表現較優異，其中最突出的是在Facebook數據集和Email-Enron數據集上。在Epinions數據集上受測試數據集劃分比例影響最小，只在測試數據為20%和30%比例的情況下與排名其后的Node2Vec方法有微小優勢。同時還能夠發現，當測試數據比例選取到40%時， Net2Vec-CLP方法甚至會低于其它基準方法。所以，Net2Vec-CLP方法的優勢還應該受測試數據集劃分比例這一參數的影響，當測試數據集劃分比例為一個比較合理的數值時，能體現出結果優勢。

圖5 不同數據集上AUC結果數據比較

同時，在分類方法角度考慮本文提出的Net2Vec-CLP方法，二分類的方法能夠雙向又全面的對能對數據集中有鏈接節點對、無鏈接節點對進行分類預測，相對于相似度計算的方式，其能從反向將無鏈接節點對與任選存在的鏈接進行比較計算，因為按照網絡模型規律，所有存在鏈接節點之間的相似度都要盡量大于無鏈接節點對之間相似度，模型才會比較準確。

第二大部分實驗是基于AP指標的結果評估，這個階段我們的測試數據集選取為30%。具體結果見表3。

表3 AP結果記錄

Net2Vec-CLP在所有測試數據集上都有較好表現，其中表現最明顯的是在Facebook數據集上，測試結果高出了Node2Vec方法3.35個百分點。但是在Epinions數據集上的結果低于Node2Vec方法。這種情況可能是因為Epinions數據集的節點的網絡聚集程度較低，從而在隨機序列生成過程中要依賴更多的重啟機制獲取新的游走起點，最終向量構造的過程中體現出的便是這些隨機重啟的信息，而并非原網絡的網絡信息，從而在分類訓練階段中的超參會出現過擬合的問題。對于這類問題，可以在進一步的后續研究中做專門的改進和研究。

5 結束語

本文在網絡節點序列化表示思想的基礎之上，提出Net2Vec-CLP方法，在向量化過程中采用增強的牛頓下降法更新參數，提升了參數的收斂速度，同時通過輔助函數f1(X)=ep(X-Xn)f(X) 解決在更新過程中梯度為0的問題。映射過程將輸出網絡節點的向量表示，然后將網絡鏈接構造成標簽化的分類訓練數據集，運用以Sigmoid為核的SVM算法對標簽數據集進行分類。在幾個數據集上運行測試的結果表明，框架在幾個數據集上，AUC指標和AP指標都能達到很好的效果。較以前對節點計算相似度的方法，此框架能夠對原網絡中無鏈接節點對有均衡，準確的度量。

下一步工作將會在本文工作的基礎上擴展對有向社會網絡數據預測問題的支持，針對有向網絡中鏈接的有方向性特點，從節點游走策略，標簽化數據集構建規則等方面為出發點來開展下一步研究工作。