陳 潔，張二明，王倩倩，趙 姝+，張燕平

1.安徽大學(xué) 計算機科學(xué)與技術(shù)學(xué)院，合肥 230601

2.安徽大學(xué) 國際教育學(xué)院，合肥 230601

近年來，在許多學(xué)科中，將結(jié)構(gòu)化數(shù)據(jù)建模和解釋為網(wǎng)絡(luò)的趨勢日益增長。網(wǎng)絡(luò)作為一種描述實體之間關(guān)系的普遍抽象概念，已成為數(shù)據(jù)科學(xué)研究的熱點，網(wǎng)絡(luò)分析也日益受到生物學(xué)和計算機科學(xué)等領(lǐng)域的關(guān)注[1]。社團(tuán)檢測是網(wǎng)絡(luò)分析中的一項重要任務(wù)，其目的是將網(wǎng)絡(luò)劃分為多個社團(tuán)，使得同一社團(tuán)內(nèi)的節(jié)點聯(lián)系比較緊密，不同社團(tuán)內(nèi)的節(jié)點聯(lián)系比較稀疏。

在許多領(lǐng)域中，真實的網(wǎng)絡(luò)數(shù)據(jù)不僅包括節(jié)點的結(jié)構(gòu)信息也包括節(jié)點的屬性信息。例如，在社交網(wǎng)絡(luò)中，邊緣表示人與人之間的關(guān)系（友誼、合作等），節(jié)點屬性描述的是一個人的角色或性格。在引文網(wǎng)絡(luò)中，節(jié)點代表論文，邊緣表示論文之間的引用關(guān)系，節(jié)點屬性描述論文的特征（關(guān)鍵詞、發(fā)表時間等）。屬性網(wǎng)絡(luò)社團(tuán)檢測任務(wù)中如果節(jié)點結(jié)構(gòu)信息缺失導(dǎo)致網(wǎng)絡(luò)結(jié)構(gòu)稀疏，屬性信息可以補充結(jié)構(gòu)信息，緩解網(wǎng)絡(luò)結(jié)構(gòu)的稀疏性，使社團(tuán)檢測更加精確。因此，同時考慮節(jié)點的結(jié)構(gòu)信息和屬性信息有助于提高社團(tuán)檢測的性能。目前，涉及到屬性網(wǎng)絡(luò)社團(tuán)檢測任務(wù)[2]的研究并不多，如何融合節(jié)點的結(jié)構(gòu)信息與屬性信息進(jìn)行社團(tuán)檢測仍然是一個難題。

現(xiàn)有的經(jīng)典社團(tuán)檢測方法，如K-means只能利用節(jié)點屬性信息進(jìn)行社團(tuán)劃分。Louvain算法[3]只能利用節(jié)點的結(jié)構(gòu)信息進(jìn)行社團(tuán)劃分。然而，在屬性網(wǎng)絡(luò)中這兩類社團(tuán)檢測方法皆存在不足，前者沒有利用屬性網(wǎng)絡(luò)中的結(jié)構(gòu)信息，后者沒有利用屬性網(wǎng)絡(luò)中屬性信息。

近幾年，結(jié)合屬性信息與結(jié)構(gòu)信息的社團(tuán)檢測方法被提出，包括基于生成模型[4]、光譜聚類[5]、隨機游走[6-7]、馬爾可夫隨機場[8-9]、非負(fù)矩陣分解[10]和圖卷積網(wǎng)絡(luò)（graph convolution network，GCN）[11]等方法。特別是基于圖卷積的方法，如GAE（graph autoencoders）[12]在幾個屬性網(wǎng)絡(luò)社團(tuán)檢測任務(wù)上展示了先進(jìn)的性能。但是現(xiàn)有的圖卷積方法大多數(shù)是直接使用圖卷積作為特征提取器，每個卷積層都加上一個投影層，很難疊加很多層，訓(xùn)練一個深度模型。如ARGE（adversarially regularized graph autoencoder）[13]和MGAE（marginalized graph autoencoder）[14]使用兩層和三層的圖卷積，只考慮每個節(jié)點兩階或三階以內(nèi)的鄰居，沒有充分利用節(jié)點之間的關(guān)系。此外，這些方法都是用一個固定的低階圖卷積算法模型，忽略了真實數(shù)據(jù)集的多樣性，這可能降低社團(tuán)檢測結(jié)果。

