姜東明，楊火根

江西理工大學 理學院，江西 贛州 341000

1 引言

近年來，深度學習方法在解決諸如圖像目標識別、語音識別和自然語言處理等很多問題方面都表現(xiàn)出色。在各種類型的神經(jīng)網(wǎng)絡(luò)當中，卷積神經(jīng)網(wǎng)絡(luò)[1]是當下研究的熱點之一。但卷積神經(jīng)網(wǎng)絡(luò)的使用目前只局限在具有歐幾里德結(jié)構(gòu)的數(shù)據(jù)，原因是歐幾里德結(jié)構(gòu)數(shù)據(jù)具有“平移不變性”的特點，如語音（1維）和圖像（2維）數(shù)據(jù)。然而實際上，很多重要的現(xiàn)實世界數(shù)據(jù)都是以高維圖結(jié)構(gòu)數(shù)據(jù)和網(wǎng)絡(luò)圖[2]的形式出現(xiàn)，比如社交網(wǎng)絡(luò)、知識圖譜、蛋白質(zhì)相互作用網(wǎng)絡(luò)、萬維網(wǎng)等非歐式距離結(jié)構(gòu)數(shù)據(jù)，這類數(shù)據(jù)往往無法直接被卷積神經(jīng)網(wǎng)絡(luò)的分類器模型處理[3]。

圖卷積神經(jīng)網(wǎng)絡(luò)[4]是為了實現(xiàn)在非歐式距離結(jié)構(gòu)數(shù)據(jù)上使用卷積神經(jīng)網(wǎng)絡(luò)的特征提取分類器模型，可以理解為圖結(jié)構(gòu)數(shù)據(jù)上的卷積操作，彌補了傳統(tǒng)神經(jīng)網(wǎng)絡(luò)很難直接對非歐式距離的數(shù)據(jù)進行特征提取的不足。不同結(jié)構(gòu)的卷積分類器對比如圖1 所示。目前主要的圖卷積神經(jīng)網(wǎng)絡(luò)定義可分為空域（spatial domain）[5]和頻域（spectral domain）[6]兩種?？沼蛑饕ㄟ^對提取高維圖數(shù)據(jù)的空間特征并對其進行操作，例如：鄰居節(jié)點的順序選擇[7]，和圖中缺失邊的猜測[8]。頻域則借助于圖拉普拉斯（Laplacian）矩陣的特征值和特征向量來研究圖的性質(zhì)[9]，即對圖結(jié)構(gòu)中某些特定節(jié)點進行卷積操作，使用包含拉普拉斯算子的特殊分類器進行參數(shù)共享，來完成局部的特征提取。該種圖卷積網(wǎng)絡(luò)已經(jīng)在半監(jiān)督學習任務(wù)中取得了良好效果[10]。

圖1 不同數(shù)據(jù)結(jié)構(gòu)中的提取特征分類器模型

圖是抽象數(shù)據(jù)（節(jié)點）的集合，它們之間的關(guān)系表示為拓撲結(jié)構(gòu)?；趫D的“小世界”理論[11]，圖中的數(shù)據(jù)可能包含某些小組結(jié)構(gòu)信息，在小組中的節(jié)點連接通常非常緊密，而小組之間的聯(lián)系相對稀疏。這樣的小組結(jié)構(gòu)被稱為社區(qū)[12]或簇，如何找到這些社區(qū)，是社區(qū)檢測的重要任務(wù)[13]。需要通過這些社區(qū)來對圖結(jié)構(gòu)數(shù)據(jù)提取信息并學習經(jīng)驗，圖中每一個社區(qū)都應(yīng)該包含對應(yīng)的節(jié)點和邊的特征信息。對應(yīng)的社區(qū)劃分算法[14-16]又根據(jù)其是否使用輸入數(shù)據(jù)的原始標簽作為數(shù)據(jù)的劃分依據(jù)分為監(jiān)督學習算法和無監(jiān)督學習算法，監(jiān)督學習算法要求算法的結(jié)果擁有預(yù)測作用，可將具有同樣屬性的數(shù)據(jù)劃分到已知的類別中達到分類效果，而無監(jiān)督學習算法對輸出結(jié)果沒有特定要求，算法的目的是在數(shù)據(jù)中尋找潛在的模式或結(jié)構(gòu)。所以社區(qū)劃分算法度量要求也有很多種，例如K-means算法[17]是通過節(jié)點的空間距離進行社區(qū)劃分，對輸入數(shù)據(jù)要求較為具體且分類結(jié)果固定。往往不適用于高維度結(jié)構(gòu)的數(shù)據(jù)和動態(tài)網(wǎng)絡(luò)圖；K-L算法[18]，通過將圖結(jié)構(gòu)數(shù)據(jù)分割成若干個子集的方式尋找社區(qū)，這種方式需要預(yù)先給出每個社區(qū)的數(shù)量，這種需要較強先驗知識的算法在沒有標簽的數(shù)據(jù)集中效果較差；譜聚類[19]算法，使用圖的鄰接矩陣作為輸入，這種使用拓撲結(jié)構(gòu)數(shù)據(jù)進行劃分的算法在現(xiàn)實世界的抽象數(shù)據(jù)集中更加適用。比如社交網(wǎng)絡(luò)和路由器拓撲網(wǎng)絡(luò)[20]。在此類圖結(jié)構(gòu)數(shù)據(jù)中若圖中兩個節(jié)點之間有邊連接，那么盡管兩個節(jié)點之間的距離很遠或空間相似度很低，這兩個節(jié)點相比于其他的節(jié)點也具有更強的關(guān)系。但是，因其需要計算拉普拉斯矩陣并特征分解后再進行聚類劃分，所以算法的復(fù)雜度極高。

