Knowledge Graph Embedding with Iterative Guidance from Soft Rules

Introduction

Knowledge graphs (KGs) such as WordNet (?), Freebase (?), YAGO (?), and NELL (?) are extremely useful resources for many AI related applications. A KG is a multi-relational graph composed of entities as nodes and relations as different types of edges. Each edge is represented as a triple (head entity, relation, tail entity), indicating that there is a specific relation between two entities, e.g., (Paris, CapitalOf, France). Although effective in representing structured data, the underlying symbolic nature of such triples often makes KGs hard to manipulate.

Recently, a new research direction termed as knowledge graph embedding has been proposed and quickly received massive attention (?; ?; ?; ?; ?; ?; ?). The key idea is to embed entities and relations in a KG into a low-dimensional continuous vector space, so as to simplify the manipulation while preserving the inherent structure of the KG. Such embeddings contain rich semantic information, and can benefit a broad range of downstream applications (?; ?; ?; ?).

Traditional methods performed embedding based solely on triples observed in a KG. But considering the power of logic rules in knowledge acquisition and inference, combining embedding models with logic rules has become a focus of current research (?; ?; ?; ?). Wang et al. (?) and Wei et al. (?) tried to use embedding models and logic rules for KG completion. But in their work, rules are modeled separately from embedding models, and would not help to learn more predictive embeddings. Rocktäschel et al. (?) and Guo et al. (?) then devised joint learning paradigms which can inject first-order logic (FOL) into KG embedding. Demeester et al. (?) further proposed lifted rule injection to avoid the costly propositionalization of FOL rules. Although these joint models are able to learn better embeddings after integrating logic rules, they still have their drawbacks and restrictions.

First of all, these joint models made a one-time injection of logic rules, taking them as additional rule-based training instances (?) or regularization terms (?). We argue that rules can better enhance KG embedding, however, in an iterative manner. Given the learned embeddings and their rough predictions, rules can be used to refine the predictions and infer new facts. The newly inferred facts, in turn, will help to learn better embeddings and more accurate logical inference. Previous methods fail to model such interactions between embedding models and logic rules. Furthermore, they focused only on hard rules which always hold with no exception. Such rules usually require extensive manual effort to create or validate. Actually, besides hard rules, a significant amount of background information can be encoded as soft rules, e.g., “a person is very likely (but not necessarily) to have a nationality of the country where he/she was born”. Soft rules can be extracted automatically and efficiently via modern rule mining systems (?; ?). Yet, despite this merit, soft rules have not been well studied in previous methods.

This paper proposes RUle-Guided Embedding (RUGE), a novel paradigm of KG embedding with iterative guidance from soft rules. As sketched in Fig. 1, it enables an embedding model to learn simultaneously from 1) labeled triples that have been directly observed in a given KG, 2) unlabeled triples whose labels are going to be predicted iteratively, and 3) soft rules with different confidence levels extracted automatically from the KG. During each iteration of the learning process, the model alternates between a soft label prediction stage and an embedding rectification stage. The former uses currently learned embeddings and soft rules to predict soft labels for unlabeled triples, and the latter further integrates both labeled and unlabeled triples (with hard and soft labels respectively) to update current embeddings. Through this iterative procedure, knowledge embodied in logic rules may be better transferred into the learned embeddings.

We empirically evaluate RUGE on large scale public KGs, namely Freebase and YAGO. Experimental results reveal that: 1) by incorporating logic rules, RUGE significantly and consistently improves over state-of-the-art basic embedding models (without rules); 2) compared to those one-time injection schemes studied before, the iterative injection strategy maximizes the utility of logic rules for KG embedding, and indeed achieves substantially better performance; 3) despite the uncertainties, automatically extracted soft rules are highly beneficial to KG embedding, even those with moderate confidence levels.

The contributions of this paper are threefold. 1) We devise a novel paradigm of KG embedding which iteratively injects logic rules into the learned embeddings. To our knowledge, this is the first work that models interactions between embedding learning and logical inference in a principled framework. 2) We demonstrate the usefulness of automatically extracted soft rules in KG embedding, thereby eliminating the requirement of laborious manual rule creation. 3) Our approach is quite generic and flexible. It can integrate various types of rules with different confidence levels to enhance a good variety of KG embedding models.

Related Work

