We thank the reviewer for praising our motivation, contribution and presentation. We will address all the questions in the following. We believe we can do this easily and hope to reach full acceptance.

Lack of discussion of related work; CQD-Hybrid is very similar to the QTO [1] and I think the difference should be cited and discussed; difference between CQD-Hybrid and QTO?

We added a discussion of related works in the revised version of the paper (page 8), including a paragraph of hybrid solvers like QTO, highlighting the differences with CQD-Hybrid in Appendix A.2. See also our global answer.

As an effort to propose new benchmarks, the experiments for the new benchmark are a little less. More baselines, some case analysis, etc., should be added.

We added QTO as a baseline for the new benchmarks in the revised version of the paper. We are happy to add more baselines and run further analysis, if you could be more specific.

The problem of information leakage in training graphs can be solved well by the inductive setting in naive knowledge graph reasoning (one-hop reasoning) task.

We agree, but we remark that the transductive setting we address is widely adopted and complementary to the inductive scenario. Therefore, investigating the issue of transductive benchmarks and fixing them without changing setting is an important contribution.

That said, the fact that inductive benchmarks can be “more challenging” will depend on how they are created. One would need to perform an in-depth analysis to the scripts and process that generate them as we did for the transductive. As in our case, the issue is not the transductive scenario, but the way the benchmarks have been generated and “blindly” used so far.

Actually, there have been some attempts to establish inductive settings in CQA[1][2], where there will be no information leakage because the training and test graphs are different. How do you think this paper differs from these works?

We remark that we do not propose a benchmark for the inductive setting, rather propose a benchmark on the transductive setting that truly evaluates reasoning performance of transductive models on performing complex query answering. We will cite those works as related works, but clarifying they are addressing two different problems. One can have a rigorous transductive benchmark with no leakage, as we shown.

In my opinion, link leaks in the training graph only affect the GNN based and neural link predictor based methods, while the embedding-based methods do not take advantage of the information in the training graph (except for 1p queries). Why does this type of approach also degrade on the new benchmark?

Our experiments suggest that also the embedding-based methods are affected by this leakage. Due to their extensive training on several query types (they train on up to 150.000 of queries for 10 query types) we suspect that they implicitly take advantage of existing triples by memorizing them in the embeddings as they are trying to reconstruct the triple tensor [3]

[3] Trouillon, Théo, et al. "Complex embeddings for simple link prediction." International conference on machine learning. PMLR, 2016.

We thank the reviewer for considering our paper interesting and praising our deep analysis. We proceed by answering their questions, believing all can be easily addressed.

almost all researches conducted on complex query answering in recent years included negative queries

Note that, since queries with negation contain a “positive” sub-query and a single negative link, our analysis can be easily carried over as the positive sub-query can be reduced to a simpler type in the presence of training links. In fact, in FB15k-237 and NELL995, for queries involving negation, we analyzed the presence of existing links in the non-negative reasoning tree of the (q,a) pairs, and we can reveal that 95.4% of 3in query-answer pairs and 98.4% of pin (q,a) pairs in FB15k-237 have existing links present in the non-negative part of their reasoning tree. We will provide such percentages for the rest of the queries involving negation in the revised version of the paper in Table A.1 in Appendix A.1

SOTA CQA models fail significantly on so-called full-inference pair is questionable, as it doesn't include recent models that are built by symbolic search algorithms, like QTO[1] and FIT[2], which use neural link predictors combined with searching algorithms and seems to bypass the challenges proposed by full-inference pair

In the revised version of the paper we will show that this is quite the opposite. Those hybrid models work great on the old benchmark, mainly because they’re constituted in the vast majority by partial-inference query-answer pairs, which QTO, FIT, and CQD-Hybrid exploit. In fact, when evaluating QTO on the portion of full-inference 2p queries of FB15k-237, the state-of-the-art remains ConE (table A.4), confirming how the perception of the progress in the field has been distorted due the the high presence of existing links. We do not consider FIT as it is equivalent to QTO on the query types we considered (see appendix G.2, and Table 5 of FIT). We are open to run more baselines if the reviewer has additional suggestions.