本文結(jié)合圖卷積網(wǎng)絡(luò)分類器實現(xiàn)的“參數(shù)共享”的性質(zhì)以及社區(qū)檢測的定義，提出一種基于圖卷積網(wǎng)絡(luò)模型的無監(jiān)督社區(qū)檢測算法。算法基于圖數(shù)據(jù)的拓撲結(jié)構(gòu)進行劃分，通過模擬在圖上的信號卷積過程，使被標記標簽的節(jié)點可以將自身的標簽順序傳遞到其他鄰居節(jié)點上。這樣不僅保留了圖的拓撲結(jié)構(gòu)的信息，也符合社會學中的信息傳播規(guī)則[21]，更適用于現(xiàn)實世界中的數(shù)據(jù)。接下來會對圖卷積網(wǎng)絡(luò)如何應(yīng)用到社區(qū)檢測模型進行詳細介紹，并使用改進后的圖卷積網(wǎng)絡(luò)模型進行社區(qū)檢測，最后將算法應(yīng)用到幾個現(xiàn)實世界數(shù)據(jù)集中，對實驗結(jié)果進行了對比和分析。

2 圖卷積網(wǎng)絡(luò)（GCN）模型與適用性改進

2.1 圖卷積網(wǎng)絡(luò)的傳播規(guī)則

定義圖數(shù)據(jù)格式為G=(V,E)，其中V={v1,v2,…,vn}表示圖中節(jié)點的集合，E是圖中邊的集合。則圖G可以表示為一個大小為N×N的鄰接矩陣A，若節(jié)點i與點j之間有邊相連，則Aij=1。反之，若沒有邊相連，則Aij=0。鄰接矩陣是圖的拓撲信息在矩陣形式中的代表性描述。將矩陣每行的元素求和就得到該節(jié)點的度，即從該節(jié)點出發(fā)有幾條邊與其他節(jié)點相連，表示為Di=。

可以將在圖上的卷積操作可以定義為一個多維信號x,x∈ ?N和一個帶有參數(shù)θ的分類器gθ,θ∈ ?N在傅里葉領(lǐng)域的乘積。Y表示正則化拉普拉斯矩，因為拉普拉斯矩陣具有特殊的特征分解形式：L=UΛUT,Λ是有拉普拉斯矩陣特征值組成的對角矩陣，則這個輸入信號的卷積形式可以表示為：

?表示卷積過程，gθ′(L)是一個含有拉普拉斯特征值的函數(shù)，由于上式的計算復(fù)雜度較高，Kipf 等人[22]根據(jù)使用切比雪夫多項式擬合來簡化其復(fù)雜度，使：gθ′(L)≈其中Tk代表k階切比雪夫多項式，并取k=1。θ為切比雪夫系數(shù)。最終得到的圖卷積網(wǎng)絡(luò)的卷積形式為：

其中，D=diag(Di),IN是大小為節(jié)點數(shù)量N的單位矩陣。而可以進一步簡化為其中A?=A+IN。通過卷積核（分類器）與輸入信號的卷積，便可以實現(xiàn)在圖結(jié)構(gòu)數(shù)據(jù)上的局部參數(shù)共享。對于監(jiān)督學習的預(yù)測和分類任務(wù)而言，參數(shù)共享的結(jié)果可以是判斷輸入數(shù)據(jù)特征與分類器的相似程度，而對于無監(jiān)督學習任務(wù)，由于節(jié)點本身不存在特征信息，所以文中使用人工標簽來模擬需要共享的參數(shù)，這個人工標簽在周圍鄰居不存在標簽的情況下進行參數(shù)共享操作，反觀就是一種參數(shù)傳播過程。

