DegreEmbed: Incorporating entity embedding into logic rule learning for knowledge graph reasoning

Abstract

Knowledge graphs (KGs), as structured representations of real world facts, are intelligent databases incorporating human knowledge that can help machine imitate the way of human problem solving. However, KGs are usually huge and there are inevitably missing facts in KGs, thus undermining applications such as question answering and recommender systems that are based on knowledge graph reasoning. Link prediction for knowledge graphs is the task aiming to complete missing facts by reasoning based on the existing knowledge. Two main streams of research are widely studied: one learns low-dimensional embeddings for entities and relations that can explore latent patterns, and the other gains good interpretability by mining logical rules. Unfortunately, the heterogeneity of modern KGs that involve entities and relations of various types is not well considered in the previous studies. In this paper, we propose DegreEmbed, a model that combines embedding-based learning and logic rule mining for inferring on KGs. Specifically, we study the problem of predicting missing links in heterogeneous KGs from the perspective of the degree of nodes. Experimentally, we demonstrate that our DegreEmbed model outperforms the state-of-the-art methods on real world datasets and the rules mined by our model are of high quality and interpretability.

1. Introduction

Recent years have witnessed the growing attraction of knowledge graphs in a variety of applications, such as dialogue systems [19,23], search engines [40] and domain-specific softwares [22,30]. Capable of incorporating large-scale human knowledge, KGs provide graph-structured representation of data that can be comprehended and examined by humans. Knowledge in KGs is stored in triple form $\mathrm{(}{\mathit{e}}_{\mathit{s}}\mathrm{,}\mathit{r}\mathrm{,}{\mathit{e}}_{\mathit{o}}\mathrm{)}$ , with ${\mathit{e}}_{\mathit{s}}$ and ${\mathit{e}}_{\mathit{o}}$ denoting subject and object entities and r a binary relation (a.k.a. predicate). For example, the fact that Mike is the nephew of Pete can be formed as $\mathrm{(}\mathtt{Mike}\mathrm{,}\mathtt{nephewOf}\mathrm{,}\mathtt{Pete}\mathrm{)}$ . However, information incompleteness can be seen in most modern KGs, that is, missing links in the graph, e.g., the work of [10,17] shows that there are more than 66% of the person entities missing a birthplace in two open KGs Freebase [3] and DBpedia [1].

Predicting missing triples based on the existing facts is usually called link prediction as a subtask of knowledge graph completion (KGC) [14], and numerous models have been developed for solving such problems. One prominent direction in this line of research is representation learning methods that learn distributed embedding vectors for entities and relations, such as TransE [4] and ComplEx [34]. In this work, they are referred to as embedding-based methods. This kind of models are capable of capturing latent knowledge through low-dimensional vectors, e.g. we can classify male and female entities in a family KG by clustering their points at the semantic space. In spite of achieving high performance, these models suffer from non-transparency and can poorly be understood by humans, which is a common issue for most deep learning models. In addition, most embedding-based methods work in a transductive setting, where they require the entities in training and test data to overlap, hindering the way to generalize in some real-world situations.

Fig. 1.

An example of KG containing heterogeneous entities and relations: paper, person and institution. Entities in different colors mark their type. The existing links in the KG are presented as solid black lines, the missing one as dashed lines in red and the proper rule for inferring the link as blue lines.

Another popular approach is rule mining that discovers logical rules through mining co-occurrences of frequent patterns in KGs [5,11]. This paper studies the problem of learning first-order logical Horn clauses for knowledge graph reasoning (KGR). As illustrated in Fig. 1, there is a missing link (i.e. nephewOf) between the subject Mike and the object Steve, but we can complete the fact through a logic rule nephewOf(Mike, Pete) ∧ brotherOf(Pete, Steve) ⇒ nephewOf(Mike, Steve), meaning that if Mike is the nephew of Pete and Steve has a brother Pete, then we can infer that Mike is the nephew of Steve. Reasoning on KGs through Horn clauses has been previously studied in the area of Inductive Logic Programming [24]. One representative method, Neural LP [42], is the first fully differentiable neural system that successfully combines learning discrete rule structures as well as confidence scores in continuous space. Although learning logical rules equips a model with strong interpretability and the ability to generalize to similar tasks [28,45], these methods often focus only on the relations of which the rules are made up, while the intrinsic properties of the involved entities are not considered. For example, in the KG shown in Fig. 1, it is definitely wrong to infer by a rule containing a female-type relation path like sisterOf starting from Mike, because Mike is the nephew of Pete, which indirectly tells us he is a male. This sort of deficiency is more severe in heterogeneous KGs where there are entities and relations of different types mixing up. In these KGs, there might be multiple rules of no use, becoming inevitable noises for reasoning tasks. For instance, the rule read(Mike, paper2) ∧ readBy(paper2, Steve) ⇒ nephewOf(Mike, Steve) is obviously wrong in logic, which might decrease the performance and interpretability of ILP models.

In this paper, in order to bridge the gap between the two lines of research mentioned above, we propose DegreEmbed, a model of logic rule learning that integrates the inner attributes of entities by embedding nodes in the graph from the perspective of their degrees. DegreEmbed is not only interpretable to humans, but also able to mine relational properties of entities. We also evaluate our model on several knowledge graph datasets, and show that we are able to learn more accurately, and meanwhile, gain strong interpretability of mined rules.

Our main contributions are summarized below:

• We propose an original model based on logic rule learning to predict missing links in heterogeneous KGs. Specifically, a new technique for encoding entities, called degree embedding, is designed to capture hidden features through the relation type of edges incident to a node.

• Comparative experiments on knowledge graph completion task with five benchmark datasets prove that our DegreEmbed model outperforms baseline models. Besides, under the evaluation of a metric called Saturation, we show that our method is capable of mining meaningful logic rules from knowledge graphs.

• Visualizing learned entity embeddings, we demonstrate that clear features of entities can be obtained by our model, thus benefitting the prediction in heterogeneous settings. Moreover, we prove the necessity of each component of our model using ablation study.

This paper is structured as follows. We briefly introduce our related work and review preliminary definitions of knowledge graphs respectively in Section 2 and Section 3. Section 4 introduces our proposed DegreEmbed model based on logic rule learning for link prediction in heterogeneous KGs. We present the experimental results in Section 5 and conclude our work by pointing out the future direction.

2. Related work

Our work is first related to previous efforts on relational data mining, based on which, a large body of deep rule induction models have been developed for link prediction. Since our approach achieves a combination of logic rule learning and knowledge graph embedding, we conclude related work in this topic as well.

Relational data mining. The problem of learning relational rules has been traditionally addressed in the field of inductive logic programming (ILP) [24]. These methods often view the task of completing a missing triple as a query $\mathit{q}\mathrm{(}\mathit{h}\mathrm{,}\mathit{t}\mathrm{)}$ where they learn a probability as confidence score for each rule between the query entity and answer entity. Among these studies, Path-Ranking Algorithm (PRA) [18] investigated the framework of random walk inference, where they select a relational path under a set of constraints and perform maximum-likelihood classification. An RNN model was developed by [25] to compose the semantics of relations for arbitrary-length reasoning. Chain-Reasoning proposed by [8], enabling multi-hop reasoning through a neural attention mechanism, reveals logical rules across all relations and entities. Although ILP models are capable of mining interpretable rules for humans, these models typically take both positive and negative examples for training and suffer from a potentially large version space, which is a critical shortage since most modern KGs are huge and contain only positive instances.

Neural logic programming. In recent years, models borrowing the idea of logic rule learning in a deep manner have emerged as successful approaches for link prediction task. Extending the idea of TensorLog that tackles the problem of rule-based logic reasoning through sparse matrix multiplication, Neural LP [42] is the first end-to-end differentiable approach to simultaneously learn continuous parameters and discrete structure of rules. Some recent methods [29,38,43] have improved the framework done by Neural LP [42] in different manners. DRUM [29] introduces tensor approximation for optimization and reformulate Neural LP to support rules of varied lengths. Neural-Num-LP [38] extends Neural LP to learn numerical relations like age and weight with dynamic programming and cumulative sum operation. NLIL [43] proposes a multi-hop reasoning framework for general ILP problem through a divide-and-conquer strategy as well as decomposing the search space into three subspaces. However, the existing methods ignore the effects caused by entities of different types while reasoning over a specific relational path, thus witness a more obvious failure where heterogeneous entities and relations are involved in the KGs.

Representation learning. Capturing their semantic information by learning low-dimensional embeddings of entities and relations, also known as knowledge graph embedding, is a vital research issue in KGC, and we term those models as embedding-based models. Newly proposed methods, including RotatE [32], ConvE [9] and TuckER [2], predict missing links by learning embedding vectors from various perspectives of the problem. Specifically, the work of RotatE [32] focuses on inferring patterns such as symmetry and inversion, where they proposed a rotational model that rotates the relation from the subject to the object in the complex space as ${\mathit{e}}_{\mathit{o}}={\mathit{e}}_{\mathit{s}}\circ \mathit{r}$ where the ∘ denotes the element-wise Hadamard product. ConvE introduces a highly parameter efficient model, which uses 2D convolution over embeddings and multiple layers of nonlinear features to express semantic information. TuckER, inspired by the Tucker decomposition [35] that factorizes a tensor into a core tensor along with a set of matrices, is a linear model for link prediction that has good expressive power. Unfortunately, the biggest problem is that these sort of methods can hardly be comprehended by humans, but we relate to these methods for their ability to capture latent information of entities and relations through embedding.