definition of union query just requires one link to hold in the graph, I do not see the necessity to do such filtering as Figure A.1 as it more resembles 2i query type after filtering.

We do the filtering because some links are impossible. Even if it’s true that only one link needs to hold in the graph, union queries should evaluate how good CQA models are in performing such a union between two missing links. However, if only one link is missing and the other does not exist at all, we are measuring something different, which gives a ‘’false’’ sense of hardness of union queries: 2u queries should be as hard as 1p, not harder!

In fact, 2u was reported to have an MRR much much lower than 1p, but this was not due to the hardness of the union itself, rather due to the presence of non-existing links in their reasoning tree. By filtering out such query-answer pairs we obtain performance that are similar to 1p.

Dear Authors: Thank you for making the rebuttals and I recognize your effort in adding QTO as one of your baselines to make the experiments more extensive. However, I think the other concern is still valid.

We do the filtering because some links are impossible. Even if it’s true that only one link needs to hold in the graph, union queries should evaluate how good CQA models are in performing such a union between two missing links. However, if only one link is missing and the other does not exist at all, we are measuring something different, which gives a ‘’false’’ sense of hardness of union queries: 2u queries should be as hard as 1p, not harder!

Regarding the discussion of the union query, if there must be two missing links, then what is the difference between a conjunctive query and a disjunctive query? 2u and 2i will be exactly the same! I think that violates the very definition of the disjunctive query.

Note that, since queries with negation contain a “positive” sub-query and a single negative link, our analysis can be easily carried over as the positive sub-query can be reduced to a simpler type in the presence of training links.

that queries with negation contain a “positive” sub-query and a single negative link is only true based on the Q2B/BetaE dataset, it is far from something that can be taken as granted and can be wrong in more advanced dataset, therefore the whole discussion is really questionable when the query doesn't meet this condition and the definition of ``full-inference'' becomes dubious.

We thank the reviewer for recognizing that we addressed some of their concern, and we hope this can be reflected in a score update. We proceed by addressing the left concerns.

Regarding the discussion of the union query, if there must be two missing links, then what is the difference between a conjunctive query and a disjunctive query? 2u and 2i will be exactly the same! I think that violates the very definition of the disjunctive query.

Let’s break this into the following points:

1. Overall, when answering a 2u union query, we’re interested in any link between the two. This is not the issue, however. The issue is that during evaluation in the old benchmarks, we have to deal with non-existing links, that is, links that do not belong either to the train or test splits. Evaluating a query-answer pair that has one non-existing link and one missing link in their reasoning tree is problematic. This is why we filter-out non-existing links and only evaluate on answers that have two missing links in their reasoning tree.

2. Why is the presence of non-existing links problematic for evaluating 2u queries? Models are trained on existing links and non-existing links will have a very low probability to exist. Therefore, if at evaluation time we ask a model to perform well to non-existing links, the reported MRR will be lower than expected, as these links are out-of-distribution. This can be clearly seen in the old benchmarks, where 2u queries had a much lower MRR than 1p queries: on these benchmarks we are asking models to score triples that do not belong to the original KG.

3. Therefore we filter out non-existing links. Such filtering is done in the same spirit of filtering out easy answers in Q2B/BetaE datasets. By filtering out some answers we do not say they are invalid, rather that we do not evaluate on them. While easy answers are filtered-out because they can be directly retrieved without predictions, answers that have non-existing links in their reasoning tree are filtered-out to evaluate the models’ performance in performing the union between missing links only.

4. Even after the filtering, 2i and 2u are not the same, as still we’re evaluating two different operators. Logically, 2u is as hard as 1p, you should agree with this statement, because we just need the model to correctly predict one of the two missing links, while for 2i we still need both to hold. You can see that this was not reflected in the old benchmarks, but it is now reflected in the new benchmarks. 2u and 1p are roughly the same in terms of MRR and there is now a significant performance difference between 2u and 2i in the new benchmarks (Table 5).

