# Is Complex Query Answering Really Complex?

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

## Key facts

- Cited by 8 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 16 Oct 2024.

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

- [Knowledge Graphs](https://mlsanity.com/paper/2003.02320/) (2020)
- [DeepPath: A Reinforcement Learning Method for Knowledge Graph Reasoning](https://mlsanity.com/paper/1707.06690/) (2017)
- [Query2box: Reasoning over Knowledge Graphs in Vector Space using Box Embeddings](https://mlsanity.com/paper/2002.05969/) (2020)
- [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)
- [Analyzing Differentiable Fuzzy Logic Operators](https://mlsanity.com/paper/2002.06100/) (2020)
- [Complex Query Answering with Neural Link Predictors](https://mlsanity.com/paper/2011.03459/) (2020)
- [Towards Foundation Models for Knowledge Graph Reasoning](https://mlsanity.com/paper/2310.04562/) (2023)
- [Knowledge Graph Completion via Complex Tensor Factorization](https://mlsanity.com/paper/1702.06879/) (2017)
- [Message Passing for Hyper-Relational Knowledge Graphs](https://mlsanity.com/paper/2009.10847/) (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)
- [Self-Supervised Hyperboloid Representations from Logical Queries over Knowledge Graphs](https://mlsanity.com/paper/2012.13023/) (2020)
- [Neural Graph Reasoning: Complex Logical Query Answering Meets Graph Databases](https://mlsanity.com/paper/2303.14617/) (2023)
- [Answering Complex Logical Queries on Knowledge Graphs via Query Computation Tree Optimization](https://mlsanity.com/paper/2212.09567/) (2022)
- [Logical Message Passing Networks with One-hop Inference on Atomic Formulas](https://mlsanity.com/paper/2301.08859/) (2023)
- [Inductive Logical Query Answering in Knowledge Graphs](https://mlsanity.com/paper/2210.08008/) (2022)
- [How to Turn Your Knowledge Graph Embeddings into Generative Models](https://mlsanity.com/paper/2305.15944/) (2023)
- [Adapting Neural Link Predictors for Data-Efficient Complex Query Answering](https://mlsanity.com/paper/2301.12313/) (2023)
- [Rethinking Complex Queries on Knowledge Graphs with Neural Link Predictors](https://mlsanity.com/paper/2304.07063/) (2023)
- [EFOk-CQA: Towards Knowledge Graph Complex Query Answering beyond Set Operation](https://mlsanity.com/paper/2307.13701/) (2023)
- [Conditional Logical Message Passing Transformer for Complex Query Answering](https://mlsanity.com/paper/2402.12954/) (2024)

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

- [Do Large Language Models Perform Latent Multi-Hop Reasoning without Exploiting Shortcuts?](https://mlsanity.com/paper/2411.16679/) (2024)
- [SEMMA: A Semantic Aware Knowledge Graph Foundation Model](https://mlsanity.com/paper/2505.20422/) (2025)
- [DAGE: DAG Query Answering via Relational Combinator with Logical Constraints](https://mlsanity.com/paper/2410.22105/) (2024)
- [Efficient and Scalable Neural Symbolic Search for Knowledge Graph Complex Query Answering](https://mlsanity.com/paper/2505.08155/) (2025)
- [Better Later Than Sooner: Neuro-Symbolic Knowledge Graph Construction via Ontology-grounded Post-extraction Correction](https://mlsanity.com/paper/2605.29168/) (2026)
- [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)
- [MERIT: Scaling KG Foundation Models with Relation Transformers](https://mlsanity.com/paper/2610.15638/) (2026)

## Abstract (arXiv)

Complex query answering (CQA) on knowledge graphs (KGs) is gaining momentum as a challenging reasoning task. In this paper, we show that the current benchmarks for CQA might not be as complex as we think, as the way they are built distorts our perception of progress in this field. For example, we find that in these benchmarks, most queries (up to 98% for some query types) can be reduced to simpler problems, e.g., link prediction, where only one link needs to be predicted. The performance of state-of-the-art CQA models decreases significantly when such models are evaluated on queries that cannot be reduced to easier types. Thus, we propose a set of more challenging benchmarks composed of queries that require models to reason over multiple hops and better reflect the construction of real-world KGs. In a systematic empirical investigation, the new benchmarks show that current methods leave much to be desired from current CQA methods.