Source-linked AI summary
Complex Query Answering with Neural Link Predictors
Erik Arakelyan, Daniel Daza, Pasquale Minervini, Michael Cochez
TL;DR
Complex queries over incomplete Knowledge Graphs remain difficult because neural link predictors are designed mainly for missing individual edges. The paper introduces CQD, which compiles logical queries into differentiable objectives scored by a pretrained link predictor and solves variable assignments continuously or combinatorially; it reports more accurate results than state-of-the-art methods with orders of magnitude less training data.
Problem
Answering queries with conjunction, disjunction, and existential quantification while accounting for missing edges remains an open challenge beyond neural link prediction.
Method
CQD combines neural link-prediction scores for query atoms with t-norm and t-conorm aggregation, then uses gradient-based optimisation or combinatorial beam search for variable assignments.
Results
CQD achieves significantly better or equivalent predictive accuracy across complex queries, out-of-distribution generalisation from simple-query training, and more explainable answers than comparison methods.
Takeaways & Limitations
Complex query answering can generalise from a neural link predictor trained on simple queries while exposing intermediate sub-query results and variable assignments as explanations.
Abstract
from arXiv · showhide
Neural link predictors are immensely useful for identifying missing edges in large scale Knowledge Graphs. However, it is still not clear how to use these models for answering more complex queries that arise in a number of domains, such as queries using logical conjunctions ($\land$), disjunctions ($\lor$) and existential quantifiers ($\exists$), while accounting for missing edges. In this work, we propose a framework for efficiently answering complex queries on incomplete Knowledge Graphs. We translate each query into an end-to-end differentiable objective, where the truth value of each atom is computed by a pre-trained neural link predictor. We then analyse two solutions to the optimisation problem, including gradient-based and combinatorial search. In our experiments, the proposed approach produces more accurate results than state-of-the-art methods -- black-box neural models trained on millions of generated queries -- without the need of training on a large and diverse set of complex queries. Using orders of magnitude less training data, we obtain relative improvements ranging from 8% up to 40% in Hits@3 across different knowledge graphs containing factual information. Finally, we demonstrate that it is possible to explain the outcome of our model in terms of the intermediate solutions identified for each of the complex query atoms. All our source code and datasets are available online, at https://github.com/uclnlp/cqd.
1 INTRODUCTION
Complex queries over incomplete Knowledge Graphs require reasoning across multiple potentially missing edges, beyond standard neural link prediction. The paper proposes a differentiable framework that combines neural atom scores with continuous or combinatorial optimisation and reports stronger accuracy with far less training data.
- Complex query answering must handle multiple potentially unobserved edges, entities, and variables rather than only missing individual edges.
- Plain sub-graph matching cannot capture semantic similarities or missing facts, while materialising all missing entries has intractable space and time requirements.
- The framework compiles each query into an end-to-end differentiable function, scoring atoms with a neural link predictor and solving variable assignments continuously or combinatorially.
- The approach generalises from 1-hop training to up to 8 complex query structures, outperforming state-of-the-art models with orders of magnitude less training data.
- CQD provides predictive accuracy, out-of-distribution generalisation, and explanations through intermediate sub-query results and variable assignments.
2 EXISTENTIAL POSITIVE FIRST-ORDER LOGICAL QUERIES
The paper formalises existential positive first-order queries over Knowledge Graphs using existential quantification, conjunction, and disjunction. Queries are represented through dependency graphs and transformed into conjunctive sub-queries for answering.
- A Knowledge Graph is represented as subject-predicate-object triples, equivalently atomic formulas over entities and binary relation predicates.
- Conjunctive queries use existential quantification and conjunction to combine atoms containing anchors, a target variable, and bound variables.
- The answer set contains entities that make the query true when substituted for its target variable.
- Valid conjunctive-query dependency graphs are directed acyclic graphs with anchors as source nodes and the target as the unique sink.
- Existential positive first-order queries additionally allow disjunction and are transformed into disjunctive normal form, a disjunction of conjunctive queries.
- For disjunctive queries, scores for conjunctive sub-queries are produced for each entity and aggregated with a t-conorm.
3 COMPLEX QUERY ANSWERING VIA OPTIMISATION
CQD answers existential positive first-order queries by combining neural link-prediction scores for their atoms into differentiable logical objectives. It optimises variable representations either continuously or through beam-style combinatorial search.
- The framework scores candidate target entities from all atomic queries under a variable-to-entity substitution, supporting queries with missing edges.
- Each variable receives an embedding, atom scores come from a neural link predictor, and t-norms or t-conorms aggregate them as continuous conjunction and disjunction relaxations.
- A neural link predictor maps atom arguments into k-dimensional embeddings and returns a [0, 1] likelihood score for each relation.
- Continuous optimisation: Continuous optimisation directly adjusts variable embeddings with gradient-based methods instead of enumerating variable-to-entity mappings.
- Combinatorial optimisation: Combinatorial optimisation traverses the dependency graph, retains the top-k substitutions at each step, and searches the resulting beam for high-scoring assignments.
- Combinatorial optimisation: The combinatorial procedure reduces possible intermediate answers, while scoring all entities can be performed efficiently in one GPU step.
4 RELATED WORK
The paper distinguishes CQD from black-box query-embedding and ad-hoc aggregation approaches by using a single differentiable formulation or scalable combinatorial search. Experiments compare these strategies with prior methods across datasets and query structures.
- CQD handles a substantially larger subset of first-order logic queries than approaches for learning to traverse Knowledge Graphs or black-box neural query answering.
- Query2Box-style methods require millions of generated queries to generalise well, whereas CQD uses far less training data.
- Neural link predictors are commonly evaluated on 1-hop queries because their formulation does not directly extend to complex queries.
- CQD uses a single pass whose aggregation steps are implemented with t-norms and t-conorms, rather than partitioning query graphs or using ad-hoc aggregation.
- Combinatorial optimisation was previously considered infeasible, but CQD shows that reducing intermediate candidates can make it scalable while outperforming state-of-the-art query answering.
5 EXPERIMENTS
CQD is evaluated on nine query types across three knowledge graphs, using the same datasets and metrics as prior work. CQD-Beam generally achieves higher H@3 than GQE and Q2B while using substantially less training data.
- Experimental setup: CQD evaluates continuous optimisation and beam search across nine query types on FB15k, FB15k-237, and NELL995.The evaluation includes two query types containing disjunctions.
- Evaluation: CQD compares against Graph Query Embedding and Query2Box using filtered Hits@3, which measures correct answers appearing among the top three ranked entities.Other correct answers are filtered before calculating H@3.
- Results: CQD produces more accurate H@3 results than GQE and Q2B on average while using orders of magnitude less training data.CQD-Beam consistently outperforms the baselines across all datasets under combinatorial optimisation.
- Results: CQD-Beam remains effective for chained 2p and 3p queries, although 3p is hardest because branching increases candidate variable substitutions.The difficulty is attributed to the search procedure’s branching factor.
- Results: More variables do not always reduce CQD-CO performance: it obtains the best ranking scores for specified ip and pi queries on FB15k-237 and NELL995.The cited ip and pi query types contain two variables.
M G Rank Correctness
CQD-Beam exposes intermediate variable assignments and ranked answers for example queries. These assignments can support correct rankings while also revealing when correct answers arise from an incorrect intermediate assignment.
- Diagnostic explanations: Intermediate assignments make CQD-Beam explanations inspectable, unlike the black-box transformations used by GQE and Q2B.The same inspection can identify failure modes even when the final answer appears correct.
- Correct rankings: For the Martin Lawrence query, CQD-Beam assigns intermediate movie variables correctly and ranks seven ground-truth genres first.The seven correct answers include Drama, Comedy, and Crime Fiction.
- Diagnostic explanations: For the Thomas Aquinas query, CQD-Beam ranks the four correct organisations first despite an incorrect intermediate nationality assignment.The correct nationality is Italy, whereas the intermediate assignment is incorrect but related.
6 CONCLUSIONS
CQD answers Existential Positive First-Order queries by decomposing them into sub-queries and aggregating scores in embedding space. It generalises across query types without complex-query training and provides step-by-step explanations.
- CQD answers Existential Positive First-Order queries by reasoning over entity sets in embedding space and aggregating sub-query scores via t-norms.
- The framework requires training a neural link predictor on atomic queries rather than millions of generated complex queries.
- Intermediate results explain each step of query answering regardless of query complexity, unlike black-box neural query embedding models.
- CQD generalises without explicitly training on specific query varieties and achieves significantly more accurate results than current state-of-the-art methods on incomplete Knowledge Graphs.
A INFLUENCE OF THE EMBEDDING SIZE ON THE RESULTS
The embedding-size experiments evaluate CQD-CO and CQD-Beam across different ranks and compare their accuracy with published complex-query baselines. The model remains accurate with significantly fewer parameters.
- Table 3 reports H@3 complex-query results across query types for different embedding sizes, including GQE and Query2Box baselines.
- CQD produces very accurate results even with significantly fewer parameters as the embedding rank changes.
B TIMING EXPERIMENTS
The timing experiments compare Q2B and CQD-Beam across query types in FB15k, FB15k-237, and NELL. CQD-Beam’s main computational bottleneck is multi-hop query processing.
- Figures 4 and 5 report seconds required by Q2B and CQD-Beam for each query type in FB15k and FB15k-237.
- CQD-Beam’s main computation bottleneck is multi-hop queries because it invokes the neural link predictor at every chain step to obtain top-k candidates.
C DISTMULT EXPERIMENTS
The DistMult experiments compare CQD-Beam using ComplEx and DistMult neural link predictors. DistMult produces slightly lower accuracy than ComplEx under the reported setup.
- Table 4 reports H@3 complex-query results for CQD-Beam using ComplEx and DistMult neural link prediction models.
- CQD-Beam with DistMult produces slightly less accurate results than with ComplEx.