A neuro-symbolic framework for answering conjunctive queries

Thank you for you review and feedback. We address your concerns below.

Contribution (C1) is not directly related to the field of Machine Learning; the results it claims are strictly within the domain of database theory...

Please note that we are not claiming the notion of tree-like approximation itself as a contribution, and we mention it has been studied before in the second paragraph of Section 2. We agree with the reviewer that unravelings are common in the literature and that the completeness claim is straightforward. The optimality claim is less straightforward, but it is not difficult. We are not aware of any optimality result of this kind (to the best of our knowledge, similar previous results deal with treewidth-1 queries, as mentioned in Section 2). If the reviewer has a concrete reference showing a similar result, we are happy to add it to the paper. Also, we are happy to improve the wording so it is clear to the reader that we are not claiming the notion of tree-like approximation as a contribution.

The contribution, as explained in the paper, is the use of tree-like approximations of conjunctive queries in the context of Machine Learning, to obtain neuro-symbolic models that can handle cyclic conjunctive queries. We stress that handling cyclic queries has been identified as an open problem in the literature (Ren et al 2023).

The significance of (C1) in the context of the current machine learning-based query answering state-of-the-art is also not evident to me. As the authors have mentioned, existing approaches are unable to handle arbitrary monadic tree-shaped conjunctive queries (CQs) without the requirement of query anchoring...

We are not claiming (C1) as a contribution, see our previous answer. As far as we can see, it is not clear how to define a notion of tree-like approximations that can be handled directly by current methods and that enjoys strong theoretical guarantees (e.g. completeness, optimality). On the other hand, we believe that the fact that current methods need to be adapted to use tree-like approximations, does not make our contribution less significant.

...it is unclear in what manner it enables the technique by Zhu et al to "support" arbitrary tree shaped CQs.

We describe this in the 3rd paragraph of Section 4.3. The idea is that GNN-QE (Zhu et al) is a method that allows one to encompass existential quantification in the latent space as a full unitary vector (in other more complex methods one would probably have to devise a more clever encoding scheme to allow for unanchored queries). We would appreciate any concrete suggestions for improving the presentation.

I also found the experimental results somewhat perplexing. Specifically, in the comparison between GNN-QE and its extension, \exists GNN-QE, applied to anchored queries, both systems are trained on distinct datasets; the significance of the reported results remains unclear to me... Adding to the confusion, the experiments appear to include results for queries that may not strictly adhere to conjunctive queries (CQs) and may incorporate other first-order constructs, including negation. To the best of my knowledge, the results presented in the core technical sections of the paper are confined to CQs (and indeed, the seminal result by Chandra and Merlin only applies to CQs). Questions: Please clarify the applicability of your results to queries involving disjunction and negation.

Both GNN-QE and \exists GNN-QE are trained on the same knowledge graphs, but different set of queries: GNN-QE is trained on tree-like anchored queries and \exists GNN-QE is trained on tree-like queries (with and without anchors). In other words, the training\validation set of GNN-QE is a proper subset of the training\validation set of \exists GNN-QE. Experiments show that training on unanchored tree-like queries improves the performance of the model in such queries without compromising its original objective (anchored tree-like queries): \exists GNN-QE achieves competitive results in both anchored and unanchored tree-like queries.

Regarding negation, our approximation scheme is indeed devised only for CQs, but GNN-QE and \exists GNN-QE are architectures capable of answering arbitrary anchored and arbitrary tree-like queries, which may include union and negation. Hence we include two different type of tests: we compare GNN-QE and \exists GNN-QE in terms of their ability to answer tree-like queries, and then test how \exists GNN-QE handles (cyclic) CQs via our approximation scheme.

Please clarify whether methods other than that by Zhu et al. can be easily extended to support CQs.

We agree with the reviewer. It is not clear how to adapt other methods to handle existential variables. This is why in this paper we focus on GNN-QE which naturally admits this extension. We believe that trying to adapt other methods (or propose new methods) that handle existential variables is an interesting question for future research.

