# Benchmarking the Combinatorial Generalizability of Complex Query Answering on Knowledge Graphs

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

## Key facts

- Cited by 21 papers in the map (data through 14 Oct 2026).
- Builds on 8 of its 24 references that are in the map.
- First posted on arXiv 18 Sep 2021.

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

- [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)
- [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)
- [Self-Supervised Hyperboloid Representations from Logical Queries over Knowledge Graphs](https://mlsanity.com/paper/2012.13023/) (2020)
- [Answering Complex Queries in Knowledge Graphs with Bidirectional Sequence Encoders](https://mlsanity.com/paper/2004.02596/) (2020)
- [Logic Embeddings for Complex Query Answering](https://mlsanity.com/paper/2103.00418/) (2021)

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

- [Evaluating Explainability for Graph Neural Networks](https://mlsanity.com/paper/2208.09339/) (2022)
- [Extending Context Window of Large Language Models via Semantic Compression](https://mlsanity.com/paper/2312.09571/) (2023)
- [Neural Graph Reasoning: Complex Logical Query Answering Meets Graph Databases](https://mlsanity.com/paper/2303.14617/) (2023)
- [Logical Message Passing Networks with One-hop Inference on Atomic Formulas](https://mlsanity.com/paper/2301.08859/) (2023)
- [Complex Query Answering on Eventuality Knowledge Graph with Implicit Logical Constraints](https://mlsanity.com/paper/2305.19068/) (2023)
- [Wasserstein-Fisher-Rao Embedding: Logical Query Embeddings with Local Comparison and Global Transport](https://mlsanity.com/paper/2305.04034/) (2023)
- [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)
- [Knowledge Graph Reasoning over Entities and Numerical Values](https://mlsanity.com/paper/2306.01399/) (2023)
- [Enhancing Transformers for Generalizable First-Order Logical Entailment](https://mlsanity.com/paper/2501.00759/) (2025)
- [Query2Triple: Unified Query Encoding for Answering Diverse Complex Queries over Knowledge Graphs](https://mlsanity.com/paper/2310.11246/) (2023)
- [Conversational Question Answering with Reformulations over Knowledge Graph](https://mlsanity.com/paper/2312.17269/) (2023)
- [DEXTER: A Benchmark for open-domain Complex Question Answering using LLMs](https://mlsanity.com/paper/2406.17158/) (2024)
- [On the Role of Entity and Event Level Conceptualization in Generalizable Reasoning: A Survey of Tasks, Methods, Applications, and Future Directions](https://mlsanity.com/paper/2406.10885/) (2024)
- [Extending Complex Logical Queries on Uncertain Knowledge Graphs](https://mlsanity.com/paper/2403.01508/) (2024)
- [Meta Operator for Complex Query Answering on Knowledge Graphs](https://mlsanity.com/paper/2403.10110/) (2024)
- [Transformers for Complex Query Answering over Knowledge Hypergraphs](https://mlsanity.com/paper/2504.16537/) (2025)
- [Efficient and Scalable Neural Symbolic Search for Knowledge Graph Complex Query Answering](https://mlsanity.com/paper/2505.08155/) (2025)
- [NGDBench: Towards Neural Graph Data Management](https://mlsanity.com/paper/2603.05529/) (2026)

## Abstract (arXiv)

Complex Query Answering (CQA) is an important reasoning task on knowledge graphs. Current CQA learning models have been shown to be able to generalize from atomic operators to more complex formulas, which can be regarded as the combinatorial generalizability. In this paper, we present EFO-1-QA, a new dataset to benchmark the combinatorial generalizability of CQA models by including 301 different queries types, which is 20 times larger than existing datasets. Besides, our work, for the first time, provides a benchmark to evaluate and analyze the impact of different operators and normal forms by using (a) 7 choices of the operator systems and (b) 9 forms of complex queries. Specifically, we provide the detailed study of the combinatorial generalizability of two commonly used operators, i.e., projection and intersection, and justify the impact of the forms of queries given the canonical choice of operators. Our code and data can provide an effective pipeline to benchmark CQA models.