LUCID: LLM-Guided Unsupervised Community Detection for Graphs

Community detection, the task of identifying cohesive groups within complex graph structures, is fundamental to graph analytics. Traditional objective-driven methods often struggle with intricate graph patterns, while deep learning approaches, though powerful, typically sacrifice interpretability and require labeled data for training. This research introduces LUCID (LLM-guided, Unsupervised Community Detection), a novel method that harnesses the reasoning capabilities and world knowledge of large language models (LLMs) to provide an interpretable and label-free solution. LUCID operates through a four-stage pipeline, drawing inspiration from natural phase-transition kinetics: initialization, merging, refinement, and selection. Within each stage, the LLM is used to generate formal, explicit, and interpretable logical rules. Specifically, it initializes local communities based on k-ego contexts, iteratively merges them using LLM-induced rules, refines boundaries with coarse-to-fine rules, and finally selects high-quality communities based on topological compactness and clarity. Extensive experiments on real-world datasets demonstrate that LUCID achieves state-of-the-art performance, outperforming both unsupervised and semi-supervised baselines.