融合圖卷積網(wǎng)絡(luò)模型的無監(jiān)督社區(qū)檢測算法

姜東明，楊火根

江西理工大學(xué) 理學(xué)院，江西 贛州 341000

1 引言

近年來，深度學(xué)習(xí)方法在解決諸如圖像目標(biāo)識別、語音識別和自然語言處理等很多問題方面都表現(xiàn)出色。在各種類型的神經(jīng)網(wǎng)絡(luò)當(dāng)中，卷積神經(jīng)網(wǎng)絡(luò)[1]是當(dāng)下研究的熱點(diǎn)之一。但卷積神經(jīng)網(wǎng)絡(luò)的使用目前只局限在具有歐幾里德結(jié)構(gòu)的數(shù)據(jù)，原因是歐幾里德結(jié)構(gòu)數(shù)據(jù)具有“平移不變性”的特點(diǎn)，如語音（1維）和圖像（2維）數(shù)據(jù)。然而實(shí)際上，很多重要的現(xiàn)實(shí)世界數(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]是為了實(shí)現(xiàn)在非歐式距離結(jié)構(gòu)數(shù)據(jù)上使用卷積神經(jīng)網(wǎng)絡(luò)的特征提取分類器模型，可以理解為圖結(jié)構(gòu)數(shù)據(jù)上的卷積操作，彌補(bǔ)了傳統(tǒng)神經(jīng)網(wǎng)絡(luò)很難直接對非歐式距離的數(shù)據(jù)進(jìn)行特征提取的不足。不同結(jié)構(gòu)的卷積分類器對比如圖1 所示。目前主要的圖卷積神經(jīng)網(wǎng)絡(luò)定義可分為空域（spatial domain）[5]和頻域（spectral domain）[6]兩種。空域主要通過對提取高維圖數(shù)據(jù)的空間特征并對其進(jìn)行操作，例如：鄰居節(jié)點(diǎn)的順序選擇[7]，和圖中缺失邊的猜測[8]。頻域則借助于圖拉普拉斯（Laplacian）矩陣的特征值和特征向量來研究圖的性質(zhì)[9]，即對圖結(jié)構(gòu)中某些特定節(jié)點(diǎn)進(jìn)行卷積操作，使用包含拉普拉斯算子的特殊分類器進(jìn)行參數(shù)共享，來完成局部的特征提取。該種圖卷積網(wǎng)絡(luò)已經(jīng)在半監(jiān)督學(xué)習(xí)任務(wù)中取得了良好效果[10]。

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

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

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

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

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

定義圖數(shù)據(jù)格式為G=(V,E)，其中V={v1,v2,…,vn}表示圖中節(jié)點(diǎn)的集合，E是圖中邊的集合。則圖G可以表示為一個(gè)大小為N×N的鄰接矩陣A，若節(jié)點(diǎn)i與點(diǎn)j之間有邊相連，則Aij=1。反之，若沒有邊相連，則Aij=0。鄰接矩陣是圖的拓?fù)湫畔⒃诰仃囆问街械拇硇悦枋?。將矩陣每行的元素求和就得到該?jié)點(diǎn)的度，即從該節(jié)點(diǎn)出發(fā)有幾條邊與其他節(jié)點(diǎn)相連，表示為Di=。

可以將在圖上的卷積操作可以定義為一個(gè)多維信號x,x∈ ?N和一個(gè)帶有參數(shù)θ的分類器gθ,θ∈ ?N在傅里葉領(lǐng)域的乘積。Y表示正則化拉普拉斯矩，因?yàn)槔绽咕仃嚲哂刑厥獾奶卣鞣纸庑问剑篖=UΛUT,Λ是有拉普拉斯矩陣特征值組成的對角矩陣，則這個(gè)輸入信號的卷積形式可以表示為：

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

其中，D=diag(Di),IN是大小為節(jié)點(diǎn)數(shù)量N的單位矩陣。而可以進(jìn)一步簡化為其中A?=A+IN。通過卷積核（分類器）與輸入信號的卷積，便可以實(shí)現(xiàn)在圖結(jié)構(gòu)數(shù)據(jù)上的局部參數(shù)共享。對于監(jiān)督學(xué)習(xí)的預(yù)測和分類任務(wù)而言，參數(shù)共享的結(jié)果可以是判斷輸入數(shù)據(jù)特征與分類器的相似程度，而對于無監(jiān)督學(xué)習(xí)任務(wù)，由于節(jié)點(diǎn)本身不存在特征信息，所以文中使用人工標(biāo)簽來模擬需要共享的參數(shù)，這個(gè)人工標(biāo)簽在周圍鄰居不存在標(biāo)簽的情況下進(jìn)行參數(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)督學(xué)習(xí)中數(shù)據(jù)只有部分節(jié)點(diǎn)含有標(biāo)簽，所以在圖上的輸入信號x直接使用帶有原始標(biāo)簽的節(jié)點(diǎn)表示。通過卷積操作便可以將節(jié)點(diǎn)標(biāo)簽共享到其他不存在標(biāo)簽的節(jié)點(diǎn)上，之后通過訓(xùn)練權(quán)重參數(shù)來完成分類或預(yù)測任務(wù)。

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

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

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

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

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

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

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

