${\rm EFO}_k$-CQA: Towards Knowledge Graph Complex Query Answering beyond Set Operation

Thank you for your kind feedback. We are honored by your approval of the completeness of our dataset.. We firmly believe that our proposed dataset will contribute to the advancement and development of new models in this field and here is our rebuttal:

The authors discussed some theoretical properties of EFO(k) queries, but did not provide enough insights on how to design a CQA model for the new types of queries that satisfy these properties. It would significantly increase the impact of the paper if the authors could explictly include such a section.

We would like to express our gratitude for your helpful reminder regarding the details of extending previous models to answer queries beyond tree structures. In fact, we believe this is a general direction in the database community, and we have noted very recent research trying to filling this gap[1], we will provide this discussion in our paper. Actually, our work provides some general extension of the previous model like ConE which can only deal with tree-form query initially. And we show that more general methods like LMPNN suffers from the biased selection of training data severely. However, we have not designed any new methods since this is a dataset and benchmark paper, and we strive to test the generalizability of existing methods, providing corresponding discussion. We will leave the more sophisticated design of CQA models in the future but we will surely include more discussions of it thanks to your advice.

It is not clear how the previous model like BetaE/LogicE/ConE etc. are extended to handle cyclic and multigraph queries. These models are known to be able to only handle tree-form queries, as far as I know.

Thank you for your correct observation, surely these models are known to be able to only handle tree-form queries. In fact, this extension is done by us while ensuring the backward compatibility, this is explained in the Section 4.4 and detailed in Appendix F, and we consider this as one of our contribution of our paper.

[1] Barceló, Pablo, et al. "A neuro-symbolic framework for answering conjunctive queries." arXiv preprint arXiv:2310.04598 (2023).

Thank you for your valuable feedback, which provides a new perspective from the NLP community. However, we believe there are some misunderstandings about the contribution and importance of the task of complex query answering and our work that we would like to clarify.

Dataset of query graphs with Answer Sets built from Query graph sampling - It is not validated whether these produce meaningful query graphs when grounded to real-concepts….

There seem to be several key limitations - How does this help with improving Complex questions answering of natural question datasets e.g. WebQSP, Complex WebQSP..…

We would like to answer these two questions together, as they seem to make the same presumption that query in formal language (first order logic) is only practical when it can be found in natural language, and the task of complex query answering (CQA) is therefore subordinate to natural language task like Knowledge Graph Question Answering (KGQA). However, this is not the case. We would like to refer you to the first question in our general feedback for the discussion where we refute this presumption and we do not reiterate the context here.

In short, the introduction of complicated queries, such as multi-variable queries, even though hard to find in natural language, is crucial for advancing the development of CQA in the sense of strengthening/benchmarking the combinatorial generalizability, which greatly differs from KGQA which is conducted in natural language.

I am not clear about how the learning-based methods are relevant here…And this still does not connect to the complex natural question KGQA methods to produce answers for natural questions from the KG….

We thank you for your questions. In fact, there have been many previous learning-base methods that focus on complex query answering, and one of our core contributions of this paper, is to benchmark the generalizability, how well they can handle query with different graph features, like different topology properties that may have not been considered during their model design. Regarding the connection to KGQA, we believe this question are addressed above.

Approach presentation and clarity - The whole Framework section (4.1-4.4) in the main paper is limited,..not presented well enough to grasp the key points … Regarding the issue of presentation, we would like to hear actionable suggestions about the context, both in the main paper and the appendix. Our goal is to explain the intuitive and brief idea in the main paper and provide enough details in the appendix. For example, in the main paper, we provide Figure 3, where each component in the framework section (4.1-4.4) is clearly illustrated, which can grasp the key point of our framework. In the appendix, we offer additional illustrations in Figure 5, together with the writing in Appendix D.1 and Section 4.1, clearly explains how to enumerate all possible abstract query graphs. Similarly, Appendix F is for Section 4.4 where we provide with the pseudo-code here. We will certainly strive to improve the presentation of our paper, but we would like to hear more actionable suggestions.

This paper is derivative…..

Regarding this issue, we would like to refer you to the second question in our general rebuttal. Here, we add some brief additional comments.

It extends to only 2 free variables in practice (and the extension to multiple free variables, over their prior work Yin et al 2023 seems trivial?).

As discussed in the general rebuttal, the extension from 1 free variable to 2 is fundramental, while 2 to k is derivative instead.

The two assumptions they define are extraneous as they themselves suggest this cannot be checked in practice.

This is a very ** clear misunderstandings**. As we state in Section 3.1, Assumption 13 and 14 apply to abstract query graph because putting these assumptions to grounded query graph should be avoided in practice. Therefore, we strictly abide by these two assumptions we put forward in practice.

We include the whole family of EFO1 query, many of them can not be represented by operator tree. This is based on prior work directly, so it's not a contribution of this paper.

However, no previous work has discussed how to enumerate the whole family of EFO1 query. Those assumptions in Section 3.1 and 3.2, help us greatly when exploring the combinatorial space and has never been discussed to the best of our knowledge.

The heuristics to sample and ground the dataset are not obvious, clear, or validated, or effectively presented.

If your concern is about the natural language, it has been addressed above. If you concern is about our presentation, we would like to hear more detailed suggestions as we have also discussed above.

