Is Complex Query Answering Really Complex?
Authors: Cosimo Gregucci
Bo Xiong
Daniel Hernández
Lorenzo Loconte
Pasquale Minervini
Steffen Staab
Antonio Vergari
Venue: ICML 2025 spotlightposter (2025)
Keywords: complex query answering
knowledge graphs
multi-hop reasoning
neuro-symbolic
Primary area: general_machine_learning->evaluation
TL;DR: We highlight how common benchmarks for complex query answering with neural models are skewed towards "simple" queries and propose new more challenging benchmarks that solve this issue.

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 might not be as *complex* as we think, as 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 decreses 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.

Is Complex Query Answering Really Complex?
Cosimo Gregueci' Bo Xiong² Daniel Hernández' Lorenzo Loconte
Pasquale Minervini
3 34
Steffen Staab 1 Antonio Vergari
Abstract
over a KG such as FreeBase (Bollacker et al., 2008), 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 another entity, i.e., an actor participating in it. However, if some links are missing in the KG, not all relevant actor entities can be immediately reachable. To deal with the unavoidable incom- pleteness of real-world KGs, ML methods were developed to solve CQA in the presence of missing links. The current state-of-the-art (SoTA) for CQA are neural query answering models (Arakelyan et al., 2021; Zhu et al., 2022; Arakelyan et al., 2023; Ren al., 2023; Galkin al., 2024b), mapping queries and KGs (i.e., entities and relation names) into unified latent space. Performance measured on de-facto- standard benchmarks such as FB15k237 (Toutanova & Chen, 2015) and NELL995 (Xiong et al., 2017) suggests impressive progress achieved in recent years on CQA on queries having different structures, and hence posing apparently different levels of difficulty to be answered.
Complex query answering (CQA) on knowledge graphs (KGs) is gaining momentum as a challeng- ing reasoning task. In this paper, we show that the current benchmarks for CQA might not be as complex we think, as the way they are built dis- torts 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-arr CQA models de- creases significantly when such models are eval- uated on queries that cannot be reduced to easier types. Thus, we propose a set of more challeng- ing 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 bench- marks show that current methods leave much to be desired from current CQA methods.
The difficulty of a benchmark relates to the size and struc- tural complexity' of its queries, and several query "types" have been proposed (Ren et al., 2020), each involving a different combination of logical operators- conjunncions,,, disjunctions, and requiring to traverse a number of missing links that generally increases with the number of logical conditions imposed (Figures 1 and 2). For instance, the query @1 is example of "2ilp" query type, since it comprises an intersection of two entity sets (2i) followed by a path 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 FB15k237 and NELL995, the vast majority of queries of a complex type simplify one simpler type, thanks to the fact that to answer them, one can leverage links already appearing in the training data. Fig- ure shows an example of how answers to the query @1 on FB15k237- which should require predicting three missing links - require the same effort associated with simpler types involving fewer links. In fact, in FB15k237, the answer "K. Dunst" can be retrieved by predicting just one missing link
1. Introduction
crucial challenge in Al and ML is learning to perform complex reasoning, i.e., solving tasks that involve several intermediate steps and sub-goals to be completed. Complex query answering (CQA; Hamilton et al., 2018; Zhang et al., 2021; Arakelyan et al., 2021; Zhu et al., 2022) emerged as way to measure complex reasoning over external knowledge bases, encoded as knowledge graphs (KGs; Hogan et al., 2021). For instance, to answer the query:
"Which actor performed in a movie filmed in New York City and distributed on Blue Ray?"
(g1)
@ Shared supervision 'Instiutee for Artificial Intelligence, Uni- versity of Stultgart, Germany "Stanford University SSchool of Informatics University of Edinburgh Edinburgh, UK "Miniml.A ' Unniversity of Southampton, UK. Correspondence to: Cosimo Gregueci <cosimo, gregueci @ ki.uni--tuuu stui-stuttart.de>..
Not to confused with the computational complexity of query answering (Dalvi & Suciu, 2012).
Proceedings of the 4 International Conference on Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).
AAlso known as projection in related works (Ren et al., 2023).

---

Is Complex Query Answering Really Complex?
"Which actor performed in a movie filmed in New York City and distributed on Blue Ray?"
training link
"Blue Ray"
missing link
2ilp
"NYC"
"King Kong"
"A. Sorkis"
2T = AV. V) (02. V) A (V, 7)
"Blue Ray"
"Blue Ray"
"Blue Ray"
1p
"NYC'
'Spiderman 2" KK. Dunst"
2P
"NYC'
"When Rome "J. Bryant"
2i
"NYC'
"King Kong" "K. Chandler"
Figure 1. Query answers are not all equally hard when some links can be found in the training data as shown for the 2 query oi and fragments of the KG FB15k237, where rı distributedVia .22 locatedin and ry = performedln 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 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, 2p, and 2i (see Sec. 2 and Figure 2).
when leveraging the training links. In this sense, 2ilp query reduces to a "Ip" query, i.e., the much simpler task of link prediction (see Sec. 2). Similarly, the answers "J. Bryant" and "K. Chandler" can be retrieved by predicting two links instead of three. Only the answer "A. Serkis" re- quires predicting three missing links, and thus follows the intuitive "hardness" associated the type 2ilp, i.e., it is the hardest when no information is available. As note here, there is spectrum of hardness, predicting "K. Dunst" will be easier than answering "K.ahnndlerr, which in turn is easier than saying "A. Serkis". However, current CQA benchmarks greatly overrepresent the easy query answers over the others- the "K. Dunst"-like answers are the vast majority - and this inflates performance as SoTA models are known to be prone to memorize training links. In this paper, we analyze this issue and propose new set of benchmarks that cover the full spectrum of hardness in CQA.
ICEWS18 (Boschee et al., 2015), where validation and test links are links that have been added to the KG after those in the training, to investigate more realistic sampling schemes to generate the train/validationntest splits. Lastly, we add the query types "4p" (a four-length path) and "4i" (a conjunc- tion of four patterns), making them more challenging.
2. KGs and Complex Query Answering
Knowledge graphs. A KG is a graph-structured knowl- edge base where information is encoded as relationships between entities. More formally, a KG is a multi-reaationl graph G = (E, R. T), where & is set of entities, R. is set of relation names, and T S & x R x E is a set of links triples, where each triple (s E T represents relationship of type p between a subject and an object o. For instance, in a KG such as FreeBase, the fact that the movie "Spiderman 2" is distributed in Blue Ray is stored in the triple (Spiderman2, distributedVia, BlueRay) or equiv- alently (BlueRay, distributedVia " Spiderman2) where distributedVia 1 is the inverse relation of distributedVia. Figure shows examples of fragments of the KG FB15k237.
Contributions. After revisiting the CQA task (Sec. 2) and highlighting how query types can simplify at test time in the presence of training links (Sec. 3), (C1) we show that up to 99.9% of the 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). This clearly inflates the reported performance. (C2) We re-evaluate pre- vious SoTA approaches (Sec. 5), revealing that neural link predictors rely on memorized information from the train- ing set. Furthermore, we show that the reported hardness of queries involving unions is only apparent. To better understand why performances are inflated, we introduce CQD-Hybrid, hybrid CQA solver that combines classi- cal graph matching with neural link predictors. (C3) We create new benchmarks for CQA (Sec. 6), FB15k237+H and N from FB15k237 and NELL995, respectively, where we equally sample all intermediate query types one can consider by accounting for known links in the training data. To these, we build ICEWS18+H from the temporal KG
The aim of CQA is to retrieve set of answers to logical query that poses conditions over entities and relation types in a KG. Following Arakelyan et al. 1202)), we consider the problem of answering logical queries with a single target variable (T), a set of constants including anchor entities (o1...., a E E), given relation names (fi...., Tn E R), and first-order logical operations that include conjunction A, disjunction V, negation - and existential quantification 3. Different queries are categorized into different types based on the structure of their corresponding logical sen- tence (Xiong et al., 2017). This taxonomy should imply that queries of the same type share the same "hardness", i.e., the level of difficulty to be answered, and different types correspond tasks that map to more or less complex rea-
2

---

