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

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.