A Comprehensive Survey and Experimental Study of Learning-based Community Search

Download PDF

Abstract

Given a graph G and a query node q , the goal of community search (CS) is to find a structurally cohesive subgraph from G that contains q. Significant progress has been made in community search using deep learning in recent years. To the best of our knowledge, no existing work has provided a comprehensive review of learning-based community search methods. Additionally, we find that: (1) Existing methods offer diverse definitions or descriptions of communities, which require systematic summarization. (2) The methods rely on distinct metrics for limited community assessment. (3) Overhead evaluations of the methods vary and exhibit certain biases. Therefore, a comprehensive survey and experimental study are essential to achieve four key objectives: designing a unified pipeline, clarifying community definitions, enriching community evaluation, and establishing overhead assessment. In this paper, we first propose a unified pipeline for these methods, highlighting techniques. We categorize community definitions and analyze the relationships between identified communities. Beyond that, we proposed several community metrics to evaluate the communities comprehensively. Moreover, we introduce a more detailed overhead evaluation approach that considers resource consumption during both the training and search phases. Finally, we employ the proposed community evaluation metrics and overhead assessment framework to evaluate and analyze the methods, examine correlations among metrics, and explore the effects of several commonly used techniques.