We regret that the reviewer finds the presentation poor and we will do our utmost best to improve the presentation. Any specific suggestions by the reviewer as to where things can be improved would be appreciated.

The motivation and the research question are not clear.

Motivation: Current state of the art only supports tree-like queries, how to use this to deal with more complex queries? Answer: tree-like approximations. Research question: What are such approximations and how do these work in practice? We answer both questions in the paper.

The experiment results are not always better than the based-line.

Unfortunately we were not able to fully reproduce results from the original GNN-QE paper due to hardware limitations.

In the case of anchored tree-like queries, on our implementation and training, results are closer, while still being slightly better in the original GNN-QE. We believe that this might be a result of the way we created unanchored queries.

In the case of unanchored tree-like queries, the results are almost always better for \exists GNN-QE, and in the cases where GNN-QE is better the difference is very small.

But, only experiments on benchmark datasets FB15K, FB15k-237 are not sufficient to support authors' second and third contribution claims.

We also report on NELL in the supplementary material as mentioned in the paper. This is precisely the same experimental setup presented in the original GNN-QE paper and other previous models such as Q2B, betaE and conE.

Questions: Why shall we be interested in the research of answering arbitrary conjunctive queries over incomplete knowledge graphs?

Knowledge bases, and graph databases in general, are one of the most important trends in data management, with dozens of engines available, large public graphs such as Wikidata, and interest fro big companies such as Apache, Google or Amazon.

Answering conjunctive queries in knowledge graphs is important because they serve as the building block of most knowledge graph query languages (see e.g. Hogan, et al. "Knowledge graphs." ACM Computing Surveys 2021). Conjunctive queries are also important outside knowledge graphs, as they serve as a formalization of SELECT FROM WHERE statements in SQL.

Finally, since knowledge graphs are commonly used to capture information, one can rarely assume knowledge graphs are complete. The most prominent example is Wikidata, serving as the knowledge graph of Wikipedia: since the aim of Wikipedia is to capture all information known to the human world, in practice we will never have a complete version of it. Hence, link prediction is important in knowledge graphs, and so is being able to answer queries (specially conjunctive queries) in the presence of missing links.

Would this method also work for complete knowledge graphs?

The model does not incorporate a way of letting it know the input graph is complete, so even if the graph is complete, it will continue trying to predict the most likely links, and using them to answer queries. However, in training we will see all relations present in the graph, so the error should be minimal. Although knowledge graphs in practice, as we mention, are usually incomplete, if, theoretically speaking, we find a complete knowledge graph, it will be more efficient to use the standard database machinery developed for complete knowledge graphs, as it is specifically designed for this scenario.

What is the intuition behind the idea of "approximating a cyclic query by an infinite family of tree-like queries"?

The idea is to have tree-like queries that approximate the original query in the sense that their answer sets are close, independently of the underlying knowledge graph. As we take better approximations in the family we expect their answer sets to be closer to the answer set of the original query.

What if a relation is self-reflective?

Our approach is oblivious to the fact that a knowledge graph relation may be self-reflective. If you mean the presence of self-loops in the conjunctive queries, these are considered as cycles. Our approximation approach still applies in the presence of self-loops.

What do you mean by "neuro-symbolic framework"?

We mean methods that work with neural architectures, but in which we introduce a specific bias, obliging that the query processing algorithm uses the symbolic information in how the query is written in a formal query language.

Thank you for your comments. We address your questions below:

Weaknesses: One apparent weakness seems to be the addition of yet another hyper-parameter which determines the depth of the tree to which the cyclic logical query is unraveled.

We agree, and this is the reason we did an empirical fitting of the depth. Experiments show that a good depth is when the root of the unraveling appears again in the query.

The proposed approach seems to achieve a lower performance compared to the baseline when evaluated on anchored tree-like queries Questions: Do you have any intuition as to why the proposed approach seems to perform worse, on average, compared to the baseline on anchored tree-like queries?

Our proposed approach does indeed perform worse on anchored tree-like queries if we look at the MRR. Unfortunately we were not able to fully reproduce results from the original GNN-QE paper due to hardware limitations. In our trained GNN-QE the results are closer, while still being slightly better than the /exists GNN-QE.

