導(dǎo)語: 生成對抗網(wǎng)絡(luò)（Generative Adversarial Network，簡稱GAN）是非監(jiān)督式學(xué)習(xí)的一種方法，通過讓兩個(gè)神經(jīng)網(wǎng)絡(luò)相互博弈的方式進(jìn)行學(xué)習(xí)。自2014年GAN網(wǎng)絡(luò)提出以來，其在Computer Vision（計(jì)算機(jī)視覺）領(lǐng)域獲得了廣泛的關(guān)注，但GAN網(wǎng)絡(luò)在其他領(lǐng)域的應(yīng)用相對較少。將GAN網(wǎng)絡(luò)的思想應(yīng)用在圖網(wǎng)絡(luò)（network）特征表達(dá)是近一年新興的課題，本文綜述GAN模型在圖網(wǎng)絡(luò)表征學(xué)習(xí)方面的研究。

背景介紹

網(wǎng)絡(luò)表征學(xué)習(xí)(Graph Representation Learning、 Network Embedding、 Graph Embedding)的主要目的在于，將圖中每一個(gè)節(jié)點(diǎn)都映射到一個(gè)低維向量空間，使得其在此空間內(nèi)保持原有圖的結(jié)構(gòu)和距離信息。直觀理解是，靠近的兩個(gè)點(diǎn)在低緯空間中的距離接近。如下圖所示（邊上的數(shù)字代表邊的長度）。

對于圖表征學(xué)習(xí)的研究從很早就開始了，從最簡單的鄰接矩陣（Adjancency Matrix）表示，到后面對鄰接矩陣進(jìn)行矩陣分解（SVD），再到前幾年比較火的基于隨機(jī)游走的方法（DeepWalk、Node2Vec）以及最近基于深度網(wǎng)絡(luò)的Graph Neural Network和基于注意力機(jī)制的Graph Attention Network模型，其目的都在于將網(wǎng)絡(luò)結(jié)構(gòu)映射到低維空間以應(yīng)用到多項(xiàng)任務(wù)中，如鏈路預(yù)測、節(jié)點(diǎn)分類等等。

本文主要介紹生成對抗網(wǎng)絡(luò)模型（Generative Adversarial Network）在圖表征學(xué)習(xí)中的最新進(jìn)展。本文中，網(wǎng)絡(luò)模型如neural network中的network均稱為模型；網(wǎng)絡(luò)結(jié)構(gòu)如social network中的network均稱為圖網(wǎng)絡(luò)。

GraphGAN模型

論文[1]將圖表征學(xué)習(xí)的方法分為兩類，第一類叫生成式（generative）模型，第二類叫判別式（discriminative）模型。

生成式模型假設(shè)每一個(gè)節(jié)點(diǎn)都有一個(gè)潛在的概率分布，這個(gè)概率分布可以體現(xiàn)出該節(jié)點(diǎn)和其他每一個(gè)節(jié)點(diǎn)的連接情況。生成式模型的主要目的就是為圖網(wǎng)絡(luò)中的節(jié)點(diǎn)找到一個(gè)盡可能接近該潛在概率分布的向量表征。論文[1]中對這個(gè)潛在概率分布的表示為Ptrue(V|Vc)，其中Vc表示正在觀測的節(jié)點(diǎn)，Ptrue(V|Vc) 就是指在除了 Vc 之外其他節(jié)點(diǎn)（V）與Vc之間構(gòu)成一條邊的概率。

判別式模型是指，模型直接去學(xué)習(xí)兩個(gè)節(jié)點(diǎn)之間有邊的概率。這種方法會(huì)將邊<Vi, Vj>的兩個(gè)定點(diǎn)Vi 和 Vj 聯(lián)合作為 feature，然后輸出的是邊<Vi, Vj>存在的概率 P(<Vi, Vj>|Vi, Vj)。判別式模型往往是有監(jiān)督的。

