EM-RBR: a reinforced framework for knowledge graph completion from reasoning perspective
Authors: Bozhou Chen
Zhaochong An
Houde Quan
Qihui Lin
Hongzhi Wang
Venue:  (2021)
Keywords: knowledge graph completion
bread first search

Abstract: Knowledge graph completion aims to predict the new links in given entities among the knowledge graph (KG). Most mainstream embedding methods focus on fact triplets contained in the given KG, however, ignoring the rich background information provided by logic rules driven from knowledge base implicitly. To solve this problem, in this paper, we propose a general framework, named EM-RBR(embedding and rule-based reasoning), capable of combining the advantages of reasoning based on rules and the state-of-the-art models of embedding. EM-RBR aims to utilize relational background knowledge contained in rules to conduct multi-relation reasoning link prediction rather than superficial vector triangle linkage in embedding models. By this way, we can explore relation between two entities in deeper context to achieve higher accuracy. In experiments, we demonstrate that EM-RBR achieves better performance compared with previous models on FB15k, WN18 and our new dataset FB15k-R, especially the new dataset where our model perform futher better than those state-of-the-arts. We make the implementation of EM-RBR available at https://github.com/1173710224/link-prediction-with-rule-based-reasoning.

Under review as a conference paper at ICLR 2021
A REINFORCED FRAMEWORK FOR KNOWL- EDGE GRAPH COMPLETION FROM REASONING PER- SPECTIVE
EM-RBR:
Anonymous authors Paper under double-blind review
ABSTRACT
Knowledge graph completion aims to predict the missing links among the knowl- edge graph (KG).i... predicting the possibility that a certain triple belongs to the knowledge graph. Most mainstream embedding methods focus on fact triplets contained in the given KG, however, ignoring the rich background information provided by logic rules driven from knowledge base implicitly. Limited to the modeling of algebraic space, contradictory in expressing certain relational pat- terns usually exists in the embedding models. Therefore, the representation of the knowledge graph is incomplete and inaccurate. To solve this problem, in this paper, we propose general framework, named EMM-BRR(embeddee based reasoning), capable of combining the advantages of reasoning based on rules and the state-of-the-are models of embedding. EM-RBR aims to utilize rela- tional background knowledge contained in rules to conduct multi-relation reason- ing link prediction. this way, we can find the most reasonable explanation for a given triplet to obtain higher prediction accuracy. In experiments, we demon- strate that EM-RBA achieves better performance compared with previous models on FB 15,,, WN18 8 and our new dataset FB 15k-R, R, especially the new dataset where our model perform futher better than those ttae We make the imple- mentation of EM-RBR available at
and rule-
com/ link Link-predictions with withh-ruleee based reasonireanninnnn
INTRODUCTION
Knowledge graph (KG) has the ability convey knowledge about the world and express the knowl- edge in structured representation. The rich structured information provided by knowledge graphs has become extremely useful resources for many Artificial Intelligence related applications like query expansion (Graupmann et al. 2005). word sense disambiguation (Wasserman Pritsker et al. 2015), information extraction (Hoffmann et al. 2011). etc. A typical knowledge representation in KG is multi-relational data, stored in RDF format, e.g. (Paris, Capital-Of, France). However, due the discrete nature of the logic facts (Wang & Cohen 2016), the knowledge contained in the KG is meant be incomplete (Sadeghian 2019).. Consequently, knowledge graph completion(KGC) has received more and more attention, which attempts to predict whether a new triplet is likely to belong the knowledge graph (KG) by leveraging existing triplets of the KG.
Currently, the popular embedding- based KGC methods aim at embedding entities and relations in knowledge graph a wwwdemmnniionll latent feature space. The implicit relationships between enti- ties can be inferred by comparing their representations in this vector space. These researchers (Bor-) des et al. 2013) Mikolov al.) 2013 Wang et al., 2014 Jí al.) 2015 Lin al.) 2015) Nguyen et al. 2017) make their own contributions for more reasonable and competent embedding. But the overall effect is highly correlated with the density of the knowledge graph. Because embedding method always fails to predict weak and hidden relations which low frequency. The embedding will converge to a solution that is not suitable for triplets owned weak relations, since the training set the hidden relations can covert the testing target to a casier one. For example, there is an existing triplet (Paul. Leader-Of, SoccerTeam) and rule Leader-Ofte Of(x,)) Member-Of(x..)) which indicates the leader of soccer
for embedding cannot contain all factual triplets. However, reasoning

---

