生成對抗式分層網絡表示學習的鏈路預測算法

高宏屹，張曦煌，王 杰

（江南大學物聯網工程學院，江蘇無錫 214122）

0 概述

隨著互聯網的高速發展，各個領域的復雜網絡［1］變得越來越龐大。在這些復雜網絡中，所有頂點代表現實系統中的實體，頂點之間的鏈接代表實體之間的聯系。復雜網絡中的鏈路預測［2］既包含對已經存在但未知的鏈接的預測，也包含對未來可能產生的鏈接的預測。

在現實世界中的鏈路預測有著廣泛的應用場景，如在復雜的社交網絡［3］中，通過鏈路預測方法可以判斷兩個人之間是否存在著一定的聯系，這樣就可以為用戶進行朋友推薦，在電子商務網絡中，也可以通過鏈路預測方法為用戶進行商品推薦。現在已知的鏈接可能只是網絡中所有頂點間存在的鏈接的較少部分，網絡中還有著大量未知的但可能存在的鏈接。如果只通過收集數據、實驗等方法了解這些鏈接，則需要耗費大量的人力物力。因此，研究鏈路預測算法具有非常重要的意義。

目前傳統的鏈路預測算法計算效率較低，且不能很好地保留網絡的高階結構特點。本文提出一種生成對抗式分層網絡表示學習算法以進行鏈路預測。該算法對網絡圖進行分層，并利用生成式對抗模型遞歸回溯地求得每一層網絡圖中頂點的低維向量表示，將其作為上一層網絡圖的初始化，直至回溯到原始網絡圖，求得原始網絡圖中所有頂點的低維向量表示進行鏈路預測。

1 相關工作

目前傳統的鏈路預測算法主要包括基于似然分析的鏈路預測算法和基于相似性的鏈路預測算法［4］。

1）基于似然分析的鏈路預測算法是根據網絡結構的產生和組織方式，以及目前已知的鏈路來計算網絡的似然值。然后將似然值最大化，計算出每一對頂點間存在邊緣的概率。

2）在基于相似性的鏈路預測算法中，如果兩個頂點之間存在鏈接，則代表這兩個頂點是相似的。因此，基于相似性的鏈路預測算法最主要的問題就是如何確定兩個頂點的相似性。基于相似性的鏈路預測分為以下兩類：

（1）基于頂點屬性相似性的鏈路預測［5］。此類鏈路預測方法大多應用在社交網絡等含有標簽的復雜網絡中。利用頂點的標簽，可以方便地計算出頂點屬性的相似性，兩個頂點的屬性越相似，這兩個頂點之間存在邊的概率就越大。

（2）基于網絡結構相似性的鏈路預測［5］。此類鏈路預測方法大多應用在難以獲取頂點屬性信息的復雜網絡中。這類方法主要分為基于局部信息的相似性指標、基于路徑的相似性指標和基于隨機游走的相似性指標。基于局部信息相似性的指標主要包括共同鄰居（Common Neighbors，CN）指標［4］、優先鏈接（Preferential Attachment，PA）指標［4］、AA（Adamic-Adar）指標［4］；基于路徑的相似性指標主要包括局部路徑（Local Path，LP）指標［4］和Katz指標［4］；基于隨機游走的相似性指標主要包括SimRank指標［6］、平均通勤時間指標［7］和Cos+指標［7］。

傳統的鏈路預測算法普遍是根據鄰接矩陣的稀疏表示而設計的，計算成本高，計算效率較低，且無法保留網絡圖的高階結構特性，因此，無法在大規模網絡上運行。

近年來，隨著網絡表示學習（Network Representation Learning，NRL）［8］的發展，基于網絡表示學習的鏈路預測算法取得了很好的效果。該算法根據網絡中頂點的鄰近性，訓練得到頂點的低維向量表示，從而計算出頂點間存在邊緣的概率，它能很好地保留網絡結構，降低計算成本，提高計算效率。

