Answering Complex Logical Queries on Knowledge Graphs via Query Computation Tree Optimization

Yushi BaiXin LvJuanzi LiLei Hou

article2023ICML53 citations

Proposes a forward-backward propagation algorithm over query computation trees to efficiently find exact optimal entity assignments for complex logical queries on incomplete knowledge graphs without requiring complex query training.

Listen

Real-world knowledge graphs are widely used to represent structured information, but they frequently suffer from incompleteness, making complex logical query answering difficult. Standard embedding approaches require costly training on millions of complex queries and struggle to generalize to unseen query structures. Recent optimization methods avoid complex query training by utilizing pretrained single-hop link predictors; however, because the combinatorial search space grows exponentially with the number of variables, they rely on heuristic approximations that degrade accuracy and provide limited interpretability for intermediate reasoning steps.

The main objective of the article is to introduce and evaluate Query Computation Tree Optimization (QTO), an optimization-based framework designed to find the exact, theoretically optimal answers to complex first-order logic queries without requiring complex query training.

The evaluated approach represents logical queries as tree-structured computation graphs and leverages structural independence to reduce the search space. QTO executes a forward-propagation pass to compute optimal subquery truth values from leaf entities to the root answer variable, followed by a backward-propagation pass that determines the exact entity assignments for all intermediate variables. The authors evaluated QTO across three benchmark datasets (FB15k, FB15k-237, and NELL995) spanning 14 query types, including existential positive queries and queries with negation, comparing it against established neural and optimization baselines.

The key findings demonstrate significant performance gains and enhanced reasoning capabilities. QTO outperformed the previous state-of-the-art method by an average of 22% overall, with relative gains of 13.5% on existential positive queries, 21.8% on out-of-distribution structures, and 37.5% on queries containing negation. Against optimization-based baselines, QTO achieved an average improvement of 30.8%. Furthermore, QTO provides strong interpretability, correctly assigning intermediate variables with over 90% accuracy for its top-ranked predictions. The framework is also mathematically guaranteed to achieve 100% accuracy on easy queries where reasoning paths exist in the graph, and it significantly reduced error in predicting answer set sizes compared to baseline models.

These results demonstrate that complex reasoning on knowledge bases can be decoupled from query-specific model training. Organizations can deploy existing, high-performing single-hop link predictors directly into multi-hop logical reasoning workflows without extensive retraining. This decoupling lowers computational costs, enhances system transparency through verifiable intermediate reasoning steps, and ensures robust generalization over longer reasoning paths.

Organizations implementing complex graph querying should consider QTO-style tree optimization frameworks to improve query accuracy and interpretability while reducing model retraining pipelines. As next steps, technical teams should explore adaptive calibration techniques for transforming single-hop predictor scores into probabilities and test subgraph decomposition techniques for very large enterprise graphs.

The primary limitations include memory and pre-computation scaling overheads when generating dense adjacency matrices for large-scale graphs, as well as a structural restriction that limits the algorithm to tree-like query topologies, excluding cyclic graph queries or queries with multiple answer variables. Confidence in the reported results is high, supported by rigorous theoretical optimality proofs and consistent empirical outperformance across standard benchmarks.

Institute for Artificial Intelligence Tsinghua University University of Cambridge complex queries knowledge graphs multihop complex logical queries query computation tree optimization knowledge graphs

arXiv: 2212.09567 bys0318/QTO

Paper: Neural-Symbolic Models for Logical Queries on Knowledge Graphs, Zhaocheng Zhu et al. (2022). Read this earlier neural-symbolic framework for complex knowledge-graph queries to see the query-execution approach that QTO advances beyond with exact tree optimization.
Paper: Embedding Entities and Relations for Learning and Inference in Knowledge Bases, Bishan Yang et al. (2014). Its unified treatment of knowledge-graph embeddings and link prediction clarifies the single-hop predictors QTO reuses as the basis for complex-query reasoning.

No sufficiently relevant recommendations were found.

Cover for Answering Complex Logical Queries on Knowledge Graphs via Query Computation Tree Optimization

Abstract

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 may not 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.