GraphGAN即為生成式模型和判別式模型的結(jié)合，其包含兩個(gè)重要部分，即生成器G(v|v_c ; θ_G)?和判別器D(v|v_c ; θ_D)。生成器為每一個(gè)節(jié)點(diǎn)維護(hù)一個(gè)向量，這些向量組合在一起構(gòu)成θG。G(v|v_c?; θ_G)?表示生成器認(rèn)為給定節(jié)點(diǎn)Vc和參數(shù)θ_G下，V與Vc之間有一條邊的概率。G(v|v_c?; θ_G)?的目的就是通過學(xué)習(xí)去逼近真實(shí)分布Ptrue(V|Vc)。判別器也為每一個(gè)節(jié)點(diǎn)維護(hù)一個(gè)向量，這些向量組合在一起構(gòu)成θ_D。D(v|v_c ; θ_D)通過向量θ_D來判斷V與Vc之間是否有一條邊。

GraphGAN采用GAN網(wǎng)絡(luò)中常見的對抗機(jī)制：生成器G盡可能的逼近Ptrue(V|Vc)以找到與Vc的相鄰節(jié)點(diǎn)極其相似的節(jié)點(diǎn)來欺騙判別器D，而判別器D則會(huì)反過來檢測給定的節(jié)點(diǎn)V是Vc的真實(shí)鄰居還是由生成器生成的。GraphGAN方法的核心在于公式（1）中的目標(biāo)函數(shù)：

在給定θ_D的情況下，生成器G希望盡可能減少下式的值：

即降低（V，Vc）被D判定為非鄰居的概率；

在給定θ_G的情況下，判別器希望盡可能增大下式的值：

即判斷真實(shí)樣本為鄰居的概率盡可能接近1

同時(shí)增大下式的值:

即判斷生成器生成的樣本的概率盡可能接近0。

理解了公式（1）就基本理解了GraphGAN的內(nèi)在原理，下圖給出GraphGAN工作的流程。θ_D和θ_G可以通過交替最小化和最大化V(G,D)函數(shù)來迭代更新得到。每次迭代，我們從 Ptrue 中 抽樣一些跟 Vc 真實(shí)相鄰的綠點(diǎn)，從 G 中又生成了一些跟 Vc 接近的藍(lán)點(diǎn)。我們將綠點(diǎn)作為正樣本，將藍(lán)點(diǎn)作為負(fù)樣本來訓(xùn)練 D，在得到 D 之后，再用 D 中的信號，通過policy gradient去反過來訓(xùn)練 G。不斷重復(fù)這個(gè)過程，直到生成器 G 和 Ptrue 極為接近。在剛開始的時(shí)候，G 相對比較差，因此對于給定的 Vc 而言，G sample 的點(diǎn)都是一些離 Vc 很遠(yuǎn)的點(diǎn)。隨著訓(xùn)練的不斷進(jìn)行，G sample 的點(diǎn)會(huì)逐漸向 Vc 接近，到最后 G 抽樣的點(diǎn)幾乎都變成了真正跟 Vc 相鄰的點(diǎn)，也就是 G 和 Ptrue 已經(jīng)很難被區(qū)分了。

判別器D的實(shí)現(xiàn)是兩個(gè)節(jié)點(diǎn)向量的內(nèi)積再取sogmoid：

生成器G的基本實(shí)現(xiàn)是一個(gè)softmax函數(shù)，即選擇離Vc向量距離最接近的V：

論文的另一個(gè)技術(shù)貢獻(xiàn)在于設(shè)計(jì)了一個(gè)基于寬度有限搜索的生成規(guī)則，使得生成器每次尋找鄰居節(jié)點(diǎn)的時(shí)候不需要將Vc和圖網(wǎng)絡(luò)中的每一個(gè)其他節(jié)點(diǎn)進(jìn)行計(jì)算，這一部分優(yōu)化與GAN網(wǎng)絡(luò)思想關(guān)系不太緊密這里不做詳細(xì)介紹了。

以上就是GraphGAN模型的主要思想和模型更改，GraphGAN基于回答“兩個(gè)節(jié)點(diǎn)之間是否存在一條邊”這個(gè)圖網(wǎng)絡(luò)研究中非常重要的問題而構(gòu)建判別器和生成器，給后續(xù)GAN模型在圖網(wǎng)絡(luò)領(lǐng)域的研究一些啟迪。代碼：

https://github.com/hwwang55/GraphGAN

CommunityGAN模型

