Approximate Knowledge Graph Query Answering: From Ranking to Binary Classification

Lecture notes in computer science, pp. 107–124

Abstract

Abstract Large, heterogeneous datasets are characterized by missing or even erroneous information. This is more evident when they are the product of community effort or automatic fact extraction methods from external sources, such as text. A special case of the aforementioned phenomenon can be seen in knowledge graphs, where this mostly appears in the form of missing or incorrect edges and nodes. Structured querying on such incomplete graphs will result in incomplete sets of answers, even if the correct entities exist in the graph, since one or more edges needed to match the pattern are missing. To overcome this problem, several algorithms for approximate structured query answering have been proposed. Inspired by modern Information Retrieval metrics, these algorithms produce a ranking of all entities in the graph, and their performance is further evaluated based on how high in this ranking the correct answers appear. In this work we take a critical look at this way of evaluation. We argue that performing a ranking-based evaluation is not sufficient to assess methods for complex query answering. To solve this, we introduce Message Passing Query Boxes (MPQB), which takes binary classification metrics back into use and shows the effect this has on the recently proposed query embedding method MPQE.

Authors 5

1. Ruud van Bakel corresponding

   Vrije Universiteit Amsterdam · University of Amsterdam

   Affiliation as printed

   University of Amsterdam

   Vrije Universiteit Amsterdam

   Computer Science, Vrije Universiteit Amsterdam, Amsterdam, The Netherlands

2. Teodor Ivanov Aleksiev corresponding Aachen

   Leiden University · Vrije Universiteit Amsterdam

   Affiliation as printed

   Leiden University

   Vrije Universiteit Amsterdam

   Computer Science, Vrije Universiteit Amsterdam, Amsterdam, The Netherlands

3. Daniel Daza corresponding

   Elsevier BV (Netherlands) · Vrije Universiteit Amsterdam · University of Amsterdam

   Affiliation as printed

   Elsevier

   University of Amsterdam

   Vrije Universiteit Amsterdam

   Computer Science, Vrije Universiteit Amsterdam, Amsterdam, The Netherlands

4. Dimitrios Alivanistos corresponding

   Elsevier BV (Netherlands) · Vrije Universiteit Amsterdam

   Affiliation as printed

   Elsevier

   Vrije Universiteit Amsterdam

   Computer Science, Vrije Universiteit Amsterdam, Amsterdam, The Netherlands

5. Michael Cochez corresponding

   Elsevier BV (Netherlands) · Vrije Universiteit Amsterdam

   Affiliation as printed

   Elsevier

   Vrije Universiteit Amsterdam

   Computer Science, Vrije Universiteit Amsterdam, Amsterdam, The Netherlands