We believe that this might be due to the way we created unanchored queries: we took the anchored ones and randomly removed anchors, this might have added some unwanted noise in the training and validation dataset and worsen the performance on anchored queries.

We must emphasize: the benefit we obtain for paying this slight price in performance for anchored queries is noticeable: we can now answer unanchored queries with a similar performance, which, in turns, allows for approximating cyclic queries. We feel it is a small price to pay for all we obtain.

In the experimental setup you mentioned that you "additionally provide a new set of training, validation and test queries...". Is this in addition to the unanchored set originally in the dataset? I was under the impression that your method could only handle unanchored queries?

Our method can handle both anchored or unanchored queries. The original datasets don't include unanchored queries, because previous approaches cannot handle them. We build a set of unanchored queries by randomly removing anchors from the original query sets.

Thank you for your comments. We address your concerns below:

There are many concepts introduced in the paper that are already discussed in inductive logic programming literature. See for instance the definition of containment and homomorphism that are known as substitution in logic programming. There is a lack of discussion of the related concepts and results...

The notions of containment and homomorphism are ubiquitous in computer science and can be considered as basic notions. For example, they are common in database theory, logic and inductive logic. We are just using them here. We note that substitutions somewhat serve a different purpose as it allows us to replace say variables with subexpressions. We are not sure why the reviewer sees the inclusion of these definitions as a weakness. Perhaps the reviewer can comment on this?

Furthermore, it should be interesting to introduce in the paper the notion of open world assumption that is not discussed.

We are working on incomplete knowledge graphs, which are by definition open world. Perhaps the reviewer can clarify the comment?

Please note that the completeness property introduced in the paper corresponds to the notion of clause substitution introduced many years ago in the logic programming literature. The homomorphism introduced in the paper is already called substitution (see for instance [1]).

Again, we are not introducing the notions of containment nor homomorphism, but simply using them. These are standard notions in computer science. The connection between containment and homomorphisms is very old and well-known in database theory as we cite in Proposition 3.1.

Finally, the experimental evaluation should be extended to include other approaches.

We would appreciate it if the reviewer could at least mention one alternative approach for answering cyclic conjunctive queries using state-of-the-art neural symbolic approaches. We are not aware of any other work (see also survey Ren et al. 2023).

Questions: Stress the contribution and the experimental results

The contributions are clearly presented in the paper (see section “More specifically, our contributions are as follows.” in the Introduction on page 2). More precisely:

• We propose an approximation scheme for complex conjunctive queries using tree-like queries. Moreover, the approximation scheme comes with theoretical guarantees: It is complete in the sense that no false negative query answers are produced. It is optimal in that we provide the best possible approximation using tree-like queries.

• The approximation scheme is adaptive in the sense that it is parameterized by the notion of depth of tree-like queries. For any depth, an approximation exists and higher depth queries potentially provide better approximations. The choice of depth can be tuned depending on available resources, queries and data at hand.

• Our approach is generic and can be used in combination with any neuro-symbolic query processor, provided that unanchored tree-like queries are supported. Figure 1b depicts an unanchored tree-like query in which the input node w is variable. As an independent contribution, we show how to go from anchored to (unanchored) tree-like queries in some neurosymbolic methods.

• We implemented our approach on top of the GNN-QE implementation by Zhu et al. (2022). Results show our techniques are a viable strategy for answering cyclic queries, and that our improvements can be carried over with little cost over this standard neuro-symbolic architecture.

Then in the experiments (Section 5) we describe that our experiments answer the following questions:

(Q1) What is the effect on the performance of answering anchored tree-like queries when the training set includes unanchored tree-like queries as well?

(Q2) Similarly, what is the effect on the performance of answering general tree-like queries? Looking ahead, as a contribution of independent interest, our results indicate that we can support general tree like queries (Q2) with little or no negative impact for both anchored tree-like queries (Q1). This gives us ground to suggest that general tree-like queries should become default members in training and testing sets of future neuro-symbolic architectures. Our third question relates to our approximation scheme.

