圖卷積網(wǎng)絡增強的非負矩陣分解社區(qū)發(fā)現(xiàn)方法

鄭裕龍，陳啟買，賀超波，2，劉 海，張曉雨

1.華南師范大學 計算機學院，廣州 510631

2.仲愷農(nóng)業(yè)工程學院 信息科學與技術(shù)學院，廣州 510225

真實世界中廣泛存在著各種各樣的復雜網(wǎng)絡，例如社交網(wǎng)絡、作者合著關(guān)系網(wǎng)絡、論文引用網(wǎng)絡以及蛋白質(zhì)交互網(wǎng)絡等。社區(qū)發(fā)現(xiàn)是復雜網(wǎng)絡分析的重要研究話題，它的任務在于將復雜網(wǎng)絡劃分成多個子網(wǎng)絡，并且要求各子網(wǎng)絡內(nèi)部節(jié)點之間連接緊密，而不同子網(wǎng)絡的節(jié)點之間連接稀疏[1]。有效發(fā)現(xiàn)復雜網(wǎng)絡存在的社區(qū)結(jié)構(gòu)有助于理解整個網(wǎng)絡的結(jié)構(gòu)特征和支持許多基于復雜網(wǎng)絡的數(shù)據(jù)分析應用，例如用戶興趣點推薦[2]和發(fā)現(xiàn)電信詐騙團伙[3]。

在過去幾十年，各類社區(qū)發(fā)現(xiàn)方法不斷涌現(xiàn)，其中包括基于圖劃分的方法[4-5]、基于譜聚類的方法[6]、基于模塊度優(yōu)化的方法[7-8]、基于標簽傳播的方法[9-10]以及基于深度學習的方法等[11]。值得指出的是，非負矩陣分解（NMF）因其簡單、易擴展和可解釋性強也被廣泛應用于社區(qū)發(fā)現(xiàn)[12]。目前，已提出許多基于NMF的社區(qū)發(fā)現(xiàn)方法，例如，基于樸素非負矩陣分解的社區(qū)方法[13]、基于對稱NMF的社區(qū)發(fā)現(xiàn)方法SNMF[14]、基于半監(jiān)督的NMF社區(qū)發(fā)現(xiàn)方法SNMF-SS15]、基于節(jié)點相似度和模塊度的NMF社區(qū)發(fā)現(xiàn)方法M-NMF[16]等。盡管現(xiàn)有基于NMF的社區(qū)發(fā)現(xiàn)方法都獲得了不同程度的性能提升，但由于NMF本質(zhì)上是線性模型，因此這些方法仍然屬于線性方法，其表達能力較弱，對于包含大量非線性特征的真實世界復雜網(wǎng)絡，常常無法獲得滿意的社區(qū)發(fā)現(xiàn)性能。

近年來，深度神經(jīng)網(wǎng)絡（如卷積神經(jīng)網(wǎng)絡）因其強大的非線性特征學習能力被廣泛應用于自然語言處理和計算機視覺領(lǐng)域[17]。然而，傳統(tǒng)的深度神經(jīng)網(wǎng)絡只能應用于歐式空間的數(shù)據(jù)，如圖像、語音以及文本等數(shù)據(jù)，而無法有效應用于更為常見的圖數(shù)據(jù)，因為圖是一種典型的非歐式空間數(shù)據(jù)結(jié)構(gòu)。針對該問題，圖神經(jīng)網(wǎng)絡[18]被提出將神經(jīng)網(wǎng)絡模型拓展到圖數(shù)據(jù)處理領(lǐng)域。目前圖神經(jīng)網(wǎng)絡發(fā)展迅速，并產(chǎn)生了許多變種，其中圖卷積網(wǎng)絡GCN[19]由于既具有傳統(tǒng)卷積網(wǎng)絡的優(yōu)勢又能應用于圖數(shù)據(jù)而備受關(guān)注?，F(xiàn)有的研究工作表明，GCN比傳統(tǒng)的深度神經(jīng)網(wǎng)絡（包括卷積網(wǎng)絡）更適合處理圖數(shù)據(jù)，并且具有強大的圖數(shù)據(jù)非線性特征學習能力[20]。由于復雜網(wǎng)絡本質(zhì)上可以很自然地建模為圖結(jié)構(gòu)數(shù)據(jù)，因此應用GCN可以期待更好地提升各類復雜網(wǎng)絡分析任務的性能，其中就包括本文關(guān)注的社區(qū)發(fā)現(xiàn)?；谝陨戏治?，本文提出應用GCN增強NMF社區(qū)發(fā)現(xiàn)方法的性能，所做的主要工作包括：

