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

A new research paper published on arXiv critically examines the prevailing assumption that neural methods for Complex Query Answering (CQA) over knowledge graphs inherently outperform symbolic approaches by learning generalized patterns. The authors, including Yannick Brunink and Daniel Daza, compare state-of-the-art neural CQA models against a training-free query relaxation strategy that retrieves answers by relaxing constraints and counting resulting paths. Their systematic analysis across multiple datasets reveals that neural models do not consistently surpass the relaxation-based approach. Furthermore, the study finds minimal overlap in the answers retrieved by both methods, suggesting they capture distinct reasoning patterns. Combining their outputs consistently improves performance, indicating that current neural models fail to subsume the logic captured by query relaxation. These findings challenge the perceived progress in neural query answering, emphasizing the need for stronger non-neural baselines and suggesting that future neural architectures should incorporate principles of query relaxation to enhance effectiveness and robustness in knowledge graph reasoning tasks.