聯合圖全局和局部互信息的重疊社團檢測算法

摘 要：圖神經網絡在學習節點表示中展現了其突出的能力，然而在社團檢測方面，大多數圖神經網絡模型仍然使用K-means來定位社團中心，為了克服K-means不適用于高維空間下聚類的缺點，提出了聯合圖的全局和局部互信息的重疊社團檢測算法（overlapping community detection algorithm using global and local mutual information of graph，overDGI），這是一種用于處理重疊社團檢測問題的圖神經網絡。首先，采用最大化圖互信息和社團互信息使得隸屬于同一社團的節點間的向量表示距離更近、更接近社團中心；然后，設計了一個目標分布來幫助模型更好地解決重疊社團檢測任務。綜合實驗表明，overDGI在重疊社團劃分上的表現對比現有的幾種基準算法都有很強的競爭力。

關鍵詞：重疊社團； 結構中心； 互信息

中圖分類號：TP301.6 文獻標志碼：A

文章編號：1001-3695（2023）08-020-2375-07

doi：10.19734/j.issn.1001-3695.2022.12.0787

Overlapping community detection algorithm using global andlocal mutual information of graph

Chen Yanbinga，b， Zhang Yinglonga

（a.School of Physics amp; Information Engineering， b.School of Computer， Minnan Normal University， Zhangzhou Fujian 363000， China）

Abstract：Graph neural network shows its outstanding ability in learning node representation. However， in terms of community detection， most graph neural network models still use K-means to locate community centers. In order to overcome the disadvantage that K-means is not suitable for clustering in high-dimensional space， this paper proposed an overlapping community of glo-bal and local mutual information of joint graphs， which was a graph neural network for dealing with overlapping community detection problems. Firstly，it used the node vector representation to express the graph structure information more accurately by maximizing graph mutual information. Then， on the basis of using the graph structure to locate the community center， by maximizing the community mutual information， the vector representation distance between nodes belonging to the same community was closer and closer to the community center. Finally， it designed a target distribution to help the model solve the overlapping community detection task better. Through comprehensive experiments， it shows that overDGI has strong competitiveness compared with several existing benchmark algorithms in overlapping community division.

Key words：overlapping communities; structure center; mutual information

0 引言

社團檢測［1，2］是復雜網絡研究和分析中的一項重要任務，它在介觀尺度上觀察和理解網絡，這有助于分析和挖掘群體之間的關系、模式和功能，發現隱藏的內部關系和規律［3］。

除了網絡拓撲，網絡節點中包含的屬性信息對于理解社團結構至關重要［4］。微博、Facebook等許多社交平臺上的數據都包含用戶的特征，例如基本個人信息、文本、圖像、IP以及他們的關系，這種具有節點屬性網絡通常被稱為屬性圖［5］。節點屬性可以用來補充屬性圖社團檢測中的結構信息，減少網絡結構稀疏性，提高社團檢測的準確性［6］。

在現實世界中，結合屬性和結構信息來發現社團是一項重要任務，但也會面臨相當大的挑戰。

圖神經網絡（graph neural network，GNN）［7］在圖結構數據的表示學習中取得了顯著進展，在節點分類、鏈接預測以及社團檢測等學習任務中表現優異。而且，圖神經網絡在分析屬性圖方面具有顯著的解釋能力［8］，為此學者們提出一種低維節點表示法，以便屬性圖中靠近的節點在嵌入空間中也同樣靠近［9］。最近，基于互信息（mutual information，MI）的DGI（deep graph infomax）［10］通過以下步驟來發現社團：a）將輸入圖和相應的擾亂圖嵌入到低維的向量空間中;b）讀出函數將輸入圖匯總為向量;c）區分輸入圖（正樣本）和擾亂圖（負樣本）;d）最大化該匯總向量和隱藏表示之間的互信息，最大化這種互信息被證明等同于最大化輸入節點特征和隱藏向量之間的互信息;d）使用簡單的聚類方法，如（K-means［11］）對學習到的節點表示進行聚類。然而，這種簡單的聚類方法不僅無法捕獲社團結構，而且在檢測重疊社團方面也無能為力，但大多數現實世界的網絡中的社團是重疊的［12］。

一些學者曾多次嘗試解決這個問題。vGraph［13］是一個可以同時學習節點嵌入和發現重疊社團的統一的框架，它是一種通過學習節點嵌入和上下文以幫助社團檢測的概率生成模型。VECODER［14］在vGraph的基礎上進行了擴展，它通過建模節點屬性和網絡結構之間的交互，并學習直接用于節點嵌入和發現社團的感知節點表示。這些方法通過使用學習的節點嵌入來重構鄰接信息，然而，社團間的連接可能會誤導模型作出錯誤的判斷，從而使不同集群的節點劃分到同一個社團。因此，如何在實現高質量節點表示的同時進行有效的重疊社團檢測成為許多案例的必要條件，這促使了本文的研究。