于是，可以定義圖上的信號傳播模型為：

其中，H(l+1)表示圖卷積網(wǎng)絡(luò)中第l+1 層的參數(shù)，H(0)=x,x是在圖上的信號，A是圖的鄰接矩陣，f(?,?)是圖卷積網(wǎng)絡(luò)分類器與信號的卷積形式。結(jié)合上文的卷積公式可以得到可以直接應(yīng)用于分類任務(wù)的圖卷積網(wǎng)絡(luò)的信號傳播規(guī)則，即：

公式（4）常被用在半監(jiān)督算法中，由于半監(jiān)督學習中數(shù)據(jù)只有部分節(jié)點含有標簽，所以在圖上的輸入信號x直接使用帶有原始標簽的節(jié)點表示。通過卷積操作便可以將節(jié)點標簽共享到其他不存在標簽的節(jié)點上，之后通過訓練權(quán)重參數(shù)來完成分類或預(yù)測任務(wù)。

2.2 圖卷積網(wǎng)絡(luò)模型的無監(jiān)督改進

本節(jié)對圖卷積網(wǎng)絡(luò)的傳播規(guī)則進行適用性改進，使其可以適用于無監(jiān)督的社區(qū)劃分領(lǐng)域中[23]。圖卷積網(wǎng)絡(luò)目前在監(jiān)督學習任務(wù)中使用完全隨機的權(quán)重W參與運算，通過訓練調(diào)整權(quán)重值，得到最優(yōu)模型后預(yù)測分類結(jié)果。而本文的社區(qū)檢測算法處理的是不存在原始標簽的數(shù)據(jù)，屬于無監(jiān)督學習，每個節(jié)點默認擁有相同的屬性。這意味著每個節(jié)點對這個圖結(jié)構(gòu)數(shù)據(jù)的貢獻度相同，相對于其他算法來說更著重考慮圖數(shù)據(jù)的拓撲結(jié)構(gòu)。因此，這里使用固定相同權(quán)重取代權(quán)重訓練，以確保社區(qū)劃分效果只與圖網(wǎng)絡(luò)的拓撲結(jié)構(gòu)有關(guān)。由于權(quán)重值大小本質(zhì)上不影響社區(qū)劃分結(jié)果，為方便計算，令權(quán)重值均為1。實際上，對于不需要訓練優(yōu)化函數(shù)或輸入數(shù)據(jù)性質(zhì)相同的模型，權(quán)重固定具有合理性，也可減小計算復(fù)雜度。

基于此，本文將圖卷積網(wǎng)絡(luò)傳播規(guī)則（4）修改如下：

又因為沒有標簽的數(shù)據(jù)無法通過自身信息模擬輸入信號。所以在這里，首先需要通過標記圖中的某些特定節(jié)點來模擬在圖上的輸入信號x，算法中可以表示為圖的輸入信號：x=N×C,N為節(jié)點數(shù)目，C表示聚類的個數(shù)。其次，通過算法中給出的方法選取模擬信號的初始點后，最后使用本文改進的圖卷積網(wǎng)絡(luò)傳播規(guī)則對其進行參數(shù)共享。

令Vi為初始信號節(jié)點，其信號值為Xi,Vj為其一階鄰居節(jié)點。這里定義X的聚合為節(jié)點i處的信號值與其一階鄰居節(jié)點j的和的平均，即：

基于上述聚合定義，對圖卷積網(wǎng)絡(luò)傳播規(guī)則的參數(shù)共享過程作如下解釋：

將本文的傳播規(guī)則公式（5），改寫為信號值與圖卷積網(wǎng)絡(luò)分類器在節(jié)點i聚合的形式：

因為D是以節(jié)點的度組成的對角矩陣，所以簡化上式可得：