1 Introduction
2 Related Work
3 Methodology
3.1 Preliminaries
3.2 Query Computation Tree Optimization
3.3 Discussion
4 Experiments
4.1 Experimental Setup
4.2 Results on Complex Query Answering
4.3 Interpretability Study
4.4 Predicting the Cardinality of Answer Sets
4.5 Analyses on Reasoning Skills and Efficiency
5 Conclusion
References
A Conversion Between FOL Expression and Query Computation Tree
B Proof of : Equivalence of Optimization on the Query Computation Tree
C Query Computation Tree Optimization Algorithm
D Proof of : Optimality of QTO
E Discussions on Neural Adjacency Matrix
F Experiment Details
F.1 Dataset Statistics
F.2 Query Structures
F.3 Implementation Details
G More Experimental Results
G.1 Hits@1 on Complex Query Answering
G.2 More Plots on Complex Query Answering w.r.t. 1-hop Query Answering
G.3 Hyperparameter Analysis
G.4 QTO with Different One-hop Link Predictors
G.5 More Results on Interpretation Study
G.6 Case Study on QTO’s Interpretation
G.7 More Results on Cardinality Prediction

Knowls

Knowl 1 — Tree-structured computation for complex logical queries
model/method
QTO represents a first-order logic (FOL) query as a rooted computation tree. The answer variable is the root, constant entities are leaves, and edges directed from child to parent represent relational projection or anti-relational projection; internal nodes combine branches by intersection or union. The method applies when the query’s dependency graph is a tree, so subqueries rooted at different branches can be optimized locally. To construct the tree from a disjunctive-normal-form query, the paper generates a dependency graph from its atoms, merges compatible same-relation branches from different disjuncts using distributivity, and separates variables at one-to-many intersection or union structures. This representation supports QTO’s exact optimization for tree-shaped queries, but not cyclic query structures.
Knowl 2 — Fuzzy truth-value objective for query answering
equation
For a query with answer candidate $x$ , existential variables collected in assignment $\mathbf z$ , and disjunctive-normal-form clauses $C_1,\ldots,C_L$ , QTO maximizes the query’s fuzzy truth score over assignments. Each atom score $s_a$ lies in $[0,1]$ ; a negated atom has score one minus the score of its positive relation atom. The product t-norm models conjunction, and its associated t-conorm models disjunction:
$S_q(x)=\max_{\mathbf z\in V^N}\left[\bigoplus_{\ell=1}^{L}\ \bigotimes_{a\in C_\ell}s_a(x,\mathbf z)\right], \qquad a\otimes b=ab,\qquad a\oplus b=1-(1-a)(1-b).$
Here $V$ is the finite set of knowledge-graph entities, $N$ is the number of existential variables, and $S_q(x)$ is the best truth score for answer candidate $x$ . The predicted answer is an entity with maximum $S_q(x)$ . Atomic scores are supplied by a pretrained knowledge-graph embedding (KGE) link predictor after calibration.
Knowl 3 — Calibration of KGE scores into a neural adjacency matrix
model/method
QTO converts KGE scores into relation-specific entity-to-entity scores $M_r[h,t]\in[0,1]$ , where $h,t\in V$ are the head and tail entities and $r$ is a relation. For a KGE score function $f_r(h,t)$ , let $N_t(h,r)$ be the larger of 1 and the number of training-graph tail entities linked from $h$ by $r$ . QTO scales the softmax probability over all candidate tails by this count, then caps non-training edges below 1:
$\widehat r(h,t)=N_t(h,r)\frac{\exp(f_r(h,t))}{\sum_{e\in V}\exp(f_r(h,e))},\qquad M_r[h,t]=\begin{cases} 1,&(h,r,t)\in E_{\mathrm{train}},\\ \min\{\widehat r(h,t),1-\delta\},&\text{otherwise}, \end{cases}$
where $E_{\mathrm{train}}$ is the set of training facts and the paper uses $\delta=0.0001$ . Thus known facts receive score 1, while predicted links remain strictly below 1. The matrix can be sparsified by setting sufficiently small entries to zero.
Knowl 4 — Forward dynamic programming on the query tree
algorithm
For each tree node $v$ , QTO computes $T_v(e)$ , the maximum truth score of the subtree rooted at $v$ conditional on assigning entity $e\in V$ to that node. The calculation proceeds from leaves to the root. Let $u_i$ be the child nodes of an intersection or union node, and let $u$ be the child of a projection node. For a relational edge from child to parent labeled by $r$ , use $M_r[x,e]$ ; for an anti-relational edge, use $1-M_r[x,e]$ .
$T_v(e)= \begin{cases} \prod_i T_{u_i}(e),&v\text{ combines children by intersection},\\ 1-\prod_i(1-T_{u_i}(e)),&v\text{ combines children by union},\\ \max_{x\in V}T_u(x)M_r[x,e],&v\text{ is a relational projection},\\ \max_{x\in V}T_u(x)(1-M_r[x,e]),&v\text{ is an anti-relational projection}. \end{cases}$
If the child of a projection is a constant entity $c$ , its output vector is the row $M_r[c,:]$ ; for an anti-relational projection it is $1-M_r[c,:]$ . Products over children are elementwise. The root vector contains the maximum query score for every possible answer entity, so its largest entry gives the predicted answer and the maximum truth value.
Knowl 5 — Backward recovery of intermediate entity assignments
algorithm
After the forward pass, QTO recovers an optimal assignment for the intermediate variables by traversing from a chosen root answer entity $e_t$ toward the leaves. At intersection and union nodes, each child copy of the same variable receives the parent’s entity assignment. At a relational projection, the child entity is selected by
$x^*=\arg\max_{x\in V}T_u(x)M_r[x,e_t];$
at an anti-relational projection it is selected by
$x^*=\arg\max_{x\in V}T_u(x)(1-M_r[x,e_t]).$
The procedure then recurses into the child subtree using $x^*$ as its assigned entity. Ties may be resolved by choosing any maximizing entity. This produces a set of most-likely intermediate assignments explaining the answer, and it can be run for any chosen answer entity, not only QTO’s top-ranked prediction.
Knowl 6 — Optimality guarantee and exact recovery of easy answers
theoretical result
For a query whose computation graph is a tree, the forward recursion computes the maximum truth value over all entity assignments, and the backward traversal returns assignments attaining that value. The guarantee holds under the paper’s product t-norm and associated t-conorm, with the relational and anti-relational scores supplied by the neural adjacency matrices. In particular, an easy answer—one derivable using existing knowledge-graph links along the required paths—has score 1 and is recovered by QTO. Because every non-training-edge score is capped at $1-\delta$ for $\delta>0$ , answers requiring a predicted missing link have score strictly below 1 under the paper’s formulation. Thus entries of the root score vector equal to 1 identify the easy answers.
Knowl 7 — Computational and storage costs
model/method
With $|V|$ entities, a direct relational or anti-relational projection in the forward pass costs $O(|V|^2)$ , and a backward assignment step costs $O(|V|)$ . For a query with $N'$ projection edges, sparsity can reduce forward projection work: if the child score vector has $s$ nonzero entries after thresholding, the projection can be computed in $O(|V|s)$ , giving total query time $O(N'|V|\max s)$ when the largest relevant support size is used. The conceptual neural adjacency matrices contain $|R||V|^2$ scores for $|R|$ relations, so QTO stores them sparsely by removing entries below a threshold. Lower thresholds retain more information but increase memory use and can improve accuracy; the threshold therefore trades storage against performance.