Recent years have witnessed increasing interest in learning distributed representations for entities and relations in KGs, a.k.a. KG embedding. Various techniques have been devised for this task, e.g., translation-based models which take relations as translating operations between head and tail entities (?; ?; ?), simple compositional models which match compositions of head-tail entity pairs with their relations (?; ?; ?; ?), and neural networks which further introduce non-linear layers and deep architectures (?; ?; ?; ?). Among these techniques, ComplEx (?), a compositional model which represents entities and relations as complex-valued vectors, achieves a very good trade-off between accuracy and efficiency. Most of the currently available techniques perform the embedding task based solely on triples observed in a KG. Some recent work further tried to use other information, e.g., entity types (?; ?) and textual descriptions (?; ?), to learn more predictive embeddings. See (?) for a thorough review of KG embedding techniques.

Given the power of logic rules in knowledge acquisition and inference, combining KG embedding with logic rules becomes a focus of current research. Wang et al. (?) and Wei et al. (?) devised pipelined frameworks which use logic rules to further refine predictions made by embedding models. In their work, rules will not help to learn better embeddings. Rocktäschel et al. (?) and Guo et al. (?) then tried to learn KG embeddings jointly from triples and propositionalized FOL rules. Demeester et al. (?) further proposed lifted rule injection to avoid the costly propositionalization. These joint models, however, made a one-time injection of logic rules, ignoring the interactive nature between embedding learning and logical inference. Moreover, they can only handle hard rules which are usually manually created or validated.

Besides logic rules, relation paths which can be regarded as Horn clauses and get a strong connection to logical inference (?), have also been studied in KG embedding (?; ?; ?). But in these methods, relation paths are incorporated, again, in a one-time manner. Our approach, in contrast, iteratively injects knowledge contained in logic rules into KG embedding, and is able to handle soft rules with various confidence levels extracted automatically from KGs.

Combining logic rules with distributed representations is also an active research topic in other contexts outside KGs. Faruqui et al. (?) tried to inject ontological knowledge from WordNet into word embeddings. Vendrov et al. (?) introduced order-embedding to model the partial order structure of hypernymy, textual entailment, and image captioning. Hu et al. (?) proposed to enhance various types of neural networks with FOL rules. All these studies demonstrate the capability of logic rules to enhance distributed representation learning.

Rule-Guided Knowledge Graph Embedding

This section introduces RUle-Guided Embedding (RUGE), a novel paradigm of KG embedding with iterative guidance from soft rules. RUGE enables an embedding model to learn simultaneously from labeled triples, unlabeled triples, and soft rules in an iterative manner. During each iteration, the model alternates between a soft label prediction stage and an embedding rectification stage. Fig. 1 sketches this overall framework. In what follows, we first describe our learning resources, and then detail the two alternating stages.

Suppose we are given a KG with a set of triples observed, i.e., $\mathcal{O}=\{(e_{i},r_{k},e_{j})\}$. Each triple is composed of two entities $e_{i},e_{j}\in\mathcal{E}$ and their relation $r_{k}\in\mathcal{R}$, where $\mathcal{E}$ and $\mathcal{R}$ are the sets of entities and relations respectively. We obtain our learning resources (i.e., labeled triples, unlabeled triples, and soft rules) and model them as follows.

Unlabeled Triples. Besides the labeled triples, we collect a set of unlabeled triples $\mathcal{U}=\{x_{u}\}$, where $x_{u}=(e_{i},r_{k},e_{j})$ indicates an unlabeled triple. In fact, all the triples that have not been observed in $\mathcal{O}$ can be taken as unlabeled ones. But in this paper, we consider only those encoded in the conclusion of a soft rule, as detailed below.

Soft Rules. We also consider a set of FOL rules with different confidence levels, denoted as $\mathcal{F}=\{(f_{p},\lambda_{p})\}_{p=1}^{P}$. Here, $f_{p}$ is the $p$-th logic rule defined over the given KG, represented, e.g., in the form of $\forall x,y:(x,r_{s},y)\Rightarrow(x,r_{t},y)$, stating that two entities linked by relation $r_{s}$ might also be linked by relation $r_{t}$. The left-hand side of the implication “$\Rightarrow$” is called the premise, and the right-hand side the conclusion. In this paper, we restrict $f_{p}\;$ to be a Horn clause rule, where the conclusion contains only a single atom and the premise is a conjunction of several atoms. The confidence level of rule $f_{p}$ is denoted as $\lambda_{p}\in$. Rules with higher confidence levels are more likely to hold, and a confidence level of $\lambda_{p}=1$ indicates a hard rule which always holds with no exception. Such rules as well as their confidence levels can be extracted automatically from the KG (with the observed triple set $\mathcal{O}$ as input), by using modern rule mining systems like AMIE and AMIE+ (?; ?).