由式（7）可知，有人工標簽?zāi)M的信號通過本文修改的圖卷積網(wǎng)絡(luò)傳播規(guī)則實現(xiàn)參數(shù)共享。參數(shù)共享的本質(zhì)其實可以理解為是一種加權(quán)平均，因為在無監(jiān)督學習任務(wù)中。輸入數(shù)據(jù)是不存在原始標簽的，所以節(jié)點的人工標簽與不存在標簽的鄰居節(jié)點的加權(quán)平均的參數(shù)共享方式就可以看作是一種標簽傳遞過程。傳播的有效信息值為人工標簽的加權(quán)平均，其權(quán)重與節(jié)點及其一階鄰居節(jié)點的度（拓撲結(jié)構(gòu)信息）相關(guān)，有效信息的加權(quán)平均共享過程如圖2 所示。對于不需要訓練且輸入數(shù)據(jù)屬性相同的情況，固定權(quán)重可以確保信息傳遞只與圖的拓撲結(jié)構(gòu)相關(guān)，因此在輸入的鄰接矩陣不變的情況下，可以保證信息傳遞的準確性。模擬信號節(jié)點的人工標簽以此方式擴散，每一次傳播一階鄰居節(jié)點，也可以理解為輸入信號x在圖中的拉普拉斯平滑[24]。又因為社區(qū)檢測算法的目的就是在圖結(jié)構(gòu)數(shù)據(jù)中尋找內(nèi)部有強相關(guān)性的社區(qū)，所以這種根據(jù)節(jié)點及其鄰居拓撲結(jié)構(gòu)之間信息傳遞的劃分方式，自然會有更好的結(jié)果。而且這種根據(jù)節(jié)點的拓撲結(jié)構(gòu)傳遞標簽方式與社會學中的信息傳播方式十分類似，因此依照此方法劃分的社區(qū)結(jié)構(gòu)也理應(yīng)具有更真實的社會性質(zhì)。

圖2 一次加權(quán)平均的參數(shù)共享過程

3 基于圖卷積網(wǎng)絡(luò)的無監(jiān)督社區(qū)檢測算法

基于改進后的圖卷積神經(jīng)網(wǎng)絡(luò)的傳播規(guī)則（5），本章分四步實現(xiàn)無監(jiān)督社區(qū)檢測算法。整個算法的偽代碼如算法1所示。

具體步驟如下：

步驟1圖數(shù)據(jù)的初始化和對模擬信號節(jié)點的選擇。

算法首先需要處理輸入的數(shù)據(jù)，即：劃分社區(qū)數(shù)量，GCN 層數(shù)和圖結(jié)構(gòu)數(shù)據(jù)集。其次算法要對給予的圖數(shù)據(jù)參數(shù)化，根據(jù)圖中的節(jié)點之間的關(guān)系計算算法所需的鄰接矩陣A，并通過鄰接矩陣計算的度矩陣D。

又根據(jù)節(jié)點數(shù)量生成單位矩陣IN，分別與鄰接矩陣和度矩陣相加之后便可得到A?和D?。在對圖數(shù)據(jù)完成初始化操作之后便可以根據(jù)輸入劃分數(shù)量選擇初始點并為其添加人工標簽來模擬輸入信號。初始點的選取在本社區(qū)劃分算法中尤為重要，作為初始標簽的攜帶者，初始點在一定程度上決定了最后社區(qū)劃分的結(jié)果。本文提出兩種初始點的選擇方法：

（1）按需求劃分個數(shù)依次選取圖中度最大的節(jié)點，即：initial_node=max( )D。

因為在本文算法中的標簽是依靠節(jié)點的鄰接矩陣進行傳播的，所以圖中度值大的節(jié)點最容易將人工標簽信息擴散。同樣，這樣的節(jié)點在現(xiàn)實世界網(wǎng)絡(luò)中也往往是圖結(jié)構(gòu)網(wǎng)絡(luò)的組織者或是有重要影響的節(jié)點。且度較大的節(jié)點在運算中會保留較小的標簽值，若作為被傳播節(jié)點很容易保留從擁有較小度的節(jié)點傳遞來的標簽值。

（2）結(jié)合度和圖中最遠跳躍數(shù)來選擇初始節(jié)點。如算法1.1所示。

考慮到在某些圖中最大度的節(jié)點可能會聚集在整個圖邊緣或圖中一些不重要的位置。所以初始點的選擇要結(jié)合圖中節(jié)點的度和兩節(jié)點之間的深度，即一個節(jié)點到另一個節(jié)點之間的最短路徑。算法首先在圖中找出最遠的節(jié)點距離，然后在距離最遠的節(jié)點中隨機選擇其中一個節(jié)點作為最遠路徑的開始節(jié)點。然后在相鄰兩階的節(jié)點之中選擇出度最大的節(jié)點，因為每運行一次GCN 模型只對節(jié)點的一階鄰居節(jié)點參數(shù)共享，所以選擇初始標簽節(jié)點時要求距離盡量大于2。使用這樣的方式選擇初始節(jié)點，能有效避免在劃分大量社區(qū)時發(fā)生的不同社區(qū)覆蓋的現(xiàn)象。

