Skip to content
Open access

To Learn or Not to Learn? An In-depth Empirical Analysis of Community Search Approaches

Sep 2026 · Proceedings of the ACM on Management of Data · Vol 4, pp. 1-27 · 0 citations · 47 references

TL;DR

This paper systematically evaluates the overall performance of representative CS approaches, investigates the impact of intrinsic properties of ground-truth communities, and analyzes the approaches' generalizability within a unified experimental framework to advocate generalizability as a pivotal direction for future research.

Abstract

Community search (CS) is a fundamental problem in graph analysis, which aims to identify a query-dependent cohesive subgraph that satisfies a specific community model and contains the given query vertices. While numerous CS approaches have been proposed, including non-learning-based and learning-based ones, existing research lacks a unified experimental evaluation that bridges these two paradigms. Consequently, the relative strengths and weaknesses of these approaches remain insufficiently understood. Moreover, practitioners lack an effective method to recommend appropriate CS approaches for diverse queries. To address these limitations, this paper conducts a comprehensive and in-depth empirical analysis of representative CS approaches across various real-world datasets. We systematically evaluate their overall performance, investigate the impact of intrinsic properties of ground-truth communities, and analyze the approaches' generalizability within a unified experimental framework. The results show that existing CS approaches exhibit limited generalizability across varying queries, implying that no single approach performs optimally in all cases and that the best-performing approach depends on the specific query. Building upon these insights, we propose RecCS, a query-aware recommendation model that selects the top-performing CS approaches. Extensive experiments demonstrate that RecCS improves CS performance efficiently and effectively. Finally, we summarize the limitations of current CS approaches and advocate generalizability as a pivotal direction for future research.

Read PDF

Similar papers

Book Open access Nov 2026

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

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 f...

Xi Yue, Chuan-Hou Sun, Ying Yin et al. · 0 citations
#machine learning Preprint Oct 2026

No-Free-Graph: Learning When Multimodal Data Should Be Graphified

Multimodal graph learning has recently emerged as an effective paradigm for in corporating inter-entity relationships into multimodal representations. Existing studies have made substantial progress on how to construct and optimize graphs, but rarely consider a more fundamental question: whether additional relational s...

Ze-Kai Chen, Kai Hu, Yu-Xin Zeng et al. · 0 citations
Sep 2026

WCCS: Efficient Wedge Conductance Community Search over Large Temporal Bipartite Graphs (Full Paper)

An online priority-driven filter-and-expand framework with several effective pruning techniques and a powerful geometric slope optimization for rapid temporal wedge conductance calculation is developed and a novel temporal wedge conductance metric is proposed that explicitly balances internal density and external spars...

Long-Long Lin, Wei Chen, Ping-Peng Yuan et al. · 0 citations
Open access Sep 2026

Budgeted Interactive Property Graph Repair with GNN

This work introduces a Graph Neural Network (GNN)-based difficulty estimator that jointly captures topological and semantic aspects of violations, enabling the system to distinguish between cases suitable for automatic repair and those requiring human input.

Amedeo Pachera, Angela Bonifati, L. Lakshmanan et al. · 0 citations
Sep 2026

Improved Methods for k-core Community Search

Community search based on user-specified query nodes is complementary to community finding or graph clustering. Prior work in community search is divided into optimizing for external separate- ness or internal cohesiveness, which does not scale well networks of over a billion edges. We present SteinerKCore, a new scala...

Ian Chen, Hao-Tian Yi, Arun Sharma et al. · 0 citations

Better Nearest Neighbor Graph Indices via (Efficient) LLM-Guided Pruning

LLM-Guided Graph Pruning (LGP), a general framework that addresses this mismatch directly by leveraging LLM reasoning to refine an existing ANN graph index itself, and consistently improves end-to-end retrieval performance over both vanilla greedy graph search and LLM-based reranking across widely used graph-based ANN...

Fangzhou Wu, Hai-Ke Xu, Sandeep Silwal · 0 citations

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.