基于雙曲圖卷積的動態社區發現算法
中文題目：基于雙曲圖卷積的動態社區發現算法
論文題目：Dynamic community detection algorithm based on hyperbolic graph convolution
錄用期刊：International Journal of Intelligent Computing and Cybernetics（EI）
原文DOI：10.1108/IJICC-01-2024-0017
作者列表：
1） 吳衛江 中國石油大學（北京）人工智能學院 計算機系教師
2） 譚和平 中國石油大學（北京）人工智能學院 計算機技術專業 碩士2020級
3） 鄭藝峰 漳州閩南師范大學 計算機科學學院 計算機系教師
摘要:
社區發現是分析復雜網絡結構特征的關鍵因素，傳統的動態社區發現方法往往不能有效解決雙曲空間中深度網絡信息丟失和計算復雜度的問題。本文提出了一種基于雙曲空間的動態圖神經網絡社區發現模型(HSDCDM)，將節點特征投影到雙曲空間，利用Poincare和Lorentz模型上的雙曲圖卷積模塊實現特征融合和信息傳遞，利用時間記憶模塊快速捕獲時域信息，在社區聚類模塊，結合空間域和時間域的節點特征對社區結構進行劃分。實驗結果表明，HSDCDM顯著提高了分層網絡中社區檢測的質量。
背景與動機:
雙曲空間具有獨特的幾何特性，其在處理具有無標度或層次結構的圖形數據時，較歐幾里得空間具有顯著優勢，在傳統方法中，為了將圖卷積推廣到雙曲空間，首先將節點特征映射到雙曲流形的切空間，然后在切空間中應用歐幾里得圖卷積操作，最后將處理過的特征投影回原始雙曲流形，以保持它們在雙曲空間中的幾何關系。信息在傳遞過程中會被稀釋或丟失，導致網絡的上層無法充分捕捉到關鍵特征，另外，傳統的循環神經網絡單元無法在雙曲空間中有效提取時間特征，計算效率也不高。為了解決上述問題，本文提出了一種基于雙曲圖神經網絡的雙曲空間動態社區發現模型HSDCDM。
設計與實現:
HSDCDM的核心架構包括以下三個關鍵模塊：
1.雙曲圖卷積模塊：該模塊負責從網絡中的節點提取空間特征信息。首先，將網絡的節點特征從歐幾里得空間映射到雙曲空間中，為節點特征提供更復雜的空間表示，使其能夠更好地捕捉網絡中的層次結構；其次，使用基于雙曲空間的卷積操作提取節點的空間特征；最后，使用殘差連接增強信息流動，捕捉高階拓撲結構特征，避免節點特征過于平滑。
2.時間記憶模塊：該模塊旨在捕捉網絡中事件變化的時間動態。引入了輕量級的HSRU單元，在雙曲空間中進行并行計算，引入了專門的遺忘門機制來動態調整信息的更新。提高了處理時間序列數據的效率，在大規模高維數據中表現尤為明顯。
3.社區聚類模塊：該模塊通過將前兩個模塊生成的節點特征輸入到HK-means算法中進行聚類。HK-means是一種在雙曲空間中改進的K-means算法，適用于非歐幾里得幾何的網絡數據。在該模塊中，用雙曲距離替代歐幾里得距離進行節點間的距離計算，提高了聚類的準確性。
總體框架如圖所示：
圖1 HSDCDM整體框架
實驗結果及分析:
實驗在WC、PS、NCC、CollegeMSG等動態網絡數據集上進行，利用NMI和ARI做評價指標。
如圖2，(a)和(b)顯示了PS數據集上的評價結果，HSDCDM的NMI值和ARI值隨著時間的推移呈穩步上升趨勢。(c)和(d)顯示了WC數據集上的評價結果，在NMI指標上，HSDCDM的最大值為0.7396，較其他算法總體改進至少為2.9%。在ARI指標上，HSDCDM的最大值為0.6699，仍然領先于其他算法。
圖2 PS和WC數據集的NMI和ARI評價結果
如圖3，(a)和(b)顯示了NCC數據集上的評估結果。在NMI指標上，HSDCDM的最大值為0.558，與DeepWalk算法相比，整體提升了8.93%。值得注意的是，DeepWalk在該數據集上獲得了最高的ARI值0.1544。這意味著，DeepWalk作為一種靜態圖嵌入方法，盡管在數據集開始時取得了很好的結果，但隨著網絡結構的推移而演變，很難始終如一地捕獲圖的關鍵特征。(c)和(d)顯示了CollegeMSG數據集上的評價結果，HSDCDM算法在NMI和ARI值上呈現出相對穩定的增長。與IDCDGT相比，HSDCDM在NMI上提高了8.5%，在ARI上提高了10.12%。而EvolveGCN在該數據集上取得了較差的結果，說明作為動態圖嵌入方法，該算法更關注模型權參數的動態變化，忽略了圖結構的變化，當網絡中節點增加或突然消失時，它的性能就會降低，進一步驗證了圖結構動態變化在動態圖嵌入中的重要性。
圖3 NCC和CollegeMSG數據集的NMI和ARI評價結果
結論:
本文提出了一種基于雙曲圖卷積的動態社區檢測模型，利用改進的HGRU學習和更新HGCN內的參數，將HGCN提取的網絡拓撲與剩余連接和節點屬性特征融合，通過HSRU提取輸出節點拓撲特征并更新節點的時態特征，最后利用節點的雙曲特征通過HK-means進行聚類。實驗表明，該模型在實驗數據集上表現良好。
關于作者:
吳衛江，中國石油大學（北京）人工智能學院計算機系副教授，校級教學名師，主要研究方向為人工智能、數據挖掘和數據庫技術，主持和參與多項橫項課題。聯系方式：wuweijiang@cup.edu.cn。