基于上述動機，本文針對屬性圖提出了一種聯合圖的全局和局部互信息的重疊社團檢測算法overDGI，用于同時學習重疊社團檢測和節點表示。與基于節點對學習節點表示的VECODER和vGraph不同，本文使用DGI最大化互信息，并捕獲局部和全局結構信息；然后引入了一個社團互信息［15］，它是在節點表示和通過圖形結構定位的社團中心之間計算的，社團互信息有助于overDGI使數據表示更接近集群中心；最后，設計了一個面向重疊社團的目標分布P，以更好地學習重疊社團檢測任務的表示。

本文工作的主要貢獻如下：a）提出了一種基于深度圖互信息的重疊社團檢測模型，該模型能夠有效地將DGI應用到重疊社團檢測任務中；b）設計了一種有效的社團中心定位方法，通過定位社團中心來解決K-means在高維空間無法有效聚類的問題；c）提出了一種新的最大化社團互信息的策略來幫助節點表示編碼更多的社團相關的特征；d）設計了一種面向重疊社團的目標分布，該目標分布能夠指導整個模型的訓練過程，從而學習到面向重疊社團的社團分布。

1 相關研究

1.1 社團檢測

早期的社團檢測算法旨在通過分析復雜網絡的拓撲結構，發現復雜網絡中有意義的社團結構。例如，模塊化優化算法［16］主要以模塊化函數為目標函數進行優化，并采用迭代法不斷提高模塊化值，從而得到模塊化的最優值對應于最優的網絡社團劃分結果。然而，傳統方法通常只檢測不重疊的集群，并不符合現實場景。相應的，非負矩陣分解（non-negative matrix factorization，NMF）［17］作為一種有效的非監督學習方法，由于其能夠學習節點對社團的軟分配，也逐漸被應用于重疊社團結構分析中。例如，BigCLAM［18］使用節點—社團隸屬關系圖模型學習代表節點社團成員關系的潛在向量。另一種方法CESNA［19］，在BigCLAM的基礎上，同時考慮了網絡拓撲和節點屬性。LC［20］提出采用一種鏈接聚類算法，該算法對節點的鏈接進行分區以進行重疊社團檢測。GREESE［21］通過選擇一個節點及其最相似的鄰居來構建一個耦合種子，然后使用改進了局部社團檢測的適應度函數來擴展這個耦合種子。CPSO［22］基于標簽傳播重新定義了粒子的編碼和解碼以及粒子的交叉繼承和變異。

1.2 節點表示學習

許多網絡分析任務表明，節點表示學習的目的是學習網絡的低維向量表示。節點表示作為一種保持網絡鄰近性結構的方法，在過去幾年中受到了廣泛關注。例如，DeepWalk［23］使用隨機游走方法對圖中的節點進行采樣，以確定圖中節點之間的共現關系。node2vec［24］優化了DeepWalk體系結構中隨機漫步的序列提取策略，設計了一個有偏隨機游走過程來探索不同的鄰域。LINE［25］關注網絡節點的一階和二階接近度。一階接近度是節點之間是否有邊，二階接近度是節點間公共近鄰集合的相似度。上述方法通過K-means或高斯混合模型得到每個節點的社團分配。近 年來，GCN［26］已經成為節點表示領域的一種流行方法，它試圖通過卷積運算來收集圖中某個節點周圍鄰居的節點信息，從而將卷積神經網絡應用到圖中。

1.3 結合社團檢測和節點表示學習

近年來，一些學者嘗試將節點表示學習與社團檢測相結合。其中一些方法提出了一個可選的優化過程，即依賴于節點表示來生成良好的社團分配，反之亦然。ComE［27］和CNRL［28］使用隨機游走對圖中的節點進行抽樣，得到節點之間的共現關系，也繼承了隨機游走的缺點。另外，GEMSEC［29］是一個使用節點序列抽樣的模型，它在社團檢測期間同時學習節點嵌入，但它僅限于檢測非重疊的社團。ACNE［30］采用感知步行策略以獲得包含更多可能邊界節點的路徑，以改進重疊社團檢測。CDE［31］基于節點屬性和社團結構嵌入，將屬性圖社團檢測描述為一個非負矩陣分解優化問題。此外，基于生成模型的方法也逐漸成為一種競爭性的方法，引起了許多學者的關注。vGraph和VECODER使用變分推理重構鄰接矩陣并更新模型。CommunityGAN［32］使用生成對抗網絡（GAN）將圖形表示學習和重疊社團檢測相結合。需要注意的是，ComE和vGraph需要兩個嵌入，即節點嵌入和上下文嵌入來解決這兩個任務，這在某種程度上會浪費計算資源。vGraph和VECODER依賴鄰接矩陣來學習節點表示，節點表示可能有噪聲和集群不可知的邊緣，這可能導致模型將來自不同集群的節點劃分在一起。相反，overDGI學習基于DGI單個社團感知節點表示，以最大化相互信息并捕獲局部和全局結構信息。

