Abductive Logical Reasoning on Knowledge Graphs

Thank you for taking the time to review our work. We appreciate your feedback and would like to respond to your comments and questions.

Re W1:

In our formulation of abductive reasoning on knowledge graphs, given a grounded observation such as Q(1), the goal is the find a hypothesis P(x) such that the set {x | P(x) holds true} closely resembles the set 1. This means that P(1) = True.

To provide a clearer understanding, we will compare our abductive logical expression generation with inductive rule mining on knowledge graphs:

Rule Mining (ILP on KG):

This task involves a given knowledge graph with some positive examples regarding the relation $speak$. The goal is to find Horn clause rules associated with the $speak$ relation.

$speaks(X, Y) \\leftarrow lives(X, A) \\land language(A, Y)$

The variables in the rules are universally quantified, and the quality of the rules is measured by head coverage and precision.

Our task:

We use a real example from FB15K-237. Our observations include the following entities:

$Grant Heslov, Jason Segel, Robert Towne, Ronald Bass, Rashida Jones$

Our task aims to find a logical expression based on the KG to describe these entities, rather than discovering general rules over the KG. These entities make the following logical expressions true:

$V_?: Occupation(V_?, Actor) \\land Occupation(V_?, Screen Writer) \\land BornIn(V_?, Los Angeles)$

This means that Grant Heslov, Jason Segel, Robert Towne, Ronald Bass, and Rashida Jones are actors and screenwriters born in Los Angeles. This logical expression is not a rule, as not all entities from the KG satisfy the logical expression.

Unlike inductive rule mining, which is not grounded, our proposed reasoning task is grounded, focusing on specific entities.

Re W2:

We have updated the description of our proposed method, RLF-KG, in Section 3 to improve clarity. The entire process is divided into three steps.

Step 1 involves preparing the training samples and converting the raw data into a format that is suitable for a transformer-based model.

In Step 2, a generative model is trained in a supervised manner. It is important to note that the resulting model from Step 2 is standalone and can be used to generate hypotheses given observations, although its performance may be relatively low.

The primary contribution of our method is Step 3, which fine-tunes the trained model via PPO with feedback from the training KG. This step is critical in improving the model's ability to reason over the KG and generate more accurate and complex hypotheses. In regard to the "model" and "reference model," both are initialized to be the trained model resulting from Step 2 (which we refer to as the "original model"). During Step 3, the "model" is optimized, while the "reference model" remains fixed. The "reference model" is used in the PPO process to prevent excessive divergence between the fine-tuned "model" and the "original model." The "reference model" is crucial in ensuring that the fine-tuned "model" produces syntactically correct hypotheses similar to the "original model." Without limiting divergence, the training process may become difficult to converge. Our quantitative experiments (presented in Table 3, Sec. 4.4) demonstrated the effectiveness of Step 3, namely RLF-KG. Figure 6 illustrates the growth in reward during the PPO process, further supporting the effectiveness of our proposed method.

In addition to the quantitative results, we provide qualitative examples in Appendix G to showcase the improvement in the generated hypotheses for the same observation. These examples illustrate how RLF-KG improves the model's ability to reason over the KG and generate more accurate and complex hypotheses.

Re W3:

In line with previous works on KG reasoning [1][2], we utilize similar hypothesis templates as those used in these studies. Due to the exponential increase in the number of logical expression templates with the number of variables, we are only able to evaluate a subset of them in our experiments. However, the selected expression templates are considered empirically significant based on their use in various previous works on complex query answering [1][2].

[1] Query2box: Reasoning over knowledge graphs in vector space using box embeddings.

[2] Beta embeddings for multi-hop logical reasoning in knowledge graphs.

Thank you for your review! We would like to make the following clarifications.

Re W1:

We revised and clarified the problem definition in section 2, which involves using abductive reasoning to find a hypothesis (H) that matches an observation set $O = \\{v_1, v_2, ..., v_k\\}$ as closely as possible. The objective of abductive reasoning is formalized in equation (4), which uses the Jaccard score to measure the similarity between the observations and the corresponding conclusions drawn from the generated conclusions on the hidden graph.

Re W2:

Please refer to Re:Q1 and Re:Q2 for the objectives of the problem and the approach. In addition, we further discuss the future work on these directions. One possible direction is to explore the use of more advanced reinforcement learning algorithms to improve the performance of the model. Another direction is to investigate the use of larger and more complex knowledge graphs. Our current experiments were conducted on relatively small graphs with 10k up to 100k vertices. It would be interesting to see how the model performs on larger graphs, as well as graphs with more complex structures and relationships.

Re W4:

We have revised the description of our approach in Section 3.2 to provide further clarity. Please refer to Re: Q2 for details.

Re Q1:

Our proposed KG reasoning task is unique and novel, which means there are no previous methods capable of generating complex first-order logical expressions to explain specific observations. In Table 5 and 6, we compare our method with pure symbolic methods, such as brute-force searching the one-hop neighbors of the observations. However, brute-force searching is very slow on graphs with at least 10k vertices, and it struggles to perform well when the hypothesis is complex and structured, involving multiple logical connectives and variables.

