Adapting Neural Link Predictors for Data-Efficient Complex Query Answering
Authors: Erik Arakelyan
Pasquale Minervini
Daniel Daza
Michael Cochez
Isabelle Augenstein
Venue: NeurIPS 2023 poster (2023)
Keywords: complex query answering
neural link prediction
knowledge graph embeddings
knowledge graphs
relational learning
adapters
TL;DR: We extend Continuous Query Decomposition with neural score adaptation layers to improve the interactions between atomic sub-query scores in complex query answering.

Abstract: Answering complex queries on incomplete knowledge graphs is a challenging task where a model needs to answer complex logical queries in the presence of missing knowledge. Prior work in the literature has proposed to address this problem by designing architectures trained end-to-end for the complex query answering task with a reasoning process that is hard to interpret while requiring data and resource-intensive training.  Other lines of research have proposed re-using simple neural link predictors to answer complex queries, reducing the amount of training data by orders of magnitude while providing interpretable answers. The neural link predictor used in such approaches is not explicitly optimised for the complex query answering task, implying that its scores are not calibrated to interact together. We propose to address these problems via CQD$^{\mathcal{A}}$, a parameter-efficient score \emph{adaptation} model optimised to re-calibrate neural link prediction scores for the complex query answering task. While the neural link predictor is frozen, the adaptation component -- which only increases the number of model parameters by $0.03\%$ -- is trained on the downstream complex query answering task. Furthermore, the calibration component enables us to support reasoning over queries that include atomic negations, which was previously impossible with link predictors. In our experiments, CQD$^{\mathcal{A}}$ produces significantly more accurate results than current state-of-the-art methods, improving from $34.4$ to $35.1$ Mean Reciprocal Rank values averaged across all datasets and query types while using $\leq 30\%$ of the available training query types. We further show that CQD$^{\mathcal{A}}$ is data-efficient, achieving competitive results with only $1\%$ of the complex training queries and robust in out-of-domain evaluations. Source code and datasets are available at https://github.com/EdinburghNLP/adaptive-cqd.

Adapting Neural Link Predictors for Data-Efficient Complex Query Answering
Erik Arakelyan"!
Pasquale Minervini
Daniel Daza 3,4,5
Michael Cochez 3.5
Isabelle Augenstein'
University of Copenhagen University of Edinburgh *Vrije Universiteit Amsterdam
University of Amsterdam Discovery Lab, Elsevier, The Netherlands
(erik.a augenstein @di ku.dk p p.minervini@er ac.uk {d. (d.dazzaruz, cochez @vu. nl
Abstract
Answering complex queries incomplete knowledge graphs is challenging task where a model needs to answer complex logical queries in the presence of missing knowledge. Prior work in the literature has proposed address this problem by designing architectures trained end-to-end for the complex query answering task with a reasoning process that hard interpret while requiring data and resource-intessive training. Other lines of research have proposed re-using simple neural link predictors answer complex queries, reducing the amount of training data by orders of magnitude while providing interpretable answers. The neural link predictor used in such approaches is not explicitly optimised for the complex query answering task, implying that its scores are not calibrated to interact together. We propose to address these problems via CQDA parameter-efficien score adaptation model optimised to re-calibrate neural link prediction scores for the complex query answering task. While the neural link predictor is frozen, the adaptation component which only increases the number of model parameters by 0.03% - trained on the downstream complex query answering task. Furthermore, the calibration component enables to support reasoning atomic negations, which was previously impossible with link predictors. In our experiments, CQDA produces significantly more accurate results than current state-of-the-an methods, improving from 34.4 to 35.1 Mean Reciprocal Rank values averaged across all datasets and query types while using 30% of the available training query types. We further show that CQDA is data-efficient, achieving competitive results with only 1% of the complex training queries, and robust in out-of-domain evaluations. Source code and datasets are available at https://githhbb http://tttuub.ccoom/aiinnrbeeeee http.///awa.ou.ggeaa//a/aaaeeeee
queries that include
Introduction
Knowledge Graph (KG) is knowledge base representing the relationships between entities in relational graph structure. The flexibility of this knowledge representation formalism allows KGs to be widely used in various domains. Examples of KGs include
knowledge bases such Wikidata (Vrandečié and Krötzsch, 2014). DBpedia [Auer et al. 2007]. Freebase [Bollacker et 2008]. and YAGO [Suchanek et al. 2007]; application-drive Graph, Microsoft's 's Bing Knowledge Graph, and Facebook's 's Social Graph [Noy al. 2019 and domain-specific ones such as SNOMED CT [Bodenreider et al. 2018). MeSH [Lipscomb] 2000]. and Hetionet [Himmelstein et al.
graphs such as the Google Know ledge
2017 for life sciences; and WordNet Miller 1992 linguistics.
*Equal contribution, alphabetical order. Senior author.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Answering complex queries over Knowledge Graphs involves a logical reasoning process where conclusion should be inferred from the available knowledge.
Neural link predictors Nickel et al. 2016] tackle the problem of identifying missing edges in large KGs. However, in many domains, queries involving multiple and potentially unobserved edges, entities, and variables rather than just single edges.
challenge to develop techniques for answering complex
Prior work proposed to address this problem using specialised neural networks trained end- to-end for the query answering task (Hamil- ton et al. 2018 Daza and Cochez 2020, Ren et al. 2020 Ren and Leskovec 2020 Zhu et al. 2022 which offer little interpretability and re- quire training with large and diverse datasets of query-answer pairs. These methods stand in contrast with Complex Query Decomposi- tion ICQD, Arakelyan al., [2021] Minervini et al. 2022]. which showed that it is sufficient to re-use simple link prediction model to answer complex queries, thus reducing the amount of training data required by orders of magnitude while allowing the possibility to explain interme- diate answers. While effective, CQD does not support negations, and fundamentally, it relies on link predictor whose scores are not necessarily calibrated for the complex query answering task. Adapting neural link predictor for the query answering task while maintaining the data and parameter efficiency of CQD, as well as its interpretable nature, is the open challenge we take on in this paper.
2 = T country(Germany. 7) music(Constantine, 7)
Sub-queries
0.5
country(Gernany.77
Q.16
-7.S
0.01
Q.02
0.65
0.07
music(Constantine.)
2.0
0.34
0.02
and
Answer
Scores
Neural Link
Predictors
Adapters
Figure 1:
Given a complex query 2, CQDA adapts the neural link prediction scores for the sub-queries to improve the interactions between them.
We propose CQDA, a lightweight adaptation model trained to calibrate link prediction scores, using complex query answering as the optimisation objective. We define the adaptation function as an affine transformation of the original score with few learnable parameters. The low parameter count and the fact that the adaptation function is independent of the query structure allow us to maintain the efficiency properties of CQD. Besides, the calibration enables a natural extension of CQD to queries with atomic negations.
An evaluation of CQD-A on three benchmark datasets for complex query answering shows an increase from 34.4 to 35.1 MRR over the current state-of-the-arr averaged across all datasets while using S 30% of the available training query types. In ablation experiments, we show that the method is data-efficient; it achieves results comparable to the state-of-the while using only 1% of the complex queries. Our experiments reveal that CQDA can generalise across unseen query types while using only 1% of the instances from single complex query type during training.
2 Related Work
I Link Predictors in Knowledge Graphs Reasoning over KGs with missing nodes has been widely explored throughout the last few years. One can approach the task using latent feature models, such as neural link predictors [Brdds et al.] 2013 Trouillon et al., 2016 Yang et al., 2014] Dettmers al. 2019 Amin et al., [020] which learn continuous representations for the entities and relation types in the graph and can answer atomic queries over incomplete KGs. Other research lines tackle the link prediction problem through graph feature models [iiong et al. 2017 Das et al. 2017 Hildebrandt et al. 20200 Yang et al. [011 Sadeghian ct al. 2019], and Graph Neural Networks [GNNs, Schlichtkrul et al. 2018 Vashishth et al. 2019
al., 2018, [Snn et al.) [2019 Balažević
Teru et al. 2020
Complex Query Answering Complex queries over knowledge graphs can be formalised by extend- ing one-hop atomic queries with First Order Logic (FOL) operators, such as the existential quantifier (3), conjunctions (A), disjunctions (V) and negations (-). These FOL constructs can be represented directed acyclic graphs, which are used by embedding- based methods that represent the queries

---

Hamilton et al. 2018 or probabilistic distributions [Ren and Leskovec 2020 Zhang et al., 2021| Choudhary al., 2021 and search the embedding space for the answer set. It is also possible to enhance the properties of the embedding space using GNNs and Fuzzy Logic (Zhu et al. 2022 Chen et al., 2022]. A recent survey [Ren et al. 2023] provides a
using geometric objects [Ren et al. 2020
broad overview of different approaches. Recent work [Daza and Cochez, 2020 Hammllon et al., 2018
Ren and Leskovee 2020] suggests that such methods require a large dataset with millions of diverse queries during the training, and it can be hard to explain their predictions.
Our work is closely related to CQD [Arakelyan et al. 2021 Minervini et al. 2022 which uses a pre-trained neural link predictor along with fuzzy logical t-norms and t-conorms for complex query answering. core limitation of CQD is that the pre-trained neural link predictor produces scores not calibrated to interact during the complex query-answering process. This implies that the final scores of the model are highly dependent on the choice of the partieular t-(co)norm aggregation functions, which, in turn, leads to discrepancies within the intermediate reasoning process and final predictions. As a side effect, the lack of calibration also means that the equivalent of logical negation in fuzzy logic does not work as expected.
With CQDA, we propose solution to these limitations by introducing scalable adaptation function that calibrates link prediction scores for query answering. Furthermore, we extend the formulation of CQD to support broader class of FOL queries, such as queries with atomic negation.
3 Background
A Knowledge Graph 9 S & x R triples, where each triple encodes a relationship of type p E R between the subject 8 E & and the object o E & of the triple, where & and R. denote the set of all entities and relation types, respectively. A Knowledge Graph can be represented
can be defined as a set of subject--rrdiicae--ojjeed (s, p, o)
First-Order Logie Knowledge Base, where each triple (s, p, o) denotes an atomic formula p(s, o), with p E R a binary predicate and 8, o E & its arguments.
First-Order Logical Queries We are concerned with answering logical queries over incomplete
knowledge graphs. We consider queries that use existential quantification (3) and conjunction (A) operations. Furthermore, we include disjunctions (V) and atomic negations (-). We follow Ren et al.
[220)] by transforming logical query into Disjunctive Normal Form [DNF, Davey and Priestley
2002]. i.e. a disjunction of conjunctive queries, along with the subsequent extension with atomic
negations in [Ren and Leskovec
2020]. We denote such queries as follows:
[[A] ?A IV...., (e' A.. ....Ae,,, Aej, v (ef where of P(c,V), with Ve (A, Vov,...,VV,jeee... Vn), E R.
(I)
or e = VV,,",, with V,V E e (A.K. Vva. AV PER
In Equation (T). the variable A is the target of the query, Vi,..., Vn denote the bound variable nodes, while e E represent the input anchor nodes, which correspond to known entities in the query. Each e denotes a logical atom, with either one (p(c, V)) or two variables (p(V, V')).
The goal of answering the logical query Q consists in finding the answer set [Q] C & such that E [[]] iff Qía] holds true. As illustrated in Figure [ the dependency graph of conjunctive query Q is a graph where nodes correspond to variable or non-variable atom arguments in Q and edges correspond to atom predicates. We follow Hamilton et al. [2018) and focus on queries whose dependency graph is a directed acyclic graph, where anchor entities correspond to source nodes, and the query target is the unique sink node.
Example 3.1 (Complex Query). Consider the question "Which people are German and pro- duced the music for the film Constantine?". It can be formalised complex query Q ?T country( Germany, T) A producerOf(( Consttatiin,,n,nienennneeee T'), where Germany and Constantine are anchor nodes, and T' is the target of the query, presented in Figure [ The answer [Q] corresponds to all the entities in the knowledge graph that are German composers for the film Constantine.
Continuous Query Decomposition CQD a framework for answering EPFO logical queries in the presence of missing edges [Arakelyan et al. 202 Minervini al.) 2022 Given query Q, COD
3

---

defines the score of a target node E E as candidate answer for a query as a function of the score of all atomic queries in 2, given a variable-to-entity substitution for all variables in Q.
Each variable is mapped to an embedding vector that can either correspond to an entity e E & or to a virtual entity. The score of each of the query atoms is determined individually using neural link predictor [Nickel et al., 2016]. Then, the score of the query with respect to a given candidate answer Q[a] computed by aggregating all of the atom scores using t-norms and I-conorms continuous relaxations of the logical conjunction and disjunction operators.
Neural Link Predictors A neural link predictor a differentiable model where atom arguments are first mapped into d-dimensional embedding space and then used to produce a score for the atom. More formally, given a query atom p(s, o). where p E R and 8, E E, the score for p(s, o) is computed op(es, where es, e, E IR are the embedding vectors of 8 and o, and Up : IRd x IRd [0, 1] is a scoring function computing the likelihood that entities 8 and are related by the relationship p. Following Arakelyan et al. [202T]. Minervini et [2022] in our experiments, we use a regularised variant of ComplEx [Trouillon al. [0016] Lacroix al. 2018 as the neural link predictor of choice, due to its simplicity, efficiency, and generalisation properties Ruffinelli et al. To ensure that the output of the neural link predictor is always in [0, 11, following Arakelyan
2020
et al.
2021 Minervini et al. 2022). we use either a sigmoid function or min-mas re-scaling.
T-norms and Negations Fuzzy logic generalises over Boolean logic by relaxing the logic conjunc- tion (A), disjunction (V) and negation (-) operators through the use of t-norms, t-conorms, and fuzzy negations. I-norm T: [0, 1] [0, 1] - [0, 1] is generalisation of conjunction in fuzzy logic [Kle- ment et al. 2000 2004). Some examples include the Gödel t-norm min (x, 3) min v). the product I-norm (rod(z,)) (T,3) !) = x x y, and the Lukasiewicz t-norm Taak(z, y) = max x + y - 1}.
Analogously, I-conorms are dual to t-norms for disjunctions given a t-norm T, the complementary t-conorm is defined by _(x, y) = T(1 x, y). In our experiments, we use the Gödel t-norm and product t-norm with their corresponding t-conorms.
Fuzzy logic also encompasses negations [0, 1] - [o, 1]. The standard (x) 1 and strict cosine necss = {1 + cos(TT)) are common examples of fuzzy negations Kruse and Moewes 1993.. To support broader class of queries, we introduce the standard and strici cosine tunctions to model negations in CQDA, which was not considered in the original formulation COD.
Continuous Query Decomposition Given DNF query Q defined in Equation (1). CQD aims to find the variable assignments that render Q true. To achieve this, CQD casts the problem of query answering as an optimisation problem. The aim find a mapping from variables to entities S = (A + a, V12 + Ui,..., Vn + }m where Ul,..., Um E E are entities and A, Vi.... Vn are variables, that maximises the score of Q:
arg max score (2, S) = arg max (oTT... ... Tel,) L.... (EtT... Tel.)) A.
where et op ev), with V [A, Vi..., E or of = (ev, ) with V, V' E V VV
where T and 1 denote a t-norm and a t-conorm - a continuous generalisation of the logical conjunc- tion and disjunction, respectively and @, e.) E [0, 1] denotes the neural link prediction score for the atom p(s,
Complex Query Answering via Combinatorial Optimisation Following Arakelyan al. [2021] Minervini et al. [2022), we solve the optimisation problem in Equation (2) by greedily searching for a of variable substitutions S {A + a, V1 t- Ui...., Vn vm ). with a, U1,... 2m E E, that maximises the complex query score, in procedure akin to beam search. We do so by traversing the dependency graph of query Q and, whenever we find an atom in the form p(c. V), where p E R. is either an entity or a variable for which we already have a substitution, and V is variable for which we do not have a substitution yet, we replace V with all entities in & and retain the top-k d (e,, ex) - i.e. the most likely entities appear as a substitution of V according to the neural link predictor. As we traverse the dependency graph of a query, we keep a beam with the most promising variable-to-entity substitutions identified so far.
J.
entities /. E & that maximise

---

Example 3.2 (Combinatorial Optimisation). Consider the query "Which musicians M received awards associated with a genre g?. which can be rewritten as ?M A...ssoc( Areeeivee (, M). To answer this query using combinatorial optimisation, we must find the top-k awards that are candidates to substitute the variable A assoc(g, A). This will allow us to understand the awards associated with the genre g. Afterwards, for each candidate substitution for A, we search for the top-k musicians m that are most likely to substitute M in received M), ending up with k² musicians. Finally, we rank the k2 candidates using the final query score produced by t-norm.
Calibrating Link Prediction Scores on Complex Queries
The main limitation in the CQD method outlined in Section B is that neural link predictors are trained to answer simple, atomic queries, and the resulting answer scores are not trained to interact with one another.
Example 4.1. Consider the running example query "Which people are German and produced the music for the film Constantine?"" ?" which can be rewritten as complex query Q ?T Cauntry(Germany T) A producerOf
T). To answer this complex query, CQD answers CeenttryGGrrmammnn (Germany. 7) and Q2 = producerOf (Constaatie,,,,,,,, T) using a neural link predictor, and aggregates the resulting scores using a t-norm. However, the neural link predictor was only trained on answering atomic queries, and the resulting scores are not calibrated to interact with each other. For example, the scores for the atomic queries about the relations country and producerOf may be on different scales, which causes problems when aggregating such scores via t-norms. Let us assume the top candidates for the variable T coming from the atomic queries Q1, Q2 A + Sam Shepard and Ag t- Klaus Badelt, with their corresponding neural link prediction scores 1.2 and 8.9, produced using Dcountry and Oproducerrf- We must also factor in the neural link prediction score of the candidate Ai for query Q2 at 7.4 and vice versa 0.5. When using the Gödel t-norm T minn(;; y) = min {x. y), the scores associated with the variable assignments A1, are computed as, min((..,000 0.5)
the atomic sub-queries Q1 = country
0.5 min(7.4, 1.2) 1.2. For both answers Ai and A2, the scores produced by Ocountry for Q are always lower than the scores produced with @prouuerrr for 22, meaning that the scores of the latter are not considered when producing the final answer. This phenomenon can be broadly observed in CQD, illustrated in Figure
To address this problem, we propose a method for adaptively learning to calibrate neural link prediction scores by pack-propagating through the complex query-answering process. More formally, let 0p denote a neural link predictor. We learn an additional adaptation function pe. parameterised by 0 = {a, 3), with a, E R. Then, we use the composition of po and Φp. Po Op. such that:
po(áp(ev, ev))) = ev:) +
(3)
Here, the function p defines an affine transformation of the score and when the parameters a = B= the transformed score pe (o),ev,, ev-)) recovers the original scoring function. The parameters 0 can be conditioned on the representation of the predicate p and the entities V and V", i.e. (ee,,, ep, ev'); here, vo is an end-to-end differentiable neural module with parameters W. ey, ey, ey respectively denote the representations of the subject, predicate, and object of the atomic query. In our experiments, we consider using one or two lincar transformation layers with ReLU non-lincarity as options for e).
The motivation for our proposed adaptation function is twofold. Initially, it is monotonic, which is desirable for maintaining the capability to interpret intermediate scores, as in the original formulation of CQD. Moreover, we draw inspiration from the use of affine transformations in methodologies such as Platt scaling [Platt et al., 1999], which also use a linear function for calibrating probabilities and have been applied in the problem of calibration of link prediction models (Tabacof and Costabello 2020). Parameter-efficient adaptation functions have also been applied effectively in other domains, such adapter layers Houlsby et al. [2019] used for fine-tuning language models in NLP tasks.
Training For training the score calibration component in Equation 3). we first compute how likely each entity a' E & is to an answer to the query Q. To this end, for each candidate answer a' E E, we compute the answer score as the complex query score assuming that a' E E is the final answer as:
score @, A d') max score ( S),, where A d' E S.
5

---

Distribution neural prediction scores
Split
Query Types
FBISK
FB15K-237
NELL995
0.6
Dendty
0.4
Train
2in, Sin. inp. pin, pni
1p. 2p, 3p. 21,
273,710
27,371
149,689
14,968
107,982
10,798
Valid
1p Others
59,078
20,004
16,910
0.2
8,000
5,000
4,000
Test
1p Others
66,990
22,804
17,021
0.0
8,000
5,000
4,000
Figure 2: The distributions two atomic scores
Table 1: Statistics on the different types of query structures in FB15K, FB15K-237, and NELL995,,
Q and 22. and the aggregated results via T min
the scores from 22 dominate the final scores.
TV: 39; inla 33
1P: My, Poott MAAM & AppR(
sin
Imp
plo
pwl
1V PlApiKTT Ampying
T
Aplls
Andhar Node
Varsari Noda
Target Node
Diqundion
Nagwion
Figure 3: Query structures considered in our experiments, as proposed by Ren and Leskovec (0220 the naming of each query structure corresponds to projection (p), intersection (i), union (u) and negation (n), reflecting how they were generated in the BetaE paper [Ren and Leskoved [020]. An example of pin query is ?T' pV,((a, V), 9V, T), rr,, T)), where and b are anchor nodes, V is a variable node, and T is the query target node.
Equation (4) identifies the variable-to-entity substitution S that 1) maximises the query score score Q, S). defined in Equation (2). and 2) associates the answer variable A with a' E, i.c. A + a' E S. For computing S with the additional constraint that A +- a' E S, we use the complex query answering procedure outlined in Section 3 We optimise the additional parameters W introduced in Section 4 by gradient descent the likelihood of the true answers
dataset D (Q2,, o, 12 of query-answer pairs by using a /-vs-all cross-entropy loss, introduced by Lacroix al. 20188. which was also used to train the neural link prediction model:
((D) = Σ score Q,, A a.) + log (D..))ED
Σ La'EE
exp (score A + A.)))
(5)
In addition to the 1-vs-all (Ruffinelli et al. 2020 loss in Equation
5 we also experiment with the
binary cross-entropy loss, using the negative sampling procedure from Ren and Leskoved (2020)
Experiments
Datasets To evaluate the complex query answering capabilities of our method, we use a benchmark comprising of KGs: FB 15K [Bordes et al., 2013), FB15K-237 [Toutanova and Chen 2015 and NELL995 [Xiong et al. 2017]. For fair comparison with previous work, we use the datasets of FOL queries proposed by Ren and Leskoved 2202]] which includes nine structures of EPFO queries and 5 query types with atomic negations, seen in Figure 3, The datasets provided by |Ren and Leskovec 2020 introduce queries with hard answers, which are the answers that cannot be obtained by direct graph traversal: in addition, this dataset does not include queries with more than 100 answers, increasing the difficulty of the complex query answering task. The statisties for each dataset can be seen in Table I Note that during training, we only use 2i, 3i, 2in, and 3in queries, corresponding to S 30% of the training dataset, for the adaptation the neural link predictor. To assess the model's 's ability to generalise, evaluate it on all query types.

---

Model
avpp
ave..
1p
2p
3p
pi
ip
2u
up
Imp
pin
pni
FB15K
GQB
27.6
22.1
Q2B
38.0
68.0
21.0
14.2
55.1
66.5
39.4
26.1
35.1
16.7
BetaB
41.6
11.8
65.1
25.7
24.7
55.8
66.5
43.9
28.1
40.1
25.2
14.3
14.7
11.5
6.5
12.4
CQD-CO
46.9
89.2
25.3
13.4
74.4
78.3
44.1
33.2
41.8
21.9
CQD Beam
68.4
89.2
65.3
29.7
76.1
79.3
70.6
70.6
72.3
39.4
Conti
73.7
50.9
35.7
55.7
18.7
9.8
15.1
GNN- QE
72.8
38.6
88.5
69.3
58.7
79.7
83.5
69.9
70.4
74,1
61.0
44.7
41.7
42.0
30.1
34.3
CQDA
70.4
42.8
89.2
64.5
57.9
76.1
79.4
70.0
70.6
68.4
57.9
54.7
47.1
37.6
35.3
24.6
FB15K-237
GQB
23.3
34.6
16.5
10.7
8.2
5.7
Q2B
20.1
40.6
9.4
6.8
29.5
42.3
21.2
12.6
11.3
7.6
Betal:
20.9
5.5
39.0
10.9
10.0
28.8
42.5
22.4
12.6
12.4
9.7
5.1
7.9
7.4
3.5
3.4
CQD-CO
46.7
31.2
40.6
23.6
16.0
14.5
8.2
CQD-Beam
25.3
46.7
13.3
7.9
34,4
48.3
27.1
20.4
17.6
11.5
ConB
23.4
5.9
41.8
12.8
11.0
32.6
47.3
25.5
14.0
14.5
10.8
5,4
8.6
7.8
4.0
3.6
GNN QF
26.8
10.2
42.8
14.7
11.8
38.3
54.1
31.1
18.9
16.2
13,4
10.0
16.8
9.3
7.2
7.8
CQD-1
25.7
10.7
46.7
13.6
11.4
34,5
48.3
27.4
20.9
17.6
11.4
13.6
16.8
7.9
8.9
5.8
NELL995
GQE
18.6
32.8
11.9
9.6
27.5
35.2
18.4
14.4
8.5
8.8
Q2B
22.9
42.2
14.0
11.2
33.3
44.5
22.4
16.8
11.3
10.3
BetaE
24.6
5.9
53.0
13.0
11.4
37.6
47.5
24.1
14.3
12.2
8.5
5.1
7.8
10.0
3.1
3.5
CQD-CO
30.1
22.0
17.3
CQD- Beam
31.8
60.4
22.6
13.6
42.6
52.0
31.2
25.6
19.9
16.7
ConR 27.2
6.4
53.1
16.1
13.9
40.0
50.8
26.3
17.5
15.3
11.3
5.7
8.1
10.8
3.5
3.9
GNN-QE 28.9
14.9
42.4
52.5
18.9
15.9
12.6
9.9
14.6
6.3
6.3
CQD
32.3
13.3
60.4
22.9
16.7
43.4
52.6
32.1
26.4
20.0
17.0
15.1
18.6
15.8
10.7
6.5
Table 2: MRR results for FOL queries on the testing sets. avg, designates the averaged results for EPFO queries (A, V), while avg, pertains to queries including atomic negations (-). The results for the baselines are from Zhu et al. [022]
Evaluation Protocol For fair comparison with prior work, we follow the evaluation scheme in Ren and Leskoved [2020) by separating the answer of each query into easy and hard sets. For test and validation splits, we define hard queries as those that cannot be answered via direct traversal along the edges of the KG and can only be answered by predicting at least missing link, meaning non-trivial reasoning should be completed. We evaluate the method on non-trivial queries by calculating the rank for each hard answer against non-answers and computing the Mean Reciprocal Rank (MRR).
Baselines We compare CQDA with state-of-the-art methods from various solution families in Section 2 In particular, choose GQE [Hamilton al. 2018 Query2Box (Ren al. 2020). BetaE Ren and Leskoved [2020] and ConE [Zhang et al. |022] as strong baselines for query embedding methods. We also compare with methods based GNNs and fuzzy logic, such as FuzzQE [Chen et al. 2022]. GNN-QE [Zhu et al., 2022]. and the original CQD |Arakelyan et al. 2021 102IMiinervin et al. 2022]. which uses neural link predictors for answering EPFO queries without any fine-tuning on complex queries.
Model Details Our method can be used with any neural link prediction model. Following Arakeelyn
et al. [2021], Minervini et al. [0022), we use ComplEx-N3 [Lacroix et al. 2018). We identify the optimal hyper- parameertsssssss using the validation MRR. We train for 30, 000 steps using Adagrad as an optimiser and 0.1 as the learning rate. The beam-size hyper-parameter & was selected in E (512, 1024......... 8192), and the loss was selected across 1-vs-all [Lacroix al. 2018 and binary cross-entropy with one negative sample.
Parameter Efficiency We use the query types 2i, 3i, 2in, 3in for training the calibration module proposed in Section We selected these query types as they do not require variable assignments other than for the answer variable A, making the training process efficient. As neural link prediction model is frozen, we only train the adapter layers that have maximum of W E 2x2 learnable weights. Compared to previous works, we have 103 times fewer trainable parameters, as shown in Table 3 while maintaining competitive results.
7

---

Average MRR with 1% and 100% training data
Number of parameters
FB15K
FB15K-237
NELL
CQDA
1.3 x 10"
1.3 10
7.5 10'
MRR
Trozzo +4 x 10
Choees
Trezen
10
1.3 -4 X 10
+4 x 10
BetaE
1.3 x 10"
Q2B
1.2 x 107
107
702
average
GNN-QE
10
3x 10
10
Performance Difference
ConE
1.2 107
1.2 x 107
6 10"
average MRR with 100%
GQE
1.5x 10"
1.5 x 107
7.5 X 10"
1 2
6 Iteration per 400 epochs
9 10 11 12 13
Figure 4: Average test MRR score (y-axis) of CQDA using 1% and 100% of the training queries from FB15K-237 throughout the training iterations (z-axis).
Table 3: Number of parameters used by different complex query answering methods values for GNN-QE are approximated using the backbone NBFNet [Zhu et al. 2021], while the remaining use their original studies.
5.1 Results
Complex Query Answering Table shows the predictive accuracy of CQDA for answering complex queries compared to the current state-of-the-art methods. Some methods do not support queries that include negations; increases the MRR from 34.4 to 35.1 averaged across all query types and datasets. In particular, CQDA shows the most substantial increase in predictive accuracy NELL995 by producing more accurate results than all other methods for all query types. CQDA can achieve these results using < 30% of the complex query types during training while maintaining competitive results across each dataset and query type. For queries including negations, CQDA achieves a relative improvement of 6.8% to 37.1 1,, which can be attributed to the fact that the adaptation is completed with query types 2in and 3in that include negation, which allows for learning an adaptation layer that is robust for these types of queries. In our experiments, we found that calculating the neural adaptation parameters of the adaptation function Pa in Equation (3) as a function of the predicate representation yields the most accurate results followed by computing entity and predicate representation, which is strictly more expressive. In Appendix A impact of the adaptation layers on the neural link prediction scores.
leave the corresponding entries blank. We
that CQDAA
function of the source we show the
The adaptation process does not require data-intensive training and allows the model to generalise to query types not observed during training. This prompts investigate the minimal amount of data samples and query types required for adaptation.
Data Efficiency To analyse the data efficiency of CQDA, we compare the behaviour of the pre-trained link predictors tuned with 1% and 100% of the training complex query examples in FB15K-237, presented in Table 4 For adapting on 1% of the training complex queries, we used the same hyper-paran prrpee-parameter we identified when training on the full dataset. Even when using 1% of the complex training queries (3290 samples) for tuning, the model still achieves competitive results, with an average MRR difference of 2.2 compared to the model trained using the entire training set. CQDA also produces higher test MRR results than GNN-QE with an average MRR increase of 4.05.
We can also confirm that the adaptation process converges after S 10% of the training epochs as seen in Figure The convergence rate is not hindered when using only 1% of the training queries. This shows that CQD-4 is scalable method with a fast convergence rate that can be trained in data-efficient manner.
Out-of-Dise Disttriiitttin Generalisation To study the generalisation properties of CQDA, we trained the adaptation layer on all atomic queries and only 1% of samples for one training query type 2i, one of the simplest complex query types. We see in Table that CQD4 can generalise to other types of complex queries not observed during training with an average MRR difference 2.9 compared to training all training query types. CQDA also produces significantly higher test MRR results

---

Dataset
Model
1p
2p
3p
pi
1p
211
up
2in
imp
pin
pni
CQDA
46.7
11.4
24.82
17.81
16.45
8.74
10.8
13.86
14.82
FB237, 1%
GNN-QE
36.82
8.96
8.13
33.02
49.28
24.58
14.18
10.73
8.47
4.89
12.31
6.74
4.41
4.09
36.80
5.94
22.84
34.34
8.72
9.23
4.44
2.94
CQD4
46.7
11.8
11.2
30.35
40.75
23.36
18.28
15.85
8.96
9.36
10.25
5.17
4.46
4.44
FB237 21, 1%
GNN QE
34.81
5.40
5.17
30.12
48.88
23.06
12.65
9.85
5.26
4.26
12.5
4.43
0.71
1.98
BetaF
37.99
5.62
4.48
23.73
35.25
15.63
7.96
9.73
4.56
0.15
0.49
0.62
0.10
0.14
Table 4: Comparison of test MRR results for queries on FB15K-233 using the following training sets FB237, 1 % (resp. FB237 2i, 1 1%) means that, in addition to all 1p (atomic) queries, only 1% of the complex queries (resp. 2i queries) was used during training. As CQDA uses a pre-trained link predictor, also include all /p queries when training GNN-QE for fair comparison.
Model
2p
2i
pi
ip
2u
up
2in
3in
inp
pin
pni
CQD
13.2
34.5
48.2
26.8
20.3
17.4
10.3
5.4
12.4
6.1
3,2
4,6
CQD;
9.3
22.8
34.9
19.8
14.5
13.0
7.2
7.4
7.1
4.9
3.9
3.8
CQDA
9.5
23.9
39.0
19.8
14.5
14.2
7.2
8.4
9.7
4.9
4.2
3.6
CQDe
10.9
33.7
47.3
25.6
18.9
16.4
9.4
7.9
12.2
6.6
4.2
5.0
CQDR
6.4
22.2
31.0
16.6
11.2
12.5
4.8
4.7
5.9
4.1
2.0
3.5
CQDA
13.2
35.0
48.5
27.3
20.7
17.6
10.5
13.2
14.9
7.4
7.8
5.5
Table 5: Test MRR results for FOL queries FB 15K-237
using the following CQD extensions: CQD from AAaaelyyn et al.] [2021). Minervini et al.] [2022] with the considered normalisation and negations; CQDF, where fine-tune all neural link predictor parameters in CQD: CQDA, where fine-tune all link predictor parameters in CQD-; CQDR. where we learn transformation for the entity and relation embeddings and we use to replace the initial entity and relation representations; and CQDc. where learn transformation for the entity and relation embeddings, and concatenate it the initial entity and relation representations.
than GNN-QE, with average increase of 5.1 MRR. The greatest degradation in predictive accuracy occurs for the queries containing negations, with an average decrease of 2.7. This prompts us to conjecture that being able to answer general EPFO queries is not enough to generalise to the larger set of queries, which include atomic negation. However, our method can generalise on all query types, using only 1% of the 2i queries, with 1496 overall samples for adaptation.
Fine-Tuning All Model Parameters One of the reasons for the efficiency of CQD is that the neural link predictor not fine-tuned for query answering. and only the parameters the adaptation function are learned. We study the effect of fine-tuning the link predictor using the full training data for CQD and CQDA on FB 2537 We consider several variants: 1) CQDF, where we Fine-tune all neural link predictor parameters in CQD; 2) CQDA, where we fine-tune all link predictor parameters in CQDA, 3) CQDR, where we learn a transformation for the entity and relation embeddings and we use it to Replace the initial entity and relation representations, and 4) CQDc, where we learn transformation for the entity and relation embeddings, and we Concatenate it to the initial entity and relation representations.
It can be seen from Table 5 that CQDA yields the highest test MRR results across all query types while fine-tuning all the model parameters produces significant degradation along all query types, which we believe is due to catastrophic forgetting [Goodfellow et al. 2013) of the pre-trained link predictor.
Conclusions
In this work, we propose the novel method CQDA for answering complex FOL queries over KGs, which increases the averaged MRR over the previous state-of-the the- art from 34.4 to 35.1 1 while using < 30% of query types. Our method uses a single adaptation layer over neural link predictors, which allows for training in data-efficient manner. We show that the method can maintain competitive predictive accuracy even when using 1% of the training data. Furthermore, our experiments on training on subset (1%) of the training queries from single query type (2i) show that it can generalise to

---

new queries that were not used during training while being data-efficiens Our results provide further evidence for how neural link predictors exhibit a form of compositionality that generalises to the complex structures encountered in the more general problem of query answering. CQDA is method for improving this compositionality while preserving computational efficiency. As a consequence, rather than designing specialised models trained end-to-end for the query answering task, we can focus our efforts on improving the representations learned by neural link predictors, which would then transfer to query answering via efficient adaptation, well other downstream tasks where they have already proved beneficial, such as clustering, entity classification, and information retrieval.
Acknowledgements
Pasquale was partially funded by the European Union's Horizon 2020 research and innovation programme under grant agreement no. 875160, ELIAI (The Edinburgh Laboratory for Integrated Artificial Intelligence) EPSRC (grant no. EP/W002876/1), an industry grant from Cisco, and donation from Accenture LLP, and is grateful to NVIDIA for the GPU donations. Daniel and Michael were partially funded by Flsevier's 's Discovery Lab. Michael was partially funded by the Graph- Massivizer project (Horizon Europe research and innovation program of the European Union under grant agreement 101093202). Erik is partially funded by DFF Sapere Aude research leader grant under grant agreement No 0171-00034B, as well as by a NEC PhD fellowship, and is supported by the Pioneer Centre for AI, DNRF grant number P1. Isabelle is partially funded by DFF Sapere Aude research leader grant under grant agreement No 0171 1770-00044B, as well as by the Pioneer Centre for AI, DNRF grant number P1. This work supported by the Edinburgh International Data Facility (EIDF) and the Data-Driven Innovation Programme at the University of Edinburgh.
References
S. Amin, S. Varanasi, K. A. Dunfield, and G. Neumann. Lowfer: Low-rank bilinear pooling for link prediction. In International Conference on Machine Learning, pages 257-268. PMLR, 2020.
E. Arakelyan, D. Daza, P. Minervini, and M. Cochez. Complex query answering with neural link predictors. In ICLR. OpenReview.net, 2021.
S. Auer, C. Bizer, G. Kobilarov, J. Lehmann, R. Cyganiak, and Z. G. Ives. DBpedia: A nucleus for web of open data. In ISWC/ASWC, volume 4825 of Lecture Notes in Computer Science, pages 722-735. Springer, 2007.
I. Balažević, C. Allen, and T. M. Hospedales. Tucker: Tensor factorization for knowledge graph completion. arXiv preprint 100.v:1901.09555 2019.
O. Bodenreider, R. Cornet, and D. Vreeman. Recent developments in clinical terminologies snomed ct, loinc, and rxnorm. Yearbook of medical informatics, 27:129-139, Aug 2018. ISSN 2364-0502.
K. D. Bollacker, C. Evans, P. Paritosh, T. Sturge, and J. Taylor. Freebase: collaboratively created graph database for structuring human knowledge. In SIGMOD Conference, pages 1247-1250. ACM, 2008
A. Bordes, N. Usunier, A. García-Durán, J. Weston, and O. Yakhnenko. Translating embeddings for modeling multi-relational data. In NIPS, pages 2787-2795, 2013.
X. Chen, Z. Hu, and Y. Sun. Fuzzy logic based logical query answering on knowledge graphs. In AAAI, pages 3939-3948. AAAI Press, 2022.
N. Choudhary, N. Rao, S. Katariya, K. Subbian, and C. K. Reddy. Self-supervised hyperboloid representations from logical queries over knowledge graphs. In Proceedings of the Web Conference 2021, pages 1373-1384, 2021.
R. Das, S. Dhuliawala, M. Zaheer, L. Vilnis, Durugkar, A. Krishnamurthy, A. Smola, and A. Mc- Callum. Go for walk and arrive at the answer: Reasoning over paths in knowledge bases using reinforcement learning. arXiv preprint 17Xiv:1111.0888 2017.
B. A. Davey and H. A. Priestley. Introduction to Lattices and Order, Second Edition. Cambridge University Press, 2002.
10

---

D. Daza and M. Cochez. Message passing query embedding. In ICML Workshop Graph Represen- tation Learning and Beyond, 2020. /ttp:/// http://aaaxivvorrga///222222 02406
Dettmers, P. Minervini, P. Stenetorp, and Riedel. Convolutional 2d knowledge graph embeddings. In AAAI, pages 1-11-1818. AAAI Press, 2018.
I. J. Goodfellow, M. Mirza, D. Xiao, A. Courville, and Y. Bengio. An empirical investigation of catastrophic forgetting in gradient-based neural networks. arXiv preprint arXiv:/312.622 2013.
W. L. Hamilton, P. Bajaj, M. Zitnik, D. Jurafsky, and J. Leskovec. Embedding logical queries on knowledge graphs. In NeurlPS, pages 2030-2041, 2018.
M. Hildebrandt, A. Q. Sema, Y. Ma, M. Ringsquandl, M. Joblin, and V. Tresp. Reasoning on knowledge graphs with debate dynamics. In AAAI, pages 11113-11131 AAAI Press, 2020.
S. Himmelstein, A. Lizee, C. Hessler, L. Brueggeman, S. L. Chen, D. Hadley, A. Green, P. Khankha- nian, and S. E. Baranzini. Systematic integration of biomedical knowledge prioritizes drugs for repurposing. bioRxiv, 2017. doi: 1011100/97661. URLbttps: //wp:////wwww... www.bboooivvv....... www.orriwwwooroooeettttttt. tarlly2011700//1/007666
N. Houlsby, A. Giurgiu, S. Jastrzebski, B. Morrone, Q. De Laroussilhe, A. Gesmundo, M. Attariyan, and S. Gelly. Parameter-efficient transfer learning for nlp. In International Conference on Machine Learning, pages 2790-2799 PMLR, 2019.
E. Klement, R. Mesiar, and E. Pap. Triangular Norms, volume 8 of Trends in Logic. Springer, 2000.
E. Klement, R. Mesiar, and E. Pap. Triangular norms. position paper I: basic analytical and algebraic properties. Fuzzy Sets Syst., 143(1):5-26, 2004.
R. Kruse and Moewes. Fuzzy systems. BG Teubner Stuttgart, 1993.
Lacroix, N. Usunier, and G. Obozinski. Canonical tensor decomposition for knowledge base completion. In ICML, volume 80 of Proceedings of Machine Learning Research, pages 2869-28778 PMLR, 2018.
C. E. Lipscomb. Medical subject headings (mesh). Bull Med Libr Assoc., //www, pwb.edeaaneent........ -nih http//aricleeeeeeeee Fogi/artid-352335
2000. URL http: 88(3): 265-266.
G. A. Miller. WORDNET: lexical database for english. In HLT. Morgan Kaufmann, 1992.
Minervini, E. Arakelyan, D. Daza, and M. Cochez. Complex query answering with neural link predictors (extended abstract). In IJCAI, pages 5309-5313, ijcai.org, 2022.
M. Nickel, K. Murphy, V. Tresp, and E. Gabrilovich. A review of relational machine learning for knowledge graphs. Proceedings of the IEEE, 104(1):11 1-33,, 2016.
N. F. Noy, Gao, Jain, A. Narayanan, A. Patterson, and J. Taylor. Industry-scale knowledge graphs: lessons and challenges. Commun. ACM, 62(8):36 43, 2019.
J. Platt et al. Probabilistic outputs for support vector machines and comparisons to regularized likelihood methods. Advances in large margin classifiers, 10(3):61-74, 1999.
H. Ren and Leskovec. Beta embeddings for multi-hop logical reasoning in knowledge graphs. Advances in Neural Information Processing Systems, 13:19716-19726, 2020.
H. Ren, W. Hu, and J. Leskovec. Query2box: Reasoning over knowledge graphs in vector space using box embeddings. In 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenReview.net, 2020. /ttp://tte///
het:/forumiddBBJr4445
H. Ren, M. Galkin, M. Cochez, Z. Zhu, and J. Leskovee. Neural graph reasoning: Complex logical query answering meets graph databases. CORR, abs/2303. 10000.146111 14617, 2023.
D. Ruffinelli, S. Broscheit, and R. Gemulla. You CAN teach an old dog new tricks! on training knowledge graph embeddings. In ICLR. OpenReview.net, 2020.

---

A. Sadeghian, M. Armandpour, P. Ding, and D. Z. Wang. Drum: End-to-end differentiable rule mining on knowledge graphs. Advances Neural Information Processing Systems. 32, 2019.
M. Schlichtkrull, N. Kipf, P. Bloem, R. Berg, Titov, and M. Welling, Modeling relational data with graph convolutional networks. In European semantic web conference, pages 593-607. Springer, 2018.
M. Suchanek, G. Kasneci, and G. Weikum, Yago: a core of semantic knowledge. WWW, pages 697-706. ACM, 2007.
Z. Sun, Z.-H. Deng, J.-Y. Nie, and J. Tang. Rotate: Knowledge graph embedding by relational rotation in complex space, arXiv preprint arXiv:1902.1111 2019.
P. Tabacof and L. Costabello. Probability calibration for knowledge graph embedding mod- els. 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenReview.net, 2020. URL AtRLLtttps///ppererviee www.eenreviee.ee/ffrroueee net/forum? 1d=Sig8K1BFWS
K. Teru, E. Denis, and W. Hamilton. Inductive relation prediction by subgraph reasoning. In International Conference Machine Learning, pages
PMLR, 2020.
K. Toutanova and D. Chen. Observed versus latent features for knowledge base and text inference. In Proceedings of the 3rd Workshop on Continuous Vector Space Models and their Compositionality. pages 57-66, Beijing, China, July 2015. Association for Computational Linguistics. doi: 10.18655. v1/W15-4007. URL htt.lhttss////t //www aclweb. oww.oogg//aooo. prgg/antoooogy/W15555-
T. Trouillon, J. Welbl, S. Riedel, É. Gaussier, and G. Bouchard. Complex embeddings for simple link prediction. In ICML, volume 48 of JMLR Workshop and Conference Proceedings, pages 2071-2080 JoLR.org, 2016.
Vashishth, S. Sanyal, Nitin, and P. Talukdar. Composition-ben bbaeod multi-relational graph convolu- tional networks. arXiv preprint arXiv: 191100001 2019.
D. Vrandečié and M. Krötzsch. Wikidata: A free collaborative knowledge base. Communi- 2014. URL http://cacm. acm org.mmagazines/2044110
cations of the ACM, 57:78-85,
118786-wiikddtta/fullee..
W. Xiong, T. Hoang, and W. Y. Wang. Deeppath: A reinforcement learning method for knowledge graph reasoning. In EMNLP, pages 564-573. Association for Computational Linguistics, 2017.
B. Yang, W.-t. Yih, X. He, J. Gao, and L. Deng. Embedding entities and relations for learning and inference in knowledge bases. arXiv preprint arXiv:1412.6577 2014.
Yang, Z. Yang, and W. W. Cohen. Differentiable learning of logical rules for knowledge base reasoning. Advances in neural information processing systems, 30, 2017.
Z. Zhang, J. Wang, J. Chen, S. Ji, and F. Wu. Cone: Cone embeddings for multi-hop reasoning knowledge graphs. Advances Neural Information Processing Systems, 34:19172-191883 2021.
Z. Zhu, Z. Zhang, L.-P. Xhonneux, and J. Tang. Neural bellman-ford networks: A general graph neural network framework for link prediction. Advances in Neural Information Processing Systems, 34:29476-29490, 2021.
Z. Zhu, M. Galkin, Z. Zhang, and J. Tang. Neural-symbolic models for logical queries on knowledge graphs. arXiv preprint arXiv:2205. 10/28, 2022.
12

---

for traiing
warga diference
Tranes ce
Distribution neural link prediction scores
Betrre StPr Atuplation
150
Density
1.5
100
8.75
5
10
Score
Figure 5: The distribution of the scores of the neural link predictor before applying the adapta- tion layer and after
Figure 6: Evaluation of CQDA using 1% and 100% of the training complex queries during tun- ing (top) and 2i queries (bottom) from FB 15K- 237.
A Impact of adaptation
We investigate the effect of the adaptation process in CQD- by comparing the score of the neural link predictor before and after applying the adaptation layer. As we see from F the scores before adaptation have variation of 5.04 with the boundaries at [-8, 12]. This makes them problematic for complex query answering as discussed in Section 4 The Adapted scores have a smaller variation at 0.03 while the maximum and minimum lie the [0, range.
B On data efficiency and generalisation of CQD4
We conduct a series of experiments comparing the performance of CQDA trained while only using 1% of the training data to the complete training set in FB15K-237. We see from Figure (o (top) that the model maintains a strong performance on the complex reasoning task with 2.4 averaged MRR degradation compared to using the complete data. This phenomenon is even more pronounced when we use only 1% of the queries while using 2i as training query types Figure 6 (bottom). In this data and query type constrained mode CQDA maintains competitive performance with a degradation of 2.7 averaged MRR for complex queries compared to training with complete data. This highlights the dltt--efficien nature of CQDA and shows that training a score adaptation layer does not require significant data for training. This is also accompanied by the observation that CQDA is able to generalise to unseen query types while training only on 2i, This behaviour is not inherent, as seen from Table 4
13


Reviews:
[{"review_id": "SOquNrEE59", "reviewer": "Reviewer_jjs4", "summary": "The paper proposes CQD$^\\mathcal{A}$ an adaptive variant of the complex query decomposition (CQD) approach. The authors identify that the neural link predictors used in CQD produce uncalibrated scores that can be in very different ranges of each other. The authors show that CQD$^\\mathcal{A}$ can adaptively learn an adaptive function that alleviates this problem.\nIn an extensive evaluation the authors show that this adaptive calibration imbues CQD with favorable properties such as being more data efficient, robust to OOD and being able to support negation.", "questions": "Perhaps the part about negation could be better explained in the paper.  The authors say that negations are modelled by either a standard or strictly cosine functions. In theory this could be added to vanilla CQD as well. Was this experimented with? Maybe improved results ny CQD$^\\mathcal{A}$  over vanilla CQD would bolster the importance of calibration for supporting negations. ", "limitations": "The authors have not addressed the limitations or potential societal impacts of their work.\n Perhaps the authors could talk about how CQD$^\\mathcal{A}$ can produce explainable solutions to complex questions which can create systems that can be verified.  ", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper addresses an important limitation of CQD, wherein the Neural link predictors can produce vastly different ranges of scores leading reduced performance. The authors provide a very simple fix that (inspired from Platt's scaling) allows these scores to be calibrated. \nThe authors show that this allows the model to boast better results on three benchmarks. The authors also show that this adaptive setting allows the modelling for negations that was previously not feasible.  (**Significance** and **originality**)\n\nThe paper is generally well written and easy to follow. (**clarity**)\n\nThe authors also provide extensive analysis with regards to their proposed approach which can give useful insights regarding what helps improve performance. (**quality**)\n\n\n", "weaknesses": "I think one weakness is that the approach lacks a great deal of novelty. The proposed method is a minor augmentation to an existing approach. However, I still believe that the authors have identified an important problem with CQD and have provided a technically sound solution.\n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank you for your comments and valuable feedback. Regarding your questions,\n- Negations are modelled by either a standard or strictly cosine functions. In theory this could be added to vanilla CQD as well.\n\nEven though the link prediction scores are not explicitly calibrated in the original formulation of CQD, we agree that negations can, in principle, be applied with similar functions. Based on your comments, we updated the results in Table 5 to include negations with CQD in our comparison (see Table 1 in the rebuttal PDF), and we find that the model still benefits from an additional calibration via fine-tuning step. This confirms the effectiveness of calibrating the scores for the complex query-answering task.\n\n- How can CQD$^\\mathcal{A}$ produce explainable solutions to complex questions which can create systems that can be verified?\n\nWe would like to refer you to our global response, where we clarify why CQD$^\\mathcal{A}$ remains as interpretable as CQD. We will update the camera ready with additional analysis on this aspect.\n"}, {"review_id": "cg7UKuzzor", "reviewer": "Reviewer_oS1P", "summary": "This paper proposes an adaptation model on top of neural link predictors to learn score re-calibration to suit complex query answering task.Shows empirical evaluation on standard benchmark datasets to show its value. One of the benefits is a simple calibration model with lesser training data on complex questions gives better results than ones present in the literature.", "questions": "Model is fine tuned with 2i and 3i queries, and test results on those two query patterns don't show any win in two datasets. Any comment on why its happening?\n\nMethod seems to get clear benefit on NELL but not on other datasets. any comments on why its happening. ", "limitations": "Yes", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 2, "strengths": "Paper is well written and easy to follow. Contributions are clearly spelled out. \nExperimental results cover complex query answering benchmarks and show the value. ", "weaknesses": "Contribution seems incremental on top of the existing works. Seems like a small extension to CQD. \nOverall results show benefits only on certain query cases compared to state of the art. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank you for your comments and valuable feedback. We would like to address the following points:\n- Contribution seems incremental.\n\nOur analysis of CQD points to a fundamental limitation of CQD that is not necessarily trivial to solve if we want to maintain its favourable properties, such as data efficiency and interpretability. We directly tackle the fundamental limitation of uncalibrated scores with a lightweight function that maintains interpretability (due to its linearity), which we argue is not an obvious extension but rather effective compared to significantly more computationally demanding and less data-efficient methods.\n\n- Method seems to get clear benefit on NELL but not on other datasets. any comments on why its happening.\n\nWe respectfully disagree with this conclusion. In the case of EPFO queries on FB15k and FB15k-237, CQD$^\\mathcal{A}$ remains close to GNN-QE, but CQD$^\\mathcal{A}$ outperforms all baselines on all datasets, on queries including negations, all while using 10^3 fewer parameters. In the low-data regime (described in the Data Efficiency subsection), the advantages of CQD$^\\mathcal{A}$ over GNN-QE become more pronounced. In additional results (see Table 2 in rebuttal PDF), we have included an additional comparison with BetaE in the low-data regime, where CQD$^\\mathcal{A}$ is still producing significantly more accurate results than the baselines."}, {"review_id": "eWBA9drMah", "reviewer": "Reviewer_jfF5", "summary": "The paper proposes a novel approach called CQD^A for answering complex queries on incomplete knowledge graphs. The authors address the challenge of answering complex logical queries in the presence of missing knowledge by re-calibrating neural link prediction scores. They introduce an adaptation component that is trained on the downstream complex query answering task, while the neural link predictor is frozen. The proposed model, CQD^A, significantly improves the Mean Reciprocal Rank values compared to existing state-of-the-art methods. It achieves this by increasing the accuracy of answers while using a smaller amount of training data. Additionally, CQD^A is shown to be data-efficient and robust in out-of-domain evaluations.\n\nTo sum up, the proposed method is simple yet efficient. I have no reason to reject.", "questions": "see weaknesses.", "limitations": "Limitations are ignored in this paper.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "1. Novel Approach: The paper introduces a unique and novel approach for answering complex queries on incomplete knowledge graphs. The use of neural link predictors and the adaptation component allows for efficient complex query answering while providing interpretable answers. Well motivation.\n2. Improved Accuracy: The proposed model, CQD^A, outperforms current state-of-the-art methods. This improvement demonstrates the effectiveness of the re-calibrated neural link prediction scores in producing more accurate results.\n3. Data Efficiency: CQD^A achieves competitive results even with only 1% of the training data. This data efficiency is advantageous as it reduces the computational and resource requirements for training the model.\n4. Robustness: The model's robustness is demonstrated through out-of-domain evaluations. The ability to perform well in different domains further strengthens the applicability and effectiveness of CQD^A.", "weaknesses": "1. Interpretability of Results: While the paper mentions that the proposed approach provides interpretable answers, it would be beneficial to provide some concrete examples or explanations to illustrate this interpretability.\n2. Further Analysis of Training Data Reduction: The paper mentions that CQD^A achieves competitive results with only 1% of the training data. It would be interesting to see a more detailed analysis of the impact of reducing the training data on the model's performance across different query types and datasets.\n3. Future Directions: It would be valuable to discuss potential future directions for the research. This could include exploring the applicability of CQD^A in different domains or investigating the scalability of the approach to larger knowledge graphs.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank you for your comments and valuable feedback. We would like to address the following points:\n- It would be beneficial to provide some concrete examples or explanations to illustrate this interpretability.\n\nWe would like to refer you to our global response, where we clarify why CQD$^\\mathcal{A}$ remains as interpretable as CQD. We will provide an additional analysis for this aspect in the camera-ready version.\n\n- Discussion of future work.\n\nIn our conclusion, we emphasise that an important direction of future work lies in fundamental enhancements to link prediction methods. With CQD$^\\mathcal{A}$, these improvements can be easily adapted for complex query answering in a data-efficient and computationally efficient way. However, we also identify other promising avenues for future exploration. One such area is the significant gap across all methods between EPFO queries and queries containing negations, potentially revealing a core limitation in existing query-answering techniques. Additionally, we propose investigating the specific type of link predictor used in CQD$^\\mathcal{A}$, which employs ComplEx+N3 as the default model. This exploration may pave the way for designing link prediction models that generalise better to complex query answering. We will include this discussion in the camera-ready version.\n"}, {"review_id": "aGZrhOpPVM", "reviewer": "Reviewer_pnJH", "summary": "The paper proposes a score adaptation model called CQDA for efficient complex query answering on incomplete knowledge graphs. The authors address the problems in existing methods that are either hard to interpret or require intensive training. CQDA is a parameter-efficient model that recalibrates neural link prediction scores for the complex query answering task. The authors demonstrate that CQDA outperforms state-of-the-art methods in terms of accuracy, data efficiency, and robustness.", "questions": "- Figure 1 shows the scores over all entities but does not clearly present if the score is from a score function, or from a linear layer. If I understand correctly, the score before adaptation should come from the score function $\\phi$, right?", "limitations": "N/A", "rating": 7, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The paper addresses an important problem in the field of complex query answering on incomplete knowledge graphs. The proposed CQDA model provides a solution that improves accuracy while maintaining computational efficiency.\n- The paper introduces a parameter-efficient score adaptation model that recalibrates neural link prediction scores. This approach reduces the need for extensive training data and resources.\n- Experimental results show that CQDA achieves significantly better results than current state-of-the-art methods. The model is also shown to be data-efficient and robust in out-of-domain evaluations.\n", "weaknesses": "I think there is a discrepancy between Figure 1 and the statement, and thus the paper lacks an important baseline: **normalizing scores then merging**.\n\nIn Figure 1, the paper shows that the score scale may be different for different subqueries, which makes me think that the original COD may be without normalization which maps the score from any scale to [0,1]. However, the paper also mentions that they follow previous work to add normalization as below:\n> To ensure that the output of the neural link predictor is always in [0, 1], following Arakelyan et al. [2021], Minervini et al. [2022], we use either a sigmoid function or min-max re-scaling.\n\n So, what would happen if we do a merge after normalization on scores for all subqueries? Please correct me if I miss anything.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review! Regarding your concerns –\n- In Figure 1, the paper shows that the score scale may be different for different subqueries, [..] However, the paper also mentions that they follow previous work to add normalization as below [..]\n\nIn CQD, for the t-norm and t-conorms to be applicable, link prediction scores need to be mapped to the $[0, 1]$ range, which they achieve, for example, via the sigmoid function. However, we find that these transformations may be insufficient to solve the score calibration problem outlined in Figure 1. For instance, given two atoms $a_1$ and $a_2$ with scores in $[-10, -5]$ and $[5, 10]$, using the sigmoid will cause the score of the former atom to be close to $0$ and the score of the latter atom to be close to $1$, which will cause the latter score always to be ignored when applying the minimum t-norm. In this work, we propose a solution to this problem by learning to adapt the scores using simple transformation learned on the downstream complex query answering task by back-propagating through the complex query answering process. In our rebuttal PDF (Table 1), we included an additional experiment that evaluates previous work with normalization but without calibration, which we observe produces less accurate results than our proposed CQD$^{\\mathcal{A}}$.\n"}, {"review_id": "cVmXULkJRz", "reviewer": "Reviewer_5Xze", "summary": "This paper addresses the challenging task of answering complex queries on incomplete knowledge graphs, where missing knowledge introduces additional complexity. Previous approaches either employed end-to-end architectures with opaque reasoning processes or relied on simple neural link predictors, sacrificing information gain for computational efficiency. To overcome these limitations, the authors propose a parameter-efficient score adaptation model optimized for recalibrating neural link prediction scores in complex query answering. While the neural link predictor remains frozen, the adaptation component, with minimal additional parameters, is trained on the downstream task. The proposed method significantly improves accuracy compared to state-of-the-art approaches, achieving higher Mean Reciprocal Rank values while using only a fraction of the available training query types. ", "questions": "N/A", "limitations": "This is a solid work.", "rating": 7, "confidence": 1, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "### Originality\nThe paper introduces a novel approach to addressing the task of answering complex queries on incomplete knowledge graphs. The use of a parameter-efficient score adaptation model, optimized for recalibrating neural link prediction scores, sets it apart from previous methods. This original approach demonstrates innovation in the field of complex query answering and contributes to advancing the understanding of addressing missing knowledge in knowledge graphs.\n\n### Quality\nThe paper provides thorough evaluations and comparisons with state-of-the-art methods, demonstrating that the proposed approach produces significantly more accurate results. The proposed method significantly improves accuracy compared to state-of-the-art approaches, achieving higher Mean Reciprocal Rank values while using only a fraction of the available training query types.\n\n### Clarity\nThe paper effectively communicates the proposed approach and its components, such as the parameter-efficient score adaptation model and the frozen neural link predictor. The writing is clear, concise, and well-structured.\n\n### Significance\nThe paper addresses an important and challenging task in the field of complex query answering on incomplete knowledge graphs. By introducing the approach and demonstrating its superior performance compared to existing methods, the paper makes a significant contribution to the advancement of techniques for handling missing knowledge in knowledge graphs.\n", "weaknesses": "The authors haven't discussed the limitation of this work in the paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review. Regarding the following,\n- The authors haven't discussed the limitation of this work in the paper.\n\nWe tried our best to run all possible ablations and analyses for this paper, and some additional experiments to run came up during this rebuttal phase. We will add results of CQD with the considered negation functions to the camera ready and a more detailed analysis of the explainability properties of CQD$^\\mathcal{A}$ -- which we assume are inherited from CQD, but we do not discuss it in the main paper mainly for space reasons; as well as potential future work directions.\n"}]

Author rebuttal:
We thank the reviewers for their time and valuable feedback. We appreciate that reviewers acknowledge CQD$^\mathcal{A}$ proposes a novel (jfF5, 5Xze) and technically sound method (jjs4) for data-efficient complex query answering.We have incorporated the provided feedback into our work, including additional experiments (highlighted in red) in the rebuttal PDF.

**Effectiveness of CQD$^\mathcal{A}$ in additional settings**

In the rebuttal PDF, we include additional experiments motivated by the reviewer’s feedback that further indicate the effectiveness of CQD$^{\mathcal{A}}$:
- Table 1 shows the result of vanilla CQD applied directly to queries with negations. We observe that CQD$^{\mathcal{A}}$ still yields more accurate results, indicating that simply normalizing via the sigmoid, or min-max re-scaling, may not be sufficient to solve issues caused by non-calibrated scores, and thus CQD$^{\mathcal{A}}$ significantly benefits from an additional fine-tuning step on the downstream complex query answering task.
- Table 2 includes an additional comparison with BetaE, showing how CQD$^{\mathcal{A}}$ yields significantly more accurate results on the downstream complex query answering tasks.

**Interpretability of CQD$^{\mathcal{A}}$**

Reviewers jfF5 and jjs4 indicated that it is not clear whether CQD$^{\mathcal{A}}$ maintains interpretability. One of the advantages of CQD is the ability to inspect link prediction scores at each step of the query-answering process. This allows to explicitly access and assess the intermediate candidate assignments made by the model for each reasoning step. Our proposed calibration function is monotonic, so the order in the ranking produced by the link prediction scores at each step is preserved and can be interpreted in the same way as in CQD (note that calibration does affect how scores are combined during complex query answering). This would not necessarily be the case if the calibration function were nonlinear. We will clarify this aspect in the camera-ready version.

We provide answers to the remaining questions in individual responses.


Meta-review: The authors propose a method for calibrating neural link predictors that leads to substantial improvements in answering complex questions against a knowledge graph.

All reviewers agree that the paper addresses an important limitation in a good way, which is carefully evaluated and demonstrated to lead to sizable improvements.
Decision: Accept (poster)