Discovering meta-paths in large knowledge bases

Abstract

A knowledge base, such as Yago or DBpedia, can be modeled as a large graph with nodes and edges annotated with class and relationship labels. Recent work has studied how to make use of these rich information sources. In particular, meta-paths, which represent sequences of node classes and edge types between two nodes in a knowledge base, have been proposed for such tasks as information retrieval, decision making, and product recommendation. Current methods assume meta-paths are found by domain experts. However, in a large and complex knowledge base, retrieving meta-paths manually can be tedious and difficult. We thus study how to discover meta-paths automatically. Specifically, users are asked to provide example pairs of nodes that exhibit high proximity. We then investigate how to generate meta-paths that can best explain the relationship between these node pairs. Since this problem is computationally intractable, we propose a greedy algorithm to select the most relevant meta-paths. We also present a data structure to enable efficient execution of this algorithm. We further incorporate hierarchical relationships among node classes in our solutions. Finally, we propose an effective similarity join algorithm in order to generate more node pairs using these meta-paths. Extensive experiments on real knowledge bases show that our approach captures important meta-paths in an efficient and scalable manner.