步驟2應(yīng)用圖神經(jīng)網(wǎng)絡(luò)的傳播規(guī)則，使節(jié)點信息得以有效擴散。

根據(jù)上一階段生成的模擬信號矩陣，結(jié)合GCN 的傳播規(guī)則，含有自定義標簽的節(jié)點就可以將其本身攜帶的標簽通過加權(quán)平均的方式傳遞出去，讓沒有標簽的節(jié)點擁有標簽。因為公式（4）中使用一階切比雪夫多項式簡化，所以節(jié)點標簽每次傳遞范圍為節(jié)點的一階鄰居。第一次傳播時使用模擬信號的初始節(jié)點矩陣，之后每次傳播會使用上次一次傳播后得到的結(jié)果矩陣，如此循環(huán)直到達到輸入要求層數(shù)。

步驟3計算結(jié)果歸類及對歸類結(jié)果的優(yōu)化與分析。

因每運行一次圖卷積網(wǎng)絡(luò)的傳播規(guī)則后，節(jié)點會接收一個或多個確定的包含了拓撲結(jié)構(gòu)有效信息加權(quán)平均值，所以在完成節(jié)點標簽的傳播過程后，同一節(jié)點難免會擁有多個不同標簽。對于每一個節(jié)點來說，這個值在每一層傳播后會逐層累加。所以在計算歸類結(jié)果時，算法會選擇節(jié)點獲得的標簽中最大的值作為社區(qū)劃分的標準。這樣不僅可以保證讓最先獲得有效信息的鄰居節(jié)點在每次傳播中依然保持其原有劃分，而且也讓傳播過程更符合信息傳播模型。但由于標簽值是根據(jù)節(jié)點拓撲結(jié)構(gòu)的加權(quán)平均傳播的，這樣可能會導致某些度很大的節(jié)點共享很小的標簽值，而度較小節(jié)點共享的標簽值較大。而算法通常選擇度較大的節(jié)點作為模擬信號的初始節(jié)點，在疊加多層卷積層后這個初始節(jié)點剩余的標簽值有可能會小于從度較小節(jié)點傳播來的標簽值，這樣就會導致度較大的初始節(jié)點被錯誤劃分到平均度較小的社區(qū)中。

算法1.2根據(jù)以上劃分異常情況進行優(yōu)化。優(yōu)化目標是將該節(jié)點回歸正確的社區(qū)，優(yōu)化方式類似標簽傳播算法[25]，即依次判斷每個節(jié)點相鄰節(jié)點的社區(qū)，隨后將節(jié)點加入其鄰居中數(shù)量最多的社區(qū)。優(yōu)化過程結(jié)合了其鄰居節(jié)點已經(jīng)從這個初始節(jié)點獲得的有效信息，并據(jù)此修改了這個初始節(jié)點在卷積層數(shù)較大時會選擇度較小節(jié)點的標簽而產(chǎn)生的錯誤社區(qū)劃分。

在多種不同圖數(shù)據(jù)上的實驗表明，這種錯誤劃分大多出現(xiàn)在選擇初始節(jié)點之間的度相差較大的社區(qū)中，而對于選擇的初始節(jié)點間度差別不大的情況，歸類結(jié)果一般與優(yōu)化后的劃分結(jié)果相同。優(yōu)化算法一般只改變度值較大的社區(qū)中心節(jié)點的劃分，社區(qū)內(nèi)鄰居節(jié)點及其他節(jié)點的劃分基本保持不變，因此優(yōu)化后節(jié)點劃分保持不變的節(jié)點與社區(qū)內(nèi)除中心節(jié)點外其他節(jié)點所占該社區(qū)節(jié)點總數(shù)的比例大致相當。

步驟4計算社區(qū)劃分結(jié)果的評價指標模塊度Q。

在將擁有多個標簽的節(jié)點進行歸類并優(yōu)化后，算法的輸出矩陣就可以被轉(zhuǎn)化成節(jié)點與其對應(yīng)社區(qū)的矩陣。進而可以評估算法計算的社區(qū)劃分效果。

社區(qū)劃分評價指標[26]，最早由Newman 等人提出，用來衡量一個劃分的好壞程度。其形式為：

