Is Complex Query Answering Really Complex?

## Abstract

Abstract Complex query answering (CQA) on knowledge graphs (KGs) is gaining momentum as a challenging reasoning task.
In this paper, we show that the current benchmarks for CQA are not really complex , and the way they are built distorts our perception of progress in this field.
For example, we find that in these benchmarks most queries (up to 98% for some query types) can be reduced to simpler problems, e.g. link prediction, where only one link needs to be predicted.
The performance
of state-of-the-art CQA models drops significantly when such models are evaluated on queries that cannot be reduced to easier types.
Thus, we propose a set of more challenging benchmarks, composed of queries that require models to reason over multiple hops and better reflect the construction of real-world KGs.
In a systematic empirical investigation, the new benchmarks show that current methods leave much to be desired from current CQA methods. † † = shared supervision.

## 1 Introduction

A crucial challenge in AI and ML is learning to perform complex reasoning, i.e., solving tasks that involve a number of intermediate steps and sub-goals to be completed. Complex query answering (CQA; Hamilton et al., ; Zhang et al., ; Arakelyan et al., ; Zhu et al., ) has emerged as one of the most prominent ways to measure complex reasoning over external knowledge bases, encoded as knowledge graphs (KGs; Hogan et al., ).
For instance, to answer the query:

$$ “ Which actor performed in a movie filmed in New York City and distributed on Blue Ray? ” ( $q_{1}$ ) $$

over a KG such as FreeBase (Bollacker et al., ),
one would need to first
intersect the set of movies found on Blue Ray and the ones shot in New York City,
and then link these intermediate candidate answers to another entity, i.e., an actor participating in it.
However, the answers computed in this way may not include entities that are unreachable if missing links are present.

To deal with the unavoidable incompleteness of real-world KGs,
ML methods were developed to solve CQA in the presence of missing links.
Neural query answering models, constituting the current state-of-the-art (SoTA) for CQA (Arakelyan et al., ; Zhu et al., ; Arakelyan et al., ; Ren et al., ; Galkin et al., ), map queries and KGs (i.e., entities and relation names) into a unified latent space that supports reasoning. Performance measurements on de-facto-standard benchmarks such as $\mathsf{FB15k237}$ (Toutanova & Chen, ) and $\mathsf{NELL995}$ (Xiong et al., )
suggest that in recent years such models achieved impressive progress on CQA on queries having different structures, and hence posing apparently different levels of difficulty to be answered.

