Effective and Efficient Conductance-based Community Search at Billion Scale
Longlong Lin, Yue He, Wei Chen, Pingpeng Yuan, Rong-Hua Li, Tao Jia · 2025
Read Effective and Efficient Conductance-based Community Search at Billion Scale by Longlong Lin, Yue He, Wei Chen, Pingpeng Yuan, Rong-Hua Li, Tao Jia (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2508-01244.txt.
Introduction
Longlong Lin and co-authors hunt for tight-knit groups in billion-edge graphs in a 2025 paper. Community search starts from one named node and wants the best connected group around it. Older methods judged a group only by its inner density, ignoring how much it leaks to the outside; the conductance score counts both, and the authors define the search around minimizing it.
They prove that exact search is NP-hard, then build a four-stage algorithm that samples the graph down, seeds a first group, grows it with worthy nodes, and prunes the unworthy. Tests on real graphs, one at billion scale, plus synthetic ones showed the routine stays fast and finds better groups than rivals. The work brings a stricter quality bar to a classic task.
Catalog record
| CREATOR | Longlong Lin, Yue He, Wei Chen, Pingpeng Yuan, Rong-Hua Li, Tao Jia |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 72 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2508-01244
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Effective and Efficient Conductance-based Community Search at Billion Scale Longlong Lin, Yue He, Wei Chen, Pingpeng Yuan, Rong-Hua Li, Tao Jia Abstract 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-known conductance metric to measure the quality of a community and introduce a novel problem of conductance -based community search ( CCS ). CCS aims at finding a subgraph with the smallest conductance among all connected subgraphs that contain the query vertex. We prove that the CCS problem is NP-hard. To efficiently query CCS , a four-stage subgraph-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. I Introduction Community search, identifying a high-quality connected subgraph (known as community) containing the given query vertex, is one of the fundamental tasks in network science [ 1 , 2 , 3 , 4 , 5 ] . The problem also witnesses many practical applications, including social recommendation [ 2 ] , protein complexes identification [ 3 ] , and impromptu activities organization [ 5 ] . Therefore, many community search models have been proposed in the literature, notable examples include k -core based [ 2 , 3 , 6 ] and k -truss based [ 7 , 8 ] . Fig. 1: Motivation example. q=Erin is the query vertex. S_{1} is the answer returned based on k -core [ 3 ] and k -truss [ 7 ] . S_{2} is our answer. Despite their success, most existing state-of-the-art (SOTA) methods are based on cohesive subgraph models, which only focus on the internal cohesiveness of the output community [ 9 ] . Taking Figure 1 as an example, the query vertex Erin plans to organize a seminar, S_{1}=\{Erin,Evan,Jack,Bella,Lily,Nelly,Alice,Henry,Daisy\} is the 3 -core community containing Erin (i.e., each vertex has at least 3 neighbors in the community. Note that 4-core containing Erin does not exist in Figure 1 ). Similarly, S_{1} is also the 4 -truss community containing Erin (i.e., each edge has at least 4-2 triangles in the community. Note that 5-truss containing Erin does not exist in Figure 1 ). However, according to [ 10 , 11 ] , we can know that a community is high-quality if the community is densely connected internally and well separated from the remainder of the graph. Thus, cohesive subgraph-based community search models significantly overlook the unique external separability of communities, potentially obtaining poor results, as stated in our experiments. For example, S_{1} has greater external connections (20 edges) than internal connections (18 edges), indicating that S_{1} is not ideally separated from the rest of the network [ 10 , 11 ] . On top of that, the qualities of communities returned by k -core or k -truss are seriously compromised by the input parameter k . For example, to obtain smaller communities that better align the size (usually between 3 to 100 in Table V ) of the ground truths, they tend to maximize k . However, since the low core/truss numbers of most vertices in real-world networks [ 12 ] , the maximum k is still naturally small. As a result, the resultant community (returned by k -core or k -truss) sizes remain significantly larger than those of real communities (Table VI ), failing to meet the properties of real-world networks [ 13 , 14 ] . Last but not least, existing solutions incur substantial computational costs for handling massive graphs with billions of edges. For example, on a Friendster with 1.8 billion edges, CSM , TCP and HK-Relax cannot obtain results within five hours in our experiments (Table IV ), which is obviously impractical for graph exploration. Summing up, it is meaningful and challenging to improve the efficiency and quality of existing community search methods. Intuitively, S_{2}=\{Erin,Evan,Jack,Bella,Lily,Nelly\} may be an ideal community in Figure 1 . This is because S_{2} has 12 dense internal edges and only has 3 sparse external edges. Inspired by this, in this paper, we use the representative and free-parameter metric conductance [ 1 , 15 , 4 ] to measure the quality of a community. Given an undirected graph G and a vertex set C , the conductance of C is defined as \phi(C)=\frac{|E(C,\bar{C})|}{\min\{vol(C),2m-vol(C)\}} , in which |E(C,\bar{C})| is the number of edges with one endpoint in C and another not in C , vol(C) is the sum of the degree of all vertices in C , and m is the number of the edges in G . Thus, a smaller \phi(C) implies that the number of edges going out of C is relatively small compared with the number of edges within C . As a consequence, the smaller the \phi(C) , the better the quality of the community C [ 10 , 11 ] , which reflects the cohesion inside the community and the sparseness outside. For example, \phi(S_{2})=0.111<\phi(S_{1})=0.833 indicates that S_{2} is more suitable for Erin to organize a seminar. As stated in Sections III and VI , the diffusion-based local clustering is most relevant to ours, which aims to identify a small conductance community near the given query vertex [ 16 ] . Although the local clustering can obtain theoretically good graph cuts, it is not desirable in community search. For example, the community returned by the local clustering may not be connected [ 17 ] or contain no the given query vertex [ 18 ] , which contradicts the definition of community search [ 9 ] . To address the dilemma, we introduce a novel conductance -based community search (named as CCS ), which aims at finding a subgraph with the smallest conductance among all connected subgraphs containing the given query vertex. Our solutions. Addressing the CCS problem raises significant challenges due to its NP-hardness (Theorem 1 ), thus we resort to the heuristic solutions. One possible simple solution is to adjust the existing local clustering framework and propose an efficient heuristic algorithm PPRCS to solve our CCS . Specifically, PPRCS first is to compute the Personalized PageRank vector seeding by the query vertex q . Then, PPRCS executes a modified sweep cut over the vector, ensuring the resultant community is connected and contains q . However, the community quality of such naive solution PPRCS is heavily dependent on many hard-to-tune parameters, resulting in that its performance is unstable and in most cases very poor [ 17 , 19 ] . To overcome these limitations, we propose an efficient and effective four-stage subgraph-condutance -based algorithm SCCS . Specifically, in the first stage,