We also notice that there are methods trying to establish a connection between learning logical rules and learning embedding vectors [37,44], where they augment the dataset by exploring new triplets from the existing ones in the KG using pre-defined logical rules to deal with the sparsity problem, which differs from our goal to consider entities of various types for learning in heterogeneous KGs.

3. Preliminaries

In this section, we introduce background concepts of logic rule learning for knowledge graph reasoning as well as the definition of topological structure of KGs.

3.1. Knowledge graph reasoning

Knowledge graph can be modeled as a collection of factual triples $\mathcal{G}=\{\mathrm{(}{\mathit{e}}_{\mathit{s}}\mathrm{,}\mathit{r}\mathrm{,}{\mathit{e}}_{\mathit{o}}\mathrm{)}|{\mathit{e}}_{\mathit{s}}\mathrm{,}{\mathit{e}}_{\mathit{o}}\in \mathcal{E}\mathrm{,}\mathit{r}\in \mathcal{R}\}$ , with $\mathcal{E}$ , $\mathcal{R}$ representing the set of entities and binary relations (a.k.a. predicates) respectively in the knowledge graph, and $\mathrm{(}{\mathit{e}}_{\mathit{s}}\mathrm{,}\mathit{r}\mathrm{,}{\mathit{e}}_{\mathit{o}}\mathrm{)}$ the triple $\mathrm{(}\mathtt{subject}\mathrm{,}\mathtt{relation}\mathrm{,}\mathtt{object}\mathrm{)}$ in form of ${\mathit{e}}_{\mathit{s}}\stackrel{\mathit{r}}{\to }{\mathit{e}}_{\mathit{o}}$ . During reasoning over KGs, each triple is usually presented in the form $\mathtt{r}\mathrm{(}{\mathit{e}}_{\mathit{s}}\mathrm{,}{\mathit{e}}_{\mathit{o}}\mathrm{)}$ . The subgraph regarding a specific relation ${\mathtt{r}}_{\mathit{i}}$ is described as a subset of $\mathcal{G}$ containing all triples with ${\mathtt{r}}_{\mathit{i}}$ being the connection between the subject and object: $\mathcal{G}\mathrm{(}{\mathtt{r}}_{\mathit{i}}\mathrm{)}=\{\mathrm{(}{\mathit{e}}_{\mathit{s}}\mathrm{,}\mathit{r}\mathrm{,}{\mathit{e}}_{\mathit{o}}\mathrm{)}|{\mathit{e}}_{\mathit{s}}\mathrm{,}{\mathit{e}}_{\mathit{o}}\in \mathcal{E}\mathrm{,}{\mathtt{r}}_{\mathit{i}}\in \mathcal{R}\mathrm{,}\mathit{r}={\mathtt{r}}_{\mathit{i}}\}$ .

Logic rule reasoning. We perform reasoning on KGs by learning a confidence score $\mathit{\alpha }\in [0\mathrm{,}1]$ for a first-order logic rule in the form $$\begin{array}{}\text{(1)}& {\mathtt{r}}_1\mathrm{(}\mathit{x}\mathrm{,}{\mathit{z}}_1\mathrm{)}\wedge \cdots \wedge {\mathtt{r}}_{\mathit{l}}\mathrm{(}{\mathit{z}}_{\mathit{l}-1}\mathrm{,}\mathit{y}\mathrm{)}\Rightarrow \mathit{q}\mathrm{(}\mathit{x}\mathrm{,}\mathit{y}\mathrm{)}:\mathit{\alpha }\mathrm{,}\end{array}$$ $\mathbf{r}\mathrm{(}\mathbf{x}\mathrm{,}\mathbf{y}\mathrm{)}\Rightarrow \mathit{q}\mathrm{(}\mathit{x}\mathrm{,}\mathit{y}\mathrm{)}$ for short, with ${\mathit{r}}_1\mathrm{,}\dots \mathrm{,}{\mathit{r}}_{\mathit{l}}\mathrm{,}\mathit{q}\in \mathcal{R}$ , ${\mathit{z}}_1\mathrm{,}\dots \mathrm{,}{\mathit{z}}_{\mathit{l}-1}\in \mathcal{E}$ , where $\mathbf{r}={\bigwedge }_{\mathit{i}}{\mathit{r}}_{\mathit{i}}$ , is called a rule pattern. For example, the rule $\mathtt{brotherOf}\mathrm{(}\mathit{x}\mathrm{,}\mathit{z}\mathrm{)}\wedge \mathtt{fatherOf}\mathrm{(}\mathit{z}\mathrm{,}\mathit{y}\mathrm{)}\Rightarrow \mathtt{uncleOf}\mathrm{(}\mathit{x}\mathrm{,}\mathit{y}\mathrm{)}$ intuitively states that if x is the brother of z and z is the father of y, then we can conclude that x is the uncle of y. All rule patterns of length l ( $\mathit{l}⩾2$ ) can be formally defined as a set of relational tuples ${\mathcal{H}}^{\mathit{l}}=\{\mathrm{(}{\mathit{r}}_1\mathrm{,}{\mathit{r}}_2\mathrm{,}\dots \mathrm{,}{\mathit{r}}_{\mathit{l}}\mathrm{)}|{\mathit{r}}_{\mathit{i}}\in \mathcal{R}\mathrm{,}1⩽\mathit{i}⩽\mathit{l}\}={\mathcal{R}}^{\mathit{l}}$ , and the set of patterns no longer than L is denoted as ${\mathbb{H}}^{\mathit{L}}={\bigcup }_{\mathit{l}=2}^{\mathit{L}}{\mathcal{H}}^{\mathit{l}}$ . A rule pathp is an instance of a certain pattern r via different sequences of entities, which can be denoted as $\mathbf{p}⊳\mathbf{r}$ , e.g., $\mathrm{(}{\mathit{r}}_{\mathit{a}}\mathrm{(}\mathit{x}\mathrm{,}{\mathit{z}}_1\mathrm{)}\mathrm{,}{\mathit{r}}_{\mathit{b}}\mathrm{(}{\mathit{z}}_1\mathrm{,}\mathit{y}\mathrm{)}\mathrm{)}$ and $\mathrm{(}{\mathit{r}}_{\mathit{a}}\mathrm{(}\mathit{x}\mathrm{,}{\mathit{z}}_2\mathrm{)}\mathrm{,}{\mathit{r}}_{\mathit{b}}\mathrm{(}{\mathit{z}}_2\mathrm{,}\mathit{y}\mathrm{)}\mathrm{)}$ are different paths of the same pattern.

The link prediction task here is considered to contain a variety of queries, each of which is composed of a query body $\mathit{q}\in \mathcal{R}$ , an entity headh which the query is about, and an entity tailt that is the answer to the query such that $\mathrm{(}\mathit{h}\mathrm{,}\mathit{q}\mathrm{,}\mathit{t}\mathrm{)}\in \mathcal{G}$ . Finally we want to find the most possible logic rules $\mathit{h}\stackrel{{\mathit{r}}_1}{\to }\cdots \stackrel{{\mathit{r}}_1}{\to }\mathit{t}$ to predict the link q. Thus, given maximum length L, we assign a single confidence score (i.e. probability) to a set of rule paths p’s adhering to the same pattern r that connects h and t: $$\begin{array}{}\text{(2)}& \{{\mathbf{p}}_{\mathit{i}}\mathrm{(}\mathit{h}\mathrm{,}\mathit{t}\mathrm{)}\Rightarrow \mathit{q}\mathrm{(}\mathit{h}\mathrm{,}\mathit{t}\mathrm{)}|{\mathbf{p}}_{\mathit{i}}⊳\mathbf{r}\mathrm{,}\mathbf{r}\in {\mathbb{H}}^{\mathit{L}}\}:\mathit{\alpha }\end{array}$$

During inference, given an entity h, the unified score of the answer t can be computed by adding up the confidence scores of all rule paths that infer $\mathit{q}\mathrm{(}\mathit{h}\mathrm{,}\mathit{t}\mathrm{)}$ , and the model will produce a ranked list of entities where higher the score implies higher the ranking.

3.2. Graph structure

Definition 1 (Directed Labeled Multigraph).

A directed labeled multigraphG is a tuple $\mathit{G}=\mathrm{(}\mathit{V}\mathrm{,}\mathit{E}\mathrm{)}$ , where V denotes the set of vertices, and $\mathit{E}\subseteq \mathit{V}\times \mathit{V}$ is a multiset of directed, labeled vertex pairs (i.e. edges) in the graph G.