2014年，PEROZZI等人提出的Deepwalk［9］算法是利用構造節點在復雜網絡中隨機游走的路徑，生成節點序列，并利用Skip-Gram和Hierarchical Softmax［10］模型對節點序列進行處理，最終得到頂點的向量表示。2015年，TANG等人提出的LINE［11］算法是基于Deepwalk進行改進，LINE通過顯式地建模一階鄰近性和二階鄰近性來學習頂點表示，而不是利用隨機游走來捕獲網絡結構。2016年，GROVER等人提出的Node2vec［12］算法同樣是在Deepwalk的基礎上進行的改進，在隨機游走的過程中設置一個偏置參數，通過控制偏置參數的大小來控制模型的搜索方式是偏向于寬度優先搜索［13］還是深度優先搜索［14］。2018年，WANG等人提出了GraphGAN［15］算法，該算法用生成式對抗網絡學習網絡圖中頂點的低維向量表示。

上述網絡表示學習算法存在兩個共同問題：1）僅關注網絡圖的局部特性，忽視了網絡圖的高階結構特性；2）在沒有先驗知識的情況下，通常用隨機數來初始化向量表示，存在收斂到較差的局部最小值的風險。

本文算法根據原始網絡圖的一階鄰近性和二階鄰近性對原始網絡圖進行分層。每一次分層處理都將上一層子網絡圖中具有較高一階鄰近性和二階鄰近性的頂點進行合并，以形成規模更小的子網絡圖。這樣不僅保留了原始網絡圖的局部特性，并且在規模變小的過程中原始網絡圖的高階鄰近性得到了降階，使高階鄰近性更容易顯現出來，從而有效地保留了網絡圖的高階鄰近性。本文算法將規模較小的子網絡圖學習到的向量表示作為其上一層子網絡圖的初始向量表示，避免了隨機初始化導致的局部最小值的風險。

2 算法描述

2.1 算法定義描述

本文主要運用以下5種定義：

1）復雜網絡：設G=(V，E)為給定的網絡圖，其中V={ν1，ν2，…，νV}表示頂點集，每個頂點表示一個數據對象表示邊集。對于給定的一個頂點νc，設N(νc)為與頂點νc直接相連的頂點（即νc的直接鄰居）。

2）生成式對抗網絡（GAN）：生成式對抗網絡包括生成器和鑒別器兩部分，生成器和鑒別器都是一個完整的神經網絡，通過生成器和鑒別器相互博弈，可以達到根據原有數據集生成近似真實數據的新數據。

首先對生成器輸入一個真實的數據分布，生成器模仿真實的數據集，生成一個近似真實的數據，將其與真實數據集一起輸入給鑒別器。鑒別器則根據自身知識對輸入數據進行鑒別，盡量為其分配正確標簽，再與真實標簽進行對比，并根據對比結果進行自我更新，同時反饋給生成器一個反饋信息。生成器根據鑒別器傳回的反饋信息進行自我更新。以此循環，直到生成器和鑒別器達到擬合為止，最終生成器可以模擬出與真實數據幾乎一致的數據。

3）一階鄰近性［11］：網絡中的一階鄰近性表示兩個頂點之間的局部相似度，對于兩個頂點u和v，如果它們之間存在邊緣（u，v），則頂點u和v具有一階鄰近性。

4）二階鄰近性［11］：網絡中一對頂點之間的二階鄰近性是它們的鄰域網絡結構之間的相似性。如果兩個頂點u和v擁有相同的鄰居節點，則頂點u和v具有二階鄰近性。

5）高階鄰近性：網絡中一對頂點之間的高階鄰近性是全局網絡結構之間的相似性。以三階鄰近性為例，對于兩個頂點u和v，如果它們分別與兩個具有二階鄰近性的頂點相連，則頂點u和v具有三階鄰近性。

2.2 基本算法指標

本文主要應用以下3種指標：

1）AA指標：對于復雜網絡中的節點，它的鄰居的數量稱為這個節點的度。AA指標根據兩個節點共同鄰居的度信息，為兩個節點的每個共同鄰居賦予一個權重，度越小的鄰居節點權重越大。AA指標定義為：

其中，N(x)為節點x的鄰居，k(x)=|N(x)|為節點x的度。每個共同鄰居的權重等于度的對數的倒數。

2）局部路徑指標（Local Path，LP）：LP指標考慮兩個頂點間路徑長度為2和3的共同鄰居，利用頂點間路徑長度為2和3的不同路徑的數量信息來表示頂點之間的相似度。LP指標定義為：