Knowl 8 — Complex-query answering results across three knowledge graphs

data/table

The comparison reports test mean reciprocal rank (MRR, %) on hard answers, with easy and other known answers filtered during ranking. The averages are over existential-positive FOL queries (avgp), out-of-distribution existential-positive query structures (avgOOD), and queries with negation (avgn). QTO uses a pretrained KGE predictor without training on complex queries; GNN-QE is the strongest reported comparison on these averages. QTO scores higher on all three averages in each dataset, with especially large gains on out-of-distribution and negated queries.

Dataset	Method	avgp	avgOOD	avgn
FB15k	GNN-QE	72.8	68.9	38.6
FB15k	QTO	74.0	71.8	49.2
FB15k-237	GNN-QE	26.8	19.9	10.2
FB15k-237	QTO	33.5	27.6	15.5
NELL995	GNN-QE	28.9	19.6	9.7
NELL995	QTO	32.9	24.0	12.9

The evaluation used the standard 14 query structures on FB15k, FB15k-237, and NELL995. For the reported out-of-distribution average, the comparison methods had been trained on only five query structures; QTO did not require complex-query training.

Knowl 9 — Accuracy of intermediate-variable explanations

empirical result

On FB15k-237, the authors evaluated whether QTO’s backward assignments make the full FOL query true in the complete graph. The following percentages give explanation accuracy when the answer variable is set to a true answer ranked within the indicated Hits@1 set, or when averaged over all true answers (“All”). Explanations for top-ranked answers are valid more often than explanations averaged over all true answers; Hits@1 accuracy exceeds 90% for six of the eight listed query structures.

	2p	3p	pi	ip	up	inp	pin	pni