Because of its graph structure, a knowledge graph can be regarded as a directed labeled multigraph [31]. In this paper, “graph” is used to refer to “directed labeled multigraph” for the sake of simplicity. $\mathit{G}\mathrm{(}\mathtt{r}\mathrm{)}=\mathrm{(}\mathit{V}\mathrm{(}\mathtt{r}\mathrm{)}\mathrm{,}\mathit{E}\mathrm{(}\mathtt{r}\mathrm{)}\mathrm{)}$ is the corresponding topological structure of $\mathcal{G}\mathrm{(}\mathtt{r}\mathrm{)}$ . $\mathit{m}=|\mathit{V}|$ and $\mathit{n}=|\mathit{E}|$ stand for the number of vertices and number of edges respectively for a graph G. Particularly in a KG, $|\mathcal{E}|=\mathit{m}$ and the total number of triplets $\mathrm{(}{\mathit{e}}_{\mathit{s}}\mathrm{,}\mathit{r}\mathrm{,}{\mathit{e}}_{\mathit{o}}\mathrm{)}$ equals the number of edges, i.e. $|\mathcal{G}|=\mathit{n}$ .

Formally, in a graph $\mathit{G}=\mathrm{(}\mathit{V}\mathrm{,}\mathit{E}\mathrm{)}$ , the degree of a vertex $\mathit{v}\in \mathit{V}$ is the number of edges incident to it. When it comes to directed graphs, in-degree and out-degree of a vertex v is usually distinguished, which are defined as $$\begin{array}{}\text{(3)}& \hfill {deg}^{+}\mathrm{(}\mathit{v}\mathrm{)}& =\left|\right\{\mathrm{(}\mathit{u}\mathrm{,}\mathit{v}\mathrm{)}|\mathit{u}\in \mathit{V}\mathrm{,}\mathrm{(}\mathit{u}\mathrm{,}\mathit{v}\mathrm{)}\in \mathit{E}\}|\text{(4)}& \hfill {deg}^{-}\mathrm{(}\mathit{v}\mathrm{)}& =\left|\right\{\mathrm{(}\mathit{v}\mathrm{,}\mathit{u}\mathrm{)}|\mathit{u}\in \mathit{V}\mathrm{,}\mathrm{(}\mathit{v}\mathrm{,}\mathit{u}\mathrm{)}\in \mathit{E}\}|\end{array}$$

But in this paper, we use “degree” to represent the edges incident to a specific node v for conciseness.

Fig. 2.

A KG example of family members and the relations between them.

Definition 2 (Heterogeneous Graph [39]).

A graph $\mathit{G}=\mathrm{(}\mathit{V}\mathrm{,}\mathit{E}\mathrm{)}$ is heterogeneous when it consists a mapping function of node type $\mathit{\varphi }:\mathit{V}\to \mathcal{A}$ and a mapping function of edge type $\mathit{\psi }:\mathit{E}\to \mathcal{R}$ . $\mathcal{A}$ and $\mathcal{R}$ denote the sets of entity types and edge types (relations) in the corresponding KG.

As shown in Fig. 2, nodes of different types are marked in different colors, and edges are categorized by their relational labels.

4. Methodology

Capable of simultaneously learning representations and logical rules, Neural LP [42] is the first differentiable neural system for knowledge graph reasoning that combines structure learning and parameter learning. Our work follows the work of Neural LP and extensive studies based on it to consider the problem of reasoning in heterogeneous KGs, from the view of mining intrinsic properties of the entities in KGs.

4.1. Neural LP for logic reasoning

4.1.1. TensorLog

The work of TensorLog [6,7] successfully simulates the reasoning process using first-order logic rules by performing sparse matrix multiplication, based on which, Neural LP [42] proposed a fully differentiable reasoning system. In the following, we will first introduce the TensorLog operator. In a KG involving a set of entities $\mathcal{E}$ and a set of relations $\mathcal{R}$ , factual triplets w.r.t. the relation ${\mathit{r}}_{\mathit{k}}$ are restored in a binary matrix ${\mathrm{M}}_{{\mathit{r}}_{\mathit{k}}}\in {\{0\mathrm{,}1\}}^{|\mathcal{E}|\times |\mathcal{E}|}$ . ${\mathrm{M}}_{{\mathit{r}}_{\mathit{k}}}$ , an adjacency matrix, is called a TensorLog operator meaning that $\mathrm{(}{\mathit{e}}_{\mathit{i}}\mathrm{,}{\mathit{r}}_{\mathit{k}}\mathrm{,}{\mathit{e}}_{\mathit{j}}\mathrm{)}$ is in the KG if and only if the $\mathrm{(}\mathit{i}\mathrm{,}\mathit{j}\mathrm{)}$ -th entry of ${\mathrm{M}}_{{\mathit{r}}_{\mathit{k}}}$ is 1. Let ${\mathrm{v}}_{{\mathit{e}}_{\mathit{i}}}\in {\{0\mathrm{,}1\}}^{|\mathcal{E}|}$ be the one-hot encoded vector of entity ${\mathit{e}}_{\mathit{i}}$ , then ${\mathit{s}}^{\top }={\mathrm{v}}_{{\mathit{e}}_{\mathit{i}}}^{\top }{\mathrm{M}}_{{\mathit{r}}_1}{\mathrm{M}}_{{\mathit{r}}_2}{\mathrm{M}}_{{\mathit{r}}_3}$ is the path features vector [43], where the j-th entry counts the number of unique rule paths following the pattern ${\mathit{r}}_1\wedge {\mathit{r}}_2\wedge {\mathit{r}}_3$ from ${\mathit{e}}_{\mathit{i}}$ to ${\mathit{e}}_{\mathit{j}}$ [12].

For example, every KG entity $\mathit{e}\in \mathcal{E}$ in Fig. 2 is encoded into a $0\text{–}1$ vector of length $|\mathcal{E}|=7$ . For every relation $\mathit{r}\in \mathcal{R}$ and every pair of entities ${\mathit{e}}_{\mathit{i}}\mathrm{,}{\mathit{e}}_{\mathit{j}}\in \mathcal{E}$ , the TensorLog operator relevant to r is define as a sparse matrix ${\mathrm{M}}_{\mathit{r}}$ with its $\mathrm{(}\mathit{i}\mathrm{,}\mathit{j}\mathrm{)}$ -th element being 1 if $\mathrm{(}{\mathit{e}}_{\mathit{i}}\mathrm{,}\mathit{r}\mathrm{,}{\mathit{e}}_{\mathit{j}}\mathrm{)}\in \mathcal{G}$ . Considering the KG in Fig. 2, for the relation $\mathit{r}=\mathtt{auntOf}$ we have

And the rule $\mathtt{sisterOf}\mathrm{(}\mathit{X}\mathrm{,}\mathit{Z}\mathrm{)}\wedge \mathtt{fatherOf}\mathrm{(}\mathit{Z}\mathrm{,}\mathit{Y}\mathrm{)}\Rightarrow \mathtt{auntOf}\mathrm{(}\mathit{X}\mathrm{,}\mathit{Y}\mathrm{)}$ can be simulated by performing the following sparse matrix multiplication:

By setting ${\mathrm{v}}_{{\mathit{x}}_1}={[1\mathrm{,}0\mathrm{,}0\mathrm{,}0\mathrm{,}0\mathrm{,}0\mathrm{,}0]}^{\top }$ as the one-hot vector of ${\mathit{x}}_1$ and multiplying by ${\mathrm{v}}_{{\mathit{x}}_1}^{\top }$ on the left, we obtain ${\mathit{s}}^{\top }={\mathrm{v}}_{{\mathit{x}}_1}^{\top }·M_{r^{\prime }}=[0\mathrm{,}0\mathrm{,}1\mathrm{,}0\mathrm{,}0\mathrm{,}1\mathrm{,}0]$ . The resultant ${\mathit{s}}^{\top }$ selects the row in $M_{r^{\prime }}$ actually identified by ${\mathit{x}}_1$ . By operating right-hand side multiplication with ${\mathrm{v}}_{{\mathit{z}}_1}$ , we get the number of unique paths following the pattern $\mathtt{sisterOf}\wedge \mathtt{fatherOf}$ from ${\mathit{x}}_1$ to ${\mathit{z}}_1$ : ${\mathit{s}}^{\top }·{\mathrm{v}}_{{\mathit{z}}_1}=1$ .

4.1.2. Neural LP

Neural LP [42] inherits the idea of TensorLog. Given a query $\mathit{q}\mathrm{(}\mathit{h}\mathrm{,}\mathit{t}\mathrm{)}$ , after L steps of reasoning, the score of the query induced through rule pattern ${\mathbf{r}}_{\mathit{s}}$ of length L is computed as $$\begin{array}{}\text{(5)}& score\mathrm{(}\mathit{t}|\mathit{q}\mathrm{,}\mathit{h}\mathrm{,}{\mathbf{r}}_{\mathit{s}}\mathrm{)}={\mathrm{v}}_{\mathit{h}}^{\top }{\displaystyle \prod }_{\mathit{l}=1}^{\mathit{L}}{\mathrm{M}}^{\mathit{l}}·{\mathrm{v}}_{\mathit{t}}\mathrm{,}\end{array}$$ where ${\mathrm{M}}^{\mathit{l}}$ is the adjacency matrix of the relation used at the l-th hop.

