陳文祺,王 英,3,王 鑫,汪洪吉

(1.吉林大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,吉林 長春 130012；2.吉林大學(xué)人工智能學(xué)院,吉林 長春 130012;3.吉林大學(xué)符號計(jì)算與知識(shí)工程教育部重點(diǎn)實(shí)驗(yàn)室,吉林 長春 130012)

1 引言

近年來，隨著互聯(lián)網(wǎng)技術(shù)的不斷發(fā)展，互聯(lián)網(wǎng)應(yīng)用層出不窮，越來越多的人們在互聯(lián)網(wǎng)上進(jìn)行工作和娛樂，互聯(lián)網(wǎng)逐漸深入人們生活的方方面面，其所承載的信息量與日俱增，大數(shù)據(jù)這一概念應(yīng)運(yùn)而生。在這些信息數(shù)據(jù)中，既有圖像、視頻和文獻(xiàn)資料這種保存信息的數(shù)據(jù)，也有保存信息之間關(guān)系的數(shù)據(jù)，而后一種信息數(shù)據(jù)就是以社交網(wǎng)絡(luò)和引文網(wǎng)絡(luò)等為代表的結(jié)構(gòu)化數(shù)據(jù)。這些結(jié)構(gòu)化數(shù)據(jù)是由節(jié)點(diǎn)和邊組成的圖結(jié)構(gòu)，節(jié)點(diǎn)可能是圖像、視頻和文獻(xiàn)資料這種保存信息的數(shù)據(jù)，而邊則是節(jié)點(diǎn)與節(jié)點(diǎn)之間的連接關(guān)系，如論文與論文之間的引用關(guān)系等。

隨著大數(shù)據(jù)時(shí)代的來臨，從互聯(lián)網(wǎng)上浩如煙海的數(shù)據(jù)中獲得想要的信息就成了當(dāng)務(wù)之急。而數(shù)據(jù)挖掘技術(shù)就是通過提取數(shù)據(jù)和變量之間的相互關(guān)系獲得精煉數(shù)據(jù)的技術(shù)，被廣泛應(yīng)用于社交網(wǎng)絡(luò)和推薦系統(tǒng)中，其本質(zhì)是對上述圖結(jié)構(gòu)數(shù)據(jù)中的節(jié)點(diǎn)進(jìn)行分類，從而獲得節(jié)點(diǎn)隱藏的其他特征。

數(shù)據(jù)量瘋狂增長，隨之而來的是處理數(shù)據(jù)、從數(shù)據(jù)中獲得有用信息愈發(fā)艱難。加拿大多倫多大學(xué)教授Hinton等人[1]在神經(jīng)網(wǎng)絡(luò)的基礎(chǔ)上提出了深度學(xué)習(xí)的概念，他們發(fā)現(xiàn)多層人工神經(jīng)網(wǎng)絡(luò)模型在特征學(xué)習(xí)方面有很好的表現(xiàn)，該學(xué)習(xí)模型學(xué)習(xí)到的特征數(shù)據(jù)相比于原始數(shù)據(jù)能夠表現(xiàn)出更深層的內(nèi)涵，這種數(shù)據(jù)能夠更好地應(yīng)用于分類和可視化問題，同時(shí)可以采用逐層訓(xùn)練方法來解決神經(jīng)網(wǎng)絡(luò)很難訓(xùn)練到最優(yōu)的問題。在這之后，研究人員基于深度學(xué)習(xí)提出了各種應(yīng)用于不同領(lǐng)域的模型，例如卷積神經(jīng)網(wǎng)絡(luò)CNN(Convolutional Neural Network)[2]模型就是一種通過卷積層和池化層來進(jìn)行特征提取的深度學(xué)習(xí)模型，其在圖像識(shí)別等領(lǐng)域的應(yīng)用取得了輝煌的成就。

深度學(xué)習(xí)模型一般分成3種：第1種為生成型深度結(jié)構(gòu)，這種結(jié)構(gòu)旨在描述數(shù)據(jù)的高階相關(guān)特性或觀測數(shù)據(jù)和相應(yīng)類別的聯(lián)合概率分布，例如自編碼器和深度置信網(wǎng)絡(luò)等；第2種為判別型深度結(jié)構(gòu)，這種結(jié)構(gòu)旨在為模式分類提供分辨能力，通常描述數(shù)據(jù)的后驗(yàn)分布；第3種則是混合型深度結(jié)構(gòu)，這種結(jié)構(gòu)同時(shí)包含了生成模型和判別模型，典型的例子就是生成對抗網(wǎng)絡(luò)GAN(Generative Adversarial Network)[3]模型。該模型包含一個(gè)生成模型和一個(gè)判別模型，其中生成模型的目的是捕捉真實(shí)數(shù)據(jù)的分布，判別模型的目的則是判斷輸入的是真實(shí)數(shù)據(jù)還是生成的樣本，二者之間通過Maxmin博弈來進(jìn)行優(yōu)化。這種模型應(yīng)用到了多個(gè)領(lǐng)域，并取得了較好的成績。

