中文题目：基于双曲图卷积的动态社区发现算法

论文题目：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。