Effective and Efficient Conductance-Based Community Search at Billion Scale
Longlong Lin, Yue He, Chen We, Pingpeng Yuan, Rong-Hua Li, Tao Jia · IEEE Transactions on Big Data · 2025
Community search is a widely studied semi-supervised graph clustering problem, retrieving a high-quality connected subgraph containing the user-specified query vertex. However, existing methods primarily focus on cohesiveness within the community but ignore the sparsity outside the community, obtaining sub-par results. Inspired by this, we adopt the well-knownconductancemetric to measure the quality of a community and introduce a novel problem ofconductance-based community search (CCS).CCSaims at finding a subgraph with the smallestconductanceamong all connected subgraphs that contain the query vertex. We prove that theCCSproblem is NP-hard. To efficiently queryCCS, a four-stagesubgraph-conductance-based community search algorithm,SCCS, is proposed. Specifically, we first greatly reduce the entire graph using local sampling techniques. Then, a three-stage local optimization strategy is employed to continuously refine the community quality. Namely, we first utilize a seeding strategy to obtain an initial community to enhance its internal cohesiveness. Then, we iteratively add qualified vertices in the expansion stage to guarantee the internal cohesiveness and external sparsity of the community. Finally, we gradually remove unqualified vertices during the verification stage. Extensive experiments on real-world datasets containing one billion-scale graph and synthetic datasets show the effectiveness, efficiency, and scalability of our solutions.