Thank you for your valuable feedback. We highly value your expertise in logic and databases, and will improve our paper, including more rigorous definitions, correcting typos in presentation, and citing related previous research according to your suggestions. However, there are also some misunderstandings we would like to clarify:

Definition 4: Consider the formula…. This may seem like a minor point, but the correct definition of this notion is necessary when considering a logic with a bounded number of variables, which is a standard way to construct fragments of first-order logic with tractable query evaluation.

We appreciate your suggestions. We presume that all variables are named differently as it is the standard way in first order logic without clear explanation. We have corrected this point to make our discussion more clear.

Paragraph after Definition 9: The authors claim the following: "... the inference of existential formulas is easier than solving CSP instances since the existential variables do not need to be kept track of". I do not understand this claim, as the complexity of CSP solving and conjunctive query evaluation is the same (both problems are NP-complete).

Your understanding is right and both solving CSP and conjunctive query evaluation are NP-complete. However, our claim is about the polynomial time reduction itself. Moreover, this polynomial reduction is very powerful in a smaller n (<10) like in our cases. In practice, our inference techniques are 100 times faster than CSP solvers. Certainly, both problems are NP-complete and it doesn’t conflict.

Definition 7: What does it mean that " is True"? Where is this query evaluated? Do you assume a fixed knowledge graph over which all queries are evaluated?

Definition 7: How is the semantics of negation defined under OWA? Do you consider a certain answer semantics over some possible worlds (otherwise no negative atoms can be inferred)? The authors use the term " is True" without defining it.

Thank you for your suggestions, since our semantics is standard and it is a common practice[1] to state in a intuitive way, we didn’t give a rigorous definition of the semantics of the query. Regarding the evaluation and OWA, the underlying knowledge graph KG is taken as ground truth to evaluate the query. Regarding the negation, any unobserved triple is considered negated. We will include this part of definition in the preliminary.

Definition 12: For an abstract query graph G, a grounding is a function I that maps G into a query graph. Do you impose any restrictions on this mapping?.....

We are extremely sorry for this typo, causing confusion in the reading, as stated in the answer regarding Definition 4, we need to assume all nodes in the abstract query graph G should be named differently. We have corrected this typo thanks to your advice.

Paragraph after Assumption 15: The authors mention the following "Assumption 15 treats negation separately because of the fact that for any KG, any relation r in R, there is |{ (h,t) | h,t in E, (h,r,t) in KG}| << E^2"..... Sorry for this Typo, it should be |\mathcal{E}|^2, we have corrected it and thank you for your observation.

In fact, the authors have made a contribution by lifting the restriction that conjunctive queries must be tree-shaped and by considering an approach to generate general graph-shaped queries. ….Most notably, the authors could have considered the notions of treewidth and hypertree width…

We really appreciate your suggestion. It is really important and necessary to include more parameters like treewidth and is also a common practice in the discussion of traditional database/CSP communities. However, we want to point out that we have made the assumption in Section 5, the footnote on the 8th page that the number of edge of query graph is no more than the number of nodes, therefore, the treewidth is either 2 or 1, making it pointless for discussion. We will leave this to future work to include even more complicated query graph.

Why do you need to develop your own algorithm to compute the answers to an existential formula, as described in Section 4.3? Why can't you leverage the substantial body of work and existing implementations for answering first-order queries?

Thank you for your suggestions. Firstly, our implementation is consistent with existing implementations and we have already double-checked its correctness. Additionally, we will cite more existing work for clarification and we reckon that our own algorithm in Section 4.3 was not a theoretical innovation but rather a convenient implementation that fits into our framework well.

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

Thank you for your valuable feedback. However, we believe there are some misunderstandings about the contribution and importance of the task of complex query answering and our work that we would like to clarify.

benchmark does not include ways of generating new data.

Thank you for your questions. However, we have produced many new queries with novel query types including both single variable and multi variables. To the best of our knowledge, we surpass all previous work regarding the query types we investigated and the process of sampling data is totally novel.

no concern over which queries are more practical than others, results may be altered by queries that would be

We thank you for your concerns, however, it seems that you presume query in formal language (first order logic) is only practical when it can be found in natural language. However, this is not the case. We refer you to the first question in our general feedback for the discussion where we refute this presumption. In short, the input of CQA models is in formal language rather than neutral language, and the CQA models aim to be trained on selected query types and combinatorially generalize to unseen complex patterns in first-order logic[1]. In this way, the study of combinatorial generalizability of the CQA models plays a pivotal role in the task of representation learning[2]. Therefore, the introduction of those complicated queries that can hardly be found in natural language has its own merit: benchmarking the combinatorial generalizability of the CQA models.

limited impact: I consider this as an add on to complement work by Ren et al.

We thank you for your concerns, however, our dataset is a huge extension to the work of Ren[1]. We would like to refer you to the second question in our general feedback. In short, we already explained in the introduction that existing dataset in complex query answering is severely inadequate, because their construction is biased and has not discussed queries with some patterns entirely: multigraph, cyclic graph, multiple free variables, resulting in lack of both combinatorial answers and structural hardness. This huge extension was also mentioned in Section 3.2 and detailed in Appendix D.3, where we provide Figure 6, clearly illustrating how huge our extension is. We welcome you to check that.

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

[2] Bai, Jiaxin, et al. ‘Sequential Query Encoding for Complex Query Answering on Knowledge Graphs’. Transactions on Machine Learning Research, 2023, https://openreview.net/forum?id=ERqGqZzSu5.