網(wǎng)絡(luò)嵌入是生成對抗網(wǎng)絡(luò)可以應(yīng)用的一個(gè)方向，對于節(jié)點(diǎn)分類來說，通過網(wǎng)絡(luò)嵌入得到特征向量是極其重要的步驟，由此通過生成對抗網(wǎng)絡(luò)獲得的特征向量有助于獲得更好的節(jié)點(diǎn)分類效果。基于此，研究人員提出了圖生成對抗網(wǎng)絡(luò)GraphGAN(Graph Generative Adversarial Network)[4]，一種利用生成對抗網(wǎng)絡(luò)來擬合其真實(shí)連通性分布的模型，通過該模型得到的擬合真實(shí)連通性分布的特征向量在鏈接預(yù)測、節(jié)點(diǎn)分類和推薦系統(tǒng)中的應(yīng)用都取得了優(yōu)異的成績。

因此，采用生成對抗網(wǎng)絡(luò)的方式將節(jié)點(diǎn)映射到低維空間，保持真實(shí)連通性分布以獲得不同鄰居的信息，以此來進(jìn)行節(jié)點(diǎn)分類是一種可行的方案，為大數(shù)據(jù)時(shí)代進(jìn)行數(shù)據(jù)挖掘提供了一條新的思路，具有一定的理論研究和參考價(jià)值。

本文第2節(jié)介紹相關(guān)工作；第3節(jié)闡述生成對抗網(wǎng)絡(luò)模型的具體構(gòu)造；第4節(jié)通過生成的節(jié)點(diǎn)特征向量矩陣來進(jìn)行節(jié)點(diǎn)分類并與其他模型進(jìn)行對比，以測試所提模型的可行性。

2 相關(guān)工作

節(jié)點(diǎn)分類作為數(shù)據(jù)挖掘技術(shù)的一種應(yīng)用，通過節(jié)點(diǎn)的各種信息進(jìn)行分類，能夠解決很多問題。對于引文網(wǎng)絡(luò)和社交網(wǎng)絡(luò)等網(wǎng)絡(luò)結(jié)構(gòu)數(shù)據(jù)來說，要將網(wǎng)絡(luò)中的節(jié)點(diǎn)進(jìn)行分類，要考慮的不僅僅是節(jié)點(diǎn)本身蘊(yùn)含的信息，還有節(jié)點(diǎn)之間的連接信息。

傳統(tǒng)的節(jié)點(diǎn)分類方法可以分為2種。一種是基于迭代使用局部分類器的方法，該類方法根據(jù)中心節(jié)點(diǎn)的節(jié)點(diǎn)信息和鄰接節(jié)點(diǎn)的標(biāo)簽信息來進(jìn)行節(jié)點(diǎn)分類。例如，Neville等人[5]將貝葉斯分類器作為局部分類器，通過訓(xùn)練數(shù)據(jù)訓(xùn)練貝葉斯分類器，然后選擇測試數(shù)據(jù)中與訓(xùn)練數(shù)據(jù)中節(jié)點(diǎn)存在邊的節(jié)點(diǎn)，將其特征向量作為輸入，貝葉斯分類器輸出該節(jié)點(diǎn)的標(biāo)簽，不斷迭代，直到所有節(jié)點(diǎn)分類完畢；Bhagat等人[6]提出了一個(gè)最近鄰分類器作為局部分類器的方法，即每次將有標(biāo)簽的節(jié)點(diǎn)的標(biāo)簽賦予和當(dāng)前節(jié)點(diǎn)相似度最高的節(jié)點(diǎn)，經(jīng)過不斷迭代，將標(biāo)簽賦予所有節(jié)點(diǎn)；Lu等人[7]將邏輯回歸分類器作為局部分類器，把鄰接節(jié)點(diǎn)的標(biāo)簽作為當(dāng)前節(jié)點(diǎn)的特征向量，并以此來進(jìn)行迭代分類；Macskassy等人[8]則直接把當(dāng)前節(jié)點(diǎn)的鄰接節(jié)點(diǎn)標(biāo)簽進(jìn)行加權(quán)平均作為分類結(jié)果，然后不斷進(jìn)行迭代以至所有節(jié)點(diǎn)的分類結(jié)果趨于穩(wěn)定。

