Counting Still Counts: Understanding Neural Complex Query Answering Through Query Relaxation
Authors: Yannick Brunink
Daniel Daza
Yunjie He
Michael Cochez
Venue: Accepted by TMLR ()

Abstract: Neural methods for Complex Query Answering (CQA) over knowledge graphs (KGs) are widely believed to learn patterns that generalize beyond explicit graph structure, allowing them to infer answers that are unreachable through symbolic query processing.
In this work, we critically examine this assumption through a systematic analysis comparing neural CQA models with an alternative, training-free query relaxation strategy that retrieves possible answers by relaxing query constraints and counting resulting paths. Across multiple datasets and query structures, we find several cases where neural and relaxation-based approaches perform similarly, with no neural model consistently outperforming the latter. Moreover, a similarity analysis reveals that their retrieved answers exhibit little overlap, and that combining their outputs consistently improves performance.
These results call for a re-evaluation of progress in neural query answering: despite their complexity, current models fail to subsume the reasoning patterns captured by query relaxation. Our findings highlight the importance of stronger non-neural baselines and suggest that future neural approaches could benefit from incorporating principles of query relaxation.

Published in Transactions on Machine Learning Research (03/2026)
Counting Still Counts: Understanding Neural
Complex Query Answering Through Query Relaxation
Yannick Brunink*
y. bruninkk@u..
Vrije Universiteit Amsterdam
Daniel Daza
ddddeacereaamsterdmmmmm.c
Translational AI Laboratory, Department of Laboratory Medicine Amsterdam University Medical Center, Vrije Universiteit Amsterdam Vrije Universiteit Amsterdam
Yunjie He University of Stuttgart
Michael Cochez
michael, conchaal.occhhe@uub..
ELLIS Institute Finland Abo Akademi University, Turku, Finland Elsevier discovery lab, Amsterdam
Reviewed OpenReview: https: // openreview. net/ per/ff id= YVPaB6bkeC
Abstract
Neural methods for Complex Query Answering (CQA) over knowledge graphs (KGs) are widely believed to learn palterns that generalize beyond explicit graph structure, allowing them to infer answers that are unreachable through symbolic query processing, In this work, we critically examine this assumption through a systematic analysis comparing neural CQA models with an alternative, training-free query relaxation strategy that retrieves possible answers by relaxing query constraints and counting resulting paths. Across multiple datasets and query structures, we find several cases where neural and relaxation- approaches perform similarly, with no neural model consistently outperforming the latter. Moreover, a similarity analysis reveals that their retrieved answers exhibit little overlap, and that combining their outputs consistently improves performance. These results call for a re- evaluation progress in neural query answering: despite their complexity, current models fail to subsume the reasoning patterns captured by query relaxation. Our findings highlight the importance of stronger non-neural baselines and suggest that future neural approaches could benefit from incorporating principles of query relaxation.
1 Introduction
Knowledge graphs (KGs) encode information as entities and relations, enabling structured reasoning and efficient answering of complex queries. Traditional query answering approaches rely on symbolic processing and rulc-based inference to derive answers that follow directly from the graph's explicit structure (Hogan et al., 2021). Yet, because real-world KGs are often incomplete, recent research has turned to neural methods that aim to infer likely answers beyond the observed edges (Nickel et al., 2016; Zhong et al., 2023).
In Complex Query Answering (CQA), these methods learn emboddings for entitics and relations and apply neural operators to process queries in a contimuous space (Ren and Leskovec, 2020; Arakelyan et al., 2021: Zhang et al., 2021; Galkin al., 2024). The prevailing assumption is that such models can extract and combine patterns from the training graph to recover answers that are unreachable by explicit traversal
FEqual contribution.

---

Published in Transactions on Machine Learning Research (03/2026)
alone. However, the central claim that neural reasoning truly extends the reach of symbolic reasoning has rarely been tested.
In this paper, we investigate this question directly. We compare a range of state-of-the-art neural CQA methods with a simple, training- free query relaxation strategy that broadens the constraints of a query to retrieve additional, plausible answers. This comparison allows us to test. whether neural models capture information beyond what can be obtained by relaxing queries over the observed graph.
We conduct an extensive empirical study across several datasets designed to include challenging query types requiring predictions over one or more missing edges (Gregucci et al., 2025). We compare multiple state-of- the-art neural methods for CQA with a training- free query relaxation strategy. Our analysis of the results leads to three main findings: (1) Unclear superiority. Neural methods do not consistently outperform query relaxation strategies across datasets and query types. Although neural approaches often achieve higher performance on more complex queries, there is no single method that clearly dominates relaxation across all settings, and in several cases relaxation performs competitively or better despite involving no learning or optimization. (2) Low answer overlap. The top-ranked answers from neural and query relaxation approaches diverge substantially, indicating that they capture different patterns in the graph. (3) Complementarity. Combining their answer sets consistently improves performance, suggesting that both contribute distinct and complementary reasoning signals.
These findings challenge a fundamental assumption behind current neural CQA research: that learned representations necessarily generalize beyond symbolic reasoning. Instead, they show that simple, non- parametric query relaxation recovers a complementary set of answers that neural models often miss. This calls for re-cxamination of how progress in CQA is assessed, emphasizing the need for stronger non-neural baselines and the potential of hybrid approaches that integrate symbolic relaxation mechanisms into future neural architectures,
2 Related Work
Complex Query Answering. Until recently, a large body of work on estimating missing information in KGs had been limited to the link prediction setting where a single relation between two entities is predicted by either learning embeddings of entities and relations, and a scoring function to compute the likelihood of a triple in graph (Nickel et al., 2016; Wang et al., 2017; Zhong et al., 2023). Link prediction can be seen as an instance of simple queries, which later works extended to complez queries involving multi-hop prediction and variables. Methods for approximate answering of complex queries can be categorized into encoder models that encode a query into an embedding and compute an answer via similarity search (Hamilton et al., 2018a; Daza. and Cochez, 2020; Chen et al., 2022; Choudhary et al., 2021; Zhang et al., 2021; Alivanistos et al., 2022; Ren et al., 2020a); and methods that traverse a computation graph following the structure of a query and produce a vector of scores for all entities in the graph (Arakelyan et al., 2021; 2023; Zhu el al., 2022; Bai et al., 2023). See (Ren et al., 2024) for a survey on different methods.
The benchmarks employed in the literature of CQA are extracted from KGs such Freebase (Bollacker et al., 2008) and NELL (Carlson et al., 2010). They contain query-answer pairs where answers in the test set cannot be obtained by direct graph traversal. In a recent analysis of these benchmarks, Gregueci et al. (2025) conclude that they are largely dominated by partial inference queries, which only require predicting one missing edge in the training graph. They propose to distinguish these from full inference queries that require predicting all edges missing for a given query, and they demonstrate that in this setting, the performance of state-of-the-rtt methods for approximate query answering degrades by a large margin. Our work extends these results by further examining how the performance of these methods compares with respect to query relaxation methods that to not rely on training procedures. This provides valuable insights into how neural methods perform and how they can be improved with respect to simple hcuristics.
Statistics for predictions in KGs. Previous works have proposed methods for learning rules over a KG that can be used to infer additional statements. These methods are based on enumerating subgraphs and extracting rules from them that have good coverage over the graph (Galárraga et al., 2013; Meilicke et al., 2019; Wang et al., 2024). More recently, Le et al. (2024) show that statistical features extracted from the KG
2

---

