Approximate Knowledge Graph Query Answering: From Ranking to Binary Classification

Ruud van Bakel, Teodor Aleksiev, Daniel Daza, Dimitrios Alivanistos, Michael Cochez

Knowledge Graphs (KGs) are fundamental structures for representing relational data, yet they are inherently incomplete. Traditional database queries fail when edges are missing, leading to the development of Approximate Query Answering (AQA). While current AQA methods focus on ranking potential answers, real-world applications often require a definitive binary decision. This paper introduces Message Passing Query Boxes (MPQB), a novel approach that represents both queries and entities as axis-aligned hyper-rectangles (boxes) to facilitate binary classification.

The Problem: Beyond Ranked Lists

In a typical KG, entities like "Alice" and "Bob" are connected to projects or topics via specific relations. However, if the link between "Alice" and "Project X" is missing, a standard symbolic query will return an empty result. AQA addresses this by embedding entities and queries into a continuous vector space, allowing for the retrieval of "likely" answers.

A typical Knowledge Graph query structure where multiple entities relate to a target node.

Currently, AQA systems are evaluated as ranking tasks, producing a list of entities ordered by proximity to a query point. For downstream tasks like automated reasoning or recommendation engines, a ranked list is often insufficient; these systems need a discrete "yes" or "no" for each entity. The transition from "how close is this entity?" to "is this entity a valid answer?" remains a significant hurdle in the field.

Methodology: Message Passing Query Boxes (MPQB)

The proposed MPQB framework merges Message Passing Query Embedding (MPQE) with the geometric intuition of Query2Box. MPQE utilizes Graph Convolutional Networks (specifically R-GCNs) to propagate information through the query's graph structure. While Query2Box represents queries as boxes, MPQB extends this logic by representing entities as boxes as well.

In this geometric framework, each box is defined by a center vector and an offset vector, representing its "volume." An entity is considered a valid answer if its box physically overlaps with the query box. This approach allows the model to capture uncertainty and the multi-faceted nature of entities. The researchers explored various aggregation methods for the message-passing phase, finding that Tree-structured Message passing (TM) best preserved the hierarchical logic of complex queries.

Geometric Insights: Points vs. Boxes

Representing entities as single points in space is limiting. A point forces an entity into a single semantic location, whereas a box allows an entity to occupy a region. This is particularly useful for entities that fulfill multiple roles or belong to disparate categories.

Geometric representation of queries and entities as overlapping boxes (A, B, C) in a high-dimensional space.

As shown in the figure above, a box can overlap with multiple disjoint query regions. For instance, a person who is both a "Professor" and a "Politician" can have a box large enough to intersect with query boxes for both academic and political roles. This "volume" provides a natural boundary for binary classification that point-based embeddings lack.

Experimental Results and Limitations

The model was evaluated primarily on the AIFB dataset, alongside MUTAG and AM datasets for context. Using the TM aggregator, MPQB achieved accuracy scores between 63% and 79% in identifying true answers over random non-answers, with the best performance on "3-chain" query structures.

However, as a proof-of-concept, the model faces several challenges:

  1. Convergence: In its current state, the model struggles to achieve "hard" physical overlap during training. While correct answers are placed significantly closer to query boxes than non-answers, they do not always intersect.
  2. Logical Complexity: While boxes handle conjunctions (intersections) naturally, they struggle with disjunctions (OR) and negations (NOT), as the union or complement of boxes does not necessarily result in another axis-aligned box.
  3. Thresholding: Determining the optimal "size" for boxes to balance precision and recall remains an open research question.

Conclusion

MPQB represents a significant step toward moving AQA from a ranking task to a formal classification task. By leveraging the geometric properties of hyper-rectangles for both queries and entities, the framework provides a more robust foundation for binary decision-making in incomplete Knowledge Graphs. Future work will focus on improving convergence and expanding the geometric vocabulary to handle a wider range of logical operators.

Summary updated

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.
BibTeX
@inproceedings{bakel2020approximate,
  author = {Ruud van Bakel and Teodor Aleksiev and Daniel Daza and Dimitrios Alivanistos and Michael Cochez},
  title = {{Approximate Knowledge Graph Query Answering: From Ranking to Binary Classification}},
  booktitle = {GKR},
  year = {2020},
  doi = {10.1007/978-3-030-72308-8\_8},
}
Figure