Advancing Abductive Reasoning in Knowledge Graphs through Complex Logical Hypothesis Generation (2024)

Abstract: Abductive reasoning is the process of making educated guesses to provide explanations for observations. Although many applications require the use of knowledge for explanations, the utilization of abductive reasoning in conjunction with structured knowledge, such as a knowledge graph, remains largely unexplored. To fill this gap, this paper introduces the task of complex logical hypothesis generation, as an initial step towards abductive logical reasoning with KG. In this task, we aim to generate a complex logical hypothesis so that it can explain a set of observations. We find that the supervised trained generative model can generate logical hypotheses that are structurally closer to the reference hypothesis. However, when generalized to unseen observations, this training objective does not guarantee better hypothesis generation. To address this, we introduce the Reinforcement Learning from Knowledge Graph (RLF-KG) method, which minimizes differences between observations and conclusions drawn from generated hypotheses according to the KG. Experiments show that, with RLF-KG’s assistance, the generated hypotheses provide better explanations, and achieve state-of-the-art results on three widely used KGs.

## introduction abductive reasoning plays a vital role in generating explanatory hypotheses for observed phenomena across various research domains @xcite . it is a powerful tool with wide-ranging applications. for example, in cognitive neuroscience, reverse inference @xcite , which is a form of abductive reasoning, is crucial for inferring the underlying cognitive processes based on observed brain activation patterns. similarly, in clinical diagnostics, abductive reasoning is recognized as a key approach for studying cause-and-effect relationships @xcite . moreover, abductive reasoning is fundamental to the process of hypothesis generation in humans, animals, and computational machines @xcite . its significance extends beyond these specific applications and encompasses diverse fields of study. in this paper, we are focused on abductive reasoning with structured knowledge, specifically, a knowledge graph. a typical knowledge graph (kg) stores information about entities, like people, places, items, and their relations in graph structures. meanwhile, kg reasoning is the process that leverages knowledge graphs to infer or derive new information @xcite @xcite . in recent years, various logical reasoning tasks are proposed over knowledge graph, for example, answering complex queries expressed in logical structure @xcite , or conducting logical rule mining @xcite @xcite . however, the abductive perspective of kg reasoning is crucial yet unexplored. consider the first example in figure 1 , where observation o 1 depicts five celebrities followed by a user on a social media platform. the social network service provider is interested in using structured knowledge to explain the users' observed behavior. by leveraging a knowledge graph like freebase @xcite , which contains basic information about these individuals, a complex logical hypothesis h 1 can be derived suggesting that they are all actors and screenwriters born in los angeles. in the second example from figure 1 , related to a user's interactions on an e-commerce platform (o 2 ), the structured hypothesis h 2 can explain the user's interest in apple products released in 2010 excluding phones. the third example, dealing with medical diagnostics, presents three diseases (o 3 ). the corresponding hypothesis h 3 indicates they are diseases v ? with symptom v 1 , and v 1 can be relieved by p anadol. from a general perspective, observations (o) hypotheses (h) interpretations 𝑂 1 = {grant heslov, jason segel, robert towne, ronald bass, rashida jones} 𝐻 1 = 𝑉 ? ∶ 𝑂𝑐𝑐𝑢𝑝𝑎𝑡𝑖𝑜𝑛(𝑉 ? , 𝐴𝑐𝑡𝑜𝑟) ∧ 𝑂𝑐𝑐𝑢𝑝𝑎𝑡𝑖𝑜𝑛 𝑉 ? , 𝑆𝑐𝑟𝑒𝑒𝑒𝑊𝑟𝑖𝑡𝑒𝑟 ∧ 𝐵𝑜𝑟𝑛𝐼𝑛 𝑉 ? , 𝐿𝑜𝑠𝐴𝑛𝑔𝑒𝑙𝑒𝑠 the actors and screenwriters born in los angeles 𝑂 2 = {ipad 1 st gen, ipod touch 4 th gen, apple tv 1 st gen} 𝐻 2 = 𝑉 ? ∶ 𝐵𝑟𝑎𝑛𝑑(𝑉 ? , 𝐴𝑝𝑝𝑙𝑒) ∧ 𝑅𝑒𝑙𝑒𝑎𝑠𝑒𝑌𝑒𝑎𝑟(𝑉 ? , 2010) ∧ ¬𝑇𝑦𝑝𝑒 𝑉 ? , 𝑃ℎ𝑜𝑛𝑒 the apple products released in 2010 that are not phones 𝑂 3 = {covid-19, seasonal flu, dysmenorrhea} 𝐻 3 = 𝑉 ? , ∃𝑉 1 : 𝐻𝑎𝑣𝑒𝑆𝑦𝑚𝑝𝑡𝑜𝑚(𝑉 ? , 𝑉 1 ) ∧ 𝑅𝑒𝑙𝑖𝑒𝑣𝑒𝑑𝐵𝑦 𝑉 1 , 𝑃𝑎𝑛𝑎𝑑𝑜𝑙 the disease whose symptoms can be relieved by panadol these problems illustrate how abductive reasoning with knowledge graphs seeks hypotheses that best explain given observations @xcite . a straightforward approach to tackle this reasoning task is to employ a search-based method to explore potential hypotheses based on the given observation. however, this approach faces two significant challenges. the first challenge arises from the incompleteness of knowledge graphs (kgs), as searching-based methods heavily rely on the availability of complete information. in practice, missing edges in kgs can negatively impact the performance of search-based methods @xcite . the second challenge stems from the complexity of logically structured hypotheses. the search space for search-based methods becomes exponentially large when dealing with combinatorial numbers of candidate hypotheses. consequently, the search-based method struggles to effectively and efficiently handle observations that require complex hypotheses for explanation. to overcome these challenges, we propose a solution that leverages generative models within a supervised learning framework to generate logical hypotheses for given observations. our approach involves sampling hypothesis-observation pairs from observed knowledge graphs @xcite and training a transformerbased generative model @xcite using the teacher-forcing method. however, a potential limitation of supervised training is that it primarily captures structural similarities, without necessarily guaranteeing improved explanations when applied to unseen observations. to address this, we introduce a technique called reinforcement learning from the knowledge graph (rlf-kg). it utilizes proximal policy optimization (ppo) @xcite to minimize the discrepancy between the observed evidence and the conclusion derived from the generated hypothesis. by incorporating reinforcement learning techniques, our approach aims to directly improve the explanatory capability of the generated hypotheses and ensure their effectiveness when generalized to unseen observations. we evaluate the proposed methods for effectiveness and efficiency on three knowledge graphs: fb15k-237 @xcite , wn18rr @xcite , and dbpedia50 @xcite . the results consistently demonstrate the superiority of our approach over supervised generation baselines and search-based methods, as measured by two evaluation metrics across all three datasets. our contributions can be summarized as follows: ## problem formulation in this task, a knowledge graph is denoted as @xmath0, r), where v is the set of vertices and r is the set of relation types. each relation type @xmath1: v × @xmath2, false}, with r(u, v) = true indicating the existence of a directed (u, r, v) from vertex u to vertex v of type r in the graph , and false otherwise. we adopt the open-world assumption of knowledge graphs @xcite , treating missing edges as unknown rather than false. the reasoning model can only access the observed kg g, while the true kg ḡ is hidden and encompasses the observed graph g. abductive reasoning is a type of logical reasoning that involves making educated guesses to infer the most likely reasons for the observations @xcite . for further details on the distinctions between abductive, deductive, and inductive reasoning, refer to appendix a. in this work, we focus on a specific abductive reasoning type in the context of knowledge graphs. we first introduce some concepts in this context. an observation is a set o of entities in v. a logical hypothesis h on a graph @xmath3, r) is defined as a predicate of a variable vertex v ? in firstorder logical form, including existential quantifiers, and (∧), or (∨), and not (¬). the hypothesis can always be written in disjunctive normal form, the subscript | g denotes that the hypothesis is formulated based on the given graph g. this means that all entities and relations in the hypothesis must exist in g, and the domain for variable vertices is the entity set of g. for example, please refer to appendix b. the same hypothesis h can be applied to a different knowledge graph, g ′ , provided that g ′ includes the entities and edges present in h. when the context is clear or the hypothesis pertains to a general statement applicable to multiple knowledge graphs (e.g., observed and hidden graphs), the symbol h is used without the subscript. the conclusion of the hypothesis h on a graph g, denoted by [[h]] g , is the set of entities for which h holds true on g: in other words, the goal is to find a hypothesis h that maximizes jaccard([[h]] ḡ , o). ## hypothesis generation with rlf-kg our methodology, referred to as reinforcement learning from the knowledge graph (rlf-kg), is depicted in fig. 4 and involves the following steps: ## experiment we utilize three distinct knowledge graphs, namely fb15k-237 @xcite , dbpe-dia50 @xcite , and wn18rr @xcite , for our experiments. to ensure consistency, we randomly partition the edges of these knowledge graphs into three setstraining, validation, and testing -using an 8:1:1 ratio. consequently, we construct the training graph g train , validation graph g valid , and testing graph g test by including the corresponding edges: training edges only, training + validation edges, and training + validation + testing edges, respectively. following the methodology outlined in section 3.2, we proceed to sample pairs of observations and hypotheses. to ensure the quality and diversity of the samples, we impose certain constraints during the sampling process. firstly, we restrict the size of the observation sets to a maximum of thirty-two elements. this limitation is enforced ensuring that the observations remain manageable. additionally, specific constraints are applied to the validation and testing hypotheses. each validation hypothesis must incorporate additional entities in the conclusion compared to the training graph, while each testing hypothesis must have additional entities in the conclusion compared to the validation graph. this progressive increase in entity complexity ensures a challenging evaluation setting. the statistics of queries sampled for datasets are detailed in appendix c. in line with previous work on kg reasoning @xcite , we utilize thirteen pre-defined logical patterns to sam- figure 5: our task involves considering thirteen distinct types of logical hypotheses. each hypothesis type corresponds to a specific type of query graph, which is utilized during the sampling process. by associating each hypothesis type with a corresponding query graph, we ensure that a diverse range of hypotheses is sampled. ## related work the problem of abductive knowledge graph reasoning shares connections with various other knowledge graph reasoning tasks, including knowledge graph completion, complex logical query answering, and rule mining. rule mining rule mining focuses on inductive logical reasoning, namely discovering logical rules over the knowledge graph. various methods are proposed in this line of work @xcite @xcite @xcite . while the direct application of rule mining to solve this task is theoretically applicable, rule mining algorithms such as those described by @xcite also rely on searches to construct the horn clauses, which face scalability issues. complex logical query complex logical query answering is a task of answering logically structured queries on kg. query embedding primary focus is the enhancement of embedding structures for encoding sets of answers @xcite @xcite @xcite @xcite @xcite . for instance, @xcite and @xcite introduce the utilization of geometric structures such as rectangles and cones within hyperspace to represent entities. neural mlp (mixer) @xcite use mlp and mlp-mixer as the operators. @xcite suggests employing multiple vectors to encode queries, thereby addressing the diversity of answer entities. fuzzqe @xcite uses fuzzy logic to represent logical operators. probabilistic distributions can also serve as a means of query encoding @xcite , with examples including beta embedding @xcite and gamma embedding @xcite . ## conclusion in summary, this paper has introduced the task of abductive logical knowledge graph reasoning. meanwhile, this paper has proposed a generationbased method to address knowledge graph incompleteness and reasoning efficiency by generating logical hypotheses. furthermore, this paper demonstrates the effectiveness of our proposed reinforcement learning from knowledge graphs (rlf-kg) to enhance our hypothesis generation model by leveraging feedback from knowledge graphs.