# Rethinking Complex Queries on Knowledge Graphs with Neural Link Predictors

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

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- Builds on 20 of its 42 references that are in the map.
- First posted on arXiv 14 Apr 2023.

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

- [Complex Embeddings for Simple Link Prediction](https://mlsanity.com/paper/1606.06357/) (2016)
- [Neural Bellman-Ford Networks: A General Graph Neural Network Framework for Link Prediction](https://mlsanity.com/paper/2106.06935/) (2021)
- [Query2box: Reasoning over Knowledge Graphs in Vector Space using Box Embeddings](https://mlsanity.com/paper/2002.05969/) (2020)
- [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)
- [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)
- [ConE: Cone Embeddings for Multi-Hop Reasoning over Knowledge Graphs](https://mlsanity.com/paper/2110.13715/) (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)
- [TensorLog: A Differentiable Deductive Database](https://mlsanity.com/paper/1605.06523/) (2016)
- [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)
- [Query2Particles: Knowledge Graph Reasoning with Particle Embeddings](https://mlsanity.com/paper/2204.12847/) (2022)
- [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)
- [Neural-Symbolic Entangled Framework for Complex Query Answering](https://mlsanity.com/paper/2209.08779/) (2022)
- [Logic Embeddings for Complex Query Answering](https://mlsanity.com/paper/2103.00418/) (2021)

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

- [A Foundation Model for Zero-shot Logical Query Reasoning](https://mlsanity.com/paper/2404.07198/) (2024)
- [EFOk-CQA: Towards Knowledge Graph Complex Query Answering beyond Set Operation](https://mlsanity.com/paper/2307.13701/) (2023)
- [Efficient Prompt Compression with Evaluator Heads for Long-Context Transformer Inference](https://mlsanity.com/paper/2501.12959/) (2025)
- [Improving Complex Reasoning over Knowledge Graph with Logic-Aware Curriculum Tuning](https://mlsanity.com/paper/2405.01649/) (2024)
- [Is Complex Query Answering Really Complex?](https://mlsanity.com/paper/2410.12537/) (2024)
- [Privacy-Preserved Neural Graph Databases](https://mlsanity.com/paper/2312.15591/) (2023)
- [A Neuro-Symbolic Framework for Answering Graph Pattern Queries in Knowledge Graphs](https://mlsanity.com/paper/2310.04598/) (2023)
- [Meta Operator for Complex Query Answering on Knowledge Graphs](https://mlsanity.com/paper/2403.10110/) (2024)
- [KGCompiler: Deep Learning Compilation Optimization for Knowledge Graph Complex Logical Query Answering](https://mlsanity.com/paper/2503.02172/) (2025)
- [KGMark: A Diffusion Watermark for Knowledge Graphs](https://mlsanity.com/paper/2505.23873/) (2025)
- [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)
- [MERIT: Scaling KG Foundation Models with Relation Transformers](https://mlsanity.com/paper/2610.15638/) (2026)

## Abstract (arXiv)

Reasoning on knowledge graphs is a challenging task because it utilizes observed information to predict the missing one. Particularly, answering complex queries based on first-order logic is one of the crucial tasks to verify learning to reason abilities for generalization and composition. Recently, the prevailing method is query embedding which learns the embedding of a set of entities and treats logic operations as set operations and has shown great empirical success. Though there has been much research following the same formulation, many of its claims lack a formal and systematic inspection. In this paper, we rethink this formulation and justify many of the previous claims by characterizing the scope of queries investigated previously and precisely identifying the gap between its formulation and its goal, as well as providing complexity analysis for the currently investigated queries. Moreover, we develop a new dataset containing ten new types of queries with features that have never been considered and therefore can provide a thorough investigation of complex queries. Finally, we propose a new neural-symbolic method, Fuzzy Inference with Truth value (FIT), where we equip the neural link predictors with fuzzy logic theory to support end-to-end learning using complex queries with provable reasoning capability. Empirical results show that our method outperforms previous methods significantly in the new dataset and also surpasses previous methods in the existing dataset at the same time.