StructSim: Meta-Structure-Based Similarity Measure in Heterogeneous Information Networks

Abstract

Similarity measures in heterogeneous information networks (HINs) have become increasingly important in recent years. Most measures in such networks are based on the meta path, a relation sequence connecting object types. However, in real-world scenarios, there exist many complex semantic relationships, which cannot be captured by the meta path. Therefore, a meta structure is proposed, which is a directed acyclic graph of object and relation types. In this paper, we explore the complex semantic meanings in HINs and propose a meta-structure-based similarity measure called StructSim. StructSim models the probability of subgraph expansion with bias from source node to target node. Different from existing methods, StructSim claims that the subgraph expansion is biased, i.e., the probability may be different when expanding from the same node to different nodes with the same type based on the meta structure. Moreover, StructSim defines the expansion bias by considering two types of node information, including out-neighbors of current expanded nodes and in-neighbors of next hop nodes to be expanded. To facilitate the implementation of StructSim, we further designed the node composition operator and expansion probability matrix with bias. Extensive experiments on DBLP and YAGO datasets demonstrate that StructSim is more effective than the state-of-the-art approaches.

Keywords

• heterogeneous information network
• similarity measure
• meta structure
• meta path
• complex semantics analysis
• knowledge graph