Philip S. Yu 團隊最新綜述！社區發現的深度學習方法：進展、挑戰、機遇

• 2020 年 5 月 22 日
• AI

雷鋒網AI科技評論按：

社區發現（Community Detection）是網路科學領域中一個經久不衰的重要問題。

隨著深度學習的發展，研究者們逐漸從傳統的統計推斷和譜聚類等方法中解放了出來。那麼，深度學習時代的社區發現工作有哪些特點，研究者們遇到了哪些挑戰，有哪些前景光明的研究方向呢？

近日，IJCAI 2020 上發表的一篇 Survey 文章，完整闡釋了這一研究方向的方法、挑戰和機遇。論文來自數據挖掘領域大牛 Philip S. Yu 團隊。

論文標題：

Deep Learning for Community Detection: Progress, Challenges and Opportunities 

社區發現（Community Detection）是網路科學領域中一個經久不衰的重要問題。隨著深度學習的發展，研究者們逐漸從傳統的統計推斷和譜聚類方法中解放了出來。那麼，深度學習時代的社區發現工作有哪些特點，研究者們遇到了哪些挑戰，有哪些前景光明的研究方向呢？

網路中的社區指的是一組由節點以及與其相連的邊緊密地形成的實體。社區發現旨在遵循「社區中的節點緊密相連，不同社區間的節點稀疏相連」的規則對實體集合進行聚類。包括譜聚類、統計推斷在內的傳統社區發現方法在處理高維圖數據時存在計算速度的問題。因此，近年來，深度學習方法被廣泛地應用。

在本文中，作者特別調研了社區發現的深度學習方法這一研究領域中的最新進展，並根據用到的深度神經網路、深度圖嵌入、圖神經網路對這些方法進行分類。由於目前深度學習的能力仍然不能滿足處理複雜網路結構的需求，本文作者指出了當前該領域面臨的挑戰和研究機遇。

一、社區發現

網路是有兩種基本的實體（即節點和邊）形成的。

根據圖理論，「社區」是一種內部節點緊密相連的子圖，它遵循以下特定的規則：

（1）社區內的節點緊密相連；

（2）不同社區中的節點稀疏相連。

人們也將社區看做一種聚類簇，其中相同社區內的節點可以共享共用的特性和/或扮演類似的角色。

這裡根據 Radicchi 等人基於網路統計分析給出的定義展開討論。根據節點在社區內部和外部的度，我們可以將社區分為兩類：強社區和弱社區。 節點的「內部度」代表將該節點與同一個社區中其它節點連接起來的邊數，節點的「外部度」則代表將該節點與屬於其它社區的節點連接起來的邊數。一個弱社區是其中的節點的內部度之和大於外部度之和的子圖。一個強社區是其中每個節點的內部度都大於外部度的子圖。針對社區的網路結構，本文採用了強社區的定義。

社區發現可以幫助我們理解網路內在的模式和功能。

在現實世界的應用中，社區將複雜系統中的資訊聚集了起來。舉例而言，

• Chen、Yuan 等人發現在「蛋白質-蛋白質」交互（PPI）網路中，被聚合到社區中的蛋白質具有相似的生物學功能；

• Chen 、Redner等人，在論文引用網路中，通過社區發現技術確定通過論文引用連接起來的課題的重要性、相互關聯以及演變情況；

• Zhang 等人，在企業網路中，通過研究離線的公司內部數據源以及在線的企業社交關係將僱員分組到不同的社區中；

• Yang 等人指出，在線社交網路中（例如 Twitter 和 Facebook）擁有共同的興趣或朋友的用戶可能來自同一個社區（如圖 1 所示）。

圖 1：社交網路中的社區發現示例。根據個體之間的緊密度，網路被劃分為兩個社區，即包含三個節點的社區 C_1 和包含四個節點的社區 C_2。

傳統的社區發現方法大部分都是基於統計推斷和機器學習發展出來的。例如， 在統計學領域非常具有代表性的社區發現方法「隨機分塊模型」（SBM）被廣泛用於描述社區是如何形成的。然而，在處理當下的複雜數據及和社交場景時，這些傳統的方法面臨著許多問題。此外，在機器學習領域，發現社區的工作往往被看做一個圖上的聚類問題。Ng 等人用特徵向量（例如鄰接矩陣和 Laplacian 矩陣）實現了將節點劃分到社區中的譜聚類方法，然而這種方法在稀疏網路上的性能較差。