We then propositionalize these rules to get their groundings. Here a grounding is the logical expression with all variables instantiated with concrete entities in $\mathcal{E}$. For instance, a universally quantified rule $\forall x,y:(x,\texttt{BornInCountry},y)$ $\Rightarrow(x,\texttt{Nationality},y)$ could be instantiated with two entities EmmanuelMacron and France, and gives a resultant grounding $(\texttt{EmmanuelMacron},\texttt{BornInCountry},\texttt{France})$ $\Rightarrow$ $(\texttt{EmmanuelMacron},\texttt{Nationality},\texttt{France})$. Obviously, there could be a huge number of groundings, especially given a large entity vocabulary $\mathcal{E}$. In this paper, to maximize the utility for knowledge acquisition and inference, we take as valid groundings only those where premise triples are observed in $\mathcal{O}$ while conclusion triples are not. That means the aforementioned grounding will be considered as valid if the triple $(\texttt{EmmanuelMacron},\texttt{BornInCountry},\texttt{France})\in\mathcal{O}$ but $(\texttt{EmmanuelMacron},\texttt{Nationality},\texttt{France})\notin\mathcal{O}$. For each FOL rule $f_{p}$, let $\mathcal{G}_{p}=\{g_{pq}\}_{q=1}^{Q_{p}}$ denote the set of its valid groundings. All the premise triples of $g_{pq}$ are contained in $\mathcal{O}$, but the single conclusion triple is not. These conclusion triples are further used to construct our unlabeled triple set $\mathcal{U}$. That means, our unlabeled triples are those which are not directly observed in the KG but could be inferred by the rules with high probabilities.

Modeling Triples and Rules. Given the labeled triples $\mathcal{L}$, unlabeled triples $\mathcal{U}$, and the valid groundings of FOL rules $\mathcal{G}=\{\mathcal{G}_{p}\}_{p=1}^{P}$, we discuss how to model these triples and rules in the context of KG embedding. To model triples, we follow ComplEx (?), a recently proposed method which is simple and efficient while achieving state-of-the-art predictive performance. Specifically, we assume entities and relations to have complex-valued vector embeddings. Given a triple $(e_{i},r_{k},e_{j})\in\mathcal{E}\!\times\!\mathcal{R}\!\times\!\mathcal{E}$, we score it by a multi-linear dot product:

where $\sigma(x)=1/(1+\exp(-x))$ denotes the sigmoid function. Triples with higher truth values are more likely to hold.

To model propositionalized rules (i.e. groundings), we use t-norm based fuzzy logics (?). The key idea is to model the truth value of a propositionalized rule as a composition of the truth values of its constituent triples, through specific logical connectives (e.g. $\wedge$ and $\Rightarrow$). For instance, the truth value of a grounded rule $(e_{u},r_{s},e_{v})\Rightarrow(e_{u},r_{t},e_{v})$ will be determined by the truth values of the two triples $(e_{u},r_{s},e_{v})$ and $(e_{u},r_{t},e_{v})$, via a composition defined by logical implication. We follow (?) and define the compositions associated with logical conjunction ($\wedge$), disjunction ($\neg$), and negation ($\neg$) as:

Here, $a$ and $b$ are two logical expressions, which can either be single triples or be constructed by combining triples with logical connectives; and $\pi(a)$ is the truth value of $a$, indicating to what degree the logical expression is true. If $a$ is a single triple, say $(e_{i},r_{k},e_{j})$, we have $\pi(a)=\phi(e_{i},r_{k},e_{j})$, as defined in Eq. (2). Given these compositions, the truth value of any logical expression can be calculated recursively (?), e.g.,

Logical expressions with higher truth values have greater degrees to be true. Let $\Theta=\{\mathbf{e}\}_{e\in\mathcal{E}}\cup\{\mathbf{r}\}_{r\in\mathcal{R}}$ denote the set of all entity and relation embeddings. The proposed approach, RUGE, then aims to learn these embeddings by using the labeled triples $\mathcal{L}$, unlabeled triples $\mathcal{U}$, and valid groundings $\{\mathcal{G}_{p}\}_{p=1}^{P}$ in an iterative manner, where each iteration alternates between a soft label prediction stage and an embedding rectification stage.

