基于梯度的重疊式層次社區檢測①

王寒蕊,丁岱宗,張 謐

(復旦大學 軟件學院,上海 200438)

長期以來,社區檢測一直是數據挖掘領域的一個研究熱點.該任務旨在基于僅由節點和邊構成的圖數據,將相似的節點聚集到社區當中,完成節點-社區隸屬關系的分配,期望社區內點的連接相比社區外更密集.例如在論文引用關系網絡中,相似方向的論文會被分到同一小組[1,2];在網頁超鏈接網絡中,相似內容的網頁將被聚集[3].該任務在刻畫圖數據的社區分布形態的同時,也影響了很多其他圖學習任務的發展,例如圖表示學習和圖鏈路預測任務等.

目前的社區檢測算法主要分為兩類:非重疊式和重疊式的社區檢測[4,5].非重疊式社區檢測的目標是識別不相交的社區,但社區不相交的假設在很多數據集上是難以成立的.例如在社交網絡中,一個人可能因為身份或興趣的多樣而同時歸屬于多個社區.因此社區間存在相交關系,這種重疊式的社區分布在假設上更合理[6].重疊的假設意味著社區檢測算法需要對每個節點學習更多的信息,因而帶來了更高的復雜性挑戰.近幾年很多研究工作[2,4,5,7]都著眼于重疊式的社區檢測,證實了重疊式的社區建模能帶來更精準的結果.

隨著圖數據的多樣化和復雜化,不論是非重疊還是重疊的社區分布,這類傳統的平坦式社區分布形態已經不能很好的描述復雜圖數據的社區分布,復雜網絡中的社區結構通常是分層的[8].針對這個問題,之前研究提出,在社區檢測的基礎上,用一棵樹來表達社區之間的層級關系[9,10].在優化的過程中,需要把網絡中的節點劃分到樹上的不同社區中.例如Bhowmick和Meneni 等[9]提出基于Louvain[11]算法遞歸的劃分網絡,從而將較大的社區拆解為小的社區,求解節點屬于樹上每一層的哪個社區[9].

但是現有層次化社區檢測方法都只能建模非重疊的社區分布,這使得這些方法很難更加精準的描述網絡結構.舉例來說,在論文作者合著關系圖數據中,同時在多個領域有研究工作的作者,在平坦社區結構中,會同時歸屬于多個社區;在層次社區結構中,其歸類應比單一領域內緊密合作的作者社區具有更高的層次等級.如圖1所示,一些同時涉獵計算機視覺(CV)多個領域的作者與具體領域的作者相比應具有更高等級;同時和計算機視覺,自然語言處理(NLP)多個任務領域合作的作者,應比單任務領域的作者們具有更高等級,因此用重疊式層次結構描述該數據的社區形態是必要的.重疊式層次化社區檢測任務的主要難點在于,由于層次結構建模問題本身被證明是一個NP 問題[12],所以之前方法通常都用啟發式算法來求解,在此基礎上就很難再加入重疊信息的建模.

圖1 基于論文合著(coauthor)部分數據的3 種社區結構

在這篇文章中,我們提出利用圖表示學習來解決這個問題.具體而言,我們利用了節點嵌入表示學習[13,14],把每個節點映射到一個實數向量上,利用這些向量來描述圖的拓撲結構,然后與層次化重疊社區檢測做聯合建模,從而同時求得兩個任務上的解.

為了實現上述框架,在本文中,對于如何聯合優化節點嵌入和重疊式層次社區檢測任務,我們提出了輕量的解決方案:首先,我們將社區的層次結構定義為一顆樹的形態,稱之為社區樹,該樹上層的社區具有更高的層次等級.其次,給定一顆社區樹,自定義基于節點嵌入和層次結構的距離算法,通過最小化有鏈接的成對節點間的距離,完成節點嵌入和社區嵌入表示的更新,以及節點-社區隸屬關系的分配.我們的方法可以靈活的適應任意的層次結構,不受深度和寬度的限制.與之前非重疊層次化社區檢測算法相比,我們的優勢在于:

