# Query2box: Reasoning over Knowledge Graphs in Vector Space using Box Embeddings

arXiv: https://arxiv.org/abs/2002.05969 · HTML: https://mlsanity.com/paper/2002.05969/

## Key facts

- Cited by 171 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 14 Feb 2020.

## Built on by (most cited first, 30 of 171)

- [QA-GNN: Reasoning with Language Models and Knowledge Graphs for Question Answering](https://mlsanity.com/paper/2104.06378/) (2021)
- [Neural Bellman-Ford Networks: A General Graph Neural Network Framework for Link Prediction](https://mlsanity.com/paper/2106.06935/) (2021)
- [Combinatorial optimization and reasoning with graph neural networks](https://mlsanity.com/paper/2102.09544/) (2021)
- [GreaseLM: Graph REASoning Enhanced Language Models for Question Answering](https://mlsanity.com/paper/2201.08860/) (2022)
- [Deep Bidirectional Language-Knowledge Graph Pretraining](https://mlsanity.com/paper/2210.09338/) (2022)
- [ConE: Cone Embeddings for Multi-Hop Reasoning over Knowledge Graphs](https://mlsanity.com/paper/2110.13715/) (2021)
- [Neural-Symbolic Models for Logical Queries on Knowledge Graphs](https://mlsanity.com/paper/2205.10128/) (2022)
- [Mask and Reason: Pre-Training Knowledge Graph Transformers for Complex Logical Queries](https://mlsanity.com/paper/2208.07638/) (2022)
- [Modeling Fine-Grained Entity Types with Box Embeddings](https://mlsanity.com/paper/2101.00345/) (2021)
- [Neural Graph Reasoning: Complex Logical Query Answering Meets Graph Databases](https://mlsanity.com/paper/2303.14617/) (2023)
- [Knowledge Base Question Answering by Case-based Reasoning over Subgraphs](https://mlsanity.com/paper/2202.10610/) (2022)
- [Role-Aware Modeling for N-ary Relational Knowledge Bases](https://mlsanity.com/paper/2104.09780/) (2021)
- [Answering Complex Logical Queries on Knowledge Graphs via Query Computation Tree Optimization](https://mlsanity.com/paper/2212.09567/) (2022)
- [Probabilistic Entity Representation Model for Reasoning over Knowledge Graphs](https://mlsanity.com/paper/2110.13522/) (2021)
- [Logical Message Passing Networks with One-hop Inference on Atomic Formulas](https://mlsanity.com/paper/2301.08859/) (2023)
- [Complex Logical Reasoning over Knowledge Graphs using Large Language Models](https://mlsanity.com/paper/2305.01157/) (2023)
- [Inductive Logical Query Answering in Knowledge Graphs](https://mlsanity.com/paper/2210.08008/) (2022)
- [Faithiful Embeddings for EL++ Knowledge Bases](https://mlsanity.com/paper/2201.09919/) (2022)
- [Query2Particles: Knowledge Graph Reasoning with Particle Embeddings](https://mlsanity.com/paper/2204.12847/) (2022)
- [Learning to Plan for Retrieval-Augmented Large Language Models from Knowledge Graphs](https://mlsanity.com/paper/2406.14282/) (2024)
- [Query Embedding on Hyper-relational Knowledge Graphs](https://mlsanity.com/paper/2106.08166/) (2021)
- [Probabilistic Box Embeddings for Uncertain Knowledge Graph Reasoning](https://mlsanity.com/paper/2104.04597/) (2021)
- [Benchmarking the Combinatorial Generalizability of Complex Query Answering on Knowledge Graphs](https://mlsanity.com/paper/2109.08925/) (2021)
- [GammaE: Gamma Embeddings for Logical Queries on Knowledge Graphs](https://mlsanity.com/paper/2210.15578/) (2022)
- [Complex Query Answering on Eventuality Knowledge Graph with Implicit Logical Constraints](https://mlsanity.com/paper/2305.19068/) (2023)
- [FALCON: Fast Visual Concept Learning by Integrating Images, Linguistic descriptions, and Conceptual Relations](https://mlsanity.com/paper/2203.16639/) (2022)
- [Faithful to the Document or to the World? Mitigating Hallucinations via Entity-linked Knowledge in Abstractive Summarization](https://mlsanity.com/paper/2204.13761/) (2022)
- [Neural-Symbolic Reasoning over Knowledge Graphs: A Survey from a Query Perspective](https://mlsanity.com/paper/2412.10390/) (2024)
- [The Power of the Weisfeiler-Leman Algorithm for Machine Learning with Graphs](https://mlsanity.com/paper/2105.05911/) (2021)
- [Knowledge Graph Reasoning with Logics and Embeddings: Survey and Perspective](https://mlsanity.com/paper/2202.07412/) (2022)

## Abstract (arXiv)

Answering complex logical queries on large-scale incomplete knowledge graphs (KGs) is a fundamental yet challenging task. Recently, a promising approach to this problem has been to embed KG entities as well as the query into a vector space such that entities that answer the query are embedded close to the query. However, prior work models queries as single points in the vector space, which is problematic because a complex query represents a potentially large set of its answer entities, but it is unclear how such a set can be represented as a single point. Furthermore, prior work can only handle queries that use conjunctions (wedge) and existential quantifiers (exists). Handling queries with logical disjunctions (vee) remains an open problem. Here we propose query2box, an embedding-based framework for reasoning over arbitrary queries with wedge, vee, and exists operators in massive and incomplete KGs. Our main insight is that queries can be embedded as boxes (i.e., hyper-rectangles), where a set of points inside the box corresponds to a set of answer entities of the query. We show that conjunctions can be naturally represented as intersections of boxes and also prove a negative result that handling disjunctions would require embedding with dimension proportional to the number of KG entities. However, we show that by transforming queries into a Disjunctive Normal Form, query2box is capable of handling arbitrary logical queries with wedge, vee, exists in a scalable manner. We demonstrate the effectiveness of query2box on three large KGs and show that query2box achieves up to 25% relative improvement over the state of the art.