3）Katz指標：Katz指標在LP指標的基礎上考慮兩頂點間所有路徑長度的共同鄰居，對路徑長度較小的共同鄰居賦予較大權重，定義為：

其中，β為權重衰減因子，β取值小于鄰接矩陣最大特征值的倒數。

2.3 算法框架

本文算法框架如圖1所示。

圖1 本文算法框架Fig.1 Framework of the proposed algorithm

算法主要分為3個部分：

1）網絡圖分層處理。如圖1中的①、②所示，利用網絡圖分層算法（NetLay）對原始網絡圖G0遞歸地進行邊緣折疊和頂點合并，形成多層規模逐層變小的子網絡圖G0到G（n圖1中以三層結構舉例，n=2）。

2.4 網絡圖分層

本文利用網絡圖分層算法對原始網絡圖G進行分層，生成一系列規模逐層變小的子網絡圖G0，G1，…，Gn，其中G0=G。

在網絡分層算法中包含邊緣折疊和頂點合并兩個關鍵部分。

2.4.1 邊緣折疊

邊緣折疊是一種可以有效保留頂點間一階鄰近性的算法，如圖2所示，頂點ν2與頂點ν1相連，且ν2與ν1不存在于任何一個閉環中，則說明頂點ν2與頂點ν1具有較高的一階鄰近性，算法對網絡圖中具有較高一階鄰近性的頂點進行邊緣折疊。如圖2過程a所示，將邊（ν1，ν2）折疊，把頂點ν1和頂點ν2合并成一個頂點ν1，2。利用邊緣折疊方法可以將網絡圖中具有一階鄰近性的頂點進行合并，合并后的子網絡圖很好地保留了原始網絡圖中頂點間的一階鄰近性。

圖2 網絡圖分層算法示例Fig.2 Example of network graph layering algorithm

2.4.2 頂點合并

在現實世界的網絡圖中，有大量的頂點無法通過邊緣折疊算法進行合并，但這些頂點間可能存在大量的共同鄰居，即具有較高的二階鄰近性。本文用頂點合并方法對這些具有較高二階鄰近性的頂點進行合并，不僅可以有效地縮小網絡圖的規模，還可以保留原始網絡圖中頂點間的二階鄰近性。如圖2過程b所示，在網絡圖中，頂點ν1，2與ν6，7都具有共同鄰居ν3、ν4和ν5，它們具有較高的二階鄰近性，則可以利用頂點合并方法將它們合并成一個頂點ν1，2，6，7。

2.4.3 網絡圖分層算法NetLay

網絡圖分層算法對每一層網絡圖先進行邊緣折疊，再進行頂點合并，直至生成規模小于所設定的閾值的子網絡圖（本文設定閾值為頂點數小于原始網絡圖中頂點數的1/2），網絡圖分層算法如下：

算法1網絡圖分層算法NetLay

由于邊緣折疊算法保留了原始圖的一階鄰近性，頂點合并算法保留了原始圖的二階鄰近性，因此分層后的網絡圖與原始網絡圖具有相似的結構特性，很好地保留了原始圖的局部結構，且與原始圖相比，規模減小了很多，所以更易于映射到低維向量空間。

網絡分層算法對不易顯現的高階鄰近性進行降階，有效地保留了原始網絡圖的高階結構特性。如圖3所示（以三階鄰近性為例），在左側網絡圖中，ν3和ν4具有三階鄰近性，且由圖中可以看出ν3和ν4具有較高的結構相似性。根據上述網絡分層算法，對左側網絡圖進行邊緣折疊以及頂點合并，得到右側子網絡圖。可見，由于將ν1和ν2合并為一個頂點ν1，2，因此ν3和ν4間的三階鄰近性降階為二階鄰近性，且仍保留相似的結構特性。

圖3 網絡圖分層示例Fig.3 Example of network graph layering

2.5 EmbedGAN網絡框架

對網絡進行分層后，遞歸地用生成式對抗網絡EmbedGAN處理每一層網絡圖。EmbedGAN框架由生成器G(ν|νc；θG)和鑒別器D(ν，νc；θD)兩部分組成。