因?yàn)镈是以節(jié)點(diǎn)的度組成的對角矩陣，所以簡化上式可得：

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

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

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

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

具體步驟如下：

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

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

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

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

因?yàn)樵诒疚乃惴ㄖ械臉?biāo)簽是依靠節(jié)點(diǎn)的鄰接矩陣進(jìn)行傳播的，所以圖中度值大的節(jié)點(diǎn)最容易將人工標(biāo)簽信息擴(kuò)散。同樣，這樣的節(jié)點(diǎn)在現(xiàn)實(shí)世界網(wǎng)絡(luò)中也往往是圖結(jié)構(gòu)網(wǎng)絡(luò)的組織者或是有重要影響的節(jié)點(diǎn)。且度較大的節(jié)點(diǎn)在運(yùn)算中會(huì)保留較小的標(biāo)簽值，若作為被傳播節(jié)點(diǎn)很容易保留從擁有較小度的節(jié)點(diǎn)傳遞來的標(biāo)簽值。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4.1 連通圖數(shù)據(jù)實(shí)驗(yàn)

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

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

在現(xiàn)實(shí)世界的數(shù)據(jù)中作為組織者的節(jié)點(diǎn)根據(jù)其重要性及影響力自然會(huì)擁有最多的度，算法使用第一種初始化方法來選擇初始節(jié)點(diǎn)，即選擇節(jié)點(diǎn){0}與節(jié)點(diǎn){33}作為初始節(jié)點(diǎn)。劃分結(jié)果在運(yùn)行第四層GCN 傳播規(guī)則時(shí)達(dá)到最優(yōu)值。圖4 中可以明顯看出：相比于原圖3中的節(jié)點(diǎn)屬性，本文算法將節(jié)點(diǎn){8，2}歸為officer 社區(qū)，原因是其與初始設(shè)定的標(biāo)簽節(jié)點(diǎn){33}直接有邊相連，而節(jié)點(diǎn){0}則沒有邊與其直接相連。社區(qū)劃分的模塊度與NMI評價(jià)指標(biāo)如表2所示。結(jié)果表明GCN 社區(qū)檢測算法在處理抽象的現(xiàn)實(shí)世界網(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 個(gè)社區(qū)，如圖5 所示。模塊度Q會(huì)隨著圖卷積網(wǎng)絡(luò)的層數(shù)而增加，社區(qū)劃分效果會(huì)隨著模塊度Q的變化很快達(dá)到峰值，隨后出現(xiàn)一定波動(dòng)，最后模塊度在第7 層以后有所下降。原因是過多的圖卷積層會(huì)使得標(biāo)簽數(shù)據(jù)過擬合，會(huì)使那些度較小節(jié)點(diǎn)的標(biāo)簽傳播到不該傳播的地方，破壞了原有的社區(qū)結(jié)構(gòu)，使原本的劃分標(biāo)簽被某一種標(biāo)簽替代。在發(fā)生過擬合的情況時(shí)不僅可能達(dá)不到預(yù)先要求的劃分?jǐn)?shù)量，而且還會(huì)失去圖中之前良好的社區(qū)劃分結(jié)構(gòu)，從而減小社區(qū)評價(jià)指標(biāo)的值。

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

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

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

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

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

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

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

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

4.2 不連通圖數(shù)據(jù)實(shí)驗(yàn)

蛋白質(zhì)相互作用數(shù)據(jù)集是對芽酵母菌中的蛋白質(zhì)相互進(jìn)行檢測并記錄觀察得到的數(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ù)才是真正需要分析和計(jì)算的。然而譜聚類算法卻無法達(dá)到此效果，因?yàn)樽V聚類算法使用的特征向量空間會(huì)優(yōu)先聚類圖中周邊的節(jié)點(diǎn)。如圖8（a）所示。這樣的劃分結(jié)果很明顯地破壞了圖結(jié)構(gòu)原本所具有的社區(qū)結(jié)構(gòu)，劃分的社區(qū)都在圖結(jié)構(gòu)的邊緣。之后的模塊度數(shù)據(jù)也說明了這一點(diǎn)。而本文提出GCN 算法則可以直接對圖中的中心數(shù)據(jù)進(jìn)行社區(qū)劃分，原因是GCN 算法使用鄰接矩陣參與運(yùn)算實(shí)現(xiàn)標(biāo)簽的傳遞，那些圖中的邊緣節(jié)點(diǎn)由于不與圖結(jié)構(gòu)中的主要部分連通，所以都劃分成一個(gè)社區(qū)，如圖8（b）所示。對于這樣節(jié)點(diǎn)分布不均勻且不連通的數(shù)據(jù)集，只有對該圖數(shù)據(jù)的中心節(jié)點(diǎn)進(jìn)行社區(qū)劃分，才可以從劃分結(jié)果中獲得有效的數(shù)據(jù)。這樣的劃分結(jié)果才具有實(shí)際意義。

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

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

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

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

5 結(jié)束語

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

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