Effective and efficient discovery of top-k meta path in heterogeneous information networks

Abstract

\textit{Heterogeneous information networks (HINs)}, which are typed graphs with labeled nodes and edges, have attracted tremendous interest from academia and industry. Given two HIN nodes $s$ and $t$, and a natural number $k$, we study the discovery of the $k$ most important paths in real time. The returned paths can be used to support friend search, product recommendation, anomaly detection, and graph clustering. Although related algorithms have been proposed before, they were primarily designed to return the $k$ shortest paths from unlabeled graphs. This leads to two problems: (1) there are often many shortest paths between $s$ and $t$, and so it is not easy to choose the $k$ best ones; and (2) it is arguable whether a shorter path implies a more crucial one. To address these issues, we study the {\it top-$k$ meta path query} for an HIN. A meta path is essentially a sequence of node and edge types between $s$ and $t$ (e.g., {\it Author}$\xrightarrow{write}${\it Paper}$\xrightarrow{written-by}${\it Author} denotes the coauthor relationship of $s$ and $t$). A meta path abstracts multiple path instances into a high-level path pattern, thereby giving more insight between two nodes. We further study several ranking functions that evaluate the \textit{importance} of meta paths based on \textit{frequency} and \textit{rarity}, rather than on path length. Also, we propose a solution that seamlessly integrates these functions into a multi-step searching framework. In addition, we combine bidirectional searching algorithm with this framework to further boost up the efficiency performance. The experiment on different datasets shows that the proposed method outperforms state-of-the-art algorithms in terms of effectiveness with reasonable response time.