同時，對於預設的社區數目的要求也特別限制了依賴統計推斷的模型的研發。在網路分析領域中，傳統的方法並沒有考慮到節點的屬性，而這些屬性描述了特徵的豐富資訊。此外，由於過高的計算複雜度，動態方法也很難被應用於大規模網路。總而言之，處理由圖及其屬性、大規模網路和動態環境形成的高維數據需要更強大的技術，從而同時兼顧高性能和計算速度。

深度學習使計算模型可以學習到具有多層次抽象的數據表徵。許多計算模型和演算法都需要對以網路結構形式存在的數據進行表徵學習。深度學習技術在學習非線性特徵時具有很大的優勢。這一點在諸如電腦視覺、自然語言處理等領域中都取得了廣泛的成功，在這些領域中數據有著內在的關係。在網路分析領域，深度學習可以有效地通過多層深度神經網路降低數據維度，從而完成社區發現、節點分類、鏈接預測等任務。

這裡重點研究深度學習在社區發現任務中的應用的新研究趨勢，Philip S. Yu等人的這篇綜述貢獻有：

（1）分析了將深度學習方法用於社區發現的優勢；

（2）從技術的視角，總結了目前最先進的研究，並對其進行分類；

（3）討論了仍然存在的挑戰，並指出了具有前景的未來工作的機遇。

據AI科技評論所知，這篇綜述也是首次全面回顧深度學習在社區發現中的應用，對研究人員和技術專家理解深度學習和社交網路領域的發展趨勢有著巨大幫助。

圖 2：社區發現之深度學習：進步、挑戰和機遇。

二、何為社區發現？

簡單來說，社區發現，即從網路 G 中發現社區 C。

這裡提到的網路是一種特殊的圖，它對現實世界中的系統（例如，互聯網、學術合作網路以及社交群組）中的複雜關係進行了抽象。在這裡，網路的概念主要強調的是其拓撲結構。

定義 1（網路 G）

基於圖理論，有權網路可以被表徵為 G=（V，E，W），而無權網路可以被表徵為 G=（V，E），其中 V 和 E 分別代表節點的集合和邊的集合，W 代表 E 相應的權值。每條邊通過權值描述連接強度或者容量。我們可以將無權圖的 W 視為1，將其從圖 G 中去除。

子圖 g⊆G 是對於圖的一種劃分，它保持了原始的網路結構。子圖的劃分遵循預先定義好的規則。根據不同的規則可能得到不同形式的子圖。社區是一種表徵真實社交現象的子圖；也就是說，在群組中存在一組具有緊密關係的對象。這裡遵循由 Radicchi 定義的強社區的概念。

定義 2（社區 C）

社區是一組網路中相互聯繫的子圖。社區中的節點具有密集的連接，而不同社區之間的節點具有稀疏的連接。根據一種將節點聚類到不同群組中的網路劃分方法給出一個社區 C_i，我們得到 C={C_1，C_2，…，C_k}，其中 k 代表可以從原始網路中被劃分出的社區數。被聚合到社區 C_i 中的節點 v 滿足：v 到社區內每個節點的內部度大於其外部度。

三、為什麼要使用深度學習進行社區發現？

與其他機器學習方法相比，深度學習的明顯優勢是它能夠將高維數據編碼到一個新的特徵表徵中。通過使用以圖結構的形式組織的數據表徵節點之間的聯繫，許多深度學習方法都可以學習到節點、鄰域以及子圖的模式。在多數現實場景中，數據缺乏節點標籤資訊和關於社區的先驗資訊，而深度學習在無監督學習的任務中體現出了優勢。除了簡單地利用網路拓撲來發現社區之外，一些方法還將語義描述作為數據中的節點屬性加以研究。在傳統社區發現方法中，這類方法主要基於鄰接矩陣和節點屬性矩陣。然而，深度學習可以構建更有效的節點屬性和社區結構表徵。

因此，深度學習填平了傳統社區發現方法中存在的關鍵短板。為了實現這一目標，近年來的工作指出了一些具有前景的研究方向：將深度學習模型應用於社區發現，以及基於社區的特性修改深度學習模型。將深度學習應用於社區發現的前景可以被表述為：

