Instance-based Learning for Knowledge Base Completion
Authors: Wanyun Cui
Xingran Chen
Venue: NeurIPS 2022 Accept (2022)
Keywords: knowledge base completion

Abstract: In this paper, we propose a new method for knowledge base completion (KBC): instance-based learning (IBL). For example, to answer (Jill Biden, lived city,? ), instead of going directly to Washington D.C., our goal is to find Joe Biden, who has the same lived city as Jill Biden. Through prototype entities, IBL provides interpretability. We develop theories for modeling prototypes and combining IBL with translational models. Experiments on various tasks confirmed the IBL model's effectiveness and interpretability.

In addition, IBL shed light on the mechanism of rule-based KBC models. Previous research has generally agreed that rule-based models provide rules with semantically compatible premise and hypothesis. We challenge this view. We begin by demonstrating that some logical rules represent {\it instance-based equivalence} (i.e. prototypes) rather than semantic compatibility. These are denoted as {\it IBL rules}. Surprisingly, despite occupying only a small portion of the rule space, IBL rules outperform non-IBL rules in all four benchmarks. %KBC can be achieved using only IBL rules in two benchmarks without sacrificing effectiveness.  We use a variety of experiments to demonstrate that rule-based models work because they have the ability to represent instance-based equivalence via IBL rules. The findings provide new insights of how rule-based models work and how to interpret their rules.

Instance-based Learning for Knowledge Base Completion
Wanyun Cui', Xingran Chen
Shanghai University of Finance and Economics
University of Michigan
cui www.waannnuueee.mmmmmmmm edu. en, chenxrandumich cc edu
Abstract
In this paper, we propose a new method for knowledge base completion (KBC): instance-basee based learning (IBL). For example, to answer (Jill Biden, lived city.? ) instead of going directly to Washington D.C., our goal is to find Joe Biden, who has the same lived city as Jill Biden. Through prototype entities, IBL provides interpretabillty. We develop theories for modeling prototypes and combining IBL with translational models. Experiments on various tasks confirmed the IBL. model's effectiveness and interpretability.
In addition, IBL shed light on the mechanism of rule-based KBC models. Previous research has generally agreed that rule-based models provide rules with semanti- cally compatible premises and hypotheses. We challenge this view. We begin by demonstrating that some logical rules represent instance-ber based equivalence (i.e. prototypes) rather than semantic compatibility. These are denoted IBL rules. Surprisingly, despite occupying only small portion of the rule space, IBI. rules outperform non-IBI. rules in all four benchmarks. We to demonstrate that rule-hased models work because they have the ability to repre- sent instance-based equivalence via IBL rules. The findings provide new insights of how rule-based models work and how to interpret their rules.
variety of experiments
Introduction
In knowledge base completion (KBC), the learner attempts to infer new facts about the world from given training facts (head, relation, tail). This problem has intrigued many researchers' interest
and benefit for as it's both fundamental task of relational data representation learning [6 33
downstream KB- applications
[34] 39).
One typical way of KBC is answer (head, relation, ?) (?, relation, tail). Knowledge graph embedding [0) and rule-based reasoning [1738] are two typical KBC methods. Knowledge graph embedding learns low-dinensional vectors for entities and relations. One disadvantage of knowledge graph embedding is its lack of interpretability. Rule-based reasoning provides interpretability by transforming queries into human-readable logical rules. However, the predictions are constrained by the rule length k. As l increases, the rule-based search space expands exponentially, increasing the difficulty of mining high-quality rules.
In this paper, we explore an alternative method: instance-based learning (IBL) 15 26 Instead of performing explicit generalization, IBL generates predictions by comparing query instances with instances seen in training. Despite its rich history in machine learning, IBL has not seen applied ask which
in KBC. In terms of KBC, instead of directly finding the target entity the query, alternative entities share the same value with the query entity and relation? For example, for the query (Jill Biden, lived city, ?), instead of directly finding Washington D.C. from the vector space or by rules, we first identify the entity Joe Biden, who has the same lived city as Jill Biden. In this
36th Conference on Neural Information Processing Systems (NeurIPS 2022).

---

