姜東明,楊火根
江西理工大學 理學院,江西 贛州 341000
近年來,深度學習方法在解決諸如圖像目標識別、語音識別和自然語言處理等很多問題方面都表現出色。在各種類型的神經網絡當中,卷積神經網絡[1]是當下研究的熱點之一。但卷積神經網絡的使用目前只局限在具有歐幾里德結構的數據,原因是歐幾里德結構數據具有“平移不變性”的特點,如語音(1維)和圖像(2維)數據。然而實際上,很多重要的現實世界數據都是以高維圖結構數據和網絡圖[2]的形式出現,比如社交網絡、知識圖譜、蛋白質相互作用網絡、萬維網等非歐式距離結構數據,這類數據往往無法直接被卷積神經網絡的分類器模型處理[3]。
圖卷積神經網絡[4]是為了實現在非歐式距離結構數據上使用卷積神經網絡的特征提取分類器模型,可以理解為圖結構數據上的卷積操作,彌補了傳統神經網絡很難直接對非歐式距離的數據進行特征提取的不足。不同結構的卷積分類器對比如圖1 所示。目前主要的圖卷積神經網絡定義可分為空域(spatial domain)[5]和頻域(spectral domain)[6]兩種。空域主要通過對提取高維圖數據的空間特征并對其進行操作,例如:鄰居節點的順序選擇[7],和圖中缺失邊的猜測[8]。頻域則借助于圖拉普拉斯(Laplacian)矩陣的特征值和特征向量來研究圖的性質[9],即對圖結構中某些特定節點進行卷積操作,使用包含拉普拉斯算子的特殊分類器進行參數共享,來完成局部的特征提取。該種圖卷積網絡已經在半監督學習任務中取得了良好效果[10]。

圖1 不同數據結構中的提取特征分類器模型
圖是抽象數據(節點)的集合,它們之間的關系表示為拓撲結構。基于圖的“小世界”理論[11],圖中的數據可能包含某些小組結構信息,在小組中的節點連接通常非常緊密,而小組之間的聯系相對稀疏。這樣的小組結構被稱為社區[12]或簇,如何找到這些社區,是社區檢測的重要任務[13]。需要通過這些社區來對圖結構數據提取信息并學習經驗,圖中每一個社區都應該包含對應的節點和邊的特征信息。對應的社區劃分算法[14-16]又根據其是否使用輸入數據的原始標簽作為數據的劃分依據分為監督學習算法和無監督學習算法,監督學習算法要求算法的結果擁有預測作用,可將具有同樣屬性的數據劃分到已知的類別中達到分類效果,而無監督學習算法對輸出結果沒有特定要求,算法的目的是在數據中尋找潛在的模式或結構。所以社區劃分算法度量要求也有很多種,例如K-means算法[17]是通過節點的空間距離進行社區劃分,對輸入數據要求較為具體且分類結果固定。往往不適用于高維度結構的數據和動態網絡圖;K-L算法[18],通過將圖結構數據分割成若干個子集的方式尋找社區,這種方式需要預先給出每個社區的數量,這種需要較強先驗知識的算法在沒有標簽的數據集中效果較差;譜聚類[19]算法,使用圖的鄰接矩陣作為輸入,這種使用拓撲結構數據進行劃分的算法在現實世界的抽象數據集中更加適用。比如社交網絡和路由器拓撲網絡[20]。在此類圖結構數據中若圖中兩個節點之間有邊連接,那么盡管兩個節點之間的距離很遠或空間相似度很低,這兩個節點相比于其他的節點也具有更強的關系。但是,因其需要計算拉普拉斯矩陣并特征分解后再進行聚類劃分,所以算法的復雜度極高。
本文結合圖卷積網絡分類器實現的“參數共享”的性質以及社區檢測的定義,提出一種基于圖卷積網絡模型的無監督社區檢測算法。算法基于圖數據的拓撲結構進行劃分,通過模擬在圖上的信號卷積過程,使被標記標簽的節點可以將自身的標簽順序傳遞到其他鄰居節點上。這樣不僅保留了圖的拓撲結構的信息,也符合社會學中的信息傳播規則[21],更適用于現實世界中的數據。接下來會對圖卷積網絡如何應用到社區檢測模型進行詳細介紹,并使用改進后的圖卷積網絡模型進行社區檢測,最后將算法應用到幾個現實世界數據集中,對實驗結果進行了對比和分析。
定義圖數據格式為G=(V,E),其中V={v1,v2,…,vn}表示圖中節點的集合,E是圖中邊的集合。則圖G可以表示為一個大小為N×N的鄰接矩陣A,若節點i與點j之間有邊相連,則Aij=1。反之,若沒有邊相連,則Aij=0。鄰接矩陣是圖的拓撲信息在矩陣形式中的代表性描述。將矩陣每行的元素求和就得到該節點的度,即從該節點出發有幾條邊與其他節點相連,表示為Di=。
可以將在圖上的卷積操作可以定義為一個多維信號x,x∈ ?N和一個帶有參數θ的分類器gθ,θ∈ ?N在傅里葉領域的乘積。Y表示正則化拉普拉斯矩,因為拉普拉斯矩陣具有特殊的特征分解形式:L=UΛUT,Λ是有拉普拉斯矩陣特征值組成的對角矩陣,則這個輸入信號的卷積形式可以表示為:

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

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

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

