基于梯度的重疊式層次社區(qū)檢測(cè)①

王寒蕊,丁岱宗,張 謐

(復(fù)旦大學(xué) 軟件學(xué)院,上海 200438)

長(zhǎng)期以來(lái),社區(qū)檢測(cè)一直是數(shù)據(jù)挖掘領(lǐng)域的一個(gè)研究熱點(diǎn).該任務(wù)旨在基于僅由節(jié)點(diǎn)和邊構(gòu)成的圖數(shù)據(jù),將相似的節(jié)點(diǎn)聚集到社區(qū)當(dāng)中,完成節(jié)點(diǎn)-社區(qū)隸屬關(guān)系的分配,期望社區(qū)內(nèi)點(diǎn)的連接相比社區(qū)外更密集.例如在論文引用關(guān)系網(wǎng)絡(luò)中,相似方向的論文會(huì)被分到同一小組[1,2];在網(wǎng)頁(yè)超鏈接網(wǎng)絡(luò)中,相似內(nèi)容的網(wǎng)頁(yè)將被聚集[3].該任務(wù)在刻畫圖數(shù)據(jù)的社區(qū)分布形態(tài)的同時(shí),也影響了很多其他圖學(xué)習(xí)任務(wù)的發(fā)展,例如圖表示學(xué)習(xí)和圖鏈路預(yù)測(cè)任務(wù)等.

目前的社區(qū)檢測(cè)算法主要分為兩類:非重疊式和重疊式的社區(qū)檢測(cè)[4,5].非重疊式社區(qū)檢測(cè)的目標(biāo)是識(shí)別不相交的社區(qū),但社區(qū)不相交的假設(shè)在很多數(shù)據(jù)集上是難以成立的.例如在社交網(wǎng)絡(luò)中,一個(gè)人可能因?yàn)樯矸莼蚺d趣的多樣而同時(shí)歸屬于多個(gè)社區(qū).因此社區(qū)間存在相交關(guān)系,這種重疊式的社區(qū)分布在假設(shè)上更合理[6].重疊的假設(shè)意味著社區(qū)檢測(cè)算法需要對(duì)每個(gè)節(jié)點(diǎn)學(xué)習(xí)更多的信息,因而帶來(lái)了更高的復(fù)雜性挑戰(zhàn).近幾年很多研究工作[2,4,5,7]都著眼于重疊式的社區(qū)檢測(cè),證實(shí)了重疊式的社區(qū)建模能帶來(lái)更精準(zhǔn)的結(jié)果.

隨著圖數(shù)據(jù)的多樣化和復(fù)雜化,不論是非重疊還是重疊的社區(qū)分布,這類傳統(tǒng)的平坦式社區(qū)分布形態(tài)已經(jīng)不能很好的描述復(fù)雜圖數(shù)據(jù)的社區(qū)分布,復(fù)雜網(wǎng)絡(luò)中的社區(qū)結(jié)構(gòu)通常是分層的[8].針對(duì)這個(gè)問(wèn)題,之前研究提出,在社區(qū)檢測(cè)的基礎(chǔ)上,用一棵樹(shù)來(lái)表達(dá)社區(qū)之間的層級(jí)關(guān)系[9,10].在優(yōu)化的過(guò)程中,需要把網(wǎng)絡(luò)中的節(jié)點(diǎn)劃分到樹(shù)上的不同社區(qū)中.例如Bhowmick和Meneni 等[9]提出基于Louvain[11]算法遞歸的劃分網(wǎng)絡(luò),從而將較大的社區(qū)拆解為小的社區(qū),求解節(jié)點(diǎn)屬于樹(shù)上每一層的哪個(gè)社區(qū)[9].

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

圖1 基于論文合著(coauthor)部分?jǐn)?shù)據(jù)的3 種社區(qū)結(jié)構(gòu)

在這篇文章中,我們提出利用圖表示學(xué)習(xí)來(lái)解決這個(gè)問(wèn)題.具體而言,我們利用了節(jié)點(diǎn)嵌入表示學(xué)習(xí)[13,14],把每個(gè)節(jié)點(diǎn)映射到一個(gè)實(shí)數(shù)向量上,利用這些向量來(lái)描述圖的拓?fù)浣Y(jié)構(gòu),然后與層次化重疊社區(qū)檢測(cè)做聯(lián)合建模,從而同時(shí)求得兩個(gè)任務(wù)上的解.

