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.
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.· Proceedings of the 35th ACM...· 0 citations
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
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...
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.· Proceedings of the ACM on Ma...· 0 citations
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.· arXiv.org· 0 citations
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...