CommunityDF: A Guided Denoising Diffusion Approach for Community Search

Denoising Diffusion Probabilistic Models (DDPMs) have recently demonstrated exceptional performance in generating high-quality data. In this work, we propose CommunityDF, a novel framework that applies DDPMs to the community search problem, which involves identifying subgraphs containing nodes closely related to a given query node. However, three key challenges arise in this context: (I) learning effective node representations from limited examples, (II) discretizing continuous node representations into community members, and (III) reducing the number of diffusion steps without sacrificing performance. To tackle these, CommunityDF introduces several innovations. First, we focus on subgraphs around the query node to reduce interference from unrelated nodes, improve scalability. We then employ a contrastive learning approach, treating node states at different diffusion steps as positive examples and designing various negative sampling strategies to learn high-quality node representations from limited examples. Second, we propose a dynamic thresholding mechanism that effectively converts continuous representations into community members. Finally, we reduce the number of diffusion steps by leveraging the rough communities to initialize the process with rough community structures, which accelerates convergence while maintaining high accuracy. Extensive experiments on seven real-world datasets demonstrate that CommunityDF outperforms existing methods by 16%-47%, establishing it as a state-of-the-art solution for community search. The source code is available at https://github.com/JiazunChen/CommunityDF.