In Appendix G Case Studies, we provide qualitative examples that compare the hypotheses produced by the search-based method, the generation-based method, and the generation-based method after applying RLF-KG.

Re Q2:

We want to clarify that the abductive reasoning objectives mentioned in the abstract and at the end of Section 2 are the same. We formally define the "best" explanation using formula (4) at the end of Section 2, which is represented by the Jaccard similarity between the conclusion of the generated hypothesis on the testing graph (which was not observed during training) and the observation.

It is crucial to note that the reward function for the PPO is chosen to approximate the objective by using the Jaccard similarity between the conclusion of the generated hypothesis on the training graph (the observed graph) and the observation. Furthermore, the primary metric used in our experiments is consistent with the task's objective.

Thank you for your review, we would like to make the following clarifications on your comments.

Re W1:

We revised and clarified the problem definition in section 2, which involves using abductive reasoning to find a hypothesis (H) that matches an observation set $O = \{v_1, v_2, ..., v_k\}$ as closely as possible. The objective of abductive reasoning is formalized in equation (4), which uses the Jaccard score to measure the similarity between the observations and the corresponding conclusions drawn from the generated conclusions on the hidden graph.

Re W2:

During supervised training, the model only learns to minimize the difference between the generated and sample hypothesis sequences. However, this doesn't guarantee that the conclusion of the generated hypothesis on the testing graph will be closer to the observation, which is our ultimate objective. Additionally, this supervision signal doesn't make full use of the knowledge graph's valuable information.

To address this, we implemented a PPO reward that uses the Jaccard similarity between the conclusion of the generated hypothesis on the training graph and the observation. We believe this reward provides logical information that can improve the quality of generated hypotheses by approximating our task's objective directly.

The positive results in our experiments in Section 4.4 further support the value of RLF-KG in improving the quality of hypotheses generated through abductive reasoning.

Re Q1:

We confirm that both the encoder-decoder and decoder-only models we used were based on the Transformer architecture. Our main focus in this paper is to introduce the abductive reasoning task and demonstrate how the RLF-KG framework improves performance on top of a supervised trained model. Our intention is to highlight the benefits of incorporating RLF-KG into the abductive reasoning process, rather than simply comparing neural models to search-based models. While more powerful models could be used as baselines, our primary objective remains to emphasize the performance improvements achieved through the application of RLF-KG.

Re Q2:

In Section 4.4, we present our experimental results, which include a comparison of model performance before and after applying PPO. Table 3 shows that RLF-KG consistently improves hypothesis generation performance across three widely used datasets, using the same metric as the task's objective.

Our goal is to overcome the limitations of supervised training by incorporating information from the knowledge graph. PPO is ideal for this task because it allows us to use the reward from the knowledge graph as feedback, which improves the quality of generated hypotheses by utilizing the available information. As we mentioned in our response to W2, this approach compensates for the limitations of supervised training.

We chose PPO because it's a proven RL method [1] for transformer-based models. Although there are newer methods like DPO [2] that use preference information, they're not directly applicable to our knowledge feedback tuning.

Re Q3:

The reference model is a copy of the model obtained from supervised training, and the model being fine-tuned by PPO starts off identical to the reference model. The reference model plays a crucial role in preventing excessive divergence between itself and the fine-tuned model. The KL term in the PPO objective measures this divergence and penalizes it to ensure that the models remain aligned.

[1] Ouyang, Long, Jeffrey Wu, Xu Jiang, Diogo Almeida, Carroll Wainwright, Pamela Mishkin, Chong Zhang et al. "Training language models to follow instructions with human feedback." Advances in Neural Information Processing Systems 35 (2022): 27730-27744.

[2] Rafailov, Rafael, Archit Sharma, Eric Mitchell, Stefano Ermon, Christopher D. Manning, and Chelsea Finn. "Direct preference optimization: Your language model is secretly a reward model." arXiv preprint arXiv:2305.18290 (2023).

Thank you for taking the time to review our work. We would like to respond to your comments and questions.

Re W1:

Abductive logical reasoning on knowledge graphs remains important because current language models, such as LLMs, struggle to reason over factual knowledge. For example, when prompted with the task of generating a logical hypothesis that matches a given observation set, ChatGPT (GPT-3.5) generated a hypothesis that claimed the devices were all first-generation Apple products, despite the observation set including an iPod touch 4th Gen. This demonstrates the model's inability to perform simple abductive reasoning.

Here is the example:
Input: “Please propose a logical hypothesis H(x) such that the set of all entities that make H(x) true should be as close to O as possible: O = {Ipad 1st Gen, Ipod touch 4th Gen, Apple TV 1st Gen}” (the 2nd example in Fig. 1)