2 基本概念

3 重疊社團檢測模型

本文提出的基于深度圖互信息的重疊社團檢測模型overDGI，其總體框架如圖1所示。首先，根據原始數據構造一個擾亂圖以充當負樣本。然后，將原始數據和隨機打亂特征順序后得到的擾亂圖充當GCN自動編碼器的輸入數據分別學習出正樣本表示和負樣本表示。

接下來，將從三個方面聯合優化學習到的節點表示：

a）通過對比正樣本對和負樣本對，尋求最大化圖級別表示與其節點表示之間的互信息，使得節點表示盡可能表達圖結構信息。

b）通過網絡拓撲來定位社團中心，然后使用節點與社團中心點之間的向量表示距離定義其與k個社團的隸屬度分布原始分布Q。最后將Q、社團中心以及正負樣本對輸入到鑒別器中，通過最大化社團互信息來幫助模型在更新時學習每個節點的更多社團級信息，從而使學習到的節點嵌入可以面向社團檢測。

c）為了使節點—社團隸屬度分布Q能有效幫助重疊社團檢測，本文設計一種目標分布P，該目標分布假設每個節點的隸屬度分布在某種程度上更接近其鄰居的隸屬度分布。然后通過最小化目標分布P和原始分布Q之間的KL散度來指導GCN編碼器的訓練過程。

overDGI通過節點表示來計算節點—社團的隸屬度分布Q，然后通過最小化目標分布P和原始分布Q之間的KL散度來指導模型學習到更好的節點表示，最終形成良性循環。

3.1 圖互信息最大化

3.2 社團中心點檢測

從屬性圖自身出發，GCN編碼器能夠學習到有用的向量表示，其中包含結構信息和屬性信息，然而卻忽略了節點和社團之間的關系。

commDGI在解決這類問題時采用的是一種可微的K-means聚類，它將節點和嵌入空間中的簇中心軟分配給簇，使用軟最小值分配來根據距離將每個點分配給社團中心。然后通過最大化社團互信息來幫助社團嵌入，將節點表示作為局部信息，將社團中心作為社團級別的信息。然而， K-means聚類在高維空間中的表現往往差強人意，因為在高維空間中樣本的分布范圍往往比較分散，這時再用樣本之間的距離來度量相似性往往不具有很強的說服力［34］。因此，本文通過采用結構中心定位的方法找出分布在不同集群中的結構中心，以此來代替K-means尋找社團中心的節點。

在尋找結構中心的過程中需要考慮如何衡量一個節點的密度，節點密度是考慮一個節點能否成為結構中心的重要指標。首先，結構中心的特點是密度比其臨近的節點高，而且與密度較高的節點之間的距離相對較遠。結構中心一般具有較高的中心性且分布在不同的社團中。此處，本文將節點密度用節點的度數表示，節點的密度表示如下：

3.3 社團互信息最大化

3.4 面向重疊社團的優化

3.5 聯合優化

4 實驗

4.1 數據集

4.2 對比模型

4.3 評估指標和參數設置

4.4 實驗結果

4.5 嵌入維度分析

本節對幾個重疊的社團檢測任務進行了實驗以探索改變overDGI的嵌入維度如何影響其在重疊社團檢測任務的性能。圖3顯示了overDGI如何在不同數據集的不同嵌入維度中執行。可以看到，在圖3（d）中，增加了嵌入維度可以顯著提高overDGI的整體性能。但在，在其他數據集中增加維度不一定能改善實驗結果，這是由于社團中心是由拓撲結構得到的，所以overDGI對維度并不敏感，但是，當嵌入維度設置為128時，可以看到overDGI的實驗結果有較為明顯的優勢。由于需要同時考慮增加節點維度可能會消耗更多的計算資源，所以overDGI將嵌入維度設置為128。

4.6 閾值τ的分析

4.7 平衡系數α的分析

5 結束語