另一種則是通過隨機(jī)游走來進(jìn)行分類，這種方法必須假設(shè)在圖中可以通過有限步數(shù)從任何無標(biāo)簽的節(jié)點(diǎn)到達(dá)存在標(biāo)簽的節(jié)點(diǎn)，在此基礎(chǔ)上，根據(jù)隨機(jī)游走的概率生成一個(gè)狀態(tài)轉(zhuǎn)移矩陣，并以此矩陣來進(jìn)行節(jié)點(diǎn)的分類。例如，Azran[9]提出了一種利用節(jié)點(diǎn)之間的相似性來構(gòu)造馬爾可夫隨機(jī)游走的概率轉(zhuǎn)移矩陣并對節(jié)點(diǎn)進(jìn)行分類的算法；Desrosiers等人[10]則提出了一種基于隨機(jī)游走的節(jié)點(diǎn)相似度度量算法，并將其應(yīng)用于節(jié)點(diǎn)分類領(lǐng)域。這些傳統(tǒng)的節(jié)點(diǎn)分類方法需要大量人工定義的變量，同時(shí)也不能將節(jié)點(diǎn)信息和連接信息考慮周全，更不能通盤地結(jié)合兩者進(jìn)行考量。由于傳統(tǒng)節(jié)點(diǎn)分類方法的局限性，研究人員考慮將其他領(lǐng)域的方法引入節(jié)點(diǎn)分類中。

神經(jīng)網(wǎng)絡(luò)算法近年來在各個(gè)領(lǐng)域取得了長足的進(jìn)步，甚至在某些方面取得了質(zhì)的突破。圖神經(jīng)網(wǎng)絡(luò)是一種可以運(yùn)行在圖結(jié)構(gòu)上的神經(jīng)網(wǎng)絡(luò)模型，這種模型利用圖中的節(jié)點(diǎn)信息和連接信息挖掘圖數(shù)據(jù)中潛藏的信息，并通過借鑒其他神經(jīng)網(wǎng)絡(luò)模型產(chǎn)生了各種不同的處理圖數(shù)據(jù)的圖神經(jīng)網(wǎng)絡(luò)。例如Niepert等人[11]提出的借鑒卷積神經(jīng)網(wǎng)絡(luò)的模型，即圖卷積神經(jīng)網(wǎng)絡(luò)。

生成對抗網(wǎng)絡(luò)是神經(jīng)網(wǎng)絡(luò)的一個(gè)分支，自從被提出以來，研究人員陸續(xù)提出了幾種具有代表性的生成對抗網(wǎng)絡(luò)模型。例如，(1)條件生成對抗網(wǎng)絡(luò)CGAN(Conditional Generative Adversarial Network)[12]，這種模型的生成模型和判別模型的輸入都需要一些條件信息，如標(biāo)簽信息和屬性信息等，基于此該模型能生成給定條件的圖像。(2)深度卷積生成網(wǎng)絡(luò)DCGAN(Deep Convolutional Generative Adversarial Network)[13]，這種模型是把卷積神經(jīng)網(wǎng)絡(luò)引入到生成對抗網(wǎng)絡(luò)，并進(jìn)行了以下改進(jìn)：①將卷積網(wǎng)絡(luò)中的池化層改為卷積層；②將全連接隱藏層去掉；③對生成模型和判別模型進(jìn)行歸一化；④生成網(wǎng)絡(luò)使用ReLU激活函數(shù)；⑤判別網(wǎng)絡(luò)使用LeakyReLU激活函數(shù)。該模型經(jīng)過上述改進(jìn)后具有更強(qiáng)的生成能力，能生成足以以假亂真的圖像。(3)信息生成對抗網(wǎng)絡(luò)InfoGAN(Info Generative Adversarial Network)[14]，該模型增加了一個(gè)潛在編碼，該編碼可以包含多個(gè)屬性，用于調(diào)整生成圖像的屬性。

