Counting Still Counts: Understanding Neural Complex Query Answering Through Query Relaxation
This challenges assumptions about neural reasoning capabilities in knowledge graph query answering and calls for stronger non-neural baselines, potentially impacting researchers in knowledge representation and reasoning.
The authors examined whether neural complex query answering models truly learn generalized reasoning patterns beyond explicit knowledge graph structure by comparing them with a training-free query relaxation approach that counts paths from relaxed constraints. They found neural models performed similarly to the relaxation method without consistent superiority, their answer sets had little overlap, and combining both approaches improved performance.
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.