結合節點表示來更好地進行社團檢測是一個具有挑戰性的問題，尤其是當假設社團是重疊的情況下，如何將這三種問題融合在同一個框架中并學習到高質量的社團是overDGI致力解決的問題。overDGI使用DGI作為基本框架，并提出了一種新的模型，用于重疊的社團檢測任務。首先使用DGI來最大化圖級表示和節點級表示之間的互信息。接著，通過結構中心定位法定位社團中心，然后應用面向社團的互信息對更多與社團相關的節點特征進行編碼。最后，設計一個目標分布 ，以更好地學習重疊社團檢測任務的表示。通過對比實驗，使用Jaccard和F1值驗證了overDGI算法的合理性和有效性。由于overDGI在劃分社團時要手動確定社團數量，所以社團數量設置的有效性直接影響算法的結果。在今后的工作將研究各種社團檢測和社交網絡分析技術，并優化社團中心定位策略來自動確定社團數量。

參考文獻：

［1］Chunaev P. Community detection in node-attributed social networks： a survey［J］. Computer Science Review， 2020，37（8）： article ID 100286.

［2］張應龍， 夏學文， 徐星， 等. 面向標簽傳播算法的社團檢測研究現狀及展望［J］. 小型微型計算機系統， 2021，42（5）： 1093-1102. （Zhang Yinglong， Xia Xuewen， Xu Xing， et al. Review on label propagation algorithms for community detection［J］. Journal of Chinese Computer Systems， 2021，42（5）： 1093-1102.）

［3］寧懿昕， 謝輝， 姜火文. 圖神經網絡社區發現研究綜述［J］. 計算機科學， 2021，48（S2）： 11-16. （Ning Yixing， Xie Hui， Jiang Huowen. A review of research on graph neural network community discovery［J］. Computer Science， 2021，48（S2）： 11-16.）

［4］Yang Tianbao， Jin Rong， Chi Yun， et al. Combining link and content for community detection： a discriminative approach［C］//Proc of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.New York：ACM Press， 2009： 927-936.

［5］張伊揚， 錢育蓉， 陶文彬， 等. 基于深度學習的屬性圖異常檢測綜述［J］. 計算機工程與應用， 2022，58（19）： 1-13. （Zhang Yiyang， Qian Yurong， Tao Wenbing， et al. Survey of attribute graph anomaly detection based on deep learning［J］. Computer Enginee-ring and Applications， 2022，58（19）： 1-13.）

［6］Zhou Yang， Cheng Hong， Yu Xu. Clustering large attributed graphs： an efficient incremental approach［C］//Proc of the 10th IEEE International Conference on Data Mining. Piscataway，NJ：IEEE Press，2010： 689-698.

［7］Su Xing， Xue Shan， Lyu Fanzhen， et al. A comprehensive survey on community detection with deep learning［J］. IEEE Trans on Neural Networks and Learning Systems， 2021，2021（1）： 1-21.

［8］Jin Di， Yu Zhizhi， Jiao Pengfeng， et al. A survey of community detection approaches： from statistical modeling to deep learning［J］. IEEE Trans on Knowledge and Data Engineering， 2021，2021（1）： 1.

［9］Tian Yu， Zhao Long， Peng Xi， et al. Rethinking kernel methods for node representation learning on graphs［J］. Advances in Neural Information Processing Systems， 2019，32（1）： 59-69.

［10］Velickovic P， Fedus W， Hamilton W L， et al. Deep graph infomax［J］. ICLR（Poster），2019，2（3）： 4-14.

［11］Krishna K， Murty M N. Genetic K-means algorithm［J］. IEEE Trans on Systems， Man， and Cybernetics， 1999，29（3）： 433-439.

［12］Shchur O， Günnemann S. Overlapping community detection with graph neural networks［EB/OL］.（2019-09-26）. https：//arxiv.org/abs/1909.12201.

［13］Sun Fan Yun， Qu Meng， Hoffmann J， et al. vGraph： a generative model for joint community detection and node representation learning［J］. Advances in Neural Information Processing Systems， 2019，32（1）： 19-31.

［14］Khan R A， Anwaar M U， Kaddah O， et al. Variational embeddings for community detection and node representation［EB/OL］. （2021-01-11）. https：//arxiv.org/abs/2101.03885.

［15］Zhang Tianqi， Xiong Yun， Zhang Jiawei， et al. CommDGI： community detection oriented deep graph infomax［C］//Proc of the 29th ACM International Conference on Information amp; Knowledge Management. New York：ACM Press，2020： 1843-1852.

［16］Newman M E J， Girvan M. Finding and evaluating community structure in networks［J］. Physical review E， 2004，69（2）： article ID 026113.

