Community Search: A Meta-Learning Approach

Community Search (CS) is one of the fundamental graph analysis tasks, which is a building block of various real applications. Given any query nodes, CS aims to find cohesive subgraphs that query nodes belong to. Recently, a large number of CS algorithms are designed. These algorithms adopt predefined subgraph patterns to model the communities, which cannot find ground-truth communities that do not have such pre-defined patterns in real-world graphs. Thereby, machine learning (ML) and deep learning (DL) based approaches are proposed to capture flexible community structures by learning from ground-truth communities in a data-driven fashion. These approaches rely on sufficient training data to provide enough generalization for ML models, however, the ground-truth cannot be comprehensively collected beforehand.

In this paper, we study ML/DL-based approaches for CS, under the circumstance of small training data. Instead of directly fitting the small data, we extract prior knowledge which is shared across multiple CS tasks via learning a meta model. Each CS task is a graph with several queries that possess corresponding partial ground-truth. The meta model can be swiftly adapted to a task to be predicted by feeding a few task-specific training data. We find that trivially applying multiple classical metalearning algorithms to CS suffers from problems regarding prediction effectiveness, generalization capability and efficiency. To address such problems, we propose a novel meta-learning based framework, Conditional Graph Neural Process (CGNP), to fulfill the prior extraction and adaptation procedure. A meta CGNP model is a task-common node embedding function for clustering, learned by metric-based graph learning, which fully exploits the characteristics of CS. We compare CGNP with CS algorithms and ML baselines on real graphs with ground-truth communities. Our experiments verify that CGNP outperforms the other native graph algorithms and ML/DL baselines 0.33 and 0.26 on F1 score by average. The source code has been made available at https://github.com/FangShuheng/CGNP.

Community is a cohesive subgraph that is densely intraconnected and loosely inter-connected in a graph. Given any query nodes, community search (CS) aims at finding communities covering the query nodes, i.e., local query-dependent communities, which has a wide range of real applications, e.g., friend recommendation, advertisement in e-commence and protein complex identification [1], [2]. In the literature, to model structural cohesiveness, various community models are adopted, including k-core [3]-[5], k-truss [6], [7], kclique [8], [9] and k-edge connected component [10], [11].

Such models can be computed efficiently by CS algorithms. But such models are designed based on some pre-defined