式中的評價指標有N個節(jié)點，并且已經(jīng)將這些節(jié)點劃分為了n個社區(qū)，節(jié)點彼此之間共有m個連接，則2m就是整個圖中全部的度。i和j是圖中的任意兩個節(jié)點，當兩個節(jié)點直接相連時Aij=1，否則Aij=0。ki代表的是節(jié)點i的度，δ(ci,cj)是克羅地亞函數(shù)，是用來判斷節(jié)點V和W是否在同一個社區(qū)內(nèi)，當節(jié)點在同一個社區(qū)內(nèi)時δ(ci,cj)=1，否則δ(ci,cj)=0。模塊度越大則表明社區(qū)劃分效果越好。Q的取值為[-0.5,1]，其論文表示當Q值在0.3～0.7 之間時，說明聚類的效果很好。所以大部分社區(qū)劃分算法的目標都是盡量提高模塊度Q。

在得到上階段對應(yīng)的社區(qū)劃分結(jié)果后，算法會首先檢查劃分數(shù)量是否達到預(yù)先設(shè)定的社區(qū)數(shù)量，判斷是否出現(xiàn)過擬合的社區(qū)覆蓋現(xiàn)象。算法在達到指定GCN 層數(shù)或在未指定層數(shù)的情況下自動運行6 次卷積層后停止并計算社區(qū)劃分所得模塊度Q，與整個算法的運行時間。最后算法將劃分結(jié)果繪圖并顯示出來，以更直觀的方式比較社區(qū)劃分結(jié)果。

4 實驗與結(jié)果分析

為了客觀全面地評價聚類效果以及對算法的適用性進行分析，本文實驗選用一些經(jīng)典且被廣泛使用的現(xiàn)實世界數(shù)據(jù)集進行算法效果對比。選用的對比方法有：基于層次聚類的GN 算法[2]，經(jīng)典的K-means 聚類算法，和同樣使用拉普拉斯矩陣進行劃分的譜聚類算法以及基于特征樹的BIRCH 算法[27]。選用的數(shù)據(jù)集如表1所示。

表1 算法選用的數(shù)據(jù)集信息

4.1 連通圖數(shù)據(jù)實驗

4.1.1 空手道俱樂部網(wǎng)絡(luò)圖

空手道俱樂部作為現(xiàn)實世界的社交網(wǎng)絡(luò)且?guī)в性紭撕灥臄?shù)據(jù)集，算法的社區(qū)檢測結(jié)果理應(yīng)更加貼近原始社區(qū)劃分（圖3）給出的實際結(jié)果。于是在這個帶有原始標簽的數(shù)據(jù)集中，可以介紹另一種社區(qū)檢測評估方法：歸一化信息[31]（Normalized Mutual Information，NMI），用于計算實際劃分與算法計算劃分之間的相似性。NMI的值越大，表示與數(shù)據(jù)集中的原始分區(qū)和社區(qū)結(jié)構(gòu)越相似。

在現(xiàn)實世界的數(shù)據(jù)中作為組織者的節(jié)點根據(jù)其重要性及影響力自然會擁有最多的度，算法使用第一種初始化方法來選擇初始節(jié)點，即選擇節(jié)點{0}與節(jié)點{33}作為初始節(jié)點。劃分結(jié)果在運行第四層GCN 傳播規(guī)則時達到最優(yōu)值。圖4 中可以明顯看出：相比于原圖3中的節(jié)點屬性，本文算法將節(jié)點{8，2}歸為officer 社區(qū)，原因是其與初始設(shè)定的標簽節(jié)點{33}直接有邊相連，而節(jié)點{0}則沒有邊與其直接相連。社區(qū)劃分的模塊度與NMI評價指標如表2所示。結(jié)果表明GCN 社區(qū)檢測算法在處理抽象的現(xiàn)實世界網(wǎng)絡(luò)數(shù)據(jù)有天然的優(yōu)勢，對于社交網(wǎng)絡(luò)和分子結(jié)構(gòu)數(shù)據(jù)也有很好的適用性。

圖3 空手道俱樂部圖的原始社區(qū)劃分

圖4 使用GCN區(qū)檢測算法的劃分結(jié)果

表2 不同算法的NMI和模塊度比較

4.1.2 悲慘世界網(wǎng)絡(luò)圖

為了比較不同圖卷積層數(shù)與模塊度的關(guān)系，先將悲慘世界人物網(wǎng)絡(luò)劃分成4 個社區(qū)，如圖5 所示。模塊度Q會隨著圖卷積網(wǎng)絡(luò)的層數(shù)而增加，社區(qū)劃分效果會隨著模塊度Q的變化很快達到峰值，隨后出現(xiàn)一定波動，最后模塊度在第7 層以后有所下降。原因是過多的圖卷積層會使得標簽數(shù)據(jù)過擬合，會使那些度較小節(jié)點的標簽傳播到不該傳播的地方，破壞了原有的社區(qū)結(jié)構(gòu)，使原本的劃分標簽被某一種標簽替代。在發(fā)生過擬合的情況時不僅可能達不到預(yù)先要求的劃分數(shù)量，而且還會失去圖中之前良好的社區(qū)劃分結(jié)構(gòu)，從而減小社區(qū)評價指標的值。