（1）通過深度學習模型提升傳統社區發現方法的性能；

（2）從對於深度學習至關重要的特徵維度上引入更多的資訊；

（3）從網路實體的拓撲和屬性入手，同時提升模型的學習性能和魯棒性；

（4）現在可以更好地從複雜的相關結構中對大規模網路進行檢測。

四、基於深度學習的社區發現

為了對近年來將深度學慣用於社區發現的研究進展進行概述，Philip等人從技術的角度總結了現有的方法。具體而言，他們首先對具有影響力的社區發現深度學習方法進行了分類。在每一類中，他們概述了框架、模型以及演算法的技術貢獻。

為了研究近年來被應用於社區發現的深度學習方法，圖 2 描述了相關深度學習方法的詳細分類情況，並相應地附上了總結出來的挑戰。本章將從基於深度神經網路、基於深度圖嵌入、以及基於圖神經網路的社區發現方法三個方面展開敘述。

4.1 基於深度神經網路的社區發現

深度神經網路在對複雜的關係進行建模和發現的任務中具有天然的優勢。考慮到現有的深度神經網路模型在社區發現領域的流形程度，作者選取了基於卷積神經網路（CNN）、基於自編碼器、基於生成對抗網路（GAN）的社區發現方法進行調研。

基於 CNN 的社區發現

CNN 的關鍵組件包含卷積操作和對卷積層結果的最大池化操作。卷積操作利用卷積核降低計算開銷。隨後，最大池化操作被用於特徵提取，這保證了 CNN 的魯棒性。

得益於 CNN 的發展，Xin 等人設計了一種用於社區發現的新型 CNN，並提出了一種用於拓撲結構不完整的網路的有監督演算法。由於社區發現被廣泛看做一種無監督聚類任務，科研人員對基於無監督 CNN 的社區發現進行了研究。人們研發出了在 CNN 框架下的係數矩陣卷積，從而專門進行對高度稀疏的鄰接矩陣的表徵。

基於自編碼器的社區發現

棧式自編碼器是一種深度學習模型，它在社區發現任務中表現出了強大的性能，可以表徵網路矩陣的非線性特徵。研究者們發現自編碼器和譜聚類在譜矩陣的低維近似方面有相似的框架，並受此啟發將自編碼器引入了社區發現領域。此後，Cao 等人提出了一種將網路拓撲和節點屬性相結合的棧式自編碼器，它提升了深度神經網路隱層的泛化能力。為了進一步解決網路拓撲和節點屬性之間的匹配問題，Cao 等人通過引入一個控制這種匹配的折中的自適應參數，研發了一種帶有圖正則化的自編碼器方法。

著眼於網路拓撲，Xie 等人提出在深度自編碼器中對鄰接矩陣進行變換，從而有效地學到節點相似度。同時，Bhatia 和 Rani 提出的自編碼器通過對隨機遊走序列建模學習節點的結構，他們通過優化社區結構的模組度對這種序列進行調優。

為了避免預設社團的數量，Bhatia 和 Rani 提出了一種層級棧式自編碼器，他們找出種子節點，基於網路結構有效地將其它節點加入到社區中。此後，該領域的研究旨在自適應地學習而不是預定義社區結構。Choong 等人提出的方法大大地提升了訓練損失驗證階段的計算效率。這種自動選擇機制保證了模型基於社區標準分配節點。

Xu 等人將包含具有正負號連接的網路成為有符號網路（signed network）。為了處理邊上的有符號資訊，Shen 和 Chung 提出了一種半監督的棧式自編碼器，它可以重構鄰接矩陣，為進一步的深度學習網路嵌入的學習表徵有符號網路。

基於生成對抗網路（GAN）的社區發現

GAN 包含兩種相互競爭的深度神經網路，因此它可以迅速調整訓練精度。典型的 GAN 是以無監督方式運行的，它們生成與訓練集中的數據具有相同統計特徵的新數據。對於網路數據來說，GAN 模型適用於無標籤的數據集和序列化的網路劃分。

