基于生成式對抗網絡的鏈路預測方法*

丁 玥，黃 玲，王昌棟

中山大學 數據科學與計算機學院，廣州 510000

1 引言

在物理世界與人類社會關系中，存在著大量的已知或未知的個體與個體之間互相交錯的連接關系。這些連接關系具象成鏈路，形成網絡。近些年來，網絡中鏈路預測問題逐漸興起，利用鏈路預測，研究者可以分析網絡關系形成的原因[1]，甚至進行事件監測[2]。如何通過已知的鏈路關系來推導未知鏈路關系存在的可能性成為鏈路預測研究的關鍵。

在傳統鏈路預測算法中，大部分的鏈路預測方法都采取計算節點相似度的方式預測鏈路[3]。這種利用節點間的相似性進行鏈路預測的方法有一個重要前提：如果兩個節點之間相似性越大，那么它們之間存在鏈接的可能性就越大。一方面，相似性的計算可以非常簡單明了，如2007年Liben-Nowell和Kleinberg提出的共同鄰居算法[4]，僅僅利用節點的共同鄰居的個數判斷相似性；另一方面，也可以基于復雜的數學與物理內容計算相似性，諸如通過計算隨機游走的平均通訊時間[5]來計算相似度或者是利用基于圖論的矩陣森林方法[6]來計算相似度。

然而，由于事先定義了相似度的計算方式，這些鏈路預測算法都在預測之前人為假定了某種特定的鏈路形成機制。因此，如果某特定網絡的形成不遵從上述規定，則算法在該網絡上的效果將不盡人意。實驗證明，共同鄰居算法雖然在社交網絡上有很好的應用，但是在生物網絡和電路網絡上卻不能獲得較好的效果[3]。

近年，神經網絡由于其能夠自我學習的優點，為鏈路預測算法的研究提供了新的研究思路，一些新型算法，如WLNM（Weisfeiler-Lehman neural machine）[3]，通過使用神經網絡來替代啟發性算法，并取得了良好的實驗效果。以神經網絡為基礎的鏈路預測算法逐漸成為重點研究領域。

本文將嘗試拋棄啟發式模型的固有思維，不事先假定網絡的形成機制，而是利用生成式對抗網絡來自我學習與發現網絡的形成機制，從而實現基于生成式對抗網絡的鏈路預測算法，以求得一種能夠處理通用網絡的鏈路預測算法。本文的主要貢獻與創新點可概括如下：

（1）首次嘗試將生成式對抗網絡[7]運用于解決鏈路預測問題。

（2）基于CatGAN（categorical generative adversarial networks）半監督模型[8]，提出了一種適用于全監督的GAN分類模型，并將之與子圖編碼思想[2]結合，提出了基于生成式對抗網絡的鏈路預測模型WL-GAN（Weisfeiler-Lehman generative adversarial networks）。實驗證明，該算法擁有優秀的實驗效果和穩定的收斂速率。

（3）通過數學推導，給出了分類GAN模型的相關梯度公式，該推導在原CatGAN[8]論文中未被提供。

2 鏈路預測問題的定義與相關算法

2.1 鏈路預測問題的定義

本文針對于無權無向圖進行鏈路預測的研究。無權無向圖可用符號G={V,E}定義，其中V={v1,v2,…,vn}表示為頂點集合，E?V×V表示為鏈路集。在實際運用中，為了方便使用矩陣運算來實現算法，網絡圖可以使用鄰接矩陣A表示。若頂點i與頂點j之間存在鏈路，則Ai,j=1；若不存在鏈路鏈接，則Ai,j=0。由于在無權無向圖中，鏈路不具有方向性，從而Ai,j與Aj,i代表相同的鏈路，A為對稱矩陣。因此，在實際運用中，為了節省空間，無權無向圖的鄰接矩陣常被其上三角矩陣所替代。在本文算法中，這種替換也被使用。而鏈路預測所要解決的問題就是，對一個不完整網絡G，判斷兩個獨立節點x,y∈V，是否存在(x,y)∈E。

2.2 鏈路預測算法

2.2.1 基于相似度的鏈路預測算法

對于網絡中未知連接關系的兩個節點x和y，基于相似度的鏈路算法會根據某規則對兩點之間存在鏈路的可能性“打分”，定義為score(x,y)。幾種經典的基于相似度的算法（共同鄰居算法（common neighbors，CN）、優先連接算法（preference attachment，PA）、Katz指數算法）的打分規則如表1所示。

