機器之心專欄
機器之心編輯部
美國物理學會院士 Barabasi 教授在其 2012 年發表於 Nature Physics 的文章中指出：「21 世紀將是網路理論的世紀，它正在形成的理論和演算法框架將成為許多研究與應用領域的新的驅動力。」
大量研究顯示，複雜網路普遍具有一些顯著的統計特性，比如小世界效應、無標度分佈、網路彈性等。尤其是，Girvan 和 Newman 發現了複雜網路的另一個重要統計特性——社團結構，即網路通常會由一些稠密相連的結點簇組成。自此，學術界掀起了對複雜網路社團結構的研究熱潮。
本文是來自天津大學圖機器學習與資料探勘團隊，聯合莫納什大學、麥考瑞大學，以及聖路易斯華盛頓大學 AI 權威 Weixiong Zhang 教授、UIC 資料探勘權威 Philip S。 Yu 教授等對網路社團發現領域的最新綜述，首次以「從統計建模到深度學習」的新視角，為現代網路資料社團發現領域描繪出一幅宏偉而全面的藍圖。
論文連結：https：//ieeexplore。ieee。org/document/9511798
1. 內容簡介
社團檢測（community detection）是網路分析的基本任務，旨在將網路劃分為多個子結構以幫助揭示其潛在功能，被廣泛用於推薦、異常檢測、恐怖組織識別等領域。經典的社團檢測方法通常利用機率圖模型，採用各種先驗知識來推斷社團結構。隨著網路方法試圖解決的問題以及要分析的網路資料變得越來越複雜，研究者們提出了新的社團檢測方法，特別是利用深度學習將網路資料轉換為低維表徵的方法。儘管這些方法促進了社團檢測的發展，但目前仍然缺乏對社團檢測理論和方法基礎的系統回顧。因此，我們提出了一個統一架構來概述社團檢測領域的最新發展。我們首先全面回顧了現有的社團檢測方法，並介紹了一種新的分類法，該分類法將現有方法分為兩類：機率圖模型和深度學習。其次，我們討論了兩類方法的主要思想，並針對不同方法進行了詳細概述。此外，我們還發布了一些社團檢測領域常用的基準資料集，重點介紹了社團檢測在各種網路分析任務中的應用。最後，我們討論了社團檢測面臨的挑戰，並對未來可能的研究方向提出了建議。
圖 1。 社團檢測方法的分類細目
2. 基於機率圖模型的社團檢測方法
基於機率圖模型的方法通常採用啟發式或元啟發式的方法（網路建模）來檢測網路社團。依據機率圖模型的型別，我們將社團檢測方法細分為三類：有向圖模型、無向圖模型以及整合有向圖和無向圖的混合圖模型。
2.1 有向圖模型
有向圖模型主要基於隱變數（樣本中未觀察到的變數），利用結點或塊結構的相似性來生成網路中的邊。依據網路建模方法的不同，有向圖模型可以分為三類：隨機塊模型、主題模型和矩陣分解。它們具有紮實的理論基礎和較好的效能，得到了廣泛應用。
2。1。1 隨機塊模型
隨機塊模型（SBM）是一種有效的網路塊結構生成模型，其首次將統計建模應用到社團檢測。SBM 使用結點隸屬似然函式將網路中的結點機率性地分配給不同的社團（塊結構），透過推理似然函式來迭代推斷結點隸屬關係，推匯出網路中的隱藏社團。雖然已經提出了多種 SBM 變體，但它們的核心生成過程是類似的。生成過程可以分為兩步：1）迭代地為網路中的每個結點分配一個社團；2）計算或更新連線兩個結點的邊的機率。
表 1。 基於 SBM 的社團檢測方法
2。1。2 主題模型
主題模型（如 LDA）是一種能夠有效建模文字中隱藏主題的統計模型，透過使用潛在變數對主題進行建模。基於 LDA 的社團檢測方法可以分為兩類：一類將網路結構建模為文件；另一類對網路屬性進行建模以檢測社團。將網路結構建模為文件的方法首先假設網路中的每個結點可能屬於多個社團，並將社團視為“主題”，將結點視為“文件”；其次，選擇幾個社團作為初始社團，根據網路拓撲結構對社團進行迭代更新，得到最終的社團劃分；使用網路屬性的方法主要利用社交網路的屬性，例如使用者興趣，來發現社團。
2。1。3 矩陣分解
非負矩陣分解（NMF）既能使處理的資料的維度得到非線性的約減，還能使分解後的所有分量均為非負值。基於 NMF 的方法首先得到網路中結點高質量和低維的特徵，然後基於這些新特徵對結點進行聚類，從而發現高質量的社團結構。我們將基於 NMF 的方法分為五大類：基本 NMF、重疊 NMF、屬性 NMF、動態 NMF 以及半監督 NMF。
表 2。 基於 NMF 的社團檢測方法
2.2 無向圖模型
無向圖模型基於場結構（如馬爾可夫隨機場 MRF），使用一元和二元勢能的約束（如相鄰結點間社團標籤的一致性）來發現社團。基於無向圖模型的方法可以分為三類：拓撲 MRF、拓撲和屬性結合的 MRF 以及 MRF 和圖神經網路（GNN）整合的方法。
表 3。 基於 MRF 的社團檢測方法
2.3 有向圖和無向圖整合的模型
混合圖模型通常將有向圖和無向圖模型轉換為統一的因子圖（factor graph）來進行社團檢測。雖然這些方法在一定程度上提升了社團檢測的效能，但它們採用變分推斷或馬爾可夫鏈蒙特卡羅（MCMC）取樣對模型進行最佳化，這不可避免地帶來過高的計算複雜度。深度學習能夠有效的對高維網路資料進行最佳化，逐漸被應用於社團檢測。
3. 基於深度學習的社團檢測方法
基於深度學習的方法旨在學習一種面向社團的網路表徵來識別社團結構。它們利用一些學習策略將網路資料從原始輸入空間對映到低維特徵空間來推導網路表徵，具有低計算複雜度、高並行化等優點。依據學習策略的不同，基於深度學習的方法主要分為四類：基於自動編碼器的方法、基於生成對抗網路的方法、基於圖卷積網路的方法以及圖卷積網路和無向圖模型整合的方法。
3.1 基於自動編碼器的方法
自動編碼器（AE）是一種簡單但重要的神經網路模型，透過使用編碼器和解碼器以無監督的方式（最小化原始輸入和重構資料之間的誤差）學習最佳的網路表徵。依據使用的 AE 型別，社團檢測方法可以分為四類：堆疊 AE、稀疏 AE、降噪 AE 及變分 AE。
表 4。 基於 AE 的社團檢測方法
3.2 基於生成對抗網路的方法
生成對抗網路（ GAN ）具有強大的網路資料分析能力，其通常是無監督的，生成的新資料理論上與真實資料擁有相同的分佈。基於 GAN 的方法主要採用對抗學習的思想，透過生成器和判別器之間的對抗博弈來檢測社團。
3.3 基於圖卷積網路的方法
圖卷積神經網路（GCN）透過聚合結點的鄰域資訊來從全域性上捕獲用於社團檢測的結點表徵。基於 GCN 的方法分為兩類：監督 / 半監督 GCN 以及無監督 GCN。
3.4 圖卷積和無向圖模型整合的方法
圖卷積和無向圖模型整合的方法透過利用這兩類模型的優勢來檢測社團。考慮到 GCN 本質上是透過區域性特徵平滑來構建結點表徵，但其沒有考慮社團屬性，使得結點表徵不是以社團為中心的；無向圖模型通常定義全域性目標來描述社團，但其沒有考慮結點資訊，並且需要大量計算來學習模型引數。因此，GCN 和無向圖模型是互補的，可以將二者結合起來以更好的進行社團檢測。
4. 社團檢測的應用
我們首先討論了社團檢測常用的資料集，接著介紹了社團檢測的應用。
4.1 資料集
我們收集整理了兩類用於社團檢測的資料集，包括：人工合成數據集（如 Girvan-Newman），以及真實資料集（如社交網路、引用網路以及合作者網路等）。
表 5。 真實資料集
4.2 實際應用
社團檢測已被廣泛應用於各種各樣的領域和任務，例如：
2）神經科學：神經科學是研究神經系統和大腦的學科。隨著大腦對映和神經成像技術的最新發展，大腦也開始被建模為網路。基於大腦網路的社團檢測能夠幫助識別大腦中起作用或存在病理的功能部分。
3）影象理解：基於社團檢測的影象理解透過引入社團來生成更好的影象語義描述。
4）推薦：推薦通常是根據使用者購買或瀏覽歷史記錄中的資訊來建立使用者興趣檔案，進而向用戶推薦類似物品來解決使用者資訊過載問題。引入社團概念的社團發現透過有效檢測結點之間的關係來產生高質量的推薦結果。
5）連結預測：連結預測透過分析觀察到的網路結構和外部資訊來處理缺失的連線並預測未來可能的連線。引入社團概念的連結預測透過設計社團特定的相似度矩陣來分析預測結點間連結的機率。
5. 未來研究方向
雖然機率圖模型和深度學習促進了社團檢測領域的發展，但目前仍然存在一些有待解決的問題：
1）更大規模的網路：隨著網路資料規模的迅速增加，更大規模的網路逐漸成為不同科學領域的標準。這些網路通常具有數百萬或數十億的結點和邊，以及更復雜的結構模式。大多數現有的社團檢測方法可能需要大量的訓練例項或模型引數，或是透過網路縮減或近似的方式來處理這些網路，但是不可避免的會丟失一些重要的網路資訊並影響建模精度。因此，如何針對更大規模的網路，設計一個在準確性和效率方面都超過當前基準的框架是亟需解決的問題。
2）社團的可解釋性：大多數現有的社團檢測方法通常利用結果中排名靠前的詞或短語來解釋社團，但是由於詞的數量少以及詞之間的關係不明確，這些方法通常不能很直觀的理解社團語義。因此，如何充分利用網路資訊為社團提供更好的語義解釋也是未來的研究方向之一。
3）自適應的社團模型選擇：自適應模型旨在根據不同網路的特性（如異構或動態）或不同任務的特定要求（如最高準確度或最低時間複雜度）選擇最合適的演算法來檢測社團。雖然現有方法在一定程度上可以從一種網路或任務擴充套件到另一種網路或任務（不可避免地會影響模型的準確性和穩定性），但是很少有方法考慮模型的自適應。因此，如何在保持模型的準確性和穩定性的情況下，設計一個可以自適應特定任務或網路的統一架構，是具有挑戰但非常值得的。
4）更復雜的網路結構：真實世界中的網路可能是異構的、動態的、分層的或者不完全的。因此，如何設計新的社團檢測方法，更好的提升模型在不同型別網路上的社團檢測，也是重要的研究方向。
5）機率圖模型和深度學習的整合：雖然目前已經提出了一些將機率圖模型與深度學習相結合的方法，但其仍然是一個新興的研究區域。現實世界中的網路社團模式通常是多樣的，如異質性或隨機性的社團結構，如何利用機率圖模型和深度學習的優勢，設計新的魯棒方法，更準確地檢測網路中的社團結構。此外，如何設計新的整合演算法，以促進機率圖模型以及深度學習在其他領域的應用，如推薦或醫學診斷等，也是重要研究方向之一。
6. 總結
我們提出了一個統一架構來綜述現有的社團檢測方法。我們首先介紹了社團檢測問題，並引入了一個新的分類法，從學習的角度將現有方法分為兩類：機率圖模型和深度學習。其次，我們對這兩類方法進行了詳細的分析和比較。我們還介紹了社團檢測在各個任務和領域的廣泛應用，並討論了社團檢測未來可能的研究方向。
機器之心 · 機動組
機動組是機器之心發起的人工智慧技術社群，聚焦於學術研究與技術實踐主題內容，為社群使用者帶來技術線上公開課、學術分享、技術實踐、走近頂尖實驗室等系列內容。機動組也將不定期舉辦線下學術交流會與組織人才服務、產業技術對接等活動，歡迎所有 AI 領域技術從業者加入。