丁 玥，黃 玲，王昌棟

中山大學(xué) 數(shù)據(jù)科學(xué)與計算機學(xué)院，廣州 510000

1 引言

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

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

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

近年，神經(jīng)網(wǎng)絡(luò)由于其能夠自我學(xué)習(xí)的優(yōu)點，為鏈路預(yù)測算法的研究提供了新的研究思路，一些新型算法，如WLNM（Weisfeiler-Lehman neural machine）[3]，通過使用神經(jīng)網(wǎng)絡(luò)來替代啟發(fā)性算法，并取得了良好的實驗效果。以神經(jīng)網(wǎng)絡(luò)為基礎(chǔ)的鏈路預(yù)測算法逐漸成為重點研究領(lǐng)域。

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

（1）首次嘗試將生成式對抗網(wǎng)絡(luò)[7]運用于解決鏈路預(yù)測問題。

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

（3）通過數(shù)學(xué)推導(dǎo)，給出了分類GAN模型的相關(guān)梯度公式，該推導(dǎo)在原CatGAN[8]論文中未被提供。

2 鏈路預(yù)測問題的定義與相關(guān)算法

2.1 鏈路預(yù)測問題的定義

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

2.2 鏈路預(yù)測算法

2.2.1 基于相似度的鏈路預(yù)測算法

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

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

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

2.2.2 基于神經(jīng)網(wǎng)絡(luò)的鏈路預(yù)測算法WLNM

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

2.3 生成式對抗網(wǎng)絡(luò)

2.3.1 原始生成式對抗網(wǎng)絡(luò)算法

生成式對抗網(wǎng)絡(luò)[7]包括一個判別器模型與一個生成器模型。其中，判別器致力于識別輸入數(shù)據(jù)的來源：來自真實數(shù)據(jù)還是生成器生成的虛擬數(shù)據(jù)，并提高自身識別數(shù)據(jù)真?zhèn)蔚恼_性；而生成器D則致力于使自己生成的虛擬數(shù)據(jù)被判別器判別為真。這種生成器與判別器相互博弈、共同進化的構(gòu)成使得D和G的性能在迭代中不斷提升，直到雙方達到納什均衡狀態(tài)。

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

GAN的損失函數(shù)如下[7]：

2.3.2 分類生成式對抗網(wǎng)絡(luò)算法CatGAN

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

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

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

3 解決鏈路預(yù)測問題的WL-GAN模型

3.1 WL-GAN模型架構(gòu)

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

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

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

（3）將噪聲信息放入CatGAN生成式對抗網(wǎng)絡(luò)的生成模型中，生成虛擬數(shù)據(jù)。

（4）使用虛擬數(shù)據(jù)與真實數(shù)據(jù)訓(xùn)練分類生成式對抗網(wǎng)絡(luò)CatGAN[8]的全監(jiān)督模型。訓(xùn)練模型使得CatGAN判別器模型和生成器模型達到納什均衡，最終獲得強勁的能夠?qū)崿F(xiàn)鏈路預(yù)測功能的判別器模型。

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

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

輸入：目標節(jié)點對(x,y)，網(wǎng)絡(luò)G和子圖節(jié)點數(shù)K。

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

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

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

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

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

3.2 構(gòu)造全監(jiān)督GAN模型

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

Fig.2 Diagram of neural network圖2 神經(jīng)網(wǎng)絡(luò)的示意圖

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

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

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

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

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

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

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

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

證明

考慮到：

且：

從而可得：

證明（誤差公式1）

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

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

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

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

4 實驗設(shè)計與結(jié)果分析

4.1 模型評價指標與實驗數(shù)據(jù)集

4.1.1 模型評價指標

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

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

4.1.2 數(shù)據(jù)集

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

Table 2 Node information of datasets表2 數(shù)據(jù)集的節(jié)點信息表

4.2 參數(shù)分析實驗

本節(jié)將探討WL-GAN模型迭代次數(shù)epoch、目標函數(shù)交叉熵項權(quán)重參數(shù)λ和學(xué)習(xí)速率η對WL-GAN算法的實驗效果的影響。

4.2.1 對參數(shù)λ的分析

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

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

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

4.2.2 對參數(shù)η的分析

參數(shù)η是神經(jīng)網(wǎng)絡(luò)梯度下降時的學(xué)習(xí)速率。圖5、圖6分別代表了在兩種不同數(shù)據(jù)集USAir和Celegans下，不同η的取值對WL-GAN模型結(jié)果的影響，此時，λ固定為0.5。從圖5、圖6中可以看出，η取值越大，則模型收斂速度越快，但模型穩(wěn)定性越差，AUC曲線曲折較多。當η=0.1時，雖然模型收斂速度較慢，但是曲線平滑。這是由于η取值越大則梯度下降越快，但不一定完全朝梯度下降方向下降，η取值越小則梯度下降越慢，但是能保證盡量朝向梯度下降方向移動的原因?qū)е碌摹?/p>

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

4.3 對比實驗分析

本節(jié)將WL-GAN的實驗效果與一些現(xiàn)有算法的實驗效果進行對比。共選取了3個啟發(fā)性算法與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數(shù)據(jù)集上不同η下的WL-GAN性能

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

PA[9]：優(yōu)先連接算法。

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

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

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

WLNM[3]：WLNM是子圖編碼模型與神經(jīng)網(wǎng)絡(luò)分類模型的結(jié)合模型。神經(jīng)網(wǎng)絡(luò)層數(shù)構(gòu)造為Nl=[N,32,32,16,2]，N為樣本的向量長度，與本文算法WL-GAN中的判別器的神經(jīng)網(wǎng)絡(luò)構(gòu)成相同。其中，學(xué)習(xí)速率η=0.1，最大迭代次數(shù)200次。

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

5 結(jié)束語

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