（1）設計了一種非線性的NMF社區(qū)發(fā)現(xiàn)方法NMFGCN，該方法通過結(jié)合NMF和GCN的各自優(yōu)勢，使得其同時具備復雜網(wǎng)絡的非線性特征學習及社區(qū)發(fā)現(xiàn)能力。

（2）通過設計NMF和GCN的聯(lián)合優(yōu)化框架，提出一個聯(lián)合訓練的損失函數(shù)，在考慮網(wǎng)絡結(jié)構(gòu)的同時也充分利用社區(qū)信息，使得GCN可以學習到更有利于NMF社區(qū)發(fā)現(xiàn)結(jié)果的網(wǎng)絡節(jié)點表示，從而促進社區(qū)發(fā)現(xiàn)性能的提高。

（3）通過在人工合成網(wǎng)絡和真實網(wǎng)絡下進行大量實驗，結(jié)果表明NMFGCN優(yōu)于現(xiàn)有基于NMF的社區(qū)發(fā)現(xiàn)方法及常用的網(wǎng)絡表示學習方法：DeepWalk[21]和LINE[22]。

1 相關(guān)工作

1.1 基于NMF的社區(qū)發(fā)現(xiàn)算法

NMF被證明與K-means和譜聚類模型具有近似等價關(guān)系[24]，因此NMF具備良好的數(shù)據(jù)聚類能力。此外，社區(qū)發(fā)現(xiàn)本質(zhì)上也是節(jié)點聚類問題，所以NMF也適合應用于社區(qū)發(fā)現(xiàn)。目前，已有許多基于NMF的社區(qū)發(fā)現(xiàn)方法，主要是通過擴展基本NMF模型解決各種復雜網(wǎng)絡的社區(qū)發(fā)現(xiàn)問題，例如，基于對稱NMF的社區(qū)發(fā)現(xiàn)方法SNMF[14，25]、基于聯(lián)合NMF的社區(qū)發(fā)現(xiàn)方法S2-j NMF[26]、基于半監(jiān)督NMF的社區(qū)方法SPOCD[27]、SMpC[28]以及基于深度NMF的社區(qū)方法DANMF[29]等。盡管這些方法在不同程度上獲得了一定的性能提升，但由于NMF本質(zhì)上是線性模型，所以這些方法仍然屬于線性方法，不具有非線性表達能力，在處理包含大量非線性特征的復雜網(wǎng)絡社區(qū)發(fā)現(xiàn)問題上仍然有待進一步改進。

1.2 圖卷積網(wǎng)絡

卷積神經(jīng)網(wǎng)絡在圖像處理和自然語言處理上效果顯著，主要歸功于其中的卷積運算可以學習到數(shù)據(jù)對象多層次的非線性表示。然而，卷積神經(jīng)網(wǎng)絡的卷積運算只能定義在圖像、文本以及序列等歐式空間數(shù)據(jù)，而無法定義在屬于非歐式空間數(shù)據(jù)結(jié)構(gòu)的圖上。為了將卷積運算推廣到圖數(shù)據(jù)，Bruna等人提出了譜域圖卷積網(wǎng)絡Spectral GCN[30]。Spectral GCN通過計算圖的拉普拉斯矩陣的特征分解，利用卷積定理[31]，在傅里葉域中定義卷積運算。然而，Spectral GCN由于需要計算圖拉普拉斯矩陣的特征值，因而具有較高的時間復雜度。為了提高Spectral GCN的計算效率，Levie等人[32]提出了切比雪夫網(wǎng)絡ChebyNet。ChebyNet利用切比雪夫展開來近似卷積運算，使得圖卷積運算的效率大大提升。Kipf等人[19]進一步將切比雪夫網(wǎng)絡簡化到一階，提出了圖卷積網(wǎng)絡GCN。GCN的核心思想是節(jié)點通過聚合鄰居節(jié)點和自身節(jié)點的表示來定義卷積操作，從而得到自身節(jié)點的表示。由于簡單有效，GCN已經(jīng)成為目前圖卷積網(wǎng)絡的基本模型。