The operators above are used to learn for query q by calculating the weighted sum of all possible patterns: $$\begin{array}{}\text{(6)}& {\displaystyle \sum }_{\mathit{s}}{\mathit{\alpha }}_{\mathit{s}}{\displaystyle \prod }_{\mathit{k}\in {\mathit{\beta }}_{\mathit{s}}}{\mathrm{M}}_{{\mathit{r}}_{\mathit{k}}}\mathrm{,}\end{array}$$ where s indexes over all potential patterns with maximum length of L, ${\mathit{\alpha }}_{\mathit{s}}$ is the confidence score associated with the rule ${\mathbf{r}}_{\mathit{s}}$ and ${\mathit{\beta }}_{\mathit{s}}$ is the ordered list of relations appearing in ${\mathbf{r}}_{\mathit{s}}$ .

To summarize, we update the score function in Eq. (5) by finding an appropriate α in $$\begin{array}{}\text{(7)}& \mathit{\phi }\mathrm{(}\mathit{t}|\mathit{q}\mathrm{,}\mathit{h}\mathrm{)}={\mathrm{v}}_{\mathit{h}}^{\top }{\displaystyle \sum }_{\mathit{s}}{\mathit{\alpha }}_{\mathit{s}}·\mathrm{(}{\displaystyle \prod }_{\mathit{k}\in {\mathit{\beta }}_{\mathit{s}}}{\mathrm{M}}_{{\mathit{r}}_{\mathit{k}}}·{\mathrm{v}}_{\mathit{t}}\mathrm{)}\mathrm{,}\end{array}$$ and the optimization objective is $$\begin{array}{}\text{(8)}& \underset{{\mathit{\alpha }}_{\mathit{s}}}{max}{\displaystyle \sum }_{\mathrm{(}\mathit{h}\mathrm{,}\mathit{q}\mathrm{,}\mathit{t}\mathrm{)}\in \mathcal{G}}\mathit{\phi }\mathrm{(}\mathit{t}|\mathit{q}\mathrm{,}\mathit{h}\mathrm{)}\mathrm{,}\end{array}$$ where ${\mathit{\alpha }}_{\mathit{s}}$ is to be learned.

Whereas the searching space of learnable parameters is exponentially large, i.e. $\mathit{O}\mathrm{(}|\mathcal{R}{|}^{\mathit{L}}\mathrm{)}$ , direct optimization of Eq. (8) may fall in the dilemma of over-parameterization. Besides, it is difficult to apply gradient-based optimization. This is because each variable ${\mathit{\alpha }}_{\mathit{s}}$ is bound with a specific rule pattern, and it is obviously a discrete work to enumerate rules. To overcome these defects, the parameter of rule ${\mathbf{r}}_{\mathit{s}}$ can be reformulated by distributing the confidence to its inclusive relations at each hop, resulting in a differentiable score function: $$\begin{array}{}\text{(9)}& {\mathit{\varphi }}_{\mathit{L}}\mathrm{(}\mathit{t}|\mathit{q}\mathrm{,}\mathit{h}\mathrm{)}=\mathrm{(}{\mathrm{v}}_{\mathit{h}}^{\top }{\displaystyle \prod }_{\mathit{l}=1}^{\mathit{L}}{\displaystyle \sum }_{\mathit{k}=0}^{|\mathcal{R}|}{\mathit{a}}_{\mathit{k}}^{\mathit{l}}{\mathrm{M}}_{{\mathit{r}}_{\mathit{k}}}\mathrm{)}·{\mathrm{v}}_{\mathit{t}}\mathrm{,}\end{array}$$ where L is a hyperparameter denoting the maximum length of patterns and $|\mathcal{R}|$ is the number of relations in KG. ${\mathrm{M}}_{{\mathit{r}}_0}$ is an identity matrix I that enables the model to include all possible rule patterns of length L or smaller [29].

To perform training and prediction over the Neural LP framework, we should first construct a KG from a large subset of all triplets. Then we remove the edge $\mathrm{(}\mathit{h}\mathrm{,}\mathit{t}\mathrm{)}$ from the graph when facing the query $\mathrm{(}\mathit{h}\mathrm{,}\mathit{q}\mathrm{,}\mathit{t}\mathrm{)}$ , so that the score of t can get rid of the influence imposed from the head entity h directly through the edge $\mathrm{(}\mathit{h}\mathrm{,}\mathit{t}\mathrm{)}$ for the correctness of reasoning.

4.2. Our DegreEmbed model

In this section, we propose our DegreEmbed model based on Neural LP [42] as a combination of models relying on knowledge graph embedding and ILP models where the potential properties of individual entities are considered through a technique we call degree embedding. We discover that the attributes of nodes in a KG can make a difference via observation on their degrees. In Fig. 1, we notice that Mike is a male because he is a nephew of someone, hence it is incorrect indeed to reason by a rule containing a female-type relation starting from Mike. Also, the in-degree (i.e. studyIn) of entity THU proves its identity as a university. Besides, as illustrated in Section 4.1.1, all knowledge of a KG is stored in the relational matrices, which is our aim to reconstruct for harboring type information of entities. For a query $\mathit{q}\mathrm{(}\mathit{h}\mathrm{,}\mathit{t}\mathrm{)}$ , the final score is a scalar obtained by Eq. (9), where the path feature vector is ${\mathit{s}}^{\top }={\mathrm{v}}_{\mathit{h}}^{\top }{\prod }_{\mathit{l}=1}^{\mathit{L}}{\sum }_{\mathit{k}=0}^{|\mathcal{R}|}{\mathit{a}}_{\mathit{k}}^{\mathit{l}}{\mathrm{M}}_{{\mathit{r}}_{\mathit{k}}}$ , and ${\mathrm{v}}_{\mathit{t}}$ selects the t-th element of ${\mathit{s}}^{\top }$ through matrix multiplication. In fact, the vector ${\mathit{s}}^{\top }\in {\mathbb{R}}^{|\mathcal{E}|}$ is a row of matrix ${\prod }_{\mathit{l}=1}^{\mathit{L}}{\sum }_{\mathit{k}=0}^{|\mathcal{R}|}{\mathit{a}}_{\mathit{k}}^{\mathit{l}}{\mathrm{M}}_{{\mathit{r}}_{\mathit{k}}}$ , each value of which is the “influence” passed from head entity h to the regarding entity. As a result, we can consider the attributes of the entity ${\mathit{e}}_{\mathit{i}}$ by changing the i-th row of adjacency matrices from the perspective of the type of degrees of ${\mathit{e}}_{\mathit{i}}$ .

Fig. 3.

An illustration of computing the DegreEmbed operators for the KG shown in Fig. 2. Superscripts (+) and (−) of the labels of degree embedding vectors denote their in and out direction. All DegreEmbed operators are initialized to zero matrices.

For any entity $\mathit{e}\in \mathcal{E}$ , we collect the ones of unique types among all of its in and out degrees separately to form a d-dimensional degree feature vector, where d is the number of unique degrees. Then we project the vector onto a semantic space by looking up in a row-vector embedding matrix ${\mathbf{E}}^{|\mathcal{R}|\times \mathit{m}}$ , and the result is number of d vectors arranged in a matrix $\mathbf{M}\in {\mathbb{R}}^{\mathit{d}\times \mathit{m}}$ , where m is the embedding dimension. The embedding vectors are input into a bidirectional LSTM [13] at different time steps. Finally, we perform attention operation on the hidden state of BiLSTM at the last time step to get the $|\mathcal{R}|$ -dimensional attention vector of e for $1⩽\mathit{i}⩽\mathit{d}$ : $$\begin{array}{}\text{(10)}& {\mathbf{h}}_{\mathit{i}}\mathrm{,}{\mathbf{h}}_{\mathit{d}-\mathit{i}+1}^{\prime }=BiLSTM\mathrm{(}{\mathbf{h}}_{\mathit{i}-1}\mathrm{,}{\mathbf{h}}_{\mathit{d}-\mathit{i}}^{\prime }\mathrm{,}\mathbf{M}\mathrm{)}\mathrm{,}\end{array}$$ where h and ${\mathbf{h}}^{\prime }$ are the hidden states of the forward and backward path LSTMs, with the subscripts denoting their time step, and H, the actual embedding vector of entity e, is obtained by concatenating ${\mathbf{h}}_{\mathit{d}}$ and ${\mathbf{h}}_1^{\prime }$ .