that queries with negation contain a “positive” sub-query and a single negative link is only true based on the Q2B/BetaE dataset, it is far from something that can be taken as granted and can be wrong in more advanced dataset, therefore the whole discussion is really questionable when the query doesn't meet this condition and the definition of ``full-inference'' becomes dubious

Which benchmarks are you referring to? The vast majority of CQA benchmarks that are commonly used, interpret negation queries in this way.

We furthermore remark (again) that regardless of the query type, the analysis that we did can be extended to other benchmarks. Applying it to negation queries is just an example to show that this can be carried out in different ways to different query types. The only condition that we impose is that every link in the reasoning tree has to be only in the test graph; such condition can be applied to any query structure. However, if one wants to bring our analysis to other benchmarks, one need to check the way query are generated to make sure this condition is satisfied.

We hope that we addressed all your concerns now, and we are happy to discuss it further if needed. We also encourage you to point to specific lines in the paper that might lead to a confusion.

We thank the reviewer for their comments and for deeming our work well written, easy to follow and highlighting an important issue.

The baselines lack of the symbolic methods like QTO and FIT, which are the mainstream of CQA methods; I am curious that the performance of symbolic method QTO and FIT as they already have the hybrid information

We thank the reviewer for pointing out the existence of such symbolic methods. In the revised version of the paper, we will also add a comparison with other neuro-symbolic methods like QTO. We do not consider FIT as it is equivalent to QTO on the query types we considered (see appendix G.2, and Table 5 of FIT). See our global answer concerning QTO reporting new results. We are in the process of adding complete results for the new benchmarks. The bottom line is that QTO performance is comparable to the other solvers: that is the new benchmarks reveal the “true hardness” of CQA. Our story and contribution still holds.

BetaE have three KGs but only two KGs are presented in the paper.

As we mentioned in the paper “ We do not consider FB15k [1] as it suffers from data leakage [2]”, we do not use FB15k as it was found to suffer from a data leakage problem [2].

[1] Bordes, Antoine, et al. "Translating embeddings for modeling multi-relational data." Advances in neural information processing systems 26 (2013).

[2] Toutanova, Kristina, and Danqi Chen. "Observed versus latent features for knowledge base and text inference." Proceedings of the 3rd workshop on continuous vector space models and their compositionality. 2015.

'reduced to easier types' is weird because query types with less constraint will be easy to solved than original query types, for example the performance of 3i is good than 2i.

The performance of 3i being much better than 2i is an indication that the old benchmarks are not good for evaluating true complex query answering performance. In fact, when adding another constraint there should be a drop in performance, as we’re adding an additional prediction that carries an error. Instead, in the old benchmarks there is a significant increase in performance because such added links were already present in the training data, making the query easier, not harder!

CQD-hybrid is not the first an hybrid solver. QTO and FIT use the information from observed KG and trained link predictor

We thank the reviewer for pointing out the existence of such symbolic methods. We amended the line “To the best of our knowledge, this is the first time such an hybrid solver is proposed in the CQA literature.” and added more lines to contextualize QTO on page 8. We remark that CQD-Hybrid is not the main contribution of the paper, see our global answer above.

Do you vary your argument in train queries? I am wondering the phenomenon that existed CQA models fails is caused by the train datasets have too many partial inference answers. Thus I am curious about the performance of symbolic search methods where these methods don not use queries to train.

No, we re-used the same training queries. Which “arguments” are you exactly referring to?

Thank you for providing the anonymous repository to reproduce the experimental results.

However, I encountered some issues while trying to run your experiments. First, several necessary files are missing, including dataset.py and the src/ directory, as well as the benchmark data. After obtaining the necessary files and data from the QTO repository and your anonymous repository referenced in the main paper, I still faced a data loading issue, specifically: Exception has occurred: UnpicklingError invalid load key, 'v'.