生成對抗網(wǎng)絡(luò)經(jīng)過不斷發(fā)展，在各個(gè)領(lǐng)域內(nèi)都開花結(jié)果，在網(wǎng)絡(luò)嵌入領(lǐng)域也不例外，GraphGAN[4]模型就是用于將圖中的連接信息和節(jié)點(diǎn)信息映射到低維空間，以便于進(jìn)行連接預(yù)測和節(jié)點(diǎn)分類等。在此模型之前，網(wǎng)絡(luò)嵌入可以分為2種：一種是生成模型，即假定每個(gè)節(jié)點(diǎn)都存在一個(gè)潛在的真實(shí)連通性分布，該分布表示圖中其他所有節(jié)點(diǎn)上的連通性分布，圖中的邊被視為由這些條件分布生成的可觀察樣本，之后通過最大化圖中邊的似然性來學(xué)習(xí)網(wǎng)絡(luò)嵌入。例如，DeepWalk[15]使用隨機(jī)游走的方法對每個(gè)節(jié)點(diǎn)的“上下文”節(jié)點(diǎn)進(jìn)行采樣，并嘗試最大化每個(gè)節(jié)點(diǎn)的“上下文”節(jié)點(diǎn)的對數(shù)似然；node2vec[16]則通過一種有偏的隨機(jī)游走過程進(jìn)一步擴(kuò)展了該思想，該過程在為給定節(jié)點(diǎn)生成上下文時(shí)提供了更大的靈活性。另一種則是判別模型，就是對于訓(xùn)練數(shù)據(jù)中的2個(gè)節(jié)點(diǎn)來說，根據(jù)2個(gè)節(jié)點(diǎn)的特征向量和2個(gè)節(jié)點(diǎn)間邊的存在與否來學(xué)習(xí)節(jié)點(diǎn)特征向量和邊的存在之間的關(guān)系，用以預(yù)測測試數(shù)據(jù)中邊是否存在。例如，結(jié)構(gòu)化深度網(wǎng)絡(luò)嵌入SDNE(Structural Deep Network Embedding)模型[17]使用自編碼機(jī)，利用多層非線性函數(shù)捕捉網(wǎng)絡(luò)的高度非線性結(jié)構(gòu)，同時(shí)利用一階相似度作為監(jiān)督信息，保留網(wǎng)絡(luò)的局部結(jié)構(gòu)，二階相似度作為無監(jiān)督學(xué)習(xí)部分，保留網(wǎng)絡(luò)的全局結(jié)構(gòu)，從而構(gòu)成一個(gè)半監(jiān)督的深度學(xué)習(xí)模型；屬性保存網(wǎng)絡(luò)嵌入PPNE(Property Preserving Network Embedding)模型[18]則是在存在邊的節(jié)點(diǎn)對和不存在邊的節(jié)點(diǎn)對上通過監(jiān)督學(xué)習(xí)直接學(xué)習(xí)網(wǎng)絡(luò)嵌入，在學(xué)習(xí)過程中還保留了節(jié)點(diǎn)的固有屬性。盡管生成模型和判別模型可能有很大的區(qū)別，但兩者并不是2條平行線，GraphGAN模型就是融合了生成模型和判別模型的一種網(wǎng)絡(luò)嵌入模型。

3 基于生成對抗網(wǎng)絡(luò)的節(jié)點(diǎn)分類模型NC-GAN

為了解決傳統(tǒng)節(jié)點(diǎn)分類方法存在的問題，本文提出基于生成對抗網(wǎng)絡(luò)的節(jié)點(diǎn)分類模型NC-GAN(Node Classification based on GAN)，擬將生成對抗網(wǎng)絡(luò)引入節(jié)點(diǎn)分類，通過結(jié)合節(jié)點(diǎn)信息和連接信息，將網(wǎng)絡(luò)中的節(jié)點(diǎn)映射到低維空間中，獲得更加合理的節(jié)點(diǎn)表示，再通過節(jié)點(diǎn)表示進(jìn)行分類，以期獲得更好的分類效果。

3.1 模型相關(guān)定義

生成器旨在嘗試擬合真實(shí)連通性分布，在這個(gè)過程中生成器生成虛假但逐漸逼近真實(shí)的樣本節(jié)點(diǎn)用以欺騙判別器。而判別器則對生成器生成的樣本和真實(shí)數(shù)據(jù)進(jìn)行判斷，在提高判斷的正確率的過程中，使得生成器生成的樣本更加真實(shí)。生成器和判別器通過不斷進(jìn)行的交替最大最小化損失函數(shù)來進(jìn)行優(yōu)化，該損失函數(shù)如式(1)所示：

Ev～G(·|vc)[ln(1-D(v,vc))])

(1)

3.2 生成器的實(shí)現(xiàn)

生成器G(v|vc)旨在擬合真實(shí)連通性分布pture(v|vc)，從圖中所有節(jié)點(diǎn)的集合V中選擇與vc最有可能存在連接的節(jié)點(diǎn)，產(chǎn)生樣本數(shù)據(jù)供判別器進(jìn)行判斷，并期望通過生成足以以假亂真的樣本降低判別器的正確率。對于損失函數(shù)來說，生成器的目的就是將判別器正確分辨的概率最小化。由于生成的樣本數(shù)據(jù)是離散的，本文將通過策略梯度來計(jì)算損失函數(shù)中參數(shù)θG的梯度：

(2)