對于給定的一個頂點νc，條件概率ptrue(ν|νc)表示頂點νc的真實的連通性分布。生成器G通過有偏差的隨機游走［16］方法抽取節點，并設置兩個偏置系數來控制隨機游走的方式，試圖生成盡可能相似于νc的真實的直接鄰居ν，來擬合νc的真實的連通性分布ptrue(ν|νc)。鑒別器則盡可能地區分這些頂點是與νc真實相連的頂點還是由生成器生成的頂點。生成器和鑒別器類似于在做一個關于價值函數V(G，D)的最大最小值游戲，通過交替地進行最大化和最小化價值函數V(G，D)來確定生成器和鑒別器的最佳參數，如式（4）所示。在這個競爭中，生成器和鑒別器共同進步，直到鑒別器無法區分生成器生成的分布與真正的連通性分布為止。

2.5.1 鑒別器優化

本文將鑒別器D(ν，νc；θD)定義為兩個輸入頂點的低維向量表示內積的sigmoid函數，如式（5）所示：

其中，dν和dνc是鑒別器低維向量表示矩陣中頂點ν和νc對應的低維向量表示。當輸入為由生成器生成的負樣本和真實存在的正樣本時，鑒別器根據sigmoid函數求得源節點νc和鄰居節點ν之間存在邊緣的概率，并為所有正負樣本分配標簽，再與真實標簽進行對比。根據對比結果，使用梯度下降法來更新頂點ν和νc的低維向量表示dν和dνc，使鑒別器為正負樣本分配正確標簽的概率最大化。

在隨機梯度下降的過程中，算法設置的學習速率會隨著迭代次數的增加而遞減，當梯度較大時，學習速率也相對較大，使求解更迅速。當梯度慢慢下降時，學習速率也隨之減小，使梯度下降過程更穩定，如式（6）所示：

2.5.2 生成器優化

生成器盡可能地采樣近似于真實連通性分布的負樣本，使鑒別器為正負樣本正確分配標簽的概率最小化。由于生成器的采樣是離散的，因此V(G，D)關于θG的梯度計算如式（7）所示，生成器根據鑒別器反饋的信息，利用梯度下降法更新生成器低維向量表示矩陣。

2.5.3 生成器采樣方法

生成器采用步長為l的有偏差的隨機游走方式對負樣本進行采樣。假設源節點為νc，當前節點為ν，上一跳節點為t，則需要決定下一跳節點x。定義N(ν)為頂點ν的直接鄰居的集合（即圖中所有與ν直接相連的頂點），ν與它的鄰居νi∈N(ν) 的轉移概率定義如式（8）所示：

在每一步游走時，根據式（8）計算出當前節點ν與其鄰居節點的轉移概率pν(νi|ν)。再用隨機游走的偏差系數α對轉移概率pν(νi|ν)進行加權處理，得出非標準化的轉移概率wν(νi|ν)=α(t，νi)·pν(νi|ν)，根據非標準化轉移概率，抽取隨機游走的下一跳節點。

α(t，νi)設置如式（9）所示：

參數p負責控制向前回溯的概率。如圖4所示，當參數p設置為一個較高的值(大于max(q，1))時，則使下一跳節點重新遍歷已遍歷過的頂點的概率變小。反之，當p設置為一個較低的值(小于min(q，1))時，向前回溯到頂點t的概率變大。

圖4 隨機游走中偏差系數的設置Fig.4 Setting of deviation coefficient in random walk

參數q負責控制下一跳節點是否靠近上一跳節點t。如圖4所示，當參數q＞1時，隨機游走方式類似于寬度優先搜索，傾向于訪問與上一跳節點t相連的頂點。當參數q＜1時，隨機游走方式則類似于深度優先搜索，傾向訪問遠離上一跳節點t的頂點。

通過改變參數p和q的大小，可以控制隨機游走的方式。這樣，抽取的節點就并不是一味地遠離給定的源節點νc，從而提高采樣效率。

當得到非標準化轉移概率wν(νi|ν)后，再利用Alias Method［17］選取一個節點作為下一跳節點x。當游走的步長達到設置的長度l時，當前節點ν就被抽取為負樣本頂點，生成器的采樣策略如算法2所示。