Table 1 Score rules of CN,PA,Katz表1 CN、PA、Katz算法的打分規則

其中，Γ(x)、Γ(y)分別代表了節點x與節點y的鄰居集合；path(x,y)=l是節點x到節點y之間所有長度為l的路徑的集合；β是一個阻尼系數，0＜β＜1。

2.2.2 基于神經網絡的鏈路預測算法WLNM

WLNM算法[3]是一個以分類器學習為核心的鏈路預測算法，也是本課題提出的WL-GAN算法的重要參考算法之一。該算法可拆分為三個子模塊：一個提取子圖算法（算法1），一個子圖編碼模型（算法2），一個分類器模型。WLNM算法首先將網絡中的每條已知鏈路信息轉化為相應的子圖和標簽，再利用神經網絡進行分類訓練，以完成鏈路預測。其中，Palette-WL模型是一種為無標號圖進行標記序號的算法，它不僅能夠根據節點在網絡中的結構角色來標記序號，而且能夠保留各節點與目標鏈接的相對距離的信息[3]，非常適合用于鏈路預測。

2.3 生成式對抗網絡

2.3.1 原始生成式對抗網絡算法

生成式對抗網絡[7]包括一個判別器模型與一個生成器模型。其中，判別器致力于識別輸入數據的來源：來自真實數據還是生成器生成的虛擬數據，并提高自身識別數據真偽的正確性；而生成器D則致力于使自己生成的虛擬數據被判別器判別為真。這種生成器與判別器相互博弈、共同進化的構成使得D和G的性能在迭代中不斷提升，直到雙方達到納什均衡狀態。

GAN的生成器和判別器可以用任意可微分的函數G、D來表示[11]。其中，生成器G的輸入為隨機噪聲變量z～P(z)，從而生成出模仿服從真實分布X的虛擬數據G(z)，使用符號x?=G(z)表示。而這里判別器的D的輸入則可以是真實數據x～X，也可以是虛擬數據。

GAN的損失函數如下[7]：

2.3.2 分類生成式對抗網絡算法CatGAN

分類生成式對抗網絡CatGAN[8]是以GAN為基礎的半監督分類模型算法，其中判別器的目的不再是判斷數據真假，而是為數據進行分類。其具體原理是利用香農熵與交叉熵[12]的性質使得判別器盡量滿足以下要求：（1）真實數據能夠被判別器以高度確定的概率劃分到某一類中。（2）若真實數據標簽已知，則盡量分入該類中。（3）由生成器產生的虛擬數據分到所有K類中的概率相似，無法被判別器分類。（4）判別器盡量使所有數據能在所有類別中均勻分布存在；而生成器則需做到（1）產生的虛擬數據能夠被判別器以高度確定的概率劃分到某一類中。（5）所有生成的虛擬數據能夠在所有類別中均勻分布。CatGAN半監督模型中生成器與判別器的損失函數公式分別如下[8]：

其中，H(x)為香農熵函數，CE(x)為交叉熵函數。對于一部分已知其對應的分類類別y的真實數據x，定義(x,y)服從分布XL。式（3）、式（4）中各項的具體表達如下：

其中，N、M分別為真實樣本與虛擬樣本的數量，K為聚類數。

3 解決鏈路預測問題的WL-GAN模型

3.1 WL-GAN模型架構

本節將詳細介紹WL-GAN模型。WL-GAN是一個結合編碼子圖算法與分類生成式對抗網絡的新型鏈路預測模型。利用子圖編碼算法與分類生成式對抗網絡，WL-GAN能夠從網絡的拓撲結構自動學習出網絡的形成規律，從而利用有監督學習對不同的編碼子圖進行分類，達到鏈路預測的效果。WLGAN包括以下四個主要步驟：

（1）使用封閉子圖提取算法[3]（算法1），對于網絡中的所有節點對，生成以該目標節點對為中心的鄰居子圖，固定子圖大小為K。

（2）使用子圖模式編碼算法Palette-WL（算法2）為所有子圖的各節點標序，并由其合成鄰接矩陣。將鄰接矩陣中表明目標節點對的連接關系的數據從鄰接矩陣中剔除，作為該子圖的標簽。所得新的鄰接矩陣及其標簽則為用于訓練GAN判別器的真實數據。

（3）將噪聲信息放入CatGAN生成式對抗網絡的生成模型中，生成虛擬數據。

