论文标题
通过查询计算树在知识图上回答复杂的逻辑查询
Answering Complex Logical Queries on Knowledge Graphs via Query Computation Tree Optimization
论文作者
论文摘要
在不完整的知识图上回答复杂的逻辑查询是一项具有挑战性的任务，并且已经得到了广泛的研究。基于嵌入的方法需要对复杂查询进行培训，并且不能很好地概括为分布的查询结构。最近的工作将这项任务视为端到端优化问题，仅需要验证的链接预测指标。但是，由于呈指数较大的组合搜索空间，最佳解决方案只能近似，从而限制了最终精度。在这项工作中，我们提出了QTO（查询计算树优化），可以有效地找到确切的最佳解决方案。 QTO通过在类似树的计算图上的前向繁殖（即查询计算树）找到最佳解决方案。特别是，QTO利用在查询计算树中编码的独立性来减少搜索空间，在优化过程中仅涉及局部计算。 3个数据集的实验表明，QTO在复杂的查询答案中获得最先进的性能，表现平均比以前的最佳结果22％。此外，QTO可以以超过90％的精度来解释查询中每个单跳原子的中间解决方案。我们论文的代码在https://github.com/bys0318/qto上。
Answering complex logical queries on incomplete knowledge graphs is a challenging task, and has been widely studied. Embedding-based methods require training on complex queries, and cannot generalize well to out-of-distribution query structures. Recent work frames this task as an end-to-end optimization problem, and it only requires a pretrained link predictor. However, due to the exponentially large combinatorial search space, the optimal solution can only be approximated, limiting the final accuracy. In this work, we propose QTO (Query Computation Tree Optimization) that can efficiently find the exact optimal solution. QTO finds the optimal solution by a forward-backward propagation on the tree-like computation graph, i.e., query computation tree. In particular, QTO utilizes the independence encoded in the query computation tree to reduce the search space, where only local computations are involved during the optimization procedure. Experiments on 3 datasets show that QTO obtains state-of-the-art performance on complex query answering, outperforming previous best results by an average of 22%. Moreover, QTO can interpret the intermediate solutions for each of the one-hop atoms in the query with over 90% accuracy. The code of our paper is at https://github.com/bys0318/QTO.
