用大模型生成可解释规则,无监督地发现图中社区结构。
Interpretable Unsupervised Community Detection with LLM-Symbolized Structured Processes

- 通过四阶段流程,让大模型生成可读规则来构建社区。
- 在真实数据集上超越现有无监督方法,性能达领先水平。
- 适合需要透明决策过程的图分析场景,如社交网络、生物网络。
社区检测是图分析中的基础任务,旨在识别行为或兴趣相似的实体群体。传统目标驱动方法难以处理复杂图结构,深度学习方法虽提升性能却牺牲可解释性且依赖标注数据与训练过程。大型语言模型(LLMs)具备强大的推理能力和世界知识,为可解释、无需标签的社区检测提供了新思路。为此,我们提出LUCID:一种由大模型引导、可解释、无需训练、无监督的社区检测方法。受自然系统相变动力学启发,该方法设计为四阶段流程:(1)局部视图初始化阶段,利用k-ego上下文和无监督节点角色编码局部图结构;(2)多因素合并阶段,基于大模型生成的规则迭代合并局部社区;(3)多粒度精炼阶段,并行应用大模型生成的粗到细规则以减少边界噪声;(4)全局视图选择阶段,依据拓扑紧凑性和边界清晰度筛选高质量社区。在多个真实数据集上的实验表明,作为无监督方法,LUCID达到当前最优性能,持续优于领先的无监督及半监督基线方法。
原文摘要 · Abstract (English)
Community detection is a fundamental task in graph analytics that aims to identify cohesive groups of entities with similar behaviors or interests. Classic objective-driven methods struggle with complex graph structures, while deep-learning approaches improve performance at the expense of interpretability and rely on labeled data and training. Large language models (LLMs), with strong reasoning capabilities and world knowledge, are promising for interpretable, label-free community detection. To leverage these strengths, we propose LUCID, an LLM-guided, interpretable, training-free, and unsupervised community detection method. Inspired by phase-transition kinetics in natural systems, where complex structures emerge through initialization, merging, refinement, and selection, LUCID is designed as a four-stage pipeline. Within this pipeline, the LLM induces formal rules that translate implicit knowledge into explicit and interpretable logical structures. Specifically, (1) the Local-View Community Initialization stage encodes local graph structures using k-ego contexts and unsupervised node roles; (2) the Multi-factor Community Merge stage uses LLM-induced rules to iteratively merge local communities; (3) the Multi-grain Community Refinement stage applies LLM-induced coarse-to-fine rules in parallel to reduce boundary noise; and (4) the Global-view Community Selection stage identifies high-quality communities based on topological compactness and boundary clarity. Extensive experiments on real-world datasets demonstrate that LUCID, as an unsupervised approach, achieves state-of-the-art performance and consistently outperforms leading unsupervised and semi-supervised baselines.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。