Hits@1	88.6	85.1	93.9	91.3	90.8	81.9	90.3	93.5
All	65.7	56.7	84.3	78.7	64.8	52.7	68.5	94.3

The assignments were checked against the full-graph facts, and the reported query types exclude structures whose explanations are trivially true whenever the answer is true. The result demonstrates that the recovered intermediate entities can often provide a valid explanation, particularly for high-ranked answers.

Knowl 10 — Scope and scalability limitations
limitation
QTO requires a tree-shaped query computation graph and supports one answer variable; it does not handle cyclic query structures or queries with multiple answer variables. It also depends on precomputing relation-specific neural adjacency matrices, which can be costly as the knowledge graph grows. On one RTX 3090 GPU, matrix precomputation took 40 minutes for FB15k, 7 minutes for FB15k-237, and 7 hours for NELL995. The method therefore trades query-time local optimization for potentially substantial preprocessing and storage requirements.

Coverage note — The auxiliary answer-set cardinality-prediction evaluation and detailed KGE-backbone and hyperparameter studies are omitted because they are secondary analyses rather than load-bearing parts of QTO’s optimization method, guarantees, and core evaluations.

References

1.Arakelyan, E., Daza, D., Minervini, P., and Cochez, M. Complex query answering with neural link predictors. In International Conference on Learning Representations, 2021.
2.Bai, Y., Ying, Z., Ren, H., and Leskovec, J. Modeling heterogeneous hierarchies with relation-specific hyperbolic cones. Advances in Neural Information Processing Systems, 34:12316–12327, 2021.
3.Bai, Y., Lv, X., Li, J., Hou, L., Qu, Y., Dai, Z., and Xiong, F. SQUIRE: A sequence-to-sequence framework for multi-hop knowledge graph reasoning. In EMNLP, 2022.
4.Balazevič, I., Allen, C., and Hospedales, T. TuckER: Tensor factorization for knowledge graph completion. In Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP), pp. 5185–5194, 2019.
5.Bordes, A., Usunier, N., Garcia-Duran, A., Weston, J., and Yakhnenko, O. Translating embeddings for modeling multi-relational data. Advances in neural information processing systems, 26, 2013.
6.Chami, I., Wolf, A., Juan, D.-C., Sala, F., Ravi, S., and Re, C. Low-dimensional hyperbolic knowledge graph embeddings. In ACL, 2020.
7.Chen, X., Hu, Z., and Sun, Y. Fuzzy logic based logical query answering on knowledge graphs. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pp. 3939–3948, 2022.
8.Chen, Y., Minervini, P., Riedel, S., and Stenetorp, P. Relation prediction as an auxiliary training objective for improving multi-relational graph representations. In 3rd Conference on Automated Knowledge Base Construction, 2021.
9.Choudhary, N., Rao, N., Katariya, S., Subbian, K., and Reddy, C. K. Self-supervised hyperboloid representations from logical queries over knowledge graphs. In Proceedings of the Web Conference 2021, pp. 1373–1384, 2021.
10.Dalvi, N. and Suciu, D. Efficient query evaluation on probabilistic databases. The VLDB Journal, 16(4):523–544, 2007.
11.Das, R., Dhuliawala, S., Zaheer, M., Vilnis, L., Durugkar, I., Krishnamurthy, A., Smola, A., and McCallum, A. Go for a walk and arrive at the answer: reasoning over paths in knowledge bases using reinforcement learning. In International Conference on Learning Representations, 2018.
12.Dettmers, T., Minervini, P., Stenetorp, P., and Riedel, S. Convolutional 2d knowledge graph embeddings. In Proceedings of the AAAI conference on artificial intelligence, volume 32, 2018.
13.Guu, K., Miller, J., and Liang, P. Traversing knowledge graphs in vector space. In Proceedings of the 2015 Conference on Empirical Methods in Natural Language Processing, pp. 318–327, 2015.
14.Hajek, P. Metamathematics of fuzzy logic, volume 4. Springer Science & Business Media, 2013.
15.Hamilton, W., Bajaj, P., Zitnik, M., Jurafsky, D., and Leskovec, J. Embedding logical queries on knowledge graphs. Advances in neural information processing systems, 31, 2018.
16.Klement, E. P., Mesiar, R., and Pap, E. Triangular norms, volume 8. Springer Science & Business Media, 2013.
17.Klir, G. and Yuan, B. Fuzzy sets and fuzzy logic, volume 4. Prentice hall New Jersey, 1995.
18.Lacroix, T., Usunier, N., and Obozinski, G. Canonical tensor decomposition for knowledge base completion. In International Conference on Machine Learning, pp. 2863–2872. PMLR, 2018.
19.Lin, X. V., Socher, R., and Xiong, C. Multi-hop knowledge graph reasoning with reward shaping. In Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing, pp. 3243–3253, 2018.
20.Lv, X., Gu, Y., Han, X., Hou, L., Li, J., and Liu, Z. Adapting meta knowledge graph information for multi-hop reasoning over few-shot relations. In Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP), pp. 3376–3381, 2019.
21.Meilicke, C., Chekol, M. W., Ruffinelli, D., and Stuckenschmidt, H. Anytime bottom-up rule learning for knowledge graph completion. In Proceedings of the 28th International Joint Conference on Artificial Intelligence, pp. 3137–3143, 2019.
22.Pearl, J. Reverend bayes on inference engines: A distributed hierarchical approach. In AAAI, 1982.
23.Pearl, J. Causality. Cambridge university press, 2009.
24.Ren, H. and Leskovec, J. Beta embeddings for multi-hop logical reasoning in knowledge graphs. Advances in Neural Information Processing Systems, 33:19716–19726, 2020.
25.Ren, H., Hu, W., and Leskovec, J. Query2box: reasoning over knowledge graphs in vector space using box embeddings. In International Conference on Learning Representations, 2019.
26.Safavi, T., Koutra, D., and Meij, E. Evaluating the calibration of knowledge graph embeddings for trustworthy link prediction. In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP), pp. 8308–8321, 2020.
27.Schlichtkrull, M., Kipf, T. N., Bloem, P., Berg, R. v. d., Titov, I., and Welling, M. Modeling relational data with graph convolutional networks. In European semantic web conference, pp. 593–607. Springer, 2018.
28.Sun, Z., Deng, Z.-H., Nie, J.-Y., and Tang, J. RotatE: Knowledge graph embedding by relational rotation in complex space. In International Conference on Learning Representations, 2018.
29.Toutanova, K. and Chen, D. Observed versus latent features for knowledge base and text inference. In Proceedings of the 3rd workshop on continuous vector space models and their compositionality, pp. 57–66, 2015.
30.Trouillon, T., Welbl, J., Riedel, S., Gaussier, E., and Bouchard, G. Complex embeddings for simple link prediction. In ICML, 2016.
31.Xiong, W., Hoang, T., and Wang, W. Y. DeepPath: A reinforcement learning method for knowledge graph reasoning. In Proceedings of the 2017 Conference on Empirical Methods in Natural Language Processing, pp. 564–573, 2017.
32.Yang, F., Yang, Z., and Cohen, W. W. Differentiable learning of logical rules for knowledge base reasoning. Advances in neural information processing systems, 30, 2017.
33.Zhang, Z., Wang, J., Chen, J., Ji, S., and Wu, F. Cone: Cone embeddings for multi-hop reasoning over knowledge graphs. Advances in Neural Information Processing Systems, 34:19172–19183, 2021.
34.Zhu, Z., Zhang, Z., Xhonneux, L.-P., and Tang, J. Neural bellman-ford networks: A general graph neural network framework for link prediction. Advances in Neural Information Processing Systems, 34:29476–29490, 2021.
35.Zhu, Z., Galkin, M., Zhang, Z., and Tang, J. Neural-symbolic models for logical queries on knowledge graphs. In Proceedings of the 39th International Conference on Machine Learning, volume 162, pp. 27454–27478, 2022.
36.Zou, L., Mo, J., Chen, L., Ozsu, M. T., and Zhao, D. gStore: answering SPARQL queries via subgraph matching. Proceedings of the VLDB Endowment, 4(8):482–493, 2011.

