摘要
回答复杂逻辑查询在不完整的知识图谱上是一项具有挑战性的任务，已受到广泛研究。基于嵌入的方法需要对复杂查询进行训练，但无法很好地泛化到分布外的查询结构。近期的研究将这一任务框架为端到端优化问题，仅需一个预训练的链接预测器。然而，由于组合搜索空间呈指数级增长，最优解只能近似求得，这限制了最终的准确性。在本工作中，我们提出了一种称为QTO（Query Computation Tree Optimization）的方法，能够高效地找到精确的最优解。QTO通过在树状计算图（即查询计算树）上进行前向-后向传播来寻找最优解。特别地，QTO利用查询计算树中编码的独立性来减少搜索空间，在优化过程中仅涉及局部计算。实验结果表明，在3个数据集上，QTO在复杂查询回答任务中取得了最先进的性能，平均比之前的最佳结果提高了22%。此外，QTO能够以超过90%的准确率解释查询中每个一跳原子的中间解。本文代码位于https://github.com/bys0318/QTO。