Soft Label Prediction

This stage is to use currently learned embeddings and propositionalized rules to predict soft labels for unlabeled triples. Specifically, let $n$ be the iteration index, and $\Theta^{(n-1)}$ the set of current embeddings learned from the previous iteration. Recall that we are given a set of $P$ FOL rules with their confidence levels $\mathcal{F}=\{(f_{p},\lambda_{p})\}_{p=1}^{P}$, and each FOL rule $f_{p}$ has $Q_{p}$ valid groundings $\mathcal{G}_{p}=\{g_{pq}\}_{q=1}^{Q_{p}}$. Our aim is to predict a soft label $s(x_{u})\in$ for each unlabeled triple $x_{u}\in\mathcal{U}$, by using the current embeddings $\Theta^{(n-1)}$ and all the groundings $\mathcal{G}=\{\mathcal{G}_{p}\}_{p=1}^{P}$.

To do so, we solve a rule-constrained optimization problem, which projects truth values of unlabeled triples computed by the current embeddings into a subspace constrained by the rules. The key idea here is to find optimal soft labels that stay close to these truth values, while at the same time fitting the rules. For the first property, given each unlabeled triple $x_{u}\in\mathcal{U}$, we calculate its truth value $\phi(x_{u})$ using the current embeddings via Eq. (2), and require the soft label $s(x_{u})$ to stay close to this truth value. We measure the closeness between $s(x_{u})$ and $\phi(x_{u})$ with a squared loss, and try to minimize it. For the second property, we further impose rule constraints onto the soft labels $\mathcal{S}=\{s(x_{u})\}$. Specifically, for each FOL rule $f_{p}$ and each of its groundings $g_{pq}$, we expect $g_{pq}$ to be true, i.e., $\pi(g_{pq}|\mathcal{S})\!=\!1$ with confidence $\lambda_{p}$. Here, $\pi(g_{pq}|\mathcal{S})$ is the conditional truth value of $g_{pq}$ given the soft labels, which can be calculated recursively with the logical compositions defined in Eq. (3) to Eq. (5). Take $g_{pq}:=(e_{u},r_{s},e_{v})\Rightarrow(e_{u},r_{t},e_{v})$ as an example, where the premise $(e_{u},r_{s},e_{v})$ is directly observed in $\mathcal{O}$, and the conclusion $(e_{u},r_{t},e_{v})$ is an unlabeled triple included in $\mathcal{U}$. The conditional truth value of $g_{pq}$ can then be calculated as:

where $\phi(e_{u},r_{s},e_{v})$ is a truth value defined by Eq. (2) with the current embeddings; and $s(e_{u},r_{t},e_{v})$ is a soft label to be predicted. Comparing Eq. (7) with Eq. (6), we can see that during the calculation of $\pi(g_{pq}|\mathcal{S})$, for any unlabeled triple, we use the soft label $s(\cdot)$ rather than the truth value $\phi(\cdot)$, so as to better impose rule constraints onto the soft labels $\mathcal{S}$.

Combining the two properties together and further allowing slackness for rule constraints, we finally get the following optimization problem:

where $\xi_{pq}$ is a slack variable and $C$ the penalty coefficient. Note that confidence levels of rules (i.e. $\lambda_{p}$’s) are encoded in the constraints, making our approach capable of handling soft rules. Rules with higher confidence levels show less tolerance for violating the constraints. This optimization problem is convex, and can be solved efficiently with its closed-form solution:

for each $x_{u}\in\mathcal{U}$. Here, $\nabla_{s(x_{u})}\pi(g_{pq}|\mathcal{S})$ means the gradient of $\pi(g_{pq}|\mathcal{S})$ w.r.t $s(x_{u})$, which is a constant w.r.t. $\mathcal{S}$,Note that each $g_{pq}$ contains only a single unlabeled triple, i.e., the conclusion triple. Take $\pi(g_{pq}|\mathcal{S})$ defined in Eq. (7) for example. In this case, $s(x_{u})=s(e_{u},r_{t},e_{v})$ is the soft label to be predicted and $\nabla_{s(x_{u})}\pi(g_{pq}|\mathcal{S})=\phi(e_{u},r_{s},e_{v})$ is a constant w.r.t. $\mathcal{S}$. and $[x]_{0}^{1}=\min(\max(x,0),1)$ is a truncation function enforcing the solutions to stay within $$. We provide the proof of convexity and detailed derivation as supplementary materials. Soft labels obtained in this way shall 1) stay close to the predictions made by the current embedding model, and 2) fit the rules as well as possible.

