0
| 本文作者： MrBear | 2020-05-16 11:16 |
雷鋒網(wǎng)AI科技評(píng)論按：
社區(qū)發(fā)現(xiàn)（Community Detection）是網(wǎng)絡(luò)科學(xué)領(lǐng)域中一個(gè)經(jīng)久不衰的重要問(wèn)題。
隨著深度學(xué)習(xí)的發(fā)展，研究者們逐漸從傳統(tǒng)的統(tǒng)計(jì)推斷和譜聚類(lèi)等方法中解放了出來(lái)。那么，深度學(xué)習(xí)時(shí)代的社區(qū)發(fā)現(xiàn)工作有哪些特點(diǎn)，研究者們遇到了哪些挑戰(zhàn)，有哪些前景光明的研究方向呢？
近日，IJCAI 2020 上發(fā)表的一篇 Survey 文章，完整闡釋了這一研究方向的方法、挑戰(zhàn)和機(jī)遇。論文來(lái)自數(shù)據(jù)挖掘領(lǐng)域大牛 Philip S. Yu 團(tuán)隊(duì)。
論文標(biāo)題：
Deep Learning for Community Detection: Progress, Challenges and Opportunities
社區(qū)發(fā)現(xiàn)（Community Detection）是網(wǎng)絡(luò)科學(xué)領(lǐng)域中一個(gè)經(jīng)久不衰的重要問(wèn)題。隨著深度學(xué)習(xí)的發(fā)展，研究者們逐漸從傳統(tǒng)的統(tǒng)計(jì)推斷和譜聚類(lèi)方法中解放了出來(lái)。那么，深度學(xué)習(xí)時(shí)代的社區(qū)發(fā)現(xiàn)工作有哪些特點(diǎn)，研究者們遇到了哪些挑戰(zhàn)，有哪些前景光明的研究方向呢？
網(wǎng)絡(luò)中的社區(qū)指的是一組由節(jié)點(diǎn)以及與其相連的邊緊密地形成的實(shí)體。社區(qū)發(fā)現(xiàn)旨在遵循「社區(qū)中的節(jié)點(diǎn)緊密相連，不同社區(qū)間的節(jié)點(diǎn)稀疏相連」的規(guī)則對(duì)實(shí)體集合進(jìn)行聚類(lèi)。包括譜聚類(lèi)、統(tǒng)計(jì)推斷在內(nèi)的傳統(tǒng)社區(qū)發(fā)現(xiàn)方法在處理高維圖數(shù)據(jù)時(shí)存在計(jì)算速度的問(wèn)題。因此，近年來(lái)，深度學(xué)習(xí)方法被廣泛地應(yīng)用。
在本文中，作者特別調(diào)研了社區(qū)發(fā)現(xiàn)的深度學(xué)習(xí)方法這一研究領(lǐng)域中的最新進(jìn)展，并根據(jù)用到的深度神經(jīng)網(wǎng)絡(luò)、深度圖嵌入、圖神經(jīng)網(wǎng)絡(luò)對(duì)這些方法進(jìn)行分類(lèi)。由于目前深度學(xué)習(xí)的能力仍然不能滿(mǎn)足處理復(fù)雜網(wǎng)絡(luò)結(jié)構(gòu)的需求，本文作者指出了當(dāng)前該領(lǐng)域面臨的挑戰(zhàn)和研究機(jī)遇。
網(wǎng)絡(luò)是有兩種基本的實(shí)體（即節(jié)點(diǎn)和邊）形成的。
根據(jù)圖理論，「社區(qū)」是一種內(nèi)部節(jié)點(diǎn)緊密相連的子圖，它遵循以下特定的規(guī)則：
（1）社區(qū)內(nèi)的節(jié)點(diǎn)緊密相連；
（2）不同社區(qū)中的節(jié)點(diǎn)稀疏相連。
人們也將社區(qū)看做一種聚類(lèi)簇，其中相同社區(qū)內(nèi)的節(jié)點(diǎn)可以共享共用的特性和/或扮演類(lèi)似的角色。
這里根據(jù) Radicchi 等人基于網(wǎng)絡(luò)統(tǒng)計(jì)分析給出的定義展開(kāi)討論。根據(jù)節(jié)點(diǎn)在社區(qū)內(nèi)部和外部的度，我們可以將社區(qū)分為兩類(lèi)：強(qiáng)社區(qū)和弱社區(qū)。 節(jié)點(diǎn)的「內(nèi)部度」代表將該節(jié)點(diǎn)與同一個(gè)社區(qū)中其它節(jié)點(diǎn)連接起來(lái)的邊數(shù)，節(jié)點(diǎn)的「外部度」則代表將該節(jié)點(diǎn)與屬于其它社區(qū)的節(jié)點(diǎn)連接起來(lái)的邊數(shù)。一個(gè)弱社區(qū)是其中的節(jié)點(diǎn)的內(nèi)部度之和大于外部度之和的子圖。一個(gè)強(qiáng)社區(qū)是其中每個(gè)節(jié)點(diǎn)的內(nèi)部度都大于外部度的子圖。針對(duì)社區(qū)的網(wǎng)絡(luò)結(jié)構(gòu)，本文采用了強(qiáng)社區(qū)的定義。
社區(qū)發(fā)現(xiàn)可以幫助我們理解網(wǎng)絡(luò)內(nèi)在的模式和功能。
在現(xiàn)實(shí)世界的應(yīng)用中，社區(qū)將復(fù)雜系統(tǒng)中的信息聚集了起來(lái)。舉例而言，
Chen、Yuan 等人發(fā)現(xiàn)在「蛋白質(zhì)-蛋白質(zhì)」交互（PPI）網(wǎng)絡(luò)中，被聚合到社區(qū)中的蛋白質(zhì)具有相似的生物學(xué)功能；
Chen 、Redner等人，在論文引用網(wǎng)絡(luò)中，通過(guò)社區(qū)發(fā)現(xiàn)技術(shù)確定通過(guò)論文引用連接起來(lái)的課題的重要性、相互關(guān)聯(lián)以及演變情況；
Zhang 等人，在企業(yè)網(wǎng)絡(luò)中，通過(guò)研究離線的公司內(nèi)部數(shù)據(jù)源以及在線的企業(yè)社交關(guān)系將雇員分組到不同的社區(qū)中；
Yang 等人指出，在線社交網(wǎng)絡(luò)中（例如 Twitter 和 Facebook）擁有共同的興趣或朋友的用戶(hù)可能來(lái)自同一個(gè)社區(qū)（如圖 1 所示）。
圖 1：社交網(wǎng)絡(luò)中的社區(qū)發(fā)現(xiàn)示例。根據(jù)個(gè)體之間的緊密度，網(wǎng)絡(luò)被劃分為兩個(gè)社區(qū)，即包含三個(gè)節(jié)點(diǎn)的社區(qū) C_1 和包含四個(gè)節(jié)點(diǎn)的社區(qū) C_2。
傳統(tǒng)的社區(qū)發(fā)現(xiàn)方法大部分都是基于統(tǒng)計(jì)推斷和機(jī)器學(xué)習(xí)發(fā)展出來(lái)的。例如， 在統(tǒng)計(jì)學(xué)領(lǐng)域非常具有代表性的社區(qū)發(fā)現(xiàn)方法「隨機(jī)分塊模型」（SBM）被廣泛用于描述社區(qū)是如何形成的。然而，在處理當(dāng)下的復(fù)雜數(shù)據(jù)及和社交場(chǎng)景時(shí)，這些傳統(tǒng)的方法面臨著許多問(wèn)題。此外，在機(jī)器學(xué)習(xí)領(lǐng)域，發(fā)現(xiàn)社區(qū)的工作往往被看做一個(gè)圖上的聚類(lèi)問(wèn)題。Ng 等人用特征向量（例如鄰接矩陣和 Laplacian 矩陣）實(shí)現(xiàn)了將節(jié)點(diǎn)劃分到社區(qū)中的譜聚類(lèi)方法，然而這種方法在稀疏網(wǎng)絡(luò)上的性能較差。
同時(shí)，對(duì)于預(yù)設(shè)的社區(qū)數(shù)目的要求也特別限制了依賴(lài)統(tǒng)計(jì)推斷的模型的研發(fā)。在網(wǎng)絡(luò)分析領(lǐng)域中，傳統(tǒng)的方法并沒(méi)有考慮到節(jié)點(diǎn)的屬性，而這些屬性描述了特征的豐富信息。此外，由于過(guò)高的計(jì)算復(fù)雜度，動(dòng)態(tài)方法也很難被應(yīng)用于大規(guī)模網(wǎng)絡(luò)。總而言之，處理由圖及其屬性、大規(guī)模網(wǎng)絡(luò)和動(dòng)態(tài)環(huán)境形成的高維數(shù)據(jù)需要更強(qiáng)大的技術(shù)，從而同時(shí)兼顧高性能和計(jì)算速度。
深度學(xué)習(xí)使計(jì)算模型可以學(xué)習(xí)到具有多層次抽象的數(shù)據(jù)表征。許多計(jì)算模型和算法都需要對(duì)以網(wǎng)絡(luò)結(jié)構(gòu)形式存在的數(shù)據(jù)進(jìn)行表征學(xué)習(xí)。深度學(xué)習(xí)技術(shù)在學(xué)習(xí)非線性特征時(shí)具有很大的優(yōu)勢(shì)。這一點(diǎn)在諸如計(jì)算機(jī)視覺(jué)、自然語(yǔ)言處理等領(lǐng)域中都取得了廣泛的成功，在這些領(lǐng)域中數(shù)據(jù)有著內(nèi)在的關(guān)系。在網(wǎng)絡(luò)分析領(lǐng)域，深度學(xué)習(xí)可以有效地通過(guò)多層深度神經(jīng)網(wǎng)絡(luò)降低數(shù)據(jù)維度，從而完成社區(qū)發(fā)現(xiàn)、節(jié)點(diǎn)分類(lèi)、鏈接預(yù)測(cè)等任務(wù)。
這里重點(diǎn)研究深度學(xué)習(xí)在社區(qū)發(fā)現(xiàn)任務(wù)中的應(yīng)用的新研究趨勢(shì)，Philip S. Yu等人的這篇綜述貢獻(xiàn)有：
（1）分析了將深度學(xué)習(xí)方法用于社區(qū)發(fā)現(xiàn)的優(yōu)勢(shì)；
（2）從技術(shù)的視角，總結(jié)了目前最先進(jìn)的研究，并對(duì)其進(jìn)行分類(lèi)；
（3）討論了仍然存在的挑戰(zhàn)，并指出了具有前景的未來(lái)工作的機(jī)遇。
據(jù)AI科技評(píng)論所知，這篇綜述也是首次全面回顧深度學(xué)習(xí)在社區(qū)發(fā)現(xiàn)中的應(yīng)用，對(duì)研究人員和技術(shù)專(zhuān)家理解深度學(xué)習(xí)和社交網(wǎng)絡(luò)領(lǐng)域的發(fā)展趨勢(shì)有著巨大幫助。
圖 2：社區(qū)發(fā)現(xiàn)之深度學(xué)習(xí)：進(jìn)步、挑戰(zhàn)和機(jī)遇。
簡(jiǎn)單來(lái)說(shuō)，社區(qū)發(fā)現(xiàn)，即從網(wǎng)絡(luò) G 中發(fā)現(xiàn)社區(qū) C。
這里提到的網(wǎng)絡(luò)是一種特殊的圖，它對(duì)現(xiàn)實(shí)世界中的系統(tǒng)（例如，互聯(lián)網(wǎng)、學(xué)術(shù)合作網(wǎng)絡(luò)以及社交群組）中的復(fù)雜關(guān)系進(jìn)行了抽象。在這里，網(wǎng)絡(luò)的概念主要強(qiáng)調(diào)的是其拓?fù)浣Y(jié)構(gòu)。
定義 1（網(wǎng)絡(luò) G）
基于圖理論，有權(quán)網(wǎng)絡(luò)可以被表征為 G=（V，E，W），而無(wú)權(quán)網(wǎng)絡(luò)可以被表征為 G=（V，E），其中 V 和 E 分別代表節(jié)點(diǎn)的集合和邊的集合，W 代表 E 相應(yīng)的權(quán)值。每條邊通過(guò)權(quán)值描述連接強(qiáng)度或者容量。我們可以將無(wú)權(quán)圖的 W 視為1，將其從圖 G 中去除。
子圖 g?G 是對(duì)于圖的一種劃分，它保持了原始的網(wǎng)絡(luò)結(jié)構(gòu)。子圖的劃分遵循預(yù)先定義好的規(guī)則。根據(jù)不同的規(guī)則可能得到不同形式的子圖。社區(qū)是一種表征真實(shí)社交現(xiàn)象的子圖；也就是說(shuō)，在群組中存在一組具有緊密關(guān)系的對(duì)象。這里遵循由 Radicchi 定義的強(qiáng)社區(qū)的概念。
定義 2（社區(qū) C）
社區(qū)是一組網(wǎng)絡(luò)中相互聯(lián)系的子圖。社區(qū)中的節(jié)點(diǎn)具有密集的連接，而不同社區(qū)之間的節(jié)點(diǎn)具有稀疏的連接。根據(jù)一種將節(jié)點(diǎn)聚類(lèi)到不同群組中的網(wǎng)絡(luò)劃分方法給出一個(gè)社區(qū) C_i，我們得到 C={C_1，C_2，...，C_k}，其中 k 代表可以從原始網(wǎng)絡(luò)中被劃分出的社區(qū)數(shù)。被聚合到社區(qū) C_i 中的節(jié)點(diǎn) v 滿(mǎn)足：v 到社區(qū)內(nèi)每個(gè)節(jié)點(diǎn)的內(nèi)部度大于其外部度。
與其他機(jī)器學(xué)習(xí)方法相比，深度學(xué)習(xí)的明顯優(yōu)勢(shì)是它能夠?qū)⒏呔S數(shù)據(jù)編碼到一個(gè)新的特征表征中。通過(guò)使用以圖結(jié)構(gòu)的形式組織的數(shù)據(jù)表征節(jié)點(diǎn)之間的聯(lián)系，許多深度學(xué)習(xí)方法都可以學(xué)習(xí)到節(jié)點(diǎn)、鄰域以及子圖的模式。在多數(shù)現(xiàn)實(shí)場(chǎng)景中，數(shù)據(jù)缺乏節(jié)點(diǎn)標(biāo)簽信息和關(guān)于社區(qū)的先驗(yàn)信息，而深度學(xué)習(xí)在無(wú)監(jiān)督學(xué)習(xí)的任務(wù)中體現(xiàn)出了優(yōu)勢(shì)。除了簡(jiǎn)單地利用網(wǎng)絡(luò)拓?fù)鋪?lái)發(fā)現(xiàn)社區(qū)之外，一些方法還將語(yǔ)義描述作為數(shù)據(jù)中的節(jié)點(diǎn)屬性加以研究。在傳統(tǒng)社區(qū)發(fā)現(xiàn)方法中，這類(lèi)方法主要基于鄰接矩陣和節(jié)點(diǎn)屬性矩陣。然而，深度學(xué)習(xí)可以構(gòu)建更有效的節(jié)點(diǎn)屬性和社區(qū)結(jié)構(gòu)表征。
因此，深度學(xué)習(xí)填平了傳統(tǒng)社區(qū)發(fā)現(xiàn)方法中存在的關(guān)鍵短板。為了實(shí)現(xiàn)這一目標(biāo)，近年來(lái)的工作指出了一些具有前景的研究方向：將深度學(xué)習(xí)模型應(yīng)用于社區(qū)發(fā)現(xiàn)，以及基于社區(qū)的特性修改深度學(xué)習(xí)模型。將深度學(xué)習(xí)應(yīng)用于社區(qū)發(fā)現(xiàn)的前景可以被表述為：
（1）通過(guò)深度學(xué)習(xí)模型提升傳統(tǒng)社區(qū)發(fā)現(xiàn)方法的性能；
（2）從對(duì)于深度學(xué)習(xí)至關(guān)重要的特征維度上引入更多的信息；
（3）從網(wǎng)絡(luò)實(shí)體的拓?fù)浜蛯傩匀胧?，同時(shí)提升模型的學(xué)習(xí)性能和魯棒性；
（4）現(xiàn)在可以更好地從復(fù)雜的相關(guān)結(jié)構(gòu)中對(duì)大規(guī)模網(wǎng)絡(luò)進(jìn)行檢測(cè)。
為了對(duì)近年來(lái)將深度學(xué)習(xí)用于社區(qū)發(fā)現(xiàn)的研究進(jìn)展進(jìn)行概述，Philip等人從技術(shù)的角度總結(jié)了現(xiàn)有的方法。具體而言，他們首先對(duì)具有影響力的社區(qū)發(fā)現(xiàn)深度學(xué)習(xí)方法進(jìn)行了分類(lèi)。在每一類(lèi)中，他們概述了框架、模型以及算法的技術(shù)貢獻(xiàn)。
為了研究近年來(lái)被應(yīng)用于社區(qū)發(fā)現(xiàn)的深度學(xué)習(xí)方法，圖 2 描述了相關(guān)深度學(xué)習(xí)方法的詳細(xì)分類(lèi)情況，并相應(yīng)地附上了總結(jié)出來(lái)的挑戰(zhàn)。本章將從基于深度神經(jīng)網(wǎng)絡(luò)、基于深度圖嵌入、以及基于圖神經(jīng)網(wǎng)絡(luò)的社區(qū)發(fā)現(xiàn)方法三個(gè)方面展開(kāi)敘述。
4.1 基于深度神經(jīng)網(wǎng)絡(luò)的社區(qū)發(fā)現(xiàn)
深度神經(jīng)網(wǎng)絡(luò)在對(duì)復(fù)雜的關(guān)系進(jìn)行建模和發(fā)現(xiàn)的任務(wù)中具有天然的優(yōu)勢(shì)。考慮到現(xiàn)有的深度神經(jīng)網(wǎng)絡(luò)模型在社區(qū)發(fā)現(xiàn)領(lǐng)域的流形程度，作者選取了基于卷積神經(jīng)網(wǎng)絡(luò)（CNN）、基于自編碼器、基于生成對(duì)抗網(wǎng)絡(luò)（GAN）的社區(qū)發(fā)現(xiàn)方法進(jìn)行調(diào)研。
基于 CNN 的社區(qū)發(fā)現(xiàn)
CNN 的關(guān)鍵組件包含卷積操作和對(duì)卷積層結(jié)果的最大池化操作。卷積操作利用卷積核降低計(jì)算開(kāi)銷(xiāo)。隨后，最大池化操作被用于特征提取，這保證了 CNN 的魯棒性。
得益于 CNN 的發(fā)展，Xin 等人設(shè)計(jì)了一種用于社區(qū)發(fā)現(xiàn)的新型 CNN，并提出了一種用于拓?fù)浣Y(jié)構(gòu)不完整的網(wǎng)絡(luò)的有監(jiān)督算法。由于社區(qū)發(fā)現(xiàn)被廣泛看做一種無(wú)監(jiān)督聚類(lèi)任務(wù)，科研人員對(duì)基于無(wú)監(jiān)督 CNN 的社區(qū)發(fā)現(xiàn)進(jìn)行了研究。人們研發(fā)出了在 CNN 框架下的系數(shù)矩陣卷積，從而專(zhuān)門(mén)進(jìn)行對(duì)高度稀疏的鄰接矩陣的表征。
基于自編碼器的社區(qū)發(fā)現(xiàn)
棧式自編碼器是一種深度學(xué)習(xí)模型，它在社區(qū)發(fā)現(xiàn)任務(wù)中表現(xiàn)出了強(qiáng)大的性能，可以表征網(wǎng)絡(luò)矩陣的非線性特征。研究者們發(fā)現(xiàn)自編碼器和譜聚類(lèi)在譜矩陣的低維近似方面有相似的框架，并受此啟發(fā)將自編碼器引入了社區(qū)發(fā)現(xiàn)領(lǐng)域。此后，Cao 等人提出了一種將網(wǎng)絡(luò)拓?fù)浜凸?jié)點(diǎn)屬性相結(jié)合的棧式自編碼器，它提升了深度神經(jīng)網(wǎng)絡(luò)隱層的泛化能力。為了進(jìn)一步解決網(wǎng)絡(luò)拓?fù)浜凸?jié)點(diǎn)屬性之間的匹配問(wèn)題，Cao 等人通過(guò)引入一個(gè)控制這種匹配的折中的自適應(yīng)參數(shù)，研發(fā)了一種帶有圖正則化的自編碼器方法。
著眼于網(wǎng)絡(luò)拓?fù)?，Xie 等人提出在深度自編碼器中對(duì)鄰接矩陣進(jìn)行變換，從而有效地學(xué)到節(jié)點(diǎn)相似度。同時(shí)，Bhatia 和 Rani 提出的自編碼器通過(guò)對(duì)隨機(jī)游走序列建模學(xué)習(xí)節(jié)點(diǎn)的結(jié)構(gòu)，他們通過(guò)優(yōu)化社區(qū)結(jié)構(gòu)的模塊度對(duì)這種序列進(jìn)行調(diào)優(yōu)。
為了避免預(yù)設(shè)社團(tuán)的數(shù)量，Bhatia 和 Rani 提出了一種層級(jí)棧式自編碼器，他們找出種子節(jié)點(diǎn)，基于網(wǎng)絡(luò)結(jié)構(gòu)有效地將其它節(jié)點(diǎn)加入到社區(qū)中。此后，該領(lǐng)域的研究旨在自適應(yīng)地學(xué)習(xí)而不是預(yù)定義社區(qū)結(jié)構(gòu)。Choong 等人提出的方法大大地提升了訓(xùn)練損失驗(yàn)證階段的計(jì)算效率。這種自動(dòng)選擇機(jī)制保證了模型基于社區(qū)標(biāo)準(zhǔn)分配節(jié)點(diǎn)。
Xu 等人將包含具有正負(fù)號(hào)連接的網(wǎng)絡(luò)成為有符號(hào)網(wǎng)絡(luò)（signed network）。為了處理邊上的有符號(hào)信息，Shen 和 Chung 提出了一種半監(jiān)督的棧式自編碼器，它可以重構(gòu)鄰接矩陣，為進(jìn)一步的深度學(xué)習(xí)網(wǎng)絡(luò)嵌入的學(xué)習(xí)表征有符號(hào)網(wǎng)絡(luò)。
基于生成對(duì)抗網(wǎng)絡(luò)（GAN）的社區(qū)發(fā)現(xiàn)
GAN 包含兩種相互競(jìng)爭(zhēng)的深度神經(jīng)網(wǎng)絡(luò)，因此它可以迅速調(diào)整訓(xùn)練精度。典型的 GAN 是以無(wú)監(jiān)督方式運(yùn)行的，它們生成與訓(xùn)練集中的數(shù)據(jù)具有相同統(tǒng)計(jì)特征的新數(shù)據(jù)。對(duì)于網(wǎng)絡(luò)數(shù)據(jù)來(lái)說(shuō)，GAN 模型適用于無(wú)標(biāo)簽的數(shù)據(jù)集和序列化的網(wǎng)絡(luò)劃分。
Yang 和 Leskovec 等人基于對(duì)抗性機(jī)制，提出了社區(qū)隸屬關(guān)系圖模型（AGM）。AGM 基于「節(jié)點(diǎn)-社區(qū)」成員隸屬關(guān)系（node membership）的思想對(duì)重疊的社區(qū)中的節(jié)點(diǎn)進(jìn)行編碼。每個(gè)社區(qū)都有一個(gè)單一的概率，使得社區(qū)結(jié)構(gòu)可以在 GAN 中進(jìn)行。Jia 等人通過(guò)將這種模型與 GAN 相結(jié)合研發(fā)了一種新型的框架，它根據(jù)具有中間項(xiàng)（即隸屬圖中的「節(jié)點(diǎn)-社區(qū)」成員隸屬關(guān)系）進(jìn)行社區(qū)發(fā)現(xiàn)。
4.2 基于深度圖嵌入的社區(qū)發(fā)現(xiàn)
深度圖嵌入是一種將網(wǎng)絡(luò)中的節(jié)點(diǎn)映射到一個(gè)低維向量空間中的技術(shù)。它將盡可能多的結(jié)構(gòu)信息保存到表征中。通過(guò)圖嵌入，基于網(wǎng)絡(luò)分析的機(jī)器學(xué)習(xí)任務(wù)（例如鏈接預(yù)測(cè)、節(jié)點(diǎn)分類(lèi)和節(jié)點(diǎn)聚類(lèi)）可以利用表征的潛在特征，這樣節(jié)省了主要由網(wǎng)絡(luò)搜索引起的計(jì)算開(kāi)銷(xiāo)。對(duì)于社區(qū)發(fā)現(xiàn)任務(wù)來(lái)說(shuō)，基于節(jié)點(diǎn)表征的圖嵌入的輸出支持聚類(lèi)的任務(wù)（例如通過(guò) k-means 聚類(lèi)）。
基于深度非負(fù)矩陣分解的社區(qū)發(fā)現(xiàn)
非負(fù)矩陣分解（NMF）是一類(lèi)將矩陣分解為兩個(gè)矩陣的算法，它具有如下性質(zhì)：三個(gè)矩陣都沒(méi)有負(fù)的特征值。NMF 自動(dòng)地對(duì)輸入數(shù)據(jù)的列進(jìn)行聚類(lèi)，通過(guò)訓(xùn)練階段的誤差函數(shù)，使原始矩陣和兩個(gè)分解出的矩陣之間的近似誤差最小。
Ye 等人提出了一種用于社區(qū)發(fā)現(xiàn)的深度 NMF 模型，其中深度學(xué)習(xí)架構(gòu)可以促進(jìn) NMF 學(xué)習(xí)原始網(wǎng)絡(luò)結(jié)構(gòu)和社區(qū)結(jié)構(gòu)之間的層次化映射。在某些情況下，社區(qū)發(fā)現(xiàn)的工作需要與對(duì)帶有屬性的內(nèi)容的語(yǔ)義理解同時(shí)進(jìn)行。為此，研究人員以一種帶屬性的圖的形式表征網(wǎng)絡(luò)，這種圖同時(shí)包含了網(wǎng)絡(luò)結(jié)構(gòu)和節(jié)點(diǎn)的屬性。Li 等人特別針對(duì)帶屬性圖的社區(qū)發(fā)現(xiàn)任務(wù)提出了一種嵌入方法，它將帶有屬性的社區(qū)發(fā)現(xiàn)看做一個(gè) NMF 優(yōu)化問(wèn)題。為了使算法收斂，他們?cè)O(shè)計(jì)了一套可計(jì)算的迭代更新規(guī)則。
基于深度稀疏濾波的社區(qū)發(fā)現(xiàn)
鄰接矩陣反映出了網(wǎng)絡(luò)的稀疏性。嵌入對(duì)輸入的成對(duì)關(guān)系進(jìn)行編碼，從而避免在稀疏矩陣上進(jìn)行搜索。稀疏濾波（SF）是一種有效的深度特征學(xué)習(xí)算法，它只用到了一個(gè)超參數(shù)，但可以處理高維輸入。SF 的關(guān)鍵模塊是針對(duì) L2 正則化后的特征的稀疏性設(shè)計(jì)的簡(jiǎn)單代價(jià)函數(shù)。對(duì)于網(wǎng)絡(luò)（尤其是在大型網(wǎng)絡(luò)中）的社區(qū)發(fā)現(xiàn)，Xie 等人基于深度稀疏濾波提出了一種高效的網(wǎng)絡(luò)表征方法。他們通過(guò)一種無(wú)監(jiān)督的深度學(xué)習(xí)算法劃分網(wǎng)絡(luò)，從而提取網(wǎng)絡(luò)特征。
基于社區(qū)嵌入的社區(qū)發(fā)現(xiàn)
傳統(tǒng)意義上，圖嵌入重點(diǎn)關(guān)注單個(gè)的節(jié)點(diǎn)。Cavallari 等人研究了另一種重要的、但是鮮有人探索過(guò)的圖嵌入情況，他們重點(diǎn)關(guān)注對(duì)社區(qū)的嵌入。他們認(rèn)為這種新的重要策略有益于社區(qū)發(fā)現(xiàn)任務(wù)。具體而言，社區(qū)嵌入的目標(biāo)是在低維空間中學(xué)習(xí)一種社區(qū)的節(jié)點(diǎn)分布。我們可以通過(guò)過(guò)渡性（transitional）的圖嵌入方法使用這種新的節(jié)點(diǎn)分布，從而很好地保留網(wǎng)絡(luò)結(jié)構(gòu)，這反過(guò)來(lái)可以提升社區(qū)發(fā)現(xiàn)的性能。此外，Tu 等人提出了一種新的圖嵌入模型，它同時(shí)探測(cè)每個(gè)節(jié)點(diǎn)的社區(qū)分布，并且學(xué)習(xí)節(jié)點(diǎn)和社區(qū)的嵌入。
網(wǎng)絡(luò)中的社區(qū)實(shí)際上反映了同一個(gè)社區(qū)中相似的觀點(diǎn)、行為等高階近似信息。Zhang 等人提出了一種保留社區(qū)信息的社交網(wǎng)絡(luò)嵌入方法來(lái)學(xué)習(xí)網(wǎng)絡(luò)表征。他們提出的這種方法在社區(qū)檢測(cè)任務(wù)中體現(xiàn)出了性能的優(yōu)越性。
4.3 基于圖神經(jīng)網(wǎng)絡(luò)的社區(qū)發(fā)現(xiàn)
近年來(lái)，圖神經(jīng)網(wǎng)絡(luò)（GNN）的迅猛發(fā)展表明了圖挖掘和深度學(xué)習(xí)技術(shù)融合的趨勢(shì)?；?GNN 的社區(qū)發(fā)現(xiàn)被用于利用圖神經(jīng)網(wǎng)絡(luò)對(duì)網(wǎng)絡(luò)上的復(fù)雜關(guān)系進(jìn)行建模，并捕獲這種關(guān)系。例如，Chen 等人提出的有監(jiān)督社區(qū)發(fā)現(xiàn) GNN 引入了一種非回溯的運(yùn)算符，來(lái)定義邊的鄰接性。這種方法可以提升學(xué)習(xí)性能。對(duì)于 GNN 來(lái)說(shuō)，運(yùn)算符的選擇非常方便。
圖卷積網(wǎng)絡(luò)（GCN）是基于 CNN 研發(fā)的，它繼承了快速學(xué)習(xí)的能力。面對(duì)圖輸入數(shù)據(jù)，GCN 展現(xiàn)出了非常好的性能。GCN 帶來(lái)的巨大提升在于整合了考慮網(wǎng)絡(luò)中實(shí)體概率分布的概率模型。例如，Jin 等人通過(guò)馬爾科夫隨機(jī)場(chǎng)解決了包含語(yǔ)義信息的帶屬性網(wǎng)絡(luò)中的半監(jiān)督社區(qū)發(fā)現(xiàn)問(wèn)題。Shchur 和 Gunnemann 將「伯努利-泊松」概率模型整合到 GCN 中，用于重疊社區(qū)發(fā)現(xiàn)問(wèn)題。通過(guò)這種方法，卷積層可以識(shí)別復(fù)雜的網(wǎng)絡(luò)模式。
近年來(lái)（尤其是近 5 年來(lái)），用于社區(qū)發(fā)現(xiàn)的深度學(xué)習(xí)技術(shù)迅速發(fā)展。由于對(duì)現(xiàn)實(shí)世界具有重大的影響，這一領(lǐng)域持續(xù)受到研究人員的關(guān)注。盡管取得了令人欣喜的成果，在將深度學(xué)習(xí)應(yīng)用于社區(qū)發(fā)現(xiàn)的領(lǐng)域中，仍然有一些挑戰(zhàn)有待被更好地解決。下面，本文將總結(jié)這些挑戰(zhàn)和機(jī)遇。
挑戰(zhàn) 1：社區(qū)數(shù)未知
長(zhǎng)久以來(lái)，由于社區(qū)數(shù)未知而引發(fā)的挑戰(zhàn)始終沒(méi)有得到很好的解決。在機(jī)器學(xué)習(xí)領(lǐng)域中，社區(qū)發(fā)現(xiàn)經(jīng)常被表示為一種無(wú)監(jiān)督聚類(lèi)任務(wù)?？偓F(xiàn)實(shí)世界的網(wǎng)絡(luò)中提取出的研究數(shù)據(jù)大多是沒(méi)有標(biāo)簽的。因此，我們很難獲取有關(guān)社區(qū)數(shù)的先驗(yàn)知識(shí)。此外，大多數(shù)現(xiàn)有的深度學(xué)習(xí)社區(qū)發(fā)現(xiàn)方法（尤其是深度圖嵌入），通過(guò)評(píng)估潛在特征空間中的節(jié)點(diǎn)相似度獲取分類(lèi)節(jié)點(diǎn)。然而，在后續(xù)的聚類(lèi)算法中，聚類(lèi)的目標(biāo)數(shù)量仍然需要被事先定義。
機(jī)遇：對(duì)于這一挑戰(zhàn)，一個(gè)直接的解決方案是通過(guò)分析網(wǎng)絡(luò)拓?fù)浯_定社區(qū)的數(shù)量，并將其整合到深度學(xué)習(xí)模型中。Bhatia 和 Rani 等人遵循這一思想，采用基于隨機(jī)游走的定制化 PageRank 算法，通過(guò)將圖重構(gòu)到一種線性的形式進(jìn)行社區(qū)發(fā)現(xiàn)，并通過(guò)模塊化的優(yōu)化方法來(lái)應(yīng)用調(diào)優(yōu)。但是這些方法并不能保證網(wǎng)絡(luò)中的每個(gè)節(jié)點(diǎn)可以被分配到特定的社區(qū)中。因此，我們需要為社區(qū)發(fā)現(xiàn)任務(wù)涉及新的模型，從而避免在分配社區(qū)的過(guò)程中漏掉某些節(jié)點(diǎn)。
挑戰(zhàn) 2：網(wǎng)絡(luò)層次
網(wǎng)絡(luò)層次反映了分層的網(wǎng)絡(luò)結(jié)構(gòu)，它將位于獨(dú)立的層上的多個(gè)群組連接了起來(lái)，從而形成一個(gè)更加復(fù)雜的網(wǎng)絡(luò)。而每一層都專(zhuān)注于特定的功能。對(duì)于多層網(wǎng)絡(luò)，用于社區(qū)發(fā)現(xiàn)的深度學(xué)習(xí)技術(shù)必須實(shí)現(xiàn)對(duì)于兩種層次上的表征的提取。而且他們將面臨多層網(wǎng)絡(luò)固有的挑戰(zhàn)，這包括不同的關(guān)系類(lèi)型以及不同層中不同的稀疏程度。
機(jī)遇：為了區(qū)分不同種類(lèi)的連接，Song 和 Thiagarajan 提出了一種具有特殊子圖設(shè)計(jì)的多層 DeepWalk 模型，從而保存了層次化的結(jié)構(gòu)。但是他們并沒(méi)有同時(shí)優(yōu)化可以用于所有層的公用表征以及保留了特定層網(wǎng)絡(luò)結(jié)構(gòu)的局部表征。他們的目的是利用不同層之間的依賴(lài)，而實(shí)際上這種依賴(lài)關(guān)系經(jīng)常被破壞。此外，對(duì)于新的設(shè)計(jì)來(lái)說(shuō)，還應(yīng)該考慮與層數(shù)增加有關(guān)的可伸縮性問(wèn)題。因此，在研發(fā)用于具有網(wǎng)絡(luò)層次的社區(qū)發(fā)現(xiàn)的深度學(xué)習(xí)方法的問(wèn)題上，我們還有很長(zhǎng)的路要走。
挑戰(zhàn) 3：網(wǎng)絡(luò)異質(zhì)性
網(wǎng)絡(luò)的異質(zhì)性指的是網(wǎng)絡(luò)中實(shí)體類(lèi)型的顯著差異，而各種各樣的節(jié)點(diǎn)集合和它們之間復(fù)雜的聯(lián)系形成了異質(zhì)網(wǎng)絡(luò)。因此，我們應(yīng)該通過(guò)不同于同質(zhì)網(wǎng)絡(luò)的方式研究異質(zhì)網(wǎng)絡(luò)中的社區(qū)發(fā)現(xiàn)。在應(yīng)用和研發(fā)深度學(xué)習(xí)模型和算法時(shí)，應(yīng)該解決異質(zhì)網(wǎng)絡(luò)實(shí)體上的概率分布的差異。
機(jī)遇：大多數(shù)之前的深度學(xué)習(xí)方法并不是基于網(wǎng)絡(luò)異質(zhì)性研發(fā)的。Change 等人設(shè)計(jì)了一種非線性嵌入函數(shù)，它被用于捕獲異質(zhì)組件之間的交互。因此，未來(lái)在異質(zhì)網(wǎng)絡(luò)上至少存在兩個(gè)方面的研究機(jī)遇：（1）異質(zhì)網(wǎng)絡(luò)表征的深度圖嵌入學(xué)習(xí)模型以及相關(guān)的支撐算法；（2）采用新型訓(xùn)練過(guò)程的特定深度學(xué)習(xí)模型，旨在學(xué)習(xí)隱藏層中的異構(gòu)圖屬性。
挑戰(zhàn) 4：邊上帶符號(hào)的信息
許多現(xiàn)實(shí)世界中的網(wǎng)絡(luò)具有邊上的符號(hào)信息（即正關(guān)系或負(fù)關(guān)系）。在有符號(hào)網(wǎng)絡(luò)的環(huán)境下，用于社區(qū)發(fā)現(xiàn)的深度學(xué)習(xí)方法面臨的挑戰(zhàn)是：通過(guò)不同的符號(hào)信息表示的節(jié)點(diǎn)之間的聯(lián)系應(yīng)該以不同的方式對(duì)待。
機(jī)遇：一種可能的解決方案是，通過(guò)設(shè)計(jì)一種隨機(jī)游走過(guò)程引入正關(guān)系邊和負(fù)關(guān)系邊。Hu 等人遵循這一思路，基于詞嵌入技術(shù)研發(fā)了一種稀疏圖嵌入模型。但是，他們的方法在一些小型的真實(shí)世界中的有符號(hào)網(wǎng)絡(luò)中的性能要差于作為對(duì)比基線的譜方法。另一種的可能的解決方案是重建一個(gè)有符號(hào)網(wǎng)絡(luò)的鄰接矩陣表征。然而，這又面臨著另外一個(gè)問(wèn)題：現(xiàn)實(shí)世界中的絕大部分鄰接連接是正關(guān)系。Shen 和 Chung 施加了更大的懲罰，使他們的棧式自編碼器模型更加關(guān)注重建稀缺的負(fù)邊而不是豐富的正邊。然而，在大多數(shù)情況下，我們并不能獲取關(guān)于大量節(jié)點(diǎn)的社區(qū)分配信息。因此，在有符號(hào)網(wǎng)絡(luò)中，社區(qū)發(fā)現(xiàn)的高效的無(wú)監(jiān)督方法仍然有待探索。
挑戰(zhàn) 5：社區(qū)嵌入
社區(qū)嵌入是一個(gè)新興的研究領(lǐng)域，這種方法將對(duì)社區(qū)而不是每個(gè)獨(dú)立的節(jié)點(diǎn)進(jìn)行嵌入。社區(qū)嵌入重點(diǎn)關(guān)注對(duì)社區(qū)進(jìn)行感知的高階近似而不是在節(jié)點(diǎn)鄰居之間的 1 階或 2 階近似。未來(lái)，社區(qū)嵌入研究面臨的挑戰(zhàn)有：（1）高昂的計(jì)算開(kāi)銷(xiāo)；（2）節(jié)點(diǎn)和社區(qū)結(jié)構(gòu)之間的關(guān)系評(píng)估；（3）應(yīng)用深度學(xué)習(xí)模型時(shí)發(fā)生的其它問(wèn)題，例如社區(qū)之間的分部漂移。
機(jī)遇：設(shè)想有一種智能的方法通過(guò)自動(dòng)選擇針對(duì)節(jié)點(diǎn)和/或社區(qū)的表征模塊來(lái)支撐社區(qū)嵌入。為此，Philip等人建議從以下研究目標(biāo)入手：（1）如何將社區(qū)嵌入整合到一個(gè)深度學(xué)習(xí)模型中？（2）如何為了「計(jì)算地更快」這樣的目標(biāo)直接嵌入社區(qū)結(jié)構(gòu)？（3）如何優(yōu)化整合好的深度社區(qū)發(fā)現(xiàn)學(xué)習(xí)模型中的超參數(shù)？
挑戰(zhàn) 6：網(wǎng)絡(luò)的動(dòng)態(tài)性
網(wǎng)絡(luò)的動(dòng)態(tài)性主要包含兩種情況：網(wǎng)絡(luò)拓?fù)涞淖兓?，以及在固定拓?fù)渖系膶傩缘淖兓?。拓?fù)涞淖兓瘯?huì)引起社區(qū)的演化。例如，添加或刪除一個(gè)節(jié)點(diǎn)會(huì)影響全局的網(wǎng)絡(luò)連接，因此它也會(huì)改變社區(qū)結(jié)構(gòu)。對(duì)于靜態(tài)網(wǎng)絡(luò)來(lái)說(shuō)，深度網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)學(xué)習(xí)模型在面對(duì)每個(gè)網(wǎng)絡(luò)的快照時(shí)，需要重新訓(xùn)練，這里面包含一些重復(fù)的工作。對(duì)于靜態(tài)網(wǎng)絡(luò)中的時(shí)序?qū)傩?，技術(shù)上的挑戰(zhàn)在于對(duì)于流數(shù)據(jù)的深度特征提取，這些流數(shù)據(jù)的概率分布和屬性隨時(shí)都會(huì)變化，它們引入圖數(shù)據(jù)作為深度學(xué)習(xí)模型輸入的另一部分。
機(jī)遇：針對(duì)時(shí)間和空間維度上的動(dòng)態(tài)特性，人們還沒(méi)有研發(fā)用于社區(qū)發(fā)現(xiàn)的深度學(xué)習(xí)模型。未來(lái)的研究方向包括：（1）發(fā)現(xiàn)并識(shí)別社區(qū)間的空間變化；（2）學(xué)習(xí)深度模式，它同時(shí)對(duì)時(shí)序特征和社區(qū)結(jié)構(gòu)信息進(jìn)行嵌入；（3）為社區(qū)發(fā)現(xiàn)任務(wù)研發(fā)一種統(tǒng)一的深度學(xué)習(xí)方法，它可以同時(shí)處理空間和時(shí)間特征。
挑戰(zhàn) 7：大規(guī)模網(wǎng)絡(luò)
大規(guī)模網(wǎng)絡(luò)指的是擁有數(shù)以百萬(wàn)計(jì)的節(jié)點(diǎn)和邊、大規(guī)模結(jié)構(gòu)化模式以及高度動(dòng)態(tài)性的大型網(wǎng)絡(luò)。因此，大規(guī)模網(wǎng)絡(luò)有其固有的規(guī)模特性（例如，社交網(wǎng)絡(luò)中與規(guī)模無(wú)關(guān)的特性，節(jié)點(diǎn)度的米率分布特性），這些特性會(huì)影響社區(qū)發(fā)現(xiàn)任務(wù)中的聚類(lèi)系數(shù)。此外，通過(guò)分解后的有關(guān)高維鄰接關(guān)系的近似度度量，研究人員將分布式計(jì)算應(yīng)用于可擴(kuò)展的學(xué)習(xí)，同時(shí)他們也面臨著魯棒的學(xué)習(xí)控制和協(xié)作計(jì)算的問(wèn)題。不斷變化的網(wǎng)絡(luò)拓?fù)溥M(jìn)一步增加了近似度估計(jì)的難度?？偠灾笠?guī)模網(wǎng)絡(luò)中的社區(qū)發(fā)現(xiàn)設(shè)計(jì)上述所有提到的挑戰(zhàn)，以及可擴(kuò)展學(xué)習(xí)方面的挑戰(zhàn)。
機(jī)遇：大規(guī)模網(wǎng)絡(luò)（例如，F(xiàn)acebook 和 Twitter）不僅提出了挑戰(zhàn)，也催生了設(shè)計(jì)更先進(jìn)的深度學(xué)習(xí)方法的機(jī)遇。為了充分利用大規(guī)模網(wǎng)絡(luò)中的豐富信息，社區(qū)上的聚類(lèi)任務(wù)更需要具有較低的計(jì)算復(fù)雜度并具有靈活性的新型無(wú)監(jiān)督算法。深度學(xué)習(xí)中用到的關(guān)鍵數(shù)據(jù)降維方法（即矩陣低秩近似）并不適用于大規(guī)模網(wǎng)絡(luò)，它在分布式計(jì)算場(chǎng)景下的計(jì)算開(kāi)銷(xiāo)也是很高昂的。因此，人們急需新型的深度學(xué)習(xí)框架、模型和算法。研發(fā)應(yīng)用于大規(guī)模網(wǎng)絡(luò)的深度學(xué)習(xí)方法需要通過(guò)精度和速度來(lái)評(píng)估，這種評(píng)估方式可能是最大的挑戰(zhàn)。
如今，我們生活在各種各樣的網(wǎng)絡(luò)中。發(fā)現(xiàn)這些網(wǎng)絡(luò)的內(nèi)在功能和特征有助于我們?nèi)娴乩斫庵車(chē)沫h(huán)境（尤其是在社交網(wǎng)絡(luò)中）。
社區(qū)還原了描述社會(huì)現(xiàn)象的復(fù)雜關(guān)系。傳統(tǒng)的社區(qū)發(fā)現(xiàn)方法曾經(jīng)依賴(lài)的是統(tǒng)計(jì)推斷和機(jī)器學(xué)習(xí)（譜聚類(lèi)）。然而，深度學(xué)習(xí)的發(fā)展極大地提升了社區(qū)發(fā)現(xiàn)方法的計(jì)算性能，用于社區(qū)發(fā)現(xiàn)的深度學(xué)習(xí)方法近五年來(lái)被廣泛地研究。
在這篇綜述文章中，Philip 等人全方位地回顧了模型和算法研發(fā)方面相應(yīng)的技術(shù)趨勢(shì)，并針對(duì)基于深度學(xué)習(xí)領(lǐng)域社區(qū)發(fā)現(xiàn)進(jìn)展做了詳細(xì)的闡述。
最為重要的是，這篇綜述還指出了將深度學(xué)習(xí)用于社區(qū)發(fā)現(xiàn)任務(wù)時(shí)存在的七個(gè)重大挑戰(zhàn)，這在一定程度上將為下一代社區(qū)發(fā)現(xiàn)研究指明方向。雷鋒網(wǎng)雷鋒網(wǎng)雷鋒網(wǎng)
雷峰網(wǎng)原創(chuàng)文章，未經(jīng)授權(quán)禁止轉(zhuǎn)載。詳情見(jiàn)轉(zhuǎn)載須知。
