Interpretable Unsupervised Community Detection with LLM-Symbolized Structured Processes

Researchers propose LUCID, an LLM-guided, interpretable, training-free, and unsupervised community detection method that achieves state-of-the-art performance on real-world datasets, outperforming leading unsupervised and semi-supervised baselines. The method uses a four-stage pipeline inspired by phase-transition kinetics, where the LLM induces formal rules to translate implicit knowledge into explicit logical structures.

arXiv:2608.06402v1 Announce Type: new Abstract: 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.