基于生成對抗網絡的多標簽節點分類研究*

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

(1.吉林大學計算機科學與技術學院,吉林 長春 130012；2.吉林大學人工智能學院,吉林 長春 130012;3.吉林大學符號計算與知識工程教育部重點實驗室,吉林 長春 130012)

1 引言

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

隨著大數據時代的來臨，從互聯網上浩如煙海的數據中獲得想要的信息就成了當務之急。而數據挖掘技術就是通過提取數據和變量之間的相互關系獲得精煉數據的技術，被廣泛應用于社交網絡和推薦系統中，其本質是對上述圖結構數據中的節點進行分類，從而獲得節點隱藏的其他特征。

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

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

網絡嵌入是生成對抗網絡可以應用的一個方向，對于節點分類來說，通過網絡嵌入得到特征向量是極其重要的步驟，由此通過生成對抗網絡獲得的特征向量有助于獲得更好的節點分類效果?；诖?，研究人員提出了圖生成對抗網絡GraphGAN(Graph Generative Adversarial Network)[4]，一種利用生成對抗網絡來擬合其真實連通性分布的模型，通過該模型得到的擬合真實連通性分布的特征向量在鏈接預測、節點分類和推薦系統中的應用都取得了優異的成績。

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

本文第2節介紹相關工作；第3節闡述生成對抗網絡模型的具體構造；第4節通過生成的節點特征向量矩陣來進行節點分類并與其他模型進行對比，以測試所提模型的可行性。

2 相關工作

節點分類作為數據挖掘技術的一種應用，通過節點的各種信息進行分類，能夠解決很多問題。對于引文網絡和社交網絡等網絡結構數據來說，要將網絡中的節點進行分類，要考慮的不僅僅是節點本身蘊含的信息，還有節點之間的連接信息。

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

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

神經網絡算法近年來在各個領域取得了長足的進步，甚至在某些方面取得了質的突破。圖神經網絡是一種可以運行在圖結構上的神經網絡模型，這種模型利用圖中的節點信息和連接信息挖掘圖數據中潛藏的信息，并通過借鑒其他神經網絡模型產生了各種不同的處理圖數據的圖神經網絡。例如Niepert等人[11]提出的借鑒卷積神經網絡的模型，即圖卷積神經網絡。

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

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

3 基于生成對抗網絡的節點分類模型NC-GAN

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

3.1 模型相關定義

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

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

(1)

3.2 生成器的實現

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

(2)

一種最簡單的生成器的實現可以將生成器定義為其他所有節點的Softmax函數，即：

(3)

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

(4)

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

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

3.3 判別器的實現

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

(5)

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

(6)

3.4 樣本節點的選取

生成器需要生成樣本節點以欺騙判別器，本文根據式(4)所計算的相似性概率來隨機選擇樣本節點。首先從廣度優先搜索樹Tvc的根節點vc開始進行隨機游走，隨機游走的狀態轉移概率矩陣由節點之間的相似性概率組成。在隨機游走的過程中，當訪問到的節點是上一個節點的父節點時，選擇上一個節點作為生成的樣本節點。

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

算法1生成器生成樣本

輸入：給定節點vc，以vc為根的廣度優先搜索樹Tvc，節點特征向量集合{gi}vi∈V。

輸出：對于給定節點生成的樣本vgen。

步驟1vpre?vc，vcur?vc；

步驟2whileTRUEdo

通過式(4)計算vcur與鄰接節點的概率，并以此隨機選擇一個節點vi；

ifvi=vprethen

vgen?vcur;

returnvgen;

else

vpre?vcur，vcur?vi；

end

4 實驗與分析

4.1 實驗數據與模型

本節分別在數據集arxiv-AstroPh和arxiv-GrQc上進行鏈接預測對比實驗，在BlogCatalog、Wikipedia、CiteSeer和Cora等數據集上進行節點分類對比實驗，實驗數據集的具體信息如表1所示。

用作對比實驗的模型包括：

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

(2)大規模網絡編碼LINE(Large-scale In-formation Network Embedding)[4]是一種利用圖數據中的一階相似度和二階相似度來進行網絡嵌入的模型。

Table 1 Experimental datasets

(3)Struc2Vec[4]是一種從空間結構相似性的角度來計算節點相似度，并將其用來捕捉節點的結構特征以獲得網絡嵌入的模型。

(4)DeepWalk[15]是針對圖表示學習的稀疏性提出的一種學習節點的社會特征的模型，該模型通過隨機游走方法從圖中提取節點序列，然后用節點序列來訓練skip-gram模型，從而學習網絡嵌入。

(5)node2vec[16]是DeepWalk模型的一種變體，也是通過隨機游走方法提取節點序列，再通過skip-gram模型來學習網絡嵌入。但是，在隨機游走選擇樣本節點時，該模型同時結合了深度優先搜索和廣度優先搜索，形成了一種有偏的隨機游走。

(6)圖卷積網絡(GCN)[11]是在圖神經網絡中引入卷積神經網絡所形成的一種神經網絡。通過對圖數據中節點信息和連接信息的提取來產生節點低維嵌入向量，再根據該低維向量來映射得到標簽。

對于所有的對比模型，本實驗采用默認設置，本文NC-GAN模型在進行梯度更新時，學習率設計為0.001。模型的迭代次數設置為20次，在每次迭代過程中，生成器和判別器的更新步數設計為30步。

4.2 實驗結果與分析

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

4.2.1 鏈接預測

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

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

Table 2 Link prediction experiments comparison of each model

4.2.2 節點分類

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

從表3中可以看出，本文的NC-GAN模型在節點分類上的性能明顯優于其他圖表示學習模型。LINE 模型注重鄰接節點的相似度，不考慮節點連接信息，得到的節點分類效果較差。Struc2Vec模型更關注于節點之間結構的相似度，得到的節點分類效果差強人意。DeepWalk和node2vec更關注于節點之間的連接信息，忽略了節點本身所蘊含的信息，導致節點分類的效果不是很理想。而GraphGAN則是更偏向于獲得更加擬合真實連通性的分布，而不是更好地對節點進行區分。

Table 3 Comparison of node classification experiments among learning models

根據圖1所示對比結果，本文的NC-GAN模型所生成的特征矩陣，在經過邏輯回歸計算分類后，所得的準確率比圖卷積網絡模型得到的分類準確率和GraphGAN模型經過邏輯回歸得到的準確率都要高。由此可以看出，本文設計的模型在GraphGAN模型的基礎上，對于節點分類來說更進了一步。

Figure 1 Node classification experiments comparison with graph convolutional networks

5 結束語

為了解決傳統節點分類方法存在的問題，本文引入生成對抗網絡。生成對抗網絡通過生成模型和判別模型之間的二元博弈來生成所需的數據。GraphGAN模型將生成對抗網絡引入圖網絡中，用于生成擬合真實連通性分布的數據，但由于過于重視節點之間的連接信息，沒有考慮節點之間的關系，節點分類效果在對比模型中沒有達到最好。本文在該模型的基礎上考慮了節點之間的相似度，用相似度來代替節點之間的連接信息，使得生成的節點表示更有利于節點分類。實驗結果也表明，本文的模型在節點分類的效果上優于其他對比模型。