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.
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.
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:
- 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.
- 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.
- 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