Efficient Maintenance of Leiden Communities in Large Dynamic Graphs

📄 arXiv: 2601.08554v1 📥 PDF

作者: Chunxu Lin, Yumao Xie, Yixiang Fang, Yongmin Hu, Yingqian Hu, Chen Cheng

分类: cs.SI, cs.DB, cs.GR

发布日期: 2026-01-13

💡 一句话要点

提出HIT-Leiden算法，高效维护大规模动态图中的Leiden社区结构。

🎯 匹配领域: 支柱九：具身大模型 (Embodied Foundation Models)

关键词: 动态图 社区检测 Leiden算法 增量维护 分层结构 连通分量 图算法

📋 核心要点

  1. 现有Leiden算法在动态图上重新计算社区结构成本高昂，已有增量维护方法缺乏理论分析且效率低。
  2. HIT-Leiden算法通过维护连通分量和分层社区结构，有效缩小受影响顶点范围，实现高效增量更新。
  3. 实验表明，HIT-Leiden在各种数据集上显著优于现有方法，速度提升高达五个数量级。

📝 摘要（中文）

Leiden算法作为一种著名的社区检测算法，已被广泛应用于各种场景，如大型语言模型生成（例如Graph-RAG）、异常检测和生物分析。在这些场景中，图通常是大型且动态的，顶点和边频繁插入和删除，因此当图发生变化时，从头开始通过Leiden算法获得更新的社区结构成本很高。最近，一项工作试图研究如何在动态图中维护Leiden社区，但缺乏详细的理论分析，并且其算法对于大型图来说效率低下。为了解决这些问题，在本文中，我们首先通过有界性分析（一种用于分析动态图上的增量算法的强大工具）在理论上表明现有算法是相对无界的，并且还分析了图变化时顶点在社区中的成员关系。基于理论分析，我们开发了一种新颖高效的维护算法，称为分层增量树Leiden（HIT-Leiden），它通过维护连通分量和分层社区结构来有效地减少受影响顶点的范围。在各种数据集上的综合实验证明了HIT-Leiden的卓越性能。特别是，与现有方法相比，它实现了高达五个数量级的加速。

🔬 方法详解

问题定义：论文旨在解决大规模动态图中Leiden社区结构维护效率低下的问题。现有方法在图发生变化时，通常需要从头开始重新运行Leiden算法，计算成本很高。已有的增量维护方法缺乏充分的理论分析，在大规模图上的性能不佳，无法满足实际应用的需求。

核心思路：论文的核心思路是利用图的连通性以及Leiden算法的分层特性，尽可能缩小每次图更新后需要重新计算的顶点范围。通过维护连通分量和分层社区结构，HIT-Leiden能够快速定位受影响的区域，并仅对这些区域进行局部更新，从而避免全局重新计算。

技术框架：HIT-Leiden算法主要包含以下几个阶段：1) 图更新：接收顶点或边的插入/删除操作。2) 影响范围确定：基于连通分量和分层社区结构，确定受影响的顶点集合。3) 局部社区结构更新：仅对受影响的顶点集合及其邻居执行Leiden算法的局部迭代，更新社区结构。4) 结构维护：更新连通分量和分层社区结构，为下一次更新做准备。

关键创新：HIT-Leiden的关键创新在于其分层增量更新策略。与现有方法相比，HIT-Leiden不是简单地对整个图进行增量更新，而是充分利用了Leiden算法的分层特性，将更新限制在受影响的局部区域内。此外，通过维护连通分量信息，可以更精确地确定受影响的顶点集合，进一步减少了计算量。

关键设计：HIT-Leiden算法的关键设计包括：1) 连通分量维护：使用高效的并查集数据结构来维护图的连通分量信息，以便快速确定顶点之间的连通性。2) 分层社区结构维护：在每次局部更新后，需要更新分层社区结构，以保证其与当前的图结构保持一致。3) 局部Leiden迭代：在局部更新过程中，需要设置合适的迭代次数，以保证社区结构的质量和更新效率。

📊 实验亮点

实验结果表明，HIT-Leiden算法在各种数据集上都显著优于现有的Leiden社区维护算法。与现有方法相比，HIT-Leiden实现了高达五个数量级的加速，尤其是在大规模动态图上，性能优势更加明显。这表明HIT-Leiden能够有效地应对实际应用中大规模动态图的挑战。

🎯 应用场景

HIT-Leiden算法可广泛应用于需要动态社区检测的场景，例如社交网络分析、推荐系统、金融风控、网络安全和生物信息学等。在这些领域，图结构通常会随着时间推移而发生变化，高效的社区结构维护能力可以帮助我们及时发现新的社区、识别异常行为、优化推荐策略等，具有重要的实际价值。

📄 摘要（原文）

As a well-known community detection algorithm, Leiden has been widely used in various scenarios such as large language model generation (e.g., Graph-RAG), anomaly detection, and biological analysis. In these scenarios, the graphs are often large and dynamic, where vertices and edges are inserted and deleted frequently, so it is costly to obtain the updated communities by Leiden from scratch when the graph has changed. Recently, one work has attempted to study how to maintain Leiden communities in the dynamic graph, but it lacks a detailed theoretical analysis, and its algorithms are inefficient for large graphs. To address these issues, in this paper, we first theoretically show that the existing algorithms are relatively unbounded via the boundedness analysis (a powerful tool for analyzing incremental algorithms on dynamic graphs), and also analyze the memberships of vertices in communities when the graph changes. Based on theoretical analysis, we develop a novel efficient maintenance algorithm, called Hierarchical Incremental Tree Leiden (HIT-Leiden), which effectively reduces the range of affected vertices by maintaining the connected components and hierarchical community structures. Comprehensive experiments in various datasets demonstrate the superior performance of HIT-Leiden. In particular, it achieves speedups of up to five orders of magnitude over existing methods.