Knowledge Graph Embedding with Iterative Guidance from Soft Rules
Shu Guo1,2 , Quan Wang1,2,3∗ , Lihong Wang4 , Bin Wang1,2 , Li Guo1,2

Institute of Information Engineering, Chinese Academy of Sciences
School of Cyber Security, University of Chinese Academy of Sciences
3
State Key Laboratory of Information Security, Chinese Academy of Sciences
4
National Computer Network Emergency Response Technical Team & Coordination Center of China
1

arXiv:1711.11231v1 [cs.AI] 30 Nov 2017

2

Abstract
Embedding knowledge graphs (KGs) into continuous vector
spaces is a focus of current research. Combining such an embedding model with logic rules has recently attracted increasing attention. Most previous attempts made a one-time injection of logic rules, ignoring the interactive nature between
embedding learning and logical inference. And they focused
only on hard rules, which always hold with no exception and
usually require extensive manual effort to create or validate.
In this paper, we propose 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 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 various confidence levels extracted automatically from the KG. In
the learning process, RUGE iteratively queries rules to obtain
soft labels for unlabeled triples, and integrates such newly labeled triples to update the embedding model. Through this
iterative procedure, knowledge embodied in logic rules may
be better transferred into the learned embeddings. We evaluate RUGE in link prediction on Freebase and YAGO. Experimental results show that: 1) with rule knowledge injected iteratively, RUGE achieves significant and consistent improvements over state-of-the-art baselines; and 2) despite their uncertainties, automatically extracted soft rules are highly beneficial to KG embedding, even those with moderate confidence
levels. The code and data used for this paper can be obtained
from https://github.com/iieir-km/RUGE.

Introduction
Knowledge graphs (KGs) such as WordNet (Miller 1995),
Freebase (Bollacker et al. 2008), YAGO (Suchanek, Kasneci, and Weikum 2007), and NELL (Carlson et al. 2010)
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.
∗

Corresponding author: Quan Wang (wangquan@iie.ac.cn).
Copyright c 2018, Association for the Advancement of Artificial
Intelligence (www.aaai.org). All rights reserved.

Recently, a new research direction termed as knowledge
graph embedding has been proposed and quickly received
massive attention (Nickel, Tresp, and Kriegel 2011; Bordes
et al. 2013; Wang et al. 2014; Lin et al. 2015b; Yang et al.
2015; Nickel, Rosasco, and Poggio 2016; Trouillon et al.
2016). 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 (Weston et al. 2013; Bordes et al. 2014; Zhang
et al. 2016; Xiong, Power, and Callan 2017).
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 (Rocktäschel et al. 2014; Vendrov et al.
2015; Wang and Cohen 2016; Hu et al. 2016). Wang et al.
(2015) and Wei et al. (2015) 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. Rocktäschel
et al. (2015) and Guo et al. (2016) then devised joint learning
paradigms which can inject first-order logic (FOL) into KG
embedding. Demeester et al. (2016) 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 (Rocktäschel, Singh, and Riedel 2015) or regularization terms (Demeester, Rocktäschel, and Riedel 2016).
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 en-

proach 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.

VRIWUXOHV

6RIW/DEHO3UHGLFWLRQ

Related Work

XQODEHOHGWULSOHV
VRIWODEHOV

HPEHGGLQJV
ODEHOHGWULSOHV
KDUGODEHOV