(Q3) What is the performance of our approximation scheme in answering cyclic queries? And related, how does this depend on the chosen depth of the unraveling?

These list are taken verbatim from the paper. Could the reviewer be more specific in which contributions and experimental results are not stressed in the paper?

Thank you for your feedback. We would like to answer to some of your comments below, and also ask for some clarification on your observations.

This paper is trying to apply a technique that works for the certainty case to reasoning under uncertainty... it is assuming that the probability of a disjunction is like the maximum probability of its components.

We are not assuming the probability of a disjunction is the maximum probability of its components. Perhaps the reviewer can point us to the place in the paper causing the confusion?

Consider the cyclic CQ of Figure 1 (c): as the number of friends of someone goes to infinity, the probability that two of them are coworkers should approach 1---

We are at a loss with the comment on the infinite number of friends. Perhaps the reviewer can clarify the comment?

You need to convince us that the sort of queries you can handle is a useful class. Can it answer all queries on knowledge graphs...?. E.g., this seems to include many fewer queries than could be made with say Problog...

The class of conjunctive queries (CQs) is one of the most fundamental query classes for structured data, and in particular, for knowledge graphs. As we discuss in the Introduction of the paper, previous machine learning methods can only handle a fragment of the class of CQs (tree-like queries). Here we propose a method for arbitrary CQs (not only tree-like), which has been identified as an important open problem in the literature (Ren et al. 2023). Note that the only restriction is having one target variable which is a common restriction in the literature due to scalability reasons.

The notion of valid paths is used to formalize the notion of unravelings. It has nothing to do with the expressiveness of the class of queries we are considering. We believe that the reviewer may have misunderstood the intention of valid paths.

We also stress that we are following an active line of research on query answering over incomplete knowledge graphs via machine learning models (the topic of this conference). We do not want to apply symbolic methods (such as Problog) as they tackle different use cases: we see purely symbolic methods as a way of obtaining reliable answers, at a greater cost, while neural approaches provide faster approximations.

Page 3 "y and z are both existentially quantified" isn't true as it stands. They are universally quantified at the scope of the rule, and existentially quantified in the scope of the body.

This is not correct. The query is a conjunctive query. The output variable is x and the variables y and z are existentially quantified by definition of the query.

I don't understand why "the number of approximations is infinite"...

The number of approximations is infinite simply by definition, as we can choose arbitrary depths for the unravelings. As explained in the first paragraph of Section 4.1, the approximations are independent of the underlying knowledge graph.

Surely, you can check for loops which would make it finite. However I suspect it is exponential in path length, so that is probably moot. Please give us the complexity.

We do not know what the reviewer means here. Perhaps the reviewer can clarify the comment?

What is the mean reciprocal rank of a set? How do you rank sets?

This is a standard measure applied in previous work. We compare the set of answers with the log-odds reported by the final layer of the architecture for each node, so that higher odds represent a higher “likelihood”. The mean reciprocal rank reported in the paper is the mean of the reciprocal rank for each query type. Hence, a higher mean reciprocal rank indicates that most probable answers are reported first by the algorithm.

If there are multiple witnesses for one x (e.g, multiple instances of y and z for a single x), how do you choose which one is the ground > truth? What is the ground truth?

The ground truth consists of the set of all nodes that are witnesses for x in any answer of the query.

What is "the Spearman correlation rank between the total number of answers...."? Spearman rank correlation measures differences between ranks. Why is it appropriate for the total number of answers?

The measure is between the model cardinality prediction (keeping entities with score over 0.5) and the number of ground truth answers as in GNN-QE or other previous work (betaE, conE).

The MRRs for FB15k-237 seem particularly low. ... the Spearman rank correlation seems particularly high. Can you explain these results?

Indeed, this also happens in previous work such as [q2b, betaE] and also in the original GNN-QE. The MRR is suggesting that the first right answer appears, on average, in positions 10-11 for unanchored queries, and it varies between 2 and 11 for anchored ones. The spearman’s rank correlation indicates that queries with more ground truth answers, also get a larger number of predicted answers, compared to other queries.