The difficulty of a benchmark relates to the size and structural complexity(^1^11Not to be confused with the computational complexity of query answering (Dalvi & Suciu, ).) of its queries, and several query “types” have been proposed (Ren et al., ), each involving a different combination of logical operators—conjunctions, disjunctions, and requiring to traverse a number of missing links that generally increases with the number of logical conditions imposed ([Figs. 1](#S1.F1) and [2](#S2.F2)).
For instance, the query [$q_{1}$](#S1.Ex1) is an example of a “2i1p” type, since it comprises an intersection of two entity sets (2i) followed by a path(^2^22Also referenced as projection in related works (Ren et al., ).) of length one (1p).

In this paper, we argue that the perception of progress on CQA benchmarks has been distorted by implicit assumptions in these benchmarks.
We start by noting how both in $\mathsf{FB15k237}$ and $\mathsf{NELL995}$, the vast majority of queries of a complex type simplifies to one simpler type, thanks to the fact that to answer them one can leverage links already appearing in the training data.
[Fig. 1](#S1.F1) shows an example of how answers to the query [$q_{1}$](#S1.Ex1) on $\mathsf{FB15k237}$– which should require predicting three missing links – require the same effort associated to simpler types involving
fewer
links.
In fact, in $\mathsf{FB15k237}$ the answer “K. Dunst” can be retrieved by
predicting
just
one missing link while leveraging
the training links.
In this sense, a 2i1p query reduces to a “1p” query, i.e., the much simpler task of link prediction (see [Sec. 2](#S2)).
Similarly,
the answers “J. Bryant” and “K. Chandler” can be retrieved by predicting two links, instead of three.
Only the answer “A. Serkis” requires predicting three
missing
links,
and thus satisfies the expected “hardness” associated to the type 2i1p.

We furthermore argue that SoTA performance is inflated likely due to current models memorizing training links.
Therefore, we create new CQA benchmarks that comprise only “hard” queries, i.e., queries that cannot be reduced to simpler types
by leveraging
training
links.
Then, we perform a thorough re-evaluation of the SoTA
models
for CQA.
Lastly, in order to raise the bar of “complexity” for CQA, we investigate more realistic sampling schemes to generate the train/validation/test splits,
and introduce query types that require more reasoning steps in order to be answered.

Figure: Figure 1: Query answers are not all equally hard when some links can be found in the training data as shown for the 2i1p query [$q_{1}$](#S1.Ex1) and fragments of the KG $\mathsf{FB15k237}$, where $r_{1}=\mathsf{distributedVia}^{-1}$, $r_{2}=\mathsf{locatedIn}^{-1}$ and $r_{3}=\mathsf{performedIn}^{-1}$. Its different answers can be obtained by traversing the training graph (continuous line) and predicting the missing links (dotted lines). (Top) Example answer that requires all links to be predicted. (Bottom) Example answers that require only a subset of the links to be predicted and that, therefore, can be reduced to the simpler types [1p](#S2.Ex2), [2p](#S2.Ex3), and [2i](#S2.Ex5) (see [Sec. 2](#S2) and [Fig. 2](#S2.F2)). non plus ultra query
Refer to caption: /html/2410.12537/assets/x1.png

#### Contributions.

After revisiting the CQA task ([Sec. 2](#S2)) and highlighting how query types can simplify at test time ([Sec. 3](#S3)),
(C1) we show that there is a major data leakage of training
links,
reporting that up to 99.9% test queries can be reduced to simpler queries, with the majority of them (up to 98%) reduced to
“one-step”
link prediction problems ([Sec. 4](#S4)).
(C2) We re-evaluate previous SoTA approaches ([Sec. 5](#S5)), revealing that neural link predictors are relying on memorized information from the training set.
Furthermore, we show that the reported hardness of queries involving unions is only apparent.
To have a better understanding of why performances are inflated, we introduce CQD-Hybrid ([Sec. 5.1](#S5.SS1)), a novel CQA model that combines classical graph-matching with neural link predictors, surpassing the SoTA on
existing
benchmarks.
(C3)
We create new benchmarks for CQA ([Sec. 6](#S6)), $\mathsf{FB15k237}$+$\mathsf{H}$ and $\mathsf{NELL995}$+$\mathsf{H}$ from $\mathsf{FB15k237}$ and $\mathsf{NELL995}$,
respectively,
and $\mathsf{ICEWS18}$+$\mathsf{H}$ from the temporal KG $\mathsf{ICEWS18}$ (Boschee et al., ), where validation and test
links are links that have been added to the KG
after those in the training, making it more challenging.
All these contain only irreducible queries, to which we add the even more challenging query types “4p” (a four-length path) and “4i” (a conjunction of four patterns).

## 2 KGs and Complex Query Answering

#### Knowledge graphs.

A KG is a graph-structured knowledge
base where knowledge about the world is encoded as relationships between entities.
More formally, a KG can be represented as a multi-relational graph $G=(\mathcal{E},\mathcal{R},\mathcal{T})$, where $\mathcal{E}$ is a set of entities, $\mathcal{R}$ is a set of relation names, and $\mathcal{T}\subseteq\mathcal{E}\times\mathcal{R}\times\mathcal{E}$ is a set of links or *triples*, where each triple $(s,p,o)\in\mathcal{T}$ represents a relationship of type $p\in\mathcal{R}$ between the subject $s\in\mathcal{E}$ and the object $o\in\mathcal{E}$ of the triple.
For instance, in a KG such as FreeBase (Bollacker et al., ), the fact that a movie such as “Spiderman 2” is distributed in Blue Ray can be stored into the triple $(\mathsf{Spiderman2},\mathsf{distributedVia},\mathsf{BlueRay})$ or equivalently
$(\mathsf{BlueRay},\mathsf{distributedVia}^{-1},\mathsf{Spiderman2})$ where $\mathsf{distributedVia}^{-1}$ denotes the inverse relation of $\mathsf{distributedVia}$.
[Fig. 1](#S1.F1) shows examples of fragments from the KG $\mathsf{FB15k237}$.

Complex Query Answering. The aim of CQA is to retrieve a set of possible answers to a logical query $q$ that poses conditions over entities and relation types in a KG.
Following the literature on CQA (Arakelyan et al., ), we consider the problem of answering logical queries with a single target variable ($T$), a set of constants including anchor entities ($a_{1},a_{2},\ldots,a_{k}\in\mathcal{E}$), given relation names ($r_{1},r_{2},\ldots,r_{n}\in\mathcal{R}$), and first-order logical operations that include conjunction $\wedge$, disjunction $\vee$ and existential quantification $\exists$.
In this work, we do not deal with queries involving negation; however, all of our considerations about the inflated performance of current benchmarks will also transfer to versions of these benchmarks that include them (Ren et al., ; Galkin et al., ).

Figure: Figure 2: Query structures we consider, adapted from Ren & Leskovec () and including path (p), intersection (i), union (u) structures. See [Sec. 2](#S2) for their logical formulation.
Refer to caption: /html/2410.12537/assets/x5.png

Different queries are categorized into different types based on the structure of their corresponding logical sentence (Xiong et al., ).
The idea behind this taxonomy is that queries of the same type share the same “hardness”, i.e., the level of difficulty to be answered
and different query types correspond to tasks that map to more or less complex reasoning tasks.
The simplest CQA task is link prediction (Bordes et al., ), i.e., answering a query of the form:

$$ $?T:(a_{1},r_{1},T),$ (1p) $$

that is, given an entity $a_{1}$ (e.g., $\mathsf{NYC}$) and a relation name $r_{1}$ (e.g., $\mathsf{locatedIn}^{-1}$), find the entity that when substituted to $T$ correctly matches the link in the KG (e.g., $\mathsf{Spiderman2}$, see [Fig. 1](#S1.F1)).
Instead of matching a single link, more complex queries involve matching sub-graphs in a KG (see [Fig. 2](#S2.F2)).
Xiong et al. () extend [1p](#S2.Ex2) queries, and ask questions that involve traversing sequential paths made of two or three links, i.e.,

$$ $\displaystyle?T:\exists V_{1}.(a_{1},r_{1},V_{1})\land(V_{1},r_{2},T),$ (2p) $\displaystyle?T:\exists V_{1},V_{2}.(a_{1},r_{1},V_{1})\land(V_{1},r_{2},V_{2})\land(V_{2},r_{3},T),$ (3p) $$

where $V_{1},V_{2}$ denote variables that need to be grounded into entities associated to nodes in the path.
Moreover, multiple ground entities can directly participate in a conjunction, e.g., in queries such as:

$$ $\displaystyle?T:(a_{1},r_{1},T)\land(a_{2},r_{2},T),$ (2i) $\displaystyle?T:(a_{1},r_{1},T)\land(a_{2},r_{2},T)\land(a_{3},r_{3},T),$ (3i) $$

which represent the intersection of the target entity sets defined over two ([2i](#S2.Ex5)) or three ([3i](#S2.Ex6)) links.
Path and intersection structures can be combined into more complex queries:
for example, the natural language expression for query [$q_{1}$](#S1.Ex1) can be formalized as the formula

$$ $?T:\exists V_{1}.(a_{1},r_{1},V_{1})\land(a_{2},r_{2},V_{1})\land(V_{1},r_{3},T),$ (2i1p) $$

involving one intersection followed by a one-length path.(^3^33In previous works (Ren et al., ) this query type was referred to as “ip”. We explicitly mention the number of steps involved in a path or conjunction, as this is a factor of complexity. Analogously, “pi”, “u” and “up” queries from Ren et al. () are now 1p2i, 2u and 2u1p.)
See also the example in [Fig. 1](#S1.F1).
By inverting the order of operations, we obtain the query type “1p2i”:

$$ $?T:\exists V_{1}.(a_{1},r_{1},V_{1})\land(V_{1},r_{2},T)\land(a_{2},r_{3},T).$ (1p2i) $$

Similarly to the introduction of conjunctions, we can consider disjunctions in queries, realizing the union query types which can be answered by matching one link or the other, such as

$$ $?T:(a_{1},r_{1},T)\lor(a_{2},r_{2},T),$ (2u) $$

or by combining the union with the previous query types, e.g., obtained by combining [2u](#S2.Ex9) and [1p](#S2.Ex2):

$$ $?T:\exists V_{1}.((a_{1},r_{1},V_{1})\lor(a_{2},r_{2},V_{1}))\land(V_{1},r_{2},T).$ (2u1p) $$

Note that despite their dissimilar syntaxes and the different sub-graphs defining possible solutions ([Fig. 2](#S2.F2)), the query type [2u](#S2.Ex9) should be as difficult as [1p](#S2.Ex2), as to answer the first it suffices to match a single link correctly.
Similarly, [2u1p](#S2.Ex10) is as complex as [2p](#S2.Ex3).
The fact that [2u](#S2.Ex9) and [2u1p](#S2.Ex10) are reported to be harder to solve in practice than [1p](#S2.Ex2) and [2p](#S2.Ex3) (Ren et al., ) is due to the way standard benchmarks are built, which we discuss in [Sec. 4](#S4), and the way in which CQA is evaluated, discussed next.

Standard evaluation.
Given a KG $G$ and a logical query $q$ from one of the types described above,
answering $q$
boils down to a graph matching problem (Hogan, ) if we assume that all the meaningful links are already in $G$.
Instead, if $G$ is incomplete, we will need to predict missing links while answering $q$.
Many ML approaches to CQA, reviewed in [Sec. 5](#S5), therefore assume a distribution over possible links (Loconte et al., ), requiring probabilistic reasoning.
To evaluate them, standard benchmarks such as $\mathsf{FB15k237}$ and $\mathsf{NELL995}$ artificially divide $G$ into $G_{\operatorname{train}}$ and $G_{\operatorname{test}}$, treating the triples in the latter as missing links.
This splitting process is done uniformly at random, a procedural choice that can alter the measured performance, as we discuss next.
CQA is generally treated as a ranking task,
counting how many true candidate answers to a query are ranked higher than non-answer ones.
Denoting the rank of a query answer pair $(q,t)$ by $\operatorname{rank}(q,t)$, the performance for each query type is calculated as the mean reciprocal rank (MRR), i.e.,

$$ $|\mathcal{Q}|^{-1}\sum\nolimits_{q\in\mathcal{Q},t\in\mathcal{E}_{q}}\left|\mathcal{E}_{q}\right|^{-1}\operatorname{rank}(q,t),$ (1) $$

where $\mathcal{Q}$ denotes the set of test queries of the considered type, and $\mathcal{E}_{q}$ is the set of candidate answer entities for each query $q\in\mathcal{Q}$.
This average, across queries and answers, assumes that every query answer pair having the same query type is equivalently hard, which is not the case.
In fact, we show that certain query answer pairs can be easier to retrieve if links from the training data leak into the model ([Fig. 1](#S1.F1)), and that the distribution of the query answer pairs in the existing benchmarks is very skewed towards those involving a single missing link ([Table 1](#S4.T1)).
Thus, computing [Eq. 1](#S2.E1) without understanding what is the benchmark distribution, distorts the perception of performance gains.

## 3 What is the real “Hardness” of CQA in incomplete KGs?

As discussed in the previous section, the perceived complexity of a query is related to the graph structure associated to its query type ([Fig. 2](#S2.F2)): queries containing more hops/existentially-quantified variables are more challenging, e.g., a [3p](#S2.Ex4) query is harder than a [2p](#S2.Ex3) query.
In this section, we give an alternative perspective on the difficulty of answering queries that take into account the information coming from the training data, and that might have leaked into a learned model.
We argue that predicting links that are truly missing, i.e., not accessible to a learned model, is actually what makes a query “hard”.
To do so, we formalize the notion of a reasoning tree for a query answer pair, and then define how we determine the practical hardness of a query answer pair.

Given a query $q$ and every answer set of candidate answers $t\in\mathcal{E}_{q}$ in its candidate set,
we define the
reasoning tree of each query answer pair $(q,t)$, as the directed acyclic graph starting from the anchor entities
of $q$
to the target entity $t$,
whose relational structure matches the query graph.
[Fig. 1](#S1.F1) provides examples of different reasoning trees for four different answers to the same query.
There, we highlight whether a link belongs to $G_{\text{train}}$ or not, i.e., it is a missing link.
We assess the hardness of each answer $t\in\mathcal{E}_{q}$, by analyzing the composition of the reasoning tree required to predict $t$.
As to answering a $(q,t)$ pair, multiple reasoning trees are possible, so we select the one with the smallest number of missing links and the fewest number of hops.

A $(q,t)$ pair is trivial if the answer $t$ can be entirely retrieved from $G_{\text{train}}$, i.e., there exists at least one reasoning tree where all the links in it are seen during training.
This type of answer does not need probabilistic inference and hence is filtered out from current CQA benchmarks (Ren & Leskovec, ), which only consider non-trivial $(q,t)$ pairs, which we call inference-based pairs.
However, inference-based pairs do not need all links in their reasoning tree to be predicted as, by definition, it is sufficient that at least one link in the tree is missing.
Therefore, we define a $(q,t)$ pair to be a partial-inference pair if its reasoning tree contains at least one link in $G_{\text{train}}$ and at least one link present in $G_{\text{test}}$.
Alternatively, a query answer pair whose reasoning tree contains only links present in $G_{\text{test}}$ is called a full-inference pair.
We claim that predicting an answer of a full-inference kind is harder than doing that for a partial-inference one, as discussed next.

To predict a partial-inference pair $(q,t)$, a ML model that has explicit access to $G_{\operatorname{train}}$ has to solve a simpler task to answer $q$, as only a subset of the links in the reasoning tree are missing and need to be predicted.
As such, the
$(q,t)$ pair can be simplified to $(q^{\prime},t)$ pair, where the query $q^{\prime}$ is of an easier query type than $q$.
[Fig. 1](#S1.F1) shows one example of how a query answer pairs of type [2i1p](#S2.Ex7) from $\mathsf{FB15k237}$ are reduced in practice to the simpler types [1p](#S2.Ex2), [2i](#S2.Ex5) and [2p](#S2.Ex3).
We will build our hybrid solver in [Sec. 5.1](#S5.SS1) leveraging this intuition.
Note that this advantage applies also to ML models that have implicit access to $G_{\operatorname{train}}$, e.g., by having memorized the triples during training, a common phenomenon for many neural link predictors (Nickel et al., ).
We confirm this in [Sec. 5](#S5), showing that the performance of all SoTA models for partial-inference pairs is comparable to the performance of full-inference pairs but of simpler types.
We next analyze how many partial vs full-inference queries the current benchmarks contain.

## 4 How Many “Complex” Queries in Current CQA Benchmarks?

In this section, we systematically analyze the practical hardness of queries from very popular CQA benchmarks and answer the following research question:
(RQ1) What is the proportion of query answer pairs that can be classified as full-inference rather than the easier partial-inference?

For this purpose, we consider the CQA benchmarks generated from the KG $\mathsf{FB15k237}$ (based on Freebase)
and $\mathsf{NELL995}$ (based on NELL systems (Carlson et al., ))
as
they are the most used to evaluate SoTA methods for CQA (Ren et al., ; Ren & Leskovec, ; Arakelyan et al., ; Zhang et al., ; Zhu et al., ; Arakelyan et al., ).(^4^44We do not consider $\mathsf{FB15k}$ (Bordes et al., ) as it suffers from data leakage (Toutanova & Chen, ).)

**Table 1: The great majority of query answer pairs are of the much easier partial-inference type (non-diagonal), rather than of the harder full-inference type (diagonal). For each query type (as rows) we show the percentage of the query answer pairs that can be reduced to an easier query type (as columns) for datasets $\mathsf{FB15k237}$ and $\mathsf{NELL995}$. Most of the complex queries can be reduced to simple link prediction queries (i.e., [1p](#S2.Ex2)). We denote as ‘-’ those reductions that are not possible given the sub-graph structure induced by the query type.**
|  | $\mathsf{FB15k237}$ | $\mathsf{NELL995}$ |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
|  | 1p | 2p | 3p | 2i | 3i | 1p2i | 2i1p | 2u | 2u1p | 1p | 2p | 3p | 2i | 3i | 1p2i | 2i1p | 2u | 2u1p |
| 1p | 100 | - | - | - | - | - | - | - | - | 100 | - | - | - | - | - | - | - | - |
| 2p | 98.1 | 1.9 | - | - | - | - | - | - | - | 97.6 | 2.4 | - | - | - | - | - | - | - |
| 3p | 97.2 | 2.7 | 0.1 | - | - | - | - | - | - | 95.6 | 4.3 | 0.1 | - | - | - | - | - | - |
| 2i | 96.0 | - | - | 4.0 | - | - | - | - | - | 94.0 | - | - | 6.0 | - | - | - | - | - |
| 3i | 91.6 | - | - | 8.2 | 0.2 | - | - | - | - | 87.4 | - | - | 12.1 | 0.5 | - | - | - | - |
| 1p2i | 86.8 | 1.0 | - | 12.0 | - | 0.2 | - | - | - | 49.5 | 0.6 | - | 49.0 | - | 0.9 | - | - | - |
| 2i1p | 96.7 | 1.8 | - | 1.4 | - | - | 0.1 | - | - | 96.2 | 2.4 | - | 1.2 | - | - | 0.2 | - | - |
| 2u | 0.0 | - | - | - | - | - | - | 100 | 0.0 | - | - | - | - | - | - | - | 100 | - |
| 2u1p | 98.3 | 0.0 | - | - | - | - | - | 1.6 | 0.1 | 98.5 | 0.0 | - | - | - | - | - | 1.4 | 0.1 |

Complex queries can be reduced to much simpler types.
We group the testing query answer pairs $(q,t)$ into query types ([Sec. 2](#S2)), and we further split them based on whether they can be reduced to simpler types after observing the training links in $G_{\operatorname{train}}$ ([Sec. 3](#S3)).
[Table 1](#S4.T1) shows that for both
$\mathsf{FB15k237}$ and $\mathsf{NELL995}$ the vast majority of $(q,t)$ pairs can be reduced to simpler types.
For $\mathsf{FB15k237}$, 86.8% to 98.3% of $(q,t)$ pairs can be reduced to [1p](#S2.Ex2) queries, while only 0.1% to 4% require full inference.
Similarly, for $\mathsf{NELL995}$, 49.5% to 98.5% of $(q,t)$ pairs map to [1p](#S2.Ex2) queries, and only 0.1% to 6% to full inference.
For instance, 96.7% of [2i1p](#S2.Ex7) $(q,t)$ pairs in $\mathsf{FB15k237}$ can be reduced to
[1p](#S2.Ex2) queries, 1.8% to
[2p](#S2.Ex3), and 1.4% to [2i](#S2.Ex5).
However, only 0.1% of these pairs cannot be reduced to any other $(q^{\prime},t)$ pair, i.e., they require full inference in order to be predicted.
The only exceptions to this trend are $(q,t)$ pairs where $q$ has a [1p](#S2.Ex2) or [2u](#S2.Ex9) structure which, by definition, only require the prediction of a single link
and therefore cannot be reduced by any other query type.

Non-existing links for union queries.
Additionally, we discovered that there are non-existing links, i.e., links that are not in the original KG $G$ and hence neither in $G_{\operatorname{train}}$ or $G_{\operatorname{test}}$, in both $\mathsf{FB15k237}$ and $\mathsf{NELL995}$ in the reasoning trees of queries involving unions, i.e., the [2u](#S2.Ex9) and [2u1p](#S2.Ex10) types.
[Fig. A.1](#A1.F1.11) shows some examples.
These links violate our definitions of inference ($q$, $t$) pairs, hence, we filter them out, and report only filtered $(q,t)$ pairs in [Table 1](#S4.T1).
More crucially, these non-existing links can alter the performance of solvers for [2u](#S2.Ex9) and [2u1p](#S2.Ex10) types, as we discuss in the next section.

**Table 2: SoTA performance drops significantly on full-inference query answer pairs. For each query type (rows), we show the MRR achieved by SoTA methods on full-inference query answer pairs only (diagonal), and compare it with the MRR achieved on all available testing queries (column “all”) and on the queries that can be reduced to simpler types (other columns). We highlight in bold how the best ranking model changes when we consider the full-inference query answer pairs only.**
|  |  | $\mathsf{FB15k237}$ |  | $\mathsf{NELL995}$ |  |  |  |  |  |  |  |  |  |  |  |  |  |  |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| Query type | method | all | 1p | 2p | 3p | 2i | 3i | 1p2i | 2i1p |  | all | 1p | 2p | 3p | 2i | 3i | 1p2i | 2i1p |
| 1p | GNN-QE | 42.8 | 42.8 | - | - | - | - | - | - |  | 53.6 | 53.6 | - | - | - | - | - | - |
| ULTRAQ | 40.6 | 40.6 | - | - | - | - | - | - |  | 38.9 | 38.9 | - | - | - | - | - | - |  |
| CQD | 46.7 | 46.7 | - | - | - | - | - | - |  | 60.4 | 60.4 | - | - | - | - | - | - |  |
| ConE | 41.8 | 41.8 | - | - | - | - | - | - |  | 60.0 | 60.0 | - | - | - | - | - | - |  |
| 2p | GNN-QE | 14.7 | 14.8 | 4.7 | - | - | - | - | - |  | 17.9 | 18.2 | 6.1 | - | - | - | - | - |
| ULTRAQ | 11.5 | 11.5 | 4.2 | - | - | - | - | - |  | 11.2 | 11.5 | 4.6 | - | - | - | - | - |  |
| CQD | 13.2 | 13.3 | 3.5 | - | - | - | - | - |  | 22.0 | 22.3 | 7.6 | - | - | - | - | - |  |
| ConE | 12.8 | 12.8 | 5.2 | - | - | - | - | - |  | 16.0 | 16.3 | 7.2 | - | - | - | - | - |  |
| 3p | GNN-QE | 11.8 | 12.0 | 4.4 | 4.8 | - | - | - | - |  | 15.2 | 15.1 | 8.1 | 3.4 | - | - | - | - |
| ULTRAQ | 8.9 | 9.0 | 4.6 | 4.4 | - | - | - | - |  | 9.7 | 9.8 | 5.1 | 4.1 | - | - | - | - |  |
| CQD | 7.8 | 7.8 | 3.4 | 1.8 | - | - | - | - |  | 13.4 | 12.8 | 7.8 | 8.5 | - | - | - | - |  |
| ConE | 11.0 | 11.0 | 5.4 | 2.6 | - | - | - | - |  | 13.8 | 13.8 | 8.2 | 6.5 | - | - | - | - |  |
| 2i | GNN-QE | 38.3 | 39.3 | - | - | 4.0 | - | - | - |  | 40.0 | 41.4 | - | - | 3.6 | - | - | - |
| ULTRAQ | 35.7 | 36.7 | - | - | 3.4 | - | - | - |  | 36.3 | 37.5 | - | - | 3.2 | - | - | - |  |
| CQD | 35.0 | 35.8 | - | - | 7.3 | - | - | - |  | 42.2 | 43.3 | - | - | 6.9 | - | - | - |  |
| ConE | 32.6 | 33.3 | - | - | 5.5 | - | - | - |  | 39.6 | 40.6 | - | - | 8.0 | - | - | - |  |
| 3i | GNN-QE | 54.1 | 56.0 | - | - | 10.9 | 5.2 | - | - |  | 50.9 | 53.6 | - | - | 10.9 | 2.2 | - | - |
| ULTRAQ | 51.0 | 52.9 | - | - | 9.7 | 4.3 | - | - |  | 47.7 | 50.0 | - | - | 11.3 | 1.5 | - | - |  |
| CQD | 48.5 | 49.6 | - | - | 17.0 | 6.0 | - | - |  | 51.8 | 53.9 | - | - | 14.4 | 3.6 | - | - |  |
| ConE | 47.3 | 48.3 | - | - | 15.6 | 4.0 | - | - |  | 50.2 | 51.9 | - | - | 18.3 | 4.8 | - | - |  |
| 1p2i | GNN-QE | 31.1 | 32.8 | 15.5 | - | 5.7 | - | 9.1 | - |  | 29.1 | 42.7 | 21.4 | - | 12.0 | - | 10.2 | - |
| ULTRAQ | 29.6 | 31.5 | 19.2 | - | 4.2 | - | 7.4 | - |  | 25.1 | 39.0 | 25.6 | - | 8.2 | - | 7.0 | - |  |
| CQD | 27.5 | 28.7 | 13.4 | - | 7.1 | - | 9.0 | - |  | 31.5 | 44.0 | 25.7 | - | 14.5 | - | 12.6 | - |  |
| ConE | 25.5 | 26.6 | 13.9 | - | 5.4 | - | 9.7 | - |  | 26.1 | 38.5 | 25.2 | - | 10.5 |  | 8.6 | - |  |
| 2i1p | GNN-QE | 18.9 | 19.2 | 8.2 | - | 6.2 | - | - | 3.4 |  | 20.5 | 20.8 | 16.3 | - | 14.6 | - | - | 20.7 |
| ULTRAQ | 18.6 | 18.9 | 8.5 | - | 5.1 | - | - | 8.1 |  | 15.6 | 16.5 | 9.5 | - | 9.6 | - | - | 11.4 |  |
| CQD | 20.7 | 21.0 | 10.5 | - | 6.7 | - | - | 7.6 |  | 25.8 | 25.9 | 21.2 | - | 26.3 | - | - | 23.6 |  |
| ConE | 14.0 | 13.8 | 9.7 | - | 12.8 | - | - | 5.6 |  | 17.6 | 17.7 | 16.4 | - | 25.7 | - | - | 19.5 |  |

## 5 How do SoTA Models Perform on Full-Inference Queries?

In this section, we re-evaluate a number of SoTA methods for CQA and answer to the following question: (RQ2) How do these approaches perform on partial-inference and full-inference query answer pairs?
Furthermore, we leverage our query hardness distinction ([Sec. 3](#S3)) to devise a model class that explicitly leverages the links stored in the training KG to solve CQA tasks.

**Table 3: Queries of type 2u are less hard than previously thought in terms of MRR by SoTA methods, with our filtered [2u](#S2.Ex9) queries having comparable performance to [1p](#S2.Ex2), as discussed in [Sec. 2](#S2), in contrast with the results of the [2u](#S2.Ex9) queries originally used ([2u](#S2.Ex9) all).**
| $\mathsf{FB15k237}$ | $\mathsf{NELL995}$ |  |  |  |  |  |  |
| --- | --- | --- | --- | --- | --- | --- | --- |
| method | 1p | 2u all | 2u filtered |  | 1p | 2u all | 2u filtered |
| GNN-QE | 42.8 | 16.2 | 40.7 |  | 53.6 | 15.4 | 34.8 |
| ULTRAQ | 40.6 | 13.2 | 33.6 |  | 38.9 | 10.2 | 21.3 |
| CQD | 46.7 | 17.6 | 32.7 |  | 60.4 | 19.9 | 35.9 |
| ConE | 41.8 | 14.9 | 29.9 |  | 60.0 | 14.9 | 28.2 |

SoTA CQA methods.

Over the years, a significant number of neural models have been proposed for solving the CQA task.
Guu et al. () propose compositional training for embedding methods to predict answers for path queries.
GQE (Hamilton et al., ) learns a geometric intersection operator to answer conjunctive queries in embedding space; this approach was later extended by Query2Box (Ren et al., ), BetaE (Ren & Leskovec, ), and GNN-QE (Zhu et al., ).
FuzzQE (Chen et al., ) improves embedding methods with t-norm fuzzy logic, which satisfies the axiomatic system of classical logic.
Some recent works such as HypE (Choudhary et al., ) and ConE (Zhang et al., ) use geometric interpretations of entity and relation embeddings to achieve desired properties for the logical operators.
Other solutions to CQA combine neural methods with symbolic algorithms.
For example, EmQL (Sun et al., ) ensembles an embedding model and a count-min sketch, and is able to find logically entailed answers, while CQD (Arakelyan et al., ; ) extends a pretrained knowledge graph embedding model to infer answers for complex queries.
In this work, we consider four representative approaches that significantly differ in their methodological designs and yield SoTA results compared to other models in their class.
We consider the following models:
(1) Cone Embeddings (ConE; Zhang et al., ) is a geometry-based complex query answering model where logical conjunctions and disjunctions are represented as intersections and union of cones.
(2) Graph Neural Network Query Executor (GNN-QE; Zhu et al., ) decomposes a complex first-order logic query into projections over fuzzy sets.
(3) Continuous Query Decomposition (CQD; Arakelyan et al., ; ), reduces the CQA task to the problem of finding the most likely variable assignment, where the likelihood of each link ([1p](#S2.Ex2) query) is assessed by a neural link predictor, and logical connectives are relaxed via fuzzy logic operators.
(4) UltraQuery (ULTRAQ; Galkin et al., ) is a foundation model for CQA inspired by Galkin et al. () where links and logical operations are represented by vocabulary-independent functions which can generalize to new entities and relation types in any KG.

SoTA methods perform significantly worse on full-inference queries.
We re-evaluate the SoTA methods mentioned above and stratify their performances based on the type of partial- and full-inference queries.
Where available, we reused the pre-trained models for their evaluation.
Otherwise, we re-produced the SoTA results using the hyperparameters provided by the authors, listed in
[Sec. C.1](#A3.SS1).
[Table 2](#S4.T2) presents the results in terms of MRR for the testing
query answer pairs
in the existing benchmarks $\mathsf{FB15k237}$ and $\mathsf{NELL995}$, along with the different $(q^{\prime},t)$ pairs they can be
simplified to when observing the training KG, grouped by each query type.
There, the performance of all SoTA methods consistently drops for query answer pairs that have a higher number of missing links in their reasoning tree.
Furthermore, [Table 2](#S4.T2) compares the MRR computed on all the available queries originally used in the benchmarks (column “all”), and the scores on those query types that they can be reduced to.
There is a high similarity in MRR between the columns “all” and “1p” that is evidence that the good performances of CQA methods are explained by their link prediction performances, as a very high percentage of queries in fact are reduced to [1p](#S2.Ex2) queries (see [Table 1](#S4.T1)).

However, in a few cases it happens that full-inference results are higher than some partial-inference; in such cases, the reason is to be found in the fact that full-inference $(q,t)$ pairs are very scarce (see [Table 1](#S4.T1)).
We rule out that this is due to the influence of the number of existing entities bounding to existential quantified variables.
For example we report such an analysis for CQD in [Figs. A.3](#A1.F3) and [B.2](#A2.F2). Moreover, we found that no anchor entities nor relation names is predominant in both benchmarks, as shown in [A.4](#A1.T4).

Non-existing links for union queries give a false sense of hardness.

We remark that for union queries, we filter query answer pairs, as discussed in [Sec. 4](#S4), removing those with non-existing links in their reasoning trees.
In [Table 3](#S5.T3), we show that if we do not do that, and consider also the pairs with non-existing links (denoted as “2u all”), MRR performance greatly drops.
In this way, we reproduce the low performance for [2u](#S2.Ex9) queries that the original SoTA baselines reported in their papers.
However, as [Table 3](#S5.T3) shows, this is just an artifact due to including non-filtered pairs while computing [Eq. 1](#S2.E1).
With our filtered pairs, instead, we recover the performance of [1p](#S2.Ex2) queries, as expected ([Sec. 2](#S2)).
Similar conclusions can be drawn for other union queries as reported in [Table A.1](#A1.T1).

### 5.1 Building an Hybrid Reasoner to Exploit Training Links

So far, we have assessed that current benchmarks are skewed towards easier query types ([Table 1](#S4.T1)) and thus the perceived progress of current SoTA CQA methods boils down to their performance on [1p](#S2.Ex2) queries ([Table 2](#S4.T2)).
To have an undistorted view of this progress, in the next section, we will devise a benchmark that allows to precisely measure model performance on full-inference queries only.
Nevertheless, we argue that in a real-world scenario one has to perform reasoning over both existing links and in the presence of missing ones.
Therefore, it is worth to evaluate CQA over partial-inference queries, however in a stratified analysis and accounting for the disproportion of [1p](#S2.Ex2) links (see [Sec. 4](#S4)).
Next, we discuss how to build an hybrid solver that exploits both link types.

Current SoTA CQA methods might implicitly exploit this aspect at test time if they are able to memorize well the entire training KG.
However, there is no guarantee that this is the case, especially for less parameterized models.
If one is interested in hybrid inference on real-world KGs, discarding the information in $G_{\operatorname{train}}$ is wasteful.
To this end, we build an hybrid CQA method that explicitly retrieves existing links from $G_{\operatorname{train}}$ when answering a query at test time.
To the best of our knowledge, this is the first time such an hybrid solver is proposed in the CQA literature.

Our hybrid solver, named CQD-Hybrid, is based on the variant of CQD that greedily answers a query by incremental search (Arakelyan et al., ).
As in CQD, a pre-trained link predictor(^5^55In our experiments we use ComplEx as it is a simple, robust and versatile predictor (Ruffinelli et al., ).) is used to compute scores for the answer entities of [1p](#S2.Ex2) queries only, denoting the unnormalized probability of that single link to exist (Loconte et al., ).
Then, assignments to existentially quantified variables in a complex query are greedily obtained by maximizing the combined score of the links, computed by replacing logical operators in the query with fuzzy ones (van Krieken et al., ).
A complete assignments to the variables (and hence to the target variable $T$), gives us an answer to the query.
In our CQD-Hybrid, we assign the maximum score to those links that are observed in $G_{\operatorname{train}}$.
That is, training links will have a higher score than the one that the link predictor would output, hence effectively steering the mentioned greedy procedure at test time.
We report hyperparameters and implementation details of CQD-Hybrid in [Sec. C.1](#A3.SS1).

This simple heuristics allows training links to be considered at test time.
By doing so we might add additional noise to the greedy search process in CQD-Hybrid.
In our experiments, however, we found CQD-Hybrid was consistently boosting performance in terms of MRR, as reported in [Table 4](#S5.T4), which shows aggregated performance for space reasons.
A stratified comparison is reported in the appendix in [Tables A.2](#A1.T2) and [A.3](#A1.T3).

**Table 4: Exploiting the links in the training KG during inference boosts MRR on existing benchmarks, as shown for our CQD-Hybrid model compared to previous SoTA, for several query types. CQD-Hybrid always achieves higher MRR scores when compared to CQD, and outperforms more sophisticated baselines 10/14 times. Best values in bold and second best underlined. For the stratified comparison of CQD-Hybrid with previous SoTA, please refer to the [Tables A.2](#A1.T2) and [A.3](#A1.T3).**
| Method | $\mathsf{FB15k237}$ | $\mathsf{NELL995}$ |  |  |  |  |  |  |  |  |  |  |  |  |  |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| 2p | 3p | 2i | 3i | 1p2i | 2i1p | 2u1p |  | 2p | 3p | 2i | 3i | 1p2i | 2i1p | 2u1p |  |
| GNN-QE | 14.7 | 11.8 | 38.3 | 54.1 | 31.1 | 18.9 | 9.7 |  | 17.9 | 15.2 | 40.0 | 50.9 | 29.1 | 20.5 | 8.8 |
| ULTRAQ | 11.5 | 8.9 | 35.7 | 51.0 | 29.6 | 18.6 | 7.3 |  | 11.2 | 9.7 | 36.3 | 47.7 | 25.1 | 15.6 | 8.4 |
| CQD | 13.2 | 7.8 | 35.0 | 48.5 | 27.5 | 20.7 | 10.5 |  | 22.0 | 13.4 | 42.2 | 51.8 | 31.5 | 25.8 | 16.0 |
| ConE | 12.8 | 11.0 | 32.6 | 47.3 | 25.5 | 14.0 | 7.4 |  | 16.0 | 13.8 | 39.6 | 50.2 | 26.1 | 17.6 | 11.1 |
| CQD-Hybrid (ours) | 15.0 | 11.0 | 37.6 | 52.7 | 31.2 | 24.0 | 10.3 |  | 23.8 | 17.8 | 44.2 | 57.8 | 33.2 | 28.4 | 16.6 |

Figure: Figure 3: MRR of SoTA on the new benchmarks (in orange) is significantly lower than the old ones (in blue). As expected from the hardness analysis presented in [Sec. 2](#S2), the performance on the new benchmark for [2u](#S2.Ex9) are similar to [1p](#S2.Ex2), and the one of [2u1p](#S2.Ex10) are similar to [2p](#S2.Ex3).
Refer to caption: /html/2410.12537/assets/x17.png

## 6 New Benchmarks for “Truly Complex” Query Answering

In this section, we answer to the following question: (RQ3) *How can we construct a set of CQA benchmarks that let us measure truly challenging queries?*
To do so, we present a new set of CQA benchmarks based on the previously used $\mathsf{FB15k237}$ and $\mathsf{NELL995}$, as well as a novel one we design out of temporal knowledge graph $\mathsf{ICEWS18}$ to question the current way to split the original KG $G$ into $G_{\operatorname{train}}$ and $G_{\operatorname{test}}$.
Then, we evaluate current SoTA methods on these new benchmarks as to establish a strong baseline for future works.

Building new CQA benchmarks.
We generate our benchmarks to comprise only full-inference question answer pairs, filtering out all partial-inference (and trivial) ones from the evaluation.
To this end, we modify the algorithm of Ren et al. () to ensure that no training links are present in the reasoning trees of any $(q,t)$ pair we generate.
To raise the bar of “complexity” in CQA, we introduce two query types that, in their full-inference versions, are harder than simpler types by design.
Specifically, we design “4p” queries, for a sequential path made of four links, i.e.,

$$ $?T:\exists V_{1},V_{2},V_{3}.(a_{1},r_{1},V_{1})\land(V_{1},r_{2},V_{2})\land(V_{2},r_{3},V_{3})\land(V_{3},r_{4},T),$ (4p) $$

and “4i”, which represents the intersection of the target entity sets defined over four links, i.e.

$$ $?T:(a_{1},r_{1},T)\land(a_{2},r_{2},T)\land(a_{3},r_{3},T)\land(a_{4},r_{4},T).$ (4i) $$

We name the harder versions of $\mathsf{FB15k237}$ and $\mathsf{NELL995}$, $\mathsf{FB15k237}$+$\mathsf{H}$ and $\mathsf{NELL995}$+$\mathsf{H}$, each comprising 50.000 full-inference test and validation $(q,t)$ pairs for all query types apart from [1p](#S2.Ex2) queries, for which we keep the same set of the old benchmark (this being already full-inference), and for the new types [4p](#S6.Ex11) and [4i](#S6.Ex12), for which we have 10.000 of them.
More details in [App. B](#A2).

Non-uniform at random splits.
For $\mathsf{FB15k237}$+$\mathsf{H}$ and $\mathsf{NELL995}$+$\mathsf{H}$, we keep the existing data splits of $G_{\operatorname{train}}$ and $G_{\operatorname{test}}$. However, to evaluate the impact of this artificial splitting process, we adopt a more realistic one for $\mathsf{ICEWS18}$+$\mathsf{H}$, where $G_{\operatorname{train}}$ contains present links and we might want to predict the future links contained in $G_{\operatorname{test}}$.
To this end, we leverage the temporal information in $\mathsf{ICEWS18}$ by (1) ordering the links based on their timestamp; (2) removing the temporal information, thus obtaining normal triples; and (3) selecting the train set to be the first temporally-ordered 80% of triples, the valid the next 10%, and the remaining to be the test split.
If the same fact appears with multiple temporal information, we retain only the link with the earliest timestamp.
For detailed statistics about the splits please refer to [App. D](#A4).

How do SoTA methods fare on our new benchmarks?
For $\mathsf{FB15k237}$+$\mathsf{H}$ and $\mathsf{NELL995}$+$\mathsf{H}$ we re-used the pre-trained models used for the experiments in [Sec. 4](#S4), while for the newly created $\mathsf{ICEWS18}$+$\mathsf{H}$ we trained GNN-QE, CQD and ConE from scratch.
As this is not necessary for ULTRAQ, being a zero-shot neural link prediction applicable to any KG, we re-used the checkpoint provided by the authors.
Hyperparameters of all models are in [Sec. C.2](#A3.SS2).

[Fig. 3](#S5.F3) reports the results of the selected baselines on the new benchmarks versus the old benchmarks.
The results on the new benchmark show consistency w.r.t the number of reasoning steps needed to predict an answer.
For example the MRR of the queries having type [3i](#S2.Ex6) is always lower than [2i](#S2.Ex5), which is also lower than [1p](#S2.Ex2). On the other hand, the performance of these query types for the old benchmarks did not follow this pattern, as [3i](#S2.Ex6) queries had in all cases better performance than [2i](#S2.Ex5), as true full-inference [3i](#S2.Ex6) queries were comprising only 0.1% of all answers ([Table 1](#S4.T1)).

[Table 5](#S6.T5) shows the results of the selected baselines on the new benchmarks, for all query types.
Note that there is no need for stratification on our new benchmarks.
Furthermore, we excluded our CQD-Hybrid baseline from this evaluation, as the usage of a hybrid model is pointless for full-inference $(q,t)$ pairs.
The surprising result from [Table 5](#S6.T5) is that CQD, which is the simplest baseline, relying only on a pre-trained link predictor, outperforms newer and more sophisticated methods in most cases.
Furthermore, we highlight how [2u](#S2.Ex9) queries have similar performance than [1p](#S2.Ex2), and [2u1p](#S2.Ex10) similar to [2p](#S2.Ex3), as expected from [Sec. 3](#S3).
Finally, we remark that $\mathsf{ICEWS18}$+$\mathsf{H}$ is much harder than $\mathsf{NELL995}$+$\mathsf{H}$ and $\mathsf{FB15k237}$+$\mathsf{H}$, across all query types, even [1p](#S2.Ex2), thus raising the for neural link predictors as well.
This confirms our hypothesis that the sampling method of the KG splits plays a big role in determining the hardness of the benchmark.

**Table 5: A simple baseline as CQD outperforms most CQA SoTA on the new benchmarks in terms of test MRR for different complex queries on $\mathsf{FB15k237}$+$\mathsf{H}$, $\mathsf{NELL995}$+$\mathsf{H}$ and $\mathsf{ICEWS18}$+$\mathsf{H}$.**
|  | Model | 1p | 2p | 3p | 2i | 3i | 1p2i | 2i1p | 2u | 2u1p | 4p | 4i |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| $\mathsf{FB15k237}$+$\mathsf{H}$ | GNN-QE | 42.8 | 6.5 | 4.2 | 10.3 | 10.3 | 4.6 | 7.8 | 36.9 | 7.2 | 3.8 | 13.2 |
| ULTRAQ | 40.6 | 5.5 | 3.7 | 8.2 | 7.9 | 4.1 | 7.9 | 33.8 | 5.1 | 3.4 | 10.8 |  |
| CQD | 46.7 | 6.3 | 2.7 | 18.4 | 16.2 | 5.6 | 9.4 | 34.9 | 7.3 | 1.1 | 16.5 |  |
| ConE | 41.8 | 5.7 | 3.9 | 16.8 | 13.9 | 4.0 | 6.6 | 25.9 | 5.3 | 3.3 | 13.1 |  |
| $\mathsf{NELL995}$+$\mathsf{H}$ | GNN-QE | 53.6 | 7.5 | 4.0 | 20.0 | 14.9 | 8.5 | 8.0 | 63.2 | 5.3 | 2.9 | 10.9 |
| ULTRAQ | 38.9 | 5.7 | 3.3 | 15.0 | 10.0 | 6.6 | 5.8 | 39.5 | 5.5 | 2.8 | 6.6 |  |
| CQD | 60.4 | 10.7 | 4.2 | 36.0 | 25.6 | 14.2 | 12.1 | 61.0 | 12.6 | 2.0 | 16.8 |  |
| ConE | 53.1 | 9.0 | 5.4 | 39.1 | 29.8 | 8.5 | 9.1 | 52.2 | 6.9 | 4.3 | 19.4 |  |
| $\mathsf{ICEWS18}$+$\mathsf{H}$ | GNN-QE | 4.3 | 0.8 | 0.3 | 3.3 | 1.9 | 2.4 | 3.3 | 9.7 | 0.7 | 0.3 | 1.1 |
| ULTRAQ | 4.0 | 1.2 | 0.9 | 2.9 | 1.5 | 2.2 | 1.1 | 4.2 | 1.0 | 0.7 | 0.8 |  |
| CQD | 9.2 | 2.8 | 1.2 | 6.1 | 3.3 | 4.4 | 6.5 | 8.6 | 4.9 | 1.1 | 1.7 |  |
| ConE | 7.0 | 0.7 | 0.4 | 2.8 | 0.8 | 1.2 | 0.9 | 5.7 | 0.5 | 0.3 | 0.3 |  |

## 7 Conclusion

In this paper, we revisit CQA on KGs and reveal that the “good” performance of SoTA approaches predominantly comes from answers that can be reduced to easier types ([Table 2](#S4.T2)), the vast majority of which boiling down to single link prediction ([Table 1](#S4.T1)).
We also propose an hybrid solver, CQD-Hybrid, that by combining classical graph matching approaches with neural query answering explicitly reduces query answer pairs to easier query types when existing links are available and therefore can surpass SoTA on old benchmarks.
We then created a set of new benchmarks $\mathsf{FB15k237}$+$\mathsf{H}$,$\mathsf{NELL995}$+$\mathsf{H}$ and $\mathsf{ICEWS18}$+$\mathsf{H}$ that only consider full-inference queries and are much more challenging for current SoTA approaches.
We consider them to be a stepping stone towards benchmarking truly complex reasoning with ML models.

However, both old and our new benchmarks only consider queries with bindings of single target variables.
While this reflects an important class of queries on real-world KGs, many real-world queries require bindings to multiple target variables (i.e. answer tuples).
We plan to extend our current study of the “real hardness” of CQA benchmarks to queries involving negation (Zhang et al., ), and to other popular settings in neural query answering, such as
inductive scenarios (Galkin et al., ) where some entities and/or relations are unseen during the test stage.

## Reproducibility Statement

We report the hyperparameter settings of all compared models in [App. C](#A3) . Our code and new benchmarks
will be made available upon acceptance.

## Author Contributions

AV, CG, and LL conceived the initial idea for which existing benchmarks were not hard enough for complex query answering.
AV, CG, DH, and LL had the intuition that a simple hybrid solver could obtain SoTA results on the old benchmarks.
BX, and CG found the issue with union queries. CG developed the necessary code, ran all the experiments, and plotted the figures, with the following exceptions: BX ran all the experiments involving ConE, LL contributed to the generation of the new benchmarks, specifically for the 4p and 4i queries, PM wrote the script for generating the KG splits of ICEWS18, AV drew Fig.1 and 2.
BX, and CG wrote the initial draft of the paper, while AV shaped the story line of the paper and helped with the writing.
All authors critically revised the paper.
AV, PM, and SS supervised all the phases of the project and gave feedback.

## Acknowledgements

AV was supported by the “UNREAL: Unified Reasoning Layer for Trustworthy ML” project (EP/Y023838/1) selected by the ERC and funded by UKRI EPSRC.
PM was partially funded by ELIAI (The Edinburgh Laboratory for Integrated Artificial Intelligence), EPSRC (grant no. EP/W002876/1), an industry grant from Cisco, and a donation from Accenture LLP.
CG was funded by SMARTY (grant no. 101140087).
BX was partially funded by the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) – SFB-1574 – 471687386.
DH was supported by the Deutsche Forschungsgemeinschaft (DFG): Germany’s Excellence Strategy – EXC 2120/1, GA 390831618 (RP20).

## Appendix A Additional analysis on the old benchmarks

Figure: Figure A.1: Some answers of union queries can be reached by a single missing link, while the other link does not exist as shown for this 2u query and fragments of the KG $\mathsf{FB15k237}$, where $r_{1}=\mathsf{releasedIn}$, $r_{2}=\mathsf{crewMemberOf}$. (Top) Example answer reachable by two missing links. (Bottom) Example answers only reachable by one missing link.
Refer to caption: /html/2410.12537/assets/x18.png

#### Additional comparisons

[Table A.3](#A1.T3) and [Table A.2](#A1.T2) show the full results of $\mathsf{FB15k237}$ and $\mathsf{NELL995}$, including the results comparing all methods, all query types, and the subtypes they are reduced to.

Moreover, [A.1](#A1.T1) show the full results of the union queries, including the old overall results, which includes $(q,t)$ pairs having non-existing links in their reasoning tree (see [Fig. A.1](#A1.F1.11)), and the “new overall”, in which those $(q,t)$ pairs are filtered out. In particular, for “up” queries, we observe that for $\mathsf{FB15k237}$, the full-inference queries have a higher MRR than the overall, while for $\mathsf{NELL995}$, we find the MRR results on full-inference$(q,t)$ pairs to be lower than the new overall results and then the partial inference$(q,t)$ pairs as expected. We attribute the results on $\mathsf{FB15k237}$ to the presence of bias in the $(q,t)$ pairs due to their scarcity in the benchmarks. We argue that for the same reason 2u1p performances are not comparable to 2p. However, we will show that on the new benchmark [Sec. 6](#S6) our claim is confirmed.

**Table A.1: Full inference “2u” $(q,t)$ pairs show higher performance than non-filtered, while full-inference “up” pairs show lower or comparable performance. Results on union queries for existing benchmarks and comparison between old and new overalls. ‘-’ refers to reductions that are not possible, while ‘/’ to reductions that are possible but that are not present in the data.**
| $\mathsf{FB15k237}$ | $\mathsf{NELL995}$ |  |  |  |  |  |  |  |  |  |  |  |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| Query type | method | overall | overall (new) | 1p | 2u | 2u1p |  | overall | overall (new) | 1p | 2u | 2u1p |
| 2u | GNN-QE | 16.2 | 40.7 | / | 40.7 | - |  | 15.4 | 34.8 | / | 34.8 | - |
| ULTRAQ | 13.2 | 33.6 | / | 33.6 | - |  | 10.2 | 21.3 | / | 21.3 | - |  |
| CQD | 17.6 | 32.7 | / | 32.7 | - |  | 19.9 | 35.9 | / | 35.9 | - |  |
| ConE | 14.3 | 29.9 | / | 29.9 | - |  | 14.9 | 28.2 | / | 28.2 | - |  |
| 2u1p | GNN-QE | 13.4 | 9.7 | 8.7 | 50.9 | 13.1 |  | 8.8 | 8.8 | 6.3 | 53.1 | 2.0 |
| ULTRAQ | 10.2 | 7.3 | 6.6 | 33.2 | 15.0 |  | 8.4 | 7.0 | 6.6 | 37.1 | 6.5 |  |
| CQD | 11.3 | 10.5 | 10.4 | 13.7 | 14.7 |  | 16.0 | 14.6 | 14.2 | 51.8 | 9.5 |  |
| ConE | 10.6 | 7.4 | 7.0 | 20.3 | 11.9 |  | 11.1 | 7.0 | 9.4 | 43.2 | 4.0 |  |

**Table A.2: Comparison of MRR scores for SOTA methods for the different sub-type queries of NELL can be reduced to. Best in bold and second best underlined.**
| Query type | method | overall | 1p | 2p | 3p | 2i | 3i | 1p2i | 2i1p | 2u | 2u1p |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| 1p | GNN-QE | 53.6 | 53.6 | - | - | - | - | - | - | - | - |
|  | ULTRA-query | 38.9 | 38.9 | - | - | - | - | - | - | - | - |
|  | ConE | 60.0 | 60.0 | - | - | - | - | - | - | - | - |
|  | CQD | 60.4 | 60.4 | - | - | - | - | - | - | - | - |
|  | CQD-hybrid | 60.4 | 60.4 | - | - | - | - | - | - | - | - |
| 2p | GNN-QE | 17.9 | 18.2 | 6.1 | - | - | - | - | - | - | - |
|  | ULTRA-query | 11.2 | 11.5 | 4.6 | - | - | - | - | - | - | - |
|  | ConE | 16.0 | 16.3 | 7.2 | - | - | - | - | - | - | - |
|  | CQD | 22.0 | 22.3 | 7.6 | - | - | - | - | - | - | - |
|  | CQD-hybrid | 23.8 | 24.2 | 6.2 | - | - | - | - | - | - | - |
| 3p | GNN-QE | 15.2 | 15.1 | 8.1 | 3.4 | - | - | - | - | - | - |
|  | ULTRA-query | 9.7 | 9.8 | 5.1 | 4.1 | - | - | - | - | - | - |
|  | ConE | 13.8 | 13.8 | 8.2 | 6.5 | - | - | - | - | - | - |
|  | CQD | 13.4 | 12.8 | 7.8 | 8.5 | - | - | - | - | - | - |
|  | CQD-hybrid | 17.8 | 17.2 | 9.9 | 8.1 | - | - | - | - | - | - |
| 2i | GNN-QE | 40.0 | 41.4 | - | - | 3.6 | - | - | - | - | - |
|  | ULTRA-query | 36.3 | 37.5 | - | - | 3.2 | - | - | - | - | - |
|  | ConE | 39.6 | 40.6 | - | - | 8.0 | - | - | - | - | - |
|  | CQD | 42.2 | 43.3 | - | - | 6.9 | - | - | - | - | - |
|  | CQD-hybrid | 44.2 | 45.7 | - | - | 6.7 | - | - | - | - | - |
| 3i | GNN-QE | 50.9 | 53.6 | - | - | 10.9 | 2.2 | - | - | - | - |
|  | ULTRA-query | 47.7 | 50.0 | - | - | 11.3 | 1.5 | - | - | - | - |
|  | ConE | 50.2 | 51.9 | - | - | 18.3 | 4.8 | - | - | - | - |
|  | CQD | 51.8 | 53.9 | - | - | 14.4 | 3.6 | - | - | - | - |
|  | CQD-hybrid | 57.8 | 61.6 | - | - | 10.7 | 2.5 | - | - | - | - |
| 1p2i | GNN-QE | 29.1 | 42.7 | 21.4 | - | 12.0 | - | 10.2 | - | - | - |
|  | ULTRA-query | 25.1 | 39.0 | 25.6 | - | 8.2 | - | 7.0 | - | - | - |
|  | ConE | 26.1 | 38.5 | 25.2 | - | 10.5 | - | 8.6 | - | - | - |
|  | CQD | 31.5 | 44.0 | 25.7 | - | 14.5 | - | 12.6 | - | - | - |
|  | CQD-hybrid | 33.2 | 48.7 | 24.2 | - | 13.7 | - | 9.4 | - | - | - |
| 2i1p | GNN-QE | 20.5 | 20.8 | 16.3 | - | 14.6 | - | - | 20.7 | - | - |
|  | ULTRA-query | 15.6 | 16.5 | 9.5 | - | 9.6 | - | - | 11.4 | - | - |
|  | ConE | 17.6 | 17.7 | 16.4 | - | 25.7 | - | - | 19.5 | - | - |
|  | CQD | 25.8 | 25.9 | 21.2 | - | 26.3 | - | - | 23.6 | - | - |
|  | CQD-hybrid | 28.4 | 28.9 | 20.4 | - | 22.8 | - | - | 23.3 | - | - |
| 2u | GNN-QE | 34.8 | - | - | - | - | - | - | - | 34.8 | - |
|  | ULTRA-query | 21.3 | - | - | - | - | - | - | - | 21.3 | - |
|  | ConE | 28.2 | - | - | - | - | - | - | - | 28.2 | - |
|  | CQD | 35.9 | - | - | - | - | - | - | - | 35.9 | - |
|  | CQD-hybrid | 35.9 | - | - | - | - | - | - | - | 35.9 | - |
| 2u1p | GNN-QE | 8.8 | 6.3 | - | - | - | - | - | - | 53.1 | 2.0 |
|  | ULTRA-query | 8.4 | 6.6 | - | - | - | - | - | - | 37.1 | 6.5 |
|  | ConE | 7.0 | 9.4 | - | - | - | - | - | - | 43.2 | 4.0 |
|  | CQD | 16.0 | 14.2 | - | - | - | - | - | - | 51.8 | 9.5 |
|  | CQD-hybrid | 16.6 | 14.5 | - | - | - | - | - | - | 53.5 | 9.6 |

**Table A.3: Comparison of MRR scores for SOTA methods for the different sub-type queries of FB15k-237 can be reduced to.**
| Query type | method | overall | 1p | 2p | 3p | 2i | 3i | 1p2i | 2i1p | 2u | 2u1p |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| 1p | GNN-QE | 42.8 | 42.8 | - | - | - | - | - | - | - | - |
|  | ULTRA-query | 40.6 | 40.6 | - | - | - | - | - | - | - | - |
|  | ConE | 41.8 | 41.8 | - | - | - | - | - | - | - | - |
|  | CQD | 46.7 | 46.7 | - | - | - | - | - | - | - | - |
|  | CQD-hybrid | 46.7 | 46.7 | - | - | - | - | - | - | - | - |
| 2p | GNN-QE | 14.7 | 14.8 | 4.7 | - | - | - | - | - | - | - |
|  | ULTRA-query | 11.5 | 11.5 | 4.2 | - | - | - | - | - | - | - |
|  | ConE | 12.8 | 12.8 | 5.2 | - | - | - | - | - | - | - |
|  | CQD | 13.2 | 13.3 | 3.5 | - | - | - | - | - | - | - |
|  | CQD-hybrid | 15.0 | 15.2 | 3.5 | - | - | - | - | - | - | - |
| 3p | GNN-QE | 11.8 | 12.0 | 4.4 | 4.8 | - | - | - | - | - | - |
|  | ULTRA-query | 8.9 | 9.0 | 4.6 | 4.4 | - | - | - | - | - | - |
|  | ConE | 11.0 | 11.0 | 5.4 | 2.6 | - | - | - | - | - | - |
|  | CQD | 7.8 | 7.8 | 3.4 | 1.8 | - | - | - | - | - | - |
|  | CQD-hybrid | 11.0 | 11.1 | 3.6 | 4.4 | - | - | - | - | - | - |
| 2i | GNN-QE | 38.3 | 39.3 | - | - | 4.0 | - | - | - | - | - |
|  | ULTRA-query | 35.7 | 36.7 | - | - | 3.4 | - | - | - | - | - |
|  | ConE | 32.6 | 33.3 | - | - | 5.5 | - | - | - | - | - |
|  | CQD | 35.0 | 35.8 | - | - | 7.3 | - | - | - | - | - |
|  | CQD-hybrid | 37.6 | 38.7 | - | - | 3.8 | - | - | - | - | - |
| 3i | GNN-QE | 54.1 | 56.0 | - | - | 10.9 | 5.2 | - | - | - | - |
|  | ULTRA-query | 51.0 | 52.9 | - | - | 9.7 | 4.3 | - | - | - | - |
|  | ConE | 47.3 | 48.3 | - | - | 15.6 | 4.0 | - | - | - | - |
|  | CQD | 48.5 | 49.6 | - | - | 17.0 | 6.0 | - | - | - | - |
|  | CQD-hybrid | 52.7 | 54.8 | - | - | 9.9 | 4.6 | - | - | - | - |
| 1p2i | GNN-QE | 31.1 | 32.8 | 15.5 | - | 5.7 | - | 9.1 | - | - | - |
|  | ULTRA-query | 29.6 | 31.5 | 19.2 | - | 4.2 | - | 7.4 | - | - | - |
|  | ConE | 25.5 | 26.6 | 13.9 | - | 5.4 | - | 9.7 | - | - | - |
|  | CQD | 27.5 | 28.7 | 13.4 | - | 7.1 | - | 9.0 | - | - | - |
|  | CQD-hybrid | 31.2 | 33.4 | 14.8 | - | 4.8 | - | 7.0 | - | - | - |
| 2i1p | GNN-QE | 18.9 | 19.2 | 8.2 | - | 6.2 | - | - | 3.4 | - | - |
|  | ULTRA-query | 18.6 | 18.9 | 8.5 | - | 5.1 | - | - | 8.1 | - | - |
|  | ConE | 14.0 | 13.8 | 9.7 | - | 12.8 | - | - | 5.6 | - | - |
|  | CQD | 20.7 | 21.0 | 10.5 | - | 6.7 | - | - | 7.6 | - | - |
|  | CQD-hybrid | 24.0 | 24.6 | 10.0 | - | 4.6 | - | - | 7.5 | - | - |
| 2u | GNN-QE | 40.7 | - | - | - | - | - | - | - | 40.7 | - |
|  | ULTRA-query | 33.6 | - | - | - | - | - | - | - | 33.6 | - |
|  | ConE | 29.9 | - | - | - | - | - | - | - | 29.9 | - |
|  | CQD | 32.7 | - | - | - | - | - | - | - | 32.7 | - |
|  | CQD-hybrid | 32.7 | - | - | - | - | - | - | - | 32.7 | - |
| 2u1p | GNN-QE | 9.7 | 8.7 | - | - | - | - | - | - | 50.9 | 13.1 |
|  | ULTRA-query | 7.3 | 6.6 | - | - | - | - | - | - | 33.2 | 15.0 |
|  | ConE | 7.4 | 7.0 | - | - | - | - | - | - | 20.3 | 11.9 |
|  | CQD | 10.5 | 10.4 | - | - | - | - | - | - | 13.7 | 14.7 |
|  | CQD-hybrid | 10.3 | 10.0 | - | - | - | - | - | - | 18.5 | 13.6 |

#### Influence of intermediate existing entities on the results

For query types having intermediate variables, such as ”2p”, ”3p”, ”pi”, ”ip”, and ”up”, we analyzed the number of existing intermediate entities matching the intermediate variables (existentially quantified variables) could influence the results.
We refer to this number as “cardinality of existing entities”.
For example, in [Fig. 1](#S1.F1) the entities ”When in Rome” and ”Spiderman 2” are existing intermediate entities for the query [$q_{1}$](#S1.Ex1).
The intuition is that while the presence of some of these entities might simplify the query answering [Sec. 3](#S3), at test time we do not know which entity leads to a reduction and which does not, as we do not have access to the test data. Hence, as we claim that the existing models memorize the training data [Sec. 5](#S5), we argue that a high value of cardinality must lead to lower performance, as those entities would act as noise for the models, hindering its capability of predicting the correct answers higher in the ranking.

To support our claim, we analyze the percentage of $(q,t)$ pairs having different values of cardinality, namely “0”, “1”, from “2” to “9”, from “10” to ”99”, more than 100 (“100+”), shown in [Fig. A.3](#A1.F3) both for partial-inference and full-inference$(q,t)$ pairs, and their MRR, using CQD (Arakelyan et al., ), shown in [Fig. A.3](#A1.F3).
Both [Figs. A.3](#A1.F3) and [A.3](#A1.F3) have bar charts for partial-inference (blue), and full-inference (orange)$(q,t)$ pairs for the difference cardinality categories,
[Fig. A.3](#A1.F3) shows that CQD is highly influenced by the value of cardinality having decreasing performance at the increase of the cardinality. Note that by matching this plot with the one in [Fig. A.3](#A1.F3), one can understand if the result on a specific query type are highly influenced by a high proportion of $(q,t)$ pairs having the same cardinally. For example, the MRR of [2u1p](#S2.Ex10) full-inference $(q,t)$ pairs in FB15k-237 is highly influenced by the presence of about 50% of $(q,t)$ pairs having cardinality of “0”.

This additional analysis shows that there is an additional level of “hardness” that can be considered when designing a benchmark or evaluating a model.

Figure: Figure A.2: Higher cardinality of intermediate existing entities leads to lower MRR. Influence of the number of existing intermediate variables on the MRR for datasets $\mathsf{FB15k237}$ and $\mathsf{NELL995}$, using CQD.
Refer to caption: /html/2410.12537/assets/x21.png

#### Imbalances of relation names and anchor nodes

Next, we check if there is some imbalances in both relation names and anchors. Note that if a relation name or an anchor entity is present multiple times in a query, this is counted only once. As shown in [Table A.4](#A1.T4), for $\mathsf{FB15k237}$ and $\mathsf{NELL995}$ we find that in most cases there is no predominant relation name nor anchor entity. However, there are exceptions, as for 3i queries of $\mathsf{FB15k237}$, where the anchor node “USA” is present in 30.1% of them, and for 2u queries, where it is present in 22.5%. We also notice that there is a predominance of USA as an anchor entity across the vast majority of query types, which is most likely given by the vast presence of this entity in the knowledge graph.

**Table A.4: There is no significant unbalancement in anchor nor relation names for each query type . Most frequent relation name and anchor per query type in the old benchmarks. Highest value in bold.**
| Query | relation name | frequency(%) | anchor entity | frequency(%) |
| --- | --- | --- | --- | --- |
| $\mathsf{FB15k237}$ |  |  |  |  |
| 1p | film_release_region^-1 | 3.7 | USA | 0.7 |
| 2p | location/location/contains | 7.8 | USA | 4.0 |
| 3p | location/location/contains | 10.5 | USA | 3.3 |
| 2i | people/person/profession^-1 | 16.3 | USA | 16.4 |
| 3i | people/person/gender^-1 | 18.7 | USA | 30.1 |
| pi | people/person/gender^-1 | 13.4 | USA | 14.1 |
| ip | people/person/profession^-1 | 7.8 | US dollars | 5.7 |
| 2u | film/film/language^-1 | 14.6 | USA | 22.5 |
| up | taxonomy_entry/taxonomy^-1 | 9.9 | /m/08mbj5d | 5.4 |
| $\mathsf{NELL995}$ |  |  |  |  |
| 1p | concept:atdate | 6.6 | concept_stateorprovince_california | 0.5 |
| 2p | concept:proxyfor^-1 | 5.5 | concept_lake_new | 1.5 |
| 3p | concept:proxyfor^-1 | 11.9 | concept_book_new | 2.5 |
| 2i | concept:atdate^-1 | 21.6 | concept_book_new | 7.6 |
| 3i | concept:atdate^-1 | 21.1 | concept_company_pbs | 12.0 |
| pi | concept:proxyfor^-1 | 9.6 | concept_book_new | 6.1 |
| ip | concept:subpartof^-1 | 7.0 | concept_athlete_sinorice_moss | 3.8 |
| 2u | concept:atdate^-1 | 10.4 | concept_company_pbs | 4.9 |
| up | concept:subpartof^-1 | 8.5 | concept_athlete_sinorice_moss | 3.3 |

## Appendix B Additional Analysis on the new benchmarks

#### Influence of intermediate existing entities on the results

Similar to what was done for the old benchmarks in [App. A](#A1), we analyze the proportion and influence (on the MRR) of the number of intermediate existing entities for CQD, on the new benchmarks $\mathsf{FB15k237}$+$\mathsf{H}$, $\mathsf{NELL995}$+$\mathsf{H}$, $\mathsf{ICEWS18}$+$\mathsf{H}$.
[Fig. B.2](#A2.F2) show a very similar result to the one in [Fig. A.3](#A1.F3), showing a decreasing MRR at the increase of the value of cardinality for all benchmarks. On the other hand the proportions of the full-inference $(q,t)$ pairs on the new benchmarks [Fig. B.2](#A2.F2) are quite different than the one shown in [Fig. A.3](#A1.F3), having in general an higher number of $(q,t)$ pairs with cardinality “0”. Nevertheless, the overall MRR on those query types on the new benchmark is much lower than the one on the old [Fig. 3](#S5.F3), showing that the “hardness” of a $(q,t)$ pair is mainly defined by (1) number of hops/number of reasoning steps, (2) being of type partial-inference or full-inference.

Figure: Figure B.1: Higher cardinality of intermediate existing entities leads to lower MRR. Influence of the number of existing intermediate variables on the MRR for datasets $\mathsf{FB15k237}$+$\mathsf{H}$, $\mathsf{NELL995}$+$\mathsf{H}$, $\mathsf{ICEWS18}$+$\mathsf{H}$, using CQD.
Refer to caption: /html/2410.12537/assets/x23.png

**Table B.1: The new benchmarks are generated such that anchors and relation names cannot appear more than 20% in each query type.Most frequent relation name and anchor per query type in the new benchmarks.**
| Query | relation name | frequency(%) | anchor entity | frequency(%) |
| --- | --- | --- | --- | --- |
| $\mathsf{FB15k237}$+$\mathsf{H}$ |  |  |  |  |
| 1p | film_release_region^-1 | 3.7 | USA | 0.7 |
| 2p | marriage/type_of_union^-1 | 19.7 | American english | 1.1 |
| 3p | people/person/nationality^-1 | 14.4 | Hartford | 1.2 |
| 2i | film_release_region^-1 | 10.2 | USA | 4.6 |
| 3i | people/person/profession^-1 | 11.8 | USA | 9.2 |
| pi | people/marriage/type_of_union^-1 | 19.6 | USA | 20.0 |
| ip | webpage/category^-1 | 20.0 | /m/02s9vc | 3.5 |
| 2u | film_release_region^-1 | 10.4 | USA | 4.7 |
| up | webpage/category^-1 | 20.0 | /m/02s9vc | 4.9 |
| 4p | people/person/profession^-1 | 19.3 | Hartford | 3.0 |
| 4i | people/person/profession^-1 | 18.6 | USA | 19.4 |
| $\mathsf{NELL995}$+$\mathsf{H}$ |  |  |  |  |
| 1p | concept:atdate | 6.6 | concept_stateorprovince_california | 0.5 |
| 2p | concept:proxyfor^-1 | 16.3 | concept_book_things | 0.6 |
| 3p | concept:proxyfor^-1 | 19.8 | concept_lake_new | 0.7 |
| 2i | concept:atdate^-1 | 10.2 | concept_lake_new | 1.9 |
| 3i | concept:atdate^-1 | 15.1 | concept_lake_new | 3.7 |
| pi | concept:proxyfor^-1 | 18.7 | concept_book_new | 17.4 |
| ip | concept:proxyfor^-1 | 19.4 | concept_lake_new | 9.7 |
| 2u | concept:atdate^-1 | 10.1 | concept_lake_new | 1.9 |
| up | concept:proxyfor^-1 | 18.3 | concept_lake_new | 6.8 |
| 4p | concept:proxyfor^-1 | 20.0 | concept_stateorprovince_colorado | 1.5 |
| 4i | concept:atdate^-1 | 20.0 | concept_date_n2004 | 8.0 |
| $\mathsf{ICEWS18}$+$\mathsf{H}$ |  |  |  |  |
| 1p | Make statement^-1 | 11.12 | USA | 3.0 |
| 2p | Make Statement^-1 | 19.9 | United Stated | 3.4 |
| 3p | Make Statement^-1 | 19.9 | Saudi Arabia | 2.7 |
| 2i | Consult^-1 | 16.4 | Citizen (India) | 3.2 |
| 3i | Consult^-1 | 20.0 | Turkey | 5.5 |
| pi | Make statement^-1 | 18.8 | United States | 7.4 |
| ip | Make statement^-1 | 19.9 | Saudi Arabia | 5.3 |
| 2u | Consult^-1 | 16.5 | Citizien (India) | 3.1 |
| up | Make statement^-1 | 20.0 | Saudi Arabia | 5.4 |
| 4p | Make statement | 19.8 | Saudi Arabia | 2.9 |
| 4i | Consult | 20.0 | Turkey | 8.4 |

#### Imbalances of relation names and anchor nodes

When creating the new benchmarks $\mathsf{FB15k237}$+$\mathsf{H}$, $\mathsf{NELL995}$+$\mathsf{H}$, $\mathsf{ICEWS18}$+$\mathsf{H}$, to make sure that no anchor entities nor relation name was predominant in each query type, we set a maximum of 20% frequency for both anchor entities and relation names accross all benchmarks and query type, as shown in [Table B.1](#A2.T1)

## Appendix C Hyperparameters

In this section we detail the hyperparameters used for each dataset and model.

### C.1 Old benchmarks

#### GNN-QE

We did not tune hyperparameters, but re-used the ones provided in the official repo. (^6^66https://github.com/DeepGraphLearning/GNN-QE/tree/master/config)

#### ULTRA

We did not tune hyperparameters, but re-used the ones provided in the official repo.(^7^77https://github.com/DeepGraphLearning/ULTRA/tree/main/config/ultraquery)

#### CQD

As mentioned in [Sec. 5](#S5), we re-used the pre-trained link predictor (Trouillon et al., ) provided by the authors.(^8^88https://github.com/Blidge/KGReasoning/) However, we tuned CQD-specific hyperparameters, namely the CQD beam “k”, ranging from [2,512] and the t-norm type being “prod” or “min”
In [Table C.1](#A3.T1) we provide the hyperparameter selection for the old benchmarks $\mathsf{FB15k237}$ and $\mathsf{NELL995}$. Also note that we normalize scores with min-max normalization.

**Table C.1: CQD hyperparameters old benchmarks. tn = tnorm. p=prod, m=min. Note that for 1p neither the k nor the tnorm are needed.**
| Dataset | 2p | 3p | 2i | 3i | 1p2i | 2i1p | 2u | up |  |  |  |  |  |  |  |  |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| k | tn | k | tn | k | tn | k | tn | k | tn | k | tn | k | tn | k | tn |  |
| $\mathsf{FB15k237}$ | 512 | p | 8 | p | 128 | p | 128 | p | 256 | p | 64 | p | 512 | m | 512 | m |
| $\mathsf{NELL995}$ | 512 | p | 2 | p | 2 | p | 2 | p | 256 | p | 256 | p | 512 | m | 512 | m |

#### ConE

We did not tune hyperparameters but re-used the ones provided in the official repo. (^9^99https://github.com/MIRALab-USTC/QE-ConE/blob/main/scripts.sh)

#### CQD-Hybrid

For CQD-Hybrid, to make the comparison with CQD fair, we re-used the hyperparameters found for CQD and fixed an upper bound value for the CQD beam “k” to 512, even when there are more existing entities matching the existentially quantified variables, to match the upper bound of the “k” used for CQD. Additionally, the scores of the pre-trained link predictor are normalized between $[0,0.9]$ using min-max normalization, and a score of $1$ is assigned to the existing triples.

### C.2 New benchmarks

For $\mathsf{FB15k237}$+$\mathsf{H}$ and $\mathsf{NELL995}$+$\mathsf{H}$, we re-used the same models trained for the old benchmarks, and using the same hyperparameters presented in [Sec. C.1](#A3.SS1).
Instead, for the new benchmark $\mathsf{ICEWS18}$+$\mathsf{H}$ we trained every model. The used hyperparameters for each model are presented in the following:

#### GNN-QE

For GNN-QE, we tuned the following hyperparameters: (1) batchsize, with values 8 or 48, and concat hidden being True or False, while the rest are the same used for the old benchmarks and do not change across benchmarks.
For $\mathsf{ICEWS18}$+$\mathsf{H}$ the best hyperparameters are “batchsize=48” and “concat hidden=True”.

#### ULTRAQ

Being a zero-shot neural link predictor, we re-used the same checkpoint provided in the official repo, as for [C.1](#A3.SS1).

#### CQD

For $\mathsf{NELL995}$+$\mathsf{H}$ and $\mathsf{FB15k237}$+$\mathsf{H}$ we re-used the pre-trained link-predictor and the same hyperparameters found for the old benchmarks [C.1](#A3.T1). Instead, for the newly created $\mathsf{ICEWS18}$+$\mathsf{H}$, we train ComplEx Trouillon et al. () link predictor with hyperparameters “regweight” 0.1 or 0.01, and batch size 1000 or 2000, with the best being, respectively 0.1 and 1000. Moreover, in [C.2](#A3.T2) are shown the hyperparameters for CQD on the new benchmark $\mathsf{ICEWS18}$+$\mathsf{H}$.

**Table C.2: CQD hyperparameters new $\mathsf{ICEWS18}$+$\mathsf{H}$ benchmark. tn = tnorm. p=prod, m=min**
| Dataset | 2p | 3p | 2i | 3i | 1p2i | 2i1p | 2u | up | 4i | 4p |  |  |  |  |  |  |  |  |  |  |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| k | tn | k | tn | k | tn | k | tn | k | tn | k | tn | k | tn | k | tn | k | tn | k | tn |  |
| $\mathsf{ICEWS18}$+$\mathsf{H}$ | 32 | p | 2 | p | 2 | p | 2 | p | 512 | p | 256 | p | 2 | m | 2 | m | 2 | p | 2 | p |

#### ConE

We re-used the same hyperparameters of $\mathsf{NELL995}$ for $\mathsf{ICEWS18}$+$\mathsf{H}$.

## Appendix D Knowledge graphs statistics

The statistics, i.e., number of entities, relation names, training/validation/test links, of the knowledge graphs used in this paper are shown in [Table D.1](#A4.T1).

**Table D.1: Statistics of knowledge graphs used to generate complex queries**
| Dataset | Entities | Relation Names | Training Links | Validation Links | Test Links | Total Links |
| --- | --- | --- | --- | --- | --- | --- |
| $\mathsf{FB15k237}$ | 14,505 | 237 | 272,115 | 17,526 | 20,438 | 310,079 |
| $\mathsf{NELL995}$ | 63,361 | 200 | 114,213 | 14,324 | 14,267 | 142,804 |
| $\mathsf{ICEWS18}$+$\mathsf{CQ}$ (new) | 20,840 | 250 | 213,304 | 25,048 | 24,689 | 263,041 |

## Peer Reviews

confidence: 4
contribution: 2
initial_rating: 3
presentation: 4
questions: Please respond to my two concerns in the weakness part.
soundness: 2
strengths: - This paper conducts an in-depth study of existing benchmarks and reveals biases regarding tree-shaped queries and union operators in several datasets.
summary: This manuscript presents a data-level study of knowledge graph complex query answering. The main argument is that the query-target pairs in existing datasets (q, t) can be somehow reduced to the easier ones (sub(q), t) if the required triple can be found in training KG. Therefore, the paper proposes to focus on the irreducible query answer pairs and empirically examine that the performance of all existing methods will drop significantly. The facts revealed above motivate a search approach highlighted by letting the edges in the train graph be memorized. The performance of the approach is compared against previous works on old and new benchmarks.

---

## Retrospective summary after the rebuttal period.

This author-reviewer discussion thread goes on for too long during the rebuttal period, and particularly, the later part of the debate becomes intense. I think it is necessary to provide such a summary to digest my concerns and how they are not fully addressed for future readers of this page. Finally, I respond to the authors' accusation of a goalpost shift. 

### My concerns and why they are or are not addressed.

My initial concerns are, as stated in the weakness in the very first review:
1. the missing but essential baseline QTO/FIT.
2. the missing discussion in similar datasets, such as the BetaE dataset, FIT dataset, and EFO_k dataset.
3. distribution of the new benchmark.

The situation of those concerns are
1. Addressed.
2. Addressed partially. The BetaE dataset was considered empirically, which satisfies my minimum standard. However, no discussion about how their methodology of benchmark construction applies to query types in FIT and EFO_k datasets can be found.
3. It is still under debate, and let me expand on it as follows.

My concerns about the distribution of the proposed benchmark are decomposed into several fine-grained issues during the rebuttal period.

Distribution issues:
1. I proposed a new set of terminology that clearly describes two parts of samples $S_{X, II}$ and $S_{X, III}$ based on the split of training and testing edges. The old benchmark, although sampled in a synthetic data distribution (no matter how weird it is), still covers both sets. The new benchmark only focuses on the $S_{X, III}$. My view is that the ignorance of $S_{X, II}$ is worrisome because such ignorance failed to reflect CQA's performances on link prediction, logical connectives, and variables on $S_{X, II}$.
2. Besides, the new benchmark, even used jointly with the old ones, actually stresses the importance of $S_{X, III}$, which is picked by enforcing the missing links. By emphasizing such a subset of data, the author tries to encourage a better link prediction because the simplest way of eliminating the gap between the new benchmark and the old one is just to make a better link prediction.

Both two issues are not fully addressed.

1. The authors acknowledge the new benchmark's ignorance. However, they tried to alleviate the negative impact in two ways. The first way is the joint usage or the stratified analysis, which leads to my second issue. The second way is to state that $S_{X, II}$ is way less important than $S_{X, III}$, which leads to our disagreement in non-factual belief. My belief is the missing link (which needs to be filled to satisfy practical application) is relatively small and will be smaller due to the advancement of knowledge graph construction and knowledge harvesting. The authors believe that the missing links in a KG are significantly large proportion. Their belief is claimed to be supported by valid math derivation, which I don't think their math can support their belief.
2. For the second issue, I think the performance gap between old and new benchmarks is caused by only picking the missing links, and it can be narrowed by proposing better link predictors that have better link prediction performances on the missing links in existing KG datasets. There are some neverending debates about whether the gap can be fully closed or if it really reflects the measurement of CQA. It does not change my view that, as a benchmark that encourages researchers to get higher and higher scores, it is very important that a benchmark does not have a clear shortcut deviating from the original goal of the task (logical connectives and variables besides link prediction). Clearly, If one method can achieve better link prediction performance on test data, it can first predict all missing links and just run symbolic algorithms. The limit of this solution is exactly one begins with a link predictor that overfits the test set, which is how the authors create benchmark data. I don't think this is a valid outlook for constructing a new benchmark to facilitate the study. Ironically, optimizing on the old benchmark, criticized by the authors that are mostly measuring link prediction (suppose the authors are correct here), will finally close the gap between new and old benchmarks, making the new benchmark less and less useful.

### Some accusations from the authors.

The authors accused of continuous goalpost shifting. However, my concerns are centered on the data distribution of the new benchmark and how it will impact the study. 

I decomposed and expanded my claims to respond to the authors' words, such as "we don't see any problems here.". I believe that the active authors deserve to know why I am against them. The authors, although very eloquent, repeatedly misunderstood my terms and words. Such as narrowing down my mentions of link predictors to neural link predictors (or knowledge graph embeddings) and refusing to accept my thoughts by just stating that neural models can never achieve perfect performance. However, no matter whether the neural models are perfect or not, the emphasis of new benchmarks on link prediction still remains unchanged.

I understand that people sometimes get emotional during the debate, and the emotional words from both the authors and me are already documented in the following threads. Please also let me express my apology if any of my words ever hurt anyone.
weaknesses: I have two concerns about the content discussed and the angle studied in this paper.

Firstly, the content seems to be very old. I am not sure whether this paper has been recycled on a sufficiently long time, so the author is not aware of the recent progress in this field. 
1. The dataset discussed only covers the query types in [1], which is outdated today. In 2024, several datasets covering far more complex queries are also proposed, including [2] for queries with logical negation, [3] for cyclic queries, and [4] for multi-answer variables. For the ``fair'' split of triples, the answer is also unaware of existing studies on temporal CQA [5].
2. The baselines discussed are also no later than the year 2023. ULTRAQ is almost the same as the GNN-QE.
3. Given the above ignorance, the proposed CQD-hybrid method is fundamentally identical to the QTO [6] proposed in ICML'23. Those two methods are all search-based approaches that involve memorizing the train edges, which is proposed in this paper and also reflected in Equation 4 in [6], noticing that normalizing link predictor scores into [0,0.9] will not change the order of solutions. 

I prefer to recognize methodological identicality as unawareness rather than plagiarism. Therefore I didn't raise an ethical review flag.


Secondly, saying that "the existing benchmark is problematic" is questionable and somehow self-contradictory with this paper's philosophy of choosing outdated simple queries. 
- On the one hand, scores on the previous benchmarks [1-5] are far from saturated because the average score is still less than 50 out of 100. Optimizing empirical models on previous benchmarks will also benefit the performance of the proposed "hard" benchmark. Meanwhile, recognizing the importance of training edges, although motivating the CQD-hybrid in this paper, is not new to the community because it is practiced in QTO [6] and later followed by FIT [3]. It hardly says why these findings are essential.
- On the other hand, the paper only focuses on the simpler query forms proposed in [1]. One might argue that such simple query forms cover a sufficiently large portion of real-world user cases, so the choice of such forms is reasonable. The same practical point of view can also apply to the easy-hard contrast produced by whether the reasoning triples of a query are observed or not. Although the previous benchmark consists of too many observed triples, as shown in this paper, it can also be reasonable by arguing that the train graph consists of a sufficiently large portion of knowledge that users are interested in.



References:

[1] Ren, H., Hu, W., & Leskovec, J. (2020). Query2box: Reasoning over knowledge graphs in vector space using box embeddings. arXiv preprint arXiv:2002.05969.

[2] Ren, H., & Leskovec, J. (2020). Beta embeddings for multi-hop logical reasoning in knowledge graphs. Advances in Neural Information Processing Systems, 33, 19716-19726.

[3] Yin, H., Wang, Z., & Song, Y. (2023). Rethinking Complex Queries on Knowledge Graphs with Neural Link Predictors. arXiv preprint arXiv:2304.07063.

[4] Yin, H., Wang, Z., Fei, W., & Song, Y. (2023). ${\rm EFO} _k $-CQA: Towards Knowledge Graph Complex Query Answering beyond Set Operation.

[5] Lin, X., Xu, C., Zhou, G., Luo, H., Hu, T., Su, F., ... & Sun, M. (2024). TFLEX: temporal feature-logic embedding framework for complex reasoning over temporal knowledge graph. Advances in Neural Information Processing Systems, 36.

[6] Bai, Y., Lv, X., Li, J., & Hou, L. (2023, July). Answering complex logical queries on knowledge graphs via query computation tree optimization. In International Conference on Machine Learning (pp. 1472-1491). PMLR.

---

confidence: 5
contribution: 1
initial_rating: 5
presentation: 3
questions: The comparison of 2u-filter is dubious. As the definition of union query just requires one link to hold in the graph, I do not see the necessity to do such filtering as Figure A.1 as it more resembles 2i query type after filtering.
soundness: 3
strengths: 1. The key observation of this paper is interesting. The partial-inference pair is prevailing in existing datasets and the paper shows that full-inference pair is empirically much harder than partial-inference pair and thus the reasoning ability of SOTA CQA models may be less powerful than our imagination.

2. This paper's case study and deep analysis are praiseworthy. For example, the paper studies the query type with union and additionally finds that if we filter out such pairs that can be accessed by just one link, the performance of 2u will increase significantly, similar to that of the 1p query type.
summary: This paper studies the complex query answering task on knowledge graph and questions whether the data in existing dataset is unqualified. To be specific, the author proposes to term those pairs of complex query & answers which the corresponding reasoning process can leverage some parts of the knowledge in the training graph as partial inference pair and thus evaluate existing CQA models on full-inference pairs. This paper conducts extensive experiments to showcase this observation and analysis on some certain query types like 2u.
weaknesses: 1. Firstly, the discussion of the query type is constrained in this paper. Most dominantly, almost all researches conducted on complex query answering in recent years included negative queries yet this paper avoids that completely. Perhaps it's a drawback of their model design originating from the initial CQD paper, or perhaps the reasoning process defined in this paper fails in a negative query. Either way, it's problematic as the scope of the query type it investigated is strictly contained.

2. The claim of SOTA CQA models fail significantly on so-called full-inference pair is questionable, as it doesn't include recent models that are built by symbolic search algorithms, like QTO[1] and FIT[2], which use neural link predictors combined with searching algorithms and seems to bypass the challenges proposed by full-inference pair.  As the paper itself proposes a symbolic search method, the missing baselines in other symbolic search methods is questionable.

---

confidence: 4
contribution: 2
initial_rating: 5
presentation: 3
questions: 1. Do you vary your argument in train queries? I am wondering  the phenomenon that existed CQA models fails is caused by the train datasets have too many partial inference answers. Thus I am curious about the performance of symbolic search methods where these methods don not use queries to train.
soundness: 2
strengths: 1. This paper find a interesting weakness of existing CQA dataset and propose a useful method and benchmark.
2. This paper is well written and easy to follow.
summary: The hard answers studied in complex logical queries are those that cannot be retrieved due to gaps in the knowledge graph (KG). This paper reclassifies these hard answers into two categories: full-inference and partial-inference The authors argue that partial inference can be reduced into simpler query types and partial inference occupies the majority of  existing datasets, BetaE. They discover that current models perform poorly on full inference tasks and propose a new benchmark to highlight this issue. Additionally, they introduce a new model specifically designed to tackle partial inference answers by explicitly retrieving existing links from the training knowledge graph.
weaknesses: 1. The baselines lack of the symbolic methods like QTO and FIT, which are the mainstream of CQA methods. The used CQD is a old symbolic method.
2. BetaE have three KGs but only two KGs are presented in the paper.
3.  The argument of 'reduced to easier types' is weird because query types with less constraint will be easy to solved than original query types, for example the performance of 3i is good than 2i. I suggest the authors use a preciser expression.
4. I disagree your arguments that your proposed CQD-hybrid is the first an hybrid solver. QTO and FIT use the information from observed KG and trained link predictor to construct the matrix and can use the hybrid information of train edges and pre-training embeddings.
5. Because of Weak 4, I am curious that the performance of symbolic method QTO and FIT as they already have the hybrid information.

---

confidence: 4
contribution: 2
initial_rating: 5
presentation: 3
questions: * The problem of information leakage in training graphs can be solved well by the inductive setting in naive knowledge graph reasoning (one-hop reasoning) task. Actually, there have been some attempts to establish inductive settings in CQA[1][2], where there will be no information leakage because the training and test graphs are different. How do you think this paper differs from these works?
* In my opinion, link leaks in the training graph only affect the GNN based and neural link predictor based methods, while the embedding-based methods do not take advantage of the information in the training graph (except for 1p queries). Why does this type of approach also degrade on the new benchmark?
* As mentioned in weakness, what's the difference between CQD-Hybrid and QTO?


[1] Inductive Logical Query Answering in Knowledge Graphs. In NeruIPS 2022.

[2] Type-aware Embeddings for Multi-Hop Reasoning over Knowledge Graphs. In IJCAI 2022.
soundness: 3
strengths: * Motivation of the paper is novel, and the re-examination of existing benchmarks is valuable.
* Experiments in this paper can support the conclusion well.
* Writing of the paper is good, the structure is clear, the layout is good, and it is easy to follow.
summary: In this paper, authors re-examine the existing problems of knowledge graph complex reasoning datasets. The authors propose that the current dataset cannot effectively measure the generalization ability of the reasoning model, that is, the complex queries in the dataset can be solved by the triples leaked in the training graph, and verifies their conjecture through extensive and sufficient experiments. Further, the authors propose a new set of benchmarks to more effectively measure the performance of complex reasoning models.
weaknesses: * Lack of discussion of related work, if the space is limited, this part can be placed in the appendix.
* In Section 5.1, the author proposes a CQD-Hybrid solver. Actually, the practice described in the paper is very similar to the QTO [1] and I think the difference should be cited and discussed.
* As an effort to propose new benchmarks, the experiments for the new benchmark are a little less. More baselines, some case analysis, etc., should be added.
* Some typos, such as line.468: 50.000

[1] Answering Complex Logical Queries on Knowledge Graphs via Query Computation Tree Optimization. In ICML2023

Meta-review: This paper shows that current benchmarks for CQA are not really complex, and that in these benchmarks most queries (up to 98% for some query types) can be reduced to simpler problems, e.g., link prediction, where only one link needs to be predicted. The performance of state-of-the-art CQA models drops significantly when such models are evaluated on queries that cannot be reduced to easier types. Thus, the results reported on existing CQA benchmarks might distort researchers’ perception of progress in this field. This paper then proposes a set of more challenging benchmarks, composed of queries that require models to reason over multiple hops and better reflect the construction of real-world KGs, and show that there is a lot of room to further improve current CQA methods on the new benchmarks. 

Strengths:

Reviewers generally agree that this paper provides an in-depth study and analysis of existing benchmarks and offers interesting observations.

Weaknesses:

Reviewers actively engaged in discussions with the authors, and many comments raised in the original reviews were addressed through the rebuttal period. Here is a summary of the unresolved (or partially resolved) issues after rebuttal:

1. The distribution of the proposed benchmark by Reviewer z9wR (relatedly, the discussion around query types raised by Reviewer fPSh), and how this impacts the proposed benchmark’s usefulness (or, why it is necessary) still remain unclear. 

While I really appreciate the authors’ efforts in actively responding to reviewers’ comments, there are still issues that remain unresolved after the discussion period. In addition, some issues that did get resolved in this process will need to be clarified in the revised version. I believe the paper could benefit from another round of revision which integrates the discussions during the rebuttal period, particularly addressing the necessity of the proposed benchmark.

Decision: Reject