Yang 和 Leskovec 等人基於對抗性機制，提出了社區隸屬關係圖模型（AGM）。AGM 基於「節點-社區」成員隸屬關係（node membership）的思想對重疊的社區中的節點進行編碼。每個社區都有一個單一的概率，使得社區結構可以在 GAN 中進行。Jia 等人通過將這種模型與 GAN 相結合研發了一種新型的框架，它根據具有中間項（即隸屬圖中的「節點-社區」成員隸屬關係）進行社區發現。

4.2 基於深度圖嵌入的社區發現

深度圖嵌入是一種將網路中的節點映射到一個低維向量空間中的技術。它將儘可能多的結構資訊保存到表徵中。通過圖嵌入，基於網路分析的機器學習任務（例如鏈接預測、節點分類和節點聚類）可以利用表徵的潛在特徵，這樣節省了主要由網路搜索引起的計算開銷。對於社區發現任務來說，基於節點表徵的圖嵌入的輸出支援聚類的任務（例如通過 k-means 聚類）。

基於深度非負矩陣分解的社區發現

非負矩陣分解（NMF）是一類將矩陣分解為兩個矩陣的演算法，它具有如下性質：三個矩陣都沒有負的特徵值。NMF 自動地對輸入數據的列進行聚類，通過訓練階段的誤差函數，使原始矩陣和兩個分解出的矩陣之間的近似誤差最小。

Ye 等人提出了一種用於社區發現的深度 NMF 模型，其中深度學習架構可以促進 NMF 學習原始網路結構和社區結構之間的層次化映射。在某些情況下，社區發現的工作需要與對帶有屬性的內容的語義理解同時進行。為此，研究人員以一種帶屬性的圖的形式表徵網路，這種圖同時包含了網路結構和節點的屬性。Li 等人特別針對帶屬性圖的社區發現任務提出了一種嵌入方法，它將帶有屬性的社區發現看做一個 NMF 優化問題。為了使演算法收斂，他們設計了一套可計算的迭代更新規則。

基於深度稀疏濾波的社區發現

鄰接矩陣反映出了網路的稀疏性。嵌入對輸入的成對關係進行編碼，從而避免在稀疏矩陣上進行搜索。稀疏濾波（SF）是一種有效的深度特徵學習演算法，它只用到了一個超參數，但可以處理高維輸入。SF 的關鍵模組是針對 L2 正則化後的特徵的稀疏性設計的簡單代價函數。對於網路（尤其是在大型網路中）的社區發現，Xie 等人基於深度稀疏濾波提出了一種高效的網路表徵方法。他們通過一種無監督的深度學習演算法劃分網路，從而提取網路特徵。

基於社區嵌入的社區發現

傳統意義上，圖嵌入重點關注單個的節點。Cavallari 等人研究了另一種重要的、但是鮮有人探索過的圖嵌入情況，他們重點關注對社區的嵌入。他們認為這種新的重要策略有益於社區發現任務。具體而言，社區嵌入的目標是在低維空間中學習一種社區的節點分布。我們可以通過過渡性（transitional）的圖嵌入方法使用這種新的節點分布，從而很好地保留網路結構，這反過來可以提升社區發現的性能。此外，Tu 等人提出了一種新的圖嵌入模型，它同時探測每個節點的社區分布，並且學習節點和社區的嵌入。

網路中的社區實際上反映了同一個社區中相似的觀點、行為等高階近似資訊。Zhang 等人提出了一種保留社區資訊的社交網路嵌入方法來學習網路表徵。他們提出的這種方法在社區檢測任務中體現出了性能的優越性。

4.3 基於圖神經網路的社區發現

近年來，圖神經網路（GNN）的迅猛發展表明了圖挖掘和深度學習技術融合的趨勢。基於 GNN 的社區發現被用於利用圖神經網路對網路上的複雜關係進行建模，並捕獲這種關係。例如，Chen 等人提出的有監督社區發現 GNN 引入了一種非回溯的運算符，來定義邊的鄰接性。這種方法可以提升學習性能。對於 GNN 來說，運算符的選擇非常方便。

圖卷積網路（GCN）是基於 CNN 研發的，它繼承了快速學習的能力。面對圖輸入數據，GCN 展現出了非常好的性能。GCN 帶來的巨大提升在於整合了考慮網路中實體概率分布的概率模型。例如，Jin 等人通過馬爾科夫隨機場解決了包含語義資訊的帶屬性網路中的半監督社區發現問題。Shchur 和 Gunnemann 將「伯努利-泊松」概率模型整合到 GCN 中，用於重疊社區發現問題。通過這種方法，卷積層可以識別複雜的網路模式。