為了實(shí)現(xiàn)上述框架,在本文中,對(duì)于如何聯(lián)合優(yōu)化節(jié)點(diǎn)嵌入和重疊式層次社區(qū)檢測(cè)任務(wù),我們提出了輕量的解決方案:首先,我們將社區(qū)的層次結(jié)構(gòu)定義為一顆樹(shù)的形態(tài),稱之為社區(qū)樹(shù),該樹(shù)上層的社區(qū)具有更高的層次等級(jí).其次,給定一顆社區(qū)樹(shù),自定義基于節(jié)點(diǎn)嵌入和層次結(jié)構(gòu)的距離算法,通過(guò)最小化有鏈接的成對(duì)節(jié)點(diǎn)間的距離,完成節(jié)點(diǎn)嵌入和社區(qū)嵌入表示的更新,以及節(jié)點(diǎn)-社區(qū)隸屬關(guān)系的分配.我們的方法可以靈活的適應(yīng)任意的層次結(jié)構(gòu),不受深度和寬度的限制.與之前非重疊層次化社區(qū)檢測(cè)算法相比,我們的優(yōu)勢(shì)在于:

(1)我們是第一個(gè)可以對(duì)節(jié)點(diǎn)嵌入和層次化社區(qū)檢測(cè)任務(wù)做聯(lián)合建模的方法.之前工作表明,節(jié)點(diǎn)嵌入與社區(qū)檢測(cè)任務(wù)是高度相關(guān)的,聯(lián)合建模會(huì)帶來(lái)互惠的優(yōu)勢(shì):① 節(jié)點(diǎn)嵌入將離散的數(shù)據(jù)映射到連續(xù)的高維空間中,可以捕獲局部信息,為社區(qū)檢測(cè)任務(wù)提供支持[1,2,7];② 社區(qū)檢測(cè)的節(jié)點(diǎn)-社區(qū)隸屬關(guān)系可以為節(jié)點(diǎn)嵌入提供全局信息[1,7].實(shí)驗(yàn)證明了我們框架的有效性.

(2)我們是第一個(gè)在層次化社區(qū)檢測(cè)中應(yīng)用梯度下降的算法.之前的層次化檢測(cè)方法通常使用啟發(fā)式學(xué)習(xí)來(lái)把每個(gè)節(jié)點(diǎn)映射到一個(gè)社區(qū)上.但是,啟發(fā)式方法往往是分離的優(yōu)化過(guò)程,無(wú)法和其它有效的連續(xù)優(yōu)化算法組合獲得更好的結(jié)果.另一方面,基于梯度的連續(xù)優(yōu)化方法不僅可以靈活的與任意相關(guān)任務(wù)組合優(yōu)化,還可以有效地在專用硬件(例如GPU)上運(yùn)行.

后文組織如下:第1 節(jié)介紹層次社區(qū)檢測(cè)任務(wù)定義;第2 節(jié)介紹自適應(yīng)的重疊式層次社區(qū)檢測(cè)方法;第3 節(jié)介紹實(shí)驗(yàn)設(shè)置以及實(shí)驗(yàn)結(jié)果;第4 節(jié)進(jìn)行總結(jié).

1 層次社區(qū)檢測(cè)任務(wù)

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

對(duì)于包含t個(gè)社區(qū)的社區(qū)樹(shù)Tt,樹(shù)上的每個(gè)葉節(jié)點(diǎn)和非葉節(jié)點(diǎn)都表示社區(qū)c=1,2,···,t.非重疊式社區(qū)樹(shù)和重疊式社區(qū)樹(shù)的區(qū)別在于:前者的每個(gè)非葉節(jié)點(diǎn)社區(qū)僅是底層社區(qū)的合并;后者的非葉節(jié)點(diǎn)社區(qū)是包含若干節(jié)點(diǎn)的獨(dú)立社區(qū),其內(nèi)部節(jié)點(diǎn)無(wú)法被下分到任意低層社區(qū)中.

層次社區(qū)檢測(cè)任務(wù)的目標(biāo)是:基于給定的任意形態(tài)的社區(qū)樹(shù)Tt和圖G的鏈路關(guān)系信息E,為每個(gè)圖節(jié)點(diǎn)vi找到最合適的歸屬社區(qū)ci,使得每個(gè)社區(qū)內(nèi)節(jié)點(diǎn)間邊的密度遠(yuǎn)高于社區(qū)間邊的密度.

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

