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. / published_or_final_version / Computer Science / Master / Master of Philosophy
| Identifer | oai:union.ndltd.org:HKU/oai:hub.hku.hk:10722/209504 |
| Date | January 2014 |
| Creators | Meng, Changping, 蒙昌平 |
| Publisher | The University of Hong Kong (Pokfulam, Hong Kong) |
| Source Sets | Hong Kong University Theses |
| Language | English |
| Detected Language | English |
| Type | PG_Thesis |
| Rights | The author retains all proprietary rights, (such as patent rights) and the right to use in future works., Creative Commons: Attribution 3.0 Hong Kong License |
| Relation | HKU Theses Online (HKUTO) |
Page generated in 0.0025 seconds