DiMAE：一种基于状态空间建模的半监督社区检测框架，通过几何正则化的相似性扩散算法实现

《Knowledge-Based Systems》：DiMAE: A State-Space Modeling Framework for Semi-Supervised Community Detection via Geometry-Regularized Similarity Diffusion

社区检测面临稀疏连接、噪声观测和模糊边界挑战，DiMAE通过几何正则化三重扩散生成稳定多尺度相似性序列，结合选择性Mamba状态空间编码器线性建模扩散深度，采用非负解码机制生成可解释社区原型，有效缓解过平滑问题，并在低标注（5%节点）场景下显著优于基线方法。

　　

作者：Ke Yuxian、Sun Yi、Li Qizhang、Zhang Hongrui、Zhang Qiyue、Deng Tao、Wang Shuwan、Yuan Limengzi、Zhu Dongqin

新疆石河子大学信息科学与技术学院，中国新疆石河子市北四路832000

摘要

在信息网络中，社区检测仍然是一个具有挑战性的问题，这主要是由于网络连接性稀疏、观测数据存在噪声、社区边界不明确以及监督信息有限所致。现有方法往往难以在复杂的高阶结构建模与稳定性、可扩展性和鲁棒性之间取得平衡，尤其是在深度传播导致过度平滑或结构漂移的情况下。本文提出了DiMAE，这是一种基于几何正则化相似性扩散的半监督社区检测状态空间建模框架。DiMAE通过三角扩散方案构建多阶相似性表示序列，每个扩散步骤都受到原始相似性结构的约束，从而有效稳定了深度传播过程。为了以线性复杂度模拟不同扩散深度之间的长距离依赖关系，采用了选择性的Mamba状态空间编码器来捕捉全局结构模式，而无需依赖注意力机制。此外，还集成了一种轻量级的半监督正则化策略，以在节点标签有限的情况下细化模糊的社区边界；非负解码机制则确保了社区原型的可解释性。在合成网络和真实世界网络上的大量实验表明，DiMAE在稀疏和高度混合的环境中，以及在极有限的监督信息下（例如只有5%的节点被标记），其性能始终优于现有的最佳方法。实验结果证实了基于几何锚定的扩散序列和状态空间建模在实现鲁棒且可扩展的社区检测方面的有效性。源代码可公开获取于：https://github.com/BroAndyLee/DiMAE.git

引言