(PEHGGLQJ5HFWLILFDWLRQ

Figure 1: Framework overview. RUGE enables an embedding model to learn simultaneously from labeled triples, unlabeled triples, and soft rules in an iterative manner, where
each iteration alternates between a soft label prediction stage
and an embedding rectification stage.
coded 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 (Galárraga et al.
2013; Galárraga et al. 2015). 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 ap-

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 (Bordes et al. 2013; Wang et al. 2014; Lin et al. 2015b),
simple compositional models which match compositions of
head-tail entity pairs with their relations (Nickel, Tresp, and
Kriegel 2011; Yang et al. 2015; Nickel, Rosasco, and Poggio 2016; Trouillon et al. 2016), and neural networks which
further introduce non-linear layers and deep architectures
(Socher et al. 2013; Bordes et al. 2014; Dong et al. 2014;
Liu et al. 2016). Among these techniques, ComplEx (Trouillon et al. 2016), 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
(Guo et al. 2015; Xie, Liu, and Sun 2016) and textual descriptions (Xie et al. 2016; Xiao, Huang, and Zhu 2017), to
learn more predictive embeddings. See (Wang et al. 2017)
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. (2015) and
Wei et al. (2015) 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. Rocktäschel et al. (2015) and Guo et al. (2016)
then tried to learn KG embeddings jointly from triples and
propositionalized FOL rules. Demeester et al. (2016) 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 (Gardner, Talukdar, and Mitchell 2015), have also been
studied in KG embedding (Neelakantan, Roth, and McCallum 2015; Lin et al. 2015a; Guu, Miller, and Liang 2015).
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. (2014) tried to inject ontological knowledge
from WordNet into word embeddings. Vendrov et al. (2015)
introduced order-embedding to model the partial order structure of hypernymy, textual entailment, and image caption-

ing. Hu et al. (2016) 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.

Learning Resources

universally quantified rule ∀x, y : (x, BornInCountry, y)
⇒ (x, Nationality, y) could be instantiated with two entities EmmanuelMacron and France, and gives a resultant
grounding (EmmanuelMacron, BornInCountry, France)
⇒ (EmmanuelMacron, Nationality, France). Obviously, there could be a huge number of groundings,
especially given a large entity vocabulary 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 O while
conclusion triples are not. That means the aforementioned grounding will be considered as valid if the triple
(EmmanuelMacron, BornInCountry, France) ∈ O but
(EmmanuelMacron, Nationality, France) ∈
/ O. For
Qp
each FOL rule fp , let Gp = {gpq }q=1 denote the set of
its valid groundings. All the premise triples of gpq are
contained in O, but the single conclusion triple is not.
These conclusion triples are further used to construct our
unlabeled triple set 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 L,
unlabeled triples U, and the valid groundings of FOL rules
G = {Gp }P
p=1 , we discuss how to model these triples and
rules in the context of KG embedding. To model triples, we
follow ComplEx (Trouillon et al. 2016), a recently proposed
method which is simple and efficient while achieving stateof-the-art predictive performance. Specifically, we assume
entities and relations to have complex-valued vector embeddings. Given a triple (ei , rk , ej ) ∈ E ×R×E, we score it by
a multi-linear dot product:
X
ηijk = Re(hei , rk , ēj i) = Re(
[ei ]m [rk ]m [ēj ]m ), (1)

Suppose we are given a KG with a set of triples observed,
i.e., O = {(ei , rk , ej )}. Each triple is composed of two entities ei , ej ∈ E and their relation rk ∈ R, where E and 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.
Labeled Triples. We take the triples observed in O as positive ones. For each positive triple (ei , rk , ej ), we randomly
corrupt the head ei or the tail ej , to form a negative triple
(e0i , rk , ej ) or (ei , rk , e0j ), where e0i ∈ E \ {ei } and e0j ∈
E \ {ej }. We denote a labeled triple as x` , and associate with
it a label y` = 1 if x` is positive, and y` = 0 otherwise. Let
L = {(x` , y` )} denote the set of these labeled triples (along
with their labels).
Unlabeled Triples. Besides the labeled triples, we collect a
m
set of unlabeled triples U = {xu }, where xu = (ei , rk , ej )
where ei , ej , rk ∈ Cd are the complex-valued vector emindicates an unlabeled triple. In fact, all the triples that have
beddings associated with ei , ej , and rk , respectively; ēj is
not been observed in O can be taken as unlabeled ones. But
the conjugate of ej ; [·]m is the m-th entry of a vector; and
in this paper, we consider only those encoded in the concluRe(·) means taking the real part of a complex value. We fursion of a soft rule, as detailed below.
ther introduce a mapping function φ : E×R×E → (0, 1), so
Soft Rules. We also consider a set of FOL rules with differas to map the score ηijk to a continuous truth value which
ent confidence levels, denoted as F = {(fp , λp )}P
p=1 . Here,
lies in the range of (0, 1), i.e.,

fp is the p-th logic rule defined over the given KG, repreφ(ei , rk , ej ) = σ(ηijk ) = σ Re(hei , rk , ēj i) , (2)
sented, e.g., in the form of ∀x, y : (x, rs , y) ⇒ (x, rt , y),
where σ(x) = 1/(1 + exp(−x)) denotes the sigmoid funcstating that two entities linked by relation rs might also
tion. Triples with higher truth values are more likely to hold.
be linked by relation rt . The left-hand side of the imTo model propositionalized rules (i.e. groundings), we use
plication “⇒” is called the premise, and the right-hand
t-norm based fuzzy logics (Hájek 1998). The key idea is to
side the conclusion. In this paper, we restrict fp to be
model the truth value of a propositionalized rule as a coma Horn clause rule, where the conclusion contains only
position of the truth values of its constituent triples, through
a single atom and the premise is a conjunction of sevspecific logical connectives (e.g. ∧ and ⇒). For instance,
eral atoms. The confidence level of rule fp is denoted
the truth value of a grounded rule (eu , rs , ev ) ⇒ (eu , rt , ev )
as λp ∈ [0, 1]. Rules with higher confidence levels are
will be determined by the truth values of the two triples
more likely to hold, and a confidence level of λp = 1
(eu , rs , ev ) and (eu , rt , ev ), via a composition defined by
indicates a hard rule which always holds with no exceplogical implication. We follow (Guo et al. 2016) and define
tion. Such rules as well as their confidence levels can be
the compositions associated with logical conjunction (∧),
extracted automatically from the KG (with the observed
disjunction (¬), and negation (¬) as:
triple set O as input), by using modern rule mining systems
like AMIE and AMIE+ (Galárraga et al. 2013; Galárraga et al. 2015).
π(a ∧ b) = π(a) · π(b),
(3)
We then propositionalize these rules to get their groundπ(a ∨ b) = π(a) + π(b) − π(a) · π(b),
(4)
ings. Here a grounding is the logical expression with all variπ(¬a)
=
1
−
π(a).
(5)
ables instantiated with concrete entities in E. For instance, a

Here, a and b are two logical expressions, which can either
be single triples or be constructed by combining triples with
logical connectives; and π(a) is the truth value of a, indicating to what degree the logical expression is true. If a is a
single triple, say (ei , rk , ej ), we have π(a) = φ(ei , rk , ej ),
as defined in Eq. (2). Given these compositions, the truth
value of any logical expression can be calculated recursively
(Guo et al. 2016), e.g.,
π(a ⇒ b) = π(¬a ∨ b) = π(a) · π(b) − π(a) + 1.

(6)

Logical expressions with higher truth values have greater degrees to be true. Let Θ = {e}e∈E ∪ {r}r∈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 L, unlabeled triples U, and valid groundings
{Gp }P
p=1 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 Θ(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 F = {(fp , λp )}P
p=1 , and each FOL rule fp has
Q

p
Qp valid groundings Gp = {gpq }q=1
. Our aim is to predict a
soft label s(xu ) ∈ [0, 1] for each unlabeled triple xu ∈ U, by
using the current embeddings Θ(n−1) and all the groundings
G = {Gp }P
p=1 .
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 xu ∈ U, we calculate its truth value φ(xu )
using the current embeddings via Eq. (2), and require the
soft label s(xu ) to stay close to this truth value. We measure
the closeness between s(xu ) and φ(xu ) with a squared loss,
and try to minimize it. For the second property, we further
impose rule constraints onto the soft labels S = {s(xu )}.
Specifically, for each FOL rule fp and each of its groundings gpq , we expect gpq to be true, i.e., π(gpq |S) = 1 with
confidence λp . Here, π(gpq |S) is the conditional truth value
of gpq given the soft labels, which can be calculated recursively with the logical compositions defined in Eq. (3) to
Eq. (5). Take gpq := (eu , rs , ev ) ⇒ (eu , rt , ev ) as an example, where the premise (eu , rs , ev ) is directly observed in
O, and the conclusion (eu , rt , ev ) is an unlabeled triple included in U. The conditional truth value of gpq can then be
calculated as:

π(gpq |S) = φ(eu , rs , ev )·s(eu , rt , ev )−φ(eu , rs , ev )+1, (7)

where φ(eu , rs , ev ) is a truth value defined by Eq. (2) with
the current embeddings; and s(eu , rt , ev ) is a soft label to be
predicted. Comparing Eq. (7) with Eq. (6), we can see that
during the calculation of π(gpq |S), for any unlabeled triple,

we use the soft label s(·) rather than the truth value φ(·), so
as to better impose rule constraints onto the soft labels S.
Combining the two properties together and further allowing slackness for rule constraints, we finally get the following optimization problem:
X
1 X
2
min
(s(xu ) − φ(xu )) + C
ξpq ,
S,ξ 2
p,q
xu ∈U

s.t. λp (1 − π(gpq |S)) ≤ ξpq , q = 1,· · ·, Qp , p = 1,· · ·, P,
ξpq ≥ 0, q = 1,· · ·, Qp , p = 1,· · ·, P,
0 ≤ s(xu ) ≤ 1, ∀s(xu ) ∈ S,
(8)
where ξpq is a slack variable and C the penalty coefficient.
Note that confidence levels of rules (i.e. λ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 closedform solution:
h
i1
X
s(xu ) = φ(xu ) + C
λp ∇s(xu ) π(gpq |S)
(9)
p,q

0

for each xu ∈ U. Here, ∇s(xu ) π(gpq |S) means the gradient
of π(gpq |S) w.r.t s(xu ), which is a constant w.r.t. S,1 and
[x]10 = min(max(x, 0), 1) is a truncation function enforcing
the solutions to stay within [0, 1]. 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
This stage is to integrate both labeled and unlabeled triples
(with hard and soft labels respectively) to update current embeddings. Specifically, we are given a set of labeled triples
with their hard labels specified in {0, 1}, i.e., L = {(x` , y` )},
and also a set of unlabeled triples encoded in propositionalized rules, i.e., U = {xu }. Each unlabeled triple xu has a
soft label s(xu ) ∈ [0, 1], predicted by Eq. (9). We would
like to use these labeled and unlabeled triples to learn the
updated embeddings Θ(n) . Here n is the iteration index.
To this end, we minimize a global loss over L and U, so
as to find embeddings which can predict the true hard labels
for triples contained in L, while imitating the soft labels for
those contained in U. The optimization problem is:
1 X
1 X
min
`(φ(x` ), y` ) +
`(φ(xu ), s(xu )), (10)
Θ |L|
|U|
L

U

where `(x, y) = −y log x − (1 − y) log(1 − x) is the cross
entropy; and φ(·) is a function w.r.t. Θ defined by Eq. (2).
We further impose L2 regularization on the parameters Θ to
avoid overfitting. Gradient descent algorithms can be used
to solve this problem. Embeddings learned in this way will
1) be compatible with all the labeled triples, and 2) absorb
rule knowledge carried by the unlabeled triples.
1
Note that each gpq contains only a single unlabeled triple, i.e.,
the conclusion triple. Take π(gpq |S) defined in Eq. (7) for example.
In this case, s(xu ) = s(eu , rt , ev ) is the soft label to be predicted
and ∇s(xu ) π(gpq |S) = φ(eu , rs , ev ) is a constant w.r.t. S.

Whole Procedure

Algorithm 1 Iterative Learning Procedure of RUGE

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 Lb , Ub , and Gb from the labeled triples L, unlabeled triples U, and propositionalized rules G, respectively
(line 3).2 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.

Require: Labeled triples L = {(x` , y` )}
Unlabeled triples U = {xu }
FOL rules F={(fp , λp )} and their groundings G={gpq }

Discussions

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. (2013).4 The
latter is extracted from the core facts of YAGO3.5 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 (Dong et al. 2014). 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+ (Galárraga et al. 2015)6 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.7 The length of a Horn clause rule is
the number of atoms appearing in its premise, e.g., ∀x, y :
(x, BornInCountry, y) ⇒ (x, 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

We further analyze the space and time complexity, and discuss possible extensions of our approach.
Complexity. RUGE follows ComplEx to represent entities
and relations as complex-valued vectors, hence has a space
complexity of O(ne d + nr d) which scales linearly w.r.t. ne ,
nr , and d. Here, ne is the number of entities, nr the number of relations, and d the dimensionality of the embedding
space. During the learning procedure, each iteration requires
a time complexity of O(τ (n` d + nu d)), where n` /nu is the
average number of labeled/unlabeled triples in a mini-batch,
and τ the number of inner epochs used for embedding rectification (cf. Eq. (10)). In practice, we usually have nu  n`
(see Table 2 for the number of labeled and unlabeled triples
used on our datasets), and we can also set τ to a very small
value, e.g., τ = 1. That means, RUGE has almost the same
time complexity as those most efficient KG embedding techniques (e.g. ComplEx) which require O(n` d) per iteration
during training.3 In addition, RUGE further requires preprocessing steps before training, i.e., rule mining and propositionalization. But these steps are performed only once, and
not required during the iterations.
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.
2
We first sample Lb from L. Gb is then constructed by those
whose premise triples are all contained in Lb but conclusion triples
are not. These conclusion triples are further used to construct Ub .
3
Such techniques often use SGD in mini-batch mode for training, and sample a mini-batch of n` labeled triples at each iteration.

1: Randomly initialize entity and relation embeddings Θ(0)
2: for n = 1 : N do
3:
Sample a mini-batch Lb / Ub / Gb from L / U / G
4:
Sb ← SoftLabelPrediction (Ub , Gb , Θ(n−1) )
. cf. Eq. (9)
5:
Θ(n) ← EmbeddingRectification (Lb , Ub , Sb ) . cf. Eq. (10)
6: end for
Ensure: Θ(N )

Experiments
We evaluate RUGE in the link prediction task. This task is
to complete a triple (ei , rk , ej ) with ei or ej missing, i.e., to
predict ei given (rk , ej ) or ej given (ei , rk ).

4

https://everest.hds.utc.fr/doku.php?id=en:smemlj12
http://www.mpi-inf.mpg.de/departments/databases-andinformation-systems/research/yago-naga/yago/downloads/
6
https://www.mpi-inf.mpg.de/departments/databases-andinformation-systems/research/yago-naga/amie/
7
AMIE+ provides two types of confidence, i.e. standard confidence and PCA confidence. This paper uses PCA confidence.
5

Table 1: Horn clause rules with confidence levels extracted
by AMIE+ from FB15K (top) and YAGO37 (bottom).
/location/people born here(x,y)⇒/people/place of birth(y,x)
/director/film(x,y)⇒/film/directed by(y,x)
/film/directed by(x,y)∧/person/language(y,z)⇒/film/language(x,z)

1.00
0.99
0.88

isMarriedTo(x,y)⇒isMarriedTo(y,x)
hasChild(x,y)∧isCitizenOf(y,z)⇒isCitizenOf(x,z)
playsFor(x,y)⇒isAffiliatedTo(x,y)

0.97
0.94
0.86

Table 2: Statistics of datasets, where ne /nr denotes the number of entities/relations, n` /nu /ng is the number of labeled
triples/unlabeled triples/valid groundings used for training,
and nv /nt denotes the number of validation/test triples.
Train
Dataset
FB15K
YAGO37

Valid

Test

ne

nr

n`

nu

ng

nv

nt

14,951
123,189

1,345
37

483,142
989,132

74,707
69,680

96,724
72,670

50,000
50,000

59,071
50,000

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 (Bordes
et al. 2013). For each test triple (ei , rk , ej ), we replace the
head entity ei with each entity e0i ∈ E, and calculate the score
for (e0i , rk , ej ). Ranking these scores in descending order,
we get the rank of the correct entity ei . 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 (Bordes et al. 2013).
Comparison Settings. We compare RUGE with four stateof-the-art basic embedding models, including TransE (Bordes et al. 2013), DistMult (Yang et al. 2015), HolE (Nickel,
Rosasco, and Poggio 2016), and ComplEx (Trouillon et al.
2016). These basic models rely only on triples observed in
a KG and use no rules. We further take PTransE (Lin et al.
2015a) and KALE (Guo et al. 2016) 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. (2016)8 for
8

https://github.com/ttrouill/complex

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 (Duchi, Hazan, and
Singer 2011) and gradient normalization. As such, we reproduce the results of TransE, DistMult, and ComplEx reported
on FB15K (Trouillon et al. 2016), and improve the results of
HolE substantially compared to those reported in the original paper (Nickel, Rosasco, and Poggio 2016).9 The code for
PTransE is provided by its authors.10 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 (Nickel, Rosasco, and Poggio 2016). Trouillon et
al. (2016) 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 (Lin et al. 2015a), 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.11
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 α
in {1, 2, 5, 10}, the initial learning rate γ in {0.01, 0.05, 0.1,
0.5, 1.0}, and the L2 regularization coefficient λ 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 δ in
{0.1, 0.2, 0.5, 1, 2, 5, 10}. The slackness penalty C in RUGE
(cf. Eq. (8)) is selected from {0.001, 0.01, 0.1, 1}, and the
number of inner iterations (cf. Eq. (10)) is fixed to τ = 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, α = 10, γ = 0.5, λ = 0.01, C = 0.01 on FB15K; and
d = 150, α = 10, γ = 1.0, λ = 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
9
HolE in its original implementation uses SGD with AdaGrad,
but no gradient normalization.
10
https://github.com/thunlp/KB2E
11
KALE takes all these groundings as hard rules. This approximation works quite well with an appropriate confidence threshold.

Table 3: Link prediction results on the test sets of FB15K and YAGO37. As baselines, rows 1-4 are the four basic models which
use triples alone, and rows 5-6 further integrate logic rules (or relation paths) in a one-time injection manner.
FB15K

YAGO37
HITS@N

HITS@N

Method

MRR

MED

1

3

5

10

MRR

MED

1

3

5

10

TransE
DistMult
HolE
ComplEx
PTransE
KALE

0.400
0.644
0.600
0.690
0.679
0.523

4.0
1.0
2.0
1.0
1.0
2.0

0.246
0.532
0.485
0.598
0.565
0.383

0.495
0.730
0.673
0.756
0.768
0.616

0.576
0.769
0.722
0.793
0.810
0.683

0.662
0.812
0.779
0.837
0.855
0.762

0.303
0.365
0.380
0.417
0.403
0.321

13.0
6.0
7.0
4.0
9.0
9.0

0.218
0.262
0.288
0.320
0.339
0.215

0.336
0.411
0.420
0.471
0.444
0.372

0.387
0.493
0.479
0.533
0.473
0.438

0.475
0.575
0.551
0.603
0.506
0.522

RUGE

0.768

1.0

0.703

0.815

0.836

0.865

0.431

4.0

0.340

0.482

0.541

0.603

Table 4: Runtime (in sec.) on FB15K and YAGO37. Extr. is
the time required for rule/path extraction, Prop. for propositionalization, and Lean. for training per iteration.
FB15K
Method

Figure 2: MRR achieved by RUGE with different confidence
thresholds on the test set of 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.12 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,
12
The other three baselines are implemented in Python and much
slower. So they are not considered here.

ComplEx
PTransE
KALE
RUGE

YAGO37

Extr.

Prop.

Learn.

Extr.

Prop.

Learn.

—
868.4
43.1
43.1

—
—
4.0
4.0

11.4
46.5
4.8
14.1

—
13939.5
337.5
337.5

—
—
13.8
13.8

49.5
23.8
27.5
55.2

we set d = 200 (embedding dimensionality) and α = 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
[Bollacker et al. 2008] Bollacker, K.; Evans, C.; Paritosh, P.;
Sturge, T.; and Taylor, J. 2008. Freebase: A collaboratively created
graph database for structuring human knowledge. In SIGMOD,
1247–1250.
[Bordes et al. 2013] Bordes, A.; Usunier, N.; Garcı́a-Durán, A.;
Weston, J.; and Yakhnenko, O. 2013. Translating embeddings for
modeling multi-relational data. In NIPS, 2787–2795.
[Bordes et al. 2014] Bordes, A.; Glorot, X.; Weston, J.; and Bengio,
Y. 2014. A semantic matching energy function for learning with
multi-relational data. MACH LEARN 94(2):233–259.
[Carlson et al. 2010] Carlson, A.; Betteridge, J.; Kisiel, B.; Settles,
B.; Hruschka Jr, E. R.; and Mitchell, T. M. 2010. Toward an architecture for never-ending language learning. In AAAI, 1306–1313.
[Demeester, Rocktäschel, and Riedel 2016] Demeester,
T.;
Rocktäschel, T.; and Riedel, S. 2016. Lifted rule injection for
relation embeddings. In EMNLP, 1389–1399.
[Dong et al. 2014] Dong, X.; Gabrilovich, E.; Heitz, G.; Horn, W.;
Lao, N.; Murphy, K.; Strohmann, T.; Sun, S.; and Zhang, W. 2014.
Knowledge vault: A web-scale approach to probabilistic knowledge fusion. In SIGKDD, 601–610.
[Duchi, Hazan, and Singer 2011] Duchi, J.; Hazan, E.; and Singer,
Y. 2011. Adaptive subgradient methods for online learning and
stochastic optimization. J MACH LEARN RES 12(Jul):2121–2159.
[Faruqui et al. 2014] Faruqui, M.; Dodge, J.; Jauhar, S. K.; Dyer,
C.; Hovy, E.; and Smith, N. A. 2014. Retrofitting word vectors to
semantic lexicons. arXiv:1411.4166.
[Galárraga et al. 2013] Galárraga, L. A.; Teflioudi, C.; Hose, K.;
and Suchanek, F. M. 2013. AMIE: Association rule mining under
incomplete evidence in ontological knowledge bases. In WWW,
413–422.
[Galárraga et al. 2015] Galárraga, L. A.; Teflioudi, C.; Hose, K.;
and Suchanek, F. M. 2015. Fast rule mining in ontological knowledge bases with AMIE+. VLDB J 24(6):707–730.
[Gardner, Talukdar, and Mitchell 2015] Gardner, M.; Talukdar, P.;
and Mitchell, T. 2015. Combining vector space embeddings with
symbolic logical inference over open-domain text. In AAAI Spring
Symposium Series, 61–65.
[Guo et al. 2015] Guo, S.; Wang, Q.; Wang, L.; Wang, B.; and Guo,
L. 2015. Semantically smooth knowledge graph embedding. In
ACL, 84–94.
[Guo et al. 2016] Guo, S.; Wang, Q.; Wang, L.; Wang, B.; and Guo,
L. 2016. Jointly embedding knowledge graphs and logical rules.
In EMNLP, 192–202.
[Guu, Miller, and Liang 2015] Guu, K.; Miller, J.; and Liang, P.
2015. Traversing knowledge graphs in vector space. In EMNLP,
318–327.

[Hájek 1998] Hájek, P. 1998. The metamathematics of fuzzy logic.
Kluwer.
[Hu et al. 2016] Hu, Z.; Ma, X.; Liu, Z.; Hovy, E.; and Xing, E.
2016. Harnessing deep neural networks with logic rules. In ACL,
2410–2420.
[Lin et al. 2015a] Lin, Y.; Liu, Z.; Luan, H.; Sun, M.; Rao, S.; and
Liu, S. 2015a. Modeling relation paths for representation learning
of knowledge bases. In EMNLP, 705–714.
[Lin et al. 2015b] Lin, Y.; Liu, Z.; Sun, M.; Liu, Y.; and Zhu, X.
2015b. Learning entity and relation embeddings for knowledge
graph completion. In AAAI, 2181–2187.
[Liu et al. 2016] Liu, Q.; Jiang, H.; Evdokimov, A.; Ling, Z.-H.;
Zhu, X.; Wei, S.; and Hu, Y. 2016. Probabilistic reasoning via
deep learning: Neural association models.
[Miller 1995] Miller, G. A. 1995. WordNet: A lexical database for
English. COMMUN ACM 38(11):39–41.
[Neelakantan, Roth, and McCallum 2015] Neelakantan, A.; Roth,
B.; and McCallum, A. 2015. Compositional vector space models for knowledge base completion. In ACL, 156–166.
[Nickel, Rosasco, and Poggio 2016] Nickel, M.; Rosasco, L.; and
Poggio, T. 2016. Holographic embeddings of knowledge graphs.
In AAAI, 1955–1961.
[Nickel, Tresp, and Kriegel 2011] Nickel, M.; Tresp, V.; and
Kriegel, H.-P. 2011. A three-way model for collective learning on
multi-relational data. In ICML, 809–816.
[Rocktäschel et al. 2014] Rocktäschel, T.; Bošnjak, M.; Singh, S.;
and Riedel, S. 2014. Low-dimensional embeddings of logic. In
ACL Workshop on Semantic Parsing, 45–49.
[Rocktäschel, Singh, and Riedel 2015] Rocktäschel, T.; Singh, S.;
and Riedel, S. 2015. Injecting logical background knowledge into
embeddings for relation extraction. In NAACL, 1119–1129.
[Socher et al. 2013] Socher, R.; Chen, D.; Manning, C. D.; and Ng,
A. Y. 2013. Reasoning with neural tensor networks for knowledge
base completion. In NIPS, 926–934.
[Suchanek, Kasneci, and Weikum 2007] Suchanek, F. M.; Kasneci,
G.; and Weikum, G. 2007. YAGO: A core of semantic knowledge.
In WWW, 697–706.
[Trouillon et al. 2016] Trouillon, T.; Welbl, J.; Riedel, S.; Gaussier,
E.; and Bouchard, G. 2016. Complex embeddings for simple link
prediction. In ICML, 2071–2080.
[Vendrov et al. 2015] Vendrov, I.; Kiros, R.; Fidler, S.; and Urtasun, R. 2015. Order-embeddings of images and language.
arXiv:1511.06361.
[Wang and Cohen 2016] Wang, W. Y., and Cohen, W. W. 2016.
Learning first-order logic embeddings via matrix factorization. In
IJCAI, 2132–2138.
[Wang et al. 2014] Wang, Z.; Zhang, J.; Feng, J.; and Chen, Z.
2014. Knowledge graph embedding by translating on hyperplanes.
In AAAI, 1112–1119.
[Wang et al. 2017] Wang, Q.; Mao, Z.; Wang, B.; and Guo, L. 2017.
Knowledge graph embedding: A survey of approaches and applications. IEEE TRANS KNOWL DATA ENG 29(12):2724–2743.
[Wang, Wang, and Guo 2015] Wang, Q.; Wang, B.; and Guo, L.
2015. Knowledge base completion using embeddings and rules.
In IJCAI, 1859–1865.
[Wei et al. 2015] Wei, Z.; Zhao, J.; Liu, K.; Qi, Z.; Sun, Z.; and
Tian, G. 2015. Large-scale knowledge base completion: Inferring via grounding network sampling over selected instances. In
CIKM, 1331–1340.

[Weston et al. 2013] Weston, J.; Bordes, A.; Yakhnenko, O.; and
Usunier, N. 2013. Connecting language and knowledge bases with
embedding models for relation extraction. In EMNLP, 1366–1371.
[Xiao, Huang, and Zhu 2017] Xiao, H.; Huang, M.; and Zhu, X.
2017. SSP: Semantic space projection for knowledge graph embedding with text descriptions. In AAAI, 3104–3110.
[Xie et al. 2016] Xie, R.; Liu, Z.; Jia, J.; Luan, H.; and Sun, M.
2016. Representation learning of knowledge graphs with entity
descriptions. In AAAI, 2659–2665.
[Xie, Liu, and Sun 2016] Xie, R.; Liu, Z.; and Sun, M. 2016. Representation learning of knowledge graphs with hierarchical types.
In IJCAI, 2965–2971.
[Xiong, Power, and Callan 2017] Xiong, C.; Power, R.; and Callan,
J. 2017. Explicit semantic ranking for academic search via knowledge graph embedding. In WWW, 1271–1279.
[Yang et al. 2015] Yang, B.; Yih, W.-t.; He, X.; Gao, J.; and Deng,
L. 2015. Embedding entities and relations for learning and inference in knowledge bases. In ICLR.
[Zhang et al. 2016] Zhang, F.; Yuan, N. J.; Lian, D.; Xie, X.; and
Ma, W.-Y. 2016. Collaborative knowledge base embedding for
recommender systems. In SIGKDD, 353–362.

Knowledge Graph Embedding with Iterative Guidance from Soft Rules:
Supplementary Material
Shu Guo1,2 , Quan Wang1,2,3∗ , Lihong Wang4 , Bin Wang1,2 , Li Guo1,2

Institute of Information Engineering, Chinese Academy of Sciences
School of Cyber Security, University of Chinese Academy of Sciences
3
State Key Laboratory of Information Security, Chinese Academy of Sciences
4
National Computer Network Emergency Response Technical Team & Coordination Center of China
1

2

A

Solving the Soft Label Prediction Problem

We discuss how to solve the soft label prediction problem,
i.e., Eq. (8) in the submission. We first review the problem.
Recall that we are given a set of P FOL rules with their
confidence levels F = {(fp , λp )}P
p=1 , and each FOL rule
Q

p
fp has Qp valid groundings Gp = {gpq }q=1
. The aim is to
predict a soft label s(xu ) ∈ [0, 1] for each unlabeled triple
xu ∈ U, by using the current embeddings Θ(n−1) and all the
groundings G = {Gp }P
p=1 . The optimization problem is:

min
S,ξ

X
1 X
2
(s(xu ) − φ(xu )) + C
ξpq ,
2
p,q
xu ∈U

s.t. λp (1 − π(gpq |S)) ≤ ξpq , q = 1,· · ·, Qp , p = 1,· · ·, P,
ξpq ≥ 0, q = 1,· · ·, Qp , p = 1,· · ·, P,
0 ≤ s(xu ) ≤ 1, ∀s(xu ) ∈ S,
(A-1)

where S = {s(xu )} is the set of soft labels; ξ = {ξpq } the
set of slack variables; φ(xu ) the truth value of xu calculated
by the current embeddings; π(gpq |S) the conditional truth
value of gpq given the soft labels; and C the penalty coefficient. Then, we prove this optimization problem is convex
and has closed-form solutions.

Proof of Convexity
It is easy to see that the objective function is convex, as it
is quadratic w.r.t. each s(xu ) and linear w.r.t. each ξpq . As
for the constraints, note that each valid grounding gpq contains only a single unlabeled triple, i.e., the triple in the conclusion. So the conditional truth value π(gpq |S) is a linear
function w.r.t. a single s(xu ). Take gpq := (eu , rs , ev ) ⇒
(eu , rt , ev ) as an example, where the premise (eu , rs , ev ) is
directly observed, and the conclusion (eu , rt , ev ) is an unlabeled triple with its soft label s(eu , rt , ev ) to be predicted.
The conditional truth value can be calculated as:
π(gpq |S) = φ(eu , rs , ev )·s(eu , rt , ev )−φ(eu , rs , ev )+1,

which is a linear function w.r.t. s(eu , rt , ev ). In this case, all
the constraints are linear functions. So the whole optimization problem is convex.
∗

Corresponding author: Quan Wang (wangquan@iie.ac.cn).

Closed-Form Solutions
The optimization problem of Eq. (A-1) can be equivalently
written as:
X
1 X
2
min
(s(xu ) − φ(xu )) + C
[λp (1 − π(gpq |S))]+ ,
S
2
p,q
xu ∈U

s.t. 0 ≤ s(xu ) ≤ 1, ∀s(xu ) ∈ S,

(A-2)

where [x]+ = max(x, 0). Given the logical compositions defined in Eq. (3) to Eq. (5) in the submission, and the
constraints φ(·) ∈ [0, 1], s(·) ∈ [0, 1] as well, we will have
π(gpq |S) ≤ 1 for any gpq . The objective function of Eq. (A2) then becomes:
X
1 X
2
P=
(s(xu ) − φ(xu )) + C
λp (1 − π(gpq |S)) .
2
p,q
xu ∈U

Recall that each π(gpq |S) is a linear function w.r.t. a single
s(xu ). So P is an upward parabola w.r.t. each s(xu ), with
the axis of symmetry given as:
X
s(xu ) = φ(xu ) + C
λp ∇s(xu ) π(gpq |S).
p,q

Here, ∇s(xu ) π(gpq |S) means the gradient of π(gpq |S) w.r.t
s(xu ), which is a constant w.r.t. S. By further considering
the constraint 0 ≤ s(xu ) ≤ 1 for each s(xu ) ∈ S, we get
the optimal solutions:
h
i1
X
s(xu ) = φ(xu ) + C
λp ∇s(xu ) π(gpq |S) , ∀xu ∈ U,
p,q

0

where
= min(max(x, 0), 1) is a truncation function
enforcing the solutions to stay within [0, 1].
[x]10