為了克服原始網(wǎng)絡(luò)結(jié)構(gòu)的稀疏性和利用節(jié)點的高階結(jié)構(gòu)關(guān)聯(lián)，本文提出了一種基于K階圖卷積的屬性網(wǎng)絡(luò)社團(tuán)檢測方法（K-order graph convolution community detection method，KGCN）。首先，根據(jù)節(jié)點屬性之間的相似性添加新邊緣對原始網(wǎng)絡(luò)進(jìn)行重構(gòu)，彌補節(jié)點的結(jié)構(gòu)信息。其次，相鄰的節(jié)點具有相似的特征表示，往往屬于一個社團(tuán)。不像之前方法那樣設(shè)計一個疊加多層的圖卷積，而是設(shè)計一個考慮到每個節(jié)點K階鄰居的K階圖卷積，作為節(jié)點特征的低通圖濾波器來獲得平滑的特征表示。最后，采用譜聚類算法進(jìn)行社團(tuán)檢測。KGCN 考慮到現(xiàn)實網(wǎng)絡(luò)結(jié)構(gòu)的多樣性，針對不同的屬性網(wǎng)絡(luò)可以選擇不同的K值。在四個真實屬性網(wǎng)絡(luò)上的實驗結(jié)果表明，KGCN具有很強的競爭力，在很多情況下優(yōu)于最先進(jìn)的方法。

1 相關(guān)工作

現(xiàn)有的社團(tuán)檢測算法大致分為三種[15]：基于結(jié)構(gòu)的社團(tuán)檢測方法、基于屬性的社團(tuán)檢測方法和融合結(jié)構(gòu)與屬性的社團(tuán)檢測方法。

基于結(jié)構(gòu)的社團(tuán)檢測方法：利用結(jié)構(gòu)信息對網(wǎng)絡(luò)進(jìn)行劃分是一種經(jīng)典的社團(tuán)檢測方法，通過邊緣信息優(yōu)化某種衡量指標(biāo)得到最優(yōu)社團(tuán)結(jié)構(gòu)，Louvain算法[3]是其中有代表性的算法。然而由于計算成本高，這些算法無法處理大規(guī)模網(wǎng)絡(luò)。標(biāo)簽傳播[16]算法根據(jù)結(jié)構(gòu)信息在網(wǎng)絡(luò)之中傳播標(biāo)簽進(jìn)行社團(tuán)檢測，該算法雖然具有可擴展性，但最近的研究表明，它在許多常見的場景[17]上運行時并不健壯。也有一些解決方案試圖從其他角度進(jìn)行社團(tuán)檢測，如DandM（deepwork and Markov）[18]算法通過網(wǎng)絡(luò)表示學(xué)習(xí)模型將結(jié)構(gòu)信息轉(zhuǎn)換為特征信息，再利用概率圖模型進(jìn)行社團(tuán)檢測。

基于屬性的社團(tuán)檢測方法：K-means是一種基于屬性的社團(tuán)檢測方法，被廣泛應(yīng)用于科研和工業(yè)領(lǐng)域。該方法首先定義K個初始社團(tuán)中心，通過不斷迭代將節(jié)點劃分到合適的社團(tuán)，在網(wǎng)絡(luò)表示學(xué)習(xí)模型的基礎(chǔ)上有著大量的擴展[19-20]。

