基于異質圖注意力網絡的重疊社區發現方法

孫 悅，趙宇紅，薛 婷

(內蒙古科技大學 信息工程學院，內蒙古 包頭 014010)

0 引 言

社區發現是將網絡中的相似節點聚成一個社區，且同一社區內的節點連接緊密[1]。早期，學者把網絡中的節點和邊都為同一類型的網絡稱為同質網絡，并提出基于圖分割算法，基于模塊度優化算法[2]等社區發現方法。但現實世界中多為異質網絡，即節點和邊是多種類型。同質網絡社區發現方法適用于異質網絡，但社區劃分準確率較低。隨著研究的深入，研究者發現真實網絡中的社區存在重疊現象，即一個節點屬于多個社區。而異質網絡中的重疊社區發現尚在起步階段，具有較大的研究空間。學者將SLPA算法[3]進行改進提出異質網絡重疊社區發現算法NELPA[4]。研究表明圖神經網絡(GNN)可以充分提取網絡中的各種信息，但傳統的GNN不能利用異質網絡不同的語義信息。本文基于GNN提出HAOCD(heterogeneous graph attention of overlapping community discovery)模型解決異質網絡中重疊社區發現問題，其中貢獻有以下幾點：①結合異質網絡多種元路徑的結構和屬性信息構建異質網絡的節點特征表示；②改變基于GNN的異質圖注意網絡(HAN)[5]中語義級注意的激活函數，解決梯度消失問題，并生成新的節點特征向量，更好利用異質網絡豐富語義信息；③通過圖卷積神經網絡[6](graph convolutional neural networks，GCN)生成社區隸屬矩陣，并將Bernoulli-Poisson(B-P)模型的負對數似然函數作為損失函數優化社區重疊度，并通過社區劃分的閾值得到最終異質網絡重疊社區劃分結果。

1 相關工作

1.1 圖神經網絡

圖神經網絡(GNN)的概念由Gori等提出，并由Scarselli等進一步闡明[7]，它具有對圖數據之間依賴關系進行建模的強大功能，并且可以對圖數據進行特征提取和表示[8]，可以用于節點分類、鏈路預測、社區發現等數據挖掘領域。

Bruna等基于譜圖論(spectral graph theory)提出了GCN。GCN與卷積神經網絡(CNN)本質上是一致的，都是將鄰域信息進行聚合計算。不同點是CNN處理的是以像素點排列成的歐幾里德結構的數據，而GCN處理的是由節點和邊構成的非歐幾里德結構的數據[9]，例如社交網絡、引文網絡等。

1.2 注意力機制

注意力機制在計算機各個領域都有大量的應用，包括機器翻譯、自然語言處理、圖像識別等領域。例如在機器翻譯領域，學者們發現上下文單詞對目標單詞的影響力不同，引入注意力模型(attention model，AM)可以得到不同單詞相對目標單詞的權重信息，來提高翻譯的準確性。通過注意力機制可以學習到不同信息的權重，更好利用影響力高的信息。注意力機制具有不同的類型包括自注意力、多頭注意力、硬注意力和軟注意力、全局注意力和局部注意力等機制[10]。

隨著圖神經網絡的提出，許多研究者將注意力機制與圖神經網絡結合并應用到各個領域中，并且相對傳統算法都有良好的表現。注意力機制結合圖神經網絡有多種形式應用，包括聚合特征信息時向不同近鄰分配注意力權重，根據注意力權重集成多個模型，以及使用注意力權重引導隨機游走等。圖注意力網絡(GAT)[11]是將GCN與注意力機制進行結合，根據不同鄰居節點特征對節點的影響力不同的特點，通過注意力機制得到不同鄰居節點的權重，充分利用影響力高的鄰居節點的特征聚合該節點的特征信息。

1.3 B-P模型

B-P模型是一種允許重疊社區的圖生成模型，通過B-P模型可以優化重疊社區發現結果。Mingyuan Zhou[12]提出的邊緣劃分模型(edge partition model)中首先提出了泊松因子模型。為了將提出的泊松因子模型用于具有二進制鄰接矩陣的非加權網絡，研究者提出了伯努利-泊松鏈(BerPo Link)。