（4）使用虛擬數據與真實數據訓練分類生成式對抗網絡CatGAN[8]的全監督模型。訓練模型使得CatGAN判別器模型和生成器模型達到納什均衡，最終獲得強勁的能夠實現鏈路預測功能的判別器模型。

WL-GAN框架架構整體結合了WLNM模型[3]與CatGAN模型[8]的全監督拓展模型，在實驗中發現WL-GAN具有良好的實驗效果與極高的收斂速率。WL-GAN框架的示意圖如圖1所示。

算法1提取子圖算法[3]

輸入：目標節點對(x,y)，網絡G和子圖節點數K。

輸出：以(x,y)為中心節點對的子圖G(V,K)。

Fig.1 Framework sketch of WL-GAN圖1 WL-GAN的框架示意圖

算法2The Palette-WL算法[3]

輸入：以(x,y)為目標鏈路的封閉子圖G(Vk)。

輸出：對所有v∈V，最終標號結果c(v)。

3.2 構造全監督GAN模型

以2.3.2小節中CatGAN的半監督模型原理以及損失函數為原型，本文提出CatGAN的全監督模型公式。當擁有所有訓練數據的類標時，可以簡化網絡中判別器的損失函數，只保留判別器對真實數據判別結果與真實類標的交叉熵信息而省略其信息熵信息項，此時判別器和生成器的損失函數如下：

Fig.2 Diagram of neural network圖2 神經網絡的示意圖

隨后，使用深度神經網絡模型來構造判別器D。神經網絡模型可使用圖2表示。多層神經網絡中，每一層網絡的輸出都會成為下一層網絡的輸入[13]，即：

其中，L為網絡的層數。fl為第l層的激活函數，zl=Wlal+bl。網絡工作時，第一層神經元從外部接受輸入的數據集矩陣x，x的每一列即為一個輸入樣本，即a0=x。最后一層神經元的輸出是整個網絡的輸出aL。對于神經網絡判別器D的某個任意層數l而言，第l層的輸出為：

其中，N為輸入的樣本個數，Nl為第l層的神經元個數。在神經網絡對輸入進行向前傳播最后得到輸出aL之后，將網絡輸出與目標輸出相比較，并使用反向傳播算法[13]結合判別器的損失函數LG調整網絡參數使得損失函數最小化。其中，損失函數的最速下降算法[14]為：

這里l是層數，表示矩陣Wl中第i行的第j個元素，表示bl的第i行元素，k為迭代次數，η是學習率。

現在，具體考慮解決鏈路預測問題的全監督GAN模型算法反向傳播過程中各梯度的計算。根據式（10）、式（11）與式（18），判別器的誤差公式如下：

誤差公式1（判別器D的誤差公式） 對于上述CatGAN網絡，判別器第L-1層第t個樣本的誤差為：

為了簡化誤差公式1的證明，先證明如下引理。

引理對于任意信息熵,其中，有：

證明

考慮到：

且：

從而可得：

證明（誤差公式1）

對于判別器而言，結合其損失函數表達式LD以及上述引理（K=2），有：

同理，對于生成器G，也可以利用反向傳播算法更新其網絡參數，只不過此時需要將生成器G和判別器D看成相互連接的統一網絡。生成器G的誤差公式如下（誤差公式2的證明過程與誤差公式1相似）。

誤差公式2（生成器G的誤差公式） 對于上述CatGAN網絡，當生成器輸出生成數據至判別器網絡時，判別器第L-1層第t個樣本的誤差為：

在WLNM中，判別器與生成器網絡模型均為5層神經網絡，其中判別器每層神經元的個數分別是[N,32,32,32,2],而生成器的神經元層個數則為[16,32,32,32,N]，其中N為輸入樣本向量的大小。而判別器與生成器神經網絡模型中，除判別器最后一層的激活函數為softmax函數，其余層激活函數均為sigmoid函數。

4 實驗設計與結果分析

4.1 模型評價指標與實驗數據集

4.1.1 模型評價指標

本文采用AUC作為模型的評價指標，AUC（area under curve）是二元分類模型中的常見評價指標。相較于原始的accuracy評價指標，AUC避免了將預測概率轉化為類別的過程，因此AUC是二元分類器中最常見的評價指標之一。AUC的公式可概括如下[15]：

其中，Np為正樣本個數，Nn為負樣本個數。ranki代表正樣本i在被模型判別為正的概率在所有正樣本中的排名。AUC得到的結果可等價看作所有樣本中模型估測正類樣本判別為正的概率大于估測負類樣本判別為正的概率的次數再除以Np×Nn。