公式(4)常被用在半監督算法中,由于半監督學習中數據只有部分節點含有標簽,所以在圖上的輸入信號x直接使用帶有原始標簽的節點表示。通過卷積操作便可以將節點標簽共享到其他不存在標簽的節點上,之后通過訓練權重參數來完成分類或預測任務。
本節對圖卷積網絡的傳播規則進行適用性改進,使其可以適用于無監督的社區劃分領域中[23]。圖卷積網絡目前在監督學習任務中使用完全隨機的權重W參與運算,通過訓練調整權重值,得到最優模型后預測分類結果。而本文的社區檢測算法處理的是不存在原始標簽的數據,屬于無監督學習,每個節點默認擁有相同的屬性。這意味著每個節點對這個圖結構數據的貢獻度相同,相對于其他算法來說更著重考慮圖數據的拓撲結構。因此,這里使用固定相同權重取代權重訓練,以確保社區劃分效果只與圖網絡的拓撲結構有關。由于權重值大小本質上不影響社區劃分結果,為方便計算,令權重值均為1。實際上,對于不需要訓練優化函數或輸入數據性質相同的模型,權重固定具有合理性,也可減小計算復雜度。
基于此,本文將圖卷積網絡傳播規則(4)修改如下:

又因為沒有標簽的數據無法通過自身信息模擬輸入信號。所以在這里,首先需要通過標記圖中的某些特定節點來模擬在圖上的輸入信號x,算法中可以表示為圖的輸入信號:x=N×C,N為節點數目,C表示聚類的個數。其次,通過算法中給出的方法選取模擬信號的初始點后,最后使用本文改進的圖卷積網絡傳播規則對其進行參數共享。
令Vi為初始信號節點,其信號值為Xi,Vj為其一階鄰居節點。這里定義X的聚合為節點i處的信號值與其一階鄰居節點j的和的平均,即:

基于上述聚合定義,對圖卷積網絡傳播規則的參數共享過程作如下解釋:
將本文的傳播規則公式(5),改寫為信號值與圖卷積網絡分類器在節點i聚合的形式:

因為D是以節點的度組成的對角矩陣,所以簡化上式可得:

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

圖2 一次加權平均的參數共享過程
基于改進后的圖卷積神經網絡的傳播規則(5),本章分四步實現無監督社區檢測算法。整個算法的偽代碼如算法1所示。

具體步驟如下:
步驟1圖數據的初始化和對模擬信號節點的選擇。
算法首先需要處理輸入的數據,即:劃分社區數量,GCN 層數和圖結構數據集。其次算法要對給予的圖數據參數化,根據圖中的節點之間的關系計算算法所需的鄰接矩陣A,并通過鄰接矩陣計算的度矩陣D。
又根據節點數量生成單位矩陣IN,分別與鄰接矩陣和度矩陣相加之后便可得到A?和D?。在對圖數據完成初始化操作之后便可以根據輸入劃分數量選擇初始點并為其添加人工標簽來模擬輸入信號。初始點的選取在本社區劃分算法中尤為重要,作為初始標簽的攜帶者,初始點在一定程度上決定了最后社區劃分的結果。本文提出兩種初始點的選擇方法:
(1)按需求劃分個數依次選取圖中度最大的節點,即:initial_node=max( )D。
因為在本文算法中的標簽是依靠節點的鄰接矩陣進行傳播的,所以圖中度值大的節點最容易將人工標簽信息擴散。同樣,這樣的節點在現實世界網絡中也往往是圖結構網絡的組織者或是有重要影響的節點。且度較大的節點在運算中會保留較小的標簽值,若作為被傳播節點很容易保留從擁有較小度的節點傳遞來的標簽值。
(2)結合度和圖中最遠跳躍數來選擇初始節點。如算法1.1所示。