We believe the main concerns of the reviewer can be fully addressed, as discussed in the general answer to all reviewers and in the single comments below.

The dataset discussed only covers the query types in [1], which is outdated today. In 2024, several datasets covering far more complex queries are also proposed, including [2] for queries with logical negation, [3] for cyclic queries, and [4] for multi-answer variables.

We agree that more sophisticated queries are possible but i) the benchmarks we analyze are still widely used (see our global answer as well) and therefore our message to the community using them is valid and ii) more sophisticated benchmarks such as those using negation are still based on the same principle, and can be affected in the same way.

See our global answer above: training links are also present in negation queries. We will update the paper with full results. For example, in 95.4% of 3in query-answer pairs and 98.4% of pin in FB15k-237 there are training links in the non-negative part of their reasoning tree. We report these values in Table A.1 in Appendix A.1.

The bottom line is that regardless of how intricated a query structure is, the hardness of a query-answer pair depends on the number of training links that can be found in its reasoning tree

For the ``fair'' split of triples, the answer is also unaware of existing studies on temporal CQA [5]

We remark we are not solving temporal CQA. Instead, we use the temporal information to better sample classical triples (no temporal information is retained).

Moreover, in [5] they use kg splits obtained by sampling uniformly at random the knowledge graph , while we create new splits s.t. the test only contains future triples (w.r.t the triples contained in train and valid).

baselines discussed are also no later than the year 2023

That’s not true, as ULTRA-Query was published on Neurips 2024 (yet to be presented!). We acknowledge that QTO was not present, and we added to our revised paper. See our global answer where we show that also the performance of QTO depends on the data leak. In fact, if we perform our stratified analysis of QTO on FB15k-237,

it provides evidence that the aggregate performance reported in the papers is essentialy due to the ~98% of queries that can be reduced to 1p (see Table 1). For the full stratified analysis please refer to table A.3 and A.4.

the proposed CQD-hybrid method is fundamentally identical to the QTO [6] proposed in ICML'23. CQD-hybrid in this paper, is not new to the community because it is practiced in QTO [6] and later followed by FIT [3]. It hardly says why these findings are essential.

We thank the reviewer for pointing out the existence of such hybrid solvers. We included it in our revision (page 8) and highlight how QTO performance is inflated (as CQD-Hybrid and all other solvers) by the current benchmarks.

We remark that , CQD-Hybrid is definitely not identical to QTO. The only point in common between the two methods is setting a score=1 to the training links. However, QTO is much more sophisticated than CQD-Hybrid, as they 1) calibrate the scores with a heuristics, 2) store a matrix $|V|\times|V|$ for each relation containing the score for every possible triples, 3) have a forward/backward mechanism in the reasoning. CQD-Hybrid only set the score for the existing triples =1, proving that a pre-trained link predictor and memorization of the training triples alone are enough to obtain SoTA performance on the old benchmarks. We hence need a new benchmark where we cannot leverage existing links to truly evaluate a model’s reasoning capabilities and advance the field of complex query answering.

Dear authors,

Thanks for your point-to-point response. I would also like to engage more in the crucial discussion and skip some wording issues here and there. To summarize, I think we have already reached an agreement on the following observation:

• The mean scores for almost all query types from existing benchmarks statistically bury the performance of full-inference query-target samples.

And also, the following two arguments:

• CQA is more than link memorization/prediction; it also includes the treatment of logical connectives and variables.
• full-inference query-target pairs performed significantly worse than the average performance.

Our major disagreement is rooted in how we understand such observations/arguments and what the implications are.