圖卷積網(wǎng)絡是半監(jiān)督方法，通常需要知道部分節(jié)點的標簽信息來訓練網(wǎng)絡參數(shù)。然而，真實世界的網(wǎng)絡大多是沒有標簽信息的，因此傳統(tǒng)的圖卷積不能直接用于處理社區(qū)發(fā)現(xiàn)任務。圖自編碼器（graph auto-encoder，GAE）[33]是GCN的一個變種，GAE不需要節(jié)點的標簽信息來監(jiān)督訓練網(wǎng)絡參數(shù)，其核心思想是通過圖卷積學習到的節(jié)點低維表示來重構(gòu)網(wǎng)絡，并在訓練過程中使得重構(gòu)網(wǎng)絡接近于原始的網(wǎng)絡。GAE是一種無監(jiān)督網(wǎng)絡表示學習方法，可以應用于沒有真實標簽的復雜網(wǎng)絡任務中，為此本文提出將圖卷積自編碼器與NMF結(jié)合的社區(qū)發(fā)現(xiàn)方法。

2 非線性社區(qū)發(fā)現(xiàn)方法NMFGCN

2.1 問題定義

不失一般性，對于給定的包含n個節(jié)點的復雜網(wǎng)絡，可以建模為無向圖G=(V,E)，其中節(jié)點集為V={v1,v2,…,v n}，無向邊集合為E={eij|vi∈V,v j∈V}。G對應的鄰接矩陣A為二值矩陣。

G中的每個節(jié)點擁有d維的特征向量x∈?1×d，G的n個節(jié)點的特征向量構(gòu)成了節(jié)點特征矩陣X∈?n×d。設k為網(wǎng)絡的社區(qū)數(shù)，C={c1,c2,…,ck}表示G的社區(qū)劃分，其中ci是屬于第i個社區(qū)的節(jié)點集合，例如c2={1,2,5}代表屬于第2個社區(qū)的節(jié)點為v1、v2、v5?；谝陨隙x，本文致力于解決的問題是：對于給定的G=(V,E)，設計非線性的無監(jiān)督社區(qū)發(fā)現(xiàn)方法NMFGCN，學習到社區(qū)成員表示矩陣U∈?n×k+，0≤uij≤1，從而預測給定網(wǎng)絡的社區(qū)劃分C，以提升基于NMF的社區(qū)發(fā)現(xiàn)方法的性能。其中，U的第i行U i是節(jié)點i隸屬于k個不同社區(qū)的概率，且具體地，u4,2=0.6代表節(jié)點4隸屬于社區(qū)c2的概率為0.6。

2.2 NMFGCN社區(qū)發(fā)現(xiàn)模型

NMFGCN的模型框架如圖1所示，它主要包括2個模塊：GCN Module和NMF Module。GCN將鄰接矩陣A和節(jié)點的特征矩陣X作為輸入，輸出節(jié)點表示Z∈?n×m+，m為GCN輸出層維度。NMF以節(jié)點表示Z作為輸入，輸出節(jié)點的社區(qū)成員表示矩陣U。下面分別介紹各模塊的具體實現(xiàn)。

圖1 NMFGCN模型框架Fig.1 Framework of NMFGCN

（1）GCN Module。GCN Module的輸入是鄰接矩陣A和節(jié)點的特征矩陣X，其目標是學習到節(jié)點的低維表示矩陣Z?？紤]L層的GCN，對于第1至L-1層，節(jié)點的隱藏層表示計算公式如下：

通過圖卷積學習到節(jié)點的表示Z后，使其與ZΤ做內(nèi)積以重構(gòu)鄰接矩陣：

重構(gòu)鄰接矩陣的目的是使A′近似于A，從而可以用低維稠密的矩陣Z來表示圖的信息。為此，需要使用一個損失函數(shù)來衡量A與A′的誤差，并通過最小化誤差來使得A′近似于A，本文使用交叉熵作為損失函數(shù)：

重復迭代使用式（14）和式（15）分別更新U和V，直到LNMF收斂，則U為節(jié)點的社區(qū)成員表示矩陣，uij∈U為節(jié)點i隸屬于社區(qū)c j的概率。算法1描述了通過節(jié)點表示Z得到社區(qū)成員表示矩陣U的過程，具體如下：

算法1NMF獲取社區(qū)成員表示算法

2.3 損失函數(shù)構(gòu)建與優(yōu)化