To compute the attention value on each relation imposed by entity e, we have $$\begin{array}{}\text{(11)}& {\mathit{\rho }}_{\mathit{e}}=softmax\mathrm{(}\mathit{WH}+\mathit{b}\mathrm{)}\end{array}$$ Elements in ${\mathit{\rho }}_{\mathit{e}}\in {\mathbb{R}}^{|\mathcal{R}|}$ can be viewed as the weights for relations. At last, we replace the elements that are in the row identified by e and equal 1 in each adjacency matrix ${\mathrm{M}}_{{\mathit{r}}_{\mathit{k}}}$ by the k-th value of ${\mathit{\rho }}_{\mathit{e}}$ . By following the same procedure for the other entities in the KG, we construct a new set of relational matrices ${\mathit{B}}_{{\mathit{r}}_1}\mathrm{,}\dots \mathrm{,}{\mathit{B}}_{{\mathit{r}}_{|\mathcal{R}|}}$ , which are called DegreEmbed operators. The score function shown in Eq. (9) is updated accordingly as follows: $$\begin{array}{}\text{(12)}& {\mathit{\varphi }}_{\mathit{L}}^{\prime }\mathrm{(}\mathit{t}|\mathit{q}\mathrm{,}\mathit{h}\mathrm{)}=\mathrm{(}{\mathrm{v}}_{\mathit{h}}^{\top }{\displaystyle \prod }_{\mathit{l}=1}^{\mathit{L}}{\displaystyle \sum }_{\mathit{k}=0}^{|\mathcal{R}|}{\mathit{a}}_{\mathit{k}}^{\mathit{l}}{\mathrm{B}}_{{\mathit{r}}_{\mathit{k}}}\mathrm{)}·{\mathrm{v}}_{\mathit{t}}\mathrm{,}\end{array}$$ where the ${\mathrm{B}}_{{\mathit{r}}_1}\mathrm{,}\dots \mathrm{,}{\mathrm{B}}_{{\mathit{r}}_{\mathcal{R}}}$ is our new DegreEmbed operators, and ${\mathrm{B}}_{{\mathit{r}}_0}$ is still the identity matrix. The whole process to compute the operators makes it possible to incorporate the information of entities for rule learning models, where the degree feature vector ${\mathit{\rho }}_{\mathit{e}}$ can be viewed as the identification of the entity e. Remarkably, the DegreEmbed operators can be pre-trained due to its belonging to the inner attribute of a KG, thus resulting in a model that can be easily deployed in similar tasks. An overview of computing the DegreEmbed operators is illustrated in Fig. 3

Finally, the confidence scores are learned over the bidirectional LSTM followed by the attention using Eqs (13) and (14) for the temporal dependency among several consecutive steps. The input in Eq. (13) is query embedding from another lookup table. For $1⩽\mathit{i}⩽\mathit{L}$ we have $$\begin{array}{}\text{(13)}& \hfill & {\mathbf{h}}_{\mathit{i}}\mathrm{,}{\mathbf{h}}_{\mathit{L}-\mathit{i}+1}^{\prime }=BiLSTM\mathrm{(}{\mathbf{h}}_{\mathit{i}-1}\mathrm{,}{\mathbf{h}}_{\mathit{L}-\mathit{i}}^{\prime }\mathrm{,}\text{input}\mathrm{)}\mathrm{,}\text{(14)}& \hfill & [{\mathit{a}}_{\mathit{i}\mathrm{,}1}\mathrm{,}\dots \mathrm{,}{\mathit{a}}_{\mathit{i}\mathrm{,}|\mathcal{R}|}]={\mathit{f}}_{\mathit{\theta }}\mathrm{\left(}\right[{\mathbf{h}}_{\mathit{i}}\Vert {\mathbf{h}}_{\mathit{L}-\mathit{i}}^{\prime }\left]\mathrm{\right)}\mathrm{,}\end{array}$$ where $[{\mathit{a}}_{\mathit{i}\mathrm{,}1}\mathrm{,}\dots \mathrm{,}{\mathit{a}}_{\mathit{i}\mathrm{,}|\mathcal{R}|}]$ is the attention vector obtained by performing a linear transformation over concatenated forward and backward hidden states, followed by a softmax operator: ${\mathit{f}}_{\mathit{\theta }}\mathrm{(}\mathit{H}\mathrm{)}=softmax\mathrm{(}\mathit{WH}+\mathit{b}\mathrm{)}$ .

4.3. Optimization of the model

Loss construction. In general, this task of link prediction is treated as a classification of entities to build the loss. For each query $\mathit{q}\mathrm{(}\mathit{h}\mathrm{,}\mathit{t}\mathrm{)}$ in a KG, we first split the objective function Eq. (12) into two parts: target vector ${\mathrm{v}}_{\mathit{t}}$ and prediction vector $$\begin{array}{}\text{(15)}& {\mathit{s}}^{\top }={\mathrm{v}}_{\mathit{h}}^{\top }{\displaystyle \prod }_{\mathit{l}=1}^{\mathit{L}}{\displaystyle \sum }_{\mathit{k}=0}^{|\mathcal{R}|}{\mathit{a}}_{\mathit{k}}^{\mathit{l}}{\mathrm{B}}_{{\mathit{r}}_{\mathit{k}}}\mathrm{,}\end{array}$$ and then our goal is to minimize the cross-entropy loss between ${\mathrm{v}}_{\mathit{t}}$ and ${\mathrm{s}}^{\top }$ : $$\begin{array}{ll}\hfill {\ell }_{\mathit{q}}\mathrm{(}\mathit{h}\mathrm{,}\mathit{t}\mathrm{)}=& -{\displaystyle \sum }_{\mathit{i}=1}^{|\mathcal{E}|}\{{\mathrm{v}}_{\mathit{t}}[\mathit{i}]·log\mathrm{(}\mathrm{s}[\mathit{i}]\mathrm{)}\\ \hfill & +\mathrm{(}1-{\mathrm{v}}_{\mathit{t}}[\mathit{i}]\mathrm{)}·log\mathrm{(}1-\mathrm{s}[\mathit{i}]\mathrm{)}\}\mathrm{,}\end{array}$$ where i indexes elements in vector ${\mathrm{v}}_{\mathit{t}}$ and s.

Low-rank approximation. It can be shown that the final confidences obtained by expanding ${\mathit{\varphi }}_{\mathit{L}}^{\prime }$ are a rank one estimation of the confidence value tensor [29], and low-rank approximation is a popular method for tensor approximation. Hence we follow the work of [29] and rewrite Eq. (12) using rank of T approximation, as shown in Eq. (16). $$\begin{array}{}\text{(16)}& {\mathit{\Phi }}_{\mathit{L}}\mathrm{(}\mathit{t}|\mathit{q}\mathrm{,}\mathit{h}\mathrm{)}=\mathrm{(}{\mathrm{v}}_{\mathit{h}}^{\top }{\displaystyle \sum }_{\mathit{j}=1}^{\mathit{T}}{\displaystyle \prod }_{\mathit{l}=1}^{\mathit{L}}{\displaystyle \sum }_{\mathit{k}=0}^{|\mathcal{R}|}{\mathit{a}}_{\mathit{j}\mathrm{,}\mathit{k}}^{\mathit{l}}{\mathrm{B}}_{{\mathit{r}}_{\mathit{k}}}\mathrm{)}·{\mathrm{v}}_{\mathit{t}}.\end{array}$$

More concretely, we update Eqs (13) and (14), as is shown in Eqs (17) and (18), by deploying number of T BiLSTMs of the same network structure, each of which can extract features from various dimensions. $$\begin{array}{}\text{(17)}& \hfill & {\mathbf{h}}_{\mathit{i}}^{\mathrm{(}\mathit{j}\mathrm{)}}\mathrm{,}{\mathbf{h}}_{\mathit{L}-\mathit{i}+1}^{\prime \mathrm{(}\mathit{j}\mathrm{)}}={BiLSTM}_{\mathit{j}}\mathrm{(}{\mathbf{h}}_{\mathit{i}-1}^{\mathrm{(}\mathit{j}\mathrm{)}}\mathrm{,}{\mathbf{h}}_{\mathit{L}-\mathit{i}}^{\prime \mathrm{(}\mathit{j}\mathrm{)}}\mathrm{,}\text{input}\mathrm{)}\text{(18)}& \hfill & [{\mathit{a}}_{\mathit{i}\mathrm{,}1}^{\mathrm{(}\mathit{j}\mathrm{)}}\mathrm{,}\dots \mathrm{,}{\mathit{a}}_{\mathit{i}\mathrm{,}|\mathcal{R}|}^{\mathrm{(}\mathit{j}\mathrm{)}}]={\mathit{f}}_{\mathit{\theta }}\mathrm{\left(}\right[{\mathbf{h}}_{\mathit{i}}^{\prime \mathrm{(}\mathit{j}\mathrm{)}}\Vert {\mathbf{h}}_{\mathit{L}-\mathit{i}}^{\prime \mathrm{(}\mathit{j}\mathrm{)}}\left]\mathrm{\right)}\mathrm{,}\end{array}$$ where the superscripts of the hidden states identify their bidirectional LSTM.

5. Experiment

