Prompt-Guided Community Search Under Extreme Few-Shot Supervision

Community search, which aims to identify cohesive subgraphs containing given query nodes, is a fundamental task in graph analysis. Existing learning-based methods depend heavily on abundant labeled communities, making them ineffective in realistic settings where labels are extreme scarce. Although several methods have been proposed to mitigate label scarcity, they still fail to perform robustly across both sparsely and densely labeled datasets due to three key limitations: (i) a query-nodecentric design that always treats the query node as the community center, causing errors when the query lies near the community boundary; (ii) lack of connectivity guarantee, as similarity-based expansions may yield disconnected results; and (iii) dependence on labeled data, where unsupervised models lack supervision while semi-supervised ones easily overfit when labels are rare. To address these issues, we propose Prompt-Guided Community Search (PGCS), a novel “pre-train, prompt, and search” framework. We design novel pretraining tasks that capture structural characteristics such as density and cohesiveness. We introduce a prompt function that measures the goodness of subgraph expansion, effectively bridging pretrained knowledge with community search. To overcome label scarcity, we propose a dual-prompt mix-training strategy, which utilize both ground truth communities and soft labels generated from unlabeled nodes. Finally, we develop an online search algorithm that expands from the query node into a coherent and connected community. Extensive experiments on nine real-world datasets show that PGCS consistently outperforms traditional and recent learning-based baselines in both accuracy and efficiency. On average, our proposed method outperforms SOTAs by up to 35.16% across all datasets.