圖5 分類效果隨GCN層數(shù)變化效果圖

所以，如上文提到的，算法要盡量減少圖卷積網(wǎng)絡(luò)的層數(shù)。在一般情況下，少量的卷積層不會出現(xiàn)過擬合的現(xiàn)象，但過擬合現(xiàn)象同時也受到圖數(shù)據(jù)的深度和節(jié)點的數(shù)量約束。

圖6 是不同社區(qū)劃分數(shù)量對比其他類型的社區(qū)劃分算法的效果圖，實驗中圖卷積網(wǎng)絡(luò)的社區(qū)劃分結(jié)果是在同一劃分數(shù)量下運行5 層GCN 傳播規(guī)則，計算模塊度并取最優(yōu)值作為結(jié)果比較。如圖所示GCN 模型在整個社區(qū)劃分結(jié)果中相比其他算法均有一定的優(yōu)勢，在第5和第8 個劃分時略低于譜聚類算法劃分結(jié)果。相比于譜聚類使用拉普拉斯的特征空間進行劃分，本文算法可以直接使用圖數(shù)據(jù)的拓撲結(jié)構(gòu)進行劃分，在減少了算法復(fù)雜程度的同時也能保持較好的劃分效果。

圖6 悲慘世界人物圖的社區(qū)劃分結(jié)果對比圖

4.1.3 arXiv引文網(wǎng)絡(luò)圖

arXiv 數(shù)據(jù)集是來自其同名出版社1991 年至1993年電子出版的科學論文及其引文，節(jié)點與邊分別對應(yīng)每篇文章與它的引文。由于這個數(shù)據(jù)集中包含的節(jié)點數(shù)量較多，且圖的深度較大，在這里使用第二種方法選擇初始節(jié)點，并設(shè)定用來對比的社區(qū)劃分數(shù)量為18 至28。對于這類關(guān)系明確且節(jié)點數(shù)量龐大的數(shù)據(jù)集，使用鄰接矩陣作為輸入?yún)?shù)的算法會有一定的優(yōu)勢。因為使用空間坐標的社區(qū)檢測算法往往會丟失節(jié)點之間邊的信息，這樣的劃分結(jié)果往往會出現(xiàn)很多不穩(wěn)定的問題。另外，大多數(shù)高維數(shù)據(jù)的空間的坐標以及很多現(xiàn)實世界的抽象數(shù)據(jù)的坐標都無法直接獲得。

因此，這類數(shù)據(jù)對于譜聚類以及同樣使用鄰接矩陣作為輸入的GCN 社區(qū)檢測算法有著相對穩(wěn)定的結(jié)果，但區(qū)別在于前者使用鄰接矩陣和相似矩陣來計算拉普拉斯矩陣并對其進行特征分解，將節(jié)點抽象到高維空間后再進行劃分，而后者僅使用鄰接矩陣來計算標簽傳播規(guī)則，劃分本質(zhì)是標簽的傳播。而譜聚類又在面對社區(qū)之間節(jié)點數(shù)量差異過大時會出現(xiàn)劃分效果變差的情況。所以，如圖7所示，GCN 社區(qū)檢測算法擁有比譜聚類算法更好且穩(wěn)定的劃分。相對于其他算法本文算法在這個數(shù)據(jù)集中仍然有很明顯的優(yōu)勢。

圖7 arXiv引文網(wǎng)絡(luò)的社區(qū)劃分結(jié)果對比圖

4.2 不連通圖數(shù)據(jù)實驗

蛋白質(zhì)相互作用數(shù)據(jù)集是對芽酵母菌中的蛋白質(zhì)相互進行檢測并記錄觀察得到的數(shù)據(jù)。通過對觀察到的已知數(shù)據(jù)分析并尋找規(guī)律，仍是現(xiàn)今生物界發(fā)現(xiàn)新型蛋白質(zhì)的常用方法。這類數(shù)據(jù)往往屬于不連通的圖數(shù)據(jù)[32]。