伯努利-泊松鏈可以衡量不同節點與多個社區的關系，所以可以用于重疊社區發現。Shchur O等[13]基于伯努利-泊松鏈提出可用于重疊社區發現的B-P模型，其公式如式(1)所示

(1)

式中：Auv∈N×N是節點的鄰接矩陣；是社區隸屬矩陣。Fu是F的行向量。從公式可以看出點積越高，即節點u和節點v共有的社區越多，節點u，v越有可能通過邊連接。

同樣，Adrien等[14]提出可用于重疊社區的馬爾科夫鏈蒙特卡洛(Markov chain Monte Carlo)模型也應用了B-P模型，得到單個節點對每個社區從屬程度的權重信息。

2 HAOCD算法

2.1 相關概念

定義1 異質網絡：給定屬性網絡G(V，E，S，R)， 其中V={v1，v2，…，vn} 是n個節點集合；E是邊集，且|E|=m，m為總邊數；S為節點類型的集合；R為邊類型的集合。當網絡中節點類型滿足 |S|>1或關系類型滿足 |R|>1時，稱這樣的網絡為異質網絡。

定義2 重疊社區：將圖劃分為k個社區，將其定義為C={c1，c2，…，ck}。 若節點i∈c1且i∈c2， 即存在一個節點屬于多個社區。直觀的解釋是，一個作者可以在多個領域發表論文，一篇論文也可以同時屬于多個領域。

2.2 HAOCD算法的基本思想

本文提出基于異質圖注意力網絡的重疊社區發現方法HAOCD模型，先構建異質網絡架構，結合結構信息和屬性信息將不同類型的節點和特征嵌入到統一的特征空間，使圖神經網絡適用于異質網絡。然后基于異質圖注意力網絡，利用雙層注意力機制捕捉節點級的重要性和語義級的重要性，融合所有重要性信息得到節點的特征向量。新的節點特征向量充分結合了異質網絡不同類型節點的語義信息和重要性信息。然后將節點的特征向量經過GCN訓練和B-P模型重構損失得到最終的重疊社區隸屬關系矩陣。HAOCD模型圖如圖1所示。

圖1 HAOCD模型

2.3 基于異質圖注意力網絡的重疊社區發現算法

2.3.1 異質網絡特征表示

異質網絡包含豐富的結構信息和屬性信息，本文首先將不同類型的節點根據指定元路徑得到基于元路徑的結構信息，然后將基于元路徑的結構信息和節點的屬性信息結合構建異質網絡特征表示Hφi， 其公式如式(2)所示

Hφi=X·Aφi

(2)

式中：X表示節點的屬性信息，Aφi表示基于元路徑的結構信息。

2.3.2 異質圖注意力網絡

本文研究異質網絡的重疊社區發現算法，異質網絡中每個節點基于不同元路徑的鄰居具有不同的影響能力，而且不同元路徑包含的語義信息不同，對社區發現任務也具有不同影響。因此引入HAN，它具有節點級和語義級兩層注意力機制，捕捉節點級的重要性和語義級的重要性。本文將HAN的語義級注意的激活函數進行改進，采用RELU函數，解決訓練過程中梯度消失問題。HAN節點級和語義級注意機制的聚合過程如圖2所示。

(1)節點級注意力機制

(3)

(4)

(5)

從公式可以看出節點i基于元路徑φ的節點級注意的嵌入向量與它所有的一階鄰居節點有關。

由于單個元路徑的單個注意力，不夠穩定且圖數據方差大，所以本文使用多頭注意力，使訓練過程更加穩定，其公式如式(6)所示

(6)

式中：X為注意力頭數。最終得到P組基于不同元路徑的節點級嵌入向量，P為選取的不同元路徑的總數，嵌入向量表示為 {Zφ1，Zφ2，…，Zφp}， 節點級注意詳細過程如圖2所示。

圖2 異質圖注意力網絡雙層注意機制

(2)語義級注意

不同元路徑代表了不同的語義信息，對于社區發現任務，不同元路徑對社區發現結果也有不同的影響能力。為了更好的捕捉不同的語義信息，使用語義級注意自動學習不同元路徑對社區發現的重要性。將得到的P組基于不同元路徑的節點級嵌入向量 {Zφ1，Zφ2，…，Zφp} 作為輸入，通過語義級注意的神經網絡學習每個元路徑的權重，其公式如式(7)所示