論文[2]中介紹了一種基于GAN模型的可重疊社區(qū)發(fā)現(xiàn)方法，稱為CommunityGAN。實(shí)際上，基于前面GraphGAN中產(chǎn)生的節(jié)點(diǎn)表征，通過聚類的方法也可以得到圖網(wǎng)絡(luò)中的社區(qū)。但是，GraphGAN中的表征僅僅考慮了邊的信息，而社區(qū)的形成往往需要更加緊密的結(jié)構(gòu)如團(tuán)（clique），所以CommunityGAN的基本思路就由GraphGAN中回答“兩個(gè)節(jié)點(diǎn)之間是否存在一條邊”變成了“多個(gè)節(jié)點(diǎn)之間是否兩兩相連”，來解決社區(qū)發(fā)現(xiàn)的問題。下面簡單介紹一下CommunityGAN模型。

首先，CommunityGAN假設(shè)每個(gè)節(jié)點(diǎn)可以屬于多個(gè)社區(qū)。論文中對每個(gè)節(jié)點(diǎn)維持一個(gè)社區(qū)歸屬度的向量，向量的每一維表示該節(jié)點(diǎn)屬于對應(yīng)社區(qū)的權(quán)重，如下圖（V為節(jié)點(diǎn)id，C為社區(qū)id）：

論文首先證明，在現(xiàn)實(shí)圖網(wǎng)絡(luò)中，團(tuán)的結(jié)構(gòu)更容易出現(xiàn)在社區(qū)當(dāng)中，即，在同一個(gè)社區(qū)中的幾個(gè)節(jié)點(diǎn)比跨社區(qū)的幾個(gè)節(jié)點(diǎn)更容易出現(xiàn)兩兩相連的情況。這一點(diǎn)也是符合我們的直觀感受的。基于這一點(diǎn)，CommunityGAN設(shè)計(jì)了與GraphGAN非常類似的模型結(jié)構(gòu)，唯一的差別就是，GraphGAN旨在判斷兩點(diǎn)之間是否有邊，而CommunityGAN則是判斷k個(gè)點(diǎn)之間是否成團(tuán)。

生成G(s|v_c;θ_G)在給定節(jié)點(diǎn)Vc的情況下，找到一個(gè)集合s，并認(rèn)為s與Vc構(gòu)成一個(gè)兩兩相連的團(tuán)。假設(shè)我們以三團(tuán)（3-clique）為目標(biāo)，那么|s|=2。判別器D(s,θ_D)則是判斷給定的節(jié)點(diǎn)集合s是否構(gòu)成一個(gè)團(tuán)。有了前面關(guān)于GraphGAN的背景，這里對于CommunityGAN的目標(biāo)函數(shù)就很容易理解了：

其中Ptrue是真實(shí)團(tuán)在網(wǎng)絡(luò)中的分布。與GraphGAN類似，θ_G由每個(gè)節(jié)點(diǎn)的圈子歸屬度向量組成，θ_D由判別器中的每個(gè)節(jié)點(diǎn)的表征向量組合而成。

模型訓(xùn)練如下圖所示：對于每一個(gè)節(jié)點(diǎn)Vc，我們根據(jù)Ptrue抽樣真實(shí)的團(tuán)結(jié)構(gòu)作為正樣本，生成器按照θ_G尋找向量接近的節(jié)點(diǎn)構(gòu)成負(fù)樣本，訓(xùn)練判別器。對應(yīng)的，判別器在收到生成器的負(fù)樣本后會(huì)對樣本進(jìn)行打分，然后將分?jǐn)?shù)反饋給生成器，生成器通過policy gradient對θ_G進(jìn)行更新。最終得到社區(qū)結(jié)果的方法是，θ_G中每一個(gè)維度上的歸屬度大于一定閾值的節(jié)點(diǎn)就屬于該維度對應(yīng)的社區(qū)。

CommunityGAN中對生成器產(chǎn)生樣本的邏輯也有一定優(yōu)化，通過隨機(jī)游走的方式保證并非所有的節(jié)點(diǎn)在一次選取中都要被全部計(jì)算一次。論文中對θ_G的起始狀態(tài)有一定要求，作者通過AGM算法對θ_G進(jìn)行初始化。在實(shí)際實(shí)驗(yàn)過程中，我們也發(fā)現(xiàn)當(dāng)θ_G沒有被合理初始化時(shí)，CommunityGAN模型很難收斂，甚至根本不具備學(xué)習(xí)的能力。但在合理初始化的前提下，CommunityGAN可以明顯提高社區(qū)劃分的質(zhì)量。代碼：