融合結(jié)構(gòu)與屬性的社團(tuán)檢測方法：屬性網(wǎng)絡(luò)社團(tuán)檢測方法需同時考慮節(jié)點的結(jié)構(gòu)信息和屬性信息。SA-Cluster[21]和HeteroAttractor[22]使用虛擬頂點來映射屬性值。每個屬性值由網(wǎng)絡(luò)上的單個虛擬頂點表示。這些虛擬頂點與網(wǎng)絡(luò)中的所有頂點相連，以保持它們的屬性關(guān)系。CODICIL[23]、SAC2（structural and attribute cluster two）[24]使用屬性為每個頂點尋找最近的鄰居，然后通過連接每個頂點與其鄰居來重構(gòu)網(wǎng)絡(luò)，保留屬性信息。一些新的方法使用圖卷積網(wǎng)絡(luò)整合結(jié)構(gòu)信息和屬性信息。例如，GAE 算法和VGAE（variational graph auto-encoders）算法用雙層圖卷積學(xué)習(xí)節(jié)點表示，然后分別用自編碼器和變分自編碼器重構(gòu)鄰接矩陣。MGAE算法用三層圖卷積學(xué)習(xí)節(jié)點特征表示，然后應(yīng)用邊緣去噪自編碼器重構(gòu)給定的節(jié)點特征。ARGE 算法和ARVGE（adversarially regularized variational graph autoencoder）算法分別通過GAE 和VGAE 學(xué)習(xí)節(jié)點嵌入，然后使用生成對抗網(wǎng)絡(luò)強制節(jié)點嵌入以匹配先驗分布。

2 模型介紹

本文提出的KGCN社團(tuán)檢測方法如圖1所示，共分為三大部分：第一部分根據(jù)節(jié)點的屬性信息對原始網(wǎng)絡(luò)進(jìn)行重構(gòu)，得到緩解稀疏性的重構(gòu)網(wǎng)絡(luò)；第二部分考慮到每個節(jié)點K階內(nèi)的鄰居，采用K階圖卷積編碼器對節(jié)點進(jìn)行編碼得到節(jié)點特征表示；第三部分根據(jù)獲得的節(jié)點特征表示使用譜聚類算法進(jìn)行社團(tuán)檢測得到屬性網(wǎng)絡(luò)的社團(tuán)結(jié)構(gòu)。

圖1 KGCN模型框架Fig.1 KGCN model framework

2.1 問題定義

給出一個屬性網(wǎng)絡(luò)G=(V,E,X)，其中V={v1,v2,…,vn}表示包含n個節(jié)點的集合，E 表示邊緣集合，X=[x1,x2,…,xn]T∈Rn×d表示節(jié)點的屬性矩陣，xi∈Rd表示節(jié)點vi的屬性信息。本文任務(wù)是將n個節(jié)點劃分為m個社團(tuán)C={c1,c2,…,cm}。

2.2 重構(gòu)網(wǎng)絡(luò)

屬性網(wǎng)絡(luò)同時包含節(jié)點的結(jié)構(gòu)信息和節(jié)點的屬性信息，對原始網(wǎng)絡(luò)結(jié)構(gòu)進(jìn)行重構(gòu)，首先定義節(jié)點之間的屬性相似度。

其中，Suv∈[0,1]為節(jié)點u與節(jié)點v之間的相似度，然后根據(jù)節(jié)點之間的屬性相似度在具有相似屬性的節(jié)點對之間添加新的邊緣。

其中，E為新增邊緣集合，α為屬性相似度閾值。如果節(jié)點u與節(jié)點v之間的相似度大于閾值α則在兩節(jié)點之間添加一條新的邊緣補充節(jié)點的結(jié)構(gòu)信息，緩解原始網(wǎng)絡(luò)的稀疏性。重構(gòu)后網(wǎng)絡(luò)的鄰接矩陣表示為A={auv}∈Rn×n，如果節(jié)點u與節(jié)點v之間存在連邊，則auv=1，相反auv=0。

2.3 K 階圖卷積

利用節(jié)點屬性信息緩解網(wǎng)絡(luò)結(jié)構(gòu)稀疏性得到重構(gòu)網(wǎng)絡(luò)，然后使用K階圖卷積編碼器對節(jié)點進(jìn)行編碼，得到每個節(jié)點的特征表示。圖卷積定義為圖信號f與圖濾波器G的乘積。

其中，Z=[z1,z2,…,zn]T，zq為用戶相關(guān)特征向量uq的系數(shù)，系數(shù)的大小表示uq的強度。

