U ni KER : A Unified Framework for Combining Embedding and Definite Horn Rule Reasoning for Knowledge Graph Inference (2021)

Abstract: Knowledge graph inference has been studied extensively due to its wide applications. It has been addressed by two lines of research, i.e., the more traditional logical rule reasoning and the more recent knowledge graph embedding (KGE). Several attempts have been made to combine KGE and logical rules for better knowledge graph inference. Unfortunately, they either simply treat logical rules as additional constraints into KGE loss or use probabilistic model to approximate the exact logical inference (i.e., MAX-SAT). Even worse, both approaches need to sample ground rules to tackle the scalability issue, as the total number of ground rules is intractable in practice, making them less effective in handling logical rules. In this paper, we propose a novel framework UniKER to address these challenges by restricting logical rules to be definite Horn rules, which can fully exploit the knowledge in logical rules and enable the mutual enhancement of logical rule-based reasoning and KGE in an extremely efficient way. Extensive experiments have demonstrated that our approach is superior to existing state-of-the-art algorithms in terms of both efficiency and effectiveness.

## introduction knowledge graphs (kgs) have grown rapidly recently which provide remarkably valuable resources for many real-world applications @xcite @xcite . kg reasoning, which aims at inferring missing knowledge through the existing facts, is the key to the success of many downstream tasks and have received wide attention. knowledge graph embedding (kge) methods currently hold the state-of-the-art in kg reasoning @xcite @xcite . they aim to capture the similarity of entities via exploring rich structure information in kgs to predict unseen triples. despite the excellent performance of kge methods, the ignorance of possible high-order constraints specified by logical rules limits their application in more complex reasoning tasks. in fig. 1 , for example, we can infer stilwell lives in usa based on kge, due to her similarity with miller in terms of embeddings, as both can be reached via the same relation transformation (i.e. ismarriedto) from the same entity @xcite . but without the capability of leveraging logical rules, we cannot infer stilwell and miller speak english. an alternative solution is to infer missing facts via logical rules, which have been extensively explored by traditional logical rule-based methods @xcite . as shown in fig. 1 , two entities (e.g., miller and english) that are not directly connected in a kg could participate in the same ground logical rule, (e.g., speaklanguage(miller, english) ← livein(miller, usa) ∧ officiallanguage(usa, english)), and a relation between them can be inferred if all predicates in the rule body are true. different from kge, logical inference treats triples as independent units and ignores the correlation among them. as a result, the performance of logical inference highly depends on the completeness of kgs, which suffers from severe insufficiency in reality. for example, due to the absence of the triple livein(mary stilwell, usa), the triple speaklanguage(mary stilwell, english) can not be inferred in fig. 1 . besides its sensitivity to the quality of kg, logical inference is also known for its high computation complexity as it requires instantiating universally quantified rules into ground rules, which is extremely time-consuming. although both embedding-based methods and logical rule-based methods have their limitations, they are complementary for better reasoning capability. as shown in fig. 1 , on one hand, logical rules are useful to provide additional information by exploiting the higher-order dependency of kg relations (fig. 1(d) ). on the other hand, highquality embedding learned by kge models, in turn, will help to prepare a more complete kg for logical rule-based reasoning (fig. 1(c )). despite several attempts made to combine kge and logical rules for kg reasoning, they either simply treat logical rules as additional constraints into kge loss @xcite @xcite or use probabilistic model to approximate the exact logical inference (i.e., max-sat) @xcite @xcite . moreover, these methods rely on ground rules, the total number of which is intractable in practice. to tackle the scalability issue, only a small portion of ground predicates/ground rules are sampled to approximate the inference process, which causes further information loss from the logic side. to overcome the above issues, we propose a novel unified framework for combining knowledge graph embedding with logical rules (uniker) for better kg reasoning, to handle a special type of first-order logic, i.e., the definite horn rules. first, we combine logical rule reasoning and kg embedding in an iterative manner, to make sure the inferred knowledge via both techniques can benefit each other as shown in fig. 1 . second, we propose an iterative grounding algorithm to extend the classic forward chaining algorithm that is designed for definite horn rule reasoning in an extremely efficient way. consequently, uniker can fully exploit the knowledge contained in logical rules and enrich kgs for better embedding. meanwhile, kge enhances the forward chaining by including more potential useful hidden facts (see fig. 1(c )). in this way, two procedures mutually enhance each other. the main contributions of this paper are summarized as follows: ## related work on integrating embedding and logical rules max-sat problem is defined using boolean logic while scoring function of kge provides a soft truth value to triples in kg. probabilistic logic is widely used to integrate both worlds into the same framework, which is able to extend boolean logic to probabilistic logic to enable uncertain inference. these approaches can be divided into two categories: (1) designing a probablistic soft logic (psl)-based regularization to embedding models and (2) designing an embedding-based variational distribution for variational inference of markov logic network (mln) @xcite , a probabilistic logic that applies markov network to fol. ## a unified framework for knowledge graph inference: uniker rather than follow probabilistic logic to integrate logical rules and kge, we show that by leveraging the nice properties of definite horn rules, there is a much simpler way to directly derive an optimal boolean solution for max-sat problem. to capture the mutual interaction between kge and logical inference, we proposed an iterative mechanism, which ensures that uniker is more potent than a simple union of kge and logical rules. ## conclusion in this paper, we proposed a novel framework, known as uniker, to integrate embedding and definite horn rules in an iterative manner for better kg inference. we have shown that uniker can fully leverage the knowledge in definite horn rules and completely transfer them into the embeddings in an extremely efficient way.