Citation

MLA

Bai, Y., et al. “Answering Complex Logical Queries on Knowledge Graphs via Query Computation Tree Optimization”. International Conference on Machine Learning, vol. 202, 2023, pp. 1472–91, https://proceedings.mlr.press/v202/bai23b.html.

APA

Bai, Y., Lv, X., Li, J., & Hou, L. (2023). Answering Complex Logical Queries on Knowledge Graphs via Query Computation Tree Optimization. International Conference on Machine Learning, 202, 1472–1491. https://proceedings.mlr.press/v202/bai23b.html

Chicago

Bai, Y., X. Lv, J. Li, and L. Hou. 2023. “Answering Complex Logical Queries on Knowledge Graphs via Query Computation Tree Optimization”. International Conference on Machine Learning 202: 1472–91. https://proceedings.mlr.press/v202/bai23b.html.

Harvard

Bai, Y. et al. (2023) “Answering Complex Logical Queries on Knowledge Graphs via Query Computation Tree Optimization”, International Conference on Machine Learning. PMLR, pp. 1472–1491. Available at: https://proceedings.mlr.press/v202/bai23b.html.

Vancouver

1. Bai Y, Lv X, Li J, Hou L (2023) Answering Complex Logical Queries on Knowledge Graphs via Query Computation Tree Optimization. In: International Conference on Machine Learning. PMLR, pp 1472–1491