Is Complex Query Answering Really Complex?
1p
2p
3p
4p
1p2i
2
conjunction link
2u
Zulp
dighunction link
Figure 2. Query structures we consider. adapted from Ren & Leskovec (2020) and including path (p), intersection (i), union (u) structures. Sec. for their logical formulation. See App. for additional query structures including negation.
soning tasks. As we will show in the next sections, this not the case, and to fully grasp the actual hardness to answer query one needs account for the "leakage" of intermediate training links. We now review the most com- mon query types used in CQA. The simplest CQA task is link prediction, i.e., answering a query of the form:
Similarly to introducing conjunctions, we can consider dis- junctions in queries, realizing the union query types which can be answered by matching one link or the other, such as
?T (a1, (a1,TI, TI, (a2, r2,
(2u)
or by combining the union with the previous query types, e.g., obtained by combining 2u and 1p:
?T: (1,, r1, T),
(1p)
?T (V.. V1), r2, (2,, T). (2ulp)
that is. given an entity an (e.g., NYC) and a relation name (e.g., locatedln "), find the entity that when substituted to T correctly matches the link in the KG (e.g., Spiderman2, see Figure I). Instead of matching a single link, more complex queries involve matching sub-grapha, in a KG (see Figure 2). Xiong et al. (2017) extend 1p queries, and ask questions involving sequential paths made of two or three links, i.e.,
Note that despite their dissimilar syntaxes and the associ- ated sub-graphs (Figure 2), the query type 2u should be as difficult as 1p, as to answer the first it suffices to match a single link correctly. Similarly, 2ulp should be as complex as 2p. The fact that 2u and 2ulp are reported to be harder to solve in practice than 1p and 2p (Ren et al., 2020) is due to the way standard benchmarks are built, which we discuss in Sec. 4, and the way in which CQA is evaluated, discussed next. App. B details further query types, including negation.
VV, r1, Vi) A (Vi, T), IVe r1, Vi) A r2, V2) A (V2, T),
(2p)
(3p)
where V/1 V/2 denote variables to be grounded into entities appearing in the path. Moreover, multiple ground entities can participate in a conjunction, e.g., in queries such as:
Standard evaluation. Given a KG G and a query an- swering boils down to a graph matching problem (Hogan, 2020) if we assume that all the meaningful links are already in G. Instead, if is incomplete, we will need to predict missing links while answering q. Many ML approaches to CQA, reviewed in Sec. 5, therefore assume distribution over possible links (Loconte et al., 2023), thus requiring some form of probabilistic reasoning. To evaluate them, standard benchmarks such as FB15k237 and NELL995 arti- ficially divide G into Guein and Grest, treating the triples in the latter as missing links. This splitting process is done uniformly at random, procedural choice that is inherited from link prediction benchmarks (Ruffinelli al., 2020) and that can alter the measured performance, 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- non-answer ones. Let the rank of query answer (QA) pair (q, 1) be rank(q, (), the performance for each query type is calculated as the mean reciprocal rank (MRR), i.:::
?T: (01, F1. (a2, r2, T), ?T: (a1, T1. T) A (a2, P2, T) A (az, r3, T),
(2i)
(3i)
which represent the intersection of the target entity sets de- fined over two (2i) or three (3i) links. Path and intersection structures can be combined into more complex queries: for example, the natural language expression for query qı can be formalized the formula
27: (Q1, rı, Vi) A (a2, r2, Vi) A (Vi, 7), (2ilp)
involving one intersection followed by a length-one path.
See also the example in Figure 1. By inverting the order of operations, we obtain the query type "Ip2i":
?T: (Vi, TI, Vi) A (V,, r2, T) (a2, ra, T). (Ip2i)
Q ' REO, E rank(g.t)
(1)
'n Ren et al. (2020) this type was referred to as "ip". We explicitly mention the number of steps involved in a path con- junction, this factor of complexity. Analogously, "pi", and "up" queries from Ren et al. (2020) are now 1p2i, and 2ulp.
where Q denotes the set of test queries of the considered type, and Ey the set of candidate answer entities for each
3

---

Is Complex Query Answering Really Complex?
query q E Q This average, across queries and answers, assumes that every QA pair having the same query type is equivalently hard, which is not the case. In fact, we show that certain QA pairs can be easier to predict if some links were already seen by the model during training (Figure 1) and that the distribution of the query answer pairs in the ex- isting benchmarks is very skewed towards those involving a
based queries encompass a spectrum of hardness, with full-inference queries being the hardest and queries that have only one truly missing link (Ip) the easiest. However, current benchmarks flatten this complexity and highlight only performance on the easiest.
To predict a partial-inference pair (g, f), a ML model that has explicit access to Girsin has to solve simpler task to answer q. as only 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 (u', () pair, where the query q' is of an casier query type than q. Figure shows one example of how a QA pairs of type 2 from FB15k237 are reduced in practice to the simpler types 1p, 2i and 2p. This is exploited by hybrid solvers such as QTO (Bai et al., 2023) and our CQD-Hybrid ( Sec. 5). Note that this advantage applies also to ML models that have implicit access to Gurain e.g., by having memorized the triples during training, a common phenomenon for many neural link predictors (Nickel et al., 2014). We confirm this in Sec.
single missing link (Table 1). Thus, computing Equation (1) without understanding what the benchmark distribution is
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 com- plexity of a query is related to the graph structure associ- ated to its query type (Figure 2): queries containing more variables are more challenging, e.g. a 3p query is harder than a 2p query. In this section, we give an alternative perspective on the difficulty of answer- ing queries that take into account the information coming from the training data. We argue that predicting links that are truly missing, i.e., not accessible to learned model, is actually what makes a query "hard". To do so, we formalize the notion of a reasoning tree for QA pair, and then define how we determine the practical hardness of a QA pair.
4. How Many "Easy" Queries in Current CQA Benchmarks?
In this section, we systematically analyze the practical hard- ness of queries from the current CQA benchmarks and answer the following research question: (RQ1) What is the proportion of QA pairs that can be classified as full- inference rather than partial-inferene and how easy are the latter? To this end, consider the CQA benchmarks generated from FB15k237 (based on Freebase) and NEL (based on NELL systems (Carlson et al., 2010)) as they are the most used to evaluate SoTA methods for CQA (Ren et al., 2020; Ren & Leskovec, 2020; Arakelyan et al., 202 I; Zhang et al., 2021: Zhu et al., 2022; Arakelyan et al., 2023)."
Given a query q and every answer set of candidate answers I E Eg. we define the reasoning tree of each QA pair (g, l), as the directed acyclic graph starting from the anchor en- tities of q to the target entity f, whose relational structure matches the query graph. Figure I provides examples of different reasoning trees for four different answers to the same query. There, we highlight whether a link belongs to Guain or not, i.e., is missing link. We assess the hardness of each answer E Eg. 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 (g. t) pair is trivial if the answer can be entirely retrieved from Guains i.e., there exists at least one reasoning tree where all the links in it seen during training. This type of answer does not need probabilistic inference and hence is filtered out from current CQA benchmarks (Ren & Leskovec, 2020), which only con- sider non-trivial (g. 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 missing. There- fore, we define a (q. t) pair to be a partial-inference pair if its reasoning tree contains at least one link in Guain and at least one link present in Grest Alternatively, a (g, L) pair whose reasoning tree contains only links present in Gues is called a full-inference pair. We claim that inference-
Complex queries can be reduced to much simpler types. We group the testing QA pairs into query types (Sec. 2), and we further split them based on whether they can be reduced to simpler types after observing the training links in Gtrain (Sec. 3). Table shows that for both FB15k237 and NELL995 the vast majority of QA pairs can be reduced to simpler types. For FB15k237, 86.8% to 98.3% of QA pairs can be reduced to 1p queries, while only 0.1% to 4% require full inference. Similarly, for NELL995, 49.5% to 98.5% of QA pairs map to 1p queries, and only 0.1% to 6% to full inference. For instance, 96.7% of 2ilp QA pairs in FB15k237 can be reduced to 1p queries, 1.8% to 2p, and 1.4% to 2i. However, only 0.1% of these pairs cannot be reduced to any other QA pair, i... they require full inference in order to be predicted. The only exceptions to this trend are QA pairs where the query has a 1p or 2u structure which,
*We do not consider FB15k (Bordes et al., 2013) as it suffers from another form of data leakage (Toutanova & Chen, 2015).
4

---

Is Complex Query Answering Really Complex?
Table 1. The great majority of QA pairs are of the much easier partial-inferenc type (non-diagonal), rather than the harder full-inference type (diagonal). For each query type (as rows) we show the percentage of the QA pairs that can be reduced to an easier query type (as columns) datasets FB15k237 and NELL995. Most of the complex queries can be reduced to simple link prediction queries (i.e., Ip). We denote as" those reductions that are not possible given the sub-graph structure induced by the query type.
FB15k237
NELL995
1p
2p
3p
2i
3i
1p2i
2ilp
2u
2ulp
1p
2p
3p
2i
3i
1p2i
2ilp
2u 2ulp
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
2ilp
96.7
1.8
1.4
0.1
96.2
2.4
1.2
0.2
2u
0.0
100
0.0
100
2ulp
98.3
0.0
1.6
0.1
98.5
0.0
1.4
0.1
by definition, only require the prediction of a single link and therefore cannot be reduced by any other query type. We conduct the same analysis for queries that include negation, considering only the reasoning tree over non-negated links (see App. A. for details). Table A. presents results anal- ogous to those in Table 1, showing that the vast majority of QA pairs including negation have training links in their reasoning tree. For example, 95.4% and 93.9% of 3in QA pairs in FB15k237 and NELL995,, respectively, have training links in their reasoning tree.
"Norwdy"
"Wiich relowved And makeuup artict in now?
mosing Aak
"Make-up arisf"
The wilrese
(a T) (au,
"Norway"
'Norway"
"Mako-up artise"
The exorciat"
"Make up artist"
American History"
Figure 3. 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 FB15k237, where ri = releasedln, 72 = crewMemberOf. (Top) Example an answer that we retain in our benchmark, heing reachable by two missing links. (Bottom) Example of answers we filter out, being only reachable by one missing link.
Is this realistic? This skewed distribution is the result of implicit assumptions behind how these benchmarks have been created. We argue they are arbitrary and not realistic. First, we note that the procedure to generate queries assumes that triples are independent, a simplifying assumption that does not hold in practice. Second, triples are sampled independently, the quantity of QA pairs that can be reduced to 1p depends on how many links are assumed to be missing. This is given by the ratio of |Grrain| and [rres] Note that however the train/test split is arbitrary and has been inherited from the benchmarks for link prediction, where the task was rightfully predict a single link.
We discourage using current CQA benchmarks, as they essentially reflect only the per- formance of predicting answers where only one link is truly missing (for both hybrid and neural solvers),
Takeaway 1.
Non-existing links for union queries. Finally, we discov- ered that there are non-existing links, i.e., links that are not in the original KG G and hence neither in Gtrain or Guest in both FB15k237 and NELL995 in the reasoning trees of queries involving unions, i.c., the 2u and 2ulp types. These links violate our definitions of inference QA pairs, hence, we filter them out, and report only filtered QA pairs in Ta- ble 1. For example, for 2u QA pairs, if either one of the two links in the reasoning tree does not exist in the graph, we remove the QA pair (see Figure bottom for an example). It follows that only QA pairs where both links in the reasoning tree exist in the test graph are retained (see Figure (Top) for an example). More crucially, these non-existing links can alter the performance of solvers for 2u and 2ulp types, as we discuss next.
5. What do SoTA Models Perceive as Hard?
In this section, we re-evaluate SoTA methods for CQA and answer to the following question: (RQ2) How do they per- form on QA pairs that are placed differently in the hardness spectrum? ? To substantiate that memorizing training links helps in answering partial-inference queries but not full- inference ones (Sec. 3), we evaluate hybrid solvers who have access to Girain-
Neural CQA methods. Over the years, a significant num- ber of neural models have been proposed for solving the CQA task, see App. C for an overview. Among purely- neural models, we consider five representative approaches
5

---

Is Complex Query Answering Really Complex?
3p
2ilp
Table 2. SoTA performance drops sig- nificantly on full-inference QA pairs as shown for the MRR for 3p and 2 queries on FB15k237. Compare the over- all MRR achieved all available testing 5.6
method
1p
2p
3p
2i
3i
1p2i
2
ONE
1p
2p
3p
2i
3i
1p21
2ilp
GNN-QE
11.8
12.0
4.4
4.8
18.9
19.2
8.2
6.2
3.4
ULTRAQ
8.9
9.0
4.6
4.4
18.6
18.9
8.5
5.1
8.1
ConE
11.0
11.0
5.4
2.6
14.0
13.8
9.7
12.8
CQD
7.8
7.8
3.4
1.8
20.7
21.0
10.5
6.7
queries (column "ovr") with that achieved 7.6
on the Ip reductions ("Ip" column, i.e., when only a single link is truly missing); 13.2 they are extremely close. This is because Ip queries are overrepresented in the existing benchmark (Table 1). Compare instead their values to those in the full-inference column (highlighted in orange) where all links in the reasoning tree of the QA pairs missing: the latter are much lower. This applies also intermediate partial-inference QA pairs (middle columns), entailing that the skewed distribution these datasets (Table 1) greatly distorts the overall performance usually reported in previous papers. The same pattern appears for all query types in both FB15k237 and NELL995, See Tables A.4 and A.5 for the complete stratified analysis for all query types and models.
CQD-Hybrid
11.0
11.1
3.6
4.4
24.0
24.6
10.0
4.6
7.5
QTO
15.6
15.8
4.5
5.0
24.7
25.3
10.3
8.6
8.1
CLMPT
11.3
11.3
6.1
4.0
19.3
19.1
18.7
7.9
that significantly differ in their methodological designs and yield SoTA results compared to other models in their class: (1) Cone Embeddings (ConE; Zhang et al., 2021) is a geometry-basee -baeed complex query answering model where logical conjunctions and disjunctions are represented as in- tersections and union of cones. (2) Graph Neural Network Query Executor (GNN-QE; Zhu al., 2022) decomposes complex first-order logic query into projections over fuzzy sets. (3) Conditional Logical Message Passing Trans- former (CLMPT; Zhang et al., 2024) leverages existing KG embeddings to conduct one-hop inferences on atomic formu- las in a message- paagggggggnnnnggggg scheme as in LMPNN (Wang et al., 2023), and extends it by using a transformer to aggregate messages incoming from neighbor nodes. (4) Continuous Query Decomposition (CQD; Arakelyan et al., 2021; 2023), reduces the CQA task to the problem of finding the most likely variable assignment, where the likelihood of each link (lp query) is assessed by neural link predictor, and logical connectives are relaxed via fuzzy logic operators. (5) U1- traQuery (ULTRAQ: Galkin et al., 2024b) is a foundation model for CQA inspired by Galkin et al. (2024a) where links and logical operations are represented by vocabulary- independent functions which can generalize to new entities and relation types in any KG.
Two remarkable examples are QTO (Bai al., 2023) and FIT (Yin et al., 2024). They explicitly retrieve existing links from Gresin when answering a query at test time. In- spired by them, and to evaluate our hypothesis, we create a light-weight hybrid solver, named CQD-Hybrid, that is a variant of CQD that uses a pre-trained link predictor to compute scores for the answer entities of Ip queries only, denoting the unnormalized probability of that single link to exist (Loconte et al., 2023). Then, assignments to existen- tially 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., 2022). A complete assign- ments to the variables (and hence the target variable T), gives us an answer to the query. In CQD- CQD-Hybrid, we assign the maximum score to those links that are observed in Gtrain- That is, training links will have a higher score than the one that the link predictor would output, hence effec- tively stecring the mentioned greedy procedure at test time. This is the only minimal change we apply to CQD to test if its performance can depend on memorizing training triples. Note that this makes CQD-Hybrid different from QTO and FIT, which involve more sophisticated steps such score calibration and a forward/backwar update stage, that can boost performance. In our experiment we will only consider QTO, as for the set of queries we considered QTO and FIT are equivalent (Yin et al., 2024). We report hyperparameters and implementation details of CQD-Hybrid in App. F.I.
Hybrid solvers. So far, we have assessed that current bench- marks are skewed towards easier query types (Table 1) and thus the perceived progress of current SoTA CQA methods boils down to their performance on 1p queries (Table 2). To have an undistorted view of this progress, in the next sec- tion, we will devise a benchmark that rebalances all partial- inference as well as full-inference queries types. That is, we will provide an equal number of QA pairs for each sub- type a query can be reduced to. Now, we argue that in a real-world scenario one has to perform reasoning over both existing links and missing ones, hence discarding the infor- mation in Gurain is wasteful. This, in addition the fact that purely-neura So CQA methods might implicitly exploit this aspect at test time if they are able to memorize well Giainn pushes us to evaluate also hybrid solvers.
All SoTA methods perform significantly worse full- inference queries. We re-evaluate the SoTA methods men- tioned above and stratify their performances based on the type of partial- and full-inference queries. Where avail- able, we reused the pre-trained models for their evaluation. Otherwise, we re-produced the SoTA results using the hy- perparameters provided by the authors, listed in App. F.I.
Table 2 presents portion of the results in terms of MRR for the testing QA pairs in the existing benchmarks FB15k237 and NELL995, along with the different QA pairs they can be reduced to when observing the training KG, grouped by
6

---

Is Complex Query Answering Really Complex?
Table Exploiting training links during inference boosts MRR on existing benchmarks. as shown by our CQD-Hybrid model compared previous SoTA, for several query types. CQD-Hybrid always achieves higher MRR scores when compared to CQD, and outperforms more sophisticated non-hybrid baselines 9/14 times. Best values in bold and second best underlined,
Figure 4. MRR SoTA on new benchmarks significantly lower than the old ones as reported for FB15k237 and NELL995 (in blue) versus our new FB15k237+H and NELL995+H (in or- ange) for different query types and SoTA models. ULTRAD
cop
ConE
QTO
Model
2p
3p
2i
1p
2ilp
2ulp
GNN-QE
14.7
11.8
38.3
54.1
3111
18.9
9.7
ULTRAQ
11.5
35.7
51.0
29.6
18.6
7.3
CQD
13.2
35.0
48.5
27.5
20.7
10.5
NELLO95
ConE
12.8
11.0
32.6
47.3
25.5
14.0
7.4
20
CLMPT
13.9
11.
37.5
51.9
28.4
19.3
11.4
CQD-Hybrid
15.0
11.0
37.6
52.7
31.2
24.0
10.3
1P 211
2015
215
2119
2019
102
2115
GNN-QE
17.9
15.2
40.0
50.9
29.1
20.5
8.8
ULTRAQ
11.2
9.7
36.3
47.7
25.1
15.6
8.4
CQD
22.0
13.4
42.2
51.8
31.5
25.8
16.0
NELL
ConE
16.0
13.8
39.6
50.2
26.1
17.6
11.1
CLMPT
22.1
18.2
41.6
51.7
29.0
24.7
16.1
Table 4. Queries of type 2u are less hard than previously thought in terms of MRR, with our filtered 2u queries having comparable performance to 1p, as discussed in Sec. 2, in contrast with the results the 2u queries originally used (2u all).
CQD-Hybrid
23.8
17.8
44.2
57.8
33.2
28.4
16.6
each query type. There, the performance of all SoTA meth- ods consistently drops for query answer pairs that have higher number of missing links in their reasoning tree. Fur- thermore, Tables A.4 and A.5 compare the MRR computed on all the available queries originally used in the bench- marks (column "all"", and the scores on those query types that they can be reduced to. There MRR between the columns "all" and "Ip" that is evidence that the good performances of CQA methods are explained by their link prediction performances, as a very high per- centage of queries in fact are reduced to 1p queries (see Table 1). A similar conclusion can be drawn for queries including negation, as shown in Table A.2.
FB15K237
NELL995
method
1p
2u all
filtered
1p
2u all
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
ConB
41.8
14.9
29.9
60.0
14,9
28.2
CLMPT
45.3
14.8
32.8
58.1
18.6
39.6
high similarity in
benchmark in the next section.
Non-existing links for union queries give false sense of hardness. For union queries, we filter query answer pairs, as discussed in Sec. 4, removing those with non non-existing links in their reasoning trees. In Table 4, we show that if we do not 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 queries that the original SoTA baselines reported in their papers. However, as Table 4 shows, this is just an artifact due to including non non-filtered pairs while computing Equation (1). With our filtered pairs, instead, we recover the performance of Ip queries, as expected (Sec. 2). Similar conclusions can be drawn for other union queries as reported in Table A.3.
Note that this happens consistently also for hybrid solvers such as QTO and our CQD-Hybrid: they have harder time solving QA pairs with more than one missing link. While their performance was consistently surpassing purely- neural solvers, and CQD-Hybrid consistently boosted the performance of CQD, their poor performance on harder QA pairs is not reflected the overall average score that is usually reported on papers, see Table 2.
Table 3 highlights that our CQD CQD-hybrid is able to surpass existing non-hybrid SOTA, which is evidence that pre- trained neural link predition plus memorization of Gtrain achieves SoTA performances for FB15k237 and NELL995. The complete stratified comparison for all solvers re- ported in Tables A.4 and A.5. However, in a few cases happens that full-inference results are higher than some partial-inferrnce; in such cases, the reason is to be found in the fact that full-inference QA pairs are very scarce (see Table 1).² This motivates us to create fully-balanced
Takeaway 2. FB15k237 and NELL995 are not suit- able to precisely assess CQA methods, as most of their QA pairs can be predicted by just predicting a single missing links. This results in highly inflated performance that distorts the perception of progress in the field and pushes the community improve the performance only the easiest QA pairs.
'ee 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 Figures A.1
and D.2. Moreover, found that no anchor entities nor relation names is predominant both benchmarks, as shown in Table A.6.

---

Is Complex Query Answering Really Complex?
6. New Benchmarks for Undistorted CQA Performance
tamp; (2) removing the temporal information, thus obtaining regular triples; and (3) selecting the train set to be the first temporally-ordere 80% of triples, the valid the next 10%, and the remaining to be the test split. If the same fact ap- pears with multiple timestamps, we retain only the link with the earliest timestamp. For detailed statistics about the splits, please refer to App. G.I. By doing so, we create much more challenging benchmark even for easy 1p queries.
In this section, we aim to answer the following question: (RQ3) How can we construct a set of CQA benchmarks that let us measure the performance on each query type while not distorting the aggregated average? To do so, we present a new set of CQA benchmarks based on the previously used FB15k237 and NELL995, as well as novel one we design out of temporal knowledge graph ICEWS18 to question the current way to split the original KG G into Gurain and Guest (see our discussion of how sampling triples independently is arbitrary in Sec. 4). Then, we evaluate current SoTA methods on these new benchmarks to establish a rigorous baseline for future works.
How do SoTA methods fare our new benchmarks? For FB15k237+H and NELL995+H we re-used the pre-trained models used for the experiments in Sec. 4, while for the newly created ICEWS18+H we trained GNN-QE, CLMPT, ConE, and the link predictor used in CQD, CQD-Hybrl and QTO from scratch. As this is not necessary for ULTRAQQ 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 App. F2.
Building new CQA benchmarks. We generate our bench- marks to comprise both full-inference and partial-inference QA pairs, but we modify the algorithm of (Ren et al., 2020) to ensure that no training links are present in the reasoning trees of full-inference pairs, and for each query type, we build the benchmark such that the full spectrum of hard- ness appears with the same frequency in it. For example, for 3p queries, we sample 30,000 QA pairs, 10,000 for 3p that can be reduced 1p, 10,000 for those reduceable to 2p. and 10,000 for full-inference QA pairs (3p QA pairs non-reduceable to any other type). Furthermore, we sample union queries 2u, 2ulp such that non-existing link are not present in their reasoning tree. Finally, 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 sequen- tial path made of four links and "4i",, which represents the intersection of the target entity sets defined over four links. For their logical formulation, see App. E.
Figure 4 reports the MRR on the new benchmarks versus the old benchmarks, where the MRR of FB15k237 and NELL995 (in blue) is much higher than the one of FB15k237+H and NELL995+H (in orange) for all methods for all query types. Considering how MRR can drop for more than 30 points, e.g., for 3i queries, this highlights once more how distorted the perception of progress in the field can be.
Table 5 shows the results of the selected baselines on the new benchmarks, for all query types in Figures 2 and B. For stratified results on FB15k237+H, NELL995+H, ICEWS18+H see Tables D.3 to D.5, respectively. For the stratified anal- ysis on queries including negation see Table D.6. The sur- prising result from Table 5 is that model obtains SoTA performance
most query type, which was not the case for the old benchmarks, where QTO obtained SoTA perfor- mance for most query types (see Tables A.2, A.4 and A.5). This is further evidence that current SoTA methods mainly focused on improving the performance on the easiest QA pairs and likely overfit the benchmarks. Instead, with our new benchmarks, this will not be possible in the same way, as we compile the benchmark with the same amount of partial- and full-inference QA pairs per type.
We do so for the query types shown in Figures 2 and 1, and name the harder versions of FB15k237 and NELL995, FB15k237+H and NELL995+H. Only exceptions are 1p, 2in, 2nu1p p those only being of type full-inference. See Apps. A.1 and B for details about queries including negation, and App. G.2 for details about query generation.
Furthermore, we highlight how full-inference 2u queries have similar performance with 1p, similar to how full- inference 2ulp are expected to be as hard as 2p, as discussed in Sec. 3. Finally, we remark that ICEWS18+H is much harder than NELL995+H and FB15K237+H, across all query types, even 1p, thus raising the bar 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. For additional analysis on the new benchmarks, comprising the influence of the number of existing entities bounding existential quantified variables. the most frequent relation name and anchor entity per query type, and statistical tests, see App. D.
Non-uniform at random splits. Recall from Sec. 4 that FB15k237 and NELL995 have been created by assuming triple independence and by inheriting the train/test split from their link prediction counterparts. For FB15k237+H and NELL995+H, sumption as we sample the same number of QA pairs per type, but we keep the existing data splits of Gurain and Guest. for retro-compatiiility. However, to evaluate the impact of this artificial splitting process, we adopt a more realistic one for ICEWS18+H, where Gueain contains only "past" links, and we might want to predict the future links contained in Grest- To this end, we leverage the temporal information in ICEWS18 by (1) ordering the links based on their times-
removed the triple independence as-
8

---

Is Complex Query Answering Really Complex?
Table There no clear SoTA method for the new benchmarks. shown Figure 4, MRR on the new benchmarks significantly lower than the old ones. For example, for 3i queries on FB15k237+H, QTO has an MRR of 10.1, while for FB15k237 it was 54.6. the stratified analysis see Tables D.3 to
Model
1p
2p
3p
2i
3i
1p2i
2ilp
2u
2ulp
4p
4i
2in
3in
2pi
2nu Ip
2in
GNN-QE QE
42.8
5.2
4.0
6.0
8.8
5.6
9.9
32.5
10.0
4.3
20.0
6.8
3.7
5.0
3.3
FB15K237+H
ULTRAQ
40.6
4.5
3.5
5.2
7.2
5.3
10.1
29.4
8.3
3.8
16.4
5.3
5.5
2.6
3.7
2.2
CQD
46.7
4.4
11.3
12.8
11.5
40.1
10.6
23.8
3.3
4.9
1.2
CQD-Hybrid
46.7
4.8
3.1
6.0
8.6
5.5
12.9
42.2
12.0
2.4
17.4
4.7
1.6
1.0
3.2
1.3
ConE
41.8
4.6
3,9
9.1
10.3
3.8
7.9
22.8
6.0
3.5
20.3
5.1
4.9
2.9
3.3
3.6
QTO
46.7
4.9
3.7
8.7
10.1
6.1
13.5
30.6
11.2
3.9
20.2
10.6
3.1
2.0
5.3
1.5
CLMPPT
45.3
5.3
4.7
10.2
12.2
5.6
14.9
33.6
14.2
4.5
24.0
6.8
2.3
1.6
4.8
2.5
GNN-QE
53.6
8.0
6.0
10.7
13.3
16.0
13.5
47.5
9.8
4.7
19.4
5.5
6.4
5.8
3.3
4.4
ICEWS18-H BELLO96+H
ULTRAQ
38.9
6.1
4.1
7.9
10.2
15.8
9.3
28.1
9.5
4.2
15.6
4.5
5.9
4.3
2.7
3.6
CQD
60.4
9.6
4.2
18.5
19.6
18.9
22.6
46.3
18.5
2.0
24.8
4.2
1.5
1.5
4.9
2.6
CQD-Hyhrid
60.4
9.0
6.1
12.1
14.4
17.4
21.2
46.4
19.3
3.5
20.4
5.1
1.2
1.4
4.3
2.4
ConE
53.1
7.9
21.8
23.6
14.9
8.8
27.6
4.6
2.7
6.4
QTO
60.3
9.8
8.0
14.6
15.8
17.6
21.1
49.1
18.9
7.0
20.9
10,2
2,3
3.1
8,4
2.4
CLMPT
58.1
10.1
7.8
22.7
25.0
17.2
24.4
50.0
22.0
7.2
29.1
6.5
2.4
4.1
2.3
4.5
GNN-QE
12.2
0.9
0.5
16.1
26.5
19.1
3.5
7.6
1.1
0.4
34.0
4.5
6.9
0.9
3.5
0.8
ULTRAQ
6.3
1.2
7.0
11.7
8.8
1.2
15.9
2.3
2.2
1.6
CQD
16.6
2.5
1.5
13.0
19.5
17.1
6.7
6.8
5.9
1.1
24.0
1.5
2.9
0.2
2.7
0.9
CQD-Hyhrii
16.6
2.6
1.5
15.0
25.5
17.5
5.8
6.8
5.6
33.2
1.7
4.0
0.3
2.2
1.1
ConE
3.5
0.9
0.9
1.2
0.5
1.2
1.6
1.1
0.9
0.6
0.3
1.7
2.9
1.1
0.9
1.3
QTO
16.6
2.6
1.4
15.7
25.0
18.4
6.2
6.7
4.9
1.1
31.5
4.9
8.7
1.2
3.0
0.9
CLMPT
4.7
12.0
23.0
9.7
2.1
2.2
31.0
1.2
0.1
1.0
0.2
CQA FB15k237 and NELL995 can be explained by their memorization ability.
Our benchmarks are built with the same amount of partial-inferenee and full-inference QA pairs that depend on the query type, allowing to measure CQA performance while not distorting the aggregated performance across all QA pairs, Additionally, ICEWS18+H highlights that more real- istic sampling strategies are challenging for current SoTA.
Takeaway 3.
We then created a set of new benchmarks FB15K237+H, NELL995+H and ICEWS18+H that comprise the same amount of full-inference and partial-inference QA pairs. The MRR performance of existing CQA greatly drops on new benchmarks. We consider new benchmarks to be stepping stone towards benchmarking truly com- plex reasoning with ML models and advise all future works on CQA to use them. However, both the old and our new benchmarks only consider queries with bindings single target variables. While this reflects an important class of queries on real-world KGs, many real-world queries require bindings multiple target variables (i.e. answer tuples). We plan to extend our current study of the "real hardness" of CQA benchmarks to other popular settings in neural query answering, such as inductive scenarios (Galkin et al., 2022; Arun et al., 2025) where some entities and/or relations are unseen during the test stage. Moreover, our work could also extended to queries requiring bindings multiple target variables (Yin al., 2023), and to queries having DAG structure (He et al., 2025).
7. Conclusion
In this paper, we revisit CQA on KGs and reveal that the "good" performance of SoTA approaches predominantly comes from answers that be reduced to easier types (Table 2), the vast majority of which boiling down to single link prediction (Table !). We perform such an analysis by dissecting the arbitrary assumptions that were used to cre- ate these datasets and by highlighting how current neural and hybrid solvers can exploit (different) forms of triple memorization to make complex queries much easier. We confirm this by reporting their performance in a stratified analysis and by proposing which, while being simple extension of an old method like CQD, can be very competitive against other SoTA models. This reveals that FB15k237 and NELL995 are not suitable to precisely assess the capability of CQA methods to an- swer complex queries and that most of their performance of
hybrid solver, CQD- (yb-Hy
Impact Statement
This work analyses current CQA benchmarks for knowledge graphs and shows that the way benchmarks are created

---

Is Complex Query Answering Really Complex?
inflates perceived progress in the field. By demonstrating that most benchmark queries can be reduced to simpler problems and developing new, more balanced benchmarks, this work helps establish more accurate measures of model performance in CQA tasks. The findings have important implications for how the research community evaluates and develops CQA systems, potentially leading to more robust and capable models to better handle truly complex queries.
Arakelyan, E., Minervini, P., Daza, D., Cochez, M., and Augenstein, I. Adapting neural link predictors for data- efficient complex query answering. In Oh, A., Naumann, T., Globerson, A., Saenko, K., Hardt, M., and Levine, S. (eds.), Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, NeurIPS 2023, New Orleans,
LA, USA, December 10 16. 2023, 2023.
Arun, A., Kumar, S., Nayyeri, M., Xiong, B., Kumaraguru, P., Vergari, A., and Staab, S. Semma: A semantic aware knowledge graph foundation model, 2025. URL https: / //aaxiiv.co org/ abs 20422
Author Contributions
AV, CG, and LL conceived the initial idea for which existing benchmarks were not hard enough for complex query an- swering. AV, CG, DH, and LLL had the intuitionn that a simple hybrid solver could obtain SoTA results on the old bench- marks. 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.
Bai, Y., Lv, X., Li, J., and Hou, L. Answering complex logical queries on knowledge graphs via query compu- tation tree optimization. In Krause, A., Brunskill, E., Cho, K., Engelhardt, B., Sabato, S., and Scarlett, J. (eds.), International Conference on Machine Learning, ICML 2023, 23-29 July 2023, Honolulu, Hawaii, USA, volume 202 of Proceedings of Machine Learning Research, pp. 1491. PMLR, 2023.
Bollacker, K. D., Evans, C., Paritosh, P. K., Sturge, T., and Taylor, J. Freebase: a collaboratively created graph database for structuring human knowledge. In SIGMOD Conference, pp. 1247-1250. ACM, 2008.
Bordes, A., Usunier, N., Garcia-Duráae A., Weston, J., and Yakhnenko, O. Translating embeddings for modeling multi-relational data. In Burges, C. J. C., Bottou, L., Ghahramani, Z., and Weinberger, K. Q. (eds.), Advances in Neural Information Processing Systems 26: 27th An- nual Conference on Neural Information Processing Sys- tems 2013. Proceedings of a meeting held December 5-8, 2013, Lake Tahoe, Nevada, United States, pp. 2787-2795, 2013.
Acknowledgements
AV was supported by the "UNREAL: Unified Reasoning Layer for Trustworthy ML." project (HP/YY23338/11 se- lected by the ERC and funded by UKRI EPSRC. PM was partially funded by ELIAI (The Edinburgh Labora- tory 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 the CHIPS Joint Undertaking (JU) under grant agreement No. 101 140087 (SMARTY), and by German Federal Ministry of Education and Research (BMBF) under the sub- aub-project with the funding number 16MEE0444. CG acknowledge compute time on HoreKa HPC (NHR @ KIT), funded by the BMBF and Wurttembrr' 's MWK through the NHR program, with additional support from the DFG. BX, DH were supported by the Deutsche Forschungsgemein- schaft (DFG, German Research Foundation)- SFB 1574- 471687386.
Boschee, E.,, Lautenschlager, J., Orien, S., Shellman, S., Starz, J., and Ward, M. ICEWS Coded Event Data, 2015.
Carlson, A., Betteridge, J., Kisiel, B., Settles, B., Jr., E. R. H., and Mitchell, T. M. Toward an architecture for never-ending language learning. In Fox, M. and Poole, D. (eds.), Proceedings of the Twenty-Four Fourth AAAI Con- ference on Artificial Intelligence, AAAI 2010, Atlanta, Georgia, USA, July 11-15, 2010, pp. 1306-1313, AAAI Press, 2010. doi: 10.
Chen, X., Hu, Z., and Sun, Y. Fuzzy logic based logical query answering on knowledge graphs. In AAAI, pp. 3939-3948. AAAI Press, 2022.
References
Arakelyan, E., Daza, D., Minervini, P., and Cochez, M. Complex query answering with neural link predictors. In 9th International Conference on Learning Representa- tions, ICLR 2021, Virtual Event, Austria, May 3-7, 2021. OpenReview.net, 2021.
Choudhary, N., Rao, N., Katariya, S., Subbian, K., and Reddy, C. K. Self-supervised hyperboloid representations from logical queries over knowledge graphs. In wWW, pp. 1373-1384. ACM/ 3W3C2, 2021.
10

---

Is Complex Query Answering Really Complex?
Dalvi, N. N. and Suciu, D. The dichotomy of probabilistic inference for unions of conjunctive queries. J. ACM, 59 (6):30:1-30:87, 2012.
Ren, H. and Leskovec, J. Beta embeddings for multi-hop logical reasoning in knowledge graphs. In Larochelle, H., Ranzato, M., Hadsell, R., Balcan, M., and Lin, H. (eds.), Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, vir- tual, 2020.
Galkin, M., Zhu, Z., Ren, H., and Tang, J. Inductive logi- cal query answering in knowledge graphs. Advances in neural information processing systems, 35:15230-15243, 2022.
Ren, H., Hu, W., and Leskovec, J. Query2box: Reason- ing over knowledge graphs in vector space using box embeddings. In 8th International Conference on Learn- ing Representationss ICLR 2020, Addis Ababa, Ethiopia. April 26-30, 2020. OpenReview.net, 2020.
Galkin, M., Yuan, X., Mostafa, H., Tang, J., and Zhu, Z. To- wards foundation models for knowledge graph reasoning. In ICLR. OpenReview.net, 2024a.
Galkin, M., Zhou, J., Ribeiro, B. F., Tang, and Zhu, Z. Zero-shot logical query reasoning on any knowledge graph. CoRR, abs/2404.07198 2024b.
Ren, H., Galkin, M., Cochez, M., Zhu, Z., and Leskovec, J. Neural graph reasoning: Complex logical query answering meets graph databases. arXiv preprint WIXx:2333..4617,, 2023.
Guu, K., Miller, J., and Liang, Traversing knowledge graphs in vector space. In EMNLP, pp. 318-327. The Association for Computational Linguistics, 2015.
Ruffinelli, D., Broscheit, S., and Gemulla, R. You CAN teach an old dog new tricks! on training knowledge graph embeddings. In ICLR. OpenReview.net, 2020.
Hamilton, W. L.., Bajaj, P., Zitnik, M., Jurafsky, D., and Leskovec, J. Embedding logical queries on knowledge graphs. In Bengio, S., Wallach, H. M., Larochelle, H., Grauman, K., Cesa-Bianchi, N., and Garnett, R. (eds.), Advances in Neural Information Processing Sys- tems 31: Annual Conference on Neural Information Pro- cessing Systems 2018, NeurlPS 2018, December 3-8, 2018, Montréal, Canada, pp. 1030-204:3 2018.
Sun, H., Arnold, A. O., Bedrax- Weiss, T., Pereira, F., and Cohen, W. Faithful embeddings for knowledge base queries. In NeurIPS, 2020.
Toutanova, K. and Chen, Observed versus latent features for knowledge base and text inference. In CVSC, pp. 57-66. Association for Computational Linguistics, 2015.
He, Y., Xiong, B., Hernández, D., Zhu, Y., Kharlamov, E.,, and Staab, S. Dage: Dag query answering via relational combinator with logical constraints. In Proceedings of the ACM on Web Conference 2025, pp. 2514-2529, 2025.
Trouillon, T., Dance, C. R., Gaussier, É.,, Welbl, J., Riedel, S., and Bouchard, G. Knowledge graph completion via complex tensor factorization. J. Much. Learn. Res., 18: 130:1-130:38, 2017.
Hogan, A. Sparql query language. The Web of Data, pp- 2020.
Hogan, A., Blomqvist, E., Cochez, M., d' Amato. C., Melo, G. D., Gutierrez, C., Kirrane, S., Gayo, J. E. L., Nay- igli, R., Neumaier, S., et al. Knowledge graphs. ACM Computing Surveys (Csur), 54(4):1-37, 2021.
van Krieken, E., Acar, E., and van Harmelen, F. Analyzing differentiable fuzzy logic operators. Artificial Intelli- gence, 302:103602, 2022.
Wang, Z., Song, Y., Wong, G. Y., and See, S. Logical message passing networks with one-hop inference on atomic formulas. ICLR, 2023.
Loconte, L., Di Mauro, N., Peharz, R., and Vergari, A. How to turn your knowledge graph embeddings into generative models. In Oh, A., Naumann, T., Globerson, A., Saenko, K., Hardt, M., and Levine, S. (eds.), Advances in Neural Information Processing Systems, volume 36, pp. 77713- 77744. Curran Associates, Inc., 2023.
Xiong, W., Hoang, T., and Wang, W. Y. Deeppath: A reinforcement learning method for knowledge graph rea- soning. In Palmer, M., Hwa, R., and Riedel, S. (eds.), Pro- ceedings of the 2017 Conference on Empirical Methods in Natural Language Processing, EMNLP 2017, Copen- hagen, Denmark, September 9-11, 2017, pp. 564-573. Association for Computational Linguistics, 2017. doi: 10.18653/V1/D17-2 1060.
Nickel, M., Jiang, X., and Tresp, V. Reducing the rank in relational factorization models by including observable patterns. In Ghahramani, Z., Welling, M., Cortes, C., Lawrence, N. D., and Weinberger, K. Q (eds.), Advances in Neural Information Processing Systems 27: Annual Conference on Neural Information Processing Systems 2014, December 8-13 2014, Montreal, Quebec, Canada, pp. 1179-1187, 2014.
Yin, H., Wang, Z., Fei, W., and Song, Y. EFO To- wards knowledge graph complex query answering beyond set operation, arXiv preprint arXiv:2307.13700 2023.

---

Is Complex Query Answering Really Complex?
Yin, H., Wang, Z., and Song, Y. Rethinking complex queries knowledge graphs with neural link predictors. In The Twelfth International Conference on Learning Represen- tations, ICLR 2024. Vienna, Austria, May 7-11, 2024. OpenReview.net, 2024.
Zhang, C., Peng, Z., Zheng. J., and Ma, Q. Conditional logical message passing transformer for complex query answering. In Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pp. 4119-4130, 2024.
Zhang, Z., Wang, J., Chen, J., Ji, S., and Wu, F. Cone: Cone embeddings for multi-hop reasoning over knowl- edge graphs. In NeurlPS, pp. 19172-19183, 2021.
Zhu, Z., Galkin, M., Zhang, Z., and Tang, Neural- symbolic models for logical queries knowledge graphs. In ICMI., volume 162 of Proceedings of Machine Learn- ing Research, pp. 27454-27477. PMLR, 2022.
12

---

Is Complex Query Answering Really Complex?
A. Additional analysis on the old benchmarks
A.1. Influence of existing links on queries involving negation
In Table A.I we show an analysis for queries involving negation. For such analysis, we split the reasoning tree, defined in Sec. 3, into two subparts, namely positive reasoning tree, composed by the non-negated triples, and the negative reasoning Iree, only composed by the negated triples. In particular, in the same spirit of Table 1, by only looking at the positive reasoning tree, we report the percentage of QA pairs that can be reduced to easier types (partial-inference) and the that cannot be reduced to a simpler type (full-inference). Furthermore, we argue that also the negative reasoning tree contains training triples, but how this propagates to performance is less clear than the positive part, as each method treats negation differently. Table A. shows that in both FB15k237 and NELL995, queries can be reduced to easier types, revealing that our analysis also extends to negated queries. The only exceptions are 2in, 2nulp where the positive reasoning tree consists of a single link, see App. B. Consequently, no reduction to partial inference is possible (see Sec. 3).
Table A.J. Most negated queries have training links in the positive reasoning tree of the QA pairs, Partial-inferene and full-inference refer to the positive reasoning tree. refers to reductions that are not possible.
FB15k237
NELL995
partial-inference
full-inference
partial-inference
full-inference
2in
100
100
3in
95.4
4.6
93.9
6.1
2p
98.4
1.6
97.8
2.2
2nulp
100
100
2in1p
97.4
2.6
95.6
4.4
A.2. Additional comparisons
Table A.5 and Table A.4 show the full results of FB15k237 and NELL995, including the results comparing all methods, all query types, and the subtypes they reduced to.
Moreover, A.3 show the full results of the union queries, including the old overall results, which include QA pairs having non-existing links in their reasoning tree (see Figure 3), and the "new overall", in which those QA pairs are filtered out. In particular, for "2ulp" queries, we observe that for FB15k237, the full-inference queries have a higher MRR than the overall, while for NELL995, we find the MRR results on full-inference QA pairs to be lower than the new overall results as expected, We attribute the results on FB15k237 to the presence of bias in the QA pairs due to their scarcity in the benchmarks. We argue that for the same reason, 2ulp performances are not comparable 2p. However, we will show that for the full-inference QA pairs in the new benchmark, our claim is confirmed (see Tables D.3 to D.5).
Moreover, for query types including negation, results in Table A.2 show the same pattern of Table 2, i.e. the MRR of the full-inference QA pairs is much lower than the one of the partial-inference QA pairs and of the overall.
Performance analysis of QTO The stratified MRR performance of QTO (Bai et al., 2023) for the old benchmarks have been included in Tables A.4 and A.5, For fair comparison, remark that we used the same link predictor for CQD, CQD-Hybrid, and QTO. Details and hyperameters are available in App. F.I. Our analysis reveals that, similarly to the other baselines, QTO performance drops when evaluated on the full-inference QA pairs only (diagonal), w.r.t overall results. Moreover, even when QTO is the SoTA on a certain query type, most of the time it is not so on the portion of full-inference QA pairs only, showing that improving performance on the partial-inference QA pairs not necessarily results on improvements over the full-inference ones.
Moreover, results on NELL995, shown in Table A.4, reveal that CQD-Hybrid outperforms QTO for some query types of NELL995, i.e. 3i, 1 1p2i, 2i suggesting that even by only setting a score=1 to the training triples it is possible to obtain SoTA results on the old benchmarks. We remark that, while both in CQD-Hybrid and QTO score=1 is set to the training links, QTO is much more sophisticated than CQD-Hybria as they 1) calibrated the scores with a heuristics, 2) store a matrix [V| x [V] for each relation name containing the score for every possible triples, 3) have a forward/backwarr mechanism in the reasoning.
13

---

Is Complex Query Answering Really Complex?
Table A.2. Even for queries including negation MRR results are highly influenced by the presence existing links positive reasoning tree of the QA pairs. For example, for 3in queries of FB15k237, the overall MRR of QTO is 16.1, while its MRR on the portion of full-inference QA pairs only 2.1. Hence, overall result highly influence by vast number of partial inference QA pairs in the benchmark (see Table A.1)
FB15k237
NELL995
Query type
method
overall
partial-inf
full-inf
overall
partial-inf
full-inf
GNN-QE
6.8
6.8
5.5
5.5
ULTRAQ
5.3
5.3
4.5
4.5
2in
CQD
3.3
3.3
4.2
4.2
CQD-hybrid
4.7
4.7
5.1
5.1
QTO
10.6
10.6
10.2
10.2
ConE
5.1
5.1
4.6
4.6
CLMPT
6.8
6.8
6.5
6.5
GNN-QE
11.3
11.7
1.1
9.0
9.5
0.6
ULTRAQ
9.6
9.9
0.6
8.2
8.6
0.7
3in
CQD
7.9
6.5
CQD-hybrid
10.4
10.7
1.1
8.3
8.8
0.7
QTO
16.1
16.7
2.1
14.2
14.9
1.2
ConE
8.0
8.3
1.7
6.5
6.8
1.3
CLMPT
13.1
7.9
GNN-QE
4.8
4.8
1.8
3.7
3.7
1.5
ULTRAQ
3.6
3.2
2pilpn
CQD
2.0
2.0
0.6
2.2
2.2
1.4
CQD-hybrid
3.1
3.1
1.1
3.1
3,2
0.8
QTO
8.9
9.0
2.5
7.4
7.5
2.7
ConE
3.0
CLMPT
4.6
3.7
3.2
GNN-QE
5.0
3.3
3.3
ULTRAQ
3.7
3.7
2.7
2.7
2nulp
CQD
4.9
4.9
4,9
4.9
CQD-hybrid
3.2
3.2
4.3
4.3
QTO
5.3
5,3
8,4
8.4
ConE
3.3
3.3
2.7
CLMPT
4.8
4.8
4.5
4.5
GNN-QE
5.2
5.4
5.5
ULTRAQ
3.8
3.8
1.4
4.7
4.8
1.9
2inIp
CQD
3.6
3.6
1.4
5.5
5.5
2.6
CQD-hybrid
4.1
4.1
1.5
6.6
6.7
2.5
QTO
7.9
7.4
ConE
6.3
6.4
3.0
7.5
7.6
4.0
CLMPT
7.9
6.1
3,0
11.6
7.8
4.2
A.3. Influence of intermediate existing entities on the results
For query types having intermediate variables, i.e., 2p, 3p, 2ilp, Ip2i, and 2ulp, we analyzed how the number of existing intermediate entities matching the existentially quantified variables could influence the results. We refer to this number as cardinality of existing entities. For example, in Figure the entities "When in Rome" and "Spiderman 2" are existing intermediate entities matching the existential quantified variable V for the query 91- The intuition is that while some of these entities simplify the prediction of the answers of the query (see Sec. 3), some others might be misleading for the prediction. Hence, if there a high number of existing entities in the path, it would be harder for the model to select only the existing entities needed to predict the next link. For this reason, claim that high value of cardinality of existing entities would make QA pair hurder.
To support our claim, we analyze the percentage of QA pairs having different values of cardinality, shown in Figure A.2 and their MRR, using CQD (Arakelyan et al., 2021), shown Figure A. Figure A.1 shows that CQD results are 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 Figure A.2, one can understand if results on specific query type are highly influenced by
14

---

Is Complex Query Answering Really Complex?
Table A.3. Full inference QA pairs show higher performance than non-filtered, while full-inference 2ulp pairs show or comparable performance. Results union queries for existing benchmarks and comparison between old and new overalls. *.' refers to reductions are not possible, while reductions are possible are not present the data.
FB15k237
NELL995
Query type
method
overall
overall (new)
1p
2u
2ulp
overall
overall (new)
1p
2u
2ulp
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
ConF
14.3
29.9
29.9
14.9
28.2
28.2
GNN-QE
13.4
9.7
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
2ulp
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
high proportion of QA pairs having the same cardinality. For example, the MRR of Ip2i partial-inference QA pairs in FB15k237 is highly influenced by the presence of about 30% of QA pairs having cardinality of "1".
A.4. 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 anchor entity is present multiple times in query, this is counted only once. As shown in Table A.6, for FB15k237 and NELL995 we find that in most cases there is no predominant relation name nor anchor entity. However, there are exceptions, as for example, for anchor entities 3i queries of FB15k237, where the anchor node "USA" present 30.1% of them, and for 2u queries, where present 22.5%. We also notice that there is predominance USA as an anchor entity across vast majority of query types, which is most likely given by the vast presence of this entity in the knowledge graph.
15

---

Is Complex Query Answering Really Complex?
Figure A.I. Higher cardinality of intermediate existing entities leads to lower MRR. Influence of the number of existing intermediate variables on the MRR for datasets FB15k237 and NELL995, using CQD.
2p
3p
1p2i
211p
2u1p
FB15K-237
NAR partial
20
0
1
2-9
10.99
100+
0
1
2.9
10.99
100+
0
1
2-9
10-
10-99
+
0
1
2-9
10-99
100+
0
1
2-9
10-99
100+
2p
3p
1p2i
211p
2u1p
NELL995
50
25
0
1
2-9
10-99
10.
100+
0
1
2-9
10
19
+00+
0
1
2-9
10-
10-99
100+
0
1
2-9
10-99
10-
100+
0
1
2
10:
10-99
100+
Figure A.2. Proportion afQA pairs having different cardinality of intermediate existing entities in the old benchmarks.
2p
3p
1p2i
211p
2u1p
FB15k-237
partial
20
0
0
1
2-9
10-99
100+
0
1
2-9
10-99
100+
0
1
2-9
10-99
100+
0
1
2-9
10-99
100+
0
1
2-9
10-99
100+
2p
3p
1p2i
2i1p
2u1p
NELL995
20
2-9
10-99
100+
0
2-9
10.99
100+
0
1
2-9
10.99
+00+
0
1
2-9
10.99
100+
0
2-9
10-99
100+
10
16

---

Is Complex Query Answering Really Complex?
Table A.4. The best model all available NELL995 queries (column "overall") and the best the full inference queries (diagonal) different for 6/7 query types, excluding 1p and 2u, being already of type full-inference. Comparison of MRR scores for SoTA methods for the different subtypes NELL995 queries be reduced Best in bold.
Query type
method
overall
2p
21
3i
1p2i
2:1p
Zulp
GNN-QE
53.6
53.6
ULTRA-query
38.9
38.9
ConE
60.0
60.0
CQD
60.4
60.4
CQD-hybrid
QTO
60.3
60.3
CLMPT
58.1
58.1
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
hybrid
QTO
24.7
25.1
7.3
CLMPT
22.1
22.3
8.9
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
CQD
7.8
CQD-hybrid
17.8
17.2
9.9
QTO
22.6
22.3
10.9
7.7
CLMPT
18.3
17.7
10.7
8.2
Zi
GNN-QE
40.0
41.4
3.6
ULTRA-query
36.3
37.5
3.2
39.6
40.6
8.0
42.2
CQD hybrid
44.2
45.7
6.7
QTO
44.2
45.7
5.1
CLMPT
41.6
42.5
8,9
3i
GNN-QE
50.9
53.6
10,9
2.2
ULTRA-query
47.7
50.0
11.3
1.5
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
QTO
56.2
60.0
12.4
2.4
CLMPT
$1.7
53.4
20.3
5.3
1p2i
GNN-QE
29.1
42.7
21.4
12.0
10.2
ULTRA-query
25.1
39.0
25.6
8.2
26.1
CQD
31.5
44.0
25.7
14.5
12.6
CQD-hybrid
33.2
48.7
24.2
13.7
94
QTO
32.8
47.4
22.0
14.5
9.8
CLMPT
29.0
39.3
15.3
21.8
12.1
2ilp
GNN-QE
20.5
20.8
16.3
14.6
20.7
ULTRA-query
9.5
9.6
ConE
17.6
16.4
25.7
CQD
25.8
25.9
21.2
26.3
23.6
CQD-hybrid
28.4
28.9
20.4
22.8
23.3
QTO
28.2
28.5
20.2
24.0
24.4
CLMPT
24.7
24.6
26.5
26.7
GNN-QE
34.8
ULTRA query
ConFi
28.2
28.2
CQD 35.9
35.9
hybrid
35.9
35.9
QTO
37.6
37.6
CLMPT
2ulp
GNN-QE
8.8
6.3
53.1
ULTRA-query
8.4
ConE
7.0
9.4
43,2
4.0
CQD
14.6
14.2
51.8
9.5
CQD-hybrid
15.0
14,5
53.5
9.6
QTO
16.4
15.8
61.2
9.6
CLMPT
17

---

Is Complex Query Answering Really Complex?
Table A.5. The best model all available FB15k237 queries (column "overall") and the best the fuil inference queries (diagonal) different for 5/7 query types, excluding p and 2u, those (q.a) pairs heing all of type full-inference. Comparison of MRR scores for SoTA methods for the different subtypes FB15k237 queries be reduced to. Best bold.
Quety type
method
overall
1p
3p
2i
1p2i
2i1p
2u
2alp
GNN-QF
42.8
42.8
UlTRy-
40.6
40.6
ConE
41.8
41.8
CQD
46.7
46.7
CQD-hybrid
QTO
46.7
46.7
CLMPT
45.3
45.3
GNN QE
14.7
14.8
4.7
ULTRAA-uery
11.5
11.5
4.2
ConE
12.8
12.8
CQD
CQD CQD-hyhrid
QTO
16.6
16.7
CLMPT
13.9
13.9
5.1
GNN-QE
11.8
12.0
4,4
4.8
ULTRA-query
8.9
9.0
4.6
4.4
ConE
11.0
2.6
CQD
CQD-hybrid
11.0
11.1
4,4
QTO
15.6
15.8
4.5
5.0
CLMPT
11.3
11.3
6.1
4.0
2:
GNN-QE
38.3
39.3
4.0
ULTRA-query
35.7
36.7
3.4
ConE
32.6
5.5
CQD
CQD-hyhrie
37.6
38.7
3.8
QTO
39.7
40.8
5.7
CLMPT
37.5
38.4
7.3
3i
GNN-QE
54.1
56.0
10.9
5.2
ULTRA-query
52.9
9.7
ConE
CQD
CQD-hybrid
52.7
54.8
9.9
4.6
QTO
54.6
56.4
15.4
5.4
CLMPT
51.9
53.1
17.7
5.9
Ip2i
GNN-QE
31.1
32,8
15.5
5.7
9.1
ULTRA-query
19.2
422
7.4
ConFi
9.7
CQD
28.7
13.4
7.1
9.0
CQD-hybrid
31.2
33.4
14.8
4.8
7.0
QIO
33.8
35.9
15.8
6.2
7.3
CLMPT
30.0
16.2
5.9
8.3
2ilp
GNN-QE
18.9
19.2
8.2
6.2
3.4
ULTRA-query
18.9
5.1
ConE
14.0
13.8
5.6
CQD
20.7
21.0
10.5
6.7
7.6
CQD-hybrid
24.0
24.6
10.0
46
7.5
QTO
24.7
25.3
10.3
8.6
8.1
CLMPT
19.1
7.9
13.2
GNN-QE
40.7
40.7
query
ConF
29.9
CQD
32.7
32.7
CQD hyhrid
32.7
32.7
QTO
37.0
37.0
32.8
2u1p
GNN-QE
50.9
13.1
ULTRA-query
33.2
ConE
7.4
20.3
11.9
CQD
10.5
10.4
13.7
14.7
CQD-hybrid
10.3
10.0
18.5
13.6
QTO
12.2
11.6
35.3
11.3
CLMPT
18

---

Is Complex Query Answering Really Complex?
Table A.6. There is no significant unbalancement anchor nor relation names 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(Se
FB15k237
1p
film rwweeeeeeeeec... region
7.5
USA
0.7
2p
location//ocatioo/contiia/
8.6
USA
4.0
3p
location//lccatio//cmaaail
11.6
USA
3.3
2i
people/persoo/prooessiii
16.4
USA
16.4
3i
people/person/gendee
18.7
USA
30.1
pi
people/person/proeessii
13.7
USA
14.1
ip
people/person/prooession
8.6
US dollars
5.7
2u
film/film_cm www.mmwwwwww....omo...e...... role
14.6
USA
22.5
Zulp
taxonomy entry/taxonomy
9.9
mm/08mbj5d
5.4
2in
people/person/procssiii
15.7
USA
15.2
3in
common/weeppageccateggnr
20.7
USA
28.5
2pilpn
people/person/prooessiin
12.4
USA
11.7
2nu1p
people/person/professiio
17.1
USA
14.5
2p
location/contains
13.4
USA
14.3
NELL995
1p
concept:atdate concept:mutualproxyyii
9.4
concept_stateorprovince wwt.prooooiiin....oonniii callifornia
0.5
2p
8.7
concept_lake, haapp__lae_eeeee _new concept_book _new concept_booke concept_compang --phs
1.5
3p
moncept
15.9
2.5
2i
concept:atdate
22.5
_now__ewoo__wwww_ww_wo__ nnww
7.6
3i
concept:atdate
21.6
12.0
pi
concept:proxyfor
11.4
concept_ book new concept.athle athlete sinorice moss concept.compen pbs concept Lathlete sinorice
6.1
ip
cubcept:subpartof
9.4
3.8
2u
concept:atdate
10.8
4.9
2ulp
cuncept:subpartof
11.1
3.3
2in
conceptaatdte
20.9
concept. bookk nnew
6.8
3in
concept:atdaee
45.8
concept_book wtt__boo__eeeee
14.2
2pilpn
concept:proxyfor
14.9
concept_booe hrooptt_boo__ewwee
5.7
2nu1p
concept:proxyfor
21.9
concept_book nnew
8.0
2in1p
concept:atdate
15.0
concept_lake.uu Jew
19

---

Is Complex Query Answering Really Complex?
cogiinction
eoglastno negation Ace
2ln1p
2p1imp
2mu1p
Aquunctiin Ank
Figure B.I. Query structures including negation, adapted from Ren Leskovec (2020), where "Zinlp" queries referred as "inp". We explicitly mention the number of steps involved in path or conjunction, as this is factor of complexity. Analogously, "pin", "pni" queries from Ren Leskovee (2020) are now "Apilnp", and "2nulp". See App. B for their logical formulation.
B. Query types including negation
In Figure B.1 we include the query types including the negation operator involved in the analysis described in App. A. Those queries are obtained by adding a negation to some of the query structures described in Sec. 2. For example, by negating a triple pattern involved in the intersection of a 2i, 3i, 2ilp queries, we obtain respectively:
?T: (41,71,7) A (2,2,22 T):
(2in)
F2, F2, A -(a3, Fs, T); ?T: (a1,71, T) (a2,
(3in)
?T: EVi-((a), Vi) A -(02, 72, V1) (V1, 13, T)),
(2inlp)
Moreover, by placing the negation in different triple patterns of the query type Ip2i, we obtain two query types:
?T VV--(( F1, Vi) (Vi, r2, r2, A ( r3: 7));
(2pilpn)
where the negation placed in the triple pattern directly involved in the intersection, and
?T: (VV1(-(((1,,)))) Vi) (21,r,,)) (a2, Tay T)),
(n2pilp)
where the negation placed on the path query 2p. Using De Morgan laws, this query can also be rewritten as:
?T (Wi-(-(an,m,,, Vi) (V,, A (az, r3, T)),
(2nulp)
Note that the visual representation of 2nulp provided by (Ren & Leskovee, 2020) was misleading, as in practice the negation applied on the whole 2p query, rather than just on one of its links.
C. More related works
Guu et al. (2015) propose compositional training for embedding methods to predict answers for path queries. GQE (Hamilton et al., 2018) learns a geometric intersection operator to answer conjunctive queries in embedding space; this approach was later extended by Query2Box (Ren et al., 2020), BetaE (Ren & Leskovec, 2020), and GNN-QE (Zhu et al., 2022). FuzzQE (Chen et al., 2022) 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., 2021) and ConE (Zhang et al., 2021) 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 al., 2020) ensembles an embedding model and count-min sketch, and is able to find logically entailed answers, while CQD (Arakelyan et al., 2021; 2023) extends pretrained knowledge graph embedding model to infer answers for complex queries.
20

---

Is Complex Query Answering Really Complex?
FB15k-2377 2815k-237+H
2p
3p
4p
1p2i
2i1p
2u1p
part VRR ful
50
2.9
10.
10.800+
0
2.9
10
09
100+
2.9
10-00
100+
1
2.9
10-
100
1
2.9
10-
99
100+
0
1
2.9
10- 09
100+
2p
3p
4p
1p2i
2i1p
2u1p
NELL995+
25
0
22.
10-880+
280+
0
2.9
100
+
0
2-9
99
100+
+
2.9
10 100
2.9
10 100+
2.9
10 100+
10
10
10
2p
3p
4p
1p2i
Zi1p
2ulp
ICEWS18+H
20
2.9
10-800
2.9
100+
2.9
10.90
100+
2.9
10.02
100+
2
2
10-00
20
180+
2
10-99
100+
10-
10
10
Figure D.I. Higher cardinality of intermediate existing entities leads to lower MRR. Influence of the number of existing intermediate variables on the MRR for datasets FB15k237+H, NELL995+H, ICEWS18+H, using CQD.
FB15K-237+H
2p
3p
4p
1p2i
2i1p partaal MI
2ulp
50
0
2.9
10.0
100+
O
2.9
10.90
100+
2-9
10-
90
2.9
00+
2.9
10- 100+
2.9
10: 100+
2p
3p
4p
1p21
211p
2ulp
NELL995+H
20
0
2.9
10-99
10.9
100+
0
10.99
9
10
100+
0
2-9
10
99
0
1
2
10
99
100+
1
2.9
10-
100+
2
10-
99
100+
2p
3p
4p
1p2i
211p
2u1p
ICEWS18+
20
2.9
20.
180
O
29
10:
180+
2.9
10.99
100+
2.9
10-09
10
100+
2
2.9
10
100+
2.9
10:
100+
Figure D.2. Proportion AfQA pairs having different cardinality of intermediate existing entities in new benchmarks.
D. Additional Analysis on the new benchmarks
D.1. Influence of intermediate existing entities on the results
Similarly to what was done for the old benchmarks in App. A, we analyze the proportion and influence (on the MRR) of the number of intermediate existing entities for CQD, on the new benchmarks FB15K237+H, NELL995+H, ICEWS18+H. Figure D.1 show a very similar result to the one in Figure A. showing a decreasing MRR at the increase of the value of cardinality for all benchmarks. Moreover, for reference, we also report the proportion of the different QA pairs for each cardinality category in Figure D.2.
21

---

Is Complex Query Answering Really Complex?
Query
relation name
Frequency((5)
unchor entryy
frequency(8)
FBL5K237-H
1p
filunreleasc ragion
7.5
USA
0.7
2p
/peoplepenoon/siionna
15.3
3.6
3p
14.2
mu/092y4_
5.4
4p
20,0
Am/lldy_5
5.5
21
people/penom/prolesss
17.2
15.5
91
19.6
ImV19:7w0
19.7
41
pespleo/punompproiie ppppoeesiiioo
19.2
Am/09k,700
20.0
pi
peeoplo/pensonvniie
19.7
Am
i
ppoplelppnsoon peneeeppoonngnndee
18.5
8.9
Zin
15.7
USA
15.2
Sin
preople/pensont corpproonngomm onggendrr
20,0
20.0
pp
ppeoplefpen preoono nationality
18.4
2mup
peopletpersoe pwwsso/ppmllssssiiooi
17.1
USA
14.5
pp
peoplerpenno penoomprooesssie professionn
13.6
AmVlkmlyyd
12.2
Zu
pecoplefpersont profession
15.6
Am009,7w0
12.1
2u1p
foummnon wwwpp//wwwooggooooooooooooo wwwp://wwwwww.w..ww/o/eeweeeeeee wwwmmwwwwwwwwyogogggggggggg
19.4
Am/0kk99
NELL995+H
1p
concept-nnatt
9.4
concept wltticoppooiiine califomiia
0.5
2g
concept:prexyyar
17.9
concept_sportstcaum
3p
comceptpprxxyfor
20.0
concepl.gcopolii geopplliicaaloocclll national
5.9
-pp
conceptiatloocee
20.0
concepl weeeiiit now yyrel.imees
6.5
2i
concept-andate
20.0
5.1
concept:atdate
20.0
concept sportskcgne milb
5.7
41
conceptandate
20.0
concept.date m20004
7.9
coocept:proxyfor
15.6
concept book new
7.8
concepttanlatt
19.1
emnceptlake lake
9.1
concept-andate
20.9
concept concept.book._eew book..ew
Sin
conceptandate
20.0
concept spotsscamposition center
15.5
2pi1pn
20.0
concept lake.mew
15.2
2ma1
procept:r
21.9
bookkeebookk.ew
8.0
2in1p
conceptrandate
20.0
concept lake now
2a
comcptaatiate
20.0
concupt
2.7
2ulp
coocept:prosyfar
19.8
concept lake new
11.0
ICEWS184H
1p
Make statement
18.8
United States
3.0
2p
Make statement
20.0
Russia
6.7
3p
Cousult
20.0
United States
3.4
4p
statement
20.0
Yakio Edano
4.4
21
Make starement
20.0
Csizien(Inda))
7.0
3i
Make statement
20.0
Inizien[Indaa)
4,2
4i
Make statement
20.0
United States
4.5
pi
statement
20.0
Unspecified Actor
9.7
ip
Make starement
20.0
Russia
6.6
2in
Make statement
19.9
Unspecified Actor
17.1
3in
Make statement
20.0
Caizien(nnda))
20.0
2p
statement
20.0
States
2na1p
Make starement
19.9
Unspocifedd Actor
16.46
2in1p
Consult
20.0
United States
10.5
2a
Cousult
19,9
China
3.5
2a1p
Make statement
19.9
United Stares
49
Table D. 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 henchmarks.
Imbalances of relation names and anchor nodes When creating the new benchmarks FB15K237+H, NELL995+H, ICEWS18+H, to make sure that no anchor entities nor relation name was predominant in each query type, we set a maximum of 20% of QA pairs having the same anchor entity or relation name across all benchmarks and query type, as shown in Table D.1
Stratified analysis on new benchmarks For reference, we also provide the stratified analysis on the new benchmarks in Tables A.4 and A.5, which shows that 1) the full-inference QA pairs have always lower MRR than the overall, and 2) the overall MRR is much lower than the Ip-reductions only, as for the new benchmark the proportion of QA pairs is equally distributed.
The same considerations also apply to queries including negation, as shown in Table D.6.
D.2. Statistical tests
As an illustrative case, we analyze 2p queries from FB15k237+H to assess whether the observed differences in model performance are statistically significant, despite similar MRR in Table 5. We conduct an all-vs-all paired Mann-Whime test on the reciprocal ranks across all models for each 2p QA pair. The results in Table D.2 reveal strong statistical differences in most pairwise comparisons, indicating that models rank correct answers differently even when aggregate
22

---

Is Complex Query Answering Really Complex?
Model
CLMPT
CQD
CQD-h
ConE
GNNQE
QTO
ULTRA
CLMPT
3.32c-63
182c-80
3.92c-01
8.28c-71
106c-188
8.55c-35
CQD
3.32e-63
1.48c-04
1.94e-52
1.72c-01
5.27e:38
2.31c.06
CQD-h
1.82e-80
1.48e-04
8.88e-75
5.08e-03
8.4e-15
6.91e-16
ConE
3.92c-01
1.94e-52
8.88c-75
6.65c-60
1.38c-165
7.04c-28
GNNQR
8.28e-71
1.72e.01
5.08e-03
6.65e-60
4.79e.30
2.32e-09
QTO
1.0cc-188
5.27e-38
8.41c-15
1.38c-165
4.79c-30
2.22c-70
ULTRA 8.55e-35
2.31e-06
6.91e-16
7.04e-28
2.32e-09
2.22e-70
Table D.2. Pairwise Mann- Mann-Whitney U test p-values on reciprocal ranks of 2p queries FB15k237+H, Lower values indicate stronger evidence of significant difference between model performances.
metrics are close. However, few model comparisons- as ConE vs. CLMPT and CQD vs. GNNQE-cxhibi statistical similarity, suggesting comparable ranking behavior on 2p queries. To examine whether the similarity limited specific query types, we apply the same test across all QA pairs of FB15k237+H from all query types. The resulting p-values are effectively zero for all comparisons, confirming that significant performance differences are widespread, though limited cases of similarity may occur between some models on some specific query types.
23

---

Is Complex Query Answering Really Complex?
Table D.3. Stratified analysis on FB15K237+H
Query type
1p
2p
3p
4p
1p2i
211p
2ulp
1p
GNN-QE
12.8
12.8
ULTRA-query
ConF
41.8
41.8
CQD
46.7
46.7
ayD-y
16.7
16.7
QTO
46.7
46.7
3p
GNN-QE
5.2
11.8
4.4
ConF
4.6
9.9
4.0
CQD
4.5
7.4
ayD-dy
4.8
15.1
QTO
4.9
14.
3.8
CLPPPT
3p
GNN-QE
4.0
16.2
4.6
3.6
ULTRA-query
ConE
3.9
10.1
5.0
3.6
ayD-ay
10.7
2.7
QTO
3.7
21.4
3.0
CLMPT
4p
GNN-QE
4.3
16.1
14.1
4.8
3.8
ULTRA-query
ConE
3.5
12.0
8.8
4.2
3.2
CQD-sybii
2.4
9.8
10.5
4.2
2.0
CLMPT
11.9
13.6
3.9
2i
GNN-QE
6.0
20.4
5.4
ULTRA queery
ConE
9.1
15.5
8.8
CQD-sybri
6.0
22.0
5.1
CLMPT
10.2
18.4
9.7
3i
GNN-QE
8.8
32.2
2.5
7.5
ULTRA-query
7.2
33.4
ConF:
10.3
25.0
6.9
9.0
CQD-sybrd
8.6
38.2
2.7
7.1
CLMPT
12.2
3188
7.6
10.7
GNN-QE
ULTRA-query
16.4
48.9
17.5
13.2
12.9
Coni:
20.3
36.9
24.9
18.2
15.8
cyD-dybrd
17.4
58.3
17.2
13.2
14.6
CLMPT
24.0
40.5
26.7
21.9
18.7
1p2i
ULTRA-query
31.4
7.6
1.9
ConE
3.8
16.7
CQD
20.1
7.2
cyb-dybnd
5.5
33.2
7.7
26
CLMPT
5.6
18.1
5.5
26.5
4,3
ULTRA-
10.1
13.8
18.4
ConE
7.9
10.8
10.4
7.2
CQD
11.5
122
21.7
10.5
CQD-sybmi
12.9
23.0
6.0
24.7
822
QTO
CLMPT
14.9
10.5
9.4
11.0
142
GNN-QE
UUTRA-
29.4
29.4
ConE
22.8
22.8
CQD
40.0
40.0
CQD-sybmi
42.2
42.2
QTO
30.6
30.6
CLMPT
33.6
33.6
Zulp
ULTRA-query
8.3
7.4
42.2
488
ConF.
CQD
10.6
9.2
13.9
8.4
CQD-bybri
12.0
10.5
41.0
8.1
QTO
11.2
100
53,3
6.7
CPMPT
142
83
9.1
134
24

---

Is Complex Query Answering Really Complex?
Table D.4, Stratified analysis on NELL995+H
Query type
2p
3p
4p
1p21
21pp
2ulp
1p
GNN-QE
53.6
53.6
ULTRA-query
ConF
600
(0.0
CQD
60.4
60.4
ayD-yy
60.1
00.4
QTO
60.3
60.3
3p
GNN-QE
8.0
21.6
6.3
ULTRA-query
ConF
7.9
15.3
7.1
CQD
21.7
8.0
ayDdd
9.0
28.4
6.6
QTO
25.9
7.7
GNN-QE
60
33.3
14.1
3.9
ULTRA-query
ConE
6.7
21.0
12.2
5.5
CQD
ayDday
6.1
22:2
10.9
4.4
QTO
8.0
42.1
15.3
5.2
CLMPT
7.8
20.1
10.6
6.4
GNN-QE
4.7
4.9
25.0
11.9
2.8
ULTRA-query
2.9
ConE
5.2
27.3
17.3
7.5
4,5
CQD
CQD-iyhni
3.5
34,9
19.3
8.1
2.1
QTO)
29.1
4.9
CLMPT
7.2
30.0
18.7
7.6
5.8
21
GNN-QE
10.7
24.5
9.8
Auqury
7.9
ConE
2188
23.3
21.1
CQD
CQD-sybnd
12.1
28.7
11.0
QTO
CLMPT
22.7
27.1
21.9
GNN-QE
13.3
34.7
11.7
10.6
ULTRA-query
26.7
7.1
ConE
23.6
31.8
22.5
21.5
CQD
CQD-sybnd
14,1
43.3
11.7
118
QTO
CLMPT
25.0
36.3
23.4
22.2
GNN-QE
24.6
14.3
ULTRA-query
15.6
42.6
24.9
12.2
8.2
ConF:
27.6
47.9
35.0
21,8
23.8
CQD
CQD-yybnd
20.4
65.1
24.9
14.2
14.5
QTO
CLMPT
29.1
50.5
36,9
22.4
24.6
1p2i
GNN-QE
ULTRA-query
15.8
55.0
23.0
5.5
5.9
ConE
14.9
32.6
10.7
7.0
CQD
18.9
54.3
22.1
12.0
10.0
17.4
64.7
19.0
12.4
8.1
QTO
CLMPT
17.2
37.9
18.2
13.1
10.6
GNN-QE
ququryy
9.3
22.2
7.6
22.3
6.0
ConE
11.8
22.6
23.2
8.4
CQD
22.6
29.9
20.1
36.9
16,1
CQD-sshmid
21.2
35.8
18.9
34,5
13.7
QTO
CLMPT
24.4
25.9
21.8
35.2
20.0
GNN-QE
28.1
28.1
ConE
39.9
39.9
COD
46.3
46.3
CQD-lybmdd
46.1
16.1
QTO
49.1
49.1
CLMPT
50.0
50.0
Bulp
GNN-QE
ULuRR--uery
9.5
12.5
36,9
5.1
ConF
8
COD
18.5
18.8
53.5
13.4
CQD-aybrid
19.3
20.5
63.7
13.1
QTO
189
21.1
58.2
11.7
MPT
22.0
17.6
29.7
19.1
25

---

Is Complex Query Answering Really Complex?
Table D.5. Stratified analysis on ICEWS18+H
Query type
1p
2p
3p
4p
1p2i
211p
2ulp
1p
GNN-QE
12.2
12.2
ULTRA-query
ConF
3.5
CQD
16.6
16.6
ayD-y
16.6
16.6
QTO
16.6
16.6
3p
GNN-QE
0.9
2.2
0.8
ConF
09
1.9
0.9
CQD
2.6
ayD-ay
2.6
10.0
QTO
266
844
2.2
CLPPPT
3p
GNN-QE
0.5
1.0
1.2
0.4
ULTRA-query
ConE
0.9
1.5
L44
0.9
ayD-by
1.5
9.8
1.2
QTO
1.4
6.2
1.2
CLMPT
0.2
4p
GNN-QE
0.4
1.6
1.4
1.0
0.3
ULTRA-query
ConE
0.6
1.8
L.8
0.9
0.6
CQD-sybii
0.9
31.4
39.3
20.1
0.7
CLMPT
0.1
2i
GNN-QE
16.1
30,0
2.4
quqery
ConE
1.2
1.9
0.8
CQD-sybni
15.0
27.3
3.3
CLMPT
12.0
20.5
2.3
3i
GNN-QE
26.5
58.5
19.3
2.0
ULTRA-query
25.9
ConF:
0.5
1.2
0.6
0.2
CQD-sybrd
25.6
58.5
15.8
2.7
CLMPT
23.0
44.0
21.4
2.9
GNN-QE
34.0
ULTRA-query
15.9
37.1
19.1
6.0
1.0
Coni:
0.3
0.9
044
0.2
0.1
cyD-sybrd
13.2
78.9
39.4
11.
2.1
CLMPT
31.0
60.3
41.5
18.4
1p
GNN-QE
62.5
ULTRA-query
8.8
19.6
13.2
ConE
12
2.6
1.5
CQD
17.1
25.8
50.1
cyb-dybnd
17.5
66.9
26.2
4.1
3.5
CLMPT
9.7
8.5
15.1
1.0
2,3
UueRr-
1.3
2.3
1.2
1.6
ConE
1.6
2.4
1.6
CQD
6.9
11.1
CQD-sybmi
588
9.2
4.6
148
QTO
CLMPT
2.1
0.5
166
0.4
233
GNN-QE
3.1
3.3
ConF
CQD
CQD-sybmi
6.8
QTO
CLMPT
2.7
2.7
Zulp
ULTRA-query
1.2
1.5
2.0
1.0
ConF
CQD
599
3.2
11.6
5.6
CQD-bybnd
5.6
178
4.5
QTO
17.8
3.7
MPMP
22
03
0.3
2,5
26

---

Is Complex Query Answering Really Complex?
Table D.6. Also for queries involving negation, there clear SoTA method for the benchmarks. The MRR on the new benchmarks is significantly lower than the old ones. For example, for 3in queries FB15K237+H. QTO has an MRR of only 3.1, while for FB15k237 was 16.1.
FB15k237+H
NELL995+H
ICEWS18+H
Query type
method
part-inf
full-inf
par-inf
full-inf
par-inf
full-inf
GNN-QE
6.8
6.8
5.5
5.5
4.5
4.5
ULTRAQ
5.3
5.3
4.5
4.5
2.3
2.3
2in
CQD
3.3
3.3
4.2
4.2
1.5
1.5
CQD-hybrid
4.7
4.7
1.7
QTO
10.6
10.6
10.2
10.2
4,9
4.9
ConE
5.1
5.1
4.6
4.6
1.7
1.7
CLMPT
6.8
6.8
6.5
6.5
1.2
1.2
GNN-QE
6.5
9.0
1.0
6.4
7.2
1.0
6,9
12.6
1.4
ULTRAQ
5.5
7.5
0.6
5.9
6.2
0.9
4.8
7.1
2.4
3in
CQD
2.6
5.9
2.5
2.9
4.0
1.6
CQD-hybrid
1.6
8.4
1.2
1.2
7.9
0.9
4.0
6.5
1.3
QTO
3.1
13.9
2.3
2.3
11.
1.8
8.7
14.5
2,8
ConE
4.9
6.4
2.0
6.0
5.8
2.8
2.9
3.3
2.0
CLMPPT
2.3
9.3
1.7
2.4
5.7
2.1
2.1
3.4
0.9
GNN-QE
3.7
4.0
1.4
5,8
7.0
1.6
0.9
1.0
0.5
ULTRAQ
2.6
2.8
1.3
4.3
5.2
1.2
1.3
0.9
2pilpn
CQD
0.6
1.3
0.5
3.2
1.4
0.2
0.7
0.1
CQD-hybrid
1.0
2.7
0.9
1.4
5.9
1.1
0.3
1.0
0.2
QTO
2.0
7.3
1.7
3.1
9.4
2.6
1.2
3.4
1.0
ConE
2.9
2.7
1.5
3.7
4.9
2.0
1.1
1.3
1.0
CLMPT
1.6
2.9
1.6
4.1
0.1
GNN-QE
5.0
5.0
3.3
3.3
3,5
3.5
ULTRAQ
3.7
3.7
2.2
2nulp
CQD
4.9
4.9
4.9
4.9
2.7
2.7
CQD-hybrid
3.2
3.2
4.3
4.3
2.2
2.2
QTO
5.3
5.3
8.4
8.4
3,0
3.0
ConE
3.3
3.3
2.7
2.7
0.9
0.9
CLMPT
4.8
4.8
2.3
1.0
1.0
GNN-QE QEQ
3.3
1.4
0.8
1.0
0.5
ULTRAQ
2.2
2.2
1.2
3.6
3.7
1.6
1.6
2.2
1.4
2in1p
CQD
1.2
1.3
1.2
2.6
3.5
2.6
0,9
0.2
0.9
CQD-hybrid
1.3
1.1
1.2
2.4
4.1
2.3
1.1
1.9
1.0
QTO
1.5
5.4
1.3
2.4
7.9
1.9
0.9
2.5
0.9
ConE
3.6
2.2
2.3
1.2
CLMPT
2.5
3.4
2.4
4.5
6.3
3.8
0.2
0.1
0.2
27

---

Is Complex Query Answering Really Complex?
Dataset
2p
2i
Ip2i
2ilp
20
2ulp
2in
3in
2pilpn
20u1p
2in1p
k
In
k
k
in
k
tn In
k
tn
in
k
I
k
tn
K.
i In
In
FB15k237
512
p
128
p
128
256
P
64
512
m
512
m
2
p
512
prod 512
prod
512 prod
P
P
P
P
P
P
prod
prod
prod
Table R.I. CQD hyperparameters old benchmarks. tnorm. p=prod, m=min. Note that for 1p neither the k nor the tnorm needed.
E. Queries with four hops
Logical formulation of the 4p and 4i queries we introduced in the benchmarks FB15k237+H, NELL995+H, ICEWS18+H
?T' : 3V1 V2, Va,(ar,7i,1 (V2, ra. Va) A (V),
(1, (V1,72, 1/2A
(4p)
PT: (01, (I,,TT,T) A (a2, T2M
(4i)
(0g, T3, T) A Ta,
F. Hyperparameters
In this section, we detail the hyperparameters used for each dataset and model. Old and new benchmarks, the generation scripts, and the implementation of CQD-hybrid are included in our official repo."
E1. Old benchmarks
GNN-QE We did not tune hyperparameters, but re-used the ones provided in the official repo."
ULTRA
We did not tune hyperparameters, but re-used the ones provided in the official repo."
CQD As mentioned in Sec. 5, we re-used the pre-trained link predictor (Trouillon et al., 2017) provided by the authors. However, tuned CQD-specific hyperparameters, namely the CQD beam "k", ranging from [2,512] and the t-norm type being "prod" or "min" In Table F. we provide the hyperparameter selection for the old benchmarks FB15k237 and NELL995. Also note that we normalize scores with min-max normalization. For negation, always use standard negation.
QTO
We re-used the hyperparameters provided in the official repo 10 For a fair comparison with CQD, CQD-hybrid, we used the same pre-trained link predictor.
CLMPT We did not tune hyperparameters but re-used the ones provided in the official repo."
ConE
We did not tune hyperparameters but re-used the ones provided in the official repo."
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 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 score of assigned the existing triples.
28

---

Is Complex Query Answering Really Complex?
Dataset
2p
3p
21
31
1p
211p
2u
2u1p
41
4p
2in
3in
Spilpn
Zna1p
Zin
ICEWS184H
P
P
P
P
P
P
P
P
P
P
512 prod
512
pood
prod
Table F.2. CQD hyperparameters ICEWS18+H benchmark. tn tnorm. p=prod, m=min
F.2. New benchmarks
For FB15k237+H and NELL995+H, re-used the same models trained for the old benchmarks, and using the same hyperparameters presented in App. F.1. The only exception is the hyperparameters for CQD and CQD-hybrid of 4p and 4i queries that were not tuned for the old benchmarks. We used k=2 and tnorm=prod for both query types in all benchmarks.
Instead, for the new benchmark ICEWS18+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 concal hidden being True or False, while the rest are the same used for the old benchmarks and do not change across benchmarks. For ICEWS18*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 F.I.
CQD We train ComplEx (Trouillon et al., 2017) 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, F.2 are shown the hyperparameters for CQD on the new benchmark ICEWS18+H.
QTO We re-used the link predictor used in CQD and CQD-Hybrid, and for QTO-specific hyperparameters, we used the same FB15k237.
CQD-Hybrid For CQD-Hybrid, as mentioned above, we re-used the hyperparameters used for CQD. Note that for 4p queries, we fixed the "k" upper bound 64 for memory constraints.
ConE We re-used the same hyperparameters of NELL995 for ICEWS18+H.
CLMPT For CLMPT, we tuned the following hyperparameters: (1) learning rate, with values in [le-5,5e-2,5e-3.5e-4 5,,5e-6), (2) temp, with values in 10.1, 0.2] We found the best hyperparameters match the same found for FB15k237. Hence, re-used them for ICEWS18+H.
G. Statistics
G.I. KG splits statistics
The statistics, i.e., number of entities, relation names, trrining/validatioonees links, of the knowledge graphs used in this paper are shown Table G.I.
Table G.I. Statistics knowledge graphs used generate complex queries
Dataset
Entities
Relation Names
Training Links
Validation Links
Test Links
Total Links
FB15k237
14,505
237
272,115
17,526
20,438
310,079
NELL995
63,361
200
114,213
14,324
14,267
142,804
ICEWS18+CQ (new)
20.840
250
213,304
25,048
24.689
263.041
The KG splits of NELL995 and FB15k237 are the same of the one used (Ren & Leskovee, 2020; Ren et al., 2020).
29

---

Is Complex Query Answering Really Complex?
G.2. New benchmark statistics
G.2.1. NELL995+H AND FB15K237+H
Training queries were not changed from the one proposed by Ren & Leskovec (2020); Ren al. (2020).
Validation and Test queries are generated to ensure a balanced distribution of hardness across the sub-query types to which given query can be reduced. As described in Sec. 6, we generate queries such that each sub-query type contains exactly 10,000 QA pairs, along with additional 10,000 pairs corresponding to full-inference queries (i.e., non-reducible cases). To achieve this, we adapt the algorithm from (Ren et al., 2020), sampling queries until the required number of QA pairs for each sub-query type is reached. For instance, for 2p queries, we continue sampling until we obtain 10,000 QA pairs reducible to Ip and 10,000 full-inference queries. When a query sampled, all its corresponding answers are included in the benchmark until the target 10,000 QA pairs per subtype is met. incorporating answers would exceed this limit, a random subset selected to ensure exactly 10,000 pairs. Similarly, once a sub-query type reaches the 10.000-pair threshold, any additional answers belonging to that category are discarded.
Only exceptions are 1p, 2in, and 2nulp, which being already of full-inference type we kept the same in (Ren & Leskovec, 2020; Ren et al., 2020).
G.2.2. ICEWS18+H
Training queries
were generated using the same strategy used in (Ren & Leskovee, 2020; Ren et al., 2020). namely by (1) creating 1p queries by considering every triple the training set, (2) retrieve the number of generated 1p queries, (3) generate queries for all training query types.
Validation and test queries were generated using the same strategy detailed in App. G.2.1. Moreover, since we generated this benchmark from scratch, also had to generate 1p (which following (Ren & Leskovee, 2020; Ren al., 2020), were generated for each triple in the validation and test split), and 2in, 2nulp queries.
30


Reviews:
[{"review_id": "lQlSMdJWkx", "reviewer": "Reviewer_jsKW", "summary": "This paper critically examines the validity of current benchmarks for complex query answering (CQA) on knowledge graphs (KGs). The authors argue that existing benchmarks (e.g., FB15k237, NELL995) overrepresent \"easy\" queries that reduce to simpler tasks like link prediction (1p), distorting perceived progress in CQA. They demonstrate that up to 98% of test queries in these benchmarks can be answered by predicting only one missing link, even for ostensibly complex query types (e.g., 2i1p). To address this, the authors propose new benchmarks (FB15k237+H, NELL995+H, ICEWS18+H) that balance query difficulty by ensuring answers require reasoning over multiple missing links. Experiments show state-of-the-art (SoTA) CQA methods perform significantly worse on these harder queries, revealing their reliance on memorizing training data. The paper introduces a hybrid solver (CQD-Hybrid) combining neural link prediction with graph traversal and highlights the need for benchmarks that better reflect real-world KG incompleteness.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for providing a precise summary of the paper and for considering our analysis rigorous. We proceed by answering their questions, believing all can be easily addressed.\n\n> no discussion of whether the new distributions reflect real-world query patterns (e.g., frequency of 4p/4i queries)\n\nThere is no ground truth to compare the frequency of query patterns in the new benchmarks ***nor in the old benchmarks*** to reflect a particular real-world application. We highlight that there is no indication that the overrepresented frequency of 1p reductions (see Table 1)  in the old benchmarks is representative, and it skews the perception of progress. \n\n\n> Limited comparison to other hybrid methods (e.g., FIT)\n\nAs we argue in Section 5 (lines 323-325, left column), and as stated in the FIT paper (Appendix G.2 and Table 5 of FIT), the FIT method works like QTO on the query types that we consider in our evaluations. Therefore, we do not include an evaluation of FIT. \n> BetaE not discussed in negation analysis.\n\nWe chose a baseline method for each relevant SoTA category. Concerning geometric embeddings (e.g., BetaE, Query2Box, ConE), we selected ConE as an established baseline that can handle negation, and it was shown to outperform BetaE.\n\n> no explicit theoretical claims. The reasoning tree formalism (Sec. 3) is intuitive but lacks formal proofs\n\nIn Sec 3, we introduce the concept of “reasoning tree” in the running text to syntactically delineate trivial, inference-based, partial-inference and full-inference QA pairs. We do not make formal claims in Section 3 that could be proven. In line 210, we should rather say “We hypothesize…” (rather than “We claim…”), and this hypothesis is later empirically validated, but we do not see any way how it could be proven formally since the hardness that we refer to is the effectiveness of making correct predictions (and not a soundness or algorithmic complexity statement).\n\n\n> Missing statistical significance tests for performance differences\n\nBy running a Mann-Whitney paired U test, we obtain low p-values in the reciprocal rank distribution of answers between models, confirming that our claims remain unchanged from those reported in our tables. For example, when executing the test for the reciprocal ranks of 2p QA pairs computed with CQD and CQD-hybrid we obtain p-value of 1.5e-4. We will include the full results in the camera-ready.\n> Removing non-existing links (Table 3) is valid but lacks details on filtering criteria\n\nWe filter out all query-answer pairs that contain non-existing links in their reasoning tree. For example, for 2u QA pairs, if either one of the two links in the reasoning tree does not exist in the graph, we remove the QA pair. (see Figure A.1 (Bottom) for an example). It follows that only QA pairs where both links in the reasoning tree exist in the graph are retained (see Figure A.1 (Top) for an example). We will include this description in the camera-ready.\n\n> The negation analysis (Table A.1) strengthens the main claims but lacks visual examples.\n\nThe visual example would be similar to the example we provided in Figure 1, and that’s the reason we did not include one. Is there a specific reason why the reviewer thinks there should be one? We can effortlessly add one in the camera ready.", "claims_and_evidence": "1. Current CQA benchmarks are skewed toward easy queries reducible to link prediction.  Systematic analysis of FB15k237/NELL995 shows 86.8–98.3% of complex queries (e.g., 2i1p) reduce to 1p (Table 1).  \n\n2. SOTA methods overperform due to memorization of training links. Performance drops sharply on full-inference queries (Table 2). Hybrid solvers (CQD-Hybrid, QTO) outperform neural models by leveraging training links.\n\n3. Union queries (2u, 2u1p) are artificially hard due to non-existing links. Filtering non-existing links improves MRR (Table 3).", "methods_and_evaluation_criteria": "- **Proposed Benchmarks**: FB15k237+H, NELL995+H balance query types and ensure full-inference answers. ICEWS18+H uses temporal splits for realism.  Addresses distribution bias in prior benchmarks. Temporal splits better mimic real-world KG updates.  But no discussion of whether the new distributions reflect real-world query patterns (e.g., frequency of 4p/4i queries).  \n\n- **CQD-Hybrid**: Combines neural link prediction with graph traversal.  Demonstrates hybrid methods’ superiority (Table A.3).  Limited comparison to other hybrid methods (e.g., FIT).", "theoretical_claims": "The paper makes no explicit theoretical claims. The reasoning tree formalism (Sec. 3) is intuitive but lacks formal proofs.", "experimental_designs_or_analyses": "1. Re-evaluating SoTA models on reduced query types (Tables 2, A.5–A.6) is rigorous.\n2. Missing statistical significance tests for performance differences. \n3. Removing non-existing links (Table 3) is valid but lacks details on filtering criteria.", "relation_to_broader_scientific_literature": "- Builds on prior CQA frameworks (Hamilton et al., 2018; Ren et al., 2020) and neural models (Arakelyan et al., 2021; Zhu et al., 2022).  \n- Extends critique of benchmark validity similar to issues in link prediction (Kadlec et al., 2017).  \n- Hybrid solvers (CQD-Hybrid, QTO) align with recent trends in neuro-symbolic reasoning (Bai et al., 2023; Yin et al., 2024).", "essential_references_not_discussed": "- **FIT** (Yin et al., 2024): A concurrent hybrid solver with score calibration, which could contextualize CQD-Hybrid’s performance.  \n- **BetaE** (Ren & Leskovec, 2020): A model handling negation, not discussed in negation analysis.", "other_strengths_and_weaknesses": "N/A", "other_comments_or_suggestions": "N/A", "questions_for_authors": "Suggestion: Include error bars in Tables 2/A.5–A.6.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "qX5lU0UTdc", "reviewer": "Reviewer_GxN2", "summary": "This paper investigates the problems in current benchmarks for complex query answering over knowledge graphs. The main points are: 1. Previous benchmarks failed to effectively evaluate the capabilities of CQA methods because most test queries can be reduced to simpler queries, 2. Using the proposed benchmark that alleviates this problem, there is no method that can claim SOTA with a clear advantage.\n\n## update after rebuttal\n\nThe rebuttal solves some of my main concerns. I have adjusted my evaluation accordingly.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We believe the main concerns of the reviewer can be fully addressed, as discussed in the comments below. We hope the score can be raised.\n\n\n>The authors “balance each query type a QA pair can be reduced to”, which is confusing to me, \n\nWe acknowledge that the usage of the term ''balance'' can lead to misunderstandings. We should rather say, ``We compile the benchmark such that all query types (e.g., 3p) a QA pair can be reduced to (e.g., 1p, 2p, and 3p) appear with the same frequency in it’’. We will clarify this in the camera-ready.\n\n>why is this a necessary choice? And how the balancing coefficient would affect the final results?\n\nThis is necessary because sub-types reductions in the old benchmark are not equally represented, while 1p reductions are greatly over-represented (see Table 1). As you can see in Fig. 3, by compiling the benchmark such that all query types a QA pair can be reduced to appear with the same frequency in the benchmark, the overall results significantly decrease. An explanation for this phenomenon is that in the new benchmarks, we evaluate the full spectrum of hardness rather than the easiest QA pairs (i.e., the ones reducible to 1p).\n\n> from well-established methods like Query2Box and BetaE and more recent strong baselines like LMPNN and CLMPT. \n\nOver the last years dozens of methods for CQA have been released, and it’s highly impractical to evaluate and compare all of them. For such a reason, we have selected a method for each category. For geometric embedding methods, we selected ConE, as it is an established baseline that can handle negation and has outperformed, e.g., BetaE, and Query2Box. For methods based on GNN, we chose GNN-QE, as it provides competitive performance compared to LMPNN and CLMPT on NELL995, but outperforms them on FB15k-237. That said, we also ran additional experiments on the new benchmarks with CLMPT, being the most recent baseline among the three, and our preliminary results confirm that our claims remain unchanged. \nIn fact, similarly to the other baselines, CLMPT's performance drops on the new benchmark, but it remains competitive. For instance, below is the MRR comparison of CLMPT and the best-reported baseline for 2p, 3p, 2i, and 3i queries on FB15k-237+H:\n\n| Method        | 2p   | 3p   | 2i   | 3i |\n|--------------|------|------|------|------|\n| CLMPT        | **5.3** | **4.7** | 10.2 | 12.2|\n| best-baseline | 5.2  | 4.0  | **11.3**  | **12.8**|\n\nWe will report the full results in the camera-ready.\n\n> This work can benefit from discussing more related works\n\nWe will extend App. C to include the methods pointed out by the reviewer in the SoTA discussion.\n\n\n>It would be great if the results of queries with negation can be included in the main content. Specific reason to exclude the results and discussions on negation queries in the main content?\n\nWe agree with the reviewer, we will use the additional page in the camera-ready to include results on negative queries in the main paper. We did not do it now just for space constraints.\n\n>A lot of CQA methods use the data splits in the BetaE data, where the training data may also have the same query reduction problem.\n\nPlease note that we have not changed the data splits, rather we have changed the way the benchmark is created (see Sec 6, and App G). \nAlso note that the query reduction problem can only occur at valid/test time, as it happens when certain ***training data*** makes the prediction of a QA pair easier, effectively *reducing* the QA pair to a simpler type (see Fig. 1).\n\n> Is the new benchmark really harder and more suitable for evaluating CQA methods, or is it out of the training data distribution and thus not that convincing to be used for evaluation?\n\nWe remark that we only change the way the benchmark is created to ensure that the distribution is not skewed towards the easiest QA pairs. Moreover, apart from 4p and 4i queries, ***we keep the same query structures used in the old benchmarks***. Then, following [1], we could consider the query types not included in the training, i.e,  ip,pi,2u,up, as well as 4p and 4i to be OOD, while considering the rest of the query types in-distribution. We also remark that there is no ground truth to compare the frequency of query patterns in the new benchmarks ***nor in the old benchmarks*** to reflect a particular real-world application. We highlight that there is no indication that the overrepresented frequency of 1p reductions (see Table 1) in the old benchmarks is representative and it skews the perception of progress. \n\n[1] 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.", "claims_and_evidence": "Please refer to the “Experimental Designs Or Analyses” section because these are mainly related to experiments", "methods_and_evaluation_criteria": "The authors “balance each query type a QA pair can be reduced to”, which is confusing to me, why is this a necessary choice? And how the balancing coefficient would affect the final results?", "theoretical_claims": "N/A", "experimental_designs_or_analyses": "The authors claim that no method can claim SOTA with a clear advantage using the proposed benchmark. However, a lot of important baselines are not included, from well-established methods like Query2Box and BetaE and more recent strong baselines like LMPNN and CLMPT (and more). It’s crucial to report the performance of important methods on a new benchmark, instead of only choosing a few among others.", "relation_to_broader_scientific_literature": "To my best knowledge, this work focuses on CQA over KGs and does not explicitly relate to the broader scientific literature/community.", "essential_references_not_discussed": "This work can benefit from discussing more related works, especially more recent works, including but not limited to:\n- https://arxiv.org/abs/2301.08859\n- https://dl.acm.org/doi/abs/10.1145/3589334.3645569\n- https://dl.acm.org/doi/abs/10.1145/3637528.3671869", "other_strengths_and_weaknesses": "It would be great if the results of queries with negation can be included in the main content", "other_comments_or_suggestions": "Section 6, numbers under subsection “Building new CQA benchmarks” should be 10,000 instead of 10.000.", "questions_for_authors": "- Is there a specific reason to exclude the results and discussions on negation queries in the main content? It’s quite important because most recent CQA methods can deal with negations and use queries with negations for evaluation. \n- A lot of CQA methods use the data splits in the BetaE data, where the training data may also have the same query reduction problem. Is the new benchmark really harder and more suitable for evaluating CQA methods, or is it out of the training data distribution and thus not that convincing to be used for evaluation?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "eQ6SWuRAkN", "reviewer": "Reviewer_gKE1", "summary": "Authors carefully analysed limitations of benchmark datasets used in current SOTA neural KG queries, showing that they reflect only the performance of predicting answers where only one link is truly missing and that FB15k237 and NELL995 are not suitable to precisely assess performances of QA systems. Authors proposed a new benchmark dataset and tested main SOTA QA systems, showing performances of all these systems dropped significantly.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for considering our paper a piece of beautiful work and considering our experiment design easy to understand.  We proceed by answering their questions.\n\n> authors do not explain at methodological level why these SOTA CQA systems fail for complex queries.\n\nIn Table 2 we showed that the performance of all SoTA methods consistently increased for QA pairs that have a higher number of existing links in their reasoning tree. This is evidence that most ''good'' performance of CQA can be explained by their memorization ability. We conclude that all methods lose performance in the new benchmarks because they overly rely on memorized facts, limiting their ability to predict answers when there are many missing links in their reasoning tree. We will add this conclusion explicitly in the camera-ready.\n\n\n>If we make a decision by tossing a coin, we will have 50% of accuracy. But, we do not believe we are doing logical reasoning. Should there be a minimum value of accuracy, below which we shall not call a system is doing logical reasoning (here logical query)?\n\nWe see where the reviewer is leading, but for CQA, even if query answering under missing links is described using logical operators, the results it produces are derived in a mixed deductive-inductive process that returns a ranking of answer entities (measured by MRR) rather than a set of logical conclusions (which are usually meant to be derived by deduction and whose correctness might be measured in terms of accuracy). Additionally, since knowledge graphs contain thousands of entities, a randomly selected ranking would result in an MRR close to zero. Hence, it is less informative to set a hard MRR threshold to determine whether a model can be considered capable of reasoning.", "claims_and_evidence": "Authors' claims are strongly supported by reproducing experiments of existing SOTA systems and by conducting their own experiments with their new datasets.", "methods_and_evaluation_criteria": "Authors very carefully conducted their experiments and analysed existing benchmark datasets.", "theoretical_claims": "Authors clearly listed three takeaways as follows.\n\n1 Not to use current CQA benchmarks as they essentially reflect only the performance of predicting answers where only one link is truly missing (for both hybrid and neural solvers).\n\n2 FB15k237 and NELL995 are not suitable to precisely assess the capability of CQA methods to answer complex queries, as most of their QA pairs can be predicted by just predicting a single missing links. This results in highly inflated performance that distorts the perception of progress in the field and pushes the community to improve the performance only on the easiest QA pairs.\n\n3. New benchmarks have a balanced amount of partial-inference and full-inference QA pairs that depends on the query type, allowing to measure CQA performance while not distorting the aggregate performance across all QA pairs with different hardness. Additionally, ICEWS18+H highlights that more realistic sampling strategies are more challenging for current SoTA.", "experimental_designs_or_analyses": "The experiment design is quite straight forward and easy to understand.", "relation_to_broader_scientific_literature": "The key contributions of this paper are related to the broader scientific literature.", "essential_references_not_discussed": "At my knowledge, authors discussed major SOTA papers in the field.", "other_strengths_and_weaknesses": "A piece of beautiful work! \nWeakness: authors do not explain at methodological level why these SOTA CQA systems fail for complex queries.", "other_comments_or_suggestions": "no further comment.", "questions_for_authors": "If we make a decision by tossing a coin, we will have 50% of accuracy. But, we do not believe we are doing logical reasoning. Should there be a minimum value of accuracy, below which we shall not call a system is doing logical reasoning (here logical query)?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: I thank the authors for their submission and the reviewers for their assessment. This is an important paper, demonstrating that SotA complex Q&A method's performance is overestimated due to memorizing training links. The authors address this by creating new balanced benchmark datasets. All reviewers unanimously agree that it meets the bar for publication at ICML.
Decision: Accept (spotlight poster)