• First, it is very important to understand why full-inference query-target pairs consist of a minor part of the query. Not surprisingly, this is the direct result of the fact that missing links (valid or test triples) are only a small ratio of all links in the investigated knowledge graph splits.
  • Why are there roughly 98% percent of partial-inference query target pairs for 2p? The answer is simply because the missing links (valid+test links) comprise about 15%. Then, the probability of two links being missing could be roughly estimated as 15% * 15% = 2.25%. I think this estimation is valid since the ratio of non-reducible 2p in FB15k237 is 1.9% and 2.4% in NELL955.
  • This means the full-inference query-target pairs become the significant ONLY when the ratio of missing links grows significantly. The ratio decays of full-inference queries will be less than 1% in many settings.

If my understanding of the nature of the full-inference pair is correct, then several concerns prevent me from accepting the proposed settings as being valid.

1. Are the full-inference query-target pairs truly complex? No, they do not relate to the ``complex'' logical structure and do not align with the original goal of studying complex logical queries. Although this concept replacement makes the title, and other parts such as intro, section 6, and conclusion more eye-catching, it does not change the nature of sample manipulation. The difficulty of such query-target pairs, evident by the low MRR, is the result of selecting difficult samples from the original datasets, and the difficult sample is intuitively defined by how many edges in the queries are missing.
2. To me, the new benchmark follows another distribution in the probabilistic space of all possible query-target pairs. The new distribution is featured by all the reasoning edges being missing and, of course, has a smaller support than the previous data distribution. How small is the support of the new distribution? My previous estimation might provide some straightforward but rough intuition suggesting it is small, with a rough ratio of about $x^k$ where the $x\in[0, 1]$ is the ratio of the missing edges, $k$ is the number of the predicates in a specific query type.
3. Suggesting such a new benchmark sends readers important messages to pay more attention to this particular data distribution when optimizing their models. I am worried that the measurement from this distribution might be biased towards certain subsets of triples/entities (at least they are 10% missing triples). Then, my question is whether this new data distribution remains valid and effective in evaluating the CQA method's comprehensive capability (for logical connectives and variables). From the description in the paper and the discussion before, I cannot see the answer.
4. Should we assign more attention to such particular data distribution from a developing point of view? Also, following my understanding of the ratio of full-inference query-target pairs, my opinion is no. The reason is that the advancement of LLMs further reduces the hardness of knowledge harvesting. I conjecture that the ratio of missing links in KG will decay, so the ratio of full-inference pairs will also decay even faster.

I still acknowledge the authors' job of identifying the more difficult part in the space of query-target pairs for a given query type. Even though we separate this part of the samples from the averaging scores, it is still hard for people to select the most suitable model per query type with multiple benchmarks. Should they make decisions by averaging the one used before and the new one proposed here? If one is willing to choose a pure neural model, is it right for the model selection process to underweight the prediction of observed links?

I am looking forward to your reply.

Best

Dear authors,

I appreciate your patience and efforts in the discussion. I think this is what makes ICLR unique. With all due respect, I will try to make my response match the seriousness of yours :-).

Recap of previous discussion

In my first round of responses, and acknowledged by the follow-up feedback, we reached the following agreement.

• The full-inference query-target pairs / truly complex queries / irreducible query-answer pairs in your terminology are essentially hard samples. The reasons are (1) the concept of query reduction does not apply to neural models and (2) treating hard samples as logically more complex queries is a concept replacement. You acknowledged those two points in your response. Then, the problem becomes how you blame the statistical average.
• CQA is more than link memorization and prediction. Treatment of other logical elements (connectives and variables) is equally important.

In my second round response:

• I mention that even when you consider the hard samples and blame the statistical averaging, the ratio of hard queries is often small. Then, it is risky to construct a benchmark before we confirm whether the data is sampled from a distribution that can evaluate other logical elements with a sufficiently wide coverage (as we have already agreed on the importance of logical elements). After reading your response, you may have confused the concept of ratio with frequency. Your reasoning is that because one can get a good number of hard samples, one can say that the underlying distribution of all hard samples has a good coverage.

The response in the third round

In this round, I will first discuss the coverage of hard samples precisely. Then, I will express again why building such a benchmark with ONLY hard samples of this kind is not necessary.

The coverage of hard samples.