In this section, we report the evaluation results of our model on a knowledge graph completion task, where we compare the effectiveness of our model against the state-of-the-art learning systems for link prediction. Meanwhile, as DegreEmbed takes advantage in the interpretability in contrast to embedding-based methods, we also examine the rules mined by DegreEmbed with the help of the indicator saturation, which assesses the quality of rules from the corresponding topological structure of a KG. We show that the top-scored rules mined by our method coincide with those of high saturation scores, which in turn reflect the interpretability of our model. To this end, we use ablation study to show how different components of our model contribute to its performance.

The knowledge graph completion task we use is a canonical one as described in [42]. When training the model, the query and head are part of incomplete triplets for training, and the goal is to find the most possible entity as the answer tail. For example, if nephewOf(Mike, Steve) is missing from the knowledge graph, our goal is to learn rules for reasoning over the existing KG and retrieve Steve when presented with the query nephewOf(Mike, ?).

5.1. Experiment setting

5.1.1. Datasets

To evaluate our method for learning logic rules in heterogeneous KGs, we select the following datasets for knowledge graph completion task:

• FB15K-237 [33], a more challenging version of FB15K [4] based on Freebase [3], a growing knowledge graph of general facts.

• WN18 [9], a subset of knowledge graph WordNet [20,21] constructed for a widely used dictionary.

• Medical Language System (UMLS) [16], from biomedicine, where the entities are biomedical concepts (e.g. organism, virus) and the relations consist of affects and analyzes, etc.

• Kinship [16], containing kinship relationships among members of a Central Australian native tribe.

• Family [16], containing individuals from multiple families that are biologically related.

Statistics about each dataset used in our experiments are presented in Table 1. All datasets are randomly split into 4 files: facts, train, valid and test, and the ratio is 6:2:1:1. The facts file contains a relatively large proportion of the triplets for constructing the KG. The train file is composed of query examples $\mathit{q}\mathrm{(}\mathit{h}\mathrm{,}\mathit{t}\mathrm{)}$ . The valid and test files both contain queries $\mathit{q}\mathrm{(}\mathit{h}\mathrm{,}\mathit{t}\mathrm{)}$ , in which the former is used for early stopping and the latter is for testing. Unlike the case of learning embeddings, our method does not necessarily require the entities in train, valid and test to overlap.

Table 1

Statistics of datasets

Dataset	# Relation	# Entity	# Triplets	# Facts	# Train	# Validation	# Test
FB15K-237	237	14541	310116	204087	68028	17535	20466
WN18	18	40943	151442	106088	35353	5000	5000
Family	12	3007	28356	17615	5868	2038	2835
Kinship	25	104	10686	6375	2112	1099	1100
UMLS	46	135	6529	4006	3009	569	633

5.1.2. Evaluation metrics

During training on the task of knowledge graph completion, for each triplet $\mathrm{(}\mathit{h}\mathrm{,}\mathit{q}\mathrm{,}\mathit{t}\mathrm{)}$ , two queries are designed as $\mathrm{(}\mathit{h}\mathrm{,}\mathit{q}\mathrm{,}?\mathrm{)}$ and $\mathrm{(}?\mathrm{,}\mathit{q}\mathrm{,}\mathit{t}\mathrm{)}$ with answers t and h for data augmentation. During evaluation, for each query, we manually remove the edge $\mathrm{(}\mathit{h}\mathrm{,}\mathit{t}\mathrm{)}$ from KG for the correctness of reasoning results and the score is computed for each entity, as well as the rank of the correct answer. For the computed ranks from all queries, we report the Mean Reciprocal Rank (MRR) and Hit@k under the filtered protocol [4]. MRR averages the reciprocal ranks of the answer entities and Hit@k computes the percentage of how many desired entities are ranked among top k.

When evaluating the interpretability of rules, we choose a set of indicators called macro, micro and comprehensive saturations that measure the probability of a rule pattern occurring in a certain relational subgraph $\mathcal{G}\mathrm{(}\mathit{r}\mathrm{)}$ from different angles. More specifically, these computational methods analyze the reasoning complexity from the inherent attributes of the graph structure G w.r.t. a KG $\mathcal{G}$ .

Definition 3 (Macro Reasoning Saturation).

Given a query $\mathit{q}\in \mathcal{R}$ and the maximum length L of a rule pattern ${\mathbf{r}}_{\mathit{l}}\in {\mathbb{H}}^{\mathit{L}}$ , the macro reasoning saturation of ${\mathbf{r}}_{\mathit{l}}$ in relation to relation q, i.e. ${\mathit{\gamma }}_{\mathit{q}}^{{\mathbf{r}}_{\mathit{l}}}$ , is the percentage of triples $\mathrm{(}{\mathit{h}}_{\mathit{i}}\mathrm{,}\mathit{q}\mathrm{,}{\mathit{t}}_{\mathit{j}}\mathrm{)}$ in subgraph $\mathcal{G}\mathrm{(}\mathit{q}\mathrm{)}$ such that ${\mathbf{r}}_{\mathit{l}}\mathrm{(}{\mathit{h}}_{\mathit{i}}\mathrm{,}{\mathit{t}}_{\mathit{j}}\mathrm{)}\Rightarrow \mathit{q}\mathrm{(}{\mathit{h}}_{\mathit{i}}\mathrm{,}{\mathit{t}}_{\mathit{j}}\mathrm{)}$ .

We can compute the macro reasoning saturation ${\mathit{\gamma }}_{\mathit{q}}^{{\mathbf{r}}_{\mathit{l}}}$ using the following equation: $$\begin{array}{}\text{(19)}& {\mathit{\gamma }}_{\mathit{q}}^{{\mathbf{r}}_{\mathit{l}}}={\displaystyle \frac{|{\mathit{U}}^{{\mathbf{r}}_{\mathit{l}}}|}{{\mathit{n}}^{\mathit{q}}}}\mathrm{,}\end{array}$$ with ${\mathit{U}}^{{\mathbf{r}}_{\mathit{l}}}$ being the set ${\mathit{U}}^{{\mathbf{r}}_{\mathit{l}}}=\{\mathrm{(}\mathit{h}\mathrm{,}\mathit{q}\mathrm{,}\mathit{t}\mathrm{)}|\mathrm{(}\mathit{h}\mathrm{,}\mathit{q}\mathrm{,}\mathit{t}\mathrm{)}\in \mathcal{G}\mathrm{(}\mathit{q}\mathrm{)}\mathrm{,}{\mathbf{r}}_{\mathit{l}}\mathrm{(}\mathit{h}\mathrm{,}\mathit{t}\mathrm{)}\Rightarrow \mathit{q}\mathrm{(}\mathit{h}\mathrm{,}\mathit{t}\mathrm{)}\}$ that collects the factual triplets in $\mathcal{G}\mathrm{(}\mathit{q}\mathrm{)}$ as the reasoning candidates of rule ${\mathbf{r}}_{\mathit{l}}$ , and ${\mathit{n}}^{\mathit{q}}=|\mathcal{G}\mathrm{(}\mathit{q}\mathrm{)}|$ being the number of edges (i.e. the number of triples) in $\mathit{G}\mathrm{(}\mathit{q}\mathrm{)}$ . We can reasonably say that the larger ${\mathit{\gamma }}_{\mathit{q}}^{{\mathbf{r}}_{\mathit{l}}}$ grows, the more likely ${\mathbf{r}}_{\mathit{l}}$ can be as a proper inference of the query q. When ${\mathit{\gamma }}_{\mathit{q}}^{{\mathbf{r}}_{\mathit{l}}}$ equals 1, it means we can reason out every factual triple in $\mathcal{G}\mathrm{(}\mathit{q}\mathrm{)}$ through at least one rule path following the pattern ${\mathbf{r}}_{\mathit{l}}$ .

Definition 4 (Micro Reasoning Saturation).

Given the maximum length L of a rule pattern, we define the micro reasoning saturation of pattern ${\mathbf{r}}_{\mathit{l}}\in {\mathbb{H}}^{\mathit{L}}$ as following. Firstly, for a specific triple $\mathtt{tri}=\mathrm{(}\mathit{h}\mathrm{,}\mathit{q}\mathrm{,}\mathit{t}\mathrm{)}\in \mathcal{G}$ , i.e. ${\mathit{\delta }}_{\mathtt{tri}}^{{\mathbf{r}}_{\mathit{l}}}$ , is the percentage of the paths ${\mathbf{p}}_{{\mathit{l}}_{\mathit{i}}}⊳{\mathbf{r}}_{\mathit{l}}$ such that ${\mathbf{r}}_{\mathit{l}}\mathrm{(}\mathit{h}\mathrm{,}\mathit{t}\mathrm{)}\Rightarrow \mathit{q}\mathrm{(}\mathit{h}\mathrm{,}\mathit{t}\mathrm{)}$ as to all paths from h to t.

