Beyond Locality: Multi-scale Structural Tokenization for Unsupervised Community Search

Abstract

Community Search (CS) aims to retrieve query-dependent cohesive subgraphs from networks, playing a crucial role in modern applications such as computing power networks and biological systems. Given the high cost of labeling, unsupervised CS has emerged as a scalable paradigm. However, existing approaches often suffer from restricted structural receptive fields and the limitation of static node representations, which fail to perceive the evolving community boundaries during expansion.To address these, this paper explores the potential of unsupervised CS by proposing the ComPass framework. We first design an incremental graph augmentation strategy to generate views with enriched community information. These views are then processed via a multi-scale structural tokenization mechanism, which transforms the graph into hierarchical sequences that bridge fine-grained topological associations with coarse-grained community contexts. By feeding these sequences into a Transformer-based encoder, ComPass effectively captures discriminative community representations without supervision. During online search, an iterative score refinement mechanism enables the co-evolution of community structure and node scoring, mitigating semantic drift.Extensive experiments illustrate the promising performance of ComPass as an exploratory step. Notably, ComPass achieves a competitive advantage over the strongest baseline, TransZero, with an average F1-score improvement of 15.23%. This exploration suggests that integrating incremental augmentation, multi-scale tokenization, and adaptive search offers a potentially effective direction for advancing unsupervised community search.