A knowledge graph contains the knowledge we observed, and we acknowledge there is also the knowledge that is missing. So in a knowledge graph dataset, the edges are split into two parts: the observed edges $E_{o}$ and the (artificially) missing edges $E_{m}$. In this part, we assume that the knowledge graph is given and the ratio of (artificially) missing edges is small.

For a fixed query type, say 2p, the set of all possible query-target pairs is a fixed set $S_{2p}$ and the set of all reasoning trees is also another fixed set $T_{2p}$

• Each $t\in T_{2p}$ is a 2-path. Then there are three categories for a 2-path: (I) all edges are observed; (II) part of edges are (artificially) missing, and the other edges are observed; (III) all edges are (artificially) missing. Resulting three subsets of $T_{2p}$, that is, $T_{2p,I}$, $T_{2p,II}$, and $T_{2p,III}$ of reasoning trees.
• Those subsets of reasoning trees directly relate to the query-answer pairs. And let's just use the same meaning of suffixes I, II, and III to justify the subset of query-target samples $S_{2p, I}, S_{2p, II}, S_{2p, III}$ due to its natural connection with the reasoning trees.
• Notably, one query-answer pair can be explained by multiple reasoning trees, and if I understood the paper correctly, all reasoning trees $t$ for each full-inference query-target pair $s\in S_{2p, III}$ should belong to $T_{2p, III}$.

What should we care about? For a fixed query type X, samples from $S_{X,I}$ are not evaluated in previous practice because it is already solved by an existing database system, samples from $S_{X,II}\cup S_{X,III}$ are then evaluated. And many methods solve $S_{X,II}\cup S_{X,III}$ as the goal.

When $|E_m| << |E_o|$, it is natural that $|T_{X, III}| << |T_{X, II}|$ and then $|S_{X,III}| << |S_{X,II}|$. For 2p case, $|T_{2p, III}|$ is the number of 2-paths with edge $|E_m|$ but $|T_{2p, II}|$ is the number of 2-path with one edge from $E_m$ and another from $E_o$. What the paper has found in this paper reflects these kinds of differences. This fact is not affected by how you sample the data. It is about the range of data you can sample from.

Constructing benchmarks from a distribution over $S_{X, III}$ ignores the entire $S_{X, II}$. The original manuscript argues that $S_{X,II}$ can actually be "reduced" to type III samples that belong to a simpler sub-query type $Y$. $S_{Y, III}$ is already measured, so we don't need to repeat that job in $S_{X,II}$. However, we all agree that the reduction is NOT valid, as I mentioned earlier. And as a result, the performance of logical connectives and variables on $S_{X,II}$ are NOT measured in your benchmark.

Please be aware that the discussion above holds regardless of the sampling algorithm. Your previous responses about how you sample 50k samples in $S_{X,III}$ still do not contribute to any information in $S_{X,II}$.

Why do I feel this benchmark is not necessary?

Another point you made in your feedback is that, even though only the proposed benchmark is insufficient, it is still meaningful for the readers to see the performance on a particular set of hard samples in $S_{X, III}$ in the so-called stratified analysis.

However, this suggestion is actually not necessary for the following reasons:

• The hardness of $S_{X, III}$ is caused by the generalization gap of the link prediction. Let's conduct one mental experiment where the link prediction is perfect. Then, the performance drop due to the of the link prediction is gone, which is exactly how the proposed stratified analysis is constructed. The ONLY thing that the stratified analysis can reveal is how other logical elements performed on different parts of the data $S_{X, II}$ or $S_{X, III}$, which was identified as the confounder in your previous response and is not significant in previous practice. This mental experiment suggested that one could almost diminish the gap between $S_{X,II}$ and $S_{X,III}$ queries by directly improving the link prediction.
• Then, let's consider what the practitioners could do if they see the old averaged scores and new stratified analysis. When they see the old averaged score, what they will try to improve is, as you argued, almost just link prediction. But interestingly, the improved link prediction will also close the gap between $S_{X, III}$ and $S_{X,II}$ performances. Interestingly, the problem you raised can be solved by optimizing the old benchmark, with still sufficient attention on logical elements on $S_{X, II}$. On the other hand, when they see a stratified analysis, they think we might sacrifice some performance on dumb samples in $S_{X,II}$ criticized by you, but win some new points from the hard samples in $S_{X,III}$ encouraged by you. However, this practice is actually encouraging in that the model overfits a tiny portion of datasets, which could be possibly problematic as one loses attention to logical elements that make the queries really logically complex on a broad range of data in $S_{X,II}$, as I demonstrated before.