社区检测是分析复杂网络的核心工作，它支持诸如在引文网络中发现主题群体或在电子邮件和社交网络中识别组织单元等任务[1][2]。在这些系统中，观察到的图往往具有稀疏性和噪声，存在缺失或虚假的链接以及模糊的社区边界[3][4]。此外，在资源有限的图学习环境中，可靠的监督信息通常很少且获取成本高昂[5]。在这种情况下，简单的一跳聚类方法不够有效，而过于激进的多跳传播则可能通过过度平滑模糊社区特定的信号[6]。 大多数现有方法试图在利用高阶结构和保持社区边界之间找到平衡，但它们通常会陷入两个极端。基于矩阵的方法通过构建全局亲和力或相似性矩阵来表示图，其中多跳结构关系被编码为某种算子（例如，来自高阶邻近性[7]、随机游走统计[8]或扩散核），然后对其进行因子分解或谱分解以获得低维表示。虽然这种方法效率较高，但将多尺度结构压缩到固定的算子中使得在异构稀疏性条件下有效的扩散变得脆弱，从而在连接较弱的节点上导致传播不足，而在密集区域则导致边界模糊。 相比之下，基于结构和消息传递的方法沿着观察到的边传播信息，范围从简单的标签传播启发式方法到现代图神经网络（GNNs）[9]。尽管这种范式可以直接在图上纳入多跳依赖关系，但在稀疏和噪声较大的网络上进行深度传播时容易发生过平滑现象，即不同社区的表示随着深度的增加而逐渐趋同并变得难以区分[10][11]。此外，监督通常仅应用于最终的嵌入结果，因此对结构信号在传播深度上的演变控制有限，也无法清晰地了解哪些社区级别的模式得到了强化[12]。 这些局限性提出了在稀疏、噪声较大和监督信息有限的环境中进行社区检测的三个要求：首先，应以可控的方式揭示高阶结构，而不是将其压缩为单一的固定尺度算子或通过全局传播深度进行调整，尤其是在异构稀疏性和混合强度较大的情况下[13][14][15]；其次，在保持脆弱的社区边界的同时注入长距离信息，以减轻迭代扩散过程中观察到的平滑和信息损失[10][11]；第三，应利用有限的标签来调节结构本身，引导高阶相似性的演变和重建为可解释的社区模式，而不仅仅是作为终端节点级别的损失[16]。 在这项工作中，DiMAE（Diffusion–Mamba AutoEncoder）被提出作为一种以扩散深度为中心的半监督社区检测状态空间框架。DiMAE通过几何正则化的三角扩散过程构建多阶相似性矩阵序列，该过程将传播限制在保持锚点的凸包内，从而产生稳定的多尺度相似性表示。然后将扩散深度视为一维信号，并使用选择性的Mamba状态空间编码器进行建模，以线性时间学习数据驱动的深度级过滤器[17][18]。最后，多层非负解码器将低秩相似性模式重构为可加性的社区原型，即使只有5%的节点被标记，这些原型也能通过轻量级的逐点和成对正则化得到优化[19]。 我们的主要贡献总结如下： - 首次从扩散深度的角度对社区检测进行了建模，将多阶相似性矩阵在扩散步骤中视为按深度索引的序列，从而将高阶结构学习转化为在稀疏和监督信息有限环境下的序列建模问题。 - 引入了几何正则化的三角扩散方案，通过在保持锚点的凸几何结构内限制深度传播来生成稳定的多尺度相似性序列，从而减轻了在较大扩散深度下的过度平滑和结构漂移。 - 开发了一种以扩散深度为中心的状态空间框架，将选择性的Mamba编码器与多层非负解码器相结合，生成对扩散敏感的表示和可解释的可加性社区原型，并允许从有限的标签中进行直接正则化。 - 在合成基准网络和真实世界网络上的广泛实验表明，DiMAE在性能上显著优于基于矩阵的方法、消息传递方法和混合方法，尤其是在节点分布稀疏且社区高度混合的情况下。

本文的其余部分组织如下：第2节回顾相关工作；第3节介绍提出的DiMAE框架，包括几何正则化扩散、状态空间序列建模和半监督正则化；第4节报告在合成网络和真实世界网络上的实验结果和消融研究；第5节总结本文并讨论未来方向。

相关工作

在本节中，我们回顾了与本工作最相关的四个研究方向：(i) 社区检测范式和结构表示；(ii) 图扩散和高阶传播；(iii) 用于结构序列建模的状态空间模型；(iv) 半监督和可解释的社区检测。同时讨论了DiMAE与以往方法在这些方面的联系和差异。

模型介绍

基于上述观察，DiMAE旨在使用状态空间编码器来建模几何正则化的扩散序列，并将逐点和成对监督集成到非负解码架构中。整个框架如图1所示。

实验设置

本节描述了实验设置，包括数据集、基线方法和实现细节。除非另有说明，报告的结果是基于10次独立运行的平均值。为了保证可重复性，所有实验都使用固定的随机种子42进行10次重复实验，并报告平均结果。

贡献总结

本文提出了DiMAE，这是一种基于几何正则化的扩散-状态空间框架，用于半监督社区检测。与传统方法不同，DiMAE引入了三角几何约束来生成稳定的多尺度扩散序列，使用选择性的Mamba编码器以线性时间复杂度对其进行建模，并通过非负分解将其解码为可解释的社区原型。在七个合成网络和真实世界网络上的大量实验表明...

未引用的内容

算法1。

CRediT作者贡献声明

Ke Yuxian：撰写 – 审稿与编辑、撰写初稿、可视化、验证、监督、软件开发、方法论设计、数据整理、概念化。 Sun Yi：撰写 – 审稿与编辑、撰写初稿、验证、监督、项目管理、方法论设计、数据整理、概念化。 Li Qizhang：可视化、验证、软件开发。 Zhang Hongrui：验证、软件开发、资源管理、数据整理、概念化。 Zhang Qiyue：

利益冲突声明

作者声明他们没有已知的可能会影响本文所述工作的竞争性财务利益或个人关系。

致谢

本项工作得到了天山人才培训计划（2023TSYCQNTJ0013）的第二批资助。