BibTeX

@InProceedings{pmlr-v202-bai23b,
  title = 	 {Answering Complex Logical Queries on Knowledge Graphs via Query Computation Tree Optimization},
  author =       {Bai, Yushi and Lv, Xin and Li, Juanzi and Hou, Lei},
  booktitle = 	 {Proceedings of the 40th International Conference on Machine Learning},
  pages = 	 {1472--1491},
  year = 	 {2023},
  editor = 	 {Krause, Andreas and Brunskill, Emma and Cho, Kyunghyun and Engelhardt, Barbara and Sabato, Sivan and Scarlett, Jonathan},
  volume = 	 {202},
  series = 	 {Proceedings of Machine Learning Research},
  month = 	 {23--29 Jul},
  publisher =    {PMLR},
  pdf = 	 {https://proceedings.mlr.press/v202/bai23b/bai23b.pdf},
  url = 	 {https://proceedings.mlr.press/v202/bai23b.html},
  abstract = 	 {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 may not 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.}
}

Metadata:DOI registry

Source Code

This paper has an official code repository available. Click below to access the source code.

View Repository

Access the Paper

This paper is available from its original source. Click below to access the PDF.

Open PDF

License: https://creativecommons.org/licenses/by/4.0/

Answering Complex Logical Queries on Knowledge Graphs via Query Computation Tree Optimization

Abstract

Topics

Keywords

Table of Contents

Knowls

Knowl 1 — Tree-structured computation for complex logical queries

Knowl 2 — Fuzzy truth-value objective for query answering

Knowl 3 — Calibration of KGE scores into a neural adjacency matrix

Knowl 4 — Forward dynamic programming on the query tree

Knowl 5 — Backward recovery of intermediate entity assignments

Knowl 6 — Optimality guarantee and exact recovery of easy answers

Knowl 7 — Computational and storage costs