Output: “Certainly! To create a logical hypothesis H(x) that is as close to the given set O = {iPad 1st Gen, iPod touch 4th Gen, Apple TV 1st Gen} as possible, you might consider the following hypothesis:

H(x): The entities in set x are first-generation electronic devices produced by Apple.”

However, in our framework, the model is trained with feedback from the observed knowledge graph. If the knowledge graph contains basic facts about Apple's products and the model generates a faulty hypothesis, the discrepancy between the observation set and the conclusion of the hypothesis will result in a relatively low reward. This encourages the model to correct the hypothesis and improves its ability to reason over factual knowledge.

Q1: We have fixed some typos and improved the presentation.

Q2: We have moved the results of the search baseline to the main table.

Thank you for taking the time to review our work. We appreciate your feedback and would like to provide some clarifications regarding your comments.

Re W1:

We would like to clarify that our task differs from inductive logical programming (ILP). This is because ILP-induced logical hypotheses are general rules, as they are not grounded. In contrast, our task involves grounded logical hypotheses, which specifically describe observations rather than expressing rules. In the knowledge graph domain, inductive reasoning is equivalent to rule mining [1,2,3], discussed in Section 5.

Here are some examples to illustrate the differences:

Rule Mining (ILP on KG):

The task involves a given knowledge graph with some positive examples regarding the relation $speak$. The goal is to find horn clause rules related to the $speak$ relation. $speaks(X, Y) \\leftarrow lives(X, A) \\land language(A, Y)$ The variables in the rules are universally quantified, and the quality of the rules is measured by head coverage and precision. However, in our task, we use a real example from FB15K-237. Our observations include the following entities:

$Grant Heslov, Jason Segel, Robert Towne, Ronald Bass, Rashida Jones$

Our task aims to find a logical expression based on the KG to describe these entities, rather than discovering general rules over the KG. These entities make the following logical expressions true:

$V_?: Occupation(V_?, Actor) \\land Occupation(V_?, Screen Writer) \\land BornIn(V_?, Los Angeles)$

This means that Grant Heslov, Jason Segel, Robert Towne, Ronald Bass, and Rashida Jones are actors and screenwriters born in Los Angeles. This logical expression is not a rule, as not all entities from the KG satisfy the logical expression.

Therefore, our problem setting is distinct from inductive logical programming over knowledge graphs, specifically rule-mining.

Re W2:

We previously explained the differences between our proposed abductive KG reasoning task and ILP. Additionally, our problem setting significantly differs from the abductive learning suggested in [4]. The study in [4] uses abductive learning (ABL) to form symbolic representations via learning methods and then applies Prolog's abductive logic programming to address hand-written puzzles. These symbolic representations may not be logical expressions, and Prolog's abductive logic programming can only evaluate their truth or falsity, without generating complex first-order structured hypotheses.

Re W3:

In the appendix, we have provided several concrete examples in Tables 12, 13, and 14. These tables contain the observations, logical expressions, and their corresponding truth values. As demonstrated in the tables, our proposed method can generate logical expressions that are appropriately long, involve multiple logical connectives, and are precise (as indicated by high Jaccard scores) in describing the observations.

Re Q1:

As presented in Equations 1 and 2, we focus on a specific form of first-order logical expressions, which includes existential quantified intermediate variables and logical connectives AND/OR/NOT. We have provided further clarification regarding the scope in Section 2 of the paper.

[1] Christian Meilicke, Melisachew Wudage Chekol, Daniel Ruffinelli, and Heiner Stuckenschmidt. Anytime bottom-up rule learning for knowledge graph completion. In Sarit Kraus (ed.), Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence, IJCAI 2019, Macao, China, August 10-16, 2019, pp. 3137–3143. ijcai.org, 2019. doi: 10.24963/ijcai.2019/ 435. URL https://doi.org/10.24963/ijcai.2019/435.

[2] Vinh Thinh Ho, Daria Stepanova, Mohamed H. Gad-Elrab, Evgeny Kharlamov, and Gerhard Weikum. Rule learning from knowledge graphs guided by embedding models. In Denny Vrandecic, Kalina Bontcheva, Mari Carmen Suarez-Figueroa, Valentina Presutti, Irene Celino, ´ Marta Sabou, Lucie-Aimee Kaffee, and Elena Simperl (eds.), ´ The Semantic Web - ISWC 2018 - 17th International Semantic Web Conference, Monterey, CA, USA, October 8-12, 2018, Proceedings, Part I, volume 11136 of Lecture Notes in Computer Science, pp. 72–90. Springer, 2018. doi: 10.1007/978-3-030-00671-6\ 5. URL https://doi.org/10.1007/ 978-3-030-00671-6_5.

[3] Luis Galarraga, Christina Teflioudi, Katja Hose, and Fabian M. Suchanek. Fast rule mining in ´ ontological knowledge bases with AMIE+. VLDB J., 24(6):707–730, 2015. doi: 10.1007/ s00778-015-0394-1. URL https://doi.org/10.1007/s00778-015-0394-1.