Embedding Rectification

To this end, we minimize a global loss over $\mathcal{L}$ and $\mathcal{U}$, so as to find embeddings which can predict the true hard labels for triples contained in $\mathcal{L}$, while imitating the soft labels for those contained in $\mathcal{U}$. The optimization problem is:

Whole Procedure

Algorithm 1 summarizes the iterative learning procedure of our approach. To enable efficient learning, we use an online scheme in mini-batch mode. At each iteration, we sample a mini-batch $\mathcal{L}_{b}$, $\mathcal{U}_{b}$, and $\mathcal{G}_{b}$ from the labeled triples $\mathcal{L}$, unlabeled triples $\mathcal{U}$, and propositionalized rules $\mathcal{G}$, respectively (line 3).We first sample $\mathcal{L}_{b}$ from $\mathcal{L}$. $\mathcal{G}_{b}$ is then constructed by those whose premise triples are all contained in $\mathcal{L}_{b}$ but conclusion triples are not. These conclusion triples are further used to construct $\mathcal{U}_{b}$. Soft label prediction and embedding rectification are then conducted locally on these mini-batches (line 4 and line 5 respectively). This iterative procedure captures the interactive nature between embedding learning and logical inference: given current embeddings, logic rules can be used to perform approximate inference and predict soft labels for unlabeled triples; these newly labeled triples carry rich rule knowledge and will in turn help to learn better embeddings. In this way, knowledge contained in logic rules can be fully transferred into the learned embeddings. Note also that our approach is flexible enough to handle soft rules with various confidence levels extracted automatically from the KG.

Discussions

We further analyze the space and time complexity, and discuss possible extensions of our approach.

Extensions. Our approach is quite generic and flexible. 1) The idea of iteratively injecting logic rules can be applied to enhance a wide variety of embedding models, as long as an appropriate scoring function is accordingly designed, e.g., the one defined in Eq. (1) by ComplEx. 2) Various types of rules can be incorporated as long as they can be modeled by the logical compositions defined in Eq. (3) to Eq. (5), and we can even use other types of t-norm fuzzy logics to define such compositions. 3) Rules with different confidence levels can be handled in a unified manner.

Experiments

We evaluate RUGE in the link prediction task. This task is to complete a triple $(e_{i},r_{k},e_{j})$ with $e_{i}$ or $e_{j}$ missing, i.e., to predict $e_{i}$ given $(r_{k},e_{j})$ or $e_{j}$ given $(e_{i},r_{k})$.

Datasets. We use two datasets: FB15K and YAGO37. The former is a subgraph of Freebase containing 1,345 relations and 14,951 entities, released by Bordes et al. (?).https://everest.hds.utc.fr/doku.php?id=en:smemlj12 The latter is extracted from the core facts of YAGO3.http://www.mpi-inf.mpg.de/departments/databases-and-information-systems/research/yago-naga/yago/downloads/ During the extraction, entities appearing less than 10 times are discarded. The final dataset consists of 37 relations and 123,189 entities. Triples on both datasets are split into training, validation, and test sets, used for model training, hyperparameter tuning, and evaluation, respectively. We use the original split for FB15K, and draw a split of 989,132/50,000/50,000 triples for YAGO37.

Note that on both datasets, the training sets contain only positive triples. Negative triples are generated using the local closed world assumption (?). This negative sampling procedure is performed at runtime for each batch of training positive triples. Such positive and negative triples (along with their hard labels) form our labeled triple set.

We further employ AMIE+ (?)https://www.mpi-inf.mpg.de/departments/databases-and-information-systems/research/yago-naga/amie/ to automatically extract Horn clause rules from each dataset, with the training set as input. To enable efficient extraction, we consider rules with length not longer than 2 and confidence levels not less than 0.8.AMIE+ provides two types of confidence, i.e. standard confidence and PCA confidence. This paper uses PCA confidence. The length of a Horn clause rule is the number of atoms appearing in its premise, e.g., $\forall x,y:$ $(x,\texttt{BornInCountry},y)\Rightarrow(x,\texttt{Nationality},y)$ has the length of 1. And the confidence threshold of 0.8 leads to the best performance on both datasets (detailed later). Using this setting, we extract 454 (universally quantified) Horn clause rules from FB15K, and 16 such rules from YAGO37. Table 1 shows some examples with their confidence levels.