考慮到同一社團(tuán)內(nèi)的節(jié)點不僅要在結(jié)構(gòu)上具有緊密性，在屬性上也應(yīng)具有同質(zhì)性，因此對屬性矩陣X進(jìn)行圖卷積，使得相鄰節(jié)點在每個維度上具有相似的特征值。濾波后的屬性矩陣計算如下：

其中，k為正整數(shù)，不同的k值對應(yīng)不同階的鄰居。k階圖卷積迭代計算公式為：

2.4 譜聚類

根據(jù)圖卷積濾波后的節(jié)點特征采用譜聚類算法[26]進(jìn)行社團(tuán)劃分，將n個節(jié)點劃分到m個社團(tuán)中。首先計算彼此節(jié)點之間的相似性，得到非負(fù)對稱的相似度矩陣S。

通過計算S的m個最大特征值相關(guān)的特征表示作為初始節(jié)點，然后應(yīng)用K-means 算法進(jìn)行社團(tuán)檢測，得到m個社團(tuán)結(jié)構(gòu)。

2.5 時間復(fù)雜度分析

用n表示節(jié)點數(shù)，d表示屬性數(shù)，m表示社團(tuán)個數(shù)，N表示鄰接矩陣A的非零項數(shù)。對原始網(wǎng)絡(luò)進(jìn)行重構(gòu)得到重構(gòu)網(wǎng)絡(luò)的時間復(fù)雜度是O(n2)。由于鄰接矩陣N?n2，初始化時計算Ls的時間復(fù)雜度為O(N)，對于一個稀疏的Ls，式（7）中計算K階圖卷積的最快方法是將X左乘重復(fù)K次，其時間復(fù)雜度為O(NdK)。對進(jìn)行譜聚類的時間復(fù)雜度為O(n2d+n2m)。由于m?d?n，總的時間復(fù)雜度為O(n2d+NdK)。

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

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

本文在4個真實數(shù)據(jù)集[25]上進(jìn)行了實驗（所有數(shù)據(jù)集的邊緣都是無向的）。Cora、CiteSeer 和Pubmed是由科學(xué)出版物組成的引文網(wǎng)絡(luò)，每個頂點代表一個出版物，一條邊表示一條引文關(guān)系。Wiki是一個網(wǎng)頁網(wǎng)絡(luò)，如果一個網(wǎng)頁與另外一個網(wǎng)頁有鏈接，則存在連邊。Cora與CiteSeer每個頂點的二元屬性表明詞包中有一個單詞存在或不存在。Pubmed與Wiki每個頂點的屬性為詞的權(quán)重。數(shù)據(jù)集的詳細(xì)信息如表1所示。

表1 數(shù)據(jù)集詳細(xì)信息Table 1 Dataset details

3.2 評估指標(biāo)與對比算法

為了評估社團(tuán)檢測性能，將KGCN 與三類社團(tuán)檢測方法進(jìn)行對比，使用三個常用性能指標(biāo)[27]：精度（accuracy，Acc）、歸一化互信息（normalized mutual information，NMI）和F1-score（F1）。對比算法如下：

（1）基于屬性的社團(tuán)檢測方法：K-means 和Spectral-g利用線性核函數(shù)構(gòu)造幾點屬性相似性矩陣進(jìn)行社團(tuán)檢測。

（2）基于結(jié)構(gòu)的社團(tuán)檢測方法：以節(jié)點鄰接矩陣作為相似矩陣的譜聚類算法（Spectral-g），DNGR 利用深度神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)節(jié)點表示，再進(jìn)行社團(tuán)劃分。

（3）融合結(jié)構(gòu)和屬性的社團(tuán)檢測方法：圖自編碼器GAE 和圖變分自編碼器VGAE，邊緣圖自編碼器MGAE，反向正則化圖自編碼器ARGE和ARVGE，以及自適應(yīng)圖編碼器AGC。

3.3 參數(shù)設(shè)置