（1）損失函數(shù)。本文處理的問題是無監(jiān)督社區(qū)發(fā)現(xiàn)，僅使用LGCN作為損失函數(shù)訓練圖卷積得到的節(jié)點表示不能很好地用作社區(qū)表示，因此本文采用LGCN與LNMF聯(lián)合訓練的方式：

在實際進行迭代優(yōu)化求解過程中，可以通過設置外部迭代次數(shù)控制GCN的更新，同時設置內(nèi)部迭代次數(shù)控制NMF的更新。當L函數(shù)收斂或超過外部迭代次數(shù)時停止迭代，得到節(jié)點社區(qū)成員表示矩陣U。矩陣U的第i行U i為節(jié)點i的社區(qū)表示。U ij為節(jié)點i隸屬于社區(qū)c j的概率。取U i中最大值所對應的下標j，則c j為節(jié)點i所屬的社區(qū)。根據(jù)該思路，NMFGCN社區(qū)發(fā)現(xiàn)算法設計如算法2所示。

算法2NMFGCN社區(qū)發(fā)現(xiàn)算法

2.4 時間復雜性分析

分析算法1和算法2，容易得出NMFGCN有兩個核心步驟：第一步是迭代優(yōu)化圖卷積網(wǎng)絡和NMF，第二步是從社區(qū)成員表示矩陣U中得到社區(qū)劃分結(jié)果C。根據(jù)算法2，第二步的時間復雜度顯然為O(nk)，以下主要分析第一步的時間復雜度。

在具體實現(xiàn)上，使用2層的GCN。為了簡單起見，GCN每一層輸出的維度均用m表示。假設網(wǎng)絡的節(jié)點數(shù)為n，邊數(shù)為 |E|，社區(qū)數(shù)為k，節(jié)點的特征維度為d，模型迭代次數(shù)為T，NMF內(nèi)部迭代次數(shù)為t，鄰接矩陣A用稀疏矩陣存儲，那么GCN的時間復雜度可表示為O(md|E|)。迭代優(yōu)化NMF的時間主要花費在式（14）、（15）對社區(qū)成員矩陣U和社區(qū)特征矩陣V的更新上，其時間復雜度為O(tnmk)。因此模型訓練的總時間復雜度為O(T(md|E|+tnmk))，其中k?m,m?d。大多數(shù)真實網(wǎng)絡由于關(guān)系復雜，節(jié)點之間連接比較稠密，網(wǎng)絡節(jié)點數(shù)n通常遠小于其邊數(shù) ||E。因此，NMFGCN的時間復雜度主要取決于網(wǎng)絡的邊數(shù) ||E。

3 實驗分析

為了驗證NMFGCN的有效性，本文在人工合成網(wǎng)絡和真實網(wǎng)絡上與多種代表性方法進行對比分析。實驗硬件平臺為Intel Core i7-9700 CPU，主頻2.4 GHz，內(nèi)存32 GB，操作系統(tǒng)為Windows 10，各對比方法均使用Python 3.7實現(xiàn)。

3.1 對比方法

本文選擇多個基于NMF的社區(qū)發(fā)現(xiàn)方法進行對比，此外還選擇目前廣泛使用的基于網(wǎng)絡表示學習的社區(qū)發(fā)現(xiàn)方法DeepWalk和LINE進行比較，所有這些對比方法簡要介紹如下：

NMF[13]：該方法采用基本的NMF模型，直接分解鄰接矩陣A獲得矩陣U和V，||A-U V||2F，其中U作為社區(qū)成員表示矩陣。

SNMF[14]：SNMF基于對稱非負矩陣分解模型（sym-其中H可以直接表示社區(qū)成員隸屬強度。

M-NMF[16]：M-NMF是一種基于模塊度的NMF社區(qū)檢測模型，該模型將網(wǎng)絡的社區(qū)結(jié)構(gòu)融入到網(wǎng)絡嵌入中，聯(lián)合優(yōu)化基于非負矩陣分解的社區(qū)檢測模型和基于模塊度的社區(qū)檢測模型。

ONMF[34]：ONMF基于正交非負矩陣分解模型（orthogonal NMF，ONMF），其基本思想是在NMF模型基礎(chǔ)上，對W施加正交約束，使得WTW=I。

HPNMF[35]：HPNMF基于圖正則化NMF模型，可以集成網(wǎng)絡的拓撲結(jié)構(gòu)以及節(jié)點的同質(zhì)性信息進行社區(qū)發(fā)現(xiàn)。