paper, Joe Biden is referred to the prototype for that query. To answer the query, we will use the prototype's known fact (i.e., (Joe Biden, lived city, Washington D.C.))
The main motivation behind IBL. is the low-rank assumption, which holds that real-world knowledge is interdependent. Such assumption has been popularized with the Netflix challenge [9] and now frequently employed in knowledge graph embedding [10, 30 33]. In the instance-based setting, we found that the low-rank assumption is significant and clear. For example, Joe Biden and Jill Biden share the same lived city because they have the same marriage event and the same children.
IBL has several advantages over traditional KBC methods: first, it enables interpretability through prototypes. For example, inferring Jill Biden's 's lived city from Joe Biden rather than Barack Obama makes more sense. Second, in contrast to rule-based reasoning. IBL is not constrained by the s-step neighborhood. In addition, the search space is always ((n_endity). Third, it helps KB curation by ensuring high-quality reasoning as the KB grows dynamically [35]. For example, we can still use Joe Biden to infer Jill Biden's 's lived city if she moves to another city in the future.
Due to the complexity of the knowledge graph, it is still challenging to find correct prototypes among the massive number of entities. Fortunately, although IBL is a new KBC method, we theoretically show that prototypes have closed-form expressions with the well-studied translational models [4] (7) in See 3] The derived IBL model has competitive performance with cutting-edge KBC methods. In addition. we establish joint optimization theory of the IBL model and the translational model in See revealing the concordance in terms of their optimization objectives. The combined model inspired by this theory outperforms existing methods in two out of four benchmarks.
Although IBI. appears to be irrelevant to rule-based KBC models, we found IBL shed light on its mechanism (S. Previous literature has commonly agreed that logical rules provide semantically compatible premises and hypotheses. We show that, some rules need to be interpreted through instance-based equivalence, rather than the semantic compatibility. We call them IBL rules. Surpris- ingly, although IBL rules only occupy a small fraction of the entire rules space, they play a significant role in rule-based reasoning. In Sec 7 we show that IBL rules are more critical than all other rules in all four benchmarks, and can even replace all other rules completely with no effect degradation in two of four benchmarks. This phenomenon challenges the previously common understanding of how logical rules work and provide interpretabilltyy Rule-based models rely much on their ability to represent saaace-based equivalence to infer new knowledge. The interpretability of logical rules should be revisited from the perspective of instance- based equivalence. And the IBL. method proposed in this paper is more effective alternative to rule-based methods when modeling the equivalency.
Our contributions are outlined as follows: (I) we explore instance-based learning for KBC. IBL provides interpretability while not being constrained by local neighborhoods. models, we prove that prototypes have closed -oosed-fommm expressions. (3) We developed a joint optimiza- tion theory for IBL and translational models foundation for combing different KBC models. Experimental results show that the combined model outperforms existing methods on two out of four benchmarks. (4) We found that rule-based reasoning relies heavily on IBL rules to represent the instance-basee equivalence. The results suggest that the mechanism and interpretability of rule-based reasoning should be reassessed in terms of instance-based based equivalence.
(2) Using translational
2 Related Work
For a comprehensive survey of knowledge graph completion, we refer readers to 33
Learning representations for knowledge via prototypes Another theory that provides support to our work is the prototype theory. The term prototypes, as initially defined in psychologist Eleanor Rosch's study "Natural Categories" 200, has been widely studied in psychology [19 and cognitive linguistics
(28) Bobrow and Winograd [3] used the prototype theory to the general knowledge representation. The general consensus is that knowledge reasoning is dominated by a recognition process in which new objects and events are compared to stored sets of expected prototypes. Although the prototype theory widely studied in variety of domains, our study is the first to apply the prototype theory for KBC to our knowledge. We concretize the theory as the equivalence of query entities to prototypes on specific relations, thus allowing knowledge reasoning.
We release code at htttpss: htt///gtttttbb httpallts///ggttt..o//oooaoarrra htt.s//www....t.oeeeaaaaaaaaaaaa
2

---

Instance-based learning There is large body of literature on IBL. The k-nearest neighbors algorithm (kNN), which uses the k-nearest examples as prototypes. the most representative work. Besides. 18 proposed to use model-based methods to calibrate the prototypes in the instance-hased method.
In recent years, IBI. has also shown its great potentials few-shot learning 25| and self-supervised learning (32. One trend of IBL is to leverage metric learning for prototype selection [8] 36 in
particular, using neural networks for instance embedding [13 (22. In this paper, similar to [13 22].
we use trainable entity embeddings to represent prototypes.
3 Models
In this section, we first formalize the KBC problem (Sec Then we demonstrate how translational models allow prototype modeling with closed-form expressions 3.2 We also investigate the relation-awareness property for specific translational representations (Sec 3.4
3.1 Problem: Link Prediction for Knowledge Base Completion
KBs are collections of triplet facts that represent world knowledge (head, relation, tail). We denote the fact in the KB D {h1, r1. f1) (hn Iny fn) }. As it is impossible to collect all facts, fundamental problem is to predict the missing facts. this paper, we formalize the completion task as link prediction. The query format in the test set is (h, r, ?) or r2
3.2 Translational Models
Translational models are one of the mainstream methods of KBC. The main idea behind translational models is model relations between entities translation from head tail over the vector space. For new fact, its plausibility can be calculated by the distance between the translated head entity and the tail entity. We formulate the plausibility of (h, r, as below:
T(h, r. t) ([mban) emb(t)]l
where emb(-) denotes the entity embedding, and trans, denotes the translation w.r.t.
There are numerous variants under the translational framework. Here we present some typical models. The feasibility of exploiting these models for IBI. are investigated in Sec
TransE [4] stores the embeddings emb(-) in an embedding matrix. It the simplest vector addition as the translation trans,(-). (-). Its scoring function is:
TransF((h, r, t) = -le, + parees e:ll
TransR 12 extends TransE by adding relationship matrix W,, which maps embeddings of entities from the entity space to the relational space:
TransR(h, r, t) = |,,,, + W,e.ll
(3)
is a cutting-edge translational model. It represents the translation via rotations in the complex space (denoted o). It has the following scoring function:
RotatE [27]
RotatE(h, r, t) = |le, reell
(4)
3.3 Modeling Prototypes in IBL
In IBL, given the query entity and relation, our primary goal is to locate the prototype whose value is the same the query and is present in the training data. We say p is the prototype of (h, r, ?) if (p. ?) = (h, r, ?). For example, Joe Biden a prototype of the query (Jill Biden, lived city, ?), since (Jill Biden, lived city, ?) (Joe Biden, lived city, ?) Washington D.C. The prototype of (2,r, r, t) is defined similarly.
We show that the prototype computation is tructable using translational models. We take advantage of translational model property: trans,() (-) a mapping from the head and relation to the tail the vector space. Thus, given the query, the prototype can be determined by Lemmal

---

Lemma 1. For an optimal translational model T, the prototypes P of (h, r, ?) are:
P= (e)brra = trans((emb(l))
(5)
Lemma I employs the absolute equality of vectors for the ideal case. In practice, relax this restriction by using the differentiable vector distance instead. particular, we model the plausibility of candidate prototype p by:
(p) = m [ttrans, - trans(
(6)
where we use marginal distance because closer distance means higher plausibility. Symmetrically, model the prototype for the query t2 by:
f. (p) max(y (|trrans"((mm((())) trans, (emb())))
where trans, is the inverse of trans,. For example, TransE uses vector subtraction as trans,".
For given query (h, r, ?), consider all candidate prototype entities whose relation is known in the training data. We aggregate these prototypes based on their scores in Eq. (6). The score of a tail entity t is the sum of scores of its corresponding prototypes:
The (t) = L/1,) E D)))
Σ (p.it)D
(pr(p)
(8)
where 1/(7) (pl(p, r, e DHH) used to normalize the score. The score of a head entity h for (?, t) computed symmetrically. We denote the above model I as IBLE cessance-basedl learning). We use the cross-entropy between Inr(t) (t) and the ground-truth entity as the training objective.
We highlight that IBLE's aggregating strategy in Eq. (8) differs from GNNs 23 For query (h, ?), regardless whether the instance a neighbor of h, we aggregate the instance p throughout the full instance space whose relation is known (i.e. (pl(p, r, E D)).
3.4 Relation-awareness for Prototype Modeling
Next, using Eq. (6). we analyze the property of relation-awarenee for prototype modeling. It is obvious that whether an entity is the prototype depends on the query relation. Joe Biden, for example, a prototype Jill Biden for lived city, but not profession. We summarize the relation-awarenee of TransE, TransR and RotatE by substituting them into Eq. (6) in Table
Table 1: Prototype modeling by translational models
Model
Prototype modeling
Relation-aware
TransE
eb ep. (10)
No
TransR
|| W,e, (11)
Yes
RotatE
[e, e.ll (12)
No
R-RotatE
W,,e, W,e (13)
Yes
Prototypes by TransE and RotatE are not relation-aware because Eq, (9) and Eq. (10) consider only entity embeddings and is agnostic the relation The relational matrix W,, on the other hand, allows TransR to distinguish different relations.
Since RotatE is the cutting-edge translational integrate the relational matrix from TransR into RotatE, denoted as relational-Rotanl (R-RotatE)):
model, propose optimize its representations. We
R-RotatE(h,r,t) ||W or -We,ll
(14)
We show the prototype modeling of R-RotatE in Table
Remark 1. TransR and R- R-RotatE are relation-awen aware for prototype modeling, whereas TransE and RotatE are not.
An interesting phenomenon is, TransE and RotatE actually have the same prototype model, as do TransR and R-RotatF. In this paper, we use the prototype modeling of TransR and R-RotatE by default.

---

Combine IBL and Translational Models
Embeddings of entities and relations of IBL can be directly reused in the translational model. In this section, we develop the theory of the joint optimization for IBL and the translational model. We show that their objectives compatible. The theory motivates to combine IBL with the translational model.
We denote the IBL model and the translational model with shared entity and relation embeddings 0 as Lo and Ta, respectively. We show that the optimization objectives of 7 and T are compatible in Lemma
Lemma 2. we use margin loss for the translational model, and cross-entropy loss for the IBL
model, and negative sampling to train both models, then the global minimum of the training criterion T can be obtained only if I also reaches its optimum.
This inspires to propose CIBLE (gombined jnstance-based learning) model, which combines la and T3 with the following scoring function:
Che (t) (1 (ll-a)thnn (t) - max(( T T th,,,t),0)
(15)
where a (0, hyper-parameter We use cross-entropy as the training objective for CIBLE The optimization objectives of T I and C are compatible. We show this in Theorem
Theorem If we use cross-entropy loss for the combined model and the IBL model, the margin loss for the translational model, and train all three models with negative sampling. then the O values for the global minimum training criteria of Ca and To are consistent. At that 8 the training criterion of Io is also minimized, and:
chi (t) = {o
(h, r,t) is a valid otherwise.
(16)
Logical Rules as Prototype-based Inference
In this section, we show that, under the low-rank assumption. the instance-based equivalence and prototypes in IBL can be represented by particular class of logical rules. We discovered that the interpretability of these rules differs from typical rules in previous papers. More numerical analysis will be presented in 7
Rule-based KBC models induct rules in the form of Horn clauses: rel A ... relk + relo- Table 2 shows examples from the body of previous publications (17 38 According to these examples, it is commonly believed that the semantic compatibility between the premise and the hypothesis provides the interpretability for humans. For example, the semantics of nationality is equal to the semantics of the path born in A place in counttyy, making the rule born in A place in country + nationality human-readable.
However, we found a special class of rules that challenge the understanding. Table shows top-3 rules inducted by RNNLogic [17] for profession in FB 137- Clearly, these rules one of the following forms:
rel, A rel_ rel, + relp
(17)
relp A rel, A rel + relg
The premises of both forms contain the composition of symmetric relations rel, A rel, whose meanings are opposition to each other. The semanties of the premise alone cannot be understood by humans, making the connection between the premise and hypothesis unclear.
5

---

award winner
awaid, wirtner y
Table 2: Examples of rules.
profession
Top rules for profession by RNNLogic [17].
crofessoon<awar winner-1 A award wimner A profession
profession--maiioallli A nationality A profession
t _aceeeoraeeeeeeeeeeee A
1 profession
profession
Examples from the RNNLogic paper [17].
premise
hypothesis
nationality=bbrn place_in_comueee jountuuryyyyyy
organization_in in otw.innnstttttorrriiiaiiioo in inyyity city locatloccee__iin state
An IBL rule indicates the instance- based relational equiva- lence.
Figure 1:
Examples from the Neural LPP paper
p contains A contains
A contains
However, after transforming such rules into the form of Fig. their meanings become clearer. The semantics of such rules are consistent with IBL's low-rank assumption. The rule in Fig. states that, conditional on the fact that z and x' both the winners of award y'. they also tend have the same profession y. As result, the rule's true purpose is to find the prototype x' to deduce the profession of æ.
We employ translational models to provide a theoretical view of IBL rules. We take TransE as an example. In Theorem 2 we show that IBL rules always hold true under the assumption of translational models.
Theorem (The effectiveness of IBL rules). For a KB with an optimal TrunsE model such that |en, + r-- egl = 0 iff (h, E KB, Vro, f1. the IBL rules rel, A relp A relo = relo and relo A rel, A rel] = relo always hold.
We highlight the difference in interpretability between the claims in previous papers and the rules in Eq. (17). We denote rules in Eq. (17) as IBL rules. IBL rules provide interpretability by establishing instance-based equivalence relations, whereas previous papers claimed that rules typically provide interpretability by semantic relevance between the premise and hypothesis. Experimental results show that the effect and interpretability of instance-based equivalence cannot be ignored. This is elaborated in Sec
Experiments
6.1
Experimental Setup
Datasets:
We select four typical KBC datasets for evaluation, including FB15k-237, WNI8RR. Kinship, and UMLS For Kinship and UMLS, we use the training/validatiionness division in [17]
Their statistics are shown in the Appendix.
Baselines We compared with the following types of KBC methods. Knowledge graph embedding:
TransE 44 Transk [12), DistMult (37). ComplEx 30,-
ConvE (6), TuckER (2) and RotatE (27).
Rule-based: RNNLogic (17), NeuralL. (38] DRUM 21 PathRank [1]] MINERVA [.. CTP 14
and M-Walk [24]. Graph neural networks: NBFNet 40
GralL [29]. and RGCN 23
Evaluation metries For each test triplet (h, r, f), we construct two queries: (h, r,) and (?, t). with the answers and h. We choose Mean Rank (MR), Mean Reciprocal Rank (MRR), and hit @k under the filtered setting (27], which is consistent with most existing work.
Implementation details We follow [27] and employ negative sampling for training. All experiments can be run on single Nvidia Tesla V100 GPU. We illustrate the hyper-parameter search process in the Appendix.
6.2 Main Results
We present the main results in Table and Table 4 IBLE is competitive with most existing KBC methods. This verify the effect and potential of IBL, as the proposed IBLE is still primitive. In
Available to researchers for non-commercial research and educational use.

---

Table Knowledge base completion results on FB15k-237 and WN18RR, means the results are from [17]. and means the results are from [40].
FB15k-237
WNI8RR
Category
Model
MR
MRR
H@!
H@3
H@ 10
MR
MRR
H@I
H@3
H@ 10
TransE#
357
0.294
46.5
3384
0.226
50.1
DistMult!
254
0.241
15.5
26.3
41.9
5110
0.430
39.0
44.0
49.0
KG
ComplEx
339
0.247
15.8
27.5
42.8
5261
0.440
41.0
46.0
51.0
Embedding
ConvE+
244
0.325
23.7
50.1
4187
0.430
40.0
44.0
52.0
TuckER!
0.358
26.6
39.4
0.470
44.3
48.2
52.6
RotatE:
177
0.338
24.1
37.5
53.3
3340
0.476
42.8
49.2
57.1
PathRank
0.087
0.189
17.1
20.0
22.5
Rule-based Learning
M-Walk
0.232
16.5
24.3
0.437
41.4
44.5
NeuralLPi
0.237
17.3
25.9
36.1
0,381
36.8
38.6
40.8
DRUM
0.238
17.4
26.1
36.4
0,382
36.9
38.8
41.0
RNNLogic!
232
0.344
25.2
38.0
53.0
4615
0.483
44.6
49.7
55.8
RNNLogic+*
0.349
25.8
53.3
4624
0.513
53.2
59.7
GNN-based
RGCN
221
0.273
18.2
30.3
45.6
2719
0.402
34.5
43.7
49.4
Learning
GralL
2053
2539
NBFNet'
114
0.415
32.1
636
0.551
49.7
57.3
IBLE CIBLE
263
0.284
20.0
31.0
45.2
7205
0.394
37.7
40.0
42.7
IBL-based
170
0.341
24.6
37.8
53.2
3400
0.490
44.6
50.7
$7.5
Table 4: Knowledge base completion results on Kinship and UMLS.
Kinship H@1
UMLS
Category
Algorithm
MR
MRR
H@3
H@ 10
MR
MRR
H@1 1
H@3
H@ 10
DistMule!
8.5
0.354
18.9
40.0
75.5
14.6
0.391
25.6
44.5
66.9
KG
ComplEx* +
7.8
0.418
24.2
49.9
81.2
13.6
0.411
27.3
46.8
70.0
Embedding
ComplEx-N3#
0.605
43.7
71.0
92.1
0.791
68.9
87.3
95.7
TuckER
6.2
0.603
46.2
69.8
86.3
5.7
0.732
62.5
81.2
90.9
RotarE
3.7
0.651
50.4
75.5
93.2
4.0
0.744
63.6
82.2
93.9
MEN
10.0
0.351
18.9
40.8
70.7
7.6
0.688
58.7
75.5
86.9
Boosted RDN
25.2
0.469
39.5
52.0
56.7
54.8
0.227
14.7
25.6
37.6
Rule
PathRank
0.369
27.2
41.6
67.3
0.197
14.8
21.4
25.2
Learning
N
16.9
0.302
16.7
33.9
10.3
33.2
56.3
77.5
DRUM
11.6
0.334
18.3
37.8
67.5
8.4
0.548
35.8
69.9
85.4
MINERVA
0.401
23.5
46.7
76.6
0.564
42.6
65.8
81.4
CTP1
0.335
17.7
37.6
70.3
0.404
28.8
43.0
67.4
RNNLogic
3.1
0.722
59.8
81.4
94.9
3.1
0.842
77.2
89.1
96.5
GNN-hased
NBFNet
3.7
0.606
43.5
72.5
93.7
3.8
0.778
68.8
84.0
93.8
IBL-based
IBLE
3.7
0.650
51.3
75.5
93.7
3.2
0.816
71.7
90.0
96.1
CIBLE
3.0
0.728
60.3
82.0
95.6
2.6
0.856
78.7
91.6
97.0
FB15k-237 and WN18RR, CIBLE outperforms previous state-of-the-art methods except the NBFNet. In Kinship and UMLS, CIBLE outperforms all existing methods. This verifies the effectiveness of CIBLE
6.3 Instance-based Interpretations
Understanding model behavior via prototypes Table shows the top 10 prototypes for predicting Taylor Swift and Barack Obama's nationalities in FB15K-237 according to Eq. (6). Despite the fact that they both Americans, they have different prototypes. Taylor Swift prefers singers and actors as prototypes, while Barack Obama prefers to use American politicians. These selections of prototypes are comprehensible to humans. In addition, we believe that prototypes are more transparent than logical rules, as many logical rules are semantically unclear to humans (see Table for some examples). See 7 will delve deeper into this.
American
Visualization global model behavior In CIBLE, the distance between entity embeddings (i.e. trans, (emb)) measures the plausibility of a candidate prototype. Here we visualize

---

Table 5: Top prototypes. For the same relation (i.e. nationality), Taylor Swift and Barack Obama This illustrates the rationality of how the model infers.
choose different prototypes.
Entity Relation
Prototypes
Taylor Swift
Carrie Underwood, Miley Cyrus, Selena Gomez, Taylor Lautner, Demi Lovato, Joe Jonas, Randy Travis, Garth Brooks, Brad Paisley, Trisha Ycarwood
Inationality
Barack Obama
Hillary Rodham Clinton, Al Gore, Jimmy Carter, Ossie Davis, James Madison, Martin Luther King, Jr., Paul Rudd, Daniel Inouye, Colin Powell, Herbert Hoover
Inationality
the entity embeddings (i.e. w, for relation of- ficial language FB15k-237 using t-SNE [I]. The visualization provides global interpretation, since it explains the prediction for all entities, rather than for one prediction.
Iraland
Weles
UK
The visualization provides rich information about how CIBLE makes predictions: (1) entities with the same value exhibit distinct clustering pat- terns, and (2) the distance between entities reflects knowledge relatedness beyond the target value. For example, Argentina (Spanish) and Brazil (Por- tuguese) close to each other, since they share other relations.. (3) The location interprets 1-to-N relations. For example, English, Mandarin, and Tamil are all official languages of Singapore, As result, Singapore is close to China (Mandarin), India (English) and Sri Lanka (Tamil).
Broal
Argenina
Portugue
Inda
Sh Lanka
Spain
Singopore
Spanish
Russian
Portuguese
French
English
Chinese
Arabic
Taml
EngishChnnserTaml
Figure 2: t-SNE visualization of entities "/country/official Janguage" FB15k-237.
6.4
Analysis
Table 6: Effect of relation-awarenes.
CIBLE
30
R RotatE
IBLE
Model
Relation -aware
FB15k-237
WNISRR
MRR
H@ 10
MRR
H@ 10
25
BILE baseline
Loss
LIBLE-TranSE CIBLE TransR
0.286
44.7
0.236
53,8
20
0.341
52.2
0.250
49.7
CIBLE-Rotatl CIBLE-R-Rothe
No
0.315
50.6
0.430
54.2
15
Yes
0.341
53.2
0.490
57.5
Steps (1000x)
Figure 3: Training loss on UMLS.
Consistency of model optimization In Theorem 1 show the consistency of the optimization objectives for the three models. To verify this theory, we show their training losses when optimizing CIBLE in Fig. 3 IBLE-baseline and RotatE-baseline denote the convergence of the training loss when we optimize them separately. Overall, as we optimizing CIBLE, the training loss of IBLE and RotatE both decreases. In addition, optimizing CIBLE helps IBLE converge its minimum training loss. This verifies the consistency of the three optimization objectives.
Effect of relation-awareness We show in 3.4 that prototypes modeled by TransR and R- R-RotatE are relation-aware while TransE. and RotatE are not. To validate the effect of relation-awareness, compare their effect when adapting to CIBLE. Thows the results. Models with relation- awareness perform better on most metrics. This is in line with our intuition about prototypes.
Rule-based Reasoners: Semantic Relevance or Instance-based Equivalence?
In Sec we defined special class of logical rules, namely IBI. rules. In this section, we reassess the mechanism and interpretability of logical rules by validating the effect of IBL rules.

---

Table Effect of IBL rules for FB15k-253 and WN18RR.
FB13k-237
WNI8RR
Model
MR
MRR
H@1 1
H@3
H@10
MR
MRR
H@1
H@3
H@ 10
all rules
178
0.349
25.8
38.5
53.3
4624
51.3
47.1
53.2
59.7
non-IBL rules only
1241
0.317
23.2
35.1
48.6
9849
44.1
41.9
45.3
48,5
IBL-rules only
1011
0.326
24.0
36.1
49.9
8946
44.0
40.6
46.3
49.9
Table 8: Effect of IBL rules for Kinship and UMLS.
Kinship H@]
UMLS
Model
MR
MRR
H@3
H@10
MR
MRR
H@1
H@3
H@ 10
all rules
3.1
0.842
77.2
89.1
96.5
3.1
0.722
59.8
81.4
94.9
non-IBL. rules only
9.9
0.667
53.7
76.9
86.2
4.0
0.681
55.0
77.3
93.2
IBL-rules only
3,0
0.840
75.1
91.3
96.6
3.3
72.1
59.5
81.4
94.7
Earlier rule-based models learn logical rules in a differential way 38 However, their search space is exponentially large, which results in limited rule length. The recently proposed method, its capacity to generate rules with maximum length of With these longer rules, RNNL Logic achieves 53.3 hit@ 10 in FBI 1B11k-237, compared to the previous highest hit of only 36.4 for rule-based models 21. Therefore, we use RNNLogic to investigate the effect of IBL rules.
RNNLogic [17), was a breakthrough
To demonstrate the effect of IBL. rules, we control the candidate rule space of RNNLogic by modifying its rule collection module. We carried out the following ablations: (1) collecting rules from the entire rule space; (2) collecting only non-IBL rules; (3) collecting only IBL rules. Table 7 and Table show the effects of these ablations.
The results surprising. Despite the fact that IBL rules only cover small portion of the entire rule space, learning IBL. rules outperforms learning non-IBI. rules all four benchmarks. In Kinship and UMLS, learning only IBL rules has almost no performance degradation when compared to learning from the entire rule space. The results indicate that, the small number of IBL rules are even more critical than non-IBL rules.
These findings challenge the widely- belief that rule-based reasoning use rules whose premises and hypotheses semantically compatible. The results imply that rule-based KBC models work largely because its capability to represent instance- based equivalence (i.e. prototypes) via IBL rules. The interpretability from instance-based equivalency should not be overlooked in rule-based models.
To understand why IBL rules outperform other semantic non-IBL. rules, we investigate the quality of each rule. More concretely, show the average precision and support 7 of each collected rule for different rule types in T The results show that both the average precision and support of IBL rules are substantially higher than those of non-IBL rules. The high quality of IBL rules explains why they outperform non-IBL rules despite occupying only a small fraction of the entire rule space.
equivalence relationship. CIBLE more flexible and theoretically sound than rule-based models using IBL rules. In Table despite the fact that RNNLogic employs complex EM algorithm for learning, CIBLE outperforms RNNLogiC in three of the four benchmark. Therefore, we consider CIBLE to be a more effective alternative to the rule-based models in instance-based equivalency modeling.
IBL-based rule-based models When representing the instance-
Table 9; Average support and precision IBL and non-IBLE rules.
FB15k237
WNI8RR
UMLS
Kinships
IBI Rule
708.3/3.75 281.4 1.7%
2374.3 / 12.7%
3.0 11.6%
8.7/ 11.6%
Non-IBI. Rule
188.3 / 5.0%
3.0/
6.7 5.1%

---

8 Conclusion
In this paper, we explore novel IBL-based method for KBC. We validate its effectiveness in two aspects. First, we show that the prototypes can be expressed in a closed-form with the well-studied translational models, and IBL-based models can be cotypeombined with translational models. Second, we found that rule-based reasoning relies heavily on IBL rules. This challenges previous common understanding of how logical rules work and provide interpretability.
Broader impact Our proposed IBL method provides a new paradigm for learning representations for knowledge bases. Based the results of the experiments, the IBL. paradigm can be combined with translational models and rule-based reasoners and enhance the effectiveness. Our theory has provided the foundation for combing IBL models and translational models. We expect to better exploit the theory to combine different KBC models in the future.
Acknowledgments and Disclosure of Funding
This paper was supported by National Natural Science Foundation of China (No. 619061 16), by Shanghai Sailing Program (No. 19YF1414700). We thank Wenting Ba for her valuable plotting assistance.
References
[1] Kelsey Allen, Evan Shelhamer, Hanul Shin, and Joshua Tenenbaum. Infinite mixture prototypes for few-shot learning. In ICMI., pages 232-241. PMLR, 2019.
[2] Ivana Balazevic, Carl Allen, and Timothy Hospedales. TuckER: Tensor factorization for knowledge graph completion. In EMNLP-IJCNLP, 2019.
[3] Daniel G Bobrow and Terry Winograd. An overview of krl, knowledge representation language. Cognitive science, 1(1):3-46, 1977.
[4] Antoine Bordes, Nicolas Usunier, Alberto Garcia-Duran, Jason Weston, and Oksana Yakhnenko. Translating embeddings for modeling multi-relational data. In NewrIPS, 2013.
[5] Rajarshi Das, Shehzaad Dhuliawala, Manzil Zaheer, Luke Vilnis Ishan Durugkar, Akshay Krishnamurthy, Alex Smola, and Andrew McCallum. Go for walk and arrive at the answer: Reasoning over paths in knowledge bases using reinforcement learning. In ICLR, 2018
[6] Tim Dettmers, Pasquale Minervini, Pontus Stenetorp, and Sebastian Riedel. Convolutional 2d knowledge graph embeddings. In Proceedings of the AAAI conference on artificial intelligence, volume 32, 2018.
[7] Luis Galárraga, Christina Teflioudi, Katja Hose, and Fabian M Suchanek. Fast rule mining in ontological knowledge bases with amie++. The VLDB Journal, 2015.
[8] Jacob Goldberger, Geoffrey E Hinton, Sam Roweis, and Russ R Salakhutdinov. Neighbourhood components analysis. NeurIPS, 2004.
[9] Yehuda Koren, Robert Bell, and Chris Volinsky. Matrix factorization techniques for recom- mender systems. Computer, 42(8):30-37, 2009.
[10] Timothee Lacroix, Nicolas Usunier, and Guillaume Obozinski. Canonical tensor decomposition for knowledge base completion. In ICMI., 2018.
[11] Sangkeun Lee, Sungchan Park, Minsuk Kahng, and Sang- goo Lee. Pathrank: Ranking nodes on a heterogeneous graph for flexible hybrid recommender systems. Expert Systems with Applications, 40(2):684-697) 697, 2013.
[12] Yankai Lin, Zhiyuan Liu, Maosong Sun, Yang Liu, and Xuan Zhu. Learning entity and relation embeddings for knowledge graph completion. In AAAI, 2015.
[13] Renqiang Min, David Stanley, Zineng Yuan, Anthony Bonner, and Zhaolei Zhang. A deep non-linear feature mapping for large-margin knn classification. In ICDM, pages 357-366, 2009.
10

---

[14] Pasquale Minervini, Sebastian Riedel, Pontus Stenetorp, Edward Grefenstette, and Tim Rock- täschel. Learning reasoning strategies in end-to-end differentiable proving. In ICML, 2020.
[15] Tom M Mitchell al. Machine learning, 1997.
[16] Maximilian Nickel, Volker Tresp, and Hans-Peter Kriegel. A three-way model for collective learning on multi-relational data. In (CM1,2011)
[17] Meng Qu, Junkun Chen, Louis-Pasce Xhonneux, Yoshua Bengio, and Jian Tang, Rnnlogie: Learning logic rules for reasoning on knowledge graphs. In ICLR, 2020.
[18] J Ross Quinlan. Combining instance-based based and model-based learning. In ICML, pages 236-243, 1993.
[19] Eleanor Rosch, Carolyn B Mervis, Wayne D Gray, David M Johnson, and Penny Boyes-Braem. Basic objects in natural categories. Cognitive psychology, 8(3):382-439 1976.
[20] Eleanor Rosch. Natural categories. Cognitive psychology, 4(3):328-350, 1973.
[21] Ali Sadeghian, Mohammadreza Armandpour, Patrick Ding, and Daisy Zhe Wang. Drum: End-to-end differentiable rule mining on knowledge graphs. NeurIPS, 2019.
[22] Ruslan Salakhutdinov and Geoff Hinton. Learning nonlinear embedding by preserving class neighbourhood structure. In AISTAT, pages 412-419, 2007.
[23] Michael Schlichtkrull, Thomas Kipf, Peter Bloem, Rianne Van Den Berg, Ivan Titov, and Max Welling. Modeling relational data with graph convolutional networks. In ESWC, 2018.
[24] Yelong Shen, Jianshu Chen, Po-Sen Huang, Yuqing Guo, and Jianfeng Gao. M-walk: Learning to walk over graphs using monte carlo tree search. NeurIPS, 2018.
[25] Jake Snell, Kevin Swersky, and Richard Zemel. Prototypical networks for few-shot learning. NeurIPS, 2017.
[26] Craig Stanfill and David Waltz. Toward memory-based reasoning. CACM, 11112)11222 1986.
[27] Zhiqing Sun, Zhi-Hong Deng, Jian- Yun Nie, and Jian Tang. Rotate: Knowledge graph embed- ding by relational rotation in complex space. In ICLR, 2019.
[28] John R Taylor. Linguistic categorization. OUP Oxford, 2003.
[29] Komal Teru, Etienne Denis, and Will Hamilton. Inductive relation prediction by subgraph reasoning. In ICMI., pages 144-99457 PMLR, 2020.
[30] Théo Trouillon, Johannes Welbl, Sebastian Riedel, Éric Gaussier, and Guillaume Bouchard. Complex embeddings for simple link prediction. ICML, pages 2071-2080. PMLR, 2016.
[31] Laurens Van der Maaten and Geoffrey Hinton. Visualizing data using t-sne. JMLR, 9(11), 2008.
[32] Carl Vondrick, Abhinav Shrivastava, Alireza Fathi, Sergio Guadarrama, and Kevin Murphy. Tracking emerges by colorizing videos. In ECCV, pages 391-408, 2018.
[33] Quan Wang, Zhendong Mao, Bin Wang, and Li Guo. Knowledge graph embedding: A survey of approaches and applications. TKDE, (912222774 2017.
[34] Xiaozhi Wang. Tianyu Gao, Zhaocheng Zhu, Zhengyan Zhang, Zhiyuan Liu, Juanzi Li, and Jian Tang. Kepler: A unified model for knowledge embedding and pre-trained language representation. TACL, 9:176-194, 2021.
[35] Gerhard Weikum, Luna Dong, Simon Razniewski, and Fabian Suchanek. Machine knowledge: Creation and curation of comprehensive knowledge bases. Foundations and Trends in Databases, 10(2-4):108-499 2021.
[36] Kilian Q Weinberger and Lawrence Saul. Distance metric learning for large margin nearest neighbor classification. JMLR, 10(2), 2009.

---

[37] Bishan Yang, Wen-tau Yih, Xiaodong He, Jianfeng Gao, and Li Deng. Embedding entities and relations for learning and inference knowledge bases. In ICLR, 2015.
[38] Fan Yang, Zhilin Yang, and William Cohen. Differentiable learning of logical rules for knowledge base reasoning. In NeurIPS, 2017.
[39] Fuzheng Zhang, Nicholas Jing Yuan, Defu Lian, Xing Xie, and Wei- Ying Ma. Collaborative knowledge base embedding for recommender systems. SIGKDD, pages 353-362, 2016.
[40] Zhaocheng Zhu, Zuobai Zhang, Louis-Pascal Xhonneux, and Jian Tang. Neural bellman-ford networks: A general graph neural network framework for link prediction. NewrIPS, 2021.
12


Reviews:
[{"review_id": "n-VrrW-Bmr", "reviewer": "Reviewer_ZosV", "summary": "This paper proposes Instance-Based Learning for translational embeddings, and evaluates its performance in knowledge-base construction tasks. The paper first defines the general concept of prototyping in translational embedding training using relational tuples, then discuss methods to train with both translational loss and IBL loss, which is through a linear combination of their respective loss functions controlled using a hyper-parameter weight alpha. The paper also presents experimental results on 4 KBC datasets, which largely surpass performances of all but 1 graph network based approach, and does so with much less computational complexity. The paper also interestingly present the finding that it seems like rule-based reasoning doesn't necessarily always find semantically relevant rules.", "questions": "1. One could probably argue, that prototyping is potentially a GNN approach with limited depth (1). Recent work on GNN for KBC have considerable difficulty with computational costs, which led to a series of path-based learning algorithms. Based on the simplicity and strong performance of CIBLE, I wonder if it could be extended to a GNN with greater depth?\n\n2. Prototyping like in CIBLE does have advantages over plain TransR and RotatE as demonstrated in this paper. However, I couldn't figure out why there seems to be quite a gap between the performance of TransE/IBLE against CIBLE, but not so much between TransE and IBLE. I wish the authors could maybe explain a bit on why this is the case. It would be especially helpful if the authors could include their own implementation of TransR's evaluation on the table if not TransE/R-RotatE as well, since as I understand CIBLE is the combination of IBLE loss and TransR, this should not be very difficult.", "limitations": "I do not see potential negative societal impact.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength:\n1. The paper is clearly written and presented. The mathematically formulation is well done and easy to understand.\n2. The paper proposes a method with relatively low-computational cost (compared to graph neural networks) to complement existing translational embedding learning method.\n3. The paper shows that the proposed method is highly competitive in all experimented datasets.\n\nWeakness:\nI could not find major weaknesses in this paper. I think it would be better to include numbers of the authors' implementation of TransE, TransR, etc. (without IBE loss) in the evaluation table as an ablation study perhaps. But all in all, IBLE itself is already an interesting approach.\n", "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": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "hHczRVkSoT", "reviewer": "Reviewer_DVJo", "summary": "The paper studies the knowledge base completion problem and proposes an instance-based learning method that utilizes the prototypes to help the inference of a given query. Then the relation information can be used in the prototype modeling and could obtain better performance. The proposed IBL can be combined with the traditional translation models to achieve the best performance. The authors also compare their model with other existing methods of rule discovery. IBL role provides interpretability by establishing instance-based equivalence relations.", "questions": "- The proposed instance-based learning looks like the neighboring entities of a relation can be aggregated to help infer the missing facts. Can you please discuss the differences between the proposed and GNN-based methods, e.g., R-GCN?\n- The motivation for combining IBL and Translational models is not clear. The authors mention the objectives are compatible. However, they did not clarify why the IBL cannot work well alone and have to work with the translation models.\n- It is not easy to understand why the IBL rule provides better interpretability than existing methods. I wonder why the IBL using instance-based equivalence relations can work better than the methods adopting semantic relevance.", "limitations": "Please discuss the limitations and negative societal impact of the work.", "rating": 4, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- Most important baselines are included in the experiments.\n- The case study and visualization are interesting.\n- The conducted experiments are comprehensive.\n\nWeaknesses:\n- The proposed instance-based method needs to work with the traditional translation models to obtain the best performance. It looks like a neighborhood aggregation to enhance the translation models as they do not consider the graph structure information. Based on that, the paper provides an incremental strategy to improve the existing methods.\n- The presentation about the logical rule is not clear and not easy to follow.\n- The motivation for combining IBL and Translational models is not clarified.", "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": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "OdobsS_Deqm", "reviewer": "Reviewer_iZrV", "summary": "This work proposed to use prototype entities to enhance the knowledge base completion methods. Specifically, the KBC methods firstly look for the alternative entities that share the same value with the query entity and relation as the prototype entities. The authors show that the prototypes have closed-form expressions when combining with translation-based KBC models like TransE. The experimental results show it outperforms existing methods. Besides, this work also claims the connections between instance-based learning and rule-based learning. Further it encourages the rethinking of interpretability of rule-based reasoning from the angle of instance-based equivalence.\n", "questions": "1. Can you demonstrate more examples of IBL rules obtained from the proposed methods? It could be better to have detailed comparisons with the rules from previous work. \n\n2. The assumption is a bit in line with collaborative filtering in the recommendations. Have you thought of any solutions from the perspective of matrix factorization? \n\n3. Can the prototype-based methods generalize to unseen relations or OOD scenarios? \n", "limitations": "N.A", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. The idea is well-motivated and prototype-based methods have been shown useful for many downstream tasks such as relation extraction etc. It is good to apply to knowledge base completion tasks. \n\n2. The closed-form solution of looking for prototype entities is interesting under the assumption of translation-based models. \n\n3. The proposed instance-based learning method can achieve competitive performance and then combining with translation-based methods outperforms the state-of-the-art methods. \n\n\nWeakness:\n1. The introduction of logical rules as prototype-based inference is vague. One concrete example in Section 5 is not convincing and clearly states the connections or significant differences between prototype-based inference and rule-based reasoning. \n2. The IBL rules should be formally defined in Section 5. \n3. The claim that replacing the rule-based reasoning with instance-based learning is a bit weak from the limited experimental results. \n", "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": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "7Sfr7jPJh9b", "reviewer": "Reviewer_qiwG", "summary": "This paper introduces a new paradigm for KBC task by exploring instance based learning. They show that most of the \nrule learning models mostly learn instance-based rules and using only those rules they can still perform close to state of the art. \nPaper also proposes ways to finding prototypes and propose models on how IBL can be combined with other approaches. \nExperimental results show that its competent on several benchmarks though it doesn't outperform existing systems. \nUsing existing embedding methods to select prototype seems novel and builds on top of the existing literature. \n\n\nAny comments on the practical scenarios with large KBs and long skewed entities and relationships? Is it \nis to find a prototype entity to answer the queries for relatively less represented entity types and relationships?\n\n", "questions": "Please see summary", "limitations": "Yes", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: \nBringing IBL to KBC space and see how it performs with respect to current systems\n\nweaknesses: \nExperimental results are not on par with other benchmarks. \nNot sure about how it can extend to practical use cases with long tail entities.", "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": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept