Multi-hop query answering on knowledge graphs is known to be a challenging computational task. Neurosymbolic approaches using neural link predictors have shown promising results but are still outperformed by combinatorial optimization methods on several benchmarks, including the FB15k dataset. We analyze the task on the FB15k dataset and propose two new gradient-based methods, one learning simultaneously the representations of several candidate answers and the other learning a skolem function projecting to candidate answers instead of learning direct candidate representations. We implement both using Logic Tensor Networks. As part of this investigation we identified two important factors that limit the ability of diferentiable methods to learn correct answers. The first factor is the (un)reliability of the pre-trained neural link predictors which biases the guesses of the query solver. To account for this, we suggest new evaluation metrics using satisfiability scores, that better reflect the true performance of neurosymbolic approaches on multi-hop query answering. The second factor is the regularization technique proposed in previous works, which limits the exploration of the gradient-based solver. Our results provide the foundation for future work mitigating these bottlenecks.
Knowledge graphs (KGs) are graph-structured knowledge bases which enable representing
knowledge as a set of relationships (binary predicates) between entities (variables), and constitute
an important data structure with many use cases [
Instead, recent literature [10] has proposed to rely on pre-trained link predictors to answer queries without relying on new sets of examples. In particular, they couple link predictors with continuous relaxations of logical operators using fuzzy logic [11] to represent complex queries in fully diferentiable representations and open the ground for diferentiable methods to optimize for the objective. We focus our study on answering First-Order Logic queries as formulated by Arakelyan et al. [10]. In the simplest form, such queries have multiple variable nodes 1, ..., , one target node and one anchor node . They can be written ? ∶ ∃ 1, ..., 0(, 1) ∧ 1( 1, 2) ∧ ... ∧ ( , ) . In plain English, the objective is to decide whether there is an entity which verifies that there exists entities 1, ..., such that entities and 1 are linked by relation 0, entities 1 and 2 are linked by relation 1, etc and entities and are linked by relation . Still, the best-performing approach in [10] is a hybrid method that is making use of neural link predictors but performs the search for candidates using a beam search heuristic. On 2-hop queries from the FB15K dataset [12], the discrepancy between the diferentiable solution CQD-CO and the heuristic method CQD-Beam proposed by [ 10] is large. In this paper, we ask the question: what is holding fully diferentiable methods back from always performing better in multi-hop querying?
As part of our investigation, we propose two new improvements of the fully diferentiable approach. The first idea is to diversify the learned candidates by learning multiple embeddings simultaneously, which must all verify the query and then pick the one closest to the data. The second idea is to learn a skolem function [13], approximated by a neural network, which maps the target node to a corresponding variable node, instead of learning directly variable node embeddings. We have implemented both approaches using Logic Tensor Networks (LTNs) [14], a neurosymbolic framework based on fuzzy logic. Although the resulting improvements upon state-of-the-art turned out to be only marginal, our investigation allows us to identify two bottlenecks of which researchers and practitioners need to be acutely aware when using diferentiable methods to perform complex querying.
First, even best-performing neural link predictors may hold some biases that make optimization in a continuous space dificult. We found, on the FB15k dataset, that the fully diferentiable method CQD-CO is consistently finding candidate answers with high satisfiability—but since the satisfiability scores are so close to one another, this is not reflected in the Hits@3 score. 1 Computing satisfiability scores is therefore a better way to evaluate the performance of gradient-based querying, and reveals that the fully diferentiable approach may perform better 1By satisfiability, we mean the fuzzy relaxation of the score of a complex query, which is calculated based on neural link predictors for the atomic queries. with suitable neural link predictors and datasets. Secondly, in the fully diferentiable approach, regularization has a huge impact on the distance to the data of the learned candidates, by inducing some constraints on the values taken by the candidate embeddings which counteracts the need for diversification. We also established that the regularization must be adapted to the formulation, e.g. existing regularizations are not adapted to the parameterized neural network in skolemization—thus resulting in learned candidates further from the data.
2-hop queries from the FB15k dataset consist in a collection of 8000 queries. Each can be seen
as a tuple (, 1, 2), where is an anchor node and 1, 2 are two relations to form queries
? ∶ ∃ 1(, ) ∧ 2( , ) . An answer to that query is a target node that satisfies the query.
We can also define a full answer as a tuple ( , ) that satisfies 1(, ) ∧ 2( , ) . In the FB15k
dataset, there are 2690 distinct relations and 14,951 distinct entities.
A neural link predictor Θ is pre-trained together with embeddings e , e ∈ ℝ for any entity
and any relation R. Θ(e , e 1, e 2) ∈ [
The CQD-CO method [10] proceeds in two phases which we denote as learning and testing. Learning
CQD-CO solves the following problem by gradient-based optimization: (e∗, e∗) = argmaxe ,e ∈ℝ Θ(e 1, e , e ) ⋅ Θ(e 2, e , e ) (1) using the product t-norm ⋅ [14] as the continuous generalization of conjunction in logic. The idea is to optimize for entity embeddings (e∗, e∗) ∈ ℝ such that the truth value (or satisfiability) is maximized. One can see that the expression is indeed fully diferentiable. Also, the anchor node embedding, the relation embeddings and the neural link predictor are all pre-trained and ifxed. (e∗ , e ∗ ), ∈ {1 … } e to find the answer: (Testing) Real targets are tested against a path decided based on their nearest neighbor. The theoretical advantage over CQD-CO is that up to intermediate paths can be found.
Then, CQD-CO fixes the variable node e∗ and tests all real candidate node embeddings eans = argmaxe ∈ Θ(e 1, e , e∗) ⋅ Θ(e 2, e∗, e ) (2) where denotes the dataset of existing node embeddings. The motivation is that, after optimization, there is no guarantee that e∗ has converged to a real data point. CQD-CO [10] proposes to query the satisfiability of the 14,951 entities with the fixed intermediate nodes and to rank their scores. The exhaustive query is acceptable because its complexity does not depend on the number of hops, and hence is tractable. 2.2. Proposed Improvements In practical knowledge graphs, it is not uncommon to encounter multiple valid answers for a given query, as depicted in Figure 1. However, CQD-CO, upon completing its learning phase, only retains a single candidate path when querying in the testing phase. To address this limitation, we suggest two approaches that retain more candidate paths after the learning phase. 2.2.1. CQD-CO Multi: Learning multiple candidates Our first approach learns multiple candidate paths after the learning phase and employs nearest neighbor strategies to select the optimal querying path during testing.
Learning
To learn multiple candidates, we used, similarly to query parallelization, the meansquared error MSE as a diferentiable aggregator that approximates ∀. Notice however that other options such as the log-product aggregator are possible. Let denote the number of candidates. The optimization problem yields (e∗1, .., e ∗ , e 1
∗ , ..., e∗ ) values: argmaxe 1,..,e ,e 1,...,e ∈ℝ MSE∈{1,...,} ( Θ(e 1, e , e ) ⋅ Θ(e 2, e , e )) (3) Testing
Given the embedding of an entity e , let be the index of its nearest neighbor within e∗1, .., e ∗ (in terms of euclidean norm). Then, let the corresponding e ∗ variable node be (a) (b) paths are not fixed.
We reproduce CQD-CO [10] and our proposed improvements using the LTN framework [14]. For each method, the optimization phase can be parallelized on all 8000 queries using a meansquared error aggregator. The number of queries optimized in parallel, which can be viewed as satisfiability scores according to: denoted as proj∗(e ). For each of the 14,951 entities, use these candidates to compute and rank eans = argmaxe ∈ Θ(e 1, e , proj∗(e )) ⋅ Θ(e 2, proj∗(e ),e )
2.2.2. CQD-CO Skolem: Non-fixed Intermediate Paths via Skolemization Our second approach, which we name CQD-CO Skolem, aims to not fix any variable node during the testing phase of the candidates. We implement a dependence between the target node e and the variable node e in the form of a skolem function, materialized by a neural network . Doing so, we leave potentially every answer path open (instead of limiting it to at most 1 path in CQD-CO or paths in CDQ-CO Multi).
We also have to learn multiple candidates at the same time, so that the neural network captures a data-dependent mapping between target nodes and variable nodes (e ) = e in the context of the given query. The optimization problem thus becomes: argmaxe 1,..,e ,∈ℝ ,∈ℝ
MSE∈{1,...,} ( Θ(e 1, e , (e )) ⋅ Θ(e 2, (e ), e ))
and use it to generate a variable node embedding for each of the 14,951 entities, which is then used to compute and rank satisfiability scores according to: eans = argmaxe ∈ Θ(e 1, e , (e )) ⋅ Θ(e 2, (e ),e ) (4) (5) (6) a batch size, has an influence on the performance. Indeed, too big batch sizes can result in a deterioration of the satisfiability for some of the queries, whereas a too small batch will favor the maximization of the satisfiability for each query, which can lead to overfitting.
CQD-CO proposes to include a diferentiable regularization term Reg which is computed through canonical tensor decomposition [15]. The full optimization problem is: (e∗, e∗) = argmaxe ,e ∈ℝ Θ(e 1, e , e ) ⋅ Θ(e 2, e , e ) − Reg(e , e ) (7) For our proposed methods, we adapt it by summing over the candidates ∑=1 Reg(e , e ).
The results in terms of Hits@3 for varying numbers of learned candidates and batch sizes are reported in Table 1. The Hits@3 is the percentage of queries such that a correct answer is in the top 3 results of the testing phase in terms of satisfiability score. On FB15k, CQD-CO reaches a Hits@3 score of 30%. CQD-CO Multi, which diversifies the learned candidates by learning paths at the same time, allows us to push the performance to a 32% Hits@3 score only. Upon further investigation, we find that the regularization method is largely limiting the diversity of the paths. We discuss this in the next section. CQD-CO Skolem is rather unsuccessful, plateauing at a 2% Hits@3 score. While we believe that the idea is promising, since having a dependency between target and variable node is undoubtedly desirable, the trained neural network projects real entity embeddings onto intermediary points that were further from the data. That is likely due to our decision to train with no more than 100 candidates per query, as training with too many examples ultimately defeats the purpose of reducing the complexity of answering multi-hop queries. We leave further exploration of this idea to future work.
4.1. Prominent efects of regularization We performed an ablation study on the regularization term to understand its impact on the performance. Also, we performed a qualitative analysis of the L2 norms and euclidean distances to data of the learned candidates. Our findings were as follows: 1) with CQD-CO and regularization, learned candidates have L2 norms one order of magnitude smaller than real regularization, for diferent number of learned candidates and batch sizes, on FB15k. are further apart from one another, but distances to data are still much higher; and 3) with CQD-CO Skolem and regularization, learned candidates are one order of magnitude further away in euclidean distance from real data points than learned candidates by the previous method. Without regularization, the distances to data remain similar.
The ablation study reveals important diferences in performance when removing regularization for both CQD-CO and our extension to learning multiple candidates. The efect is not observable with skolemization. Results are reported in Table 2. Noticing that the regularizer tends to push learned candidates towards points with small norms and close to one another, we implement a more explicit norm regularization, namely L2-regularization, and interestingly, it is possible to reproduce state-of-the-art results with the right choice of hyperparameter.
Our interpretation of these empirical observations is that the regularizer constrains the exploration of the search space onto embeddings with smaller norms, which also limits the ability to learn correct patterns. This could be one of the glass ceilings of performance by these methods. Yet, when no constraint is applied, nothing prevents overfitting from happening, which explains why performance deteriorates although the learned embeddings are closer to real embeddings. Skolemization is a diferent story: the search space is diferent and regularization fails to mitigate overfitting. The trained neural network projects real embeddings onto points far away from the data, and the regularization term is not adapted to its parameterization which is why it has little to no efect. In our opinion, one would therefore need to come up with an entirely diferent regularization technique, adapted to this formulation, in order to harness the power of skolemization. 4.2. Satisfiability scores reveal biases in neural link predictors In order to gain a finer understanding of what gradient-based complex querying is actually learning, we studied directly the satisfiability scores instead of computing only Hits@3. The idea was to evaluate the satisfiability scores of the candidate answers to 2-hop queries to see by how much they were of, in comparison with ground truth answers.
For each query (, 1, 2), we consider the target node that was selected by each of the gradient-based complex querying methods through ranking of satisfiability scores. For each entity amongst the 14,951 possible entities, we evaluate the satisfiability Θ(e 1, e , e ) ⋅ Θ(e 2, e , e ), and we pick the entity with the highest satisfiability to form the full answer ( , ) . Similarly, considering a ground truth answer , we use the same procedure to form a full answer ( , ). If the satisfiability of a full answer obtained by our gradient-based methods is higher or equal to the satisfiability of the full answer from ground truth, we classify the answer as correct; otherwise, we classify it as incorrect. This allows us to compute a percentage of correct answers that we call satisfiability metric . The results are reported in Table 2 and show that the performance of gradient-based methods is underestimated by the Hits@3 metric. In other words, in some cases, it is possible to find an answer ( , ) with a higher satisfiability than that of ground truth answers ( , ), i.e. Θ(e 1, e , e )⋅ Θ(e 2, e , , e ) > Θ(e 1, e , e )⋅ Θ(e 2, e , e ), which reveals that the neural link predictor Θ may be biased.
We computed the typical diference between the highest satisfiability of a learned candidate answer and the highest satisfiability of a ground truth answer, when the learned answer is incorrect. For comparison, we computed the same typical diference between a random answer and a ground truth answer. Suprisingly, the diference with the random answer is already quite low (10−3). But the diference with our learned candidates is even lower ( 10−4) for our best-performing gradient-based method. There are two take-aways from these evaluations: 1) the neural link predictor creates a bias towards high values of satisfiability. For a given 2-hop query, for any entity chosen as the target node , it is possible to find a corresponding variable node which would yield a satisfiability close to the highest possible satisfiability, as much as a diference of 10−3; 2) the answers returned by our best-performing gradient-based complex querying methods, although they may be incorrect, are not just any answers: they are answers with a satisfiability very close to that of ground truth answers, as much as a diference of 10−4.
Our analysis sheds light on inherent dificulties that gradient-based complex querying methods may encounter on some particular datasets. Here, the task is to find, amongst entities with satisfiability scores close to one another as much as 10−3, the entities with best satisfiability to a 10−4 precision. In our opinion, this provides an explanation on why it is dificult to solve it with continuous optimization methods, which are inherently approximative. It comes as no surprise that a combinatorial optimization method which treats entities as discrete, no matter the diference between them, would perform better on this instance. Yet, our observations suggest that the gradient-based methods are learning what they should be learning and that some signal is definitely captured. We can infer that the performance of gradient-based methods could be dramatically better in configurations where the neural link predictors and the dataset are suitable, e.g. if the correct answers stick out in terms of satisfiability.
We have investigated the task of complex query answering on incomplete knowledge graphs, with one question in mind: why don’t gradient-based methods always produce the best performance? Although our attempts to improve on the existing methods have achieved only marginal improvements on the FB15k dataset, our in-depth analysis of the behavior of these methods in terms of distance to the data and satisfiability has given us ways to understand these results. We highlight the role of regularization in driving the learned candidates away or closer to the data and advocate that this should be carefully taken into account when using and designing these methods. Furthermore, we see that the Hits@3 metric may underestimate the performance of gradient-based complex querying in its inherent task, which is to generalize in terms of satisfiability. We also pinpoint a bottleneck that would perhaps need to be mitigated independently from the complex querying task: proximities in terms of satisfiability induced by the neural link predictor and the data. By demistifying in part the behavior of gradient-based complex querying, we hope that our work will serve as foundation for developing new solutions. (Eds.), Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, PMLR, 2022, pp. 27454–27478. URL: https://proceedings.mlr.press/v162/zhu22c.html. [10] E. Arakelyan, D. Daza, P. Minervini, M. Cochez, Complex query answering with neural link predictors, in: International Conference on Learning Representations, 2021. URL: https://openreview.net/forum?id=Mos9F9kDwkz. [11] E. van Krieken, E. Acar, F. van Harmelen, Analyzing diferentiable fuzzy logic operators, Artificial Intelligence 302 (2022) 103602. URL: https://www.sciencedirect.com/science/ article/pii/S0004370221001533. doi:h t t p s : / / d o i . o r g / 1 0 . 1 0 1 6 / j . a r t i n t . 2 0 2 1 . 1 0 3 6 0 2 . [12] A. Bordes, N. Usunier, A. Garcia-Duran, J. Weston, O. Yakhnenko, Translating embeddings for modeling multi-relational data, in: C. Burges, L. Bottou, M. Welling, Z. Ghahramani, K. Weinberger (Eds.), Advances in Neural Information Processing Systems, volume 26, Curran Associates, Inc., 2013. URL: https://proceedings.neurips.cc/paper/2013/file/ 1cecc7a77928ca8133fa24680a88d2f9-Paper.pdf. [13] A Shorter Model Theory, Cambridge University Press, 1997. [14] S. Badreddine, A. d’Avila Garcez, L. Serafini, M. Spranger, Logic tensor networks, Artificial Intelligence 303 (2022) 103649. URL: https://www.sciencedirect.com/science/article/pii/ S0004370221002009. doi:h t t p s : / / d o i . o r g / 1 0 . 1 0 1 6 / j . a r t i n t . 2 0 2 1 . 1 0 3 6 4 9 . [15] T. Lacroix, N. Usunier, G. Obozinski, Canonical tensor decomposition for knowledge base completion, in: J. Dy, A. Krause (Eds.), Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, PMLR, 2018, pp. 2863–2872. URL: https://proceedings.mlr.press/v80/lacroix18a.html.