{βφ1，βφ2…，βφp}=attsem(Zφ1，Zφ2…，Zφp}

(7)

式中：attsem表示語義級注意的圖神經網絡。

為了捕捉不同元路徑的重要性，利用結合語義級注意力機制的單層感知機，并且將ReLU函數作為激活函數，得到該元路徑對不同的節點的重要性，其公式如式(8)所示

ωφi=qT·f(Zφi)=qT·ReLU(W·Zφi+b)

(8)

式中：i∈P表示元路徑i；ωφi表示元路徑i對不同節點的重要性；f(·) 是所使用的單層感知機；ReLU(·) 是單層感知機所用的非線性激活函數；W是單層感知機的權值向量；b是單層感知機的偏差向量；q是語義級注意向量。

將特定元路徑對不同節點的重要性ωφi的平均值作為這條元路徑的重要性ωφi，其公式如式(9)所示

(9)

然后，上述得到的不同元路徑的重要性需要通過softmax函數進行歸一化處理，最終得到元路徑的權重系數βφi， 其公式如式(10)所示

(10)

利用學習到的權重系數與特定元路徑的嵌入進行融合聚集，獲得最終的節點特征嵌入，詳細過程如圖2所示，其公式如式(11)所示

(11)

2.3.3 圖卷積網絡

基于異質注意網絡得到了節點特征嵌入Z，然后以Z作為輸入數據經過GCN得到社區隸屬矩陣F，GCN的構成如式(12)所示

(12)

式中：A∈N×N是節點的鄰接矩陣；是結合自循環的鄰接矩陣；ReLU(·) 是非線性激活函數可以確保F的非負性；W是權重矩陣。

接著，將B-P模型的負對數似然作為損失函數，并且最小化B-P模型的負對數似然來優化社區隸屬矩陣F，其公式如式(13)所示

(13)

得到最終的社區隸屬矩陣后，設置一個固定閾值ρ， 進行二元社區分配。具體過程為，如果節點i的隸屬強度Fuv高于固定閾值ρ， 將節點i分配給社區c。

3 實驗與結果分析

為了驗證異質網絡重疊社區發現HAOCD模型的有效性和可行性，本文選取了2個真實異質網絡數據集和2個同質網絡數據集與傳統社區發現算法和其它基于圖神經網絡的算法進行對比實驗分析。

3.1 相關數據集介紹

本文選取了DBLP、IMDB兩個真實異質網絡數據集和兩個同質網絡Facebook數據集。下面詳細敘述這幾個數據集，其參數見表1。

表1 數據集參數

DBLP數據集。此數據集是經典的記錄計算機領域文獻的數據集。本文選取DBLP-FOUR-AREA中的一個子集，包含作者(Author)、論文(Paper)、會議(Confe-rence)、術語(Term)4種類型的節點。作者分為數據庫、數據挖掘、信息檢索、機器學習4個領域。作者特征是由關鍵字組成的單詞包構成。

IMDB數據集。此數據集是經典的電影數據集。本文選取IMDB中的一個子集，包含電影(Movie)、導演(Director)、演員(Actor)3種類型的節點。電影分為動作片、喜劇片、戲劇片3種類型。電影的特征是由情節組成的單詞包元素構成。

Facebook數據集1(F1)和Facebook數據集2(F2)。此數據集是社交網絡數據集。本文選取Facebook網絡中兩個小型同質網絡數據集。Facebook用戶為網絡中的節點，社區由真實人際關系構成。用戶的特征由用戶的信息構成。

通過對節點類型、元路徑語義、元路徑長度的充分考慮與分析，在DBLP數據集選取APA、APCPA、APTPA這3條元路徑信息，在IMDB數據集選取MDM、MAM兩條元路徑信息。

3.2 評價指標