考慮到在某些圖中最大度的節點可能會聚集在整個圖邊緣或圖中一些不重要的位置。所以初始點的選擇要結合圖中節點的度和兩節點之間的深度,即一個節點到另一個節點之間的最短路徑。算法首先在圖中找出最遠的節點距離,然后在距離最遠的節點中隨機選擇其中一個節點作為最遠路徑的開始節點。然后在相鄰兩階的節點之中選擇出度最大的節點,因為每運行一次GCN 模型只對節點的一階鄰居節點參數共享,所以選擇初始標簽節點時要求距離盡量大于2。使用這樣的方式選擇初始節點,能有效避免在劃分大量社區時發生的不同社區覆蓋的現象。
步驟2應用圖神經網絡的傳播規則,使節點信息得以有效擴散。
根據上一階段生成的模擬信號矩陣,結合GCN 的傳播規則,含有自定義標簽的節點就可以將其本身攜帶的標簽通過加權平均的方式傳遞出去,讓沒有標簽的節點擁有標簽。因為公式(4)中使用一階切比雪夫多項式簡化,所以節點標簽每次傳遞范圍為節點的一階鄰居。第一次傳播時使用模擬信號的初始節點矩陣,之后每次傳播會使用上次一次傳播后得到的結果矩陣,如此循環直到達到輸入要求層數。
步驟3計算結果歸類及對歸類結果的優化與分析。
因每運行一次圖卷積網絡的傳播規則后,節點會接收一個或多個確定的包含了拓撲結構有效信息加權平均值,所以在完成節點標簽的傳播過程后,同一節點難免會擁有多個不同標簽。對于每一個節點來說,這個值在每一層傳播后會逐層累加。所以在計算歸類結果時,算法會選擇節點獲得的標簽中最大的值作為社區劃分的標準。這樣不僅可以保證讓最先獲得有效信息的鄰居節點在每次傳播中依然保持其原有劃分,而且也讓傳播過程更符合信息傳播模型。但由于標簽值是根據節點拓撲結構的加權平均傳播的,這樣可能會導致某些度很大的節點共享很小的標簽值,而度較小節點共享的標簽值較大。而算法通常選擇度較大的節點作為模擬信號的初始節點,在疊加多層卷積層后這個初始節點剩余的標簽值有可能會小于從度較小節點傳播來的標簽值,這樣就會導致度較大的初始節點被錯誤劃分到平均度較小的社區中。
算法1.2根據以上劃分異常情況進行優化。優化目標是將該節點回歸正確的社區,優化方式類似標簽傳播算法[25],即依次判斷每個節點相鄰節點的社區,隨后將節點加入其鄰居中數量最多的社區。優化過程結合了其鄰居節點已經從這個初始節點獲得的有效信息,并據此修改了這個初始節點在卷積層數較大時會選擇度較小節點的標簽而產生的錯誤社區劃分。

在多種不同圖數據上的實驗表明,這種錯誤劃分大多出現在選擇初始節點之間的度相差較大的社區中,而對于選擇的初始節點間度差別不大的情況,歸類結果一般與優化后的劃分結果相同。優化算法一般只改變度值較大的社區中心節點的劃分,社區內鄰居節點及其他節點的劃分基本保持不變,因此優化后節點劃分保持不變的節點與社區內除中心節點外其他節點所占該社區節點總數的比例大致相當。
步驟4計算社區劃分結果的評價指標模塊度Q。
在將擁有多個標簽的節點進行歸類并優化后,算法的輸出矩陣就可以被轉化成節點與其對應社區的矩陣。進而可以評估算法計算的社區劃分效果。
社區劃分評價指標[26],最早由Newman 等人提出,用來衡量一個劃分的好壞程度。其形式為:

式中的評價指標有N個節點,并且已經將這些節點劃分為了n個社區,節點彼此之間共有m個連接,則2m就是整個圖中全部的度。i和j是圖中的任意兩個節點,當兩個節點直接相連時Aij=1,否則Aij=0。ki代表的是節點i的度,δ(ci,cj)是克羅地亞函數,是用來判斷節點V和W是否在同一個社區內,當節點在同一個社區內時δ(ci,cj)=1,否則δ(ci,cj)=0。模塊度越大則表明社區劃分效果越好。Q的取值為[-0.5,1],其論文表示當Q值在0.3~0.7 之間時,說明聚類的效果很好。所以大部分社區劃分算法的目標都是盡量提高模塊度Q。
在得到上階段對應的社區劃分結果后,算法會首先檢查劃分數量是否達到預先設定的社區數量,判斷是否出現過擬合的社區覆蓋現象。算法在達到指定GCN 層數或在未指定層數的情況下自動運行6 次卷積層后停止并計算社區劃分所得模塊度Q,與整個算法的運行時間。最后算法將劃分結果繪圖并顯示出來,以更直觀的方式比較社區劃分結果。
為了客觀全面地評價聚類效果以及對算法的適用性進行分析,本文實驗選用一些經典且被廣泛使用的現實世界數據集進行算法效果對比。選用的對比方法有:基于層次聚類的GN 算法[2],經典的K-means 聚類算法,和同樣使用拉普拉斯矩陣進行劃分的譜聚類算法以及基于特征樹的BIRCH 算法[27]。選用的數據集如表1所示。

表1 算法選用的數據集信息
4.1.1 空手道俱樂部網絡圖
空手道俱樂部作為現實世界的社交網絡且帶有原始標簽的數據集,算法的社區檢測結果理應更加貼近原始社區劃分(圖3)給出的實際結果。于是在這個帶有原始標簽的數據集中,可以介紹另一種社區檢測評估方法:歸一化信息[31](Normalized Mutual Information,NMI),用于計算實際劃分與算法計算劃分之間的相似性。NMI的值越大,表示與數據集中的原始分區和社區結構越相似。
在現實世界的數據中作為組織者的節點根據其重要性及影響力自然會擁有最多的度,算法使用第一種初始化方法來選擇初始節點,即選擇節點{0}與節點{33}作為初始節點。劃分結果在運行第四層GCN 傳播規則時達到最優值。圖4 中可以明顯看出:相比于原圖3中的節點屬性,本文算法將節點{8,2}歸為officer 社區,原因是其與初始設定的標簽節點{33}直接有邊相連,而節點{0}則沒有邊與其直接相連。社區劃分的模塊度與NMI評價指標如表2所示。結果表明GCN 社區檢測算法在處理抽象的現實世界網絡數據有天然的優勢,對于社交網絡和分子結構數據也有很好的適用性。

圖3 空手道俱樂部圖的原始社區劃分

圖4 使用GCN區檢測算法的劃分結果

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

圖5 分類效果隨GCN層數變化效果圖
所以,如上文提到的,算法要盡量減少圖卷積網絡的層數。在一般情況下,少量的卷積層不會出現過擬合的現象,但過擬合現象同時也受到圖數據的深度和節點的數量約束。
圖6 是不同社區劃分數量對比其他類型的社區劃分算法的效果圖,實驗中圖卷積網絡的社區劃分結果是在同一劃分數量下運行5 層GCN 傳播規則,計算模塊度并取最優值作為結果比較。如圖所示GCN 模型在整個社區劃分結果中相比其他算法均有一定的優勢,在第5和第8 個劃分時略低于譜聚類算法劃分結果。相比于譜聚類使用拉普拉斯的特征空間進行劃分,本文算法可以直接使用圖數據的拓撲結構進行劃分,在減少了算法復雜程度的同時也能保持較好的劃分效果。

圖6 悲慘世界人物圖的社區劃分結果對比圖
4.1.3 arXiv引文網絡圖
arXiv 數據集是來自其同名出版社1991 年至1993年電子出版的科學論文及其引文,節點與邊分別對應每篇文章與它的引文。由于這個數據集中包含的節點數量較多,且圖的深度較大,在這里使用第二種方法選擇初始節點,并設定用來對比的社區劃分數量為18 至28。對于這類關系明確且節點數量龐大的數據集,使用鄰接矩陣作為輸入參數的算法會有一定的優勢。因為使用空間坐標的社區檢測算法往往會丟失節點之間邊的信息,這樣的劃分結果往往會出現很多不穩定的問題。另外,大多數高維數據的空間的坐標以及很多現實世界的抽象數據的坐標都無法直接獲得。
因此,這類數據對于譜聚類以及同樣使用鄰接矩陣作為輸入的GCN 社區檢測算法有著相對穩定的結果,但區別在于前者使用鄰接矩陣和相似矩陣來計算拉普拉斯矩陣并對其進行特征分解,將節點抽象到高維空間后再進行劃分,而后者僅使用鄰接矩陣來計算標簽傳播規則,劃分本質是標簽的傳播。而譜聚類又在面對社區之間節點數量差異過大時會出現劃分效果變差的情況。所以,如圖7所示,GCN 社區檢測算法擁有比譜聚類算法更好且穩定的劃分。相對于其他算法本文算法在這個數據集中仍然有很明顯的優勢。