https://github.com/SamJia/CommunityGAN

NetRA模型

為了對每個(gè)節(jié)點(diǎn)進(jìn)行表征，前面兩個(gè)模型都需要針對每一個(gè)節(jié)點(diǎn)去抽樣正樣本和生成負(fù)樣本，這在現(xiàn)實(shí)生活中的巨型網(wǎng)絡(luò)上是很難實(shí)現(xiàn)的。論文[3]采用了一種基于隨機(jī)游走的圖表征模型。實(shí)際上，基于隨機(jī)游走的圖表征模型已經(jīng)有很多，例如DeepWalk。但這類模型有一個(gè)問題，就是當(dāng)我們控制抽樣數(shù)量不變時(shí)，walk的長度越長，則效果越差。原因在于walk的長度變長時(shí)，可能出現(xiàn)的walk所組成的sample也增多，而當(dāng)我們采樣不足時(shí)則會(huì)出現(xiàn)過擬合的問題。反過來講，如果我們減小walk的長度，那么其對于網(wǎng)絡(luò)表征的能力也會(huì)相應(yīng)下降。論文給出了一組基于DeepWalk進(jìn)行邊預(yù)測的實(shí)驗(yàn)，假設(shè)圖中節(jié)點(diǎn)的平均度數(shù)為d，walk的長度為l，而抽樣的walk數(shù)量為k，他們?nèi)咧g的關(guān)系如下圖所示。

如上圖，當(dāng)l或者d增大是，抽樣變得越來越稀疏，使得模型過擬合導(dǎo)致效果變差。而當(dāng)我們增加walk的數(shù)量時(shí)，模型表現(xiàn)就會(huì)提升。

論文[3]提出的NetRA模型(Network Representation with Adversatially Regularized Autoencoders)要解決的就是在抽樣比較稀疏的情況下，避免圖表征過擬合的問題。具體而言，NetRA通過引入一個(gè)GAN模型的正則項(xiàng)使得encoder能夠提取到更有用的信息。NetRA的整體模型框架如下圖。

該模型主要包含三個(gè)部分，Autoencoder（藍(lán)色虛線框部分）、GAN（綠色虛線框部分）和圖表征（紅色虛線框部分）。下面分別介紹這三個(gè)部分。

Autoencoder

該部分包含兩個(gè)函數(shù)，編碼函數(shù)fφ(·)和解碼函數(shù)h_Ψ(·)。編碼函數(shù)將輸入映射到一個(gè)低維空間上，而解碼函數(shù)則可以通過低維向量反推出原輸入。Autoencoder的目標(biāo)就是輸入（x）經(jīng)過編碼和解碼之后，輸出(h_Ψ(fφ(x)))和輸入（x）盡可能的接近。假設(shè)Pdata為數(shù)據(jù)的真實(shí)分布，那么Autoencoder的目標(biāo)函數(shù)則為

其中，距離函數(shù)采用交叉熵定義，即

值得一提的是，本文采用LSTM模型作為編碼器，主要是因?yàn)長STM模型對于序列型輸入的有效處理能夠使得由隨機(jī)游走產(chǎn)生的節(jié)點(diǎn)序列被最好的表達(dá)。

GAN

圖中綠色框線中即為GAN模型的圖示。

生成器g_θ(·)嘗試從噪音中產(chǎn)生離真實(shí)數(shù)據(jù)分布盡可能接近的數(shù)據(jù)，而判別器d_w(x)則會(huì)計(jì)算輸入x來自真實(shí)樣本的概率。假設(shè)真實(shí)樣本分布為Pdata（x），而生成器采用分布為Pg（z），那么GAN模型中

這里的真實(shí)樣本即為上面的Autoencoder中的編碼器Encoder所產(chǎn)生的低維向量，所以當(dāng)我們對GAN進(jìn)行訓(xùn)練時(shí)，同時(shí)也將正負(fù)樣本之間的差異反饋給Encoder，從而使得1）Encoder需要提取更有效的代表節(jié)點(diǎn)的信息以區(qū)分偽樣本；2）Encoder需要避免過擬合，以免太容易被生成器學(xué)習(xí)。

Network Embedding

