HOPLoP: Multi-hop Link Prediction over Knowledge Graph Embeddings

• Author / Creator

  Ranganathan, Varun

• Large-scale Knowledge Graphs (KGs) built from Web resources have gained in importance and popularity in support of applications such as question answering, which are ubiquitous, and also as a source of training data for a plethora of tasks in natural language processing and artificial intelligence. Despite their success, building and maintaining KGs remains a challenge: manual approaches offer higher accuracy but very limited coverage while automatic approaches yield low coverage due to the limitations of the state-of-the-art Information Extraction tools. As a result, even the best KGs out there are notoriously incomplete, giving rise to a large crop of reasoning tools for the task of Link Prediction, aimed at finding missing links in the graph based on structural regularities in the graph. Among the many LP methods, those based on embeddings have become prevalent in the literature. In particular, multi-hop link prediction algorithms have been found to model complex relations better by exploiting correlations between types of relations and paths connecting the entities related in that way. However, state-of-the-art multi-hop methods find paths by traversing the KG itself, and, therefore, are hampered by the incompleteness of the KGs themselves and by the skewed degree distribution in the KG---which causes some so-called supernodes to be overly represented during training and testing, resulting in poor generalization. We present a simple, efficient and highly effective multi-hop method, called \HOPLOP, whose main predicate is to perform ``traversals'' on the embedding space instead of the KG itself. We show how to train and tune our method, and report on experiments with different representative embedding-based LP methods on many benchmarks, showing that \HOPLOP improves each LP method on its own and that it consistently outperforms the previous state-of-the-art multi-hop LP methods by a good margin. Finally, we also describe a method for the interpretation of the paths generated during reasoning by \HOPLOP when used with embedding models where entities and relations are mapped to the same space.

• Subjects / Keywords

  • Link Prediction
  • Knowledge Graph Embeddings
  • Multi-hop Reasoning

• Graduation date

  Fall 2021

• Type of Item

  Thesis

• Degree

  Master of Science

• DOI

  https://doi.org/10.7939/r3-r7vb-cz02

• License

  This thesis is made available by the University of Alberta Libraries with permission of the copyright owner solely for non-commercial purposes. This thesis, or any portion thereof, may not otherwise be copied or reproduced without the written consent of the copyright owner, except to the extent permitted by Canadian copyright law.