五、挑戰和機遇

近年來（尤其是近 5 年來），用於社區發現的深度學習技術迅速發展。由於對現實世界具有重大的影響，這一領域持續受到研究人員的關注。儘管取得了令人欣喜的成果，在將深度學習應用於社區發現的領域中，仍然有一些挑戰有待被更好地解決。下面，本文將總結這些挑戰和機遇。

挑戰 1：社區數未知

長久以來，由於社區數未知而引發的挑戰始終沒有得到很好的解決。在機器學習領域中，社區發現經常被表示為一種無監督聚類任務。總現實世界的網路中提取出的研究數據大多是沒有標籤的。因此，我們很難獲取有關社區數的先驗知識。此外，大多數現有的深度學習社區發現方法（尤其是深度圖嵌入），通過評估潛在特徵空間中的節點相似度獲取分類節點。然而，在後續的聚類演算法中，聚類的目標數量仍然需要被事先定義。

機遇：對於這一挑戰，一個直接的解決方案是通過分析網路拓撲確定社區的數量，並將其整合到深度學習模型中。Bhatia 和 Rani 等人遵循這一思想，採用基於隨機遊走的訂製化 PageRank 演算法，通過將圖重構到一種線性的形式進行社區發現，並通過模組化的優化方法來應用調優。但是這些方法並不能保證網路中的每個節點可以被分配到特定的社區中。因此，我們需要為社區發現任務涉及新的模型，從而避免在分配社區的過程中漏掉某些節點。

挑戰 2：網路層次

網路層次反映了分層的網路結構，它將位於獨立的層上的多個群組連接了起來，從而形成一個更加複雜的網路。而每一層都專註於特定的功能。對於多層網路，用於社區發現的深度學習技術必須實現對於兩種層次上的表徵的提取。而且他們將面臨多層網路固有的挑戰，這包括不同的關係類型以及不同層中不同的稀疏程度。

機遇：為了區分不同種類的連接，Song 和 Thiagarajan 提出了一種具有特殊子圖設計的多層 DeepWalk 模型，從而保存了層次化的結構。但是他們並沒有同時優化可以用於所有層的公用表徵以及保留了特定層網路結構的局部表徵。他們的目的是利用不同層之間的依賴，而實際上這種依賴關係經常被破壞。此外，對於新的設計來說，還應該考慮與層數增加有關的可伸縮性問題。因此，在研發用於具有網路層次的社區發現的深度學習方法的問題上，我們還有很長的路要走。

挑戰 3：網路異質性

網路的異質性指的是網路中實體類型的顯著差異，而各種各樣的節點集合和它們之間複雜的聯繫形成了異質網路。因此，我們應該通過不同於同質網路的方式研究異質網路中的社區發現。在應用和研發深度學習模型和演算法時，應該解決異質網路實體上的概率分布的差異。

機遇：大多數之前的深度學習方法並不是基於網路異質性研發的。Change 等人設計了一種非線性嵌入函數，它被用於捕獲異質組件之間的交互。因此，未來在異質網路上至少存在兩個方面的研究機遇：（1）異質網路表徵的深度圖嵌入學習模型以及相關的支撐演算法；（2）採用新型訓練過程的特定深度學習模型，旨在學習隱藏層中的異構圖屬性。

挑戰 4：邊上帶符號的資訊

許多現實世界中的網路具有邊上的符號資訊（即正關係或負關係）。在有符號網路的環境下，用於社區發現的深度學習方法面臨的挑戰是：通過不同的符號資訊表示的節點之間的聯繫應該以不同的方式對待。

機遇：一種可能的解決方案是，通過設計一種隨機遊走過程引入正關係邊和負關係邊。Hu 等人遵循這一思路，基於詞嵌入技術研發了一種稀疏圖嵌入模型。但是，他們的方法在一些小型的真實世界中的有符號網路中的性能要差於作為對比基準線的譜方法。另一種的可能的解決方案是重建一個有符號網路的鄰接矩陣表徵。然而，這又面臨著另外一個問題：現實世界中的絕大部分鄰接連接是正關係。Shen 和 Chung 施加了更大的懲罰，使他們的棧式自編碼器模型更加關注重建稀缺的負邊而不是豐富的正邊。然而，在大多數情況下，我們並不能獲取關於大量節點的社區分配資訊。因此，在有符號網路中，社區發現的高效的無監督方法仍然有待探索。