(1)我們是第一個可以對節點嵌入和層次化社區檢測任務做聯合建模的方法.之前工作表明,節點嵌入與社區檢測任務是高度相關的,聯合建模會帶來互惠的優勢:① 節點嵌入將離散的數據映射到連續的高維空間中,可以捕獲局部信息,為社區檢測任務提供支持[1,2,7];② 社區檢測的節點-社區隸屬關系可以為節點嵌入提供全局信息[1,7].實驗證明了我們框架的有效性.

(2)我們是第一個在層次化社區檢測中應用梯度下降的算法.之前的層次化檢測方法通常使用啟發式學習來把每個節點映射到一個社區上.但是,啟發式方法往往是分離的優化過程,無法和其它有效的連續優化算法組合獲得更好的結果.另一方面,基于梯度的連續優化方法不僅可以靈活的與任意相關任務組合優化,還可以有效地在專用硬件(例如GPU)上運行.

后文組織如下:第1 節介紹層次社區檢測任務定義;第2 節介紹自適應的重疊式層次社區檢測方法;第3 節介紹實驗設置以及實驗結果;第4 節進行總結.

1 層次社區檢測任務

對于包含N個節點的無向同質圖G=(V,E),其中V表示節點,滿足|V|=N;E表示邊.對于任意一對節點vi,vj∈V都存在一條邊eij∈E且eij={0,1},eij=0表示邊不存在,否則存在.

對于包含t個社區的社區樹Tt,樹上的每個葉節點和非葉節點都表示社區c=1,2,···,t.非重疊式社區樹和重疊式社區樹的區別在于:前者的每個非葉節點社區僅是底層社區的合并;后者的非葉節點社區是包含若干節點的獨立社區,其內部節點無法被下分到任意低層社區中.

層次社區檢測任務的目標是:基于給定的任意形態的社區樹Tt和圖G的鏈路關系信息E,為每個圖節點vi找到最合適的歸屬社區ci,使得每個社區內節點間邊的密度遠高于社區間邊的密度.

之前啟發式的工作[9,10]采用貪心策略或遺傳算法做出決策,但實際上是分離的兩步策略,簡單來說:(1)首先進行圖節點嵌入表示學習,通過映射函數F:vi→φi∈Rd將圖節點vi從原始離散空間映射到d維連續空間.對于任意有真實連接關系的eij=1的節點vi和vj,其嵌入向量φi和φj在空間上的距離應該盡可能的近,反之亦然.(2)隨后,利用節點嵌入表示啟發式地探索層次社區結構.這種分離的策略不能使得節點嵌入和社區檢測兩個任務互利互惠[1,2,7],此外,非重疊社區分布假設的不合理性限制了這些工作僅能建模簡單的淺層非重疊式社區樹.

為了更合理的描述復雜圖數據的社區分布,我們提出建模重疊式層次社區結構,部分圖節點vi只隸屬于社區樹Tt中的非葉節點社區,表示重疊部分.為了消解層次結構和重疊結構帶來的建模難題,我們引入圖表示學習任務來構建雙任務優化模型,任務目標是:

(1)學習節點-社區一一對應的隸屬關系.

(2)學習節點和社區的d維嵌入表示.

基于這樣的定義,不僅可以獲得圖數據的層次社區分布,為不同粒度的分析任務提供支持;也可以獲得其節點的嵌入表示,應用于豐富的下游任務.

2 基于梯度的重疊式層次社區檢測算法

對于固定的重疊式社區樹Tt,我們需要在嵌入表示信息的指引下,將圖節點放置到社區樹的不同社區中,形成節點-社區的隸屬關系;同時需要根據分配的隸屬關系,更新節點和社區的嵌入表示.

2.1 節點-社區隸屬關系的分配

我們定義圖節點vi歸屬于社區c=1,2,···,t的概率服從多項式分布:P(C|vi)=ρic,其中ρic∈[0,1]且

為了使得節點和社區的嵌入表示能夠指導節點-社區隸屬關系的分配,我們將節點和社區嵌入到相同的表示空間當中,基于空間距離決策隸屬關系.因此,進一步定義圖節點vi∈V的d維嵌入表示為φi∈Rd,社區c={1,2,···,t}的d維嵌入表示為φc∈Rd.通過將節點和社區從原始不同的離散空間嵌入映射到相同的d維連續空間,可以定義節點vi歸屬于社區c的概率為空間內兩向量的乘積:

2.2 節點和社區嵌入表示的學習

為了和原始數據盡可能保持一致,我們期望在圖數據中有真實連接eij=1的節點vi和vj,在社區樹Tt上的距離盡可能相近.由于層次社區檢測任務和節點嵌入表示任務分別描述了圖數據的整體分配和局部信息,因此在雙任務聯合優化時,我們同時考慮成對節點隸屬社區的距離和它們嵌入表示的距離,提出了成對節點的距離計算方法.

當給定一對節點vi和vj時,根據節點和社區的嵌入表示,可以獲得節點-社區隸屬關系的概率 ρic和ρjc,分別選取概率最大的社區ci和cj作為社區樹Tt上的隸屬社區.社區間的距離Λ (ci,cj)被定義為:

其中,co為社區ci和cj在 樹上的最小公共祖先,distance(·,·)表示樹上兩節點的最短路徑長度.因此我們定義節點vi和vj在社區樹上的距離:

其中,Λ ∈Rt×t是社區樹上所有社區的距離矩陣,ρi∈Rt是節點vi隸屬社區概率 ρic的向量表示.我們的目標是期望有真實連接的成對節點vi和vj在社區樹上的距離dij盡可能小,反之亦然,因此損失函數為:

其中,eij=1,eik=0;β是一個大于0的常數,用于控制正負樣本的差距.基于這樣的正負樣本距離損失函數,可以在學習過程中不斷更新節點和社區的嵌入表示,,從而更新節點基于社區樹的概率分布,最終獲得節點-社區的最優隸屬關系.

2.3 完整的基于梯度的優化框架

基于給定的一顆重疊式社區樹,可以通過節點和社區的嵌入表示計算節點-社區隸屬關系,進而計算成對節點間的距離.通過最小化距離損失來調整節點和社區的嵌入表示,更新隸屬關系.如圖2所示,反復這一學習過程直至收斂,就可得到最終解.

圖2 基于梯度的重疊式層次社區檢測算法

整體的算法描述如算法1.

算法1.基于梯度的重疊式層次社區檢測算法1) 初始化:給定真實圖數據,定義重疊式社區樹和距離矩陣.隨機生成圖節點和社區的維嵌入表示.φ,φ{ρic}t+1 c=1 G=(V,E) Tt Λtd φ,φ 2) 基于節點和社區的嵌入表示 計算節點-社區隸屬概率,確認隸屬關系.{ρic}t+1 c=1 dij 3) 基于隸屬關系 計算節點間距離.?(φ,φ) Λt φ,φ {ρic}t+1 c=1 4) 基于損失函數,和距離矩陣 更新節點和社區的嵌入表示以及隸屬關系.5) 循環過程2)-4)直至收斂.

上述算法展示了如何基于自定義的距離計算方式,自適應任意的重疊式層次結構,進行節點嵌入表示學習和節點-社區隸屬關系分配.兩個基于圖數據的基礎任務共享知識,互相指引,實現了端到端的聯合優化模型,兩個任務的表現共同得到了提升.

值得注意的是,我們將所有的距離計算融合為矩陣計算,極大的提升了算法效率.

3 實驗分析

3.1 實驗設置

我們分別使用Aminer 數據集[15]和Wiki-vote 數據集進行了實驗.Aminer 數據集是從dblp 學術論文網站收集的4258 615 組引文(cocitation)關系,以及相應的論文信息和作者信息.我們去除了沒有任何引用關系的論文數據后,共獲得包含12 840 個節點和190 658條邊.Wiki-vote 數據集是維基百科數據集,包含3135 個節點和95 028 條邊.

我們使用6 種社區檢測算法作為基線模型:

ComE[2]和MNMF[7]:重疊式的平坦社區檢測算法.兩者都與節點嵌入任務聯合建模,前者基于重疊的高斯分布假設,后者基于非負矩陣分解.

HCDE[10]和LouvainNE[9]:非重疊式的層次社區檢測算法.HCDE 預先用圖學習算法,例如LINE[14],獲得節點的嵌入表示,再自頂向下地用啟發式的策略構建節點-社區隸屬關系.LouvainNE 自頂向下遞歸地利用Louvain[11]算法進行層次化社區構建,隨后再根據社區樹單獨學習節點的嵌入表示.

