Effective and Efficient Discovery of Top-k Meta Paths in Heterogeneous Information Networks

<italic>Heterogeneous information networks (HINs)</italic>, which are typed graphs with labeled nodes and edges, have attracted tremendous interest from academia and industry. Given two HIN nodes <inline-formula><tex-math notation="LaTeX">$s$</tex-math><alternatives><mml:math><mml:mi>s</mml:mi></mml:math><inline-graphic xlink:href="zhu-ieq1-3037218.gif"/></alternatives></inline-formula> and <inline-formula><tex-math notation="LaTeX">$t$</tex-math><alternatives><mml:math><mml:mi>t</mml:mi></mml:math><inline-graphic xlink:href="zhu-ieq2-3037218.gif"/></alternatives></inline-formula>, and a natural number <inline-formula><tex-math notation="LaTeX">$k$</tex-math><alternatives><mml:math><mml:mi>k</mml:mi></mml:math><inline-graphic xlink:href="zhu-ieq3-3037218.gif"/></alternatives></inline-formula>, we study the discovery of the <inline-formula><tex-math notation="LaTeX">$k$</tex-math><alternatives><mml:math><mml:mi>k</mml:mi></mml:math><inline-graphic xlink:href="zhu-ieq4-3037218.gif"/></alternatives></inline-formula> most important meta paths in real time, which can be used to support friend search, product recommendation, anomaly detection, and graph clustering. In this work, we argue that the shortest path between <inline-formula><tex-math notation="LaTeX">$s$</tex-math><alternatives><mml:math><mml:mi>s</mml:mi></mml:math><inline-graphic xlink:href="zhu-ieq5-3037218.gif"/></alternatives></inline-formula> and <inline-formula><tex-math notation="LaTeX">$t$</tex-math><alternatives><mml:math><mml:mi>t</mml:mi></mml:math><inline-graphic xlink:href="zhu-ieq6-3037218.gif"/></alternatives></inline-formula> may not necessarily be the most important path. As such, we combine several ranking functions, which are based on <italic>frequency</italic> and <italic>rarity</italic>, to redefine the unified importance function of the meta paths between <inline-formula><tex-math notation="LaTeX">$s$</tex-math><alternatives><mml:math><mml:mi>s</mml:mi></mml:math><inline-graphic xlink:href="zhu-ieq7-3037218.gif"/></alternatives></inline-formula> and <inline-formula><tex-math notation="LaTeX">$t$</tex-math><alternatives><mml:math><mml:mi>t</mml:mi></mml:math><inline-graphic xlink:href="zhu-ieq8-3037218.gif"/></alternatives></inline-formula>. Although this importance function can capture more information, it is very time-consuming to find top-<inline-formula><tex-math notation="LaTeX">$k$</tex-math><alternatives><mml:math><mml:mi>k</mml:mi></mml:math><inline-graphic xlink:href="zhu-ieq9-3037218.gif"/></alternatives></inline-formula> meta paths using this importance function. Therefore, we integrate this importance function into a multi-step framework, which can efficiently filter some impossible meta paths between <inline-formula><tex-math notation="LaTeX">$s$</tex-math><alternatives><mml:math><mml:mi>s</mml:mi></mml:math><inline-graphic xlink:href="zhu-ieq10-3037218.gif"/></alternatives></inline-formula> and <inline-formula><tex-math notation="LaTeX">$t$</tex-math><alternatives><mml:math><mml:mi>t</mml:mi></mml:math><inline-graphic xlink:href="zhu-ieq11-3037218.gif"/></alternatives></inline-formula>. In addition, we combine bidirectional searching algorithm with this framework to further boost the efficiency performance. The experiment on different datasets shows that our proposed method outperforms state-of-the-art algorithms in terms of effectiveness with reasonable response time.