用大语言模型符号化结构过程实现可解释的无监督社区发现

社区发现是图分析中的一项基础任务，旨在识别具有相似行为或兴趣的内聚实体群体。经典的目标驱动方法难以应对复杂图结构，而深度学习方法以牺牲可解释性为代价提升了性能，并依赖标注数据与训练。大语言模型（LLM）凭借强大的推理能力和世界知识，有望实现可解释、无标注的社区发现。为利用这些优势，我们提出LUCID，一种由LLM引导的、可解释的、免训练的无监督社区发现方法。受自然界中复杂结构经由初始化、合并、细化与选择而涌现的相变动力学启发，LUCID被设计为四阶段流水线。在该流水线中，LLM归纳形式化规则，将隐式知识转化为显式且可解释的逻辑结构。具体而言：(1) 局部视角社区初始化阶段用k-ego上下文和无监督节点角色编码局部图结构；(2) 多因素社区合并阶段使用LLM归纳的规则迭代合并局部社区；(3) 多粒度社区细化阶段并行应用LLM归纳的由粗到细规则以减少边界噪声；(4) 全局视角社区选择阶段基于拓扑紧凑性与边界清晰度识别高质量社区。在真实数据集上的大量实验表明，作为无监督方法的LUCID取得了最先进的性能，并持续超越领先的无监督与半监督基线。