The equation to compute ${\mathit{\delta }}_{\mathtt{tri}}^{{\mathbf{r}}_{\mathit{l}}}$ is $$\begin{array}{}\text{(20)}& {\mathit{\delta }}_{\mathtt{tri}}^{{\mathbf{r}}_{\mathit{l}}}={\displaystyle \frac{|{\mathit{V}}^{{\mathbf{r}}_{\mathit{l}}}|}{|{\mathit{V}}^{\mathit{L}}|}}\end{array}$$ where ${\mathit{V}}^{{\mathbf{r}}_{\mathit{l}}}=\{{\mathbf{p}}_{{\mathit{l}}_{\mathit{i}}}|{\mathbf{p}}_{{\mathit{l}}_{\mathit{i}}}⊳{\mathbf{r}}_{\mathit{l}}\mathrm{,}{\mathbf{r}}_{\mathit{l}}\mathrm{(}\mathit{h}\mathrm{,}\mathit{t}\mathrm{)}\Rightarrow \mathit{q}\mathrm{(}\mathit{h}\mathrm{,}\mathit{t}\mathrm{)}\}$ , ${\mathit{V}}^{\mathit{L}}=\{{\mathbf{p}}_{{\mathit{k}}_{\mathit{j}}}|{\mathbf{p}}_{{\mathit{k}}_{\mathit{j}}}⊳{\mathbf{r}}_{\mathit{k}}\mathrm{,}\forall {\mathbf{r}}_{\mathit{k}}\in {\mathbb{H}}^{\mathit{L}}\mathrm{,}{\mathbf{r}}_{\mathit{k}}\mathrm{(}\mathit{h}\mathrm{,}\mathit{t}\mathrm{)}\Rightarrow \mathit{q}\mathrm{(}\mathit{h}\mathrm{,}\mathit{t}\mathrm{)}\}$ . ${\mathit{V}}^{{\mathbf{r}}_{\mathit{l}}}$ denotes the set of rule paths derived from the pattern ${\mathbf{r}}_{\mathit{l}}$ that is able to infer the fact $\mathrm{(}\mathit{h}\mathrm{,}\mathit{q}\mathrm{,}\mathit{t}\mathrm{)}$ , and ${\mathit{V}}^{\mathit{L}}$ involves all the rules with their lengths no longer that L.

Then, we average ${\mathit{\delta }}_{\mathtt{tri}}^{{\mathbf{r}}_{\mathit{l}}}$ over all triples $\mathrm{(}\mathit{h}\mathrm{,}\mathit{q}\mathrm{,}\mathit{t}\mathrm{)}\in \mathcal{G}\mathrm{(}\mathit{q}\mathrm{)}$ and get the micro reasoning saturation of the pattern ${\mathbf{r}}_{\mathit{l}}\in {\mathbb{H}}^{\mathit{L}}$ for query q: $$\begin{array}{}\text{(21)}& {\mathit{\delta }}_{\mathit{q}}^{{\mathbf{r}}_{\mathit{l}}}={\displaystyle \frac{1}{{\mathit{n}}^{\mathit{q}}}}{\displaystyle \sum }_{\mathtt{tri}\in \mathcal{G}\mathrm{(}\mathit{q}\mathrm{)}}{\mathit{\delta }}_{\mathtt{tri}}^{{\mathbf{r}}_{\mathit{l}}}\end{array}$$

In Eqs (19) and (21), ${\mathit{\gamma }}_{\mathit{q}}^{{\mathbf{r}}_{\mathit{l}}}$ and ${\mathit{\delta }}_{\mathit{q}}^{{\mathbf{r}}_{\mathit{l}}}$ assess how the probability to infer q following the pattern ${\mathbf{r}}_{\mathit{l}}$ respectively from a macro and a micro perspective. The higher the two indicators are, the easier for models to gain the inference ${\mathbf{r}}_{\mathit{l}}\mathrm{(}\mathit{h}\mathrm{,}\mathit{t}\mathrm{)}\Rightarrow \mathit{q}\mathrm{(}\mathit{h}\mathrm{,}\mathit{t}\mathrm{)}$ . In order to obtain an overall result, we define the comprehensive reasoning saturation ${\mathit{\eta }}_{\mathit{q}}^{{\mathbf{r}}_{\mathit{l}}}$ by combining the two indicators through multiplication, as revealed in Eq. (22). $$\begin{array}{}\text{(22)}& {\mathit{\eta }}_{\mathit{q}}^{{\mathbf{r}}_{\mathit{l}}}={\mathit{\gamma }}_{\mathit{q}}^{{\mathbf{r}}_{\mathit{l}}}\times {\mathit{\delta }}_{\mathit{q}}^{{\mathbf{r}}_{\mathit{l}}}\end{array}$$ We can imagine that the computation of comprehensive saturation on a certain logical rule ${\mathbf{r}}_{\mathit{l}}$ to infer the relation q involves two procedures: (1) select the triplets $\mathrm{(}\mathit{h}\mathrm{,}\mathit{q}\mathrm{,}\mathit{t}\mathrm{)}$ in subgraph $\mathcal{G}\mathrm{(}\mathit{q}\mathrm{)}$ that imply ${\mathbf{r}}_{\mathit{l}}\mathrm{(}\mathit{h}\mathrm{,}\mathit{t}\mathrm{)}\Rightarrow \mathit{q}\mathrm{(}\mathit{h}\mathrm{,}\mathit{t}\mathrm{)}$ and (2) for each selected triplets, calculate the percentage of rule paths following the pattern ${\mathbf{r}}_{\mathit{l}}$ within all possible paths that imply $\mathit{q}\mathrm{(}\mathit{h}\mathrm{,}\mathit{t}\mathrm{)}$ .

We can take the relation $\mathit{q}=$ auntOf and the rule ${\mathbf{r}}_{\mathit{l}}=$ sisterOf ∧ fatherOf in Fig. 2 as an example to show the computation of saturations. In subgraph $\mathcal{G}\mathrm{(}\mathit{q}\mathrm{)}$ , there are totally three triples (presented in red), thus ${\mathit{n}}^{\mathit{q}}=3$ . For the triple $\mathrm{(}{\mathit{x}}_2\mathrm{,}\mathtt{auntOf}\mathrm{,}{\mathit{z}}_2\mathrm{)}$ , two rule paths can contribute to its inference: wifeOf( ${\mathit{x}}_2$ , ${\mathit{z}}_1$ ) ∧ uncleOf( ${\mathit{z}}_2$ , ${\mathit{z}}_1$ ) and sisterOf( ${\mathit{x}}_2$ , ${\mathit{z}}_3$ ) ∧ fatherOf( ${\mathit{z}}_3$ , ${\mathit{z}}_1$ ). In the same way, we can see there are one and two rule paths for $\mathrm{(}{\mathit{x}}_1\mathrm{,}\mathtt{auntOf}\mathrm{,}{\mathit{z}}_1\mathrm{)}$ and $\mathrm{(}{\mathit{x}}_1\mathrm{,}\mathtt{auntOf}\mathrm{,}{\mathit{z}}_4\mathrm{)}$ respectively. The rule ${\mathbf{r}}_{\mathit{l}}=$ sisterOf ∧ fatherOf appears as an inference among all these three triples, therefore the macro saturation is ${\mathit{\gamma }}_{\mathit{q}}^{{\mathbf{r}}_{\mathit{l}}}=3\mathrm{/}{\mathit{n}}^{\mathit{q}}=100\mathrm{\%}$ . More detailed information can be extracted through computing the micro saturation. The rule ${\mathbf{r}}_{\mathit{l}}$ takes a percentage of 50% among all paths for the triple $\mathrm{(}{\mathit{x}}_2\mathrm{,}\mathtt{auntOf}\mathrm{,}{\mathit{z}}_1\mathrm{)}$ , while 100% and 50% for the other two triples. Thus, the micro saturation of ${\mathbf{r}}_{\mathit{l}}$ for q is ${\mathit{\delta }}_{\mathit{q}}^{{\mathbf{r}}_{\mathit{l}}}=\mathrm{(}0.5+1+0.5\mathrm{)}\mathrm{/}{\mathit{n}}^{\mathit{q}}=67\mathrm{\%}$ . Finally, we can compute the comprehensive saturation ${\mathit{\eta }}_{\mathit{q}}^{{\mathbf{r}}_{\mathit{l}}}={\mathit{\gamma }}_{\mathit{q}}^{{\mathbf{r}}_{\mathit{l}}}\times {\mathit{\delta }}_{\mathit{q}}^{{\mathbf{r}}_{\mathit{l}}}=67\mathrm{\%}$ .

Table 2

Saturations of the Family dataset. ${\mathit{\gamma }}_{\mathit{q}}^{{\mathbf{p}}_{\mathit{l}}}$ , ${\mathit{\delta }}_{\mathit{q}}^{{\mathbf{p}}_{\mathit{l}}}$ , ${\mathit{\eta }}_{\mathit{q}}^{{\mathbf{p}}_{\mathit{l}}}$ are macro, micro and comprehensive saturations. The results relating to a specific relation are sorted by the comprehensive saturation in descending order

We show a small subset of saturations computed from Family dataset in Table 2 for joint evaluation with logical rules mined by our model. More results can be obtained in App. C.

5.1.3. Comparison of algorithms

In experiment, the performance of our model is compared with that of the following algorithms:

• Rule learning algorithms. Since our model is based on neural logic programming, we choose Neural LP and a Neural LP-based method DRUM [29]. We also consider a probabilistic model called RNNLogic [27].