NSED[36]：NSED基于聯(lián)合NMF模型，包含一個編碼器和一個解碼器，可以通過編碼器獲得社區(qū)成員表示矩陣。

DeepWalk[21]：DeepWalk是一種經(jīng)典的網(wǎng)絡表示學習方法，該方法的核心思想是通過隨機游走的方式在圖中進行采樣，使用圖中節(jié)點之間的共現(xiàn)關(guān)系來學習節(jié)點的低維表示。

LINE[22]：LINE也是一種網(wǎng)絡表示學習方法，其通過保留節(jié)點的一階和二階相似度來獲得網(wǎng)絡節(jié)點的低維表示。

需要指出的是，對于基于NMF的社區(qū)發(fā)現(xiàn)方法，即NMF、SNMF、ONMF、M-NMF、HPNMF以及NSED，可以直接通過社區(qū)成員表示矩陣獲得社區(qū)發(fā)現(xiàn)結(jié)果，而對于基于網(wǎng)絡表示學習的方法DeepWalk和LINE，可以使用這些方法先學習到節(jié)點的低維表示，再通過K-means對低維表示進行聚類，聚類結(jié)果作為最終的社區(qū)發(fā)現(xiàn)結(jié)果。

3.2 數(shù)據(jù)集

實驗使用的數(shù)據(jù)集包括人工合成網(wǎng)絡和真實網(wǎng)絡兩部分，這些數(shù)據(jù)集介紹如下。

（1）人工合成網(wǎng)絡。本文使用LFR基準網(wǎng)絡合成工具[37]生成帶有真實社區(qū)標簽的人工網(wǎng)絡，LFR工具有多個可調(diào)參數(shù)（表1）。本文通過固定部分參數(shù)，變化剩余參數(shù)來生成多組不同的人工網(wǎng)絡。具體地，首先通過固定n、k、maxk、minc、maxc，使mu從0.1變化到0.3，且每次增加0.05共生成一組5個網(wǎng)絡。接著通過固定k、maxk、minc、maxc及mu，使節(jié)點數(shù)量n從1 000增加到5 000，每次遞增1 000生成另外一組5個網(wǎng)絡。兩組網(wǎng)絡的具體參數(shù)設置如表2所示。

表1 LFR的可調(diào)節(jié)參數(shù)Table 1 Adjustable parameters of LFR

表2 人工合成網(wǎng)絡參數(shù)設置Table 2 Parameters setting of synthetic networks

（2）真實網(wǎng)絡。本文選擇4個真實網(wǎng)絡的數(shù)據(jù)集，分別是WebKB、Cora、Citeseer和Pubmed[38]。真實數(shù)據(jù)集的具體參數(shù)如表3所示。以上四個數(shù)據(jù)集均可在https：//linqs.soe.ucsc.edu/data下載獲得。

表3 真實網(wǎng)絡參數(shù)Table 3 Parameters of real networks

考慮到對比方法大多數(shù)是針對非屬性網(wǎng)絡的無監(jiān)督社區(qū)發(fā)現(xiàn)方法，為了公平起見，在真實網(wǎng)絡和合成網(wǎng)絡中，與對比方法進行比較時，NMFGCN的輸入特征X使用NMF分解鄰接矩陣A得到。

3.3 評價準則與參數(shù)設置

為評價社區(qū)發(fā)現(xiàn)結(jié)果的性能，本文使用4個目前普遍采用的評價準則：互信息（normalized mutual information，NMI）、調(diào)整蘭德指數(shù)（adjusted rand index，ARI）、準確率（accuracy，ACC）及模塊度Q，這些評價準則的具體定義可以參考文獻[39]關(guān)于社區(qū)發(fā)現(xiàn)性能評價準則的綜述。對于人工合成網(wǎng)絡，本文均采用NMI、ARI、ACC及模塊度Q進行結(jié)果評價。對于真實網(wǎng)絡，由于沒有真實的社區(qū)劃分標簽，本文使用模塊度Q進行結(jié)果評價。對于所有評價準則，值越大預示著性能越好，反之則相反。

為了公平比較，實驗中所有對比方法的參數(shù)均參考其在原文中的默認值。具體地，對于M-NMF，設置其正則化參數(shù)α=1，β=5；對于HPNMF，置其正則化參數(shù)λ=1；對于DeepWalk，設置窗口大小ω=10，迭代次數(shù)γ=80，walk_length=40，特征維度d=128；對于LINE，保留二階相似度，設置負樣本數(shù)量k=5，特征維度d=128；對于NMFGCN，設置損失權(quán)衡系數(shù)λ=1。GCN Module使用2層的圖卷積，第1層、第2層的輸出維度分別設置為256和128。此外，實驗中對于每個方法均運行10次，并取各評價指標的平均值進行評價。

