扩展经典聚类算法，支持复杂图与超图的高效局部聚类。
Local Clustering on Complex Graphs and Complex Hypergraphs
- 基于PageRank改进算法，适配加权、有向、自环图及带顶点权重的超图。
- 在两个温和条件下，保证聚类结果的导通率接近二次最优。
- 适用于社交网络、知识图谱等复杂结构数据的局部聚类任务。
局部聚类旨在从给定种子节点附近发现紧凑簇。现有研究多基于离散图（无权、无向、无自环），但现实世界图更复杂。本文将经典非近似化Andersen-Chung-Lang（ACL）聚类算法拓展至复杂图与超图，包括加权、有向、自环图及边依赖顶点权重的超图。通过引入PageRank，提出Graph版GeneralACL与Hypergraph版HyperACL。我们证明，在两个温和条件下，两算法均能实现导通率意义上的二次最优聚类。实验验证了理论结论。代码已开源：https://github.com/iDEA-iSAIL-Lab-UIUC/HyperACL。
原文摘要 · Abstract (English)
Local/seeded clustering aims to find a compact cluster near the given starting instances. While most existing studies on graph clustering assume a discrete graph setting (i.e., unweighted, undirected graphs without self-loops), real-world graphs can be more complex. In this paper, we extend the classic non-approximating Andersen-Chung-Lang (ACL) clustering algorithm beyond discrete graphs and generalize its quadratic optimality to a wider range of complex graphs, including weighted, directed, and self-looped graphs and hypergraphs with edge-dependent vertex weights. Specifically, by leveraging PageRank, we propose two algorithms: GeneralACL for graphs and HyperACL for hypergraphs. We prove that, under two mild conditions, both algorithms can identify a quadratically optimal cluster in terms of conductance. Additionally, we provide experiments to validate our theoretical findings. Our code is available at https://github.com/iDEA-iSAIL-Lab-UIUC/HyperACL.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。