• Embedding-based algorithms. We choose several embedding-based algorithms for comparison of the expressive power of our model, including TransE [4], DistMult [41], ComplEx [34], TuckER [2] and RotatE [32].

The implementations of the above models we use are available at the links listed in App. A.

5.1.4. Model configuration

Our model is implemented using PyTorch [26] and the code will be publicly available. We use the same hyperparameter setting during evaluation on all datasets. The query and entity embedding have the dimension 128 and are both randomly initialized. The hidden state dimension of BiLSTM(s) for entity and degree embedding are also 128. As for optimization algorithm, we use mini-batch ADAM [15] with the batch size 128 and the learning rate initially set to 0.001. We also observe that the whole model tends to be more trainable if we use the normalization skill.

Note that Neural LP [42], DRUM [29] and our method all conform to a similar reasoning framework. Hence, to reach a fair comparison, we ensure the same hyperparameter configuration during experiments on these models, where the maximum rule length L is 2 and the rank T is 3 for DRUM and DegreEmbed, because Neural LP is not developed using the low-rank approximation method.

5.2. Results on KGC task

We compare our DegreEmbed to several baseline models on the KGC benchmark datasets as stated in the Section 5.1.1 and Section 5.1.3. Our results on the selected benchmark datasets are summarized in Table 3 and App. B.

Table 3

Knowledge graph completion performance comparison. Hit@k (H@k) is in %

	Family				Kinship				UMLS
	MRR	H@1	H@3	H@10	MRR	H@1	H@3	H@10	MRR	H@1	H@3	H@10
TransE	.34	7	53	86	.26	1	42	76	.57	28	84	96
DistMult	.58	39	71	91	.51	36	57	87	.73	63	81	90
ComplEx	.83	72	94	98	.61	44	71	92	.79	69	87	95
TuckER	.43	28	52	72	.60	46	70	86	.73	63	81	91
RotatE	.90	85	95	99	.65	50	76	93	.73	64	82	94
RNNLogic	.93	91	95	99	.64	50	73	93	.75	63	83	92
Neural LP	.91	86	95	99	.62	48	69	91	.75	62	86	92
DRUM	.94	90	98	99	.58	43	67	90	.80	66	94	97
DegreEmbed	.95	91	99	100	.70	57	79	94	.80	65	94	98

We notice that except that ComplEx [34] produces the best result among all methods on UMLS under the evaluation of Hit@1, all models are outperformed by DegreEmbed with a clear margin in Table 3, especially on the dataset Kinship where we can see about 10% improvement on some metrics. As expected, incorporating entity embedding enhances the expressive power of DegreEmbed and thus benefits to reasoning on heterogeneous KGs.

In Table 7, our model achieves state-of-the-art performance on WN18. It is intriguing that embedding-based methods provide better predictions on FB15K-237 dataset, with rule based methods, including RNNLogic, Neural LP, DRUM and ours, left behind. As pointed in [9], there are inverse relations from the training data present in the test data in FB15K, which is called the problem of test set leakage, resulting in the variant FB15K-237 where inverse relations are removed. No wonder that methods depending on logic rule learning fails on this dataset. Future work on more effective embedding representation of a node and its neighbor edges is likely to significantly advance the performance of link prediction models based on logic rules.

Notably, DegreEmbed not only is capable of producing state-of-the-art results on KGC task thanks to the degree embedding of entities, but also maintains the advantage of logic rule learning that enables our model to be interpretable to humans, which is of vital significance in current research of intelligent systems. We will show the experiment results on the interpretability of our DegreEmbed model later.

5.3. Interpretability of our model

To demonstrate the interpretability of our method, we first report the logical rules mined by our model and compare them with those by DRUM [29]. Then we visualize the embedding vectors learned through the proposed technique degree embedding to prove its expressive power.

5.3.1. Quality of mined rules

Apart from reaching state-of-the-art performance on KGC task which is largely thanks to the mechanism of entity embedding, our DegreEmbed, as a knowledge graph reasoning model based on logic rule mining, is of excellent interpretability as well. Our work follows the Neural LP [42] framework, which successfully combines structure learning and parameter learning to generate rules along with confidence scores.

In this section, we report evaluation results on explanations of our model where some of the rules learned by DegreEmbed and DRUM are shown. As for evaluation metrics, we use the indicator saturations to objectively assess the quality of mined rules in a computable manner. We conduct two separate KGC experiments for generating the logical rules where the only difference is whether the inverted queries are learned. For better visualization purposes, experiments are done on the Family dataset, while other datasets such as UMLS produce similar results.

We sort the rules by their normalized confidence scores, which are computed by dividing by the maximum confidence of rules for each relation, and show top rules mined by our DegreEmbed and DRUM without augmented queries respectively in Table 4 and Table 5. Saturations of rules according to specific relations are shown in Table 2. For more results of saturations, learned rules w.r.t. both pure and augmented queries, please refer to the Appendix.

Table 4

Top rules without reverse queries mined by DegreEmbed on the Family dataset

Table 5

Top rules without reverse queries mined by DRUM on the Family dataset

By referring to the results given by computing saturations, we can see the rules mined by our model solidly agree with the ones with high saturation level. Meanwhile, our model obviously gets rid of the noises rendered by the heterogeneousness of the dataset through blending entity attributes (e.g. gender of entities) into rule learning. The rules mined for predicting the relation brotherOf, such as brotherOf ∧ sisterOf and brotherOf ∧ brotherOf, all show up with a male-type relation at the first hop. However, there are logically incorrect rules mined by DRUM which are highlighted by red in Table 5. We think this is mainly because DRUM does not take entity attributes in to account. In this case, our DegreEmbed model is capable of learning meaningful rules, which indeed proves the interpretability of our model.

Fig. 4.

A t-SNE plot of the entity embedding of our trained model on Family dataset. Node colors denote their classes (i.e. degree feature vectors).

5.3.2. Learned entity embeddings

To explain the learned degree embedding, we visualize the embeddings vectors of some entities from the Family dataset. We use t-SNE [36] to project the embeddings to two-dimensional space and plot them in Fig. 4. In order to obtain the entity embeddings, we first train our DegreEmbed model on Family with the same hyperparameter settings mentioned in Section 5.1.4, and store the entire entity embedding matrix given by Eq. (10). Then, we classify the entities according to their degree feature vector proposed in Section 4.2 and choose top ten most populated clusters marked with various colors to plot in Fig. 4.

Note that, we use a logarithmic scale for the embedding plot to get better visualization results. In fact, the representation of entities exhibits localized clustering in the projected 2D space, which verifies the capability of our model to encode latent features of entities in heterogeneous KGs through their degrees.

5.4. Ablation study

Fig. 5.

Model performance on Family with the original entity embeddings replaced by pre-trained ones from embedding-based methods. Hit@k is in %. The number inside each bar indicates its Hit@k value.

Fig. 6.

Comparison among DegreEmbed variants with different ranks on three benchmark datasets.

To study the necessity of each component of our method, we gradually change the configuration of each component and observe how the model performance varies.

Degree embedding. In this work, degree embedding is proposed as a new technique of entity embedding for incorporating heterogeneous information in KGs. We successively replace this component with learned entity embeddings from five pre-trained embedding-based models listed in Section 5.1.3 on three datasets. We measure the Hit@1, Hit@3 and Hit@10 metrics and show the results on Family in Fig. 5. Results on another two datasets are placed in the Appendix. In summary, the original model using degree embedding to encode entities produces the best results among all variants. We hypothesis that this is due to the fact that many inner attributes of entities are lost in the embeddings of those variants while DegreEmbed can learn to utilize these features implicitly.

Low-rank approximation. Tensor approximation of rank T enables our model to learn latent features from various dimensions, as show Eqs (17) and (18). We conduct experiments on three datasets and show how model behavior differs with rank ranging from 1 to 4 in Fig. 6. Training curves in Fig. 6(a) imply that model may converge faster with lower training loss as rank goes up. However, Fig. 6(b) demonstrates that higher rank does not necessarily bring better test results. We conjecture that this is because the amount of learnable features of distinct dimensions varies from dataset to dataset, where the choice of rank matters a lot. An intriguing insight can be obtained by combining Fig. 6(a) and Fig. 6(b): training loss degrades as model rank increases while it barely contributes to results on test sets, which provides a view of over-fitting.

6. Conclusions

In this paper, a logic rule learning model called DegreEmbed has been proposed for reasoning more effectively in heterogeneous knowledge graphs, where there exist entities and relations of different types. Based on mining logic rules, DegreEmbed simultaneously leverages latent knowledge of entities by learning embedding vectors for them, where the degrees of the entities are closely observed. Experiment results show that our model benefits from the advantages of both embedding-based methods and rule learning systems, as one can see DegreEmbed outperforms the state-of-the-art models with a clear margin, and it produces high-quality rules with great interpretability. In the future, we would like to optimize the way of entity embedding to increase the expressive power of logic rule learning models for knowledge graph reasoning.