MOCHI: Motif-Based Community Search Over Large Heterogeneous Information Networks

In this paper, we investigate the problem of motif-based community search over heterogeneous information networks (MOCHI). We introduce a novel motif density modularity (MDM) to measure the motif cohesiveness of communities. Based on MDM, we define the MOCHI problem as follows: given a heterogeneous information network (HIN) H, a motif M, and a query vertex set Q, the objective is to identify the subgraph of H connected by motif instances, containing Q, and maximizing MDM. Since motifs encapsulate rich semantics, the MOCHI problem enables the retrieval of semantically meaningful communities, facilitating applications like fraud detection and academic collaboration analysis. Due to the NP-hardness of MOCHI, we propose three algorithms. The basic algorithm iteratively removes vertices to maximize MDM. However, vertex selection and maintaining M-connectivity incur significant overhead. Hence, we devise an MW-HIN-based algorithm that employs a vertex selection strategy and a compact data structure motif-based weighted HIN to boost efficiency. Additionally, we propose a motif-distance-based algorithm to further improve performance by integrating motif distance and a lightweight goodness function M-ratio to remove vertices. Extensive experiments on real-world HINs demonstrate the effectiveness and efficiency of our proposed methods.