一種最簡單的生成器的實(shí)現(xiàn)可以將生成器定義為其他所有節(jié)點(diǎn)的Softmax函數(shù)，即：

(3)

為了解決使用上述Softmax函數(shù)作為生成器所帶來的問題，本文將使用一種能夠解決上述問題的函數(shù)來實(shí)現(xiàn)生成器。這種函數(shù)在計(jì)算時(shí)僅使用少量涉及到的節(jié)點(diǎn)特征向量，并且能夠充分地考慮圖數(shù)據(jù)中的節(jié)點(diǎn)連接信息，以生成擬合真實(shí)連通性分布的樣本，即生成樣本時(shí)2個(gè)節(jié)點(diǎn)的特征向量乘積越小，且節(jié)點(diǎn)之間的相似度越低，兩者之間存在邊的概率越小。為了實(shí)現(xiàn)上述函數(shù)，首先要從每一個(gè)節(jié)點(diǎn)開始，通過以該節(jié)點(diǎn)vc為根節(jié)點(diǎn)對圖數(shù)據(jù)進(jìn)行廣度優(yōu)先搜索，得到以vc為根所生成的廣度優(yōu)先搜索樹Tvc，那么Nvc(v)就是該廣度優(yōu)先搜索樹Tvc中和節(jié)點(diǎn)v存在直接連接信息的節(jié)點(diǎn)的集合，包括樹中該節(jié)點(diǎn)的父節(jié)點(diǎn)和所有子節(jié)點(diǎn)。對于節(jié)點(diǎn)v和與其鄰接的節(jié)點(diǎn)vi∈Nvc(v)之間的相似性概率，定義為：

(4)

式(4)表示的是在廣度優(yōu)先搜索樹中的節(jié)點(diǎn)v，與其他樹中與之鄰接的節(jié)點(diǎn)之間的相似性概率。該式是引入了注意力機(jī)制的結(jié)果，使用該式會(huì)使得生成樣本時(shí)更偏向于選擇相似度高的節(jié)點(diǎn)，從而使得相似度概率越大的節(jié)點(diǎn)對更新的影響越大。其中，‖gvi-gv‖2是給定的節(jié)點(diǎn)v和鄰接節(jié)點(diǎn)vi之間的歐氏距離，利用節(jié)點(diǎn)特征向量計(jì)算得到的歐氏距離可以表示2個(gè)節(jié)點(diǎn)之間的相似度，歐氏距離值越大，代表2個(gè)節(jié)點(diǎn)越遠(yuǎn)，也就是2個(gè)節(jié)點(diǎn)相似度越低?！苬j∈Nvc(v)e(‖gvj-gv‖2)則是在樹中與節(jié)點(diǎn)v相鄰的所有節(jié)點(diǎn)與v之間的相似度之和。用某一個(gè)節(jié)點(diǎn)的相似度除以所有節(jié)點(diǎn)的相似度之和，代表的是后續(xù)樣本選擇中選擇該節(jié)點(diǎn)的概率以及更新當(dāng)前節(jié)點(diǎn)的概率。

為了獲得生成器所需樣本，需要利用式(4)計(jì)算圖數(shù)據(jù)中所有節(jié)點(diǎn)與其鄰接節(jié)點(diǎn)的相似性概率，并利用該相似性概率進(jìn)行隨機(jī)采樣。

3.3 判別器的實(shí)現(xiàn)

判別器D旨在對生成器生成的樣本和真實(shí)數(shù)據(jù)進(jìn)行區(qū)分，通過判斷結(jié)果對自身進(jìn)行更新，使自身判斷的正確率得以提升。在NC-GAN模型中判別器被定義為2個(gè)節(jié)點(diǎn)之間特征向量的乘積的Sigmoid函數(shù)：

(5)

其中，v和vc是給定的2個(gè)節(jié)點(diǎn)，dv和dvc是給定節(jié)點(diǎn)對應(yīng)的k維特征向量。式(5)將2個(gè)節(jié)點(diǎn)特征向量的點(diǎn)乘代入Sigmoid函數(shù)中，得到的值就是給定的2個(gè)節(jié)點(diǎn)之間存在邊的概率，特征向量點(diǎn)乘的值越大，2個(gè)節(jié)點(diǎn)之間存在邊的概率越大。判別器以此概率作為對生成的樣本和真實(shí)連通性分布中的數(shù)據(jù)進(jìn)行判斷的依據(jù)，并根據(jù)該概率來對自身進(jìn)行隨機(jī)梯度上升更新：

(6)

3.4 樣本節(jié)點(diǎn)的選取