3.4 人工合成網(wǎng)絡實驗結(jié)果與分析

在表2所示的兩組人工合成網(wǎng)絡數(shù)據(jù)集上進行了對比分析，其中第一組網(wǎng)絡的實驗結(jié)果如表4所示。

表4 具有不同混淆系數(shù)mu的人工合成網(wǎng)絡性能比較Table 4 Performance comparison of synthetic networks with different mu

從表4可以看出，隨著混淆系數(shù)mu的增大，網(wǎng)絡的社區(qū)結(jié)構(gòu)越來越不清晰，檢測社區(qū)的難度不斷加大，各個方法的性能都有著較為明顯的下降趨勢，但本文方法NMFGCN在各個網(wǎng)絡上的表現(xiàn)都優(yōu)于其他模型。例如，當mu=0.1時，與基于NMF表現(xiàn)最好的社區(qū)發(fā)現(xiàn)算法SNMF相比，NMFGCN的ACC、NMI、ARI和模塊度Q分別提升了7.7%、3.1%、8.2%、2.4%。與基于圖表示學習表現(xiàn)最好的社區(qū)發(fā)現(xiàn)算法LINE相比，NMFGCN的ACC、NMI、ARI和模塊度Q分別提升了4.6%、1.7%、7.1%、1.3%。不同的數(shù)據(jù)集上，NMFGCN在四個評價指標上也有不同程度的提升。第二組人工合成網(wǎng)絡上的實驗結(jié)果如圖2所示，從中也可以看出NMFGCN在所有具有不同節(jié)點數(shù)量的網(wǎng)絡均獲得最好的性能。

圖2 具有不同節(jié)點數(shù)量n的人工合成網(wǎng)絡性能比較Fig.2 Performance comparison of synthetic networks with different n

以上在人工合成網(wǎng)絡上的實驗結(jié)果表明，NMFGCN比現(xiàn)有基于NMF的社區(qū)發(fā)現(xiàn)方法具有更好的性能，GCN增強NMF社區(qū)發(fā)現(xiàn)性能的設想得到了初步驗證。

3.5 真實網(wǎng)絡實驗結(jié)果與分析

為進一步驗證NMFGCN的有效性，在4個真實網(wǎng)絡上進行比較分析，實驗結(jié)果如表5所示。可以看出，NMFGCN在各真實網(wǎng)絡上的結(jié)果均優(yōu)于各對比方法。在WebKB、Cora、Citeseer、Pubmed上，NMFGCN與基于NMF表現(xiàn)最好的方法HPNMF相比，模塊度分別提升了5.4%、1.5%、9.3%、1.3%，與基于圖表示學習表現(xiàn)最好的方法LINE相比，模塊度分別提升了58.4%、19.6%、6.4%、2.4%。真實網(wǎng)絡通常比合成網(wǎng)絡更加復雜，包含更多非線性的節(jié)點特征，在合成網(wǎng)絡上表現(xiàn)較好的模型SNMF、LINE，在三個真實的數(shù)據(jù)集中表現(xiàn)較差，而NMFGCN是一種非線性的社區(qū)發(fā)現(xiàn)模型，在真實網(wǎng)絡和合成網(wǎng)絡中表現(xiàn)都比其他模型好，上述結(jié)果進一步證明NMFGCN通過集成GCN與NMF模塊，可以增強網(wǎng)絡非線性特征的表示能力，進而提升NMF社區(qū)發(fā)現(xiàn)的性能。

表5 真實網(wǎng)絡模塊度Q比較Table 5 Modularity Q comparison on real networks

3.6 NMFGCN的聯(lián)合優(yōu)化效果驗證

如前所述，NMFGCN通過聯(lián)合優(yōu)化NMF和GCN模塊，可以得到更好的社區(qū)劃分結(jié)果。為進一步驗證NMFGCN的聯(lián)合優(yōu)化效果，對NMFGCN與GCN+NMF的性能進行對比分析。

