Abstract
Current Knowledge Graph (KG) query systems primarily focus on ranking entities, which limits their utility for downstream applications requiring discrete answer sets. We propose Message Passing Query Boxes (MPQB), a framework that represents both queries and entities as axis-aligned hyper-rectangles (boxes). By treating query answering as a binary classification task based on box intersection, MPQB establishes hard boundaries for answer sets. Our proof-of-concept evaluation on the AIFB dataset demonstrates the potential of volume-based embeddings to capture complex relational logic and improve decision-making in incomplete KGs.
Introduction
Knowledge Graphs (KGs) are vast networks of entities and their relationships, serving as the backbone for many intelligent systems. However, KGs are notoriously incomplete. Traditional database queries fail if a single link is missing. To address this, researchers developed "approximate" query answering using machine learning embeddings.
A significant limitation of current systems is their reliance on ranking. Evaluation metrics like Mean Reciprocal Rank (MRR) indicate if a correct answer is near the top of a list, but they do not provide a definitive "Yes" or "No" for downstream applications. This paper advocates for a shift from ranking to binary classification, requiring systems to explicitly define the boundaries of an answer set.
Methodology: Message Passing Query Boxes (MPQB)
The proposed MPQB framework integrates Message Passing Query Embeddings (MPQE) with the Query2Box approach. While previous models represented queries as boxes and entities as points, MPQB represents both as axis-aligned hyper-rectangles (boxes).
Geometric Logic and Overlap
An entity is considered a valid answer if its box intersects with the query box. This volume-based approach allows the model to capture the "width" or specificity of a concept. For instance, a broad query like "People who live in Europe" results in a large box, whereas a specific entity like "Alice" is represented by a smaller box. This geometric representation allows entities to occupy multiple roles; two boxes might overlap in one dimension (context) while remaining distant in others.
Experimental Setup
The model was evaluated using the AIFB dataset, which describes an academic institution's entities (persons, projects, publications). Comparative statistics were also considered for MUTAG (complex molecules) and AM (Amsterdam Museum artifacts). The researchers generated seven distinct query structures, including chains and intersections, to test multi-hop reasoning capabilities.
To sharpen the decision boundary, the authors utilized "hard negatives"—entities similar to the answer but technically incorrect—to address the challenges posed by the Closed-World Assumption in incomplete KGs.
Results and Discussion
The proof-of-concept results indicate both promise and areas for improvement:
- Convergence and Overlap: The model initially struggled with convergence, requiring over 200,000 iterations to achieve full box overlap for correct answers.
- Relative Proximity: Even in cases where boxes did not overlap, target boxes were significantly closer to the query box than non-answers.
- Aggregator Performance: The Target-aware Message passing (TM) aggregator outperformed standard SUM or MLP aggregators, placing answers closer to the query box in 70-80% of cases across various query structures.
Conclusion
MPQB introduces a novel way to handle the "hard" boundaries required for real-world software applications by utilizing geometric volumes. However, limitations remain regarding training scale and the complexity of queries. Future work will explore handling negation (NOT) and disjunction (OR) logic, which require more complex geometric shapes than simple boxes, and tuning the overlap thresholds for specific task requirements.
Summary updated