生成器需要生成樣本節(jié)點(diǎn)以欺騙判別器，本文根據(jù)式(4)所計(jì)算的相似性概率來隨機(jī)選擇樣本節(jié)點(diǎn)。首先從廣度優(yōu)先搜索樹Tvc的根節(jié)點(diǎn)vc開始進(jìn)行隨機(jī)游走，隨機(jī)游走的狀態(tài)轉(zhuǎn)移概率矩陣由節(jié)點(diǎn)之間的相似性概率組成。在隨機(jī)游走的過程中，當(dāng)訪問到的節(jié)點(diǎn)是上一個(gè)節(jié)點(diǎn)的父節(jié)點(diǎn)時(shí)，選擇上一個(gè)節(jié)點(diǎn)作為生成的樣本節(jié)點(diǎn)。

詳細(xì)來說，生成樣本時(shí)可以選擇以每一個(gè)節(jié)點(diǎn)為根的廣度優(yōu)先搜索樹來進(jìn)行隨機(jī)游走取樣，也可以隨機(jī)選取其中的某一部分節(jié)點(diǎn)，從以這些節(jié)點(diǎn)為根的搜索樹中隨機(jī)游走取樣。對于給定的節(jié)點(diǎn)vc，在以該節(jié)點(diǎn)為根的廣度優(yōu)先搜索樹Tvc中進(jìn)行隨機(jī)游走，從根節(jié)點(diǎn)開始，通過式(4)計(jì)算當(dāng)前節(jié)點(diǎn)和樹中父節(jié)點(diǎn)與所有子節(jié)點(diǎn)之間的相似性概率，并根據(jù)這個(gè)概率來選擇下一個(gè)要游走的節(jié)點(diǎn)，在隨機(jī)游走中不斷進(jìn)行迭代，直到第一次選擇上一個(gè)節(jié)點(diǎn)的父節(jié)點(diǎn)時(shí)，終止迭代，將上一個(gè)節(jié)點(diǎn)選擇為生成的樣本。節(jié)點(diǎn)vc有幾個(gè)鄰接節(jié)點(diǎn)，就生成幾個(gè)樣本供判別器進(jìn)行判斷和更新。生成器對生成樣本進(jìn)行更新時(shí)，使用生成樣本時(shí)經(jīng)過的路徑上的節(jié)點(diǎn)對作為更新時(shí)的樣本。算法1描述了生成器生成樣本的過程。

算法1生成器生成樣本

輸入：給定節(jié)點(diǎn)vc，以vc為根的廣度優(yōu)先搜索樹Tvc，節(jié)點(diǎn)特征向量集合{gi}vi∈V。

輸出：對于給定節(jié)點(diǎn)生成的樣本vgen。

步驟1vpre?vc，vcur?vc；

步驟2whileTRUEdo

通過式(4)計(jì)算vcur與鄰接節(jié)點(diǎn)的概率，并以此隨機(jī)選擇一個(gè)節(jié)點(diǎn)vi；

ifvi=vprethen

vgen?vcur;

returnvgen;

else

vpre?vcur，vcur?vi；

end

4 實(shí)驗(yàn)與分析

4.1 實(shí)驗(yàn)數(shù)據(jù)與模型

本節(jié)分別在數(shù)據(jù)集arxiv-AstroPh和arxiv-GrQc上進(jìn)行鏈接預(yù)測對比實(shí)驗(yàn)，在BlogCatalog、Wikipedia、CiteSeer和Cora等數(shù)據(jù)集上進(jìn)行節(jié)點(diǎn)分類對比實(shí)驗(yàn)，實(shí)驗(yàn)數(shù)據(jù)集的具體信息如表1所示。

用作對比實(shí)驗(yàn)的模型包括：

(1)GraphGAN[4]是使用節(jié)點(diǎn)特征向量的點(diǎn)乘來構(gòu)造生成器的一種圖生成對抗網(wǎng)絡(luò)模型，該模型更偏向于將節(jié)點(diǎn)的連接信息投影到低維空間，并不考慮節(jié)點(diǎn)之間的相似度，對所有節(jié)點(diǎn)一視同仁。

(2)大規(guī)模網(wǎng)絡(luò)編碼LINE(Large-scale In-formation Network Embedding)[4]是一種利用圖數(shù)據(jù)中的一階相似度和二階相似度來進(jìn)行網(wǎng)絡(luò)嵌入的模型。

Table 1 Experimental datasets

(3)Struc2Vec[4]是一種從空間結(jié)構(gòu)相似性的角度來計(jì)算節(jié)點(diǎn)相似度，并將其用來捕捉節(jié)點(diǎn)的結(jié)構(gòu)特征以獲得網(wǎng)絡(luò)嵌入的模型。

