A Clique-Based Approach for Community Search in Heterogeneous Information Networks

Community search over heterogeneous information networks (HINs) aims to find a tightly connected subgraph containing a query node. Existing methods based on meta-paths or density metrics fail to guarantee structural completeness or support complex queries involving closed loops and multi-path interactions, i.e., all members interact according to a predefined high-order pattern. To address this, we introduce the concept of the motif clique(m-clique) as the community model. Unlike prior work that enumerates all maximal m‑cliques globally, we focus on query‑driven community search, efficiently finding a maximal m‑clique containing a given query node. We formalize the Structural Complete Community Search (SCCS) problem and propose the MCS algorithm, which employs a local expansion strategy starting from query nodes and enhances search efficiency through embedded indexing and dominance relation pruning. Extensive experiments on three real-world datasets demonstrate that this algorithm effectively supports the identification of communities with more complete structures and clearer semantics.