Efficient Meta-Path Constrained Reachability Query on Heterogeneous Information Networks

Heterogeneous information networks (HINs) are prevalent in real-world applications, capturing complex semantic relationships through multiple types of entities and links. Metapath constrained reachability (MCR) queries, which ask whether two vertices are connected via a simple path under given metapath pattern, are fundamental to HIN analysis. However, existing methods are inadequate, they either fail to represent complex meta-path constrains or cannot efficiently answer MCR queries on large-scale HINs. To address these limitations, we present a novel hybrid indexing framework, MCR-Index, that integrates partial tree decomposition with anchor-based indexing and a compact meta-path Aho-Corasick automaton for meta-path representation. Based on MCR-Index, we develop an efficient query processing algorithm and a scalable index construction method. Extensive experiments on diverse real-world HINs demonstrate that our MCR-Index significantly outperforms existing solutions in query efficiency, index size, and construction time, enabling practical and scalable meta-path reachability query processing for large-scale HINs.