Under review as a conference paper at ICLR 2021
team is also member of sport team. Then can apply the rule on the triplet to obtain new triplet (Paul, Member-of, SportTeam) even if the relation Member-of of is weak in knowledge graph.
Besides, some innovative models try to harness rules for better prediction. Joint models (Rocktäschel ct al. 2013; Wang et al.) 2019; Guo et al. 2016) utilize the rules loss functions of translation models and get a better embedding representation of entities and relations. An optimization based on ProPPR (Wang & Cohen 2016) embeds rules and then uses those embedding results to calculate the hyper-parameters of ProPPR. These efforts all end up on getting better embedding from rules and triplets, rather than solving completion through real rule-based reasoning. which is necessary to address weak relation prediction as mentioned before. Compared with them, EM-RBB can perform completion from the reasoning perspective.
Usually, there are some contradictions in the mathematical space of existing embedding-bedd mod- els. Take transE (Bordes et al., 2013) and RotatE (Sun et al. 2019) as examples. For the relation pattern R(x, y) = Rly. x), i.e., symmetrical relation, transE cannot model as described in |Sun al. (2019). While RotatE can not model some relation pattern. For example, transitive relation I?, w.r.t R( y) A R(y, z) + R(x, 2). We assume that the embedding of the relation R under RotatE eiOn, abbreviated as Formula is necessary and sufficient to transitivity. So we will get , r, which means that cº00R= = 1, so 0 = 0, R E 2x). 0g = 0 denotes that is a reflexive relation. That is all the embedding of the transitive relation will be trained to have the nature of the reflexive relation, which is out of our expect.
r-
(1)
In addition to the above problems, transE and RotatE models cannot model data that has multiple relations between two entities. TransR (Lin et al.) 2015) can solve this problem by training the relationship as transformation matrix. But none of them can solve the problem that entity has the same relation with multiple other entities. For example, there are two triples (4, r, 4 (1), (h, r, (2) in the knowledge graph(/1 * 12). For the transE model, h r is fixed result. So wrong equation T1 will exist under transE model. The other two mathematical models are no exception.
The nhove-mentioned shortcomings can be solved by defining the relation pattern in rule directly. Morivated by this, We propose a novel framework EM-RBR combing embedding and rule-based reasoning, which heuristic search essentially. In the development of the joint framework EM- RBR, we meet two challenges. On the one hand, we use AMIE (Galárraga et al., 2013) to auto-mine large amount of rules but not manually. However, these rules automatically mined sometimes are not completely credible. Therefore, it is necessary to propose reasonable way to measure rules to pick proper rules when reasoning. On the other hand, it is known that traditional reasoning- based methods will give only 0 or to one triplet indicate acceptance rejection for the given knowledge graph. This conventional qualitative analysis lacks the quantitative information as the embedding models. So the result of EM-RBR need to reflect the probability one triplet belonging to the knowledge graph.
Three main contributions in EM-RBR are summarized as follows:
EM-RBR is flexible and general enough to be combined with a lot of embedding models.
We propose a novel reasoning algorithm, which can distinguish a given triplet with other wrong triplets better.
We propose a novel rating mechanism for auto-mined reasoning rules and each rule will be measured properly in framework.
In the remaining of this paper, we will explain how our model works in Section 2 experiments in
Section 3 and related work in Section
2
METHOD
Our motivation is to use rules to make up for the shortcomings of embedding model. When the mathematical space of a certain embedding model is not enough to represent a certain relation pat- tern, the relation pattern can be declared through rules. For example, for the symmetric relationship R, we declare a rule R(I, y) + R(y, z). When scoring certain triple (a, R, b) under transE model, we can take min min(s(a, R b), sb, R,a) as the The final score of the triple. This is equivalent
2

---

Under review as a conference paper at ICLR 2021
Test set
Step
Step
black box
Knowledge
Reasoning
(A.
Gule embeddings
Knowledge base
1h, 3) (.)
h. fl (.)
Rule S
Embaddlings
2a 2 7b 2a 7b
entty
relation
21 7ar
3a 8f 70 76
Step
Pa
Step 3
Embedding model
Embeddings
Rule embeddinng
entiy
reledon
conbedding
Figure I: An overview of our framework.
to finding another triple that can explain the rationality of this triple through rules. Although the relation between the new triplet and the original triplet cannot be expressed the algebraic space of embedding, the most reasonable explanation can be found through rules to solve the defects of the model.
The core idea of our framework is to conduct multi-relation path prediction in deeper context from reasoning perspective, that the form of heuristic search. Before explaining the concrete reason- ing algorithm, let's take overview of our framework in Section 2.1
2.1 OVERVIEW
Definition 2.1. Rule: A rule in our framework is in the form of Bi B1 z) A B2(2,y) = ((x v) or B(x, y) H (xx,)) y).
We model knowledge graph as collection of facts G ((h, th,, E E, E RJ, where & and R represent the set entities and relations in the knowledge graph, respectively. The steps of our framework are follows corresponding to Figure [
Step 1. We invoke embedding model get a Set (R(EE+|R)) containing the k-dimensional embedding entities and relations in G.
Step 2. We apply AMIE (Galárraga et 2013) on G to get the reasoning rule set Q where each rule meets Definition
Step 3. The reasoning rules are measured based on the embedding of relations contained in the rule, which will explained Secion 2.2.2
Step 4. Reasoning conducted for given triplet (h, r, (), which will be described in Section 2.2
2.2 REASONING ALGORITIMM
Definition 2.2. initial state:
Initial state is represented as set consisting of single triplet, i.e. (hh, r, t)). state: According to the initial state and the state's 's expansion method described in Section 2.2.1 each state is represented set triples.
This reasoning algorithm is the core our framework and it's a heuristic search. The input this algorithm is triplet (h, r, t). State in the search space is as Definition 2.2 Each state has two
3

---

Under review as a conference paper at ICLR 2021
scores, i.e. H and C. H.. is the heuristic score of state and C is the score of the state. The calculation of scores is explained in Section 2.2.2
The target of search is to compute (h(hhr:t) (h, r, t). The score & of triplet meets + 2 1. The smaller is, the triplet belongs to knowledge graph with greater probability.
( (h, t)} for specific triple
The pseudo code of search is as shown in Appendix B
We use priority queue Q to store states in ascending order of H. The initial state is the target triplet itself, whose is 1. Push the initial state into Q and then begin the loop until is empty.
During the search process, pop the top of Q as the current state Scur. It will not be extended Hozur 2 4, otherwise we will extend it by matching rules to get new states. For each new state Snews compute its score H Hsnow and L Henor < B the state will then be pushed into Q.
2.2.1 MATCHING AND EXTENSION
State is a set of triplets, the initial state is the target triplet itself. Intermediate states are extended from the initial state. So essentially, the extension of state is extension of the triplets in the state. For triplet (h, r, t), the process of matching and extension is roughly as follows:
1. Find rules Ω in the form of B1 (Ir, 2) B2(2.9)
H< where H
2. Assign entities variables in the rule, i.e. h,y -.
3. Find all 20 that satisfy (x, Bi, E G or (zo, B2,8) E G. where x = h,y= L.
4. (h,r, () is extended to {hh, B1, =o), (Zo, B2, A triplet always has multiple extensions.
For example, we expand the target triplet in the initial state. There are two triplets in the sub-state, and either of them must be the knowledge graph. When the sub-state is further expanded, the triplet in the knowledge graph need not to be expanded. Therefore, there should be m + triplets in each sub-state after extending m times. And at least m of them belong to the knowledge graph.
2.2.2 COMPUTATION OF AND
Hoo (h, r, t) denotes the heuristic score of triplet (h, r, t) when extended to state O and Lw r,t) the corresponding state score.
II (h, HEE
w(BI, H. w.r.t, w(BI, B2, H) + || + m2 M||
(h, r) is defined as Equation indicating the product of the scores of all the rules, Apoth represents the set of the rules used in the extension from the initial state to the current state. w(B,, B2, H) is the score of rules in the shape of B₁ A B2 + H.
f r, -
Hoo(h,r
II
Sutransx (O,,, O,,
(3)
(O..O...,EEO
(hoth, t) is defined as Equation 3 indicating the product of Hholh, r, t) and the scores of all the triplets in the state. O denotes the state and (On, O,. O2) is a triplet belongs to O. Sutranss (O,, O,, Oi) is the embedding score of this triplet as defined in Equation 4
S-tranex (On Or, O,) = |1 + O. - O+1l/k+1 +1
if (On, O,, E
if
(4)
E.)
Rule's 's score
To evaluate the score of rule B1 (1x 2) B2(2.y) v) H (2., y). we visualize the three triplets of this rule in a two-dimensional space in Figure of Appendix A In our model, if rule has a high confidence, it should satisfy || + - yll s | B₁ x z B₂ yll. We have so we can use [ + B2 H to evaluate the score of the rule. k is the dimension of embedding.
B1 B2.
'The rules we analyzed here are in the form of Bı =) A B2(2. = H(x,)) As for rules like B(r,)) = Hs, y), the process is similar and will not be overtalked here.
4

---

Under review as a conference paper at ICLR 2021
The smaller score, the higher confidence. To make the dimension in the calculation uniform, divide the score of the rule by k. And then perform the exponential transformation to get the form in the Equation
2
The reason for this transformation will be explained in section 2.4
Tripler's score
||0, + - | is the score of triplet (O,, Or, O,,Ot) O+) in transE mode The smaller the value, the more likely the triplet in G. When (O,, (O, E G, the score is assumed to be O. The same to rule's score, also perform a certain transformation on the scores of the triplets, which is divide by k and add 1.
2.3 EXAMPLE
Assumption 2.1. We put all the necessary message in Table 3 and Apart from that, make two assumptions. One is that we use the same symbol T4 to represent a rule 's symbol and rule't 's score. Another is that we define some data relations Equation
rirars Cmaa r1 & (h, > (~
(5)
>
72R
103
6+
R76
2
thane min 1 (hars) C (h, rt)]
min (Pa(a Curg (h.r.))
min (airr)) Lives (1, 1)3
=Lony (1.
Co (li,
r,
V
120
n2
2357
x0
((hnt)
(hirt) min (hors)))))) Cerns (,,,
Dninnd min (U-(a)))) (h,
min (Ratheng) Con (h.m
0}
II (h,
=0w(hs)))
Figure 2: Demonstration of the search process based on an example. The search process is divided into six stages, each stage is contained in a sub-graph, each sub-graph contains three parts. The top of the sub- aab-graph shows the current state of the priority queue, the middle part is the visualization of the search, the formula for updating 4 (h.rr.)))) at each stage is given at the bottom.
In this section, we use an example to illustrate our algorithm as shown in Figure The initial state 8p only contains one triplet (h, r, (), and its state score and heuristic score are both 1. At the beginning, the priority queue Q has only one element, i.c. the initial state with its scores. The search process is as follows, and the necessary message is defined in Assumption 2.
so matches 71 and r2 and extends to s1 and $2 respectively. $2 a termination state for the triplets in are all in G. We use L (h, () to update (h.hh. and push into Q.
II. Pop the top of queue $1. Use it update (..(h.);))) and then extend it to three states which will be pushed to Q.
HHere we take transP as an example, so we use | + O, Oell. If combined model changes, this formula should change to the form in the combined model, too. TTheee will be some conflicts in the usage of symbols. For these symbols, it's only valid in this example.
5

---

Under review as a conference paper at ICLR 2021
III. Pop the top of queue 83 to update (=)),r;))) and extend it with matching the rule rs. Since
Ti > Linag (h, r, i.e. the solution produced by this path will not be the global minimum. As consequence, this state is no longer extended.
IV. Pop the top of queue 84 to update & P~(h,,,)) and extend to get two new states $6, 87.
V. Pop the top of queue S6 update Φ P~(h,n,)) and extend to after the rule
VI. Pop the top of queue $7 and now H~wr r, r). > P~ So 87 and the remaining states in Q need not extend. Therefore, all the remaining states in Q become termination states. The search stops.
2.4 ANALYSE
IS THE ALGORITHM SURE TO BE EFFECTIVE?
For three real number a, b, cla,bbc.. 1), it's possible that c a=b=1. Consider triplet (h, t) and rule B (z, 2) A Bg (2, y) = H(x,)) w H. represents the score (h, r, t), a represents the score of the nule, represents the score of the expanded graph, and represents the score the expanded new triplet that the knowledge graph. Then the score of (h, r, will be reduced evaluate (h, r, t).
triplet that not in the knowledge
b, i.c. we use the new expanded triplets and the rule to
Of course, this optimization will be effective only on the correct triplets. For the wrong triplets, in this
another wrong triplet with large score will be obtained after rule matching. So occasion is a very unlikely event. As result, the correct triplets are optimized, and the wrong triplets will generally not be optimized. Therefore, from macro perspective, the ranking of the correct triplets will increase.
IS THIS ALGORITHM A TERMINATING ALGORITHM?
The heuristic score of state is the product of scores of all the rules along the reasoning path. The scores of the rules are all number greater than 1, when search path long enough, H must be greater than 4. So the search must be able to stop.
WHAT IS THE PRINCIPLE WHEN DESIGNING THE CALCULATION OF RULES AND TRIPLETS?
From the above, we require that the scores of rules and triplets are greater than and close 1. Given that each dimension of embedding obtained by the translation model is number less than and close to O, we divide the score by the corresponding dimension & and then add meet our requirements. In addition, in order to highlight the importance of rules in the calculation, we use exponential changes for rules instead of plus
3 EXPERIMENT
We would like to prove two things. One is that EM-RBR is valid reinforced model, i.e. EM- RBR(X) model always performs better than X model. Another is that EM-RBR will beat all of the current state-of-the-arts data set with rich rules.
3.1 EXPERIMENT SETUP
FB15k237 (Toutanova & Chen 2015) and WNI8RR (Dettmers et al. 2017). We propose data set FB15k- whose test set contains rich rule information as described in Appendix
Dataset: We evaluate EM-RBR on FB15k, WN18 (Bordes al. 2013).
We use number of commonly used metrics, including Mean Rank (MR), Mean Recip- rocal Rank (MRR), and Hit ratio with cut-off values n = 1.10. MR measures the average rank of all correct entities and MRR is the average inverse rank for correct entities. Hits @ measures the proportion of correct entities the top n entities. MR is always greater or equal to and the lower MR indicates better performance, while MRR and Hits @ scores always range from 0.0 to 1.0 and
Metrics:

---

Under review as a conference paper at ICLR 2021
Table 1: Experimental results on FB15K WNI8 and FB15k-R test set. [+]:E-R(E) denotes EM-
RBR(E), indicating that the embedding model in this experimental group is transE. [+] We don't t
We:
use here because it's time-consuming and not better than transE on WN18 reported in Lin al.
2017).
FB15k
WN18
FB15k237
Model
MR
MRR
H@1
H@
MR
MRR
H@1
H@ T0
MR
MRR
HΦ
H@
TransE
70.3
45.77
29.98
74.27
200.9
57.47
23.21
97.68
310.2
21.57
12.45
40.4
TransH
72.56
45.81
30.37
74.01
210.7
61.94
32.03
97.49
319
22.18
13.12
40.77
TransR
55.98
47.88
31.1
77.04
*--
431.3
23.49
15.35
39.96
TransD
56.41
47.88
32.48
75.99
202.8
60.35
29.6
97.37
(E-R(E)
68.36
50.01
34.44
76.23
198.1
85.23
73.94
97.83
301.9
25.26
16.5
42.83
E-R(H)
70.72
52.39
38.82
76.52
201.4
84.57
74.97
96.48
311.8
25.58
16.81
43.09
E-R(R)
55.47
51.93
35.86
78.35
422.1
25.58
17.54
41.61
E-R(D) 55.21
53.02
38.25
78.33
201.8
84.63
75.21
97.5
higher score reflects better prediction results. We use filtered setting protocol (Bordes al. 2013 i.e, filtering out any corrupted triples that appear in the KB to avoid possibly flawed evaluation.
Baseline: To demonstrate the effectiiveness of EM-RBR, we compare with number of compet- itive baselines: TransE (Bordes et al.) 2013). TransH (Wang et al. 2014). TransR (Lin et al., 2013). TransD (Ji al. 2015). RUGE (uoo al., 2017). ComplEx (Touillon al.) 2016). Dist- Mult (Kaleec et al. 2017) and MINERVA (Das et al. 2011aa) Among these state-of-arty TransE, TransH, TransR and Trans are combined with our reasoning framework. These models are eval- uated on 4 standard datasets prove that our framework is real reinforced framework. In the end, all the baselines and combined models are evaluated on FB15k-R.
Implementation: For TransE, TransH, TransR and TransD, we set the same parameters, i.e., the dimensions of embedding = 100, learning rate = 0.001, the margin y = 1. We traverse all the training triplets for 1000 rounds. Other parameters of models are set as the same with the parameters in the published works [Bordes et al. 2013 Wang et al., 2014 Lin et al. 2015 For RUGE, we set the embedding dimension & 100 and other hyper- syper-parameters
the same with Guo et al. (2017 [ For ComplEx and DistMult, all the parameters are consistent with Trouillon et al. 2016 For MINERVA,
the implementation of Das al. (201aa
3.2 EXPERIMENT RESULTS
Firstly, compare EM- (M-R with transX model FB15k, WN18, FB15k237 and WN18RR. Experimental Results are shown in Table 6 Among the four datasets, the performance on WN18RR not optimized much cause this dataset is too sparse and its result is shown in E
When evaluating on FB WN18 and FB 153--233, our model has improved all the metrics com- pared with the translation model in the baseline, especially MRR and Hits @1 each dataset. For example, EM-RBR(D) improve Hits @ on WN18 from 0.296 to 0.752 compared to transD. While our EM-RBR doesn't 't have obvious optimization on WN18RR, cause the dataset is too sparse. We have show the experiment result in Appendix P
Secondly, we compare all the baselines mentioned above FB15k-R, each triplet in this data set can match lot of rules so that they can be optimized extremely under EM-RBR. The result is in Table 2 Among those baselines, MINERVA shows the best performance for the test set is rich in rules. While the performance is further optimized compared to MINERVA.

---

Under review as a conference paper at ICLR 2021
Table 2: Experimental results on FB15k-R.
Model
TransE
TransH
TransR
TransD
RotatE
RUGE
ComplEx
DistMult
MINERVA
MRR
26.11
30.43
18.51
26.16
33.29
49.14
51.1
46.2
57.3
Hits @
14.9
18.25
7.65
14
20.05
33.05
35.8
30.2
42.2
Hits @ 10
48.1
54.95
36.7
50.45
59.75
78.2
79
77.1
84.9
Model
(M-RBR((ranSE)
(taan(())
((aRBR((ranRR)
(M-RBR(rannSD
MRR
79.88
85.61
86.01
82.04
Hits@1 |
65.1
75.45
74.3
70.45
Hits @ 10
96.4
97.8
99.2
96.15
3.3 RESULT ANALYSIS
Actually, only a small part of triples in the test set optimized. FB15k, the ratio of this optimiza- tion is 1/6. Various metrics have been improved much even with this small ratio. The capabilities of our model can be fully demonstrated on the FB15k-R, because each triplet this set has many rules that can be matched to obtain good optimization effect. We have recorded each triple's s rank under transX and EMRBR(X) respectively as shown in Appendix
4 RELATED WORK
For the path-based methods, Lao et al. (201I) uses Path Ranking Algorithm (PRA) (Lao & Cohen 2010) to estimate the probability of an unseen triplet combination of weighted random walks.
Zhang et al. (2020) and (Qu & Tang 2019) are both the combination Markov logic network and embedding. Kok & Domingos (207) mainly clustering algorithm, clustering entity sets under multiple relationship categories. Garrdner et al. (2014) makes use of an external text corpus to increase the connectivity of KB. The Neural T.P model (Yang al.] 2017) compiles inferen- tial tasks into differentiable numerical matrix sequences. Besides, many studies have modeled the path-finding problem as Markov decision-making process, such as the DeepPath model (Xiong et al. 2)17) and MINERVA (Das et al. 2017b). For the embedding methods, Nguyen (2017) has organized the existing work. Our paper divides all embedding methods into four categories, which are: translation, Bilinear & Tensor, neural network and complex vector. Firstly, for translation, the Unstructured model (Bordes et al. 2014) assumes that the head and tail entity vectors are similar without distinguishing relation types. The Structured Embedding (SE) model (Bordes et al. 201T) assumes that the head and tail entities are similar only in a relation-dependent subspace. Later, there transE, transR, transH (Bordes et al. 2013 Lin al. 2015; Wang et al.) (014)) etc. [Sadeghian jet al. (2019) mines first-order logical rules from knowledge graphs and uses those rules to solve KBC. Additionally, other work (Yang et al., 2017 Galárraga al. 2013)
extract some high- quality rules from knowledge base. For the second type, DISTMULT (Yang et al. 2014) is based on the Bilinear model (Nickel al. [201T) where each relation is represented by diagonal matrix rather than a full matrix. SimplE (Kazemi & Poole 20018) extends CP models (Hitchcock 1927) to allow two embeddings of each entity be learned dependently. The third method is implement embedding with neural network. Apart from the models mentioned in Section [ NTN (Socher al. 2013) and ER-MIPP (Dong al. 2014) also belong to this method. Fourthly, instead of em- bedding entities and relations in real-valued vector space, ComplEx (Trouillon et al. 2016) is an extension of DISTMULT in the complex vector space. ComplEx-N3 (Lacroix et al. 2018)) extends ComplEx with weighted nuclear 3-norm. Also in the complex vector space, RotatE (Sun et al. 2019 defines each relation as a rotation from the head entity to the tail entity. QuatE (Zhang et al,
2019 represents entities by quaternion embeddings (i.e., hypercomplex-valuee embeddings) and models relations as rotations in the quaternion space.
5
CONCLUSION & FUTURE WORK
This paper introduces an innovative framework called EM-RBR combining embedding and rule- based reasoning, which can be easily integrated with any translation based embedding model. Unlike
8

---

Under review as a conference paper at ICLR 2021
previous joint models trying get better embedding results from rules and triplets, model allows solving completion from the reasoning perspective by conducting multi-relation path prediction, ie. breadth first search. We also demonstrate that EM-RBR can efficiently improve the performance of emhedding methods for KGC. This makes the existing translation based embedding methods more suitable and reliable be used in the real and large scale knowledge inference tasks.
There are two possible directions in the future. On one hand, we will combine our model with more embedding models, not just the translation-based embedding model. On the other hand, are going to extract more and more reliable association rules to optimize our work. As mentioned above, only part of triples are optimized when evaluating on FB15k. The fundamental reason for the rest is that there is no corresponding rule for matching. If these two problems are solved, EM-RBR can be better improved.

---

Under review as a conference paper at ICLR 2021
REFERENCES
Antoine Bordes, Jason Weston, Ronan Collobert, and Yoshua Bengio. Learning structured embed- dings of knowledge bases. In Twenty-Fifth AAAI Conference on Artificial Intelligence. 2011.
Antoine Bordes, Nicolas Usumier, Alberto Garcia-Duran, Jason Weston, and Oksana Yakhnenko. Translating embeddings for modeling multi nulti-relational data. In Advances in neural information processing systems, pp. 2787-2795, 2013.
Antoine Bordes, Xavier Glorot, Jason Weston, and Yoshua Bengio. A semantic matching energy function for learning with multi-relational data. Machine Learning, 94(2):233-259, 2014.
Rajarshi Das, Shehzaad Dhuliawala, Manzil Zaheer, Luke Vilnis, Ishan Durugkar, Akshay Krishna- murthy, Alex Smola, and Andrew Mccallum. Go for a walk and arrive at the answer: Reasoning paths in knowledge bases using reinforcement learning. 11 2017a.
Rajarshi Das, Shehzaad Dhuliawala, Manzil Zaheer, Luke Vilnis, Ishan Durugkar, Akshay Krish- namurthy, Alexander J. Smola, and Andrew McCallum. Go for a walk and arrive at the answer: Reasoning over paths in knowledge bases using reinforcement learning. CoRR, abs/171 1.05551, 2017b.
Tim Dettmers, Pasquale Minervini, Pontus Stenetorp, and Sebastian Riedel. Convolutional 2d knowledge graph embeddings. In 32nd AAAI Conference on Artificial Intelligence (AAAI-18), 2-7 February 2018, New Orleans, LA, USA, 2017.
Xin Dong, Evgeniy Gabrilovich, Geremy Heitz, Wilko Horn, Ni Lao, Kevin Murphy, Thomas Strohmann, Shaohua Sun, and Wei Zhang. Knowledge vault: web-scale approach to proba- bilistic knowledge fusion. In Proceedings the 20th ACM SIGKDD international conference Knowledge discovery and data mining, pp. 601-610, 2014.
Luis Antonio Galárraga, Christina Teffioudi, Katja Hose, and Fabian Suchanek. Amie: association rule mining under incomplete evidence in ontological knowledge bases. In Proceedings of the 22nd international conference on World Wide Web, pp. 413-422, 2013.
Matt Gardner, Partha Talukdar, Jayant Krishnamurthy, and Tom Mitchell. Incorporating vector space similarity in random walk inference over knowledge bases. In Proceedings of the 2014 conference on empirical methods in natural language processing (EMNLP), 397-406, 2014.
Jens Graupmann, Ralf Schenkel, and Gerhard Weikum. The spheresearch engine for unified ranked retrieval of heterogeneous xml and web documents. volume 2, pp. 529-540, 01 2005.
Shu Guo, Quan Wang, Lihong Wang, Bin Wang, and Li Guo. Jointly embedding knowledge graphs and logical rules. In Proceedings of the 2016 Conference on Empirical Methods in Natural Lan- guage Processing, pp. 192,202, 2016.
Shu Guo, Quan Wang, Lihong Wang, Bin Wang, and Li Guo. Knowledge graph embedding with iterative guidance from soft rules. arXiv preprint arXiv:1711.112311 2017.
Frank I. Hitchcock. The expression of tensor polyadic sum of products. Journal of Mathematics and Physics, 6(1 611441114-118, 1927.
Raphael Hoffmann, Congle Zhang, Xiao Ling, Luke Zettlemoyer, and Daniel S. Weld. Knowledge- based weak supervision for information extraction of overlapping relations. In Proceedings of the 49th Anmual Meeting of the Association for Computational Linguistics: Human Language Technologies Volume 1, HLT '11, pp. 541-550, USA, 2011. Association for Computational Linguistics. ISBN 9781932432879.
Guoliang Ji, Shizhu He, Liheng Xu, Kang Liu, and Jun Zhao. Knowledge graph embedding via dynamic mapping matrix. Proceedings of the 53rd Annual Meeting of the Association for Computational Linguistics and the 7th International Joint Conference on Natural Language Pro- cessing (Volume 1: Long Papers), pp. 687-696. 2015.
Rudolf Kadlec, Ondrej Bajgar, and Jan Kleindienst. Knowledge base completion: Basclines strike back. arXiv preprint arXiv: 1705. 1705.10744. 2017.
10

---

Under review as a conference paper at ICLR 2021
Seyed Mehran Kazemi and David Poole. Simple embedding for link prediction in knowledge graphs In Advances in neural information processing systems, pp. 4284 4295, 2018.
Stanley Kok and Pedro Domingos. Statistical predicate invention. In Proceedings of the 24th inter- national conference Machine learning. pp. 433 433-440, 2007.
Timothée Lacroix. Nicolas Usunier, and Guillaume Obozinski. Canonical tensor decomposition for knowledge base completion. In ICML, 2018.
Ni Lao and William W. Cohen. Relational retrieval using a combination of path-constrained random walks. Mach. Learn., 81(1):53-61 2010.
Ni Lao, Tom Mitchell, and William W Cohen. Random walk inference and learning in large scale knowledge base. In Proceedings of the Conference on Empirical Methods Natural Language Processing, pp. 529-5529999 Association for Computational Linguistics, 2011.
Hailun Lin, Yong Liu, Weiping Wang, Yinliang Yue, and Zheng Lin. Learning entity and relation embeddings for knowledge resolution. Procedia Computer Science, 108:345-354, 2017.
Yankai Lin, Zhiyuan Liu, Maosong Sun, Yang Liu, and Xuan Zhu. Learning entity and relation embeddings for knowledge graph completion. In Twenty-ninth AAAI conference artificial intelligence, 2015.
Tomas Mikolov, Ilya Sutskever, Kai Chen, Greg S Corrado, and Jeff Dean. Distributed represen- tations of words and phrases and their compositionality. In Advances in neural information pro- cessing systems, pp. 3111-3119, 2013.
Dai Quoc Nguyen, Tu Dinh Nguyen, Dat Quoc Nguyen, and Dinh Phung. A novel embedding model for knowledge base completion based convolutional neural network. arXiv preprint 122. 2017.
Dat Quoe Nguyen. An overview of embedding models of entities and relationships for knowledge base completion. arXiv preprint arXiv: arXiv: 1703.0808, 2017.
Maximilian Nickel, Volker Tresp. and Hans-Peter Kriegel. A three-way model for collective learning on multi-relatee centtiirllaional data. In leml, volume 11, pp. 809-816, 2011.
Meng Qu and Jian Tang. Probabilistic logic neural networks for reasoning. In Advances in Neural Information Processing Systems, pp. 7712-7722. 2019.
Tim Rocktäschel, Sameer Singh, and Sebastian Riedel. Injecting logical background knowledge into embeddings for relation extraction. In Proceedings of the 2015 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, pp- 1119-1129, 2015.
Ali Sadeghian, Mohammadreza Armandpour, Patrick Ding, and Daisy Zhe Wang. Drum: End-to- end differentiable rule mining knowledge graphs. In Advances in Neural Information Process- ing Systems, pp. 15321-15331, 2019.
Richard Socher, Danqi Chen, Christopher D Manning, and Andrew Ng. Reasoning with neural tensor networks for knowledge base completion. In Advances in neural information processing systems, pp. 926-934, 2013.
Zhiqing Sun, Zhi-Hong Deng, Jian Yun Nie, and Jian Tang. Rotate: Knowledge graph embedding by relational rotation in complex space. CoRR, abs/1902.10197, 2019.
Kristina Toutanova and Danqi Chen. Observed versus latent features for knowledge base and text inference. In The 3rd Workshop on Continuous Vector Space Models and their Compositionalliyy 2015.
Théo Trouillon, Johannes Welbi, Sebastian Riedel, Éric Gaussier, and Guillaume Bouchard. Com- plex embeddings for simple link prediction. CORR,
2016.
Pengwei Wang, Dejing Dou, Fangzhao Wu, Nisansa de Silva, and Lianwen Jin. Logic rules powered knowledge graph embedding. arXiv preprint 0tti:::903.07770 2019.

---

Under review as a conference paper at ICLR 2021
William Yang Wang and William W Cohen. Learning first-order logic embeddings via matrix fac- torization. In Ijeai, pp. 2132-2138, 2016.
Zhen Wang, Jianwen Zhang, Jianlin Feng, and Zheng Chen. Knowledge graph embedding by trans- lating hyperplanes. In Twenty-Eighth AAAI conference on artificial intelligence, 2014.
Evgenia Wasserman Pritsker, William Cohen, and Einat Minkov. Learning to identify the best con- texts for knowledge-based WSD. In Proceedings of the 2015 Conference on Empirical Methods in Natural Language Processing, pp. 1662 1667, Lisbon, Portugal, September 2015. Association for Computational Linguistics. doi: 10. 1/155//1/D11--112.
Wenhan Xiong, Thien Hoang, and William Yang Wang. Deeppath: A reinforcement learning method for knowledge graph reasoning. CoRR, 0101117777699999 2017.
Bishan Yang. Wen-tau Yih, Xiaodong Hc, Jianfeng Gao, and Li Deng. Embedding entities and relations learning and inference in knowledge bases. arXiv preprint arXiv:1412.6575. 2014.
Fan Yang, Zhilin Yang, and William Cohen. Differentiable learning of logical rules for knowledge base reasoning. In Advances in Neural Information Processing Systems, pp. 2319-2328, 2017.
Shuai Zhang, Yi Tay, Lina Yao, and Qi Liu. Quaternion knowledge graph embedding. CoRR, 1as/1994.10281,, 2019.
Yuyu Zhang, Xinshi Chen, Yuan Yang. Arun Ramamurthy, Bo Li, Yuan Qi, and Le Song. Efficient probabilistic logic reasoning with graph neural networks. arXiv preprint arXiv:2001, 18500, 2020.
12

---

Under review as a conference paper at ICLR 2021
A RULE'S VISUALIZATION
Figure 3: visualization of rule.
B PSEUDO CODE
Algorithm EM-RBR
Input: r,)
Output: (>.(h.r.))
1: Initialize Q as an empty priority queue
2: Initialize the first state: s0 < ((h,,,)}. Hawo (h, (,, (h, Sntranex (h, r,t)
3: Initialize the score: (h.,h.))t f Sutransx (h, r,t)
4: Q.push(sa)
5: while iQ.empty() do
6: Sour + Q.pop()
7:
Pw(h)r))) t- min( Lrneur (h, r, ()} if Phanea (h, < (~(hr)))) then
8:
9:
for each Sne extended from Sour with rule (B1, B2, H) do
10:
Hwene (h, r,, Hhseur (h, rtt) (BB,, B2, H))
11:
Lissn (h, H.sne (h, f) ,' Sutraus (h', ,t)
12:
if H.aan (h, t)- < Caseur (h, then Q.push(8nc)
14:
end if end for
15:
16:
end if
17:
end while
C DATA MESSAGE IN EXAMPLE
Table 3: Triplets in each state. [+]: If this symbol appears in the upper right corner of triple, the triplet is not in the knowledge graph. Other triplets are all the knowledge graph.
state
triplets
81
(h, B m2
(m): B2, t)
(h, B3, m2)
(m22 B4, 1)
83
(h, Bs, mz)
(mg, Be,mi mi)
(m), B2, 1)
(h, Bs,m1)*
(m4: Bs, m1
(m1. Bz, t)
$5
(h, m²)*
(ms. Bg,m1) m1)
(m1. B2, t)
(h, Bo, m6)
(mo; Bio, ma)
(ma, B8,mi m1)
(mi: B2,
87
(h, B11, m7)
(m7, B12, ma
ma. Bs, m2)
(mi. B2, t)
88
(h, Bo, m6)
(mg: B13, mg
(mg; B14, m4)
(m4, BB, m2)
(mis B2, t) (mi, B2, t)
(h, Bo, m
(me, B13, me)
(mg. B14, m4)
(m4, Bo, m))
13

---

Under review as a conference paper at ICLR 2021
Table 4: Rule's score
rule
score
(2, AB2(2,
= r(z,))
rl
22(x,z) ABa 7 >r(,,
r2
B5( ABa(2,)) 7 (z,
r3
By(r,z) ABg(2,,)) 7 (B,
r4
Bo(z,z) AB10(2,3) + (z(
I5
21 (z(x,))
r6
B1 A144 = (I0(F.y)
r7
Table 5: Dataset used in our study
Dataset
Relations
Entities
Train
Validation
Test
FBI5k
1,345
14,951
483,142
50,000
59, 071
WN18
18
40,943
141.442
5,000
5,000
FB 15K377
237
14,541
272.115
17,535
20, 466
WNISRR
11
40943
86,835
3,034
3,134
FB15k-R
1,345
14,951
483,142
50,000
1000
D DATASET USED IN OUR EXPERIMENT
Some triples in the test set of FB15k are selected to make up of a new test set named FB15k-R. We construct the new test set with the following steps. Firstly, sort all triples in the test by some indicator, denoted as 7(h, r. t). Secondly, randomly select triples within different ranking ranges with certain probability distribution, until 1,000 triples are selected. The probability distribution is described as Equaion 6
0.1,
event select triple whose Z =0
0.2,
event +- select triple whose ranking < 10000
P(event) = 0.3,
event + select a triple with ranking T. > 10000 & т S 30000 (6)
0.4,
event + select triple whose ranking 2 30000 & Z #
2(h, r, 1) can be calculated as one of the candidates in the following.
The number of rules each triple can match, and the matching method is the same to that in Section 2.2.1
The number of valid rules each triple match. A valid rule meets Sutrans (h, t), where w denotes the score of rule and S r,, r,t) denotes the score of the triple under transE.
The maximum SwarannE (h, r, wrute for each triple, and rule E rule(u...) rule is the set rules (h, r,t) t) can match.
Sntrans (h, Swreasoning (h, l), where swreasoning (h, r,,) denotes the score of (h, t) under EM EM-RBR((ranSE).
In our formal experiment, we choose the last strategy to generate FB15k-R.
E EXPERIMENT RESULT OF WN18RR
The metrics reported in this table better than that reported in other work parameters result in this. This experiment is verification of the enhancement effect, so it makes sense only when comparing transX and EM-RBR(X).
8 The different hyper-
14

---

Under review as a conference paper at ICLR 2021
Table 6: Experimental results WN18RR
Model
MR
MRR
H@!
H@ 10
TransE
5338
19.92
1.04
43.43
TransH
5494
19.58
2.28
42.95
HEM-RBR (trant)))))
5477
19.25
1.08
44.07
(trans((r
5597
19.31
1.52
43.68
F SINGLE TRIPLE RANKING ANALYSIS
In order to better understand the specific situation being optimized on each triplet. We respectively analyzed the corresponding ranking of each triplet under the translation model and the EM-RBR model when the head entity replacement and tail entity replacement were performed. The results were displayed in Table 7 The data item the table the result of sorting from largest to smallest value of S~trans - S-ER, where S~trans is the ranking under the corresponding translation model and S-E- the ranking under the corresponding EM-RBR model.
Table 7: Optimized case analysis. [+]: the id number the test case, for example, the first
test is /m/01qscs /m/02x8nIn and its number is 0. [+]: the rank of the test case in EM-RBR, [$] the rank of the test
nonnnnatn/aattttnnnnnnnnnoooonoo wontinatons//vvard/wwadddd
in the embedding model. [o]: L corresponds to replacing the head entity and R the tail entity.
EM-RBR(E)
EM-RBR(H)
EM-RBR(R)
Rank
+id
*E-R
ttrans oLR
Fid
*E-R
ftrans oL/R
+id
*E-R
ftrans oL/
47722
14141
18355
2
12689
L
15105
2
966
L
47722
13900
L.
32966
3
8551
I.
42675
868
R
18355
7525
18355
2
7231
R
34891
733
R
36133
6884
47722
2
4569
24314
714
33004
6253
24243
4547
L
32849
701
L
33243
5883
33004
4490
I.
55951
673
L
7
30883
5674
R
47722
2
3977
R
38773
640
L
14035
4862
13358
5
3741
54283
52
674
18355
55951
2
3699
25500
24243 10
3655
50019
3386
R
34891
2
555
L
19372
52886
2
23339
6
44273
R
19373
52707
11
23288
7
43969
R
19374
52529
7
23218
7
2
R
43664
L
19375
51447
1
21906
7
2
R
43483
2
L
19376
50932
2
R
20794
7
2
42380 R
2
R
15


Reviews:
[{"review_id": "wICTiIp7eCS", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper proposes a framework (EM-RBR) for doing Knowledge Base (KB) completion. Instead of the direct triple score from an embedding based method, EM-RBR allows the triple score to be calculated as a composition of the scores of the rules mined from the KB. EM-RBR uses a BFS type algorithm that recursively searches for reasoning paths connecting the triple while also updating the score.  The authors show that EM-RBR when used as an addendum to a translation-based embedding method (such as TrasnE, TransH) is able to outperform them. They show their results on FB15k and WN18. \n\nIssues:\n- The method section is not clearly explained and it was hard to understand the algorithm\n- The algorithm performs BFS on every example which is bound to increase the inference time, the authors claim that the approach is efficient and so should provide some analysis on that\n- The paper talks about other path-/rule-based methods, the authors should compare their approach with them (like Neural LP, MINERVA, DeepPath, etc). (Approaches that combine embedding based and rule-based methods are not novel, example: https://arxiv.org/pdf/1506.00379) \n- The authors evaluate their work on FB15k and WN18, which have been shown to have several issues (leaking of test triples as inverses, etc). Some of the current benchmarks for the task are FB15k-237 (https://www.aclweb.org/anthology/W15-4007.pdf) and WN18RR (https://arxiv.org/abs/1707.01476). \n- The authors show results on a version of FB15k they create called FB15k-R. The only thing they talk about it is \n  >  We create FB15k-R, a subset of FB15k, which contains 1000 tested\ntriplets that have rich rules to take reasoning\"\n\n- **This is a major problem**. There is no explanation regarding how this subset was chosen. It seems that it was chosen specifically because their model performed well on it. This is blatant cherry-picking.  \n\n\nOn the basis of the above points, I recommend rejection. ", "extra_scores": {}, "extra_text": {}}, {"review_id": "koRtu295chX", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary:\n\nThis paper proposes a novel algorithm for the task of Knowledge Graph Completion. Proposed algorithm uses reasoning rules from Knowledge base jointly with Translation Embedding models to gather rich information for multi-relation reasoning link prediction in Knowledge Graphs. This enables the algorithm to explore relation between two entities in a deeper context. \n\n-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------\n\nPros: \n\n+ Personally, I feel like the problem tackled in this paper is highly practical. Proposed algorithm proves the importance of high quality rules in a Knowledge Base. This can motivate further research in constructing new Knowledge Bases with rules rich relations or mining high quality rules from already existing Knowledge Bases. \n\n+ This paper also introduces a new rules rich dataset named FB15k-R. The dataset can be used in future work to ascertain the quality of rule mining and for judging performance of methods on Link Prediction task as well. \n\n+ The proposed algorithm is novel and achieves SOTA performance on variety of Knowledge Graph Link Prediction datasets. \n\n-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------\n\nCons: \n\n- Overall the paper is well written but some details seem to be missing or are not consistent (see questions below). \n\n- The motivation for choosing this algorithm is not explained in the paper. This makes the algorithm a little hard to understand. \n\n- Very minimal details are provided about the new dataset FB15k-R. The paper should include the dataset generation strategy/algorithm (at least in the appendix section). \n\n-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------\n\nOverall, I vote for accepting the paper. This paper can certainly be improved in a number of ways but the contributions are worthwhile and it may inspire some interesting future work. Hopefully the authors can address my concern in the rebuttal period. \n\n-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------\n\nQuestions: \n\n- How does equation 1 change in case of rules like B(x,y) => H(x,y)?\n\n- Both heuristic score and phi are initialised with 1 in the starting. The stopping criteria for the algorithm is written as H_scur >= phi (section 2.2). How will the algorithm start with this criteria? Is this a mistake or am I missing something here? \n\n- In Definition 2.1, what do you mean by \"where the entities order in one triplet is random, i.e. B3(z; x)^B4(z; y) =>\nR(x; y) is also a valid rule.\"? This statement seems to imply that order of the entities doesn't matter, but in reality it should matter. Maybe the statement can be rephrased? \n\n- [AMIE](http://resources.mpi-inf.mpg.de/yago-naga/amie/amie.pdf) is used for auto-mining rules from the KB. There are several other method like [DRUM](https://papers.nips.cc/paper/9669-drum-end-to-end-differentiable-rule-mining-on-knowledge-graphs.pdf), [Neural-LP](https://arxiv.org/pdf/1702.08367.pdf) for auto-mining of rules. Were they tried before deciding on AMIE? \n\n- In example section, the algorithm tries to calculate the score of the target triplet by going one step one level deeper (expanding the current triplet). The process resembles to DFS on the graph structure shown in Figure 2.\nEarlier it is mentioned that the algorithm is based on BFS and it is attributes to the use of Priority Queue. For me this creates inconsistency while understanding the algorithm. Could you please provide an example of how it resembles BFS?\n\n- While ranking all the possible triplets, how is a tie between scores resolved? \n\n-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------\n\nMinor Comments/Typos:\n\n- Section 2.2: states that were **pop** from Q -> states that were **popped** from Q\n- Footnote 2: B(x,z) => H(x,y) -> B(x,y) => H(x,y)\n\nPost Rebuttal Comments: Following the discussion in rebuttal phase and after reading all the other reviews (and authors response) , I feel that the paper is not ready for submission. While authors did address some of my concerns, the evaluation strategy seems flawed and the compared methods are not representative (as pointed out by reviewer 1). As a result, I am changing my rating from 6 to 4. Thanks!", "extra_scores": {}, "extra_text": {}}, {"review_id": "Neu0y_PTYyo", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary: The paper seek to improve KG representation (e.g. for link prediction and question answering) by combining logical reasoning (logical rule templates) with statistical methods (TransE). Rules are mined from the KG using AMIE and recursive backward steps are taken, using the mined rules, to determine if a fact is true.\n\nQuality: the paper is very difficult to read, to an extent that puts it below the quality I would expect for a top conference.\n\nClarity: As above, the paper is very difficult to read, and even pushing through grammatical errors, the algorithm itself is very difficult to understand. In many cases, terms are used first and defined later, making it hard to comprehend and requiring a lot of going back-and-forth. As one specific example, shortly after definition 2.2, H_{s_cur} is compared to \\phi, which hasn't been given a value (the clearest explanation is given in an appendix - in my view this should be in the main body since it essential). A footnote says that will be initialised to L_{s_o}, but that value (including the meaning of s_o) is not yet defined. As another example, \\Delta_path appears in Eq 1, having not been previously defined (including any notion of \"path\"), it is then defined loosely in terms of \"rules used in the extension ...\", but this is fundamental to the algorithm and should be stated concretely (perhaps built iteratively with each extension step).\n\nOriginality: The model uses a pre-existing rule mining algorithm (AMIE) and KG model (TransE) as a basic triplet score function within an exhaustive logical search framework. Using BFS to find supporting predicates does not seem particularly novel, but the means of combining score functions seems to be.\n\nSignificance: Hard to say given the difficulty understanding the paper overall and its apparent unbounded complexity.\n\nPros: The subject tackled, i.e. combining logical reasoning and statistical learning, is an important area of research.\n\nCons: \n- The paper is insufficiently clear and the poor grammar makes it too difficult to comprehend to be acceptable at a top conference. \n- Many other works combine logical rules and KG embeddings but are not compared to. It is unclear why not. The KG embedding models (that do not use logical rules) compared to are not representative of state-of-art, e.g. \n  RotatE (Zhiqing Sun, Zhi-Hong Deng, Jian-Yun Nie, and Jian Tang. Rotate: Knowledge graph embedding by relational rotation in complex space. arXiv preprint arXiv:1902.10197, 2019.)\n  QuatE (Shuai Zhang, Yi Tay, Lina Yao, and Qi Liu. Quaternion knowledge graph embeddings. In Advances in Neural Information Processing Systems, pp. 2731–2741, 2019)\n  Tucker (Ivana Balaˇzevi´c, Carl Allen, and Timothy M Hospedales. Tucker: Tensor factorization for knowledge graph completion. arXiv preprint arXiv:1901.09590, 2019.)\n  MuRP (Ivana Balazevic, Carl Allen, and Timothy Hospedales. Multi-relational poincar´e graph embeddings. In Advances in Neural Information Processing Systems, pp. 4465–4475, 2019.)\n- The approach of breadth first search has the potential for exponential explosion and seems something that embedding approaches avoid by capturing these relationships implicitly. In that respect the proposed approach appears retrograde.", "extra_scores": {}, "extra_text": {}}, {"review_id": "LtqlSMX4WBH", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The work utilizes relational background knowledge contained in logical rules to conduct multi-relational reasoning for knowledge graph (KG) completion. This is different from the superficial vector triangle linkage used in embedding models. It solves the KG completion task through rule-based reasoning rather than using rules to obtain better embeddings. Experiments on FB15K, WN18, and a new dataset FB15K-R demonstrate the effectiveness of the proposed model EM-RBR. \n\nThe work is well motivated. As for KG completion, embedding-based methods usually fail to predict long-tail relations, while rules can alleviate the problem. Hence, the work proposes to use a rating mechanism combined with a rule-based reasoning process for ranking test triplets. Generally, the technique sounds reasonable.\n\nA minor question:\n\n1) In Algorithm 1, why to push the state into the queue when H_snew < L_scur? My understanding is that if H_snew >= L_scur, and we already know L_snew >= H_snew, then we can get L_snew >= L_scur. In this case, it is not necessary to push the state into the queue. Right? I think the authors should further clarify this.\n\nSome suggestions:\n\n1) The paper demonstrates that the proposed EM-RBR(X) performs better than the X model, but I think it is better to compare with more models that utilize rules for KG completion.\n\n2) FB15k and WN18 are too old and suffer from the test data leakage issue. Recent studies for KGC no longer use FB15k and WN18. I would suggest the authors to try FB15k-237 and WN18RR. Besides, I found that if many of the test triples can not be matched by rules, the performance improvement would be subtle. I think in sparse KGs like WN18RR or FB15k-237, the proposed model will also suffer this problem, as the rules mined by AMIE will also be sparse. \n\n3) It is better to provide a rule-based reasoning path that can explain why the inferred triple is true. I think such a case study is meaningful.\n\nMinor mistakes (my point of view):\n\n1) On page 3, it says that \"The initial state is the target triplet itself, whose H is 1 and L is its score under an embedding model\", and at the footnote of page 3, it says that \"Φ is defined as Definition 2.2 and initialized as L_{s0}\". However, Algorithm 1 of Appendix B initializes H and L as 1. And in section 2.3 (page 4), it says that \"The initial state s0 only contains one triplet (h, r, t), and its state score and heuristic score are both 1\". I think it is very confusing.\n\n2) On page 4 (Section 2.2.2), it says that  \"kB1 + B2 − Hk ∈ R 3*k\". I think it may be wrong.\n\n3) I think Algorithm 1 of Appendix B lacks the procedure to handle the state whose triples are all in the KG. Just like in Figure 2 (I), I don't know which part in Algorithm 1 is used to update \\phi using L_s2.\n\n4) In Table 3, the s3 state is {(h, B5, m3) (m3, B6, m1)* (m1, B2, t)}. And in Table 5, the rule 5 (r5) is \"B9(x, z) ∧B10(z, y) ⇒ B5(x, y) r5\". Based on these, I think the example extension in Figure 2 (III) may be wrong.\n\nOverall, I think this paper is interesting, but it needs further improvement.\n\n-- after rebuttal --\n\nThank the authors for their responses. ", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper combines logical reasoning and statistical methods to improve knowledge graph completion. Rules are mined from the KG using AMIE and recursive backward steps are taken, using the mined rules, to determine if a fact is true. The reviewers agree that the paper can be improved by explaining more details of the method to make it more easy to understand. 

Decision: Reject