為了更合理的描述復(fù)雜圖數(shù)據(jù)的社區(qū)分布,我們提出建模重疊式層次社區(qū)結(jié)構(gòu),部分圖節(jié)點(diǎn)vi只隸屬于社區(qū)樹(shù)Tt中的非葉節(jié)點(diǎn)社區(qū),表示重疊部分.為了消解層次結(jié)構(gòu)和重疊結(jié)構(gòu)帶來(lái)的建模難題,我們引入圖表示學(xué)習(xí)任務(wù)來(lái)構(gòu)建雙任務(wù)優(yōu)化模型,任務(wù)目標(biāo)是:

(1)學(xué)習(xí)節(jié)點(diǎn)-社區(qū)一一對(duì)應(yīng)的隸屬關(guān)系.

(2)學(xué)習(xí)節(jié)點(diǎn)和社區(qū)的d維嵌入表示.

基于這樣的定義,不僅可以獲得圖數(shù)據(jù)的層次社區(qū)分布,為不同粒度的分析任務(wù)提供支持;也可以獲得其節(jié)點(diǎn)的嵌入表示,應(yīng)用于豐富的下游任務(wù).

2 基于梯度的重疊式層次社區(qū)檢測(cè)算法

對(duì)于固定的重疊式社區(qū)樹(shù)Tt,我們需要在嵌入表示信息的指引下,將圖節(jié)點(diǎn)放置到社區(qū)樹(shù)的不同社區(qū)中,形成節(jié)點(diǎn)-社區(qū)的隸屬關(guān)系;同時(shí)需要根據(jù)分配的隸屬關(guān)系,更新節(jié)點(diǎn)和社區(qū)的嵌入表示.

2.1 節(jié)點(diǎn)-社區(qū)隸屬關(guān)系的分配

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

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

2.2 節(jié)點(diǎn)和社區(qū)嵌入表示的學(xué)習(xí)

為了和原始數(shù)據(jù)盡可能保持一致,我們期望在圖數(shù)據(jù)中有真實(shí)連接eij=1的節(jié)點(diǎn)vi和vj,在社區(qū)樹(shù)Tt上的距離盡可能相近.由于層次社區(qū)檢測(cè)任務(wù)和節(jié)點(diǎn)嵌入表示任務(wù)分別描述了圖數(shù)據(jù)的整體分配和局部信息,因此在雙任務(wù)聯(lián)合優(yōu)化時(shí),我們同時(shí)考慮成對(duì)節(jié)點(diǎn)隸屬社區(qū)的距離和它們嵌入表示的距離,提出了成對(duì)節(jié)點(diǎn)的距離計(jì)算方法.

當(dāng)給定一對(duì)節(jié)點(diǎn)vi和vj時(shí),根據(jù)節(jié)點(diǎn)和社區(qū)的嵌入表示,可以獲得節(jié)點(diǎn)-社區(qū)隸屬關(guān)系的概率 ρic和ρjc,分別選取概率最大的社區(qū)ci和cj作為社區(qū)樹(shù)Tt上的隸屬社區(qū).社區(qū)間的距離Λ (ci,cj)被定義為:

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

其中,Λ ∈Rt×t是社區(qū)樹(shù)上所有社區(qū)的距離矩陣,ρi∈Rt是節(jié)點(diǎn)vi隸屬社區(qū)概率 ρic的向量表示.我們的目標(biāo)是期望有真實(shí)連接的成對(duì)節(jié)點(diǎn)vi和vj在社區(qū)樹(shù)上的距離dij盡可能小,反之亦然,因此損失函數(shù)為:

其中,eij=1,eik=0;β是一個(gè)大于0的常數(shù),用于控制正負(fù)樣本的差距.基于這樣的正負(fù)樣本距離損失函數(shù),可以在學(xué)習(xí)過(guò)程中不斷更新節(jié)點(diǎn)和社區(qū)的嵌入表示,,從而更新節(jié)點(diǎn)基于社區(qū)樹(shù)的概率分布,最終獲得節(jié)點(diǎn)-社區(qū)的最優(yōu)隸屬關(guān)系.

2.3 完整的基于梯度的優(yōu)化框架

基于給定的一顆重疊式社區(qū)樹(shù),可以通過(guò)節(jié)點(diǎn)和社區(qū)的嵌入表示計(jì)算節(jié)點(diǎn)-社區(qū)隸屬關(guān)系,進(jìn)而計(jì)算成對(duì)節(jié)點(diǎn)間的距離.通過(guò)最小化距離損失來(lái)調(diào)整節(jié)點(diǎn)和社區(qū)的嵌入表示,更新隸屬關(guān)系.如圖2所示,反復(fù)這一學(xué)習(xí)過(guò)程直至收斂,就可得到最終解.