Published in Transactions on Machine Learning Research (03/2026)
can be useful learning signals for the link prediction problem. These works provide evidence that traversing graph and collecting statistics from it can already result in useful patterns for prediction problems on KG, which motivates our analysis of performance of neural methods for the CQA case in comparison with query relaxation strategies that can be applied to the problem.
Query relaxation and path heuristics. Our work is motivated by prior work on query relaration in KGs. Query relaxation aims to retrieve results even when some conditions cannot be exactly met due to missing facts (Fakih and Serrano-Alvarado, 2024). Several approaches for relaxing a query exist, such as replacing constants with variables, which allow returning answers with varying degrees of exactness and ranking them by how closely they meet the original query (Hurtado et al., 2008). Other approaches are based similarity- based relaxations, using language model to replace entities in the query with similar ones based on the context (Mai et al., 2019); answering the query by averaging graph embeddings directly in the embedded space (Wang et al., 2018); or identifying which conditions cause empty results and incrementally broadening or dropping such constraints (Fokou et al., 2015).
Another line of related work relics on graph paths as signals for link prediction in KGs. The Path Ranking Algorithm (Lao and Cohen, 2010; Lao et al., 2011), for example, performs random walks guided by relation sequences and counts how often node can be reached via those paths. In similar vein, heuristics like Katz inder (Katz, 1953) and PageRank (Page et al., 1999) which rely existing paths in the graph can be useful for link prediction tasks (Zhang and Chen, 2018; Iyer et al., 2023).
Even though these relaxation and path-based approaches can, in principle, be applied to complex query answering, to the best of our knowledge no prior work has systematically examined whether neural methods recover the same answers, or whether they truly surpass what can be achieved by query relaxation over the graph.
3 Preliminaries
KGs. We represent a KG as a tuple G = EV,E, R), where V denotes the set of entitics, R is the set of relations, and & consists edges structured as triples (h, r, (). Here, h, E V are the head and tail entities, respectively, while r R represents the relation connecting them. Each triple r, t) in the KG corresponds to factual statement in first-order logic, which we express th, where r R is binary predicate with h and as its arguments.
First-order logic queries. A query q over 9 specifies set of constraints that entity must fulfill to qualify as valid answer. Entities in V that meet the constraints form the answer set Ag- We consider conjunctive queries (CQs) whose constraints can be written using first order logic in disjunctive normal form. Formally, the answer set for query is the following set:
Ag = (vx Eei..................... UN E V: (cl A..... A A V V (c) ... A Cm.) }}:
Here, 01,.--, UN existentially quantified variables, and e is the target variable. The constraints of define relationships between two variables or between variable and known entity (i. constant) in E, that is, cf = r(ee or oj r(v(,)) v) where E E, u, v' E {vr, (I..,,...., un}. and r E R.
Example
Consider the query "What is the location of the baseball tcam for which Aaron Judge plays?". This query can be expressed as:
Ag = {vz Bug V (lays_foo(Aarz Judge, v1) location(VI, v.)
(2)
This corresponds to a 2p query (query types are illustrated in Fig. 1), where the leaf node corresponds to the constant Aaron Judge, and the root node corresponds to the target variable et representing a location.
3

---

Published in Transactions on Machine Learning Research (03/2026)
Anchor
Intermaditte varieble
Target
3i Ip
Figure 1: Query graphs for different types of conjunctive queries and their shorthand notation.
Prior work on CQA has focused on a specific subset of queries that can be associated with a query graph: a directed acyclic graph where leaf nodes (also known as anchor nodes) constants in the query, intermediate nodes are existentially quantified variables, and the root node corresponds to the target variable. We illustrate query graphs for different types of queries in Fig. 1.
The answers to a query can be obtained by finding subgraphs of the KG that match the query graph. Tn the case where the graph is incomplete, several methods have been proposed for cstimating likely answers, by training query answering models with query-answer pairs. An alternative, which to the best of our knowledge has not been explored before for the problem of CQA, to use query relaxation strategies Fakih and Perrao-AAvarade (2024), which also allow estimating which entities are likely to be answers.
4 CQA via Query Relaxation
Query relaxation methods are designed to recover answers when an exact match yields few or no results due to KG incompleteness (Fakih and Serrano-Alvaradee 2024). The core idea to iteratively relax parts of the query, such as replacing constant entity with a variable, and then to score each entity with the counts of paths arriving to it according to the relaxed query. These relaxed matches often originate from structurally or sealntically related subgraphs that would otherwise remain unreachable.
When one relaxation step is applied to a query, it is possible that multiple entities receive the same count; in this case, we say that these entities are tied. In our analysis, we employ a symbolic relaxation strategy that progressively relaxes a query, breaking ties in the ranking at each stage. Starting from the original query, the algorithm iteratively considers coarser relaxed forms of the query, broadening the search space while preserving its overall structure. Relaxation proceeds hierarchically: more specific matches are preferred, and further relaxation is only applied when ties occur among candidate entities. This ensures that the most constrained matches prioritized while still providing a systematic fallback when exact matches are unaaiilable
Formally, given a query 4, the goal is to assign a score to each entity in E according to how well it satisfies the (possibly relaxed) query. The algorithm traverses the query graph from the leaves (constants) to the root (target variable) as follows:
1. Replace the constants at the leaves with variables, count how many paths in the KG match the relaxed query that reach each entity, and assign that count as the score.
When entities receive the same score (tie groups), apply a coarser relaxation to the tied portion of the query, dropping previously fixed constraints and counting matches under the simpler relaxed pattern within the tied group.
3. Residual ties are resolved by ranking entities based on their in-degree in the KG.
We present a more extensive description the algorithm in Appendix A.1, and an example in Example 2. Among the many possible implementations of query relaxation, we adopt this stratogy because it implements fundamental capability that neural methods for query answering are expected to capture: the ability exploit structural regularities and multi-hop connectivity in the graph to infer plausible answers beyond
4

---

Published in Transactions on Machine Learning Research (03/2026)
Example 2
Initialize: We consider a 2p conjunctive query:
Aaron Judge
PlaysBaxeBalForr Ptr Looutedte, T?
The following triples are true but missing:
(Aaron Judge, FoallfaseBallForr Yankees)
(Yankees, LocatedIn, USA)
Step Anchor Relaxation. Replace Aaron Judge" with a variable and count matching paths:
Pa1 BuattBaseBBllfor
P01 Locatedin T?
Ranking groups: (1) USA, Canada (5 paths), (ii) Mexico (3 paths), (ii) France, Spain (1 path).
USA Canada > Mexico > France Spain
Step Orelicate-Only Relaxation (If Ties Exist). Step still produces ties, we break them using a coarser relaxation that keeps only the final predicate:
Pmn Locatedie
T?
Counts (paths): USA (100), Canada (80), France (50), Spain (50). Updated Ranking:
USA Canada Mexico > France Spain
Step 3: Maximum Relaxation (If Ties Persist). Break the remaining ties using the in-degree of the tied entities:
Poj 23 T?
France (500), Spain (450). Final ranking:
USA > Canada Mexico > France > Spain
direct traversal. This approach thus provides clear, interpretable baseline for testing whether learned models offer gemuine advantages over training-free reasoning based solely on graph topology. Moreover, it is computationally efficient in practice, allowing systematic comparison across large datascts and query types (we present time complexity results and runtimes Appendix B).
5
Experiments
5.1 Methodology
Datasets. Earlier work has evaluated models on query answering benchmarks such FB15k237 (Toutanova and Chen, 2015) and NELL995 (Xiong al., 2017), introduced by Hamilton et al. (2018b), and refined by Ren and Leskovee (2020). Although these benchmarks were designed to include queries of varying structures, later analysis showed that most of their queries effectively reduce to one-hop link prediction, since answers can often be obtained by memorizing edges already present in the training graph (Gregucci et. al., 2025). To overcome this limitation, we adopt the datasets introduced by Gregucci et al. (2025), which provide more balanced query sets that require predicting over one to three odges. These include FB15k237+H and NEL.L995+H, derived from the carlier datasets, well ICEWS18+H, where queries are temporally split so that test queries involve predicting future edges from past graph states.
5

---

Published in Transactions on Machine Learning Research (03/2026)
Evaluation metrics. We report performance in query answering using Mean Reciprocal Rank (MRR). Given a query and a ranking of entities provided by a method, MRR is computed by taking the inverse of the ranking for a correct answer, and then averaging over all queries in the test set. We compute filtered MRR (Bordes et al., 2013), where for each answer the ranking is adjusted to ignore other correct answers that might be ranked higher.
Query relaxation. For experiments involving the query relaxation strategies described in Section 4, we load the training and validation edges in a graph database', which we use to answer the relaxed queries. While in principle we can compute a relaxation for every constant entity and predicate in the query, for some queries such as path queries of length three (shown as 3p in Figure 1), in practice we limit this to up to two predicates to preserve memory, which we observe to work well in practice. We refer this method in our experimental results as RELAX. We run our experiments machine with AMD EPYC-2 CPU with 128GB of RAM.
Baselines We run an extensive comparative analysis with several ttate-of-the-art neuro-symbolic CQA methods: GNN-QE (Zhu et al., 2022), ULTRAQ (Galkin et al., 2024), CQD (Arakelyan et al., 2021), ConE (Zhang et al., 2021), and QTO (Bai et al., 2023).
5.2 Query answering performance
Prior work on CQA has been motivated by the idea that learning-bssd neural methods can eapolaa beyond the information explicitly stated in the graph. Our experiments are designed to test whether existing methods indeed achieve this goal, by comparing them with what can be achieved with query relaxation strategies that rely only on edges existing in the graph to score answers to a query. We thus begin our study by investigating the following research question:
RQ1: Do neural methods consistently outperform a query relaxation strategy in the task of CQA over incomplete knowledge graphs?
We present results on query answering performance in Table 1, where denote query relaxation results RELAX. We identify several cases where RELAX performs better comparably with neural methods. While some neural models do outperform RELAX in cerlain cases, this advantage is neither consistent nor predictable across datasets, For instance, ConE outperforms RELAX on the FB115237+H dataset, but achieves similar results on 3p queries in NELL995+H, and underperforms across 1p, 2p, and 3p querics in ICEWS18+H.
We additionally observe a pattern related to the length of path queries. For 2p queries, three neural methods (GNN-QE, ULTRAQ, and ConE) perform worse than RELAX in the ICEWS18+ dataset. For 3p queries, which have an additional edge in the path, the same methods perform worse close in the three methods, with CQD additionally performing worse in NELL995 H. These findings indicate that the gap in performance between neural methods and RELAX increases with query length, as neural methods compute predictions whose errors can propagate with length.
These findings carry particular weight given the computational overhead of neural models. They require extensive training, hyperparameter tuning, and optimization, whereas query relaxation strategies do not depend on iteralive optimization and are dalaset-agnostic. The narrow performance gap, and in some cases the better results obtained via relaxation, raises critical questions about the added value of current neural approaches and the computations that they might be performing. The results suggest two plausible interpretations: (i) neural models may in practice be reducing lo simple statistical patterns akin to those exploited by query relaxation; or (ii) they may be retrieving fundamentally different answers.
We GraphDB as our graph database.
2 All our code available

---

Published in Transactions on Machine Learning Research (03/2026)
Table 1: Query answering results (MRR in %). Orange indicates worse or equal performance than query
relaxation strategies (RELAX), lighter orange indicates a delta of less with RELAX.
Model
1p
2p
3p
2i
3i
pi
ip
GNN-QE
42.8
5.2
4.0
6.0
8.8
5.6
9.9
1215523777
ULTRAQ
40.6
4.5
3.5
5.2
7.2
5.3
10.1
CQD
46.7
4.4
2.4
11.3
12.8
6.0
11.5
ConE
41.8
4.6
3.9
9.1
10.3
3.8
7.9
QTO
46.7
4.9
3.7
8.7
10.1
6.1
13.5
RELAX
31.5
4.0
3.9
5.2
5.2
1.8
5.3
GNN-QE
53.6
8.0
6.0
10.7
13.3
16.0
13.5
HT9661TIN
ULTRAQ
38.9
6.1
4.1
7.9
10.2
15.8
9.3
CQD
60.4
9.6
4.2
18.5
19.6
18.9
22.6
ConE
53.1
7.9
6.7
21.8
23.6
14.9
11.8
QTO
60.3
9.8
8.0
14.6
15.8
17.6
21.1
RELAX
35.1
5.6
5.2
12.4
12.1
3.9
6.5
GNN-QE
12.2
0.9
0.5
16.1
26.5
19.1
3.5
TGMMSSTHH
ULTRAQ
6.3
1.2
1.2
7.0
11.7
8.8
1.3
CQD
16.6
2.5
1.5
13.0
19.5
17.1
6.7
ConE
3.5
0.9
0.9
1.2
0.5
1.2
1.6
QTO
16.6
2.6
1.4
15.7
25
18.4
6.2
RELAX
6.1
1.6
1.3
1.6
1.0
1.6
1.6
Answer to RQI: Neural methods do not consistently outperform a query relaxation strategy in the task CQA over incomplete knowledge graphs. In several cases, their performance comparable or inferior. This raises the possibility that these models either collapse to count-based reasoning complex settings, alternatively, retrieve different class of answers altogether.
5.3 Overlap Analysis
The observed comparable performance between neural models and query relaxation leads to an important question: these methods arriving at the same answers, do they achieve similar performance through fundamentally different predictions? Addressing this question is crucial to understanding whether neural models and symbolic approaches as the ones we investigate are truly interchangeable in this set setting, if they offer complementary capabilities. We investigate this issue in the following research question:
RQ2: Is the observed similar performance between neural mothods and query relaxation due them producing the same set of answers for complex queries?
To answer this question, we examine the filtered ranks assigned to all entities by RELAX and three represen- tative neural methods that rely on different mechanisms for query answering: ULTRAQ (Galkin et al., 2024) (which has the ability to answer queries across KGs without requiring additional training), ConE (Zhang et al., 2021) (a method that maps a query inlo a vector and answers queries via similarity search), and QTO (Bai et al., 2023) (a neuro-symbolic method that traverses the query graph with fuzzy operators). Given query and pair of rankings lists produced by RELAX and neural model, collect the set of entities the top for each method. Tet ((k) and ( be such sets for RELAX and a neural model,
respectively, for given value of To measure the overlap among these sets, we compute the Jaccard similarity & which we define
J@k = (A()) 0 (A) [A U (k)
(3)

---

Published in Transactions on Machine Learning Research (03/2026)
ULTRAQ
ConE
QTO
1.0
1.0
1.0
0.8
0.8
0.8
F815K237#
0.6
0.6
0.6
0.2
0.2
0.2
0.0
0.0
0.0
20
40
60
80
100
20
40
60
80
100
0
20
40
60
80
100
1.0
1.0
1.0
0.8
0.8
NELL995+H
0.6
0.6
0.6
0.4
0.4
0.4
0.2
0.2
0.0
0.0
0.0
20
40
80
100
40
60
100
60
80
100
1.0
1.0
1.0
0.8
0.8
0.8
ICEWS18+
0.6
0.6
0.4
0.4
0.4
0.2
0.2
0.2
0.0
0.0
0.0
2p 3p
avg
Figure 2: Jaccard similarity of top-k retrieved answers between RELAX and three neural methods (columms), across different datasets (rows) and query structures (shown in colors in the legend). If the top-k contains the same set of answers, the similarity would reach 1.
According to this definition, a value of J@k 1 indicates that the two methods rank the same entities the top k whereas a value of means that the sets are disjoint.
We present results of J@k for different values of k in Fig. 2. In the FB15k237+HI and NELL995+H datasets, for simple query types such as 1p, RELAX and neural models exhibit moderate to high overlap, approaching from 60% to up to 80% for high values of k. However, query structure complexity increases (e.g., 2i, 3p, pi), overlap declines substantially. For ICEWS18+H, the overlap is much lower (with ULTRAQ showing the lowest. degree of similarity). These results indicate that while neural models and RELAX may achieve similar MRR, they do so by ranking different entities highly. This divergence is especially notable given the simplicity of RELAX, which relies on symbolic path enumeration and counting. That a neural model, despite being far more complex, retrieves distinct of answers suggests that fails to capture certain signals that RELAX exploits, and vice versa..
8

---

Published in Transactions on Machine Learning Research (03/2026)
The similar performance between neural models and query relaxation does not stem from retrieving the same answers. Their top-ranked outputs diverge significantly for complex queries, suggesting that these methods capture complementary patterns.
Answer to RQ2:
5.4 Combining neural and symbolic methods
The divergence in top-ranked answers between neural models and query relaxation, particularly for complex query structures, suggests that these methods might be capturing complementary patterns that useful for the task. We therefore investigate the following rescarch question:
RQ3: Is there an optimal combination of answers computed by neural methods and query relaxation that consistently produces better results than their individual performance in the lask of complex query answering?
To answer this question, we introduce an oracle-based evaluation aimed determining the theoretical optimal combination of RELAX and several neural methods. For cach query, the oracle selects the list of scores from each method that yields the higher MRR for the given query.
We present the results for QTO, query relaxation, and their oracle combination (denoted RELAX+QTO) in Table 2. Statistical significance is assessed using paired t-tests with -ooffBooferroni correction for multiple comparisons, and all differences between RELAX+QTO and the individual methods are significant (p < 0.001). Across datasots and query types, the oracle combination consistently achieves higher MRR, with relative gains in the metric reaching 30 50% for several query types (notably 2p 3p in FB15k237+H and NELL995+H)).
A closer inspection revcals clear patterns in where these gains arisc. On average over the three datascts, the largest improvements occur for path queries (2p, 3p), which require reasoning over longer relational chains. This suggests that query relaxation effectively recovers structural connections that neural models only partially capture or whose learned representations degrade with path length. In contrast, for inter- section queries (denoted as 2i and 3i in Figure 1), the relative improvements are smaller, particularly in ICEWS18+H. This dataset is temporally split and generally more challenging, and both neural and RELAX appear less effective.
When extending the analysis to other neural methods (see Appendix C), we observe similar trends. ConE benefits across all query types but especially on path queries, reinforcing the idea that relaxation complements pash-based reasoning. ULTRAQ, a foundation model capable zero-shot transfer across KGs, shows the strongest relative gains overall, indicating that large, pretrained neural architectures may still overlook local structural regularities that relaxation can recover efficiently.
Overall, these results evidence of systematic complementarity between neural reasoning and query relax- alion. The distinct patlerns across query lypes, datasets, and architectures highlight where current neural models fall short, particularly on path queries and temporally complex graphs, and point to opportunities for integrating relaxation-like mochanisms into future ncural CQA approaches.
Answer RQ3: The optimal combination of neural and query relaxation predictions yields consis- tently and significantly gains across datasets and query types (particularly for path queries), demon- strating that both approaches capture complementary reasoning signals, rather than redundant ones.
6 Discussion
Our analyses aim to understand what current neural methods for complex query answering (CQA) over knowledge graphs actually capture. By comparing them with a training-free query relaxation strategy that exploits the graph structure alone, we evaluate whether neural models compute answers beyond those
9

---

Published in Transactions on Machine Learning Research (03/2026)
Table Query answering results (MRR) comparing the original performance of QTO, RELAX, their optimal combination, denoted RELAX+QTO, and the relative difference percent.
Model
1p
2p
3p
2i
31
pi
ip
FB15k237+H
QTO
46.7
5.3
3.8
8.9
10.6
6.1
13.9
RELAX
31.5
4.0
3.9
5.2
5.2
1.8
5.3
RELAX+QTO
49.0
7.1
5.6
10.9
12.2
6.8
15.7
Abs. A
2.4
1.9
1.7
2.0
1.6
0.7
1.8
Rel. A (%)
5.1
35.1
44.6
22.3
15.6
11.4
12.8
NELL995+H
QTO
60.7
10.0
7.6
15.6
17.0
17.0
21.3
RELAX
35.1
5.6
5.2
12.4
12.1
3.9
6.5
RELAX+QTO
64.9
12.7
9.9
23.6
23.7
18.1
23.5
Abs. A
4.2
2.7
2.3
8.0
6.7
1.1
2.2
Rel. A (%)
7.0
27.1
30.8
51.2
39.1
6.4
10.3
ICEWS18+H
QTO
16.6
2.6
1.3
14.8
22.5
17.2
5.9
RELAX
6.1
1.6
1.3
1.6
1.0
1.6
1.6
RELAX+QTO
19.3
3.5
2.2
15.4
22.7
17.8
6.8
Abs. A
2.7
1.0
0.9
0.6
0.2
0.6
0.9
Rel. A (%)
16.2
38.2
67.5
3.8
1.0
3.4
15.7
reachable by symbolic reasoning. Across datasets and query types, neural methods do not consistently outperform query relaxation. In many cases, their performance is similar or lower, which does not rulc out that learned representations may often reproduce patterns that can already be recovered through structural statistics.
However, a more detailed analysis shows that the low overlap between neural and query relaxation methods, coupled with the strong improvements observed when combining them, indicates that both approaches capture complementary reasoning signals. Neural models and query relaxation thus emphasize different aspects of the graph which together explain broader range of answers. These findings motivate rethinking the relationship between symbolic and neural reasoning in CQA as interacting perspectives that can inform future hybrid approaches.
Concretely, we find that a promising area where neural methods and query relaxation complement each other in path queries. We observe that the relative improvements of the optimal combination of the two approaches increases consistently with query length. This suggests that the compounding errors, which we observe in prior work (Hamilton et al. (2018a); Ren et al. (2020b); Ren and Leskovee (2020), among others) can be improved by incorporating information available from query relaxation methods. This interpretation is further supported by an analysis of successive relaxation steps for 2p queries (Appendix C), which shows that performance is preserved or improved at each step, highlighting that query relaxation mitigates error accumulation by only refining scores within tie groups.
6.1 Limitations and Future Work
Our work relies on query relaxation as an analytical tool to understand the comparative performance of neural methods for CQA, which effective for the scale of KGs that we consider in this work and that have been used benchmark existing neural methods. Extending this analysis large scale KGs might require additional techniques of scalability, and especially if were to study more complex queries than
10

---

Published in Transactions on Machine Learning Research (03/2026)
the ones considered in this work. An example, which we implemented in our work, is limiting relaxations to subset of predicates. For larger scale KGs, future analyses should explore principled ways of pruning approsimating relaxations while retaining predictive power, especially when considering incorporating the learnings from our work into future models for CQA.
Our combination experiments used an oracle to estimate the theoretical upper bound of complementarity. This is useful for analysis purposes, but designing realistic fusion mechanisms, such as learned ensembles, meta-predictors, neural architectures that explicitly incorporate relaxation signals, remains an open av- enue. Concretely, we note two concrete directions for designing future methods based on results: (1) Heuristic routing, where query relaxation counts are used when their signal is strong (for example, few ties remaining after a relaxation step), otherwise falling back to a neural model when query relaxation produces large tie groups. In this sense, query relaxation provides a notion of confidence based on how discriminative counts are for a given query. The challenge of implementing such an approach determining precise strate- gies for choosing one approach over the other. (2) Rank-level ensembling, where normalized ranks or scores from query relaxation and neural models are combined using learned weights. This approach requires devising principled combination methods, RELAX computes counts, which have different interpretation than the normalized scores computed by neural models.
Such designs would require identifying which aspects of query relaxation met can be usefully integrated into a learning pipeline, and how to do so without sacrificing differentiability or scalability.
Finally, our analysis focuses on one instantiation of broader class of query relaxation strategies. Future work could explore alternative relaxation schemes, richer statistical features (e-g., path diversity, edge weights, type constraints), domain-informed houristics. Such extensions may further sharpen understanding of what current neural methods capture and what they miss.
7 Conclusion
Our study provides a systematic analysis of neural methods for complex query answering through the lens of query relaxation. Across diverse datasets and query types, we find that neural approaches do not al- ways retrieve the same answers than simple, training-free relaxation strategy. Despite comparable overall performance, their retrieved answers differ substantially, and combining both yields statistically significant improvements. These findings highlight the importance of strong, interpretable non-neural baselines in as- sessing progress in CQA, and reveal that neural and symbolic reasoning capture complementary patterns in the graph. Understanding and bridging this gap may guide the next generation of neural architectures toward models that integrate the structural reasoning capabilities of symbolic approaches with the flexibility of learned representations.
Acknowledgments
For this work, Michael Cochez is partially funded by the Elsevier Discovery Lab, partially funded by the Graph-Maasivizer project, funded by the Horizon Europe programme of the European Union (grant 101093202), and supported by a gift from Accenture LLP. His work on this publication is in part based upon work from COST Action CA23147 GOBLIN Global Network on Large-Scale, Cross-domain and Mul- tilingual Open Knowledge Graphs, and COST Action CA24121 Knowledge Graphs in the Era of Large Language Models (KGELL), both supported by COST (European Cooperation in Science and Technology, https:/ www./ost.eww...........oo......) Daniel Daza was funded by gift from Accenture LLP.
References
Aidan Hogan, Eva Blomqvist, Michael Cochez, Claudia d' Amato, Gerard de Melo, Claudio Gutiérrez, Sabrina Kirranc, José Emilio Labra Gayo, Roberto Navigli, Scbastian Neumaier, Axel-Cyrill Ngonga Ngomo, Axel Polleres, Sabbir M. Rashid, Anisa Rula, Lukas Schmelzeisen, Juan F. Sequeda, Steffen Staab, and Antoine Zimmermann. Knowledge Graphs. Number 22 in Synthesis Lectures on Data, Semantics, and
11

---

Published in Transactions on Machine Learning Research (03/2026)
Knowledge. Springer, 2021. ISBN 978-3-031-00790-3, doi: 2.200//01122D0110002220022222222 URL https://kkgbokk.og org/.
Maximilian Nickel, Kevin Murphy, Volker Tresp, and Evgeniy Gabrilovich. A review of relational machine learning for knowledge graphs. Proc. IEEE, 104(1):11-33, 2016. doi: 10.100//PRKC.:001224333222 URL https://doi.. org/ 10. 1109//RR0CC... 2015. 2483592.
Lingfeng Zhong, Jia Wu, Qian Li, Hao Peng, and Xindong Wu. A Comprehensive Survey on Automatic Knowledge Graph Construction. ACM Comput. Surv., 56(4):94:1 94:62, November 2023. ISSN 0360-0300. doi: 10.1145/30 00.1145/361822 1262999 URL https://dd http://dlla...c....mmm acm. wwanm.rgg/ooio /ttp////...11//118999099999
Hongyu Ren and Jure Leskovec. Beta Embeddings for Multi- Hop Logical Reasoning in Knowledge Graphs. In Hugo Larochelle, Marc' Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Ticn Lin, editors, Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Pro- cessing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual, 2020. URL https://prooceedings. Abstract. html..
neurips.cc/paper///
Erik Arakelyan, Daniel Daza, Pasquale Minervini, and Michael Cochez. Complex Query Answering with Neural Link Predictors. In 9th International Conference on Learning Representations, ICLR 2021, Vir- tual Event, Austria, May 3-7, 2021. OpenReview.net, 2021. URL https://openrevie:: wtwp:/rrwwwoee.eetootuott....... Moa9F9kDwkz.
Zhanqiu Zhang, Jie Wang, Jiajun Chen, Shuiwang Ji, and Feng Wu. ConE: Cone Embeddings for Multi- Hop Reasoning over Knowledge Graphs. In Marc' Aurelio Ranzato, Alina Beygelzimer, Yann N. Dauphin, Percy Liang, and Jennifer Wortman Vaughan, editors, Advances in Neural Information Processing Systems 34: Annual Conference on Newral Information Processing Systems 2021, NeurIPS 2021, December 6-14, 2021, virtual, pages 19183, 2021. URL attps://proceese Abstract. html.
nwwrips.ccppapeerrte. cc/papper/222///assl
Michael Galkin, Jincheng Zhou, Bruno Ribeiro, Jian Tang, and Zhaocheng Zhu. A Foundation Model for Zero-shot Logical Query Reasoning. Tn Amir Globersons, Lester Mackey, Danielle Belgrave, Angela Fan, Urrch Paquet, Jakub M. Tomezak, and Cheng Zhang, editors, Advances Neural Information Processing Systems 38: Annual Conference on Newral Information Processing Systems 2024, NeurIPS 2024, Vancowver, BC, Canada, December 10 15, 2024, 2024. URL http://papers mips. cc/paper_ hills//paperr/224//haee http:///22...............6666660 ott.raaee.......0.7444000------- Dustract-Confereent html.
Cosimo Gregucci, Bo Xiong, Danicl Hernández, Lorenzo Loconte, Pasquale Minervini, Steffen Staab, and Antonio Vergari. Is complex query answering really complex? In Forly-second International Conference on Machine Learning, 2025. URL https:/ http://pparrreeeee.eeerorrraaaap wtt..e//oorr//111FFBAAAA...
Quan Wang, Zhendong Mao, Bin Wang, and Li Guo. Knowledge graph embedding: A survey of approaches and applications. JEEE Transactions on Knowledge and Data Engineering, (2(2)):72442743, December 2017. ISSN 10414347. doi: 20000//TKEE..2.0.777//.....
Publisher: TEFE Computer Society.
William Hamilton, Payal Bajaj, Marinka Zitnik, Dan Jurafsky, and Jure Leskovec. Embedding Logical Queries on Knowledge Graphs. arXiv preprint arXie:1806. 01445, 2018a.
Daniel Daza and Michael Cochez. Message passing query embedding. In ICML Workshop Graph Repre- sentation Learning and Beyond, 2020. URL betts::/aarxee orwooog//aaa..oooooooooo.a. httpg/bb//000..000//
Xuclu Chen, Zinin Hu, and Yizhou Sun. Fuzzy Logic Based Logical Query Answering on Knowledge Graphs. In Thirly-Siath AAAI Conference on Artificial Intelligence, AAAI 2022, Thiriy-Fourth Con- ference on Innovative Applications of Artificial Intelligence, IAAI 2022, The Twelveth Symposium on Educational Advances Artificial Intelligence, EAAT 2022 Virtual Event, February 22 March 1, 2022, pages 3939 9939-3948. AAAI Press, 2022. doi: 10.1609/ AAAL V3614.2333 aaai. v3614. 20310.
URL https://dol http::///ooo.rr10..111...
12

---

Published in Transactions on Machine Learning Research (03/2026)
Nurendra Choudhary, Nikhil Rao, Sumeet Katariya, Karthik Subbian, and Chandan K. Reddy. Self- Supervised Hyperboloid Representations from Logical Queries over Knowledge Graphs. In Jure Teskovec, Marko Grobelnik, Mare Najork, Jie Tang, and Leila Zia, editors, WWW 211 The Web Conference 2021, Virtual Event / Ljubljana, Slovenia, April 19-23, 2021, pages 1373 1384. ACM / IW3C2, 2021. doi: 10.1145/34423511.44488
Dimitrios Alivanistos, Max Berrendorf, Michael Cochez, and Mikhail Galkin. Query Embedding on Hyper- Relational Knowledge Graphs. In The Tenth International Conference on Learning Representations, ICLR 2022, Virtual Event, April 25-29, 2022. OpenReview net, 2022. URL https: https:// wttpooeeeeiieeeeeeeeoooeeee
Hongyu Ren, Weihua Hu, and Jure Leskovec. Query2box: Reasoning over knowledge graphs in vector space using box embeddings. In International Conference on Learning Representations, 2020a. URL httts://openrewwe net/ffrumm dir.rurnnddd...rrsSSS...
Erik Arakelyan, Pasquale Minervini, Daniel Daza, Michael Cochez, and Isabelle Augenstein. Adapting Neural Link Predictors for Data-Ffficient Complex Query Answering. In Alice Oh, Tristan Naumann, Amir Globerson, Kate Saenko, Moritz Hardt, and Sergey Levine, editors, 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. URL http::/papers. ccppperrppper_ files/papers httpppppapppp////pep
oat.raaaaae..000000--eeeerttt--- htmml.
Zhaocheng Zhu, Mikhail Galkin, Zuobai Zhang, and Jian Tang. Neural-Symbolii Models for Logical Queries on Knowledge Graphs. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvári, Gang Niu, and Sivan Sabato, editors, International Conference on Machine Learning, ICML 2022, 17-23 July 2022, Baltimore, Maryland, USA, volume 162 of Proceedings of Machine Learning Reseorch, pages PMLR, 2022. URL https: http:///ooocedddeee mlr. press/v162 htte:/hh222cchccc html.
Yushi Bai, Xin Lv, Juanzi Li, and Lei Hou. Answering Complex Logical Queries on Knowledge Graphs via Query Computation Tree Optimization. In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett, editors, International Conference on Muchine Learning, ICML 2023, 23-29 July 2023, Honolulu, Hawaii, USA, volume 202 of Proceedings of Machine Learning Research, pages 1472-1491. PMLR, 2023. URL https: / /ttp///ercceess....////////. mwr.m.r........ press//202/////// htt//baa33b html..
Hongyu Ren, Mikhail Galkin, Zhaocheng Zhu, Jure Leskovee, and Michael Cochez. Neural graph reasoning: A survey on complex logical query answering. Transactions on Machine Learning Research, 2024. ISSN 2835-8856. URL https://openrevii wwwpreeviiiieee/ffrrireeee
Survey Certification.
Kurt D. Bollacker, Colin Evans, Praveen K. Paritosh, Tim Sturge, and Jamie Taylor. Freebase: col- laboratively created graph database for structuring human knowledge. In Jason Tsong-Li Li Wang, editor, Proceedings of the ACM SIGMOD International Conference on Management of Data, SIGMOD 2008, Vancouver, BC, Canada, June 10-12, 2008, pages 1247-1250. ACM, 2008. doi:
0114451377616..1111
Andrew Carlson, Justin Betteridge, Bryan Kisiel, Burr Settles, Estevam R. Hruschka Jr, and Tom M. Mitchell. Toward an Architecture for Never-Ending Language Learning. In Maria Fox and David Poole, ed- itors, Proceedings of the Twenly-Fourth AAAT Conference on Artificial Intelligence, A AAAT 2010, Atlanta, Georgia, USA, July 11-15, 2010, pages 1306 1313. AAAI Press, 2010. doi: 10.1609/ABB AAAL V241. V2411.7519. URL https://doi.org: 16090.1.../1.00 aaaii. v2411.7519.
Luis Antonio Galárrag,, Christina Teflioudi, Katja Hose, and Fabian M. Suchanck. AMIE: association rule mining under incomplete evidence in ontological knowledge bases. In Daniel Schwabe, Virgílio A. F. Almeida, Hartmut Glaser, Ricardo Baeza-Yates, and Sue B. Moon, editors, 22nd International World Wide Web Conference, WWW '13, Rio de Janeiro, Brazil, May 13-17, 2013, pages 413 422. International World Wide Web Conferences Steering Committce ACM, 2013. doi:
Christian Meilicke, Melisachew Wudage Chekol, Daniel Ruffinelli, and Heiner Stuckenschmidt. Any- time Bottom-UP Up Rule Learning for Knowledge Graph Completion. In Sarit Kraus, editor, Proceed- ings of the Twenty-FFigh Fightt International Joint Conference on Artificial Intellggenee IJCAT 2019, Macao,
13

---

Published in Transactions on Machine Learning Research (03/2026)
China, August 10-16, 2019, pages 3137-3143. ijcai.org. 2019. doi: 10.24963/1ICAA.2019//2 URL attps://dof org/roo//// 24963/1jccc 2019/435.
X Wang, DJ Tena Cucala, B Cuenca Gran, and I Horrocks. Faithful rule extraction for differentiable rule learning models. In Proceedings of the 12th International Conference Learning Representations (ICLR 2024). OpenReview, 2024.
Duy Le, Shaochen (Henry) Zhong, Zirui Liu, Shuai Xu, Vipin Chaudhary, Kaixiong Zhou, and Zhaozhuo Xu. Knowledge graphs can be Icarned with just intersection features. In Proceedings of the 4 1sst International Conference on Machine Learning, ICML'24. JMgR.org, 2024.
Ginwa Fakih and Patricia Serrano-Alvarado. A survey on SPARQL query relaxation under the lens of RDF reification. Semantic Web, 15(6):2507-2554, 2024. doi: (0.3333/SW-24302 URL https://journals: sagepub. cttp:/c/c////abbb.a/a/aaa//aa 11t.1/00//333224443333
Carlos A. Hurtado, Alexandra Poulovassilis, and Peter T. Wood. Query relaxation in RDF. J. Data Semant., 10:31 61, 2008. doi: 10.1007/978-3-550--77888 2. URL https://doi. https://doi.org/10....o org/10.1007/
178-3-540-77688-8
Gengchen Mai, Bo Yan, Krzysztof Janowicz, and Rui Zhu. Relaxing unanswerable geographic questions using A spatially explicit knowlodge graph embedding model. In Phaedon C. Kyriakidis, Diofantos G. Hadjim- itsis, Dimitrios Skarlatos, and Ali Mansourian, editors, Geospotial Technologies for Local and Regional Development- Proceedings of the 22nd AGILE Conference on Geographic Information Science, Limassol, Cyprus, June 17-20, 2019, Lecture Notes in Geoinformation and Cartography, pages 21 39. Springer, 2019. doi: 10.1007/978- /-009/788--000--4455----7-71 2. URL
20gg/1..00 3007/178---0000- 1070000--1477-2
Meng Wang, Ruijie Wang, Jun Liu, Yihe Chen, Lei Zhang, and Guilin Qi. Towards empty answers in sparql: Approximating querying with rdf embedding. In Denny Vrandečić, Kalina Bontcheva, Mari Carmen Suárez-Figueroa, Valentina Presutti, Irene Celino, Marta Sabou, Lucie-Aimée Kaffee, and Elena Simperl, editors, The Semanlic Web ISWC 2018, pages 513 529, Cham, 2018. Springer International Publishing. ISEN 978-3-030-00671-6.
Géraud Fokou, Stéphane Jean, Allel Hadjali, and Mickaël Baron. Cooperative techniques for SPARQL query relaxation in RDF databases. In Fabien Gandon, Marta Sabou, Harald Sack, Claudia d' A'mmtto, Philippe Cudré-Mauroux, and Antoine Zimmermann, editors, The Semantic Weh. Latest Advances and New Domains 12th European Semantic Web Conference, ESWC 2015, Portoroz, Slovenia, May 31 June 4, 2015. Proceedings, volume 9088 of Lecture Notes in Computer Science, pages 237-252. Springer, 2015. doi: 10.1007/978 197777778-3333 3-188-3--9------ 18818-8) 15. URL sttps://ddi.org///// 300.000111000000--1---1----
Lao and William W Cohen. Relational retrieval using a combination of path-constrained random walks. Machine learning, 81(1):53-61 67, 2010.
Lao, Tom Mitchell, and William W. Cohen. Random walk inference and learning in a large scale knowledge basc. In Regina Barzilay and Mark Johnson, editors, Proceedings of the 2011 Conference on Empiricul Methods in Natural Language Processing, pages 529 539, Edinburgh, Scotland, UK., July 2011. Association for Computational Linguistics. URL https: /aaaaaaaaaaalloooeeeeeee org/D11-1049/.
Leo Katz. A new status index derived from sociometric analysis. Psychometrika, 18(1):39 43, 1953. doi: 10.1007/BF0228000
Lawrence Page, Sergey Brin, Rajeev Motwani, and Terry Winograd. The pagerank citation ranking: Bringing order to the web. Technical Report 1999-66, Stanford InfoLab, November 1999. URL http://ilpubs. stanford, edu: 8020/422/. Previous number STDI-WP-199990120.
Muhan Zhang and Yixin Chen. Link prediction based on graph neural networks. Advances neural information processing systems, 31, 2018.
14

---

Published in Transactions on Machine Learning Research (03/2026)
Roshni Iyer, Thuy Vu, Alessandro Moschitti, and Yizhou Sun. Question-answer sentence graph for joint mod- eling answer selection. In Andreas Vlachos and Isabelle Augenstein, editors, Proceedings of the 17th Confer- ence of the European Chapter of the Association for Computational Linguistics, pages 968 979, Dubrovnik, Croatia, May 2023. Association for Computational Linguistics. doi: (118653/v11221 10.08663//1///223..ccoom mtw.//222..clmmmmn....... URL https://acllanthologg. org/2023..../...oooo. bacl-main www...ainn.............m........ .8/.
Kristina Toutanova and Danqi Chen. Observed versus latent features for knowledge base and text inference. In Alexandre Allauzen, Edward Grefenstette, Karl Moritz Hermann, Hugo Larochelle, and Scott Wen-tan Yih, editors, Proceedings of the 3rd Workshop on Continuous Vector Space Models and their Composi- lionality, CVSC 2015, Beijing, China, July 26-31, 2015, pages 57 66. Association for Computational Tinguistics, 2015. doi:
URL https://doi. wtt.........//................. 18053/81///1111440000
Wenhan Xiong, Thien Hoang, and William Yang Wang. DeepPath: A Reinforcement Learning Method for Knowledge Graph Reasoning. In Martha Palmer, Rebecca Hwa, and Sebastian Riedel, editors, Proceedings of the 2017 Conference on Empirical Methods in Natural Language Processing, pages 564 573, Copenhagen, Denmark, Seplember 2017. Association for Computational Linguistics. doi: attps://aclantbologg org/D17-100//.
URL
Will Hamilton, Payal Bajaj, Marinka Zitnik, Dan Jurafsky, and Jure Leskovec. Embedding logical queries on knowledge graphs. In S. Bengio, Н. Wallach, H. Larochelle, K. Grauman, N. Cesa- Bianchi, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 31. Cur- ran Associates, Inc., 2018b. URL https://pppet https://proceeddnggs www.eeeenn.......p.............. 0555c35ccaff00eee653ss0d02222
neurips wwturip..cpppppe.... wwtpappr_fileeeppeeeeeeeeeeeeeee files/paper/2018/f110
pdf.
Antoine Bordes, Nicolas Usunier, Alberto Garcia-Duran, Jason Weston, and Oksana Yakhnenko. Translating embeddings for modeling multi-relational data. In C.J. Burges, L. Bottou, M. Welling, Z. Ghahramani, and K.Q. Weinberger, editors, Aduances in Neural Information Processing Systems, volume 26. Cur- Associates, Inc., 2013. URL https://procedddggg www.eeeeiinnn..uuis.ss..... pttp:psccccpppprralle///p/////// / Tcccc2ar722200113114468888822282 pdf.
Hongyu Ren, Weihua Hu, and Jure Leskovec. Query2box: Reasoning over knowledge graphs vector space using box embeddings. In International Conference on Learning Representations, 2020b.
15

---

Published in Transactions on Machine Learning Research (03/2026)
A
Appendix
A.1 Query relaxation strategies
In Algorithm 1 we present the exact procedure used to obtain the results reported in the main paper. Next, we motivate our design decisions and discuss worst case complexity and run time.
A.2 Design Decisions
Progressive Relaxation Our relaxation strategy follows progressive relaxation philosophy, prioritizing signals that preserve the most specific query information before resorting to more general cues. While fully relaxed features (e.g., global indegree) can indeed be strong indicators of prominence or connectivily, they are also less discriminative with respect to the original query intent. By starting from the most constrained (anchor-rclaxationnnnl)) formulation and introducing incrcasingly relaxed criteria only as tie-breakers, we ensure that ranking decisions remain grounded in the semantics of the original query. The database literature offers many alternative ways to combine relaxed signals (Fakih and Serrano-Alvaradee 2024; Hurtado et al., 2008; Mai et al., 2019; Fokou et al., 2015), but our approach is guided by the philosophy that more specific constraints should always dominate less specific ones, as they carry higher semantic fidelity to the original query.
In our experiments, this progressive strategy consistently yielded the most stable and interpretable results, even though we do not claim be universally optimal. Instead, our goal is to compare such strategies with existing neural methods for query answering.
Fallback Strategy The final two stages of progressive relaxation rely global signals, specifically, (rela- tion) indegrecs, that do not depend on the structure of the query. We therefore precompute and store these values in a lookup table, enabling fast retrieval al query time. This design allows us to produce rankings even when earlier, more specific query evaluations are skipped due to space or time constraints, ensuring both efficiency and robustness.
Efficiency Tradeoff We observe that, given our anchor-relaxation query and available statisties, only the 3p query has an additional relaxation step that could be used as additional tiebreaker by re-executing this further relaxed query to the engine. We choose not to do this in favor of a clear and efficient workflow: the query engine is invoked only once (the expensive step), and all subsequent relaxations rely on lightweight statistical lookups.
Query Decomposition Trick For intersection-type queries (e-g., 2i, 3i), direct evaluation can produce large intermediate join on the shared variable (e.g., target t), yielding cubic or quartic complexity. To mitigate this, evaluate each arm of the intersection separately an aggregate subquery grouped by t, and then merge the resulting tables. We use this optimized version for intersection-only queries but keep the original (non-aggregated) formulation for projection intersection combinations.
B Complexity Analysis
Relaxation proceeds hierarchically: more specific matches are preferred, and further relaxation is only applied when ties occur among candidate entities worst-case complexity of Step (anchor-relaxation) of Algorithm 1. Knowledge Graph (KG) with Ne entities and N, relations. Complexities
We evaluate each query type are expressed in terms of N₂ since for KGs it dominates the cost of enumerating possible bindings. Each query paltern can be seen as a join of triple patterns; the nunber of free (unbound) entily variables determines the exponent Ne in the worst case. Dense graphs, where each entity is connected to every other entity by each relation type, represent the upper bound for these operations. Since the intermediate join results must be materialized (or at least streamed) to compute counts, the space complexity scales in the same order as time.
16

---

Published in Transactions on Machine Learning Research (03/2026)
Therefore, for k-hop path or multii-ineerecttinn query with worst-case complexity O(Ne), both the time and space complexities are (generally) ((N²).
For intersection queries, we mitigate this by decomposing the complex query in multiple simple queries and aggregate the results. See section A.2. This subquery aggregation trick reduces the overall complexity (e.g., from ( to O(3N.)) For all other query types, the asymptotic time complexity does corresponds to the number of possible entity bindings explored during query execution, see Table 3.
However, in practice KGs are highly sparse graphs, and the worst-case complexity is not realistic scenario. Therefore, we also provide an empirical evaluation of the runtimes, which we present next.
B.1 Empirical Run Time Performance
We evaluate time performance on the benchmarks used in this study. We set the standard GraphDB maximum memory to 10GB (default), and enforce timeout of 10s. Naturally, both can adjusted based on preferences. Please present results in Table 4. The results are in line with the theoretical complexity analysis (Table 3) and confirm the practical observation that KGs are sparse graphs i.e, our fallback strategy only has to be invoked an acceptable number of timcouts. Our primary goal was the analysis of the results, not runtime performance. that concern, one could execule queries in parallel to improve efficiency.
C Additional Results
Alternative metrics. As an alternative to MRR, we present results of Hits at 10 (H@10) in Table 5. Similar to the results observed with MRR, we notice that there several cases, the performance of RELAX is close or better than that of neural methods.
Combining RELAX with other methods. Section 5.4 shows the upper bound in performance that results from the optimal combination of rankings produced by QTO and RELAX. Here present additional results where RELAX is combined with ConE (Table 6) and ULTRAQ (Table 7). Similar to the experiments with QTO, we note that the upper bound results in a significant increase MRR, which demonstrates the complementary nature of the correct answers computed by neural methods and RELAX.
Effect of progressive query relaxation. To further analyze the behavior of query relaxation and assess whether progressively relaxing query leads to error escalation, we examine the effect of individual relaxation steps performance. In particular, we foeus on path queries of length two (denoted as 2p), for which the relaxation procedure proceeds through multiple stages described in Section 4.
Recall that the relaxation strategy operates hicrarchically: at each step, only entities that received identical scores in the previous step (tie groups) are affected, while the relative ordering of entities with distinct scores is preserved. This design suggests that additional relaxation steps should not degrade performance, but instead either maintain or improve the ranking of correct answers. To verify this empirically, we compute Mean Reciprocal Rank (MRR) after each relaxation step for 2p queries on FB151237+H, H and ICEWS18+H. The results are shown in Table 8.
Across all datasets, observe that intermediale relaxation steps preserve MRR, indicating that breaking ties at these stages has no effect on performance. Importantly, the final relaxation step consistently increases MRR, demonstrating that deeper relaxation resolves ambignity among tied candidates rather than intro- ducing additional error. These results provide no evidence of error escalation as relaxation proceeds, and instead support the stability of the hierarchical relaxation strategyy. They further contrast with neural query answering methods, where errors may accumulate predictions are composed over longer paths.
17

---

Published in Transactions on Machine Learning Research (03/2026)
Preliminaries Definitions:
G R)) Knowledge graph with edges & and relations R
Q: Conjunctive query over g
Anchors A = -aa,....,as) ax): known entities in Q
Target variable Us variable in Q rank candidate answers for
RelaxAnchors(Q): Replace anchors a, Q with newly coined variables ?a
InDeg, [v r,) E E (indegree w.r.t relation)
InDeg(#) | (v.r) EV R (y,r, E E (total indegree)
et satisfics Q - 3 path(s) & matching the constraints Q
For intersection queries of the form, we define T((1)) + [a, 0x) E
Conjunctive Query Q with anchors A = {ai,..., ..), a KG 9, target variable e Output: Ranked candidate answers for t/.
Input:
Step 1: Anchor relaxation
Qrelaxed RelaxAnchors(Q))
Step 2: Execute relaxed qucry and initial scoring
C (Ue Ur satisfies Qrelaxed in G}
If Q is intersection query:
For each anchor a,, compute (v:) score(v.) 4
Else:
score(v:) <- number of matching paths
Partition candidates into tie groups:
G G2 Gin Gj {c E C
same Step 2 score)
Step 3: In-degree given relation (for ties within groups)
For each lie group Gy:
If Q is intersection: score(c) + I InDeg,, (c), Ve e G2
Else: score(e) + (c), Gj
Higher-ranked groups remain above lower-ranked groups
Step 4: Target indegree (maximum relaxation for remaining ties)
For each tie group still tied: score(c) InDeg(c), Ve G3
Return: Candidates v sorted by descending score(v:), preserving group order
Algorithm 1: RELAX: Hierarchical Query Relaxation for Conjunctive Queries with Grouped Tie-
Breaking
18

---

Published in Transactions on Machine Learning Research (03/2026)
Table 3: Worst-case time complexity for each query type when the anchor relaxed. Complexity grows with the number of free entity variables. For intersection queries, subquery aggregation significantly reduces cost.
Query type Relaxed pattern
Free vars
Evaluation style
Worst-case
1p
r, (?a,ri, a) A (2)
table lookup
O(c)
2p
direct
O(N2)
3p
(2a, A (21, A (02, ra, 7)
direct
((N2)
(Tai; T) (?a2, v2, T)
with aggregation trick
O(2N.)
3i
(2a1, r1, T) A (?az, r2, T) A (?ag, r3. T)
with aggregation trick
O(3N.)
ip
(?a,.ri, (2.1)) A (3, T)
direct
O
pi
(1,)) A (z, r2, T) A (?a, r3, T)
direct
O(N2)
Table 4: Empiriaal run time performance for each query type when the anchor relaxed (avg, std, timeout ratio). A timeout called if the query does not finish within 10 seconds.
Dataset
1p
2p
3p
2i
31
ip
pi
FB115237+H
avg (ms)
30
80
331
60
72
1187
276
std (ms)
54
129
559
56
65
1963
579
timeout (%)
0
0
0
0
15.6
NELL995+HH +H
avg (ms)
33
47
107
50
56
1088
95
std (ms)
112
37
268
61
74
1969
158
timcout (%)
0
0
O
7.8
ICEWS18+H
avg (ms)
127
321
1382
146
143
84
1182
stdl (ms)
288
290
1786
142
135
625
1757
timeout (%)
0
1.9
0
0.5
2.0
Table 5: Query answering results (H@10 in %). Orange indicates worse equal performance than RELAX, lighter orange indicates delta of 1 or less with RELAX.
Model
1p
2p
3p
2i
3i
ip
pi
ICBWS18+H NELL995+H FB15K237-H
ULTRAQ
59.8
9.5
6.7
10.2
12.9
15.7
8.4
ConE
58.4
7.0
5.8
16.2
19.6
10.1
6.3
QTO
67.1
9.7
6.7
18.0
19.8
21.9
10.7
RELAX
45.9
7.3
6.5
8.8
9.7
8.5
3.1
ULTRAQ
50.7
11.9
9.0
14.4
19.2
17.7
26.3
ConE
71.8
15.3
10.5
40.7
45.1
21.4
24.6
QTO
77.3
18.1
12.5
32.3
34.4
31.3
29.7
RELAX
51.8
10.0
9.7
25.3
26.1
11.5
8.1
ULTRAQ
12.2
2.3
2.4
13.4
20.5
2.8
17.0
ConE
8.7
1.9
1.3
2.3
1.0
3.1
2.4
QTO
32.5
4.9
2.4
27.1
33.7
11.7
29.9
RELAX
11.8
2.9
2.2
3.5
2.0
3.2
3.3
19

---

Published in Transactions on Machine Learning Research (03/2026)
Table 6: Query answering results (MRR) comparing the original performance of ConE, RELAX, their optimal combination, denoted as REIAX+ConE, and the relative difference in percent.
Model
1p
2p
3p
21
3i
pi
ip
FB15k237+
ConE
38.1
3.6
3.0
7.8
9.7
3.2
5.5
RELAX
31.5
4.0
3.9
5.2
5.2
1.8
5.3
RELAX+ConE
44.2
5.7
5.4
10.0
11.5
4.0
8.2
Abs. A
6.1
1.8
1.5
2.2
1.8
0.8
2.7
Rel. A (%)
16.0
44.5
38.0
27.6
18.5
24.7
49.0
NELL995
ConE
52.9
7.8
5.7
19.5
22.5
14.0
11.9
RELAX
35.1
5.6
5.2
12.4
12.1
3.9
6.5
RELAX+ConF.
58.4
10.1
8.4
25.1
27.1
14.2
Abs. A
5.6
2.3
2.7
5.6
4.6
1.1
2.3
Rel. A (%)
10.5
29.2
46.8
28.5
20.5
8.2
19.0
ICEWS18+H
ConE
3.8
0.9
0.8
1.0
0.4
1.1
1.4
RELAX
6.1
1.6
1.3
1.6
1.0
1.6
1.6
RELAX+ConE
7.1
2.0
1.7
1.8
1.1
1.9
2.3
Abs. A
0.9
0.4
0.4
0.2
0.1
0.3
0.7
Rel. A (%)
14.8
24.8
26.9
11.8
9.2
20.3
44.0
Table 7: Query answering results (MRR) comparing the original performance of ULTRAQ, RELAX, their optimal combination, denoted as RELAX+ULTRAQ, and the relative difference in percent.
Model
1p
2p
3p
2i
3i
pi
ip
FB15K237+H
ULTRAQ RELAX
40.6
4.5
3.5
5.2
7.2
5.3
10.1
31.5
4.0
3.9
5.2
5.2
1.8
5.3
RELAX+UITRAQ
45.6
6.3
5.3
8.3
9.8
6.1
11.6
Abs. A
4.9
1.8
1.4
3.1
2.6
0.8
1.5
Rel. A (%)
12.1
41.3
36.6
59.5
35.9
14.8
15.1
NELL995
ULTRAQ
38.9
6.1
4.1
7.9
10.2
15.8
9.3
RELAX
35.1
5.6
5.2
12.4
12.1
3.9
RELAX+UITRAQ
52.4
8.8
7.0
18.3
19.2
17.3
12.2
Abs. A
13.5
2.6
1.8
5.9
7.0
1.5
2.9
Rel. A (%)
34.8
43.0
34.1
47.1
58.2
9.8
31.4
ICEWS18
ULTRAQ
6.3
1.2
1.2
7.0
11.7
8.8
1.3
RELAX
1.6
1.3
1.6
1.0
1.6
1.6
RELAX+UITRAQ
11.6
2.3
2.0
8.1
12.1
9.8
2.4
Abs. A
5.3
0.7
0.6
1.1
0.5
1.0
0.8
Rel. A (%)
85.2
44.0
47.7
15.3
3.9
11.7
48.6
20

---

Published in Transactions on Machine Learning Research (03/2026)
Table 8: MRR after successive relaxation steps for 2p queries.
Relaxation step
FB151237+H
NELL995+H
ICEWS18+H
0.0315
0.0428
0.0148
2
0.0315
0.0428
0.0148
3
0.0401
0.0565
0.0160
21


Reviews:
[{"review_id": "5Ic7yGB4aY", "reviewer": "Reviewer_hT4K", "summary": "", "questions": "", "limitations": "", "rating": null, "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": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper systematically analyzes the strength of query relaxation in answering complex knowledge graph-based queries. The thorough empirical results demonstrate that the SOTA neural approaches do not outperform this simple strategy consistently, and there is no clear overlap in the rankings proposed by the neural methods and this training-free strategy. Consequently, the authors show that combining the two directions help to further boost the performance of complex query answering by a clear margin.", "claims_and_evidence_yn": "Yes", "claims_explanation": "- The proposed strategy of query relaxation, albeit not entirely novel, is easy to follow and clearly demonstrated by Example 2.  \n- The three research questions studied in Section 5 are strongly motivated and built upon sequentially.  \n- The empirical results to the three research questions are clearly presented and accurately supported by the figures and tables in Section 5.", "audience_yn": "Yes", "audience_explanation": "The empirical results of this paper show that the simple, training-free strategy of query relaxation is a strong baseline in complex query answering. This is clearly an important finding for the community, where future work, especially those neural methods, should sincerely consider this baseline in their reports.", "requested_changes": "It would be great to include some error analysis of the query relaxation strategy. Since the relaxation happens step by step, as explained in Section 4, it is important to check whether this would lead to error escalation as more relaxation is allowed.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "BxJdmiIMzU", "reviewer": "Reviewer_GR5S", "summary": "", "questions": "", "limitations": "", "rating": null, "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": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper shows that a simple heuristic baseline is able to solve some parts of the Complex Query Answering problem that existing neural methods cannot solve, and that there is potential for combining the approaches.\n\n(CQA) In Complex Query Answering (CQA) one is given a knowledge graph (KG) and a question like the example in this paper: “What is the location of the baseball team for which Aaron Judge plays?”. These questions correspond to a small sub-graph of the KG where the answer could be found by traversing the graph from known anchor entities to unknown target entities, except that missing relations may preclude the existence of such a path. Neural approaches to CQA are state of the art according to existing benchmarks, but recent work (Gregucci et al. '25) showed that these benchmarks focus mostly on simple queries and proposed a new benchmark that is used here to deconstruct performance according to query complexity.\n\n(RQ1) This paper proposes a simple query relaxation heuristic for CQA which is called RELAX. It ranks potential target/answer entities according to how many paths exist in the known graph that are similar to the query (except with a minimal number of entities or relations changed). In the first (RQ1) experiment the paper establishes that this heuristic and non-learned baseline can outperform some neural methods on some more complex query types, though the neural methods most often perform best.\n\n(RQ2) Approaches produce a ranked list of answers and are evaluated via MRR (Mean Reciprocal Rank). The paper next compares approaches by asking how similar the ranked lists of answers are between RELAX and 3 neural approaches. It shows that there is significant dissimilarity between these lists: most answers are not shared between a pair of approaches, fewer answers are shared for (roughly speaking) higher complexity queries, and there is variation across datasets. The conclusion is that the errors of neural methods are complementary to the errors of RELAX.\n\n(RQ3) Finally, the paper considers an oracle approach that combines RELAX with neural approaches to investigate how complementary they could be. It does this by picking the ranked answer list from either RELAX or a neural approach like QTO on a per-query basis. The results show consistent improvements in MRR across all query levels and datasets, so the paper concludes there is something to be gained here.", "claims_and_evidence_yn": "Yes", "claims_explanation": "The claims in the paper are mostly well supported by experiments, but the paper does over-estimate the performance of the proposed RELAX baseline by claiming that it is closer in performance to the neural methods than it actually is (see 2nd part of RQ1 below).\n\n> RQ1 (Comparable Performance): \"Neural methods do not consistently perform better than query relaxation strategies. Across datasets and query structures, the two perform similarly, despite the latter involving no learning or optimization.\"\n\nThe first sentence is well substantiated (Tab 1), but the 2nd is not. I do not think it is fair to say that RELAX performs similarly to the neural approaches for the more complex queries (2i, 3i, pi, ip). In Table 1 it looks like it almost always underperforms them.\n\n> RQ2 (Low answer overlap): \"The top ranked answers from neural and relaxation-based approaches diverge substantially, indicating that they capture different patterns in the graph.\"\n\nThis claim is well substantiated by the IOU experiments (Fig 2).\n\n> RQ3 (Complementarity): \"Combining their answer sets consistently improves performance, suggesting that both contribute distinct and complementary reasoning signals.\"\n\nThis claim is well substantiated by Table 2.", "audience_yn": "Yes", "audience_explanation": "I think the audience for this paper includes people interested in CQA, but also those interested in interpretability of neural nets.", "requested_changes": "* Do not claim that the RELAX approach matches the performance matches that of neural approaches across all the different configurations studied and more clearly emphasize where the RELAX approach struggles. That change does nothing to contradict the main point of the paper; I think the paper still clearly details a complementarity between RELAX and the studied neural approaches.\n\n* The paper reports MRR improvements in relative terms instead of absolute terms. I think an improvement of +0.02 MRR from 0.6 is probably more difficult than +0.02 from 0.2 and relative percent improvement suggests the opposite. It may be better to present absolute improvement instead of or in addition to relative improvement.", "broader_impact_concerns": "No concerns", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "BCtn9r3j8y", "reviewer": "Reviewer_FBxT", "summary": "", "questions": "", "limitations": "", "rating": null, "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": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "**Summary of Contributions:** This work challenges a prevailing assumption in neural CQA research and highlights the importance of strong, interpretable non-neural baselines. It also suggests that future progress may benefit from hybrid approaches that integrate structural query relaxation principles into neural architectures. \n\n**Strengths:**\n- Rather than proposing yet another neural model, the paper asks a well-defined and underexplored question about what existing neural CQA methods actually capture, making the contribution conceptually valuable. \n- The findings provide concrete evidence for complementarity between neural and symbolic reasoning, offering useful guidance for future hybrid methods.\n\n**Weaknesses:**\n- The oracle fusion does not translate directly into a practical method, and the paper does not propose a realizable hybrid approach\n- How broadly the conclusions extend to more expressive query classes or alternative relaxation schemes? Now, the analysis focuses on conjunctive queries and a specific instantiation of query relaxation", "claims_and_evidence_yn": "Yes", "claims_explanation": "The paper’s central claims that neural CQA methods do not consistently outperform a training-free query relaxation baseline, that the two approaches retrieve substantially different answers, and that their combination yields complementary gains are each backed by targeted empirical analyses. The authors evaluate multiple SOTA neural models across several datasets and query structures, using standard metrics, which lends credibility to the performance comparisons.\n\nBeyond aggregate performance, the overlap analysis based on Jaccard similarity provides convincing evidence that similar MRR scores often arise from fundamentally different ranked answers, directly supporting the claim that neural methods do not subsume relaxation-based reasoning. The oracle-based combination experiments further strengthen this conclusion by demonstrating consistent and statistically significant gains, reinforcing the argument for complementarity rather than redundancy.\n\nWhile the analysis is limited to conjunctive queries and a specific relaxation strategy, within this scope the experimental design is careful, the evidence is coherent, and the conclusions are well-aligned with the presented results.", "audience_yn": "Yes", "audience_explanation": "While the work is specialized to CQA over knowledge graphs, its methodological insights, especially regarding how to rigorously assess claims of generalization and reasoning, are likely to resonate with readers interested in trustworthy evaluation and hybrid reasoning systems", "requested_changes": "- I recommend the authors try to discuss practical hybrid strategies beyond the oracle. The oracle-based combination experiments convincingly demonstrate complementarity,  while plausible non-oracle fusion strategies, e.g., heuristic selection rules, confidence-based routing, or lightweight learned combinations, even if left for future work, would make the implications of the results more concrete. \n- Please provide additional intuition for failure modes of neural methods.  The analysis shows that neural performance degrades with query length and that overlap with relaxation decreases for more complex queries. A more explicit discussion, possibly with qualitative examples, of why certain neural models fail in these settings would further enhance interpretability. \n- Add brief reminders of query-type notation (e.g., 2p, 3i) when first referenced in the experimental section. \n- Ensure consistent terminology when referring to “query relaxation,” “relaxation-based reasoning,” and “RELAX” to avoid any possible confusion for non-specialist readers.", "broader_impact_concerns": "The submission focuses on a methodological and empirical analysis of complex query answering over knowledge graphs. It does not introduce new data sources, deployable systems, or application-specific models that could directly raise ethical concerns related to fairness, privacy, security, or misuse. The proposed query relaxation strategy is analytical in nature and is used primarily as a diagnostic baseline rather than as a production-ready system.\n\nWhile the findings may influence future research directions in neural–symbolic reasoning and benchmarking practices, these implications are methodological rather than societal. As such, the work does not appear to require an additional Broader Impact Statement beyond standard disclosure, and there are no ethical risks that are insufficiently addressed.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Decision: Accept (poster)