圖8是蛋白質(zhì)相互作用網(wǎng)絡(luò)圖的圖像，由圖可見大部分蛋白質(zhì)聚集在圖結(jié)構(gòu)的中心區(qū)域，只有少量分布在中心周圍的其他區(qū)域，對于這樣的圖結(jié)構(gòu)數(shù)據(jù)，中心部分的數(shù)據(jù)才是真正需要分析和計算的。然而譜聚類算法卻無法達到此效果，因為譜聚類算法使用的特征向量空間會優(yōu)先聚類圖中周邊的節(jié)點。如圖8（a）所示。這樣的劃分結(jié)果很明顯地破壞了圖結(jié)構(gòu)原本所具有的社區(qū)結(jié)構(gòu)，劃分的社區(qū)都在圖結(jié)構(gòu)的邊緣。之后的模塊度數(shù)據(jù)也說明了這一點。而本文提出GCN 算法則可以直接對圖中的中心數(shù)據(jù)進行社區(qū)劃分，原因是GCN 算法使用鄰接矩陣參與運算實現(xiàn)標簽的傳遞，那些圖中的邊緣節(jié)點由于不與圖結(jié)構(gòu)中的主要部分連通，所以都劃分成一個社區(qū)，如圖8（b）所示。對于這樣節(jié)點分布不均勻且不連通的數(shù)據(jù)集，只有對該圖數(shù)據(jù)的中心節(jié)點進行社區(qū)劃分，才可以從劃分結(jié)果中獲得有效的數(shù)據(jù)。這樣的劃分結(jié)果才具有實際意義。

圖9 是本文介紹的四種算法在蛋白質(zhì)交互網(wǎng)絡(luò)中的社區(qū)評價指標模塊度對比，由于BIRCH 算法使用節(jié)點特征樹來計算社區(qū)劃分，對于非連通圖無法進行有效劃分，其模塊度低于譜聚類算法，故不在圖中進行對比。由圖可見本文使用的GCN 社區(qū)劃分算法在不同劃分數(shù)量上的模塊度Q都優(yōu)于其他算法。體現(xiàn)了GCN算法在特殊類型的圖數(shù)據(jù)上也依然有較好的適用性，有相對更廣泛的應(yīng)用空間。

圖8 蛋白質(zhì)相互作用網(wǎng)絡(luò)圖的社區(qū)劃分結(jié)果圖

4.3 算法復(fù)雜度分析

對GCN 社區(qū)檢測算法的時空復(fù)雜度進行分析，由于圖卷積網(wǎng)絡(luò)的社區(qū)劃分算法是使用圖的鄰接矩陣作為輸入，且整個運算過程幾乎不需要隨機選取數(shù)值，所以每層圖卷積層運行一次的時間復(fù)雜度可以簡化為O(n)。但是，正是因為由于算法使用鄰接矩陣(N×N)作為輸入，導致算法的空間復(fù)雜度較高O(n3)?？偠灾?，GCN 算法的核心就是矩陣相乘，相對于需要隨機和循環(huán)次數(shù)較多的GN 算法O(n2m)和K-means 算法O(mn)，其中m為用來計算的節(jié)點個數(shù)，以及BICRH 算法O(nlbn)也有一定的優(yōu)勢。而對于譜聚類算法，其在選取特征向量及特征值后還需要二次聚類，所以其理論時間復(fù)雜度是算法之中最高的。

5 結(jié)束語

本文提出了一種基于圖卷積網(wǎng)絡(luò)的社區(qū)檢測方法。將半監(jiān)督學習方法擴展到非監(jiān)督學習領(lǐng)域，在社區(qū)檢測中應(yīng)用圖卷積網(wǎng)絡(luò)模型卷積核高效的參數(shù)共享性質(zhì)，通過添加人工標簽的節(jié)點矩陣來模擬輸入信號，使用GCN 傳播規(guī)則通過加權(quán)平均傳遞標簽，然后比較節(jié)點接收到的每個標簽并將節(jié)點歸類。最后對歸類的數(shù)據(jù)進行優(yōu)化進而得到最終的社區(qū)劃分。

在不同類型的數(shù)據(jù)集進行了實驗，并與許多經(jīng)典的社區(qū)檢測算法進行了比較，結(jié)果表明本文算法比所比較的其他社區(qū)檢測算法具有更好的性能。而且由于圖卷積網(wǎng)絡(luò)傳播規(guī)則的性質(zhì)，該算法將更適合于現(xiàn)實世界的圖形數(shù)據(jù)集以及動態(tài)圖形數(shù)據(jù)。同時也發(fā)現(xiàn)卷積層過多會導致過度擬合的問題和某些節(jié)點劃分異常的情況。接下來的工作是尋找更好的初始點選擇方法，并解決劃分結(jié)果中可能出現(xiàn)某些節(jié)點劃分異常的情況，以及在社區(qū)劃分過程中考慮邊含有的信息，并提高社區(qū)檢測結(jié)果的準確性和檢測速度。