# EFOk-CQA: Towards Knowledge Graph Complex Query Answering beyond Set Operation

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

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- Placed in Knowledge- and tool-augmented reasoning, one of 17 directions in LLM reasoning.
- Builds on 23 of its 73 references that are in the map.
- First posted on arXiv 15 Jul 2023.

## Placed in

- LLM reasoning / [Knowledge- and tool-augmented reasoning](https://mlsanity.com/lr/knowledge-and-tool-augmented-reasoning/)

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

- [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)
- [Complex Query Answering with Neural Link Predictors](https://mlsanity.com/paper/2011.03459/) (2020)
- [Question Answering Over Temporal Knowledge Graphs](https://mlsanity.com/paper/2106.01515/) (2021)
- [ConE: Cone Embeddings for Multi-Hop Reasoning over Knowledge Graphs](https://mlsanity.com/paper/2110.13715/) (2021)
- [Complex Temporal Question Answering on Knowledge Graphs](https://mlsanity.com/paper/2109.08935/) (2021)
- [Mask and Reason: Pre-Training Knowledge Graph Transformers for Complex Logical Queries](https://mlsanity.com/paper/2208.07638/) (2022)
- [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)
- [Query2Particles: Knowledge Graph Reasoning with Particle Embeddings](https://mlsanity.com/paper/2204.12847/) (2022)
- [Query Embedding on Hyper-relational Knowledge Graphs](https://mlsanity.com/paper/2106.08166/) (2021)
- [Benchmarking the Combinatorial Generalizability of Complex Query Answering on Knowledge Graphs](https://mlsanity.com/paper/2109.08925/) (2021)
- [Neural-Symbolic Entangled Framework for Complex Query Answering](https://mlsanity.com/paper/2209.08779/) (2022)
- [Few-shot Relational Reasoning via Connection Subgraph Pretraining](https://mlsanity.com/paper/2210.06722/) (2022)
- [Logic Embeddings for Complex Query Answering](https://mlsanity.com/paper/2103.00418/) (2021)
- [Wasserstein-Fisher-Rao Embedding: Logical Query Embeddings with Local Comparison and Global Transport](https://mlsanity.com/paper/2305.04034/) (2023)
- [Type-aware Embeddings for Multi-Hop Reasoning over Knowledge Graphs](https://mlsanity.com/paper/2205.00782/) (2022)
- [Rethinking Complex Queries on Knowledge Graphs with Neural Link Predictors](https://mlsanity.com/paper/2304.07063/) (2023)
- [Knowledge Graph Reasoning over Entities and Numerical Values](https://mlsanity.com/paper/2306.01399/) (2023)
- [NQE: N-ary Query Embedding for Complex Query Answering over Hyper-Relational Knowledge Graphs](https://mlsanity.com/paper/2211.13469/) (2022)

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

- [Extending Context Window of Large Language Models via Semantic Compression](https://mlsanity.com/paper/2312.09571/) (2023)
- [Advancing Abductive Reasoning in Knowledge Graphs through Complex Logical Hypothesis Generation](https://mlsanity.com/paper/2312.15643/) (2023)
- [A Foundation Model for Zero-shot Logical Query Reasoning](https://mlsanity.com/paper/2404.07198/) (2024)
- [Efficient Prompt Compression with Evaluator Heads for Long-Context Transformer Inference](https://mlsanity.com/paper/2501.12959/) (2025)
- [Is Complex Query Answering Really Complex?](https://mlsanity.com/paper/2410.12537/) (2024)
- [Understanding Inter-Session Intentions via Complex Logical Reasoning](https://mlsanity.com/paper/2312.13866/) (2023)
- [Conditional Logical Message Passing Transformer for Complex Query Answering](https://mlsanity.com/paper/2402.12954/) (2024)
- [Meta Operator for Complex Query Answering on Knowledge Graphs](https://mlsanity.com/paper/2403.10110/) (2024)
- [Learning Representations for Reasoning: Generalizing Across Diverse Structures](https://mlsanity.com/paper/2410.13018/) (2024)
- [One Model, Any Conjunctive Query: Graph Neural Networks for Answering Queries over Incomplete Knowledge Graphs](https://mlsanity.com/paper/2409.13959/) (2024)
- [NGDBench: Towards Neural Graph Data Management](https://mlsanity.com/paper/2603.05529/) (2026)
- [Neural Scalable Symbolic Search Framework for Complex Logical Queries with Multiple Free Variables](https://mlsanity.com/paper/2605.25985/) (2026)

## Abstract (arXiv)

To answer complex queries on knowledge graphs, logical reasoning over incomplete knowledge is required due to the open-world assumption. Learning-based methods are essential because they are capable of generalizing over unobserved knowledge. Therefore, an appropriate dataset is fundamental to both obtaining and evaluating such methods under this paradigm. In this paper, we propose a comprehensive framework for data generation, model training, and method evaluation that covers the combinatorial space of Existential First-order Queries with multiple variables (EFOk). The combinatorial query space in our framework significantly extends those defined by set operations in the existing literature. Additionally, we construct a dataset, EFOk-CQA, with 741 types of query for empirical evaluation, and our benchmark results provide new insights into how query hardness affects the results. Furthermore, we demonstrate that the existing dataset construction process is systematically biased that hinders the appropriate development of query-answering methods, highlighting the importance of our work. Our code and data are provided in~urlhttps://github.com/HKUST-KnowComp/EFOK-CQA.