# Efficient and Scalable Neural Symbolic Search for Knowledge Graph Complex Query Answering

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 33 of its 52 references that are in the map.
- First posted on arXiv 13 May 2025.

## Builds on (most cited first, 30 of 33)

- [Open Graph Benchmark: Datasets for Machine Learning on Graphs](https://mlsanity.com/paper/2005.00687/) (2020)
- [HyperNetworks](https://mlsanity.com/paper/1609.09106/) (2016)
- [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)
- [A Survey on Knowledge Graphs: Representation, Acquisition and Applications](https://mlsanity.com/paper/2002.00388/) (2020)
- [A Survey of Hallucination in Large Foundation Models](https://mlsanity.com/paper/2309.05922/) (2023)
- [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)
- [CoDEx: A Comprehensive Knowledge Graph Completion Benchmark](https://mlsanity.com/paper/2009.07810/) (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)
- [Neural-Symbolic Models for Logical Queries on Knowledge Graphs](https://mlsanity.com/paper/2205.10128/) (2022)
- [Relation Prediction as an Auxiliary Training Objective for Improving Multi-Relational Graph Representations](https://mlsanity.com/paper/2110.02834/) (2021)
- [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)
- [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)
- [Complex Query Answering on Eventuality Knowledge Graph with Implicit Logical Constraints](https://mlsanity.com/paper/2305.19068/) (2023)
- [Neural-Symbolic Reasoning over Knowledge Graphs: A Survey from a Query Perspective](https://mlsanity.com/paper/2412.10390/) (2024)
- [SMORE: Knowledge Graph Completion and Multi-hop Reasoning in Massive Knowledge Graphs](https://mlsanity.com/paper/2110.14890/) (2021)
- [Rethinking Knowledge Graph Evaluation Under the Open-World Assumption](https://mlsanity.com/paper/2209.08858/) (2022)
- [Neural Methods for Logical Reasoning Over Knowledge Graphs](https://mlsanity.com/paper/2209.14464/) (2022)
- [Wasserstein-Fisher-Rao Embedding: Logical Query Embeddings with Local Comparison and Global Transport](https://mlsanity.com/paper/2305.04034/) (2023)
- [Top Ten Challenges Towards Agentic Neural Graph Databases](https://mlsanity.com/paper/2501.14224/) (2025)
- [CLR-Fact: Evaluating the Complex Logical Reasoning Capability of Large Language Models over Factual Knowledge](https://mlsanity.com/paper/2407.20564/) (2024)
- [Is Complex Query Answering Really Complex?](https://mlsanity.com/paper/2410.12537/) (2024)

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

- [Neural Scalable Symbolic Search Framework for Complex Logical Queries with Multiple Free Variables](https://mlsanity.com/paper/2605.25985/) (2026)

## Abstract (arXiv)

Complex Query Answering (CQA) is a crucial reasoning task over Knowledge Graphs (KGs), which aims to answer first-order logical queries from incomplete KGs. While existing neural-symbolic methods achieve strong performance, they face significant complexity bottlenecks: quadratic data complexity scaling with the number of entities, and NP-hard query complexity for cyclic queries. Consequently, these approaches struggle to scale effectively to large knowledge graphs and complex queries. To address these limitations, we propose an efficient and scalable symbolic search method comprising two key components: (1) constraint strategies that drastically reduce the variable search domain, lowering data complexity; and (2) a local search algorithm that approximately solves NP-hard cyclic queries. Experiments on various CQA benchmarks demonstrate that, for tree-form queries, our method achieves 97% relative MRR with a 10× speedup using only 10% of the search space. Furthermore, it demonstrates robust performance on complex cyclic queries and large-scale KGs, effectively alleviating efficiency and scalability challenges. Our code is provided in https://github.com/HKUST-KnowComp/NLISAKDD2026.