圖7 arXiv引文網絡的社區劃分結果對比圖
蛋白質相互作用數據集是對芽酵母菌中的蛋白質相互進行檢測并記錄觀察得到的數據。通過對觀察到的已知數據分析并尋找規律,仍是現今生物界發現新型蛋白質的常用方法。這類數據往往屬于不連通的圖數據[32]。
圖8是蛋白質相互作用網絡圖的圖像,由圖可見大部分蛋白質聚集在圖結構的中心區域,只有少量分布在中心周圍的其他區域,對于這樣的圖結構數據,中心部分的數據才是真正需要分析和計算的。然而譜聚類算法卻無法達到此效果,因為譜聚類算法使用的特征向量空間會優先聚類圖中周邊的節點。如圖8(a)所示。這樣的劃分結果很明顯地破壞了圖結構原本所具有的社區結構,劃分的社區都在圖結構的邊緣。之后的模塊度數據也說明了這一點。而本文提出GCN 算法則可以直接對圖中的中心數據進行社區劃分,原因是GCN 算法使用鄰接矩陣參與運算實現標簽的傳遞,那些圖中的邊緣節點由于不與圖結構中的主要部分連通,所以都劃分成一個社區,如圖8(b)所示。對于這樣節點分布不均勻且不連通的數據集,只有對該圖數據的中心節點進行社區劃分,才可以從劃分結果中獲得有效的數據。這樣的劃分結果才具有實際意義。
圖9 是本文介紹的四種算法在蛋白質交互網絡中的社區評價指標模塊度對比,由于BIRCH 算法使用節點特征樹來計算社區劃分,對于非連通圖無法進行有效劃分,其模塊度低于譜聚類算法,故不在圖中進行對比。由圖可見本文使用的GCN 社區劃分算法在不同劃分數量上的模塊度Q都優于其他算法。體現了GCN算法在特殊類型的圖數據上也依然有較好的適用性,有相對更廣泛的應用空間。

圖8 蛋白質相互作用網絡圖的社區劃分結果圖
對GCN 社區檢測算法的時空復雜度進行分析,由于圖卷積網絡的社區劃分算法是使用圖的鄰接矩陣作為輸入,且整個運算過程幾乎不需要隨機選取數值,所以每層圖卷積層運行一次的時間復雜度可以簡化為O(n)。但是,正是因為由于算法使用鄰接矩陣(N×N)作為輸入,導致算法的空間復雜度較高O(n3)。總而言之,GCN 算法的核心就是矩陣相乘,相對于需要隨機和循環次數較多的GN 算法O(n2m)和K-means 算法O(mn),其中m為用來計算的節點個數,以及BICRH 算法O(nlbn)也有一定的優勢。而對于譜聚類算法,其在選取特征向量及特征值后還需要二次聚類,所以其理論時間復雜度是算法之中最高的。
本文提出了一種基于圖卷積網絡的社區檢測方法。將半監督學習方法擴展到非監督學習領域,在社區檢測中應用圖卷積網絡模型卷積核高效的參數共享性質,通過添加人工標簽的節點矩陣來模擬輸入信號,使用GCN 傳播規則通過加權平均傳遞標簽,然后比較節點接收到的每個標簽并將節點歸類。最后對歸類的數據進行優化進而得到最終的社區劃分。
在不同類型的數據集進行了實驗,并與許多經典的社區檢測算法進行了比較,結果表明本文算法比所比較的其他社區檢測算法具有更好的性能。而且由于圖卷積網絡傳播規則的性質,該算法將更適合于現實世界的圖形數據集以及動態圖形數據。同時也發現卷積層過多會導致過度擬合的問題和某些節點劃分異常的情況。接下來的工作是尋找更好的初始點選擇方法,并解決劃分結果中可能出現某些節點劃分異常的情況,以及在社區劃分過程中考慮邊含有的信息,并提高社區檢測結果的準確性和檢測速度。