Dear authors,

I am glad to see our discussion converge to a certain topic, indicating the debate will end soon. According to your post, I think now the frontier is about (1) Why I am saying the hardness of your hard class is caused by link prediction and can be fixed by the link predictor and (2) the "belief" about whether the ratio of missing edges in KGs is large or small.

About (1)

We fail to see the value of this mental experiment that will never be achieved and follows some "interesting" non-classical logic.

In fact, you have just simulated this mental experiment when you sample your new benchmark. You see all the missing edges in your sampling algorithm. You use the derived results as the gold answer.

This is again factually wrong, there is no concrete evidence that B and C are "almost satisfied

I don't need empirical evidence for that.

• For (B), please check the computation of QTO, and you should realize that QTO calculated graph traversal by multiplication of the adjacency matrix produced by the link predictor. (B) holds if you admit that the matrix multiplication can simulate graph traversal.
• For (C), please check the definitions of triangle norms. (C) holds if you admit that they collapse into the standard logic calculus when the input truth value is boolean.

If you don't like my wording, what would you call it if a computation process were implemented as its definition?

In fact, if it were true, then QTO, GNN-QE and CQD would perform much better for simple queries such as 2p on the new benchmarks.

On my side, I think we can blame the link predictor because the algorithm implemented by QTO/FIT follows the standard evaluation of existential queries if the adjacency matrix used by them is perfect (by link predictor is perfect, but this does not happen usually). Please check Chapter 4 in the literature [8].

Also, please explain your statement if you want to use it.

[8] Suciu, D., Olteanu, D., Ré, C., & Koch, C. (2022). Probabilistic databases. Springer Nature.

Here you can have a reason why the new benchmarks are important: you can exactly disentangle A, from B and C.

I don't understand this sentence. Please elaborate.

We see several flaws in this reasoning. You are projecting what you would like to see and achieve in a scenario that has no concrete basis to exist.

As I said before, this scenario is exactly how you produced your benchmark, which suggested one shortcut to exceed in your benchmark. It is okay if you are happier to call it unrealistic. But please also look at some related arguments.

The experimental evidence -- please re-run our experiments -- (and see also our answer to z2gA) says the opposite.

Please see my above and explain what is the reason if I can not produce the correct answer only because I had a bad adjacency matrix produced by the imprecise link predictor.

---

About (2)

We provided solid math evidence for the number of missing links being much larger on real-world KGs.

I have no intention of changing your personal beliefs because this is your free will, and I left it to the community’s judgment. I stated that the impact of the disagreement in belief would be weakened in the final score. But if you look into FB15k-237 for solid math evidence for your belief, here is my response because this is the real case I can analyze.

Let me recall your math evidence by quoting your earlier responses as follows:

Consider FB15k-237 it has 14,541 entities and 237 relation types, so potentially 50,111,441,397 triples, but we observe only 310,116 of them.

And also the following quote:

Even if you (arbitrarily) decide that 49 billion triples are meaningless somehow, there will be more missing links in the remaining 1+ billion.

Please add to it if I missed anything about your math.

You must want to distinguish two concepts: (1) the total number of possible triples. (2) the missing triples we care about, that is, the triples can be justified as true. Recall that knowledge is justified as true.

Please look at the actual data, in particular the relations, in FB15k-237 before you tried to persuade yourself with those evidences