Then, we instantiate these rules with concrete entities, i.e., propositionalization. Propositionalized rules whose premise triples are all contained in the training set (while conclusion triples are not) are taken as valid groundings and used during embedding learning. We obtain 96,724 valid groundings on FB15K and 72,670 on YAGO37. Conclusion triples of these valid groundings are further collected to form our unlabeled triple set. We finally get 74,707 unlabeled triples on FB15K and 69,680 on YAGO37. Table 2 provides some statistics of the two datasets.

Evaluation Protocol. To evaluate the performance in link prediction, we follow the standard protocol used in (?). For each test triple $(e_{i},r_{k},e_{j})$, we replace the head entity $e_{i}$ with each entity $e_{i}^{\prime}\!\in\!\mathcal{E}$, and calculate the score for $(e_{i}^{\prime},r_{k},e_{j})$. Ranking these scores in descending order, we get the rank of the correct entity $e_{i}$. Similarly, we can get another rank by replacing the tail entity. Aggregated over all test triples, we report three metrics: 1) the mean reciprocal rank (MRR), 2) the median of the ranks (MED), and 3) the proportion of ranks no larger than $n$ (HITS@N). During this ranking process, we remove corrupted triples which already exist in either the training, validation, or test set, since they themselves are true triples. This corresponds to the “filtered” setting in (?).

Comparison Settings. We compare RUGE with four state-of-the-art basic embedding models, including TransE (?), DistMult (?), HolE (?), and ComplEx (?). These basic models rely only on triples observed in a KG and use no rules. We further take PTransE (?) and KALE (?) as additional baselines. Both of them are extensions of TransE, with the former integrating relation paths (Horn clauses), and the latter FOL rules (hard rules) in a one-time injection manner. In contrast, RUGE incorporates soft rules and transfers rule knowledge into KG embedding in an iterative manner.

We use the code provided by Trouillon et al. (?)https://github.com/ttrouill/complex for TransE, DistMult, and ComplEx, and reimplement HolE so that all these four basic models share the identical mode of optimization, i.e., SGD with AdaGrad (?) and gradient normalization. As such, we reproduce the results of TransE, DistMult, and ComplEx reported on FB15K (?), and improve the results of HolE substantially compared to those reported in the original paper (?).HolE in its original implementation uses SGD with AdaGrad, but no gradient normalization. The code for PTransE is provided by its authors.https://github.com/thunlp/KB2E We implement KALE and RUGE in Java, both using SGD with AdaGrad and gradient normalization to facilitate a fair comparison.

There are two types of loss functions that could be used for these baselines, i.e., the logistic loss or the pairwise ranking loss (?). Trouillon et al. (?) have recently demonstrated that the logistic loss generally performs better than the pairwise ranking loss, except for TransE. So, for TransE and its extensions (PTransE and KALE) we use the pairwise ranking loss, and for all the other baselines we use the logistic loss. To extract relation paths for PTransE, we follow the optimal configuration reported in (?), where paths constituted by at most 3 relations are included. For KALE and RUGE, we use the same set of propositionalized rules to make it a fair comparison.KALE takes all these groundings as hard rules. This approximation works quite well with an appropriate confidence threshold.

For all the methods, we create 100 mini-batches on each dataset, and tune the embedding dimensionality $d$ in $\{50,$ $100,150,200\}$, the number of negatives per positive triple $\alpha$ in $\left\{1,2,5,10\right\}$, the initial learning rate $\gamma$ in $\{0.01,0.05,0.1,$ $0.5,1.0\}$, and the $L_{2}$ regularization coefficient $\lambda$ in $\{0.001,$ $0.003,0.01,0.03,0.1\}$. For TransE and its extensions which use the pairwise ranking loss, we further tune the margin $\delta$ in $\{0.1,0.2,0.5,1,2,5,10\}$. The slackness penalty $C$ in RUGE (cf. Eq. (Soft Label Prediction)) is selected from $\{0.001,0.01,0.1,1\}$, and the number of inner iterations (cf. Eq. (10)) is fixed to $\tau=1$. Best models are selected by early stopping on the validation set (monitoring MRR), with at most 1000 iterations over the training set. The optimal configurations for RUGE are: $d=$ $200$, $\alpha=10$, $\gamma=0.5$, $\lambda=0.01$, $C=0.01$ on FB15K; and $d=150$, $\alpha=10$, $\gamma\!=\!1.0$, $\lambda\!=\!0.003$, $C\!=\!0.01$ on YAGO37.