對于GCN+NMF，先通過GCN學習節(jié)點的表示Z，再使用NMF分解Z得到社區(qū)劃分結(jié)果。由于不再進行聯(lián)合訓練，GCN的損失函數(shù)只有重構(gòu)鄰接矩陣的損失LGCN，而不再考慮NMF分解的損失LNMF，即其損失函數(shù)為L=LGCN。

對比實驗中，分別在真實網(wǎng)絡與人工合成網(wǎng)絡（表2第二組數(shù)據(jù)）中進行實驗比較，并在每個網(wǎng)絡數(shù)據(jù)集上均運行10次并取平均值。合成網(wǎng)絡的實驗結(jié)果如圖3所示，真實網(wǎng)絡的實驗結(jié)果如圖4所示?？梢钥闯?，NMFGCN在四個真實數(shù)據(jù)集上的模塊度Q均高于GCN+NMF。其原因是NMFGCN在訓練的同時考慮了鄰接矩陣重構(gòu)的損失和NMF分解的損失，從而可以同時利用網(wǎng)絡的拓撲結(jié)構(gòu)信息和社區(qū)信息，并使得NMF與GCN可以相互促進存進：GCN能夠?qū)W習到更有利于NMF的節(jié)點表示，NMF也能獲得更好的社區(qū)劃分結(jié)果。在人工合成網(wǎng)絡上，隨著節(jié)點數(shù)的增加，NMFGCN和GCN+NMF的四個指標上的值均有所下降，但NMFGCN的表現(xiàn)仍優(yōu)于GCN+NMF。以上兩組實驗充分證明了NMFGCN進行聯(lián)合優(yōu)化的有效性。

圖3 人工合成網(wǎng)絡的聯(lián)合優(yōu)化對比Fig.3 Comparison of joint optimization on synthetic networks

圖4 真實網(wǎng)絡的聯(lián)合優(yōu)化對比Fig.4 Comparison of joint optimization on real networks

3.7 社區(qū)劃分可視化分析

為更清楚地展示NMFGCN的社區(qū)劃分效果，本文利用t-SNE[40]工具對社區(qū)成員表示向量在二維平面進行可視化分析實驗。實驗選擇Cora和Citeseer作為數(shù)據(jù)集，同時選擇NMF和HPNMF作為對比方法。通過為不同社區(qū)的節(jié)點標識不同的顏色，可以對可視化結(jié)果進行對比分析（圖5和圖6）。從圖5可以看出，在Cora上，NMFGCN的相同顏色節(jié)點更加集中，社區(qū)邊界更清晰，而NMF和HPNMF不同顏色的節(jié)點聚集混合明顯，社區(qū)邊界較為模糊。從圖6可以看出，在Citeseer數(shù)據(jù)集上，NMF劃分的數(shù)據(jù)集幾乎不能看清楚邊界，HPNMF劃分的社區(qū)雖然能夠看清邊界，但是屬于同一社區(qū)的節(jié)點比較分散，而NMFGCN在該數(shù)據(jù)集上不僅社區(qū)邊界清晰，而且同一社區(qū)的節(jié)點也相對集中。這些結(jié)果進一步表明NMFGCN具有更好的社區(qū)劃分性能。

圖5 Cora的社區(qū)劃分可視化Fig.5 Community partitioning visualization on Cora

圖6 Citeseer的社區(qū)劃分可視化Fig.6 Community partitioning visualizations on Citeseer

為進一步觀察NMFGCN的社區(qū)劃分能力，將其在Cora和Citeseer上不同迭代次數(shù)（分別取1、5和10）的社區(qū)劃分結(jié)果進行可視化，結(jié)果如圖7和圖8所示?？梢钥闯鲭S著迭代次數(shù)的增加，NMFGCN的社區(qū)邊界越來越清晰，并且不需要太多的迭代次數(shù)就可以獲得較好的社區(qū)劃分效果，這在一定程度上也說明了NMFGCN具有較好的社區(qū)發(fā)現(xiàn)效率。

圖7 NMFGCN在Cora上不同迭代次數(shù)的社區(qū)劃分可視化Fig.7 NMFGCN community partitioning visualizations with different iterations on Cora

圖8 NMFGCN在Citeseer上不同迭代次數(shù)的社區(qū)劃分可視化Fig.8 NMFGCN community partitioning visualizations with different iterations on Citeseer

3.8 λ設置

