# Neural Graph Reasoning: Complex Logical Query Answering Meets Graph Databases

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

## Key facts

- Cited by 35 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 102 of its 171 references that are in the map.
- First posted on arXiv 26 Mar 2023.

## Placed in

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

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

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Chain-of-Thought Prompting Elicits Reasoning in Large Language Models](https://mlsanity.com/paper/2201.11903/) (2022)
- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Retrieval-Augmented Generation for Knowledge-Intensive NLP Tasks](https://mlsanity.com/paper/2005.11401/) (2020)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Self-Consistency Improves Chain of Thought Reasoning in Language Models](https://mlsanity.com/paper/2203.11171/) (2022)
- [Measuring Mathematical Problem Solving With the MATH Dataset](https://mlsanity.com/paper/2103.03874/) (2021)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [On the Opportunities and Risks of Foundation Models](https://mlsanity.com/paper/2108.07258/) (2021)
- [Neural Message Passing for Quantum Chemistry](https://mlsanity.com/paper/1704.01212/) (2017)
- [Billion-scale similarity search with GPUs](https://mlsanity.com/paper/1702.08734/) (2017)
- [REALM: Retrieval-Augmented Language Model Pre-Training](https://mlsanity.com/paper/2002.08909/) (2020)
- [node2vec: Scalable Feature Learning for Networks](https://mlsanity.com/paper/1607.00653/) (2016)
- [Modeling Relational Data with Graph Convolutional Networks](https://mlsanity.com/paper/1703.06103/) (2017)
- [DeepWalk: Online Learning of Social Representations](https://mlsanity.com/paper/1403.6652/) (2014)
- [Federated Learning: Challenges, Methods, and Future Directions](https://mlsanity.com/paper/1908.07873/) (2019)
- [Deep Sets](https://mlsanity.com/paper/1703.06114/) (2017)
- [Least-to-Most Prompting Enables Complex Reasoning in Large Language Models](https://mlsanity.com/paper/2205.10625/) (2022)
- [Relational inductive biases, deep learning, and graph networks](https://mlsanity.com/paper/1806.01261/) (2018)
- [Geometric Deep Learning: Grids, Groups, Graphs, Geodesics, and Gauges](https://mlsanity.com/paper/2104.13478/) (2021)
- [Neural Collaborative Filtering](https://mlsanity.com/paper/1708.05031/) (2017)
- [Program of Thoughts Prompting: Disentangling Computation from Reasoning for Numerical Reasoning Tasks](https://mlsanity.com/paper/2211.12588/) (2022)
- [ConceptNet 5.5: An Open Multilingual Graph of General Knowledge](https://mlsanity.com/paper/1612.03975/) (2016)
- [Embedding Entities and Relations for Learning and Inference in Knowledge Bases](https://mlsanity.com/paper/1412.6575/) (2014)
- [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)
- [Knowledge Graphs](https://mlsanity.com/paper/2003.02320/) (2020)
- [Augmented Language Models: a Survey](https://mlsanity.com/paper/2302.07842/) (2023)
- [Composition-based Multi-Relational Graph Convolutional Networks](https://mlsanity.com/paper/1911.03082/) (2019)
- [Neural Bellman-Ford Networks: A General Graph Neural Network Framework for Link Prediction](https://mlsanity.com/paper/2106.06935/) (2021)

## Built on by (most cited first, 30 of 35)

- [Complex Query Answering on Eventuality Knowledge Graph with Implicit Logical Constraints](https://mlsanity.com/paper/2305.19068/) (2023)
- [Can LLMs Evaluate Complex Attribution in QA? Automatic Benchmarking using Knowledge Graphs](https://mlsanity.com/paper/2401.14640/) (2024)
- [Wasserstein-Fisher-Rao Embedding: Logical Query Embeddings with Local Comparison and Global Transport](https://mlsanity.com/paper/2305.04034/) (2023)
- [A Foundation Model for Zero-shot Logical Query Reasoning](https://mlsanity.com/paper/2404.07198/) (2024)
- [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)
- [HOT: Higher-Order Dynamic Graph Representation Learning with Efficient Transformers](https://mlsanity.com/paper/2311.18526/) (2023)
- [Is Complex Query Answering Really Complex?](https://mlsanity.com/paper/2410.12537/) (2024)
- [Intention Knowledge Graph Construction for User Intention Relation Modeling](https://mlsanity.com/paper/2412.11500/) (2024)
- [Enhancing Transformers for Generalizable First-Order Logical Entailment](https://mlsanity.com/paper/2501.00759/) (2025)
- [A Neuro-Symbolic Framework for Answering Graph Pattern Queries in Knowledge Graphs](https://mlsanity.com/paper/2310.04598/) (2023)
- [Learning Federated Neural Graph Databases for Answering Complex Queries from Distributed Knowledge Graphs](https://mlsanity.com/paper/2402.14609/) (2024)
- [Demystifying Higher-Order Graph Neural Networks](https://mlsanity.com/paper/2406.12841/) (2024)
- [Adaptive Stochastic Weight Averaging](https://mlsanity.com/paper/2406.19092/) (2024)
- [The Discovery Engine: A Framework for AI-Driven Synthesis and Navigation of Scientific Knowledge Landscapes](https://mlsanity.com/paper/2505.17500/) (2025)
- [IntelliGraphs: Datasets for Benchmarking Knowledge Graph Generation](https://mlsanity.com/paper/2307.06698/) (2023)
- [Extending Complex Logical Queries on Uncertain Knowledge Graphs](https://mlsanity.com/paper/2403.01508/) (2024)
- [RConE: Rough Cone Embedding for Multi-Hop Logical Query Answering on Multi-Modal Knowledge Graphs](https://mlsanity.com/paper/2408.11526/) (2024)
- [Transformers for Complex Query Answering over Knowledge Hypergraphs](https://mlsanity.com/paper/2504.16537/) (2025)
- [NGDB-Zoo: Towards Efficient and Scalable Neural Graph Databases Training](https://mlsanity.com/paper/2602.21597/) (2026)
- [KGPFN: Unlocking the Potential of Knowledge Graph Foundation Model via In-Context Learning](https://mlsanity.com/paper/2605.14907/) (2026)
- [Pathformer: Recursive Path Query Encoding for Complex Logical Query Answering](https://mlsanity.com/paper/2406.14880/) (2024)
- [Complex Logical Query Answering by Calibrating Knowledge Graph Completion Models](https://mlsanity.com/paper/2410.07165/) (2024)
- [Learning Representations for Reasoning: Generalizing Across Diverse Structures](https://mlsanity.com/paper/2410.13018/) (2024)
- [Graph Neural Networks on Graph Databases](https://mlsanity.com/paper/2411.11375/) (2024)
- [Efficient and Scalable Neural Symbolic Search for Knowledge Graph Complex Query Answering](https://mlsanity.com/paper/2505.08155/) (2025)
- [Approximate Answering of Graph Queries](https://mlsanity.com/paper/2308.06585/) (2023)
- [Efficient Parallel Multi-Hop Reasoning: A Scalable Approach for Knowledge Graph Analysis](https://mlsanity.com/paper/2406.07727/) (2024)
- [MPRM: A Markov Path-based Rule Miner for Efficient and Interpretable Knowledge Graph Reasoning](https://mlsanity.com/paper/2505.12329/) (2025)

## Abstract (arXiv)

Complex logical query answering (CLQA) is a recently emerged task of graph machine learning that goes beyond simple one-hop link prediction and solves a far more complex task of multi-hop logical reasoning over massive, potentially incomplete graphs in a latent space. The task received a significant traction in the community; numerous works expanded the field along theoretical and practical axes to tackle different types of complex queries and graph modalities with efficient systems. In this paper, we provide a holistic survey of CLQA with a detailed taxonomy studying the field from multiple angles, including graph types (modality, reasoning domain, background semantics), modeling aspects (encoder, processor, decoder), supported queries (operators, patterns, projected variables), datasets, evaluation metrics, and applications. Refining the CLQA task, we introduce the concept of Neural Graph Databases (NGDBs). Extending the idea of graph databases (graph DBs), NGDB consists of a Neural Graph Storage and a Neural Graph Engine. Inside Neural Graph Storage, we design a graph store, a feature store, and further embed information in a latent embedding store using an encoder. Given a query, Neural Query Engine learns how to perform query planning and execution in order to efficiently retrieve the correct results by interacting with the Neural Graph Storage. Compared with traditional graph DBs, NGDBs allow for a flexible and unified modeling of features in diverse modalities using the embedding store. Moreover, when the graph is incomplete, they can provide robust retrieval of answers which a normal graph DB cannot recover. Finally, we point out promising directions, unsolved problems and applications of NGDB for future research.