(4)DeepWalk[15]是針對圖表示學(xué)習(xí)的稀疏性提出的一種學(xué)習(xí)節(jié)點(diǎn)的社會(huì)特征的模型，該模型通過隨機(jī)游走方法從圖中提取節(jié)點(diǎn)序列，然后用節(jié)點(diǎn)序列來訓(xùn)練skip-gram模型，從而學(xué)習(xí)網(wǎng)絡(luò)嵌入。

(5)node2vec[16]是DeepWalk模型的一種變體，也是通過隨機(jī)游走方法提取節(jié)點(diǎn)序列，再通過skip-gram模型來學(xué)習(xí)網(wǎng)絡(luò)嵌入。但是，在隨機(jī)游走選擇樣本節(jié)點(diǎn)時(shí)，該模型同時(shí)結(jié)合了深度優(yōu)先搜索和廣度優(yōu)先搜索，形成了一種有偏的隨機(jī)游走。

(6)圖卷積網(wǎng)絡(luò)(GCN)[11]是在圖神經(jīng)網(wǎng)絡(luò)中引入卷積神經(jīng)網(wǎng)絡(luò)所形成的一種神經(jīng)網(wǎng)絡(luò)。通過對圖數(shù)據(jù)中節(jié)點(diǎn)信息和連接信息的提取來產(chǎn)生節(jié)點(diǎn)低維嵌入向量，再根據(jù)該低維向量來映射得到標(biāo)簽。

對于所有的對比模型，本實(shí)驗(yàn)采用默認(rèn)設(shè)置，本文NC-GAN模型在進(jìn)行梯度更新時(shí)，學(xué)習(xí)率設(shè)計(jì)為0.001。模型的迭代次數(shù)設(shè)置為20次，在每次迭代過程中，生成器和判別器的更新步數(shù)設(shè)計(jì)為30步。

4.2 實(shí)驗(yàn)結(jié)果與分析

本文NC-GAN模型所生成的數(shù)據(jù)，是將節(jié)點(diǎn)信息和連接信息同時(shí)映射到低維空間所得到的特征向量矩陣，該矩陣中節(jié)點(diǎn)之間的特征向量點(diǎn)乘值可以很好地反映出2節(jié)點(diǎn)之間存在邊的概率，為了驗(yàn)證生成的特征向量矩陣所蘊(yùn)含的這種連接信息，本節(jié)采用鏈接預(yù)測的方法，將本文NC-GAN模型的生成結(jié)果與其他圖表示學(xué)習(xí)模型的生成結(jié)果進(jìn)行對比。而為了驗(yàn)證NC-GAN模型生成的結(jié)果對節(jié)點(diǎn)分類的效果，本文將其生成的結(jié)果通過9∶1的比例使用邏輯回歸進(jìn)行對比。

4.2.1 鏈接預(yù)測

鏈接預(yù)測旨在預(yù)測2個(gè)節(jié)點(diǎn)之間是否存在邊，該任務(wù)能很好地展現(xiàn)圖表示學(xué)習(xí)所生成的結(jié)果中邊的可預(yù)測性。在實(shí)驗(yàn)中，將按照9∶1的比例來劃分?jǐn)?shù)據(jù)集，以其中90%的數(shù)據(jù)作為訓(xùn)練數(shù)據(jù)，另外10%的數(shù)據(jù)作為測試數(shù)據(jù)。在訓(xùn)練結(jié)束之后，將得到節(jié)點(diǎn)的特征向量矩陣，并使用邏輯回歸對給定節(jié)點(diǎn)之間邊的存在概率進(jìn)行預(yù)測。預(yù)測時(shí)，選擇10%的數(shù)據(jù)集中的節(jié)點(diǎn)以及節(jié)點(diǎn)之間的邊作為正樣本，并選擇隨機(jī)斷開存在的邊的節(jié)點(diǎn)作為負(fù)樣本。對比模型在數(shù)據(jù)集arxiv-AstroPh和arxiv-GrQc上的預(yù)測準(zhǔn)確率(Accuracy)和Macro-F1如表2所示。

從表2中可以看出，模型LINE和Struc2Vec并不能很好地獲取網(wǎng)絡(luò)中節(jié)點(diǎn)之間的連接信息，在連接預(yù)測中表現(xiàn)不好。DeepWalk和node2vec模型對連接信息進(jìn)行了考慮，在鏈接預(yù)測中取得了不錯(cuò)的成績。模型GraphGAN則取得了相對來說最好的成績，由于該模型在生成樣本時(shí)更偏向于存在邊概率更大的節(jié)點(diǎn)，最終模型生成的節(jié)點(diǎn)特征向量會(huì)更加容易判斷出邊是否存在。本文提出的模型NC-GAN更關(guān)注于節(jié)點(diǎn)之間的相似度，僅比更專注于節(jié)點(diǎn)連接信息的GraphGAN模型在鏈接預(yù)測上稍差一籌。