圖2 基于梯度的重疊式層次社區(qū)檢測(cè)算法

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

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

上述算法展示了如何基于自定義的距離計(jì)算方式,自適應(yīng)任意的重疊式層次結(jié)構(gòu),進(jìn)行節(jié)點(diǎn)嵌入表示學(xué)習(xí)和節(jié)點(diǎn)-社區(qū)隸屬關(guān)系分配.兩個(gè)基于圖數(shù)據(jù)的基礎(chǔ)任務(wù)共享知識(shí),互相指引,實(shí)現(xiàn)了端到端的聯(lián)合優(yōu)化模型,兩個(gè)任務(wù)的表現(xiàn)共同得到了提升.

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

3 實(shí)驗(yàn)分析

3.1 實(shí)驗(yàn)設(shè)置

我們分別使用Aminer 數(shù)據(jù)集[15]和Wiki-vote 數(shù)據(jù)集進(jìn)行了實(shí)驗(yàn).Aminer 數(shù)據(jù)集是從dblp 學(xué)術(shù)論文網(wǎng)站收集的4258 615 組引文(cocitation)關(guān)系,以及相應(yīng)的論文信息和作者信息.我們?nèi)コ藳](méi)有任何引用關(guān)系的論文數(shù)據(jù)后,共獲得包含12 840 個(gè)節(jié)點(diǎn)和190 658條邊.Wiki-vote 數(shù)據(jù)集是維基百科數(shù)據(jù)集,包含3135 個(gè)節(jié)點(diǎn)和95 028 條邊.

我們使用6 種社區(qū)檢測(cè)算法作為基線模型:

ComE[2]和MNMF[7]:重疊式的平坦社區(qū)檢測(cè)算法.兩者都與節(jié)點(diǎn)嵌入任務(wù)聯(lián)合建模,前者基于重疊的高斯分布假設(shè),后者基于非負(fù)矩陣分解.

HCDE[10]和LouvainNE[9]:非重疊式的層次社區(qū)檢測(cè)算法.HCDE 預(yù)先用圖學(xué)習(xí)算法,例如LINE[14],獲得節(jié)點(diǎn)的嵌入表示,再自頂向下地用啟發(fā)式的策略構(gòu)建節(jié)點(diǎn)-社區(qū)隸屬關(guān)系.LouvainNE 自頂向下遞歸地利用Louvain[11]算法進(jìn)行層次化社區(qū)構(gòu)建,隨后再根據(jù)社區(qū)樹(shù)單獨(dú)學(xué)習(xí)節(jié)點(diǎn)的嵌入表示.

為了觀察先驗(yàn)知識(shí)擾動(dòng)對(duì)我們模型的影響,我們分別設(shè)計(jì)了Ours-Wide,Ours-Deep和Ours-Comb.3 種基于廣度樹(shù),深度樹(shù)和組合樹(shù)的重疊式層次社區(qū)檢測(cè)算法,僅社區(qū)層次結(jié)構(gòu)的表達(dá)形式不一致.

我們用以下兩組指標(biāo)來(lái)評(píng)估模型在社區(qū)檢測(cè)任務(wù)和節(jié)點(diǎn)嵌入下游任務(wù)的表現(xiàn):

Modularity:評(píng)估得到的節(jié)點(diǎn)-社區(qū)隸屬關(guān)系是否符合社區(qū)檢測(cè)任務(wù)模塊化的要求.它的值越高,就意味著越多有密集關(guān)聯(lián)的節(jié)點(diǎn)被分配到同一社區(qū)當(dāng)中,社區(qū)檢測(cè)的結(jié)果越好.

AUC:為評(píng)估節(jié)點(diǎn)嵌入表示在下游鏈路預(yù)測(cè)任務(wù)上的表現(xiàn)力,我們通過(guò)嵌入表示計(jì)算成對(duì)節(jié)點(diǎn)的相似度,并映射到[0,1]區(qū)間內(nèi),結(jié)合多種閾值設(shè)定和成對(duì)節(jié)點(diǎn)的真實(shí)標(biāo)簽計(jì)算AUC的值,該值越高意味著預(yù)測(cè)結(jié)果越準(zhǔn)確.

此外,我們對(duì)層次社區(qū)結(jié)構(gòu)進(jìn)行可視化展示,以證明我們模型的層次結(jié)構(gòu)建模能力.

3.2 實(shí)驗(yàn)結(jié)果