挑戰 5：社區嵌入

社區嵌入是一個新興的研究領域，這種方法將對社區而不是每個獨立的節點進行嵌入。社區嵌入重點關注對社區進行感知的高階近似而不是在節點鄰居之間的 1 階或 2 階近似。未來，社區嵌入研究面臨的挑戰有：（1）高昂的計算開銷；（2）節點和社區結構之間的關係評估；（3）應用深度學習模型時發生的其它問題，例如社區之間的分部漂移。

機遇：設想有一種智慧的方法通過自動選擇針對節點和/或社區的表徵模組來支撐社區嵌入。為此，Philip等人建議從以下研究目標入手：（1）如何將社區嵌入整合到一個深度學習模型中？（2）如何為了「計算地更快」這樣的目標直接嵌入社區結構？（3）如何優化整合好的深度社區發現學習模型中的超參數？

挑戰 6：網路的動態性

網路的動態性主要包含兩種情況：網路拓撲的變化，以及在固定拓撲上的屬性的變化。拓撲的變化會引起社區的演化。例如，添加或刪除一個節點會影響全局的網路連接，因此它也會改變社區結構。對於靜態網路來說，深度網路社區發現學習模型在面對每個網路的快照時，需要重新訓練，這裡面包含一些重複的工作。對於靜態網路中的時序屬性，技術上的挑戰在於對於流數據的深度特徵提取，這些流數據的概率分布和屬性隨時都會變化，它們引入圖數據作為深度學習模型輸入的另一部分。

機遇：針對時間和空間維度上的動態特性，人們還沒有研發用於社區發現的深度學習模型。未來的研究方向包括：（1）發現並識別社區間的空間變化；（2）學習深度模式，它同時對時序特徵和社區結構資訊進行嵌入；（3）為社區發現任務研發一種統一的深度學習方法，它可以同時處理空間和時間特徵。

挑戰 7：大規模網路

大規模網路指的是擁有數以百萬計的節點和邊、大規模結構化模式以及高度動態性的大型網路。因此，大規模網路有其固有的規模特性（例如，社交網路中與規模無關的特性，節點度的米率分布特性），這些特性會影響社區發現任務中的聚類係數。此外，通過分解後的有關高維鄰接關係的近似度度量，研究人員將分散式計算應用於可擴展的學習，同時他們也面臨著魯棒的學習控制和協作計算的問題。不斷變化的網路拓撲進一步增加了近似度估計的難度。總而言之，大規模網路中的社區發現設計上述所有提到的挑戰，以及可擴展學習方面的挑戰。

機遇：大規模網路（例如，Facebook 和 Twitter）不僅提出了挑戰，也催生了設計更先進的深度學習方法的機遇。為了充分利用大規模網路中的豐富資訊，社區上的聚類任務更需要具有較低的計算複雜度並具有靈活性的新型無監督演算法。深度學習中用到的關鍵數據降維方法（即矩陣低秩近似）並不適用於大規模網路，它在分散式計算場景下的計算開銷也是很高昂的。因此，人們急需新型的深度學習框架、模型和演算法。研發應用於大規模網路的深度學習方法需要通過精度和速度來評估，這種評估方式可能是最大的挑戰。

六、結語

如今，我們生活在各種各樣的網路中。發現這些網路的內在功能和特徵有助於我們全面地理解周圍的環境（尤其是在社交網路中）。

社區還原了描述社會現象的複雜關係。傳統的社區發現方法曾經依賴的是統計推斷和機器學習（譜聚類）。然而，深度學習的發展極大地提升了社區發現方法的計算性能，用於社區發現的深度學習方法近五年來被廣泛地研究。

在這篇綜述文章中，Philip 等人全方位地回顧了模型和演算法研發方面相應的技術趨勢，並針對基於深度學習領域社區發現進展做了詳細的闡述。

最為重要的是，這篇綜述還指出了將深度學慣用於社區發現任務時存在的七個重大挑戰，這在一定程度上將為下一代社區發現研究指明方向。雷鋒網雷鋒網雷鋒網