Table 2 Link prediction experiments comparison of each model

4.2.2 節(jié)點(diǎn)分類

節(jié)點(diǎn)分類旨在通過節(jié)點(diǎn)屬性信息和節(jié)點(diǎn)之間的連接信息，將節(jié)點(diǎn)分成不同的類別，以對應(yīng)不同的標(biāo)簽，以此來獲取原始數(shù)據(jù)中不含有的信息。節(jié)點(diǎn)分類實(shí)驗(yàn)中將按照9∶1的比例把數(shù)據(jù)集分為訓(xùn)練集和測試集，通過監(jiān)督學(xué)習(xí)在使用訓(xùn)練集進(jìn)行訓(xùn)練之后，能夠在測試集中預(yù)測節(jié)點(diǎn)所屬的類別標(biāo)簽。實(shí)驗(yàn)分為2個(gè)部分：首先在數(shù)據(jù)集BlogCatalog和Wikipedia上使用各種使用圖表示學(xué)習(xí)模型獲得節(jié)點(diǎn)特征向量，再通過邏輯回歸對各種模型的結(jié)果進(jìn)行節(jié)點(diǎn)分類對比；然后在數(shù)據(jù)集CiteSeer和Cora上對圖卷積網(wǎng)絡(luò)得到的節(jié)點(diǎn)分類效果、使用GraphGAN模型得到的特征矩陣對應(yīng)的邏輯回歸節(jié)點(diǎn)分類效果以及使用NC-GAN模型得到的特征矩陣對應(yīng)的邏輯回歸節(jié)點(diǎn)分類效果進(jìn)行對比。對比結(jié)果如表3所示。

從表3中可以看出，本文的NC-GAN模型在節(jié)點(diǎn)分類上的性能明顯優(yōu)于其他圖表示學(xué)習(xí)模型。LINE 模型注重鄰接節(jié)點(diǎn)的相似度，不考慮節(jié)點(diǎn)連接信息，得到的節(jié)點(diǎn)分類效果較差。Struc2Vec模型更關(guān)注于節(jié)點(diǎn)之間結(jié)構(gòu)的相似度，得到的節(jié)點(diǎn)分類效果差強(qiáng)人意。DeepWalk和node2vec更關(guān)注于節(jié)點(diǎn)之間的連接信息，忽略了節(jié)點(diǎn)本身所蘊(yùn)含的信息，導(dǎo)致節(jié)點(diǎn)分類的效果不是很理想。而GraphGAN則是更偏向于獲得更加擬合真實(shí)連通性的分布，而不是更好地對節(jié)點(diǎn)進(jìn)行區(qū)分。

Table 3 Comparison of node classification experiments among learning models

根據(jù)圖1所示對比結(jié)果，本文的NC-GAN模型所生成的特征矩陣，在經(jīng)過邏輯回歸計(jì)算分類后，所得的準(zhǔn)確率比圖卷積網(wǎng)絡(luò)模型得到的分類準(zhǔn)確率和GraphGAN模型經(jīng)過邏輯回歸得到的準(zhǔn)確率都要高。由此可以看出，本文設(shè)計(jì)的模型在GraphGAN模型的基礎(chǔ)上，對于節(jié)點(diǎn)分類來說更進(jìn)了一步。

Figure 1 Node classification experiments comparison with graph convolutional networks

5 結(jié)束語

為了解決傳統(tǒng)節(jié)點(diǎn)分類方法存在的問題，本文引入生成對抗網(wǎng)絡(luò)。生成對抗網(wǎng)絡(luò)通過生成模型和判別模型之間的二元博弈來生成所需的數(shù)據(jù)。GraphGAN模型將生成對抗網(wǎng)絡(luò)引入圖網(wǎng)絡(luò)中，用于生成擬合真實(shí)連通性分布的數(shù)據(jù)，但由于過于重視節(jié)點(diǎn)之間的連接信息，沒有考慮節(jié)點(diǎn)之間的關(guān)系，節(jié)點(diǎn)分類效果在對比模型中沒有達(dá)到最好。本文在該模型的基礎(chǔ)上考慮了節(jié)點(diǎn)之間的相似度，用相似度來代替節(jié)點(diǎn)之間的連接信息，使得生成的節(jié)點(diǎn)表示更有利于節(jié)點(diǎn)分類。實(shí)驗(yàn)結(jié)果也表明，本文的模型在節(jié)點(diǎn)分類的效果上優(yōu)于其他對比模型。