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

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 s and t t , and a natural number k k , we study the discovery of the k k most important meta paths in real time, whi...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on knowledge and data engineering 2022-09, Vol.34 (9), p.4172-4185
Main Authors: Zhu, Zichen, Chan, Tsz Nam, Cheng, Reynold, Do, Loc, Huang, Zhipeng, Zhang, Haoci
Format: Article
Language:English
Subjects:
Anomalies
Anomaly detection
Clustering
Computer science
Directed graphs
Heterogeneous information networks
Image edge detection
Industries
meta path
Nodes
Real-time systems
Response time (computers)
Search algorithms
Shortest-path problems
Time factors
top-<named-content xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:ali="http://www.niso.org/schemas/ali/1.0/" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" content-type="kwd" xlink:type="simple"> <inline-formula> <tex-math notation="LaTeX"> k</tex-math> <mml:math> <mml:mi>k</mml:mi> </mml:math> <inline-graphic xlink:href="zhu-ieq12-3037218.gif" xlink:type="simple"/> </inline-formula> </named-content>
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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 s and t t , and a natural number k k , we study the discovery of the k k 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 s s and t t may not necessarily be the most important path. As such, we combine several ranking functions, which are based on frequency and rarity , to redefine the unified importance function of the meta paths between s s and t t . Although this importance function can capture more information, it is very time-consuming to find top-k k 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 s
ISSN:1041-4347
1558-2191
DOI:10.1109/TKDE.2020.3037218