［17］Lee D D， Seung H S. Learning the parts of objects by non-negative matrix factorization［J］. Nature， 1999，401（6755）： 788-791.

［18］Yang J， Leskovec J. Overlapping community detection at scale： a nonnegative matrix factorization approach［C］//Proc of the 6th ACM International Conference on Web Search and Data Mining.New York：ACM Press， 2013： 587-596.

［19］Yang J，McAuley J，Leskovec J. Community detection in networks with node attributes［C］//Proc of the 13th IEEE International Conference on Data Mining. Piscataway，NJ：IEEE Press， 2013：1151-1156.

［20］Ahn Y Y，Bagrow J P，Lehmann S. Link communities reveal multiscale complexity in networks［J］. Nature，2010，466（7307）：761-764.

［21］Asmi K， Lotfi D， Abarda A. The greedy coupled-seeds expansion method for the overlapping community detection in social networks［J］. Computing， 2022，104（2）： 295-313.

［22］Jiang Wenjun， Pan Shucan， Lu Chaohai， et al. Label entropy-based cooperative particle swarm optimization algorithm for dynamic overlapping community detection in complex networks［J］. International Journal of Intelligent Systems， 2022，37（2）： 1371-1407.

［23］Perozzi B， Al-Rfou R， Skiena S. DeepWalk： online learning of social representations［C］//Proc of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.New York：ACM Press， 2014： 701-710.

［24］Grover A， Leskovec J. node2vec：scalable feature learning for networks［C］//Proc of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 2016： 855-864.

［25］Tang Jian， Qu Meng， Wang Mingzhe， et al. LINE： large-scale information network embedding［C］//Proc of the 24th International Conference on World Wide Web. 2015： 1067-1077.

［26］Welling M， Kipf T N. Semi-supervised classification with graph con-volutional networks［C］//Proc of International Conference on Lear-ning Representations. 2016： 1035-1046.

［27］Cavallari S， Zheng V W， Cai H， et al. Learning community embedding with community detection and node embedding on graphs［C］//Proc of ACM on Conference on Information and Knowledge Management. New York：ACM Press，2017： 377-386.

［28］Tu Cunchao， Zeng Xiangkai， Wang Hao， et al. A unified framework for community detection and network representation learning［J］. IEEE Trans on Knowledge and Data Engineering， 2019，31（6）： 1051-1065.

［29］Rozemberczki B， Davies R， Sarkar R， et al. Gemsec： graph embedding with self clustering［C］//Proc of IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining. 2019： 65-72.

［30］Chen Junyang，Gong Zhiguo，Mo Jiqian， et al.Self-training enhanced： network embedding and overlapping community detection with adversa-rial learning［J］. IEEE Trans on Neural Networks and Learning Systems， 2021，33（11）： 6737-6748.

［31］Li Ye， Sha Chaofeng， Huang Xin， et al. Community detection in attributed graphs： an embedding approach［C］//Proc of AAAI Confe-rence on Artificial Intelligence. 2018.

［32］Jia Yuting， Zhang Qinqin， Zhang Weinan， et al. CommunityGAN： community detection with generative adversarial nets［C］//Proc of World Wide Web Conference. 2019： 784-794.

［33］Ren Yuxiang， Liu Bo， Huang Chao， et al. Heterogeneous deep graph infomax［EB/OL］. （2019）. https：//arxiv.org/abs/1911.08538.

［34］Aneiros G， Cao R， Fraiman R， et al. Recent advances in functional data analysis and high-dimensional statistics［J］. Journal of Multivariate Analysis， 2018，170： 3-9.

［35］Van Der Maaten L， Hinton G. Visualizing data using t-SNE［J］. Journal of Machine Learning Research， 2008，9（11）： 2579-2605.

［36］Mcauley J， Leskovec J. Discovering social circles in ego networks［J］. ACM Trans on Knowledge Discovery from Data， 2014，8（1）： 1-28.

［37］Wang Xiao， Cui Peng， Wang Jing， et al. Community preserving network embedding［C］//Proc of the 31st AAAI Conference on Artificial Intelligence. 2017： 1-11.

［38］Ye Fanghua， Chen Chuan， Zheng Zibin. Deep autoencoder like nonnegative matrix factorization for community detection［C］//Proc of the 27th ACM International Conference on Information and Knowledge Management.New York：ACM Press， 2018： 1393-1402.

［39］Whang J J， Dhillon I S， Gleich D F. Non-exhaustive， overlapping K-means［C］//Proc of SIAM International Conference on Data Mining.［S.l.］：Society for Industrial and Applied Mathematics， 2015： 936-944.