對比算法中的參數(shù)遵循原始文獻(xiàn)中的設(shè)置。其中DeepWalk的隨機漫步次數(shù)為10次，每個節(jié)點的潛在維數(shù)為128，每次隨機漫步的路徑長度為80。DNGR的自編碼器有三層，分別包含512個神經(jīng)元和256個隱含層神經(jīng)元。對于GAE和VGAE，構(gòu)建了隱含層具有32 個神經(jīng)元和嵌入層具有16 個神經(jīng)元的編碼器，并使用學(xué)習(xí)率為0.01的Adam優(yōu)化器訓(xùn)練編碼器進(jìn)行200次迭代。對于MGAE，損失等級p為0.4，層數(shù)為3，λ參數(shù)為10-5。對于ARGE 和ARVGE，本文構(gòu)造了一個包含32 個神經(jīng)元隱含層和16 個神經(jīng)元嵌入層的編碼器。識別器由兩個隱含層組成，分別包含16 個神經(jīng)元和64 個神經(jīng)元。在Cora、CiteSeer和Wiki 上，本文用Adam 優(yōu)化器訓(xùn)練了ARGE 和ARVGE 的自動編碼器相關(guān)模型200 次迭代，編碼器學(xué)習(xí)率和判別器學(xué)習(xí)率均為0.001；在Pubmed 上，本文以編碼器學(xué)習(xí)率0.001 和識別器學(xué)習(xí)率0.008 訓(xùn)練它們進(jìn)行2 000 次迭代。在算法KGCN 中，超參數(shù)α和k分別在網(wǎng)絡(luò)重構(gòu)和節(jié)點編碼過程中起到作用。定義α取值范圍為α∈[0,1]，步長為0.1,k的取值范圍為k∈[1,60]，步長為1，通過實驗觀察KGCN 算法的最佳參數(shù)值。如圖2、圖3所示，在4個真實數(shù)據(jù)集上α和k的普適性范圍為α∈[0.5,1.0]和k∈[15,25]。其中當(dāng)α=0.5,k=14 時Cora 數(shù)據(jù)集取得最佳實驗結(jié)果，當(dāng)α=1.0,k=19 時CiteSeer 數(shù)據(jù)集取得最佳實驗結(jié)果，當(dāng)α=0.9,k=50 時Pubmed 數(shù)據(jù)集取得最佳實驗結(jié)果，當(dāng)α=0.2,k=4 時Wiki 數(shù)據(jù)集取得最佳實驗結(jié)果。

圖2 評價指標(biāo)隨α 變化圖Fig.2 Preformance changing with α

圖3 評價指標(biāo)隨k 變化圖Fig.3 Preformance changing with k

3.4 結(jié)果分析

遵循參數(shù)設(shè)置部分的最優(yōu)參數(shù)值，本文在4個真實數(shù)據(jù)集上分別運行10次取平均值作為最終實驗結(jié)果，如表2所示，其中加粗表示最優(yōu)實驗結(jié)果。

由表2可以得出，本文提出的KGCN算法在總體上優(yōu)于其他11種算法。KGCN的社團(tuán)檢測性能與僅利用結(jié)構(gòu)信息或?qū)傩孕畔⒌纳鐖F(tuán)檢測方法相比，往往表現(xiàn)出很大的優(yōu)勢。原因是同一社團(tuán)內(nèi)不僅在結(jié)構(gòu)上具有緊密性，在屬性上也具有同質(zhì)性，KGCN 算法融合了節(jié)點的結(jié)構(gòu)信息與節(jié)點的屬性信息，這兩種信息可以相互補充，提高社團(tuán)檢測性能。

表2 不同數(shù)據(jù)集上各算法結(jié)果對比Table 2 Comparison of algorithm results on different datasets 單位：%

KGCN 算法與現(xiàn)有的同時使用屬性信息和結(jié)構(gòu)信息的社團(tuán)檢測方法相比依然有著很大的優(yōu)勢。因為GAE、VGAE、ARGE和ARVGE在對節(jié)點進(jìn)行編碼時僅考慮到每個節(jié)點的二階鄰居，MGAE 只考慮到每個節(jié)點的三階鄰居，AGC 模型雖然考慮到節(jié)點的高階鄰居，但原始的網(wǎng)絡(luò)結(jié)構(gòu)具有稀疏性，部分節(jié)點因為缺失結(jié)構(gòu)信息會導(dǎo)致社團(tuán)檢測性能下降。KGCN 算法通過屬性信息重構(gòu)網(wǎng)絡(luò)緩解了原始網(wǎng)絡(luò)的稀疏性，在節(jié)點編碼時獲得質(zhì)量更佳的節(jié)點特征表示，從而提高社團(tuán)檢測性能。

