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