arXiv:2502.06117cs.LGcs.AI2025-02中稿 · TheWebConf 2025被引 37

提升动态图聚类的效率与抗噪能力,适用于大规模实时图数据。

Revisiting Dynamic Graph Clustering via Matrix Factorization

  • 分时矩阵分解,将大矩阵拆解并行处理,加速计算。
  • 引入双聚类正则化,联合优化嵌入与聚类,过滤噪声特征。
  • 仅更新动态节点嵌入,静态节点保持固定,兼顾效率与效果。

动态图聚类旨在检测和追踪动态图中随时间变化的簇,揭示复杂现实系统演化机制。基于矩阵分解的方法在该任务中表现良好,但通常面临可扩展性差、计算耗时的问题,且对真实世界中的噪声数据敏感。为此,本文提出三项关键改进:首先,为提升可扩展性,提出时间分离矩阵分解,将单个大矩阵拆分为多个小矩阵分别独立分解,显著加快计算速度;其次,为增强鲁棒性,引入双聚类正则化,联合优化图嵌入与聚类,有效过滤嵌入中的噪声特征;第三,为进一步提升效率与有效性,提出选择性嵌入更新策略,仅更新随时间变化的节点嵌入,而静态节点嵌入在不同时间戳间保持不变。在六个合成数据集和五个真实世界基准上的实验结果表明,所提方法在可扩展性、鲁棒性和有效性方面均优于现有方法。源代码已开源:https://github.com/Clearloveyuan/DyG-MF。

原文摘要 · Abstract (English)

Dynamic graph clustering aims to detect and track time-varying clusters in dynamic graphs, revealing the evolutionary mechanisms of complex real-world dynamic systems. Matrix factorization-based methods are promising approaches for this task; however, these methods often struggle with scalability and can be time-consuming when applied to large-scale dynamic graphs. Moreover, they tend to lack robustness and are vulnerable to real-world noisy data. To address these issues, we make three key contributions. First, to improve scalability, we propose temporal separated matrix factorization, where a single matrix is divided into multiple smaller matrices for independent factorization, resulting in faster computation. Second, to improve robustness, we introduce bi-clustering regularization, which jointly optimizes graph embedding and clustering, thereby filtering out noisy features from the graph embeddings. Third, to further enhance effectiveness and efficiency, we propose selective embedding updating, where we update only the embeddings of dynamic nodes while the embeddings of static nodes are fixed among different timestamps. Experimental results on six synthetic and five real-world benchmarks demonstrate the scalability, robustness and effectiveness of our proposed method. Source code is available at https://github.com/Clearloveyuan/DyG-MF.

动态图聚类矩阵分解高效算法

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。