由實驗數(shù)據(jù)可以得出，在數(shù)據(jù)集CiteSeer與Wiki上，KGCN算法在所有評價指標(biāo)上均優(yōu)于其他對比算法。相比第二優(yōu)算法，KGCN在CiteSeer數(shù)據(jù)集上分別取得了1.7%的精度提升、2.4%的歸一化互信息提升和1.5%的F1值提升；KGCN在Wiki數(shù)據(jù)集上分別取得了21.3%的精度提升、28.9%的歸一化互信息提升和38.0%的F1 值提升；在數(shù)據(jù)集Cora 和Pubmed上，KGCN在評價指標(biāo)Acc和F1上獲得最優(yōu)的表現(xiàn)，可能由于屬性長度較短，未能根據(jù)不豐富的屬性信息得到理想的重構(gòu)網(wǎng)絡(luò)，在評價指標(biāo)NMI 上僅獲得相近的結(jié)果，其中在Cora 數(shù)據(jù)集上，KGCN 算法與第二優(yōu)算法相比獲得了3.3%的精度提升和2.4%的F1值提升。

3.5 消融分析

與其他社團(tuán)檢測算法對比的同時，也針對KGCN算法進(jìn)行了如下消融分析：原始網(wǎng)絡(luò)結(jié)構(gòu)上使用一階圖卷積對節(jié)點進(jìn)行編碼（Ori_1），原始網(wǎng)絡(luò)結(jié)構(gòu)上使用K階圖卷積對節(jié)點進(jìn)行編碼（Ori_k），重構(gòu)網(wǎng)絡(luò)上使用K階圖卷積對節(jié)點進(jìn)行編碼（Re_k）。表3給出了實驗結(jié)果，其中加粗表示最優(yōu)實驗結(jié)果。通過表3可以看出，Ori_1的社團(tuán)檢測結(jié)果最差，這是因為原始網(wǎng)絡(luò)具有稀疏性且低階圖卷積沒有考慮節(jié)點高階結(jié)構(gòu)關(guān)聯(lián)。Ori_k 的社團(tuán)檢測結(jié)果有所提升，這是因為對節(jié)點進(jìn)行編碼時考慮到節(jié)點高階結(jié)構(gòu)關(guān)聯(lián)。Re_k 得到最優(yōu)社團(tuán)檢測結(jié)果，這是因為其不僅克服了原始網(wǎng)絡(luò)結(jié)構(gòu)的稀疏性，在對節(jié)點進(jìn)行編碼時也考慮到節(jié)點高階結(jié)構(gòu)關(guān)聯(lián)。

表3 消融分析實驗結(jié)果Table 3 Results of ablation analysis 單位：%

4 總結(jié)與展望

本文提出了一種屬性網(wǎng)絡(luò)社團(tuán)檢測方法。首先根據(jù)節(jié)點的屬性信息對原始網(wǎng)絡(luò)進(jìn)行重構(gòu)，緩解原始網(wǎng)絡(luò)結(jié)構(gòu)的稀疏性。為充分利用結(jié)構(gòu)信息和優(yōu)化不同屬性網(wǎng)絡(luò)的社團(tuán)檢測性能，針對不同的屬性網(wǎng)絡(luò)考慮到不同階的鄰居，采用K階圖卷積編碼器對節(jié)點進(jìn)行編碼獲得節(jié)點特征表示。最后根據(jù)獲得的節(jié)點特征表示使用譜聚類算法進(jìn)行社團(tuán)檢測。實驗結(jié)果表明，本文提出的融合屬性信息與結(jié)構(gòu)信息的K階圖卷積社團(tuán)檢測方法在許多大型真實網(wǎng)絡(luò)上都優(yōu)于目前最先進(jìn)的社區(qū)檢測方法。在未來的工作中，考慮改進(jìn)網(wǎng)絡(luò)重構(gòu)方法，使方法具有更好的社團(tuán)檢測性能。