在式（12）中，NMFGCN的損失函數(shù)為L=LGCN+λLNMF，其中λ用來平衡NMF損失。為獲得λ的合理設置，本文選擇表2的第二組人工合成網(wǎng)絡中節(jié)點數(shù)量n為3 000的數(shù)據(jù)集進行實驗，通過將λ在{10-3，10-2，10-1，100，101，102，103}依次取值并計算相應的NMI、ARI、ACC以及模塊度Q，結(jié)果如圖9所示?？梢钥闯?，λ在[10-3，1]取值時，各性能評價指標表現(xiàn)平穩(wěn)。當λ大于10時，隨著λ增大，各性能評價指標略有下降趨勢，但并不明顯。在不同數(shù)據(jù)集上，λ的取值也在[10-3，1]內(nèi)取得最好的結(jié)果。整體而言，NMFGCN對參數(shù)λ是不敏感的。為了使NMFGCN得到較好的性能，λ可以在[10-3，1]內(nèi)取值，如本文中的所有實驗，都將λ設置為1。

圖9 不同λ取值對NMFGCN性能的影響Fig.9 Performance of NMFGCN with differentλ

3.9 運行效率分析

在2.4節(jié)中，本文分析得出NMFGCN的時間復雜度為O(T(md|E|+tnmk))，但迭代次數(shù)T是不確定的。為了探索NMFGCN獲得最好的社區(qū)劃分結(jié)果所需要的最小迭代次數(shù)。本節(jié)選擇真實網(wǎng)絡Pubmed作為實驗數(shù)據(jù)，選擇基于NMF的社區(qū)發(fā)現(xiàn)方法NMF、SNMF、M-NMF、ONMF、HPNMF、NSED進行對比，測試并記錄每個方法在獲得最好社區(qū)劃分結(jié)果時所需要的最少迭代次數(shù)T m以及相應所花費的時間S。實驗結(jié)果如圖10所示，可以看出，在運行時間上，NMF和SNMF由于模型簡單，運行效率更高，因而獲得最好社區(qū)劃分結(jié)果所花費的時間更少。ONMF所花費的時間最長，主要是由正交約束計算復雜度高所導致。HPNMF由于計算相似度矩陣導致模型復雜度高，且相應的Tm值較大，因此所花費的時間僅次于ONMF。NMFGCN的Tm為11，相比于其他模型，NMFGCN能夠在更小的迭代次數(shù)下獲得理想的社區(qū)劃分結(jié)果。在運行時間上，相比于ONMF和HPNMF，NMFGCN具有較為明顯的優(yōu)勢。

圖10 運行時間比較Fig.10 Runtime comparison

4 總結(jié)和展望

為了提升基于NMF的社區(qū)發(fā)現(xiàn)方法性能，本文提出了一種GCN增強的非線性NMF社區(qū)發(fā)現(xiàn)方法NMFGCN，利用GCN強大的網(wǎng)絡節(jié)點非線性特征學習能力提升NMF社區(qū)發(fā)現(xiàn)性能。為了驗證NMFGCN的有效性，本文在人工合成網(wǎng)絡和真實網(wǎng)絡進行了大量的對比實驗，結(jié)果表明NMFGCN優(yōu)于現(xiàn)有基于NMF的社區(qū)發(fā)現(xiàn)方法，也優(yōu)于常用的網(wǎng)絡表示學習方法DeepWalk和LINE，很好地解決了現(xiàn)有NMF社區(qū)發(fā)現(xiàn)方法由于屬于線性模型而導致非線性網(wǎng)絡節(jié)點特征難于處理、社區(qū)發(fā)現(xiàn)性能受限的問題。

需要指出的是，盡管相比于現(xiàn)有的基于NMF的社區(qū)發(fā)現(xiàn)模型和一些常用的圖表示學習方法，NMFGCN都獲得了不小的提升，但其仍存在需要改進的地方，具體表現(xiàn)在兩個方面：

（1）NMFGCN的運行效率不高，訓練大型網(wǎng)絡花費時間較長。NMFGCN的訓練時間主要花費在圖卷積層學習節(jié)點表示Z以及NMF分解Z上。其中后者可以通過減小圖卷積層的輸出維度的大小和減少NMF迭代次數(shù)來減少訓練時間。

（2）由于圖卷積是一種直推式圖表示學習方法，當網(wǎng)絡中增加節(jié)點或者改變拓撲關(guān)系時需要重新訓練模型。為了解決該問題，在下一步工作中將會考慮借鑒歸納式圖表示學習方法GraphSAGE[41]來學習節(jié)點的表示Z。