為了觀察先驗知識擾動對我們模型的影響,我們分別設計了Ours-Wide,Ours-Deep和Ours-Comb.3 種基于廣度樹,深度樹和組合樹的重疊式層次社區檢測算法,僅社區層次結構的表達形式不一致.

我們用以下兩組指標來評估模型在社區檢測任務和節點嵌入下游任務的表現:

Modularity:評估得到的節點-社區隸屬關系是否符合社區檢測任務模塊化的要求.它的值越高,就意味著越多有密集關聯的節點被分配到同一社區當中,社區檢測的結果越好.

AUC:為評估節點嵌入表示在下游鏈路預測任務上的表現力,我們通過嵌入表示計算成對節點的相似度,并映射到[0,1]區間內,結合多種閾值設定和成對節點的真實標簽計算AUC的值,該值越高意味著預測結果越準確.

此外,我們對層次社區結構進行可視化展示,以證明我們模型的層次結構建模能力.

3.2 實驗結果

我們按照7:1:2的比例劃分了訓練、驗證和測試數據集,并以正樣本兩倍的數量隨機采樣負樣本,采用10-fold 交叉驗證的方式來確定最優參數.我們定義社區數量在15-20 之間,訓練過程中使用學習率為0.003的Adma 優化器[16].表1展示了4 組模型在社區檢測任務和鏈路預測任務上的結果.

表1 不同模型的實驗結果

我們首先根據4 組模型的社區檢測結果來考量這些社區的模塊化程度:(1) 重疊式平坦模型ComE和MNMF的模塊化程度整體上是高于非重疊模型SCD和vGraph的,這表明了重疊社區建模的優勢;(2)非重疊層次模型HCDE和LouvainNE的效果持平或略差于SCD和vGraph,這是因為沒有利用圖表示學習進行雙任務聯合優化,因此效果略差;(3)我們的3 種重疊式層次社區檢測算法在兩組數據集上的結果均優于基線模型,這也進一步說明了層次社區結構和重疊社區分布的合理性.

其次,我們需要驗證節點嵌入表示在下游鏈路預測任務上競爭力:(1)重疊式平坦模型MNMF的AUC值高于非重疊模型vGraph,這表明了重疊式社區分布假設的優勢.ComE的值沒有競爭力是因為模型側重于社區建模,SCD 沒有節點嵌入表示學習建模的部分;(2) 非重疊層次模型HCDE和LouvainNE的效果與vGraph 持平或更差,其原因是啟發式算法節點嵌入表示和社區檢測分離的優化方式競爭力不足;(3)我們的模型與所有基線模型相比同樣具有強勁的競爭力,這證明了重疊式層次社區分布假設的合理性,以及節點嵌入和社區檢測雙任務可以達到雙贏的效果.

此外,我們發現在基于不同形態的層次結構時,不論是純粹的深度樹(deep)還是廣度樹(wide)其社區模塊化程度和下游任務效果都沒有深廣度組合樹(Comb.)好,這意味著一份數據集內不同的社區可被細分的粒度是不一致的,有些傾向于細分為多類,有些傾向于細分為更多的層次,這是一種合理的現象.

3.3 社區分布可視化展示

我們利用t-SNE 技術[17]將節點的嵌入表示從高維空間映射到二維空間.以假設存在15 個社區的Aminer數據集為例,為屬于同社區的節點賦予相同的顏色進行可視化展示.圖3展示了基線算法和我們的社區樹.這3 個模型的社區模塊化程度都較高,相同顏色的點都比較聚集.但我們的模型學習出了基于任意層次結構模型的節點-社區隸屬關系分布.

圖3 社區分布可視化展示

4 結論與展望

本文提出了一種基于梯度的重疊式層次社區檢測算法,在層次結構未知的情況下,通過梯度更新的方式聯合優化節點嵌入表示和社區檢測任務,靈活地探索節點和重疊式層次社區的隸屬關系.我們提供了多樣化的實驗結果以及社區樹的可視化形態,均證明了該算法的有效性.接下來,我們將考慮如何利用基于梯度的優化方式和強化學習等技術,幫助模型自動探索層次結構,不必受到獲取先驗知識的成本約束.