# Answering Complex Logical Queries on Knowledge Graphs via Query Computation Tree Optimization

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

## Key facts

- Cited by 29 papers in the map (data through 14 Oct 2026).
- Builds on 23 of its 35 references that are in the map.
- First posted on arXiv 19 Dec 2022.

## Builds on (most cited first, 23 of 23)

- [Modeling Relational Data with Graph Convolutional Networks](https://mlsanity.com/paper/1703.06103/) (2017)
- [Complex Embeddings for Simple Link Prediction](https://mlsanity.com/paper/1606.06357/) (2016)
- [RotatE: Knowledge Graph Embedding by Relational Rotation in Complex Space](https://mlsanity.com/paper/1902.10197/) (2019)
- [Convolutional 2D Knowledge Graph Embeddings](https://mlsanity.com/paper/1707.01476/) (2017)
- [TuckER: Tensor Factorization for Knowledge Graph Completion](https://mlsanity.com/paper/1901.09590/) (2019)
- [Neural Bellman-Ford Networks: A General Graph Neural Network Framework for Link Prediction](https://mlsanity.com/paper/2106.06935/) (2021)
- [DeepPath: A Reinforcement Learning Method for Knowledge Graph Reasoning](https://mlsanity.com/paper/1707.06690/) (2017)
- [Low-Dimensional Hyperbolic Knowledge Graph Embeddings](https://mlsanity.com/paper/2005.00545/) (2020)
- [Query2box: Reasoning over Knowledge Graphs in Vector Space using Box Embeddings](https://mlsanity.com/paper/2002.05969/) (2020)
- [Go for a Walk and Arrive at the Answer: Reasoning Over Paths in Knowledge Bases using Reinforcement Learning](https://mlsanity.com/paper/1711.05851/) (2017)
- [Canonical Tensor Decomposition for Knowledge Base Completion](https://mlsanity.com/paper/1806.07297/) (2018)
- [Beta Embeddings for Multi-Hop Logical Reasoning in Knowledge Graphs](https://mlsanity.com/paper/2010.11465/) (2020)
- [Embedding Logical Queries on Knowledge Graphs](https://mlsanity.com/paper/1806.01445/) (2018)
- [Multi-Hop Knowledge Graph Reasoning with Reward Shaping](https://mlsanity.com/paper/1808.10568/) (2018)
- [Complex Query Answering with Neural Link Predictors](https://mlsanity.com/paper/2011.03459/) (2020)
- [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)
- [Traversing Knowledge Graphs in Vector Space](https://mlsanity.com/paper/1506.01094/) (2015)
- [Modeling Heterogeneous Hierarchies with Relation-specific Hyperbolic Cones](https://mlsanity.com/paper/2110.14923/) (2021)
- [Relation Prediction as an Auxiliary Training Objective for Improving Multi-Relational Graph Representations](https://mlsanity.com/paper/2110.02834/) (2021)
- [Self-Supervised Hyperboloid Representations from Logical Queries over Knowledge Graphs](https://mlsanity.com/paper/2012.13023/) (2020)
- [Adapting Meta Knowledge Graph Information for Multi-Hop Reasoning over Few-Shot Relations](https://mlsanity.com/paper/1908.11513/) (2019)
- [SQUIRE: A Sequence-to-sequence Framework for Multi-hop Knowledge Graph Reasoning](https://mlsanity.com/paper/2201.06206/) (2022)

## Built on by (most cited first, 29 of 29)

- [LongBench v2: Towards Deeper Understanding and Reasoning on Realistic Long-context Multitasks](https://mlsanity.com/paper/2412.15204/) (2024)
- [GFT: Graph Foundation Model with Transferable Tree Vocabulary](https://mlsanity.com/paper/2411.06070/) (2024)
- [Neural Graph Reasoning: Complex Logical Query Answering Meets Graph Databases](https://mlsanity.com/paper/2303.14617/) (2023)
- [Probabilistic Tree-of-thought Reasoning for Answering Knowledge-intensive Complex Questions](https://mlsanity.com/paper/2311.13982/) (2023)
- [A Foundation Model for Zero-shot Logical Query Reasoning](https://mlsanity.com/paper/2404.07198/) (2024)
- [Sequential Query Encoding For Complex Query Answering on Knowledge Graphs](https://mlsanity.com/paper/2302.13114/) (2023)
- [Rethinking Complex Queries on Knowledge Graphs with Neural Link Predictors](https://mlsanity.com/paper/2304.07063/) (2023)
- [Top Ten Challenges Towards Agentic Neural Graph Databases](https://mlsanity.com/paper/2501.14224/) (2025)
- [EFOk-CQA: Towards Knowledge Graph Complex Query Answering beyond Set Operation](https://mlsanity.com/paper/2307.13701/) (2023)
- [Is Complex Query Answering Really Complex?](https://mlsanity.com/paper/2410.12537/) (2024)
- [Effective Instruction Parsing Plugin for Complex Logical Query Answering on Knowledge Graphs](https://mlsanity.com/paper/2410.20321/) (2024)
- [Understanding Inter-Session Intentions via Complex Logical Reasoning](https://mlsanity.com/paper/2312.13866/) (2023)
- [Enhancing Transformers for Generalizable First-Order Logical Entailment](https://mlsanity.com/paper/2501.00759/) (2025)
- [A Neuro-Symbolic Framework for Answering Graph Pattern Queries in Knowledge Graphs](https://mlsanity.com/paper/2310.04598/) (2023)
- [Extending Complex Logical Queries on Uncertain Knowledge Graphs](https://mlsanity.com/paper/2403.01508/) (2024)
- [Knowledge Base Embeddings: Semantics and Theoretical Properties](https://mlsanity.com/paper/2408.04913/) (2024)
- [Transformers for Complex Query Answering over Knowledge Hypergraphs](https://mlsanity.com/paper/2504.16537/) (2025)
- [Pathformer: Recursive Path Query Encoding for Complex Logical Query Answering](https://mlsanity.com/paper/2406.14880/) (2024)
- [Complex Logical Query Answering by Calibrating Knowledge Graph Completion Models](https://mlsanity.com/paper/2410.07165/) (2024)
- [KGCompiler: Deep Learning Compilation Optimization for Knowledge Graph Complex Logical Query Answering](https://mlsanity.com/paper/2503.02172/) (2025)
- [Efficient and Scalable Neural Symbolic Search for Knowledge Graph Complex Query Answering](https://mlsanity.com/paper/2505.08155/) (2025)
- [Neural Reasoning for Robust Instance Retrieval in SHOIQ](https://mlsanity.com/paper/2510.20457/) (2025)
- [Type-based Neural Link Prediction Adapter for Complex Query Answering](https://mlsanity.com/paper/2401.16045/) (2024)
- [One Model, Any Conjunctive Query: Graph Neural Networks for Answering Queries over Incomplete Knowledge Graphs](https://mlsanity.com/paper/2409.13959/) (2024)
- [Interactive Query Answering on Knowledge Graphs with Soft Entity Constraints](https://mlsanity.com/paper/2508.13663/) (2025)
- [CQD-SHAP: Explainable Complex Query Answering via Shapley Values](https://mlsanity.com/paper/2510.15623/) (2025)
- [Counting Still Counts: Understanding Neural Complex Query Answering Through Query Relaxation](https://mlsanity.com/paper/2511.22565/) (2025)
- [Neural Scalable Symbolic Search Framework for Complex Logical Queries with Multiple Free Variables](https://mlsanity.com/paper/2605.25985/) (2026)
- [MERIT: Scaling KG Foundation Models with Relation Transformers](https://mlsanity.com/paper/2610.15638/) (2026)

## Abstract (arXiv)

Answering complex logical queries on incomplete knowledge graphs is a challenging task, and has been widely studied. Embedding-based methods require training on complex queries, and cannot generalize well to out-of-distribution query structures. Recent work frames this task as an end-to-end optimization problem, and it only requires a pretrained link predictor. However, due to the exponentially large combinatorial search space, the optimal solution can only be approximated, limiting the final accuracy. In this work, we propose QTO (Query Computation Tree Optimization) that can efficiently find the exact optimal solution. QTO finds the optimal solution by a forward-backward propagation on the tree-like computation graph, i.e., query computation tree. In particular, QTO utilizes the independence encoded in the query computation tree to reduce the search space, where only local computations are involved during the optimization procedure. Experiments on 3 datasets show that QTO obtains state-of-the-art performance on complex query answering, outperforming previous best results by an average of 22%. Moreover, QTO can interpret the intermediate solutions for each of the one-hop atoms in the query with over 90% accuracy. The code of our paper is at https://github.com/bys0318/QTO.