Autoencoder通過隨機(jī)游走抽樣網(wǎng)絡(luò)中路徑來獲得節(jié)點(diǎn)與節(jié)點(diǎn)在整體網(wǎng)絡(luò)上的結(jié)構(gòu)信息，而Network Embedding這一部分則通過保留節(jié)點(diǎn)與節(jié)點(diǎn)之間的邊信息來獲得local的連接關(guān)系。這里Embedding的函數(shù)仍然是Autoencoder中的編碼器，即fφ(·)。通過最小化下面這個(gè)函數(shù)使得編碼器編碼出的向量能夠保證有邊連接的節(jié)點(diǎn)的低維表達(dá)是接近的：

這里?φ_ij?表示節(jié)點(diǎn)i與j之間是否有連邊，有為1，沒有則為0.

有了前面三部分的介紹，整體NetRA模型優(yōu)化的函數(shù)則可以寫為

這里L(fēng)AE表示Autoencoder學(xué)習(xí)的目標(biāo)，LLE和W分別是Network Embedding和GAN模型所承擔(dān)的正則項(xiàng)，用來保證編碼器的結(jié)果可以保留網(wǎng)絡(luò)中的邊信息以及防止過擬合。

NetRA模型的訓(xùn)練過程為：

• 給定一個(gè)網(wǎng)絡(luò)，通過隨機(jī)游走獲得一些長度為l的路徑。將這些路徑中的節(jié)點(diǎn)通過one-hot encoding構(gòu)建特征序列輸入LSTM模型產(chǎn)生Encoder的輸出，即節(jié)點(diǎn)的向量表征。

• 將這些向量表征輸入Decoder函數(shù)，得到解碼的特征向量。通過計(jì)算這些解碼的特征向量與原始特征向量求交叉熵?fù)p失來更新Autoencoder的參數(shù)。

• 同時(shí)，Network Embedding保證相鄰的節(jié)點(diǎn)的編碼向量互相接近。

• 另外，將編碼的向量與GAN模型中的生成器產(chǎn)生的向量分別作為正負(fù)樣本去訓(xùn)練判別器。

• 最終的節(jié)點(diǎn)向量表征幾時(shí)編碼器產(chǎn)生的結(jié)果。

可以看見，NetRA模型并不僅僅是一個(gè)GAN模型的結(jié)構(gòu)，而是將GAN模型當(dāng)做正則項(xiàng)的一部分嵌入整個(gè)模型中得到節(jié)點(diǎn)的表征。這里為我們對GAN模型的應(yīng)用提供了一個(gè)不同的思路。

小結(jié)

本文介紹了生成對抗網(wǎng)絡(luò)模型在圖表征學(xué)習(xí)中的基本方法（GraphGAN）、在社區(qū)發(fā)現(xiàn)任務(wù)中的應(yīng)用（CommunityGAN）以及作為模型的正則項(xiàng)構(gòu)建更復(fù)雜的圖表征模型（NetRA）。基于GAN模型或者說對抗學(xué)習(xí)思路在圖表征學(xué)習(xí)當(dāng)中的 研究還有很多，本文僅僅拋磚引玉的調(diào)研了三種比較常見的使用場景。這里是一個(gè)圖神經(jīng)網(wǎng)絡(luò)相關(guān)論文的集錦，可以看到圖神經(jīng)網(wǎng)絡(luò)在近兩年受到很多的關(guān)注。

除了同學(xué)、同事、親人這樣的親密關(guān)系，微信上我們還加了許多房產(chǎn)中介、招聘HR、商品經(jīng)銷商等等非親密關(guān)系的好友。我們和非親密關(guān)系的好友之間的邊被稱為weak ties（弱關(guān)系）。我們團(tuán)隊(duì)針對關(guān)系鏈的畫像任務(wù)中，不僅僅挖掘出強(qiáng)關(guān)系，還找到了微信網(wǎng)絡(luò)中的弱關(guān)系。

參考文獻(xiàn)

[1] Wang etc.?GraphGAN: Graph Representation Learning with Generative Adversarial Nets. AAAI'18.

[2] Jia etc.?CommunityGAN: Community Detection with Generative Adversarial Nets. WWW'19.

[3] Yu etc. Learning Deep Network Representations with Adversarially Regularized Autoencoders. KDD'18.

總結(jié)

以上是生活随笔為你收集整理的综述 | 生成对抗网络（GAN）在图网络中的应用的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。