You can look at your data or the public source I mentioned below. https://github.com/liuxiyang641/RAGAT/blob/main/data/FB15k-237/rel_cat.ipynb

Please go through every relation and ask some questions like the following examples.

• How many triples can be found for relation "/people/person/place_of_birth"? How many places of birth can one person have? Is it 14,541?
• How many triples can be found for relation "/award/award_winning_work/awards_won"? How many movie awards have been made in human history? Is it more than 1% of 14,541*14,541?

You can then see that your estimation is inflated by (1) counting triples with impossible relation types. (Can entity pair (a movie, an award) be connected by "/people/person/place_of_birth"?) (2) ignoring the fact that many relations are just sparse.

You mentioned QTO, GNN-QE and CQD first and now you are providing some ex-post explanation only for QTO. This is goalpost shifting.

I think QTO is a valid example that made my arguments clear due to my limited time. But it seems that I failed :-). But thanks for your response and for being OKAY with my justification with QTO. Then, let me express my point why CQD and GNN-QE are also satisfied.

1. For (B), the link predictor part. I say that QTO uses the adjacency matrix multiplication, and the link predictor is perfect if the adjacency matrix produced by scores is perfect, and added to that, set projection modeled by adjacency matrix multiplication. Now, you should see that the link predictor plays a crucial role with the combined (i) and (ii), which means the perfect set projection.

• Now you should look at CQD, I suppose you used CQD-beam, if you can just make your beam size larger, the argument is the same as QTO.
• If you look at GNN-QE, you should be aware that the the role of the backbone NBFNet plays the role exactly as set projection, which is made by a perfect link predictor.

2. For (C), both use triangle norm.

Furthermore, you are confusing formal reasoning with probabilistic reasoning. [...] You are confusing an adjacency matrix with a probability tensor (that is definitely non-sparse, unless you enforce constraints as in [A])

Why do the link predictor produce a dense adjacency matrix? This very accurate phrase is named by its functionality of predicting links. A formal reasoner, if it predicts links, can also be named a link predictor. I am not talking about KG embedding; please read carefully. What do you mean by a paper about KG embedding? Don't distort my words.

When a link predictor is perfect, the adjacency can be binary. I hope you can see that those two concepts (formal reasoning with probabilistic reasoning) are the same under this very circumstances, and this very discussion is also linked to the mental experiment, and also how you construct your hard dataset.

it is supporting beliefs with solid evidence.

I am very cautious with your example. Your reasoning is flawed; I can only see what you are doing is like (1) the number of total candidates is large, but that is okay. (2) Let's assume there is a constant ratio of the missing links; if 1/49 does not seem convincing enough, let's try 1/10000.

Do you think (1) and (2) is valid?

But wait, why is the ratio a constant? Have you ever thought about that critically?

---

This is a friendly reminder. In your revised manuscript, the equation (1) about the definition of MRR is wrong; it seems to be a mean rank. :-)

Dear reviewers,

We uploaded a new version of the paper, where we completed all the experiments:

Negation queries: We run the full analysis for all negation queries, confirming that even by just looking at the positive reasoning tree, the vast majority of query-answer pairs contain existing links thus pointing at the same issues we already analyzed for positive-only queries in the paper. We report these values in Table A.1 in Appendix A.1.

QTO on old benchmarks: The additional experiments on the old benchmarks with QTO, table A.3, A.4, confirm that QTO aggregated performance is due to 1p queries and it drops for the portion of full-inference query-answer pairs, as any other solver. 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 query-answer pairs only, showing that improving performance on the partial-inference query-answer pairs does not necessarily result in improvements over the full-inference ones.

QTO on new benchmarks: We completed the experiments for QTO on the new benchmarks, see Table 5. The experiments show that QTO have similar performance with CQD, a much simpler and older baseline, enforcing our claim for which the perception of progress in the field has been inflated due to the presence of a massive amount of partial-inference query-answer pairs in the old benchmarks.