Link Prediction Results. Table 3 shows the results of these methods on the test sets of FB15K and YAGO37. The results indicate that RUGE significantly and consistently outperforms all the baselines on both datasets and in all metrics. It beats not only the four basic models which use triples alone (TransE, DistMult, HolE, and ComplEx), but also PTransE and KALE which further incorporate logic rules (or relation paths) in a one-time injection manner. This demonstrates the superiority of injecting logic rules into KG embedding, particularly in an iterative manner. Compared to the best performing baseline ComplEx (this is also the model based on which RUGE is designed), RUGE achieves an improvement of 11%/18% in MRR/HITS@1 on FB15K, and an improvement of 3%/6% on YAGO37. The improvements on FB15K are more substantial than those on YAGO37. The reason is probably that FB15K contains more relations from which a good range of rules can be extracted (454 universally quantified rules from FB15K, and 16 from YAGO37).

Influence of Confidence Levels. We further investigate the influence of the threshold of rules’ confidence levels used in RUGE. To do so, we fix all the hyperparameters to the optimal configurations determined by the previous experiment, and vary the confidence threshold in $[0.1,1]$ with a step 0.05. Fig. 2 shows MRR achieved by RUGE with various thresholds on the test set of FB15K. We can see that the threshold of 0.8 is a good tradeoff and indeed performs best. A threshold higher than that will reduce the number of rules that can be extracted, while a one lower than that might introduce too many less credible rules. Both hurt the performance. However, even so, RUGE outperforms ComplEx by a large margin, with the threshold set in a broad range of $[0.35,0.9]$. This observation indicates that soft rules, even those with moderate confidence levels, are highly beneficial to KG embedding despite their uncertainties.

Comparison of Runtime. Finally, we compare RUGE with ComplEx, PTransE, and KALE in their runtime.The other three baselines are implemented in Python and much slower. So they are not considered here. ComplEx is a basic model which only requires model training. RUGE as well as the other two baselines further require preprocessing of rule/path extraction and propositionalization. Table 4 lists the runtime of these methods required for each step on FB15K and YAGO37. Here, to facilitate a fair comparison, we set $d\!=\!200$ (embedding dimensionality) and $\alpha\!=\!2$ (number of negatives per positive triple) for all the methods. Other hyperparameters are fixed to their optimal configurations determined in link prediction. We can see that RUGE is still quite efficient despite integrating additional rules. The average training time per iteration increases from 11.4 to 14.1 on FB15K, and from 49.5 to 55.2 on YAGO37. The preprocessing steps, although performed only once, are also highly efficient, requiring much less time compared to PTransE.

Conclusion

This paper proposes a novel paradigm that learns entity and relation embeddings with iterative guidance from soft rules, referred to as RUGE. It enables an embedding model to learn simultaneously from labeled triples, unlabeled triples, and soft rules in an iterative manner. Each iteration alternates between 1) a soft label prediction stage which predicts soft labels for unlabeled triples using currently learned embeddings and soft rules, and 2) an embedding rectification stage which further integrates both labeled and unlabeled triples to update current embeddings. This iterative procedure may better transfer the knowledge contained in logic rules into the learned embeddings. Link prediction results on Freebase and YAGO show that RUGE achieves significant and consistent improvements over state-of-the-art baselines. Moreover, RUGE demonstrates the usefulness of automatically extracted soft rules. Even those with moderate confidence levels can be highly beneficial to KG embedding.

Acknowledgments

The authors would like to thank all the reviewers for their insightful and valuable suggestions, which significantly improve the quality of this paper. This work is supported by the National Key Research and Development Program of China (grants No. 2016YFB0801003 and No. 2016QY03D0503), the Fundamental Theory and Cutting Edge Technology Research Program of the Institute of Information Engineering, Chinese Academy of Sciences (grant No. Y7Z0261101), and the National Natural Science Foundation of China (grant No. 61402465).

References