4.1.2 數據集

在本實驗中，共采用了四個數據集：USAir[3]數據集是美國航空系統的航線網絡數據；NS[16]數據集是一個發表于《科學網絡》雜志上的作者合作關系網絡；Celegans[17]數據集是秀麗隱桿線蟲的神經網絡數據；Power[17]數據集是美國西部地域的電網網絡數據。這四個網絡涵蓋生物、物理、人際關系等多個領域，能夠很好地測試算法在不同性質的網絡上各自的性能。所有數據集的具體信息如表2所示。

Table 2 Node information of datasets表2 數據集的節點信息表

4.2 參數分析實驗

本節將探討WL-GAN模型迭代次數epoch、目標函數交叉熵項權重參數λ和學習速率η對WL-GAN算法的實驗效果的影響。

4.2.1 對參數λ的分析

參數λ是判別器的目標函數LD中交叉熵項的權重值。圖3、圖4分別代表了在兩種不同數據集USAir和Celegans下，不同λ的取值對WL-GAN模型結果的影響，此時，學習速率η固定為0.5。從圖3、圖4中可以看出，若λ取值為0，即去除交叉熵項，則模型無法收斂，效果極差。但若λ＞0，則WLGAN均能夠取得較好的實驗效果。另外，λ取值越大，則模型收斂速度越快，但是收斂后的最終效果相似。

Fig.3 Performance of WL-GAN via different λon USAir dataset圖3 USAir數據集上不同λ的WL-GAN性能

Fig.4 Performance of WL-GAN via different λon Celegans dataset圖4 Celegans數據集上不同λ下的WL-GAN性能

4.2.2 對參數η的分析

參數η是神經網絡梯度下降時的學習速率。圖5、圖6分別代表了在兩種不同數據集USAir和Celegans下，不同η的取值對WL-GAN模型結果的影響，此時，λ固定為0.5。從圖5、圖6中可以看出，η取值越大，則模型收斂速度越快，但模型穩定性越差，AUC曲線曲折較多。當η=0.1時，雖然模型收斂速度較慢，但是曲線平滑。這是由于η取值越大則梯度下降越快，但不一定完全朝梯度下降方向下降，η取值越小則梯度下降越慢，但是能保證盡量朝向梯度下降方向移動的原因導致的。

Fig.5 Performance of WL-GAN via different ηon USAir dataset圖5 USAir數據集上不同η下的WL-GAN性能

4.3 對比實驗分析

本節將WL-GAN的實驗效果與一些現有算法的實驗效果進行對比。共選取了3個啟發性算法與3個基于分類器的算法作為WL-GAN的對比算法，分別如下：

Table 3 Comparison performance of WL-GAN表3 WL-GAN對比效果

Fig.6 Performance of WL-GAN via different ηon Celegans dataset圖6 Celegans數據集上不同η下的WL-GAN性能

CN[4]：共同鄰居算法。

PA[9]：優先連接算法。

Katz[10]：Katz指數算法。其中參數β=0.01。

WL-KNN：WL-KNN是子圖編碼模型與KNN（Knearest neighbors）分類模型的結合模型。其中，KNN模型使用余弦距離作為距離度量，分類規則為隨機分類。

WL-LR：WL-LR是子圖編碼模型與邏輯回歸（logistic regression）分類模型的結合模型。

WLNM[3]：WLNM是子圖編碼模型與神經網絡分類模型的結合模型。神經網絡層數構造為Nl=[N,32,32,16,2]，N為樣本的向量長度，與本文算法WL-GAN中的判別器的神經網絡構成相同。其中，學習速率η=0.1，最大迭代次數200次。

對比結果如表3所示。從表3中可以看出，WLNM與WL-GAN算法的效果明顯優于其他算法，而本文提出的WL-GAN算法的實驗效果較之WLNM又有了進一步提升。這是由于WL-GAN算法能夠利用自身生成的虛擬數據來輔助判別器進行模型的訓練，進而提升了實驗效果。

5 結束語

本文嘗試使用生成式對抗網絡解決鏈路預測問題，并創新性地提出了基于生成式對抗網絡的鏈路預測模型WL-GAN，并在實驗中證明了WL-GAN算法在性能上的優越性。生成式對抗網絡在計算機視覺上已經較為成熟，但是將生成式對抗網絡用于分類或其他用途的研究遠沒有計算機視覺領域成熟，如何更多地嘗試將生成式對抗網絡融入到更多的研究領域是一個值得研究的問題。