算法2生成器采樣策略

2.5.4 EmbedGAN算法

EmbedGAN算法框架如圖5所示，EmbedGAN算法模型是將輸入向量作為生成器和鑒別器的初始向量表示矩陣。每次迭代，生成器為每個源節點生成一定數量的負樣本，并抽取等量的正樣本交給鑒別器進行訓練，見圖5中的①。鑒別器根據自身低維向量表示，對正負樣本分配標簽，并與真實標簽進行對比得到誤差。再利用隨機梯度下降方法更新自身低維向量表示以最小化誤差，見圖5中的②。鑒別器將誤差信息傳遞給生成器，生成器根據鑒別器反饋的誤差信息對自身低維向量表示進行更新。生成器與鑒別器在對抗中不斷更新自身低維向量表示，直到鑒別器無法區分正負樣本為止，生成器的低維向量表示就是最終輸出的網絡圖頂點的低維向量表示，見圖5中的③。

圖5 EmbedGAN算法框架Fig.5 EmbedGAN algorithm framework

利用生成式對抗網絡EmbedGAN生成網絡圖中頂點的低維向量表示算法，如算法3所示。

算法3 EmbedGAN算法

2.6 GAHNRL算法

本文GAHNRL算法流程如下：

1）根據算法1中網絡圖分層算法對原始網絡圖G進行分層，生成一系列規模逐層減小的子網絡圖G0，G1，…，Gn，其中G0=G。

2）利用Node2vec算法對規模最小的子網絡圖Gn進行預處理，生成該層子網絡圖中頂點的初始向量表示。

3）從Gn開始，遞歸地將每層子網絡圖以及圖中頂點的初始向量表示輸入至生成式對抗網絡中進行訓練。

4）利用算法3中EmbedGAN算法學習得到Gn中頂點的低維向量表示，并將學習到的低維向量表示作為上一層子網絡圖Gn-1的初始向量表示，遞歸地進行回溯學習，直到學習至初始網絡圖G0為止，最終得到所有頂點的低維向量表示。

GAHNRL算法框架如算法4所示。

算法4GAHNRL算法

3 實驗結果與分析

3.1 實驗數據集

本文選擇了4個不同領域中具有代表性的真實網絡數據集，其中包括社交網絡Facebook［18］、Wiki-Vote［19］、合作網絡CA-GrQc［20］及細胞代謝網絡Metabolic［21］。4個數據集均忽略各邊的權重與方向，詳細信息如表1所示，其中，N表示節點數，E表示邊數。

表1 網絡數據集信息Table 1 Information of networks datasets

3.2 評價標準

本文實驗在原始網絡圖中隨機抽取10%的邊緣作為正樣本加入測試集，90%作為訓練集，在隨機生成與測試集中正樣本數量相同的邊作為負樣本加入測試集。

本文采用準確率（Precision）和AUC指標來評價本文算法鏈路預測任務上的性能，準確率和AUC指標是鏈路預測任務中最常用的兩種評價指標。

Precision是在測試集中L個預測邊被準確預測是否存在鏈接的比例。假如測試集中有L個正樣本和L個負樣本，根據算法計算每個樣本中頂點對間可能存在鏈接的概率，并按從大到小排列，若排在前L個的樣本中，有m個正樣本，則Precision定義為m/L。

AUC是在測試集中隨機抽取一個正樣本和一個負樣本，即正樣本分數高于負樣本分數的概率。在n次獨立重復的實驗中，有n1次正樣本分數高于負樣本分數，有n2次正樣本分數等于負樣本分數，則AUC的定義為：

3.3 實驗設置

在本文算法中，步長l設置為10，針對不同的參數p和q設置在4組數據集上進行實驗。在Metabolic數據集上的準確率如表2所示，在Facebook數據集上的準確率如表3所示，在Wiki-Vote數據集上的準確率如表4所示，在CA-GrQc數據集上的準確率如表5所示。由表2～表4可知，在Metabolic、Facebook、Wiki-Vote 3個數據集上，當參數p設置為1.5，參數q設置為1時，實驗效果最好（見粗體）。在CA-GrQc數據集上，當參數p設置為1，參數q設置為1時，實驗效果最好，但是當參數p設置為1.5，參數q設置為1時，實驗效果與最佳結果相差不大，所以本文對所有數據集均將參數p設置為1.5，參數q設置為1。

表2 在Metabolic數據集上不同參數設置的實驗結果Table 2 Experimental results for different parameter settings on Metabolic dataset

表3 在Facebook數據集上不同參數設置的實驗結果Table 3 Experimental results for different parameter settings on Facebook dataset

表4 在Wiki-Vote數據集上不同參數設置的實驗結果Table 4 Experimental results for different parameter settings on Wiki-Vote dataset

表5 在CA-GrQc數據集上不同參數設置的實驗結果Table 5 Experimental results for different parameter settings on CA-GrQc dataset

3.4 結果分析

為證明實驗的穩定性和準確性，本文進行了10次重復實驗，并將10次實驗結果的平均值作為最終的結果。本節介紹了3種傳統算法和4種網絡表示學習算法與本文算法在相同條件下鏈路預測準確率和AUC的對比，準確率如表6所示，AUC如表7所示（其中前兩個最優值用粗體突出顯示）。

表6 不同算法準確率對比結果Table 6 Comparison results of different algorithms accuracy

表7 不同算法AUC對比結果Table 7 Comparison results of different algorithms AUC

在表6、表7中，傳統算法包括LP、Katz和AA，網絡表示學習算法包括LINE、DeepWalk、Node2vec和GraphGAN。

從表6和表7中可以看出：

1）本文GAHNRL算法在4個數據集上的準確率和AUC值均優于4種網絡表示學習算法和傳統Katz算法。

2）與傳統LP算法相比，除Wiki-Vote數據集外，本文算法在其他3個數據集上的準確率和AUC值均優于LP算法。

3）與傳統AA算法相比，本文算法在GA-GrQc數據集和Metabolic數據集上準確率和AUC值優于AA算法，在Facebook數據集上AUC值優于AA算法。

傳統算法是采用one-hot的形式表示網絡頂點的鄰接矩陣，計算成本較大且無法保留網絡圖的高階結構特性。當訓練集中的樣本數減少時，傳統算法無法保持算法的穩定性，準確率明顯降低。而本文算法對網絡圖進行分層處理，更好地保留原始網絡圖的高階結構特性，因此在訓練集樣本很少的情況下具有較好的穩定性。本文算法與傳統算法在樣本數減少的情況下準確率變化如圖6所示。

圖6 不同數據集上準確率變化結果Fig.6 Results of accuracy changes on different datasets

實驗按照10%～90%劃分成訓練集，分別測試在不同訓練集比率下準確率的變化。通過觀察圖6可知，由于AA算法采取one-hot的形式表示網絡的鄰近關系，因此在網絡規模較小，且已知的可訓練的邊緣充足時，在Facebook數據集和Wiki-Vote數據集中，訓練集比率為40%～90%時優于GAHNRL，但是當訓練集比率為10%～30%時，網絡中可用于訓練的已知邊緣減少，AA算法的準確率明顯下降，但GAHNRL算法能保持較好的穩定性。如圖7所示，由于AA算法采用one-hot形式，占用內存較多，而GAHNRL算法采用低維向量來表示鄰接矩陣，內存占用率明顯小于AA算法。從整體來看，GAHNRL算法波動較小，性能更優。

圖7 AA算法和GAHNRL算法的內存占用率Fig.7 Memory usage of AA algorithm and GAHNPL algorithm

4 結束語

鏈路預測作為復雜網絡分析的重要研究方向，具有較強的應用前景。本文提出一種生成式對抗分層網絡表示學習的鏈路預測算法。該算法保留原始網絡圖的局部特性與高階結構特性，將生成式對抗網絡模型運用到網絡表示學習中以達到更好的效果，通過對網絡圖進行分層，將下一層子網絡圖學習獲得的向量表示作為上層網絡圖的初始向量表示進行迭代求解，解決隨機初始化可能產生的局部最小值的問題。實驗結果表明，與LP、Katz等算法相比，該算法性能更加穩定。下一步將針對異構網絡和動態網絡對算法進行優化，并加入標簽及節點屬性信息，使算法具有更廣的應用場景。