Is Complex Query Answering Really Complex?

We thank the reviewer for considering our paper a piece of beautiful work and considering our experiment design easy to understand. We proceed by answering their questions.

authors do not explain at methodological level why these SOTA CQA systems fail for complex queries.

In Table 2 we showed that the performance of all SoTA methods consistently increased for QA pairs that have a higher number of existing links in their reasoning tree. This is evidence that most ''good'' performance of CQA can be explained by their memorization ability. We conclude that all methods lose performance in the new benchmarks because they overly rely on memorized facts, limiting their ability to predict answers when there are many missing links in their reasoning tree. We will add this conclusion explicitly in the camera-ready.

If we make a decision by tossing a coin, we will have 50% of accuracy. But, we do not believe we are doing logical reasoning. Should there be a minimum value of accuracy, below which we shall not call a system is doing logical reasoning (here logical query)?

We see where the reviewer is leading, but for CQA, even if query answering under missing links is described using logical operators, the results it produces are derived in a mixed deductive-inductive process that returns a ranking of answer entities (measured by MRR) rather than a set of logical conclusions (which are usually meant to be derived by deduction and whose correctness might be measured in terms of accuracy). Additionally, since knowledge graphs contain thousands of entities, a randomly selected ranking would result in an MRR close to zero. Hence, it is less informative to set a hard MRR threshold to determine whether a model can be considered capable of reasoning.

We thank the reviewer for providing a precise summary of the paper and for considering our analysis rigorous. We proceed by answering their questions, believing all can be easily addressed.

no discussion of whether the new distributions reflect real-world query patterns (e.g., frequency of 4p/4i queries)

There is no ground truth to compare the frequency of query patterns in the new benchmarks nor in the old benchmarks to reflect a particular real-world application. We highlight that there is no indication that the overrepresented frequency of 1p reductions (see Table 1) in the old benchmarks is representative, and it skews the perception of progress.

Limited comparison to other hybrid methods (e.g., FIT)

As we argue in Section 5 (lines 323-325, left column), and as stated in the FIT paper (Appendix G.2 and Table 5 of FIT), the FIT method works like QTO on the query types that we consider in our evaluations. Therefore, we do not include an evaluation of FIT.

BetaE not discussed in negation analysis.

We chose a baseline method for each relevant SoTA category. Concerning geometric embeddings (e.g., BetaE, Query2Box, ConE), we selected ConE as an established baseline that can handle negation, and it was shown to outperform BetaE.

no explicit theoretical claims. The reasoning tree formalism (Sec. 3) is intuitive but lacks formal proofs

In Sec 3, we introduce the concept of “reasoning tree” in the running text to syntactically delineate trivial, inference-based, partial-inference and full-inference QA pairs. We do not make formal claims in Section 3 that could be proven. In line 210, we should rather say “We hypothesize…” (rather than “We claim…”), and this hypothesis is later empirically validated, but we do not see any way how it could be proven formally since the hardness that we refer to is the effectiveness of making correct predictions (and not a soundness or algorithmic complexity statement).

Missing statistical significance tests for performance differences

By running a Mann-Whitney paired U test, we obtain low p-values in the reciprocal rank distribution of answers between models, confirming that our claims remain unchanged from those reported in our tables. For example, when executing the test for the reciprocal ranks of 2p QA pairs computed with CQD and CQD-hybrid we obtain p-value of 1.5e-4. We will include the full results in the camera-ready.

Removing non-existing links (Table 3) is valid but lacks details on filtering criteria

We filter out all query-answer pairs that contain non-existing links in their reasoning tree. For example, for 2u QA pairs, if either one of the two links in the reasoning tree does not exist in the graph, we remove the QA pair. (see Figure A.1 (Bottom) for an example). It follows that only QA pairs where both links in the reasoning tree exist in the graph are retained (see Figure A.1 (Top) for an example). We will include this description in the camera-ready.

The negation analysis (Table A.1) strengthens the main claims but lacks visual examples.

The visual example would be similar to the example we provided in Figure 1, and that’s the reason we did not include one. Is there a specific reason why the reviewer thinks there should be one? We can effortlessly add one in the camera ready.

We believe the main concerns of the reviewer can be fully addressed, as discussed in the comments below. We hope the score can be raised.

The authors “balance each query type a QA pair can be reduced to”, which is confusing to me,

We acknowledge that the usage of the term ''balance'' can lead to misunderstandings. We should rather say, ``We compile the benchmark such that all query types (e.g., 3p) a QA pair can be reduced to (e.g., 1p, 2p, and 3p) appear with the same frequency in it’’. We will clarify this in the camera-ready.

why is this a necessary choice? And how the balancing coefficient would affect the final results?

This is necessary because sub-types reductions in the old benchmark are not equally represented, while 1p reductions are greatly over-represented (see Table 1). As you can see in Fig. 3, by compiling the benchmark such that all query types a QA pair can be reduced to appear with the same frequency in the benchmark, the overall results significantly decrease. An explanation for this phenomenon is that in the new benchmarks, we evaluate the full spectrum of hardness rather than the easiest QA pairs (i.e., the ones reducible to 1p).

from well-established methods like Query2Box and BetaE and more recent strong baselines like LMPNN and CLMPT.

Over the last years dozens of methods for CQA have been released, and it’s highly impractical to evaluate and compare all of them. For such a reason, we have selected a method for each category. For geometric embedding methods, we selected ConE, as it is an established baseline that can handle negation and has outperformed, e.g., BetaE, and Query2Box. For methods based on GNN, we chose GNN-QE, as it provides competitive performance compared to LMPNN and CLMPT on NELL995, but outperforms them on FB15k-237. That said, we also ran additional experiments on the new benchmarks with CLMPT, being the most recent baseline among the three, and our preliminary results confirm that our claims remain unchanged. In fact, similarly to the other baselines, CLMPT's performance drops on the new benchmark, but it remains competitive. For instance, below is the MRR comparison of CLMPT and the best-reported baseline for 2p, 3p, 2i, and 3i queries on FB15k-237+H:

We will report the full results in the camera-ready.

This work can benefit from discussing more related works

We will extend App. C to include the methods pointed out by the reviewer in the SoTA discussion.

It would be great if the results of queries with negation can be included in the main content. Specific reason to exclude the results and discussions on negation queries in the main content?

We agree with the reviewer, we will use the additional page in the camera-ready to include results on negative queries in the main paper. We did not do it now just for space constraints.

A lot of CQA methods use the data splits in the BetaE data, where the training data may also have the same query reduction problem.

Please note that we have not changed the data splits, rather we have changed the way the benchmark is created (see Sec 6, and App G). Also note that the query reduction problem can only occur at valid/test time, as it happens when certain training data makes the prediction of a QA pair easier, effectively reducing the QA pair to a simpler type (see Fig. 1).

Is the new benchmark really harder and more suitable for evaluating CQA methods, or is it out of the training data distribution and thus not that convincing to be used for evaluation?

We remark that we only change the way the benchmark is created to ensure that the distribution is not skewed towards the easiest QA pairs. Moreover, apart from 4p and 4i queries, we keep the same query structures used in the old benchmarks. Then, following [1], we could consider the query types not included in the training, i.e, ip,pi,2u,up, as well as 4p and 4i to be OOD, while considering the rest of the query types in-distribution. We also remark that there is no ground truth to compare the frequency of query patterns in the new benchmarks nor in the old benchmarks to reflect a particular real-world application. We highlight that there is no indication that the overrepresented frequency of 1p reductions (see Table 1) in the old benchmarks is representative and it skews the perception of progress.

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