我們按照7:1:2的比例劃分了訓(xùn)練、驗(yàn)證和測(cè)試數(shù)據(jù)集,并以正樣本兩倍的數(shù)量隨機(jī)采樣負(fù)樣本,采用10-fold 交叉驗(yàn)證的方式來(lái)確定最優(yōu)參數(shù).我們定義社區(qū)數(shù)量在15-20 之間,訓(xùn)練過(guò)程中使用學(xué)習(xí)率為0.003的Adma 優(yōu)化器[16].表1展示了4 組模型在社區(qū)檢測(cè)任務(wù)和鏈路預(yù)測(cè)任務(wù)上的結(jié)果.

表1 不同模型的實(shí)驗(yàn)結(jié)果

我們首先根據(jù)4 組模型的社區(qū)檢測(cè)結(jié)果來(lái)考量這些社區(qū)的模塊化程度:(1) 重疊式平坦模型ComE和MNMF的模塊化程度整體上是高于非重疊模型SCD和vGraph的,這表明了重疊社區(qū)建模的優(yōu)勢(shì);(2)非重疊層次模型HCDE和LouvainNE的效果持平或略差于SCD和vGraph,這是因?yàn)闆](méi)有利用圖表示學(xué)習(xí)進(jìn)行雙任務(wù)聯(lián)合優(yōu)化,因此效果略差;(3)我們的3 種重疊式層次社區(qū)檢測(cè)算法在兩組數(shù)據(jù)集上的結(jié)果均優(yōu)于基線模型,這也進(jìn)一步說(shuō)明了層次社區(qū)結(jié)構(gòu)和重疊社區(qū)分布的合理性.

其次,我們需要驗(yàn)證節(jié)點(diǎn)嵌入表示在下游鏈路預(yù)測(cè)任務(wù)上競(jìng)爭(zhēng)力:(1)重疊式平坦模型MNMF的AUC值高于非重疊模型vGraph,這表明了重疊式社區(qū)分布假設(shè)的優(yōu)勢(shì).ComE的值沒(méi)有競(jìng)爭(zhēng)力是因?yàn)槟Ｐ蛡?cè)重于社區(qū)建模,SCD 沒(méi)有節(jié)點(diǎn)嵌入表示學(xué)習(xí)建模的部分;(2) 非重疊層次模型HCDE和LouvainNE的效果與vGraph 持平或更差,其原因是啟發(fā)式算法節(jié)點(diǎn)嵌入表示和社區(qū)檢測(cè)分離的優(yōu)化方式競(jìng)爭(zhēng)力不足;(3)我們的模型與所有基線模型相比同樣具有強(qiáng)勁的競(jìng)爭(zhēng)力,這證明了重疊式層次社區(qū)分布假設(shè)的合理性,以及節(jié)點(diǎn)嵌入和社區(qū)檢測(cè)雙任務(wù)可以達(dá)到雙贏的效果.

此外,我們發(fā)現(xiàn)在基于不同形態(tài)的層次結(jié)構(gòu)時(shí),不論是純粹的深度樹(shù)(deep)還是廣度樹(shù)(wide)其社區(qū)模塊化程度和下游任務(wù)效果都沒(méi)有深廣度組合樹(shù)(Comb.)好,這意味著一份數(shù)據(jù)集內(nèi)不同的社區(qū)可被細(xì)分的粒度是不一致的,有些傾向于細(xì)分為多類,有些傾向于細(xì)分為更多的層次,這是一種合理的現(xiàn)象.

3.3 社區(qū)分布可視化展示

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

圖3 社區(qū)分布可視化展示

4 結(jié)論與展望

本文提出了一種基于梯度的重疊式層次社區(qū)檢測(cè)算法,在層次結(jié)構(gòu)未知的情況下,通過(guò)梯度更新的方式聯(lián)合優(yōu)化節(jié)點(diǎn)嵌入表示和社區(qū)檢測(cè)任務(wù),靈活地探索節(jié)點(diǎn)和重疊式層次社區(qū)的隸屬關(guān)系.我們提供了多樣化的實(shí)驗(yàn)結(jié)果以及社區(qū)樹(shù)的可視化形態(tài),均證明了該算法的有效性.接下來(lái),我們將考慮如何利用基于梯度的優(yōu)化方式和強(qiáng)化學(xué)習(xí)等技術(shù),幫助模型自動(dòng)探索層次結(jié)構(gòu),不必受到獲取先驗(yàn)知識(shí)的成本約束.