社區發現的評價指標大致分為兩類：一類是需要真實社區劃分結果，例如標準化互信息NMI值和準確率precsion；另一類不需要真實社區劃分結果，例如模塊度Q。模塊度Q是經典的社區發現評價指標，通過計算同一社區和不同社區之間邊的關系，可以衡量社區發現的穩定度。擴展模塊度EQ考慮了社區之間的重疊節點，適用于重疊社區發現算法。

本文所研究異質網絡重疊社區發現算法，選擇不需真實社區發現結果的評價指標擴展模塊度EQ，并且根據異質網絡不同節點類型的特點，結合特定元路徑的鄰接矩陣和元路徑權重系數，將擴展模塊度EQ函數改進為EQ*，其公式如式(14)所示

(14)

3.3 對比算法

本文提出的HAOCD模型與傳統社區發現算法SLPA，異質網絡重疊社區發現方法NELPA，基于圖神經網絡的算法GAT、HAN、NOCD進行對比。

SLPA：是一種傳統的重疊社區發現算法，是LPA[16](標簽傳播算法)的擴展，它通過記錄每次迭代所分配的社區來實現重疊社區發現。

NELPA：是一種基于SLPA的異質網絡重疊社區發現算法，首先通過Metapath2vec異質網絡嵌入方法獲得節點嵌入向量，然后改進SLPA算法實現重疊社區發現。

GAT：一種基于圖神經網絡結合注意力機制的同質網絡圖嵌入方法，得到節點嵌入之后采用K-MEANS方法進行聚類得到社區發現結果。

HAN：一種基于圖神經網絡結合注意力機制的異質圖嵌入方法，同樣采用K-MEANS方法對得到的節點嵌入進行聚類得到社區發現結果。

NOCD：一種同質網絡中基于圖神經網絡的重疊社區發現方法，采用B-P模型重構損失，使得到的社區結果更接近真實社區。

3.4 實驗結果與分析

3.4.1 實驗過程

對于基線算法，SLPA和NELPA算法設置標簽閾值r為0.35。GAT算法設置注意力頭X的數量為8。HAN算法設置注意力頭X的數量為8，語義級注意向量q的維數為128。NOCD算法設置固定閾值ρ為0.5。為了對比實驗的統一性，所有算法都采用100patience的提前停止策略。并都使用改進過的擴展模塊度EQ*作為標準對實驗結果進行測評。

3.4.2 參數分析

本文對兩個異質網絡數據集DBLP和IMDB進行實驗，從模型的注意力頭數X，語義級注意向量維度q，社區劃分閾值ρ這3個參數進行分析。

本文研究不同注意力頭數量X對社區劃分結果的影響，X的數量影響節點級注意力機制過程的權重的生成，多個注意力頭會學習到不同的節點權重信息并加以整合。以X=1作為初始實驗參數，即只有單一注意力頭。通過圖3參數分析圖可以看出，當X=1時，EQ*=0.65(DBLP)和EQ*=0.35(IMDB)，相對多頭注意力EQ*值偏低，原因是單個注意力頭可能導致注意力機制學習到的權重不穩定。兩個實驗都可表明注意力頭數越多，EQ*值越高，即社區劃分結果更好。但當X>8時，DBLP實驗中EQ*值增長緩慢，IMDB實驗中EQ*值略有下降，并且注意力頭數過多會使模型過于復雜，因此選取X=8作為不同數據集的注意力頭數設置。研究語義級注意力向量的維度q對社區劃分結果的影響，q的維度影響語義級注意力機制過程的權重的生成，維度越大權重信息表示越豐富。以q=32作為初始實驗參數，之后成倍增加語義級注意力向量的維度。通過兩個數據集的實驗可以看出，當維度q設置為128時，EQ*值最高。當q>128時，EQ*值都呈降低趨勢這可能是因為過擬合導致語義級注意力權重信息不準確，因此選取q=128作為最終的參數設置。社區劃分閾值ρ的設置直接影響最后社區劃分結果，ρ的取值偏大或偏小都會導致社區劃分出現較大偏差。以ρ=0.1作為初始實驗參數，依次獲取閾值ρ在0.1，0.3，0.5，0.7，0.9取值的實驗結果。通過兩個數據集的實驗可以看出當閾值ρ=0.5時EQ*值更高，說明此時社區發現結果更準確，因此選取ρ=0.5作為最終的閾值設置。

圖3 HAOCD模型的參數分析

3.4.3 實驗結果

圖4展示了本文提出的HAOCD模型與SLPA、GAT、HAN、NOCD、NELPA算法在DBLP、IMDB兩個異質網絡數據集和兩個同質網絡數據集F1、F2上進行的實驗對比結果，并采用EQ*作為評價指標。

圖4 6種社區發現模型EQ*值對比

從兩個異質網絡數據集的實驗中可以看出，本文提出的模型相比傳統社區發現算法和基于GNN的社區發現方法都有一定程度的提升。傳統社區發現方法SLPA在DBLP數據集實驗中EQ*值只有0.35，IMDB數據集中EQ*為0.109。SLPA相對基于GNN的社區發現方法，不僅EQ*值偏低，而且所得結果不穩定。這可能與SLPA只利用了網絡的結構信息進行社區發現，沒有結合網絡節點的特征信息有關。與基于GNN的算法不同的是，NELPA算法是通過Metapath2vec異質網絡嵌入方法將異質網絡的結構信息和屬性信息結合并抽取不同元路徑的特征信息，然后經過SLPA算法實現重疊社區劃分。本文提出的HAOCD模型與NELPA算法相比也有小幅度提升。HAOCD模型基于GNN可以充分挖掘異質信息網絡的節點信息和語義信息，具有較高的社區發現準確率。實驗結果表明基于GNN社區發現方法在DBLP實驗中EQ*值都大于0.6，表示基于GNN的社區發現算法可以更好結合網絡的節點特征信息和結構信息并提高社區發現準確性。

HAOCD模型在與基于GNN的算法GAT、HAN、NOCD的對比中也有不同程度提高。GAT可以通過注意力機制得到鄰居節點的權重，更新節點特征嵌入，但是沒有利用異質網絡的特點。HAN提出的雙層注意力機制可以更好地利用異質網絡的語義信息，但是沒有關注到網絡中存在的重疊社區現象。HAN與GAT相比在DBLP、IMDB實驗中EQ*值都提升了大約10%，可以表明基于異質網絡進行社區發現可以充分利用網絡中的語義信息并使社區發現結果更準確。NOCD基于圖神經網絡結合B-P模型，關注到網絡中的重疊社區現象，但是沒有利用異質網絡中的不同語義信息。本文提出的算法HAOCD相比其它基于GNN算法在IMDB實驗中EQ*值提升明顯，大約提升了20%，在DBLP實驗中也提升了大約5%。HAOCD模型通過注意力機制充分提取異質網絡的語義信息，并關注到社區中的重疊現象采用重疊生成模型B-P模型。

HAOCD算法在同質網絡數據集F1、F2的實驗中也有類似的結果。在同質網絡數據集實驗中HAOCD算法相對傳統社區發現算法SLPA提升了大約20%，相對基于GNN的算法和NELPA算法提升了大約5%。因此實驗結果表明HAOCD模型將異質圖注意力網絡與重疊生成模型B-P模型進行有效結合，不僅可以充分利用異質網絡中的語義信息進行異質網絡重疊社區發現并使社區發現結果接近真實社區，也可用于同質網絡社區發現，提升社區發現的準確率。

4 結束語

本文研究基于異質圖注意力網絡的重疊社區發現問題，并提出了HAOCD模型。該模型首先基于改進的異質圖注意力網絡融合基于元路徑鄰居節點的權重和不同元路徑的權重得到新的節點特征嵌入向量，然后通過圖卷積網絡結合B-P模型得到社區隸屬矩陣，最后通過社區劃分閾值取得最終社區發現結果。將提出的模型與傳統社區發現方法SLPA和基于圖神經網絡的方法GAT、HAN、NOCD進行實驗對比并以改進過的EQ*作為評價指標，結果顯示HAOCD模型在真實數據集DBLP、IMDB、F1和F2上均有良好的表現。

但是，HAOCD模型只考慮了異質網絡中節點類型不同的問題，但異質網絡還存在關系類型不同的特點，所以未來可以全面考慮異質網絡中節點類型和關系類型不同的特點，更好利用網絡中的信息進行社區發現。