# Counting Still Counts: Understanding Neural Complex Query Answering Through Query Relaxation

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 18 of its 40 references that are in the map.
- First posted on arXiv 27 Nov 2025.

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

- [Link Prediction Based on Graph Neural Networks](https://mlsanity.com/paper/1802.09691/) (2018)
- [Knowledge Graphs](https://mlsanity.com/paper/2003.02320/) (2020)
- [DeepPath: A Reinforcement Learning Method for Knowledge Graph Reasoning](https://mlsanity.com/paper/1707.06690/) (2017)
- [A Review of Relational Machine Learning for Knowledge Graphs](https://mlsanity.com/paper/1503.00759/) (2015)
- [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)
- [ConE: Cone Embeddings for Multi-Hop Reasoning over Knowledge Graphs](https://mlsanity.com/paper/2110.13715/) (2021)
- [A Comprehensive Survey on Automatic Knowledge Graph Construction](https://mlsanity.com/paper/2302.05019/) (2023)
- [Neural-Symbolic Models for Logical Queries on Knowledge Graphs](https://mlsanity.com/paper/2205.10128/) (2022)
- [Self-Supervised Hyperboloid Representations from Logical Queries over Knowledge Graphs](https://mlsanity.com/paper/2012.13023/) (2020)
- [Answering Complex Logical Queries on Knowledge Graphs via Query Computation Tree Optimization](https://mlsanity.com/paper/2212.09567/) (2022)
- [Query Embedding on Hyper-relational Knowledge Graphs](https://mlsanity.com/paper/2106.08166/) (2021)
- [A Foundation Model for Zero-shot Logical Query Reasoning](https://mlsanity.com/paper/2404.07198/) (2024)
- [Adapting Neural Link Predictors for Data-Efficient Complex Query Answering](https://mlsanity.com/paper/2301.12313/) (2023)
- [Is Complex Query Answering Really Complex?](https://mlsanity.com/paper/2410.12537/) (2024)
- [Question-Answer Sentence Graph for Joint Modeling Answer Selection](https://mlsanity.com/paper/2203.03549/) (2022)

## Abstract (arXiv)

Neural methods for Complex Query Answering (CQA) over knowledge graphs (KGs) are widely believed to learn patterns that generalize beyond explicit graph structure, allowing them to infer answers that are unreachable through symbolic query processing. In this work, we critically examine this assumption through a systematic analysis comparing neural CQA models with an alternative, training-free query relaxation strategy that retrieves possible answers by relaxing query constraints and counting resulting paths. Across multiple datasets and query structures, we find several cases where neural and relaxation-based approaches perform similarly, with no neural model consistently outperforming the latter. Moreover, a similarity analysis reveals that their retrieved answers exhibit little overlap, and that combining their outputs consistently improves performance. These results call for a re-evaluation of progress in neural query answering: despite their complexity, current models fail to subsume the reasoning patterns captured by query relaxation. Our findings highlight the importance of stronger non-neural baselines and suggest that future neural approaches could benefit from incorporating principles of query relaxation.