高宏屹，張曦煌，王 杰

（江南大學物聯(lián)網(wǎng)工程學院，江蘇無錫 214122）

0 概述

隨著互聯(lián)網(wǎng)的高速發(fā)展，各個領(lǐng)域的復雜網(wǎng)絡(luò)［1］變得越來越龐大。在這些復雜網(wǎng)絡(luò)中，所有頂點代表現(xiàn)實系統(tǒng)中的實體，頂點之間的鏈接代表實體之間的聯(lián)系。復雜網(wǎng)絡(luò)中的鏈路預測［2］既包含對已經(jīng)存在但未知的鏈接的預測，也包含對未來可能產(chǎn)生的鏈接的預測。

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

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

1 相關(guān)工作

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

1）基于似然分析的鏈路預測算法是根據(jù)網(wǎng)絡(luò)結(jié)構(gòu)的產(chǎn)生和組織方式，以及目前已知的鏈路來計算網(wǎng)絡(luò)的似然值。然后將似然值最大化，計算出每一對頂點間存在邊緣的概率。

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

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

（2）基于網(wǎng)絡(luò)結(jié)構(gòu)相似性的鏈路預測［5］。此類鏈路預測方法大多應(yīng)用在難以獲取頂點屬性信息的復雜網(wǎng)絡(luò)中。這類方法主要分為基于局部信息的相似性指標、基于路徑的相似性指標和基于隨機游走的相似性指標?；诰植啃畔⑾嗨菩缘闹笜酥饕ü餐従樱–ommon Neighbors，CN）指標［4］、優(yōu)先鏈接（Preferential Attachment，PA）指標［4］、AA（Adamic-Adar）指標［4］；基于路徑的相似性指標主要包括局部路徑（Local Path，LP）指標［4］和Katz指標［4］；基于隨機游走的相似性指標主要包括SimRank指標［6］、平均通勤時間指標［7］和Cos+指標［7］。

傳統(tǒng)的鏈路預測算法普遍是根據(jù)鄰接矩陣的稀疏表示而設(shè)計的，計算成本高，計算效率較低，且無法保留網(wǎng)絡(luò)圖的高階結(jié)構(gòu)特性，因此，無法在大規(guī)模網(wǎng)絡(luò)上運行。

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

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

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

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

2 算法描述

2.1 算法定義描述

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

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

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

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

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

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

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

2.2 基本算法指標

本文主要應(yīng)用以下3種指標：

1）AA指標：對于復雜網(wǎng)絡(luò)中的節(jié)點，它的鄰居的數(shù)量稱為這個節(jié)點的度。AA指標根據(jù)兩個節(jié)點共同鄰居的度信息，為兩個節(jié)點的每個共同鄰居賦予一個權(quán)重，度越小的鄰居節(jié)點權(quán)重越大。AA指標定義為：

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

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

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

其中，β為權(quán)重衰減因子，β取值小于鄰接矩陣最大特征值的倒數(shù)。

2.3 算法框架

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

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

算法主要分為3個部分：

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

2.4 網(wǎng)絡(luò)圖分層

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

在網(wǎng)絡(luò)分層算法中包含邊緣折疊和頂點合并兩個關(guān)鍵部分。

2.4.1 邊緣折疊

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

圖2 網(wǎng)絡(luò)圖分層算法示例Fig.2 Example of network graph layering algorithm

2.4.2 頂點合并

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

2.4.3 網(wǎng)絡(luò)圖分層算法NetLay

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

算法1網(wǎng)絡(luò)圖分層算法NetLay

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

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

圖3 網(wǎng)絡(luò)圖分層示例Fig.3 Example of network graph layering

2.5 EmbedGAN網(wǎng)絡(luò)框架

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

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

2.5.1 鑒別器優(yōu)化

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

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

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

2.5.2 生成器優(yōu)化

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

2.5.3 生成器采樣方法

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

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

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

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

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

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

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

當?shù)玫椒菢藴驶D(zhuǎn)移概率wν(νi|ν)后，再利用Alias Method［17］選取一個節(jié)點作為下一跳節(jié)點x。當游走的步長達到設(shè)置的長度l時，當前節(jié)點ν就被抽取為負樣本頂點，生成器的采樣策略如算法2所示。

算法2生成器采樣策略

2.5.4 EmbedGAN算法

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

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

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

算法3 EmbedGAN算法

2.6 GAHNRL算法

本文GAHNRL算法流程如下：

1）根據(jù)算法1中網(wǎng)絡(luò)圖分層算法對原始網(wǎng)絡(luò)圖G進行分層，生成一系列規(guī)模逐層減小的子網(wǎng)絡(luò)圖G0，G1，…，Gn，其中G0=G。

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

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

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

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

算法4GAHNRL算法

3 實驗結(jié)果與分析

3.1 實驗數(shù)據(jù)集

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

表1 網(wǎng)絡(luò)數(shù)據(jù)集信息Table 1 Information of networks datasets

3.2 評價標準

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

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

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

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

3.3 實驗設(shè)置

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

表2 在Metabolic數(shù)據(jù)集上不同參數(shù)設(shè)置的實驗結(jié)果Table 2 Experimental results for different parameter settings on Metabolic dataset

表3 在Facebook數(shù)據(jù)集上不同參數(shù)設(shè)置的實驗結(jié)果Table 3 Experimental results for different parameter settings on Facebook dataset

表4 在Wiki-Vote數(shù)據(jù)集上不同參數(shù)設(shè)置的實驗結(jié)果Table 4 Experimental results for different parameter settings on Wiki-Vote dataset

表5 在CA-GrQc數(shù)據(jù)集上不同參數(shù)設(shè)置的實驗結(jié)果Table 5 Experimental results for different parameter settings on CA-GrQc dataset

3.4 結(jié)果分析

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

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

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

在表6、表7中，傳統(tǒng)算法包括LP、Katz和AA，網(wǎng)絡(luò)表示學習算法包括LINE、DeepWalk、Node2vec和GraphGAN。

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

1）本文GAHNRL算法在4個數(shù)據(jù)集上的準確率和AUC值均優(yōu)于4種網(wǎng)絡(luò)表示學習算法和傳統(tǒng)Katz算法。

2）與傳統(tǒng)LP算法相比，除Wiki-Vote數(shù)據(jù)集外，本文算法在其他3個數(shù)據(jù)集上的準確率和AUC值均優(yōu)于LP算法。

3）與傳統(tǒng)AA算法相比，本文算法在GA-GrQc數(shù)據(jù)集和Metabolic數(shù)據(jù)集上準確率和AUC值優(yōu)于AA算法，在Facebook數(shù)據(jù)集上AUC值優(yōu)于AA算法。

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

圖6 不同數(shù)據(jù)集上準確率變化結(jié)果Fig.6 Results of accuracy changes on different datasets

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

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

4 結(jié)束語

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