Rethinking Knowledge Graph Evaluation Under the Open-World Assumption
Authors: Haotong Yang
Zhouchen Lin
Muhan Zhang
Venue: NeurIPS 2022 Accept (2022)
Keywords: Knowledge graph
theory

Abstract: Most knowledge graphs (KGs) are incomplete, which motivates one important research topic on automatically complementing knowledge graphs. However, evaluation of knowledge graph completion (KGC) models often ignores the incompleteness---facts in the test set are ranked against all unknown triplets which may contain a large number of missing facts not included in the KG yet. Treating all unknown triplets as false is called the closed-world assumption. This closed-world assumption might negatively affect the fairness and consistency of the evaluation metrics. In this paper, we study KGC evaluation under a more realistic setting, namely the open-world assumption, where unknown triplets are considered to include many missing facts not included in the training or test sets. For the currently most used metrics such as mean reciprocal rank (MRR) and Hits@K, we point out that their behavior may be unexpected under the open-world assumption. Specifically, with not many missing facts, their numbers show a logarithmic trend with respect to the true strength of the model, and thus, the metric increase could be insignificant in terms of reflecting the true model improvement. Further, considering the variance, we show that the degradation in the reported numbers may result in incorrect comparisons between different models, where stronger models may have lower metric numbers. We validate the phenomenon both theoretically and experimentally. Finally, we suggest possible causes and solutions for this problem. Our code and data are available at https://github.com/GraphPKU/Open-World-KG .

Rethinking Knowledge Graph Evaluation Under the Open-World Assumption
Haotong Yang!2
Zhouchen Lin 123+ Muhan Zhang
KKey Lab of Machine Perception (MoE),
School of Intelligence Science and Technology. Peking University Institute for Artificial Intelligence, Peking University
SPeng Cheng Laboratory
4 Beijing Institute for General Artificial Intelligence
(haotongyang, zlin, muhan) @pku edu. cn
Abstract
Most knowledge graphs (KGs) are incomplete, which motivates one important research topic automatically complementing knowledge graphs. However, evaluation of knowledge graph completion (KGC) models often ignores the incompleteness-faee facts in the test are ranked against all unknown triplets which may contain a large number of missing facts not included in the KG yet. Treating all unknown triplets false is called the closed-world assumption. This closed-world assumption might negatively affect the fairness and consistency of the evaluation metrics. In this paper, we study KGC evaluation under a more realistic setting, namely the open-world assumption, where unknown triplets are considered to include many missing facts not included in the training or test sets. For the cur- rently most used metrics such mean reciprocal rank (MRR) and Hits @ K, we point out that their behavior may be unexpected under the open-world assumption. Specifically, with not many missing facts, their numbers show a logarithmic trend with respect to the true strength of the model, and thus, the metric increase could be insignificant in terms of reflecting the true model improvement. Further, consider- ing the variance, we show that the degradation in the reported numbers may result in incorrect comparisons between different models, where stronger models may have lower metric numbers. We validate the phenomenon both theoretically and experimentally. Finally, we suggest possible causes and solutions for this problem. Our code and data are available at htttts://gihhubb.... attlttpss/gghhbb...C//oGPPP////P Coa//raaPPP/////ppp World-KG KG
Introduction
Knowledge graph (KG) is structural method to store facts about some field the world. Because most KGs are incomplete, the knowledge graph completion (KGC) task is proposed to automatically complement the existing KG with missing facts. However, when we do not know the missing facts in advance, we must manually evaluate whether each predicted completion is correct, which is an impossible task for modern KGs. This problem is called the open-world problem and the assumption that KGs are incomplete is called the open-world assumption. A general solution is to extract the training. validation and test sets from the existing incomplete KG and then evaluate the trained models on the test set. Then, natural question is whether the conclusion drawn from the incomplete test set consistent with the true strength of the model, which should be measured on the complete KG.
To answer this question, we need to investigate the metrics used to evaluate KGC models. KGC models are often evaluated by ranking-based metrics, such mean reciprocal rank (MRR) and
"Corrsponning authors.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

Table 1: The filtered ranking as well as the metric MRR. "wlo c": without correction and "with c": with correction. Query: "What sports were included in the 1956 Summer Olympics?"
Test Answers
Missing Answers
swimming sailing
water polo
boxing
dressage
show jumping
canoe sprint
eycling
ranking w/o ranking with c
5
5
4
9
1
1
Hits@K. K. Under the open-world assumption, when a missing fact that should have been included in the test answers is predicted by the model, its ranking could be higher than some test answers, which makes the rankings of these test answers drop. In this situation, despite actually recognizing more right answers, the metrics drop instead.
To intuitively show the problem, we train BetaE [Ren and Leskovec, 2020]. one state-of-the-a multi-hop KGC model, on the FB15k-237 dataset [Toutanova and Chen 2013]. One of the test queries is "What sports were included in the 1956 Summner Olympics ?". The two test answers swimming and sailing, both with the filtered rankings (refer to Section 2 of 5, so the MRR on this query is 20%. However, when we manually check the first 30 predictions, we found that many of them are in fact sports included in the 1956 Summer Olympics but not included in the answer set 2 We present these missing answers in Table [ We can see that all the four sports previously ranking higher than the two test answers turn out to be missing true answers. Thus, if we correct the answer set by adding these missing answers to the test set, the actual filtered rankings of the two test answers are both 1, and the corrected MRR on the new test set becomes 82% which is much higher than the reported 20%, indicating that the model strength on this query is significantly underestimated.
In this paper, we study the odd behavior of the ranking- based metrics under the open-world assump- tion, and summarize two problems affecting the KGC evaluation: 1) Metric Degradation. It means that with the increasing of the actual model strength, the increasing of the reported metric becomes slower and slower. Thus, the reported metric might not be able reflect the true model improvement. 2) Metric Inconsistency. It means that when comparing two models, the model with lower reported metric may actually have better performance if we evaluate them on the complete KG.
Our main contributions include that: For the first time, we theoretically analyze the evaluation of KGC under the open-world assumption and point out the degradation and inconsistency problems. Furthermore, we suggest that the degradation and inconsistency may be related to the focus-on-top behavior of the metrics, and provide solution to relieve the two problems. Finally, we verify the theoretical analysis through experiments on an artificial closed-world KG.
2 Background and related work
Knowledge graph completion Current KGC models can be mainly categorized into three classes: logic-based, embedding- based, and neural-based. Logic-based models (Joseph and Riley 1998] Richardson and Domingos 2006) use some explicit rules for KGC, which are manually provided or mined by some rule-mining methods, such as [Galárraga et al. 2013 Yang et al. 2017 Sadeghian et al. 2019]. These models search through the existing KG and deduce missing facts according the given rules. However, this process can be coneucinn and noise-sensitive. At the same time,
the KGs are highly incomplete, the performance could be poor. Embedding- based models [Bordes) ee al. 2013 Yang et al. 20155 [Truillon et al.) 2016, Sun et al. 2019 represent entities and relations by learned vectors or tensors, where the possibility of a fact is measured by a score function. These models have good scalability and can be applied to large and sparse KGs. Some works aim to
generalize smbedding-basee models to more patterns [Trouillon al. 2016 Abboud et al., 2020 and more assumptions (such as multiple answers) [Vilnis et al. 2018 Ren et al. 2020 Abboud et al. 2020). One of the interesting directions is to consider multi-hop reasoning (Ren et al.) 2020) Ren and
Leskovec [020 ZZang et al., 2021]. where a query can be composed by several conditions, such as "Who is the Canadian and won the Turing Award ?" Note that the open- open-world problem could be more severe in the multi-hop setting, because missing in any condition leads to missing in the final
results. Neural-based based models combine neural networks with embeddings. Dettmers et al. (018 and Nguyen et al. 2018 use a convolution networks as the score function to enlarge the capacity of
2 All sports held this Olympics are in: https: //en. wikipedia. wtg/wwki///// 1ttp:///1116___mmeee_e11 00iepric__mmpccs

---

the models. Nathani et al. (2019), Vashishth et al. (2020) and Wang et al. [2021] use graph neural networks on the KGs to learn the embeddings or directly predict the links.
KG evaluation Current KGC evaluation resorts to manually split training, validation and test sets from the incomplete KG. Given a test query r(ea,?) ?) (which entities have the relation r with the head entity ex ?), a typical method is to predict a score for all entities as the tail entity, rank all the entities, and then measure the average of a manking--bscee function h(r) on the test answers. Here, the most-used metrics are MRR h(r) = 1/r and the Hits h(r) I[r I K). Because there could be multiple answers for a query, the metrics should be filtered, which means the answers in the training and test sets do not occupy position that the number of training and test answers does not affect the metrics. The details of the filtering can be found in [Bordes et al. 2013). Due to the nonlinearity metrics, some works have theoretically investigated their behavior. [aang] et al. [0113] point out some ranking-based metrics always converge to 1 on different models as the number of objects rank goes infinity, so that the performance of models is indistinguishable.
of most ranking-basse
Krichene and Rendle [2020] analyze the behavior of taikinngbbased metrics under negative sampling.
They point out the sampled metries can be inconsistent with exact metries and all metries lose their focus-on-top feature and collapse to linear one, AUC-ROC, in the small sample limit. Sun et al.
[2020] focus on the unfair tic- tiebbrakiin methods. [Akrami et al. (2020) find some data argumentation such as adding inverse relations could be kind of excessive data leakage during evaluation.
Open-world assumption Some recent works have noticed the gap between the actual open- world situation and the glosed-works assumption. Cao et al. [2021] point out that the closed- world assumption leads to a trivial evaluation on the triple classification task. They offer their manually- labeled seatii--negatie--unneee
ternary triple classification datasets following the open- open-world assumption and point out the lack of capacity for current models to distinguish unknown from negative. However, the unknown part in the dataset is only on the triple classification task, while we focus on the link prediction task here. Additionally, Das et al. [2020) analyze the open-world setting as an evolving world that continuously adds new entities and facts to KGs. Under this setting, their work focuses on the inductive or case learning capacity, i.e., the capacity of models to generalize on unobserved entities. Here, aim to analyze the possible inconsistent comparison in evaluation with missing facts instead of a specific framework with larger inductive capacity.
3 Open-world problem
In this section, we formally define the open-world problem that will be analyzed in our paper.
Definition 3.1 (Knowledge Graph). A knowledge graph is a relational graph G = (E, F, R) where E is the vertex set containing entities, F is the edge set containing facts, and R is the relation set. Each edge f E F labeled by a relation. If an edge I between entities en and e, is labeled by relation R. we denote the edge f as r(en, es) where en is the head entity and e is the tail entity.
In this paper, we assume F and R are fixed. Therefore, we sometimes directly use G to denote the fact set F, and r(en, ex) G means there is relation between e₁ and 6, in the KG G.
A set of KGs with the same entities E and relations Rt but different facts F is called a world and denoted by W (E, Rt). An (open-worke KG can be considered as observation or understanding of the world where there could be unobserved or unknown facts, while the closed-wor world KG contains all the true facts of the world. Formally, the closed-world and open- open-world KGs are defined as follows:
Definition 3.2 (Closed- World KG and Open-World KG). For world W W(E, R), the closed-worke KG G is the closure the world.
G= U=UG'
G'EW
where the union is defined on the fact set. And for KG G' E Wf & G' is open-world 3
Some property of corle KGs: 1) There is a one-to-one correspondence between closed-world KGs and worlds W(E, R). 2) All the KGs in world are subgraphs of the closed- world one. 3) If G is the closed- KG of the world W, we have f & G = VG E W, f G'.
SSoe works use open-
open-world world
refer to only facts but also entities may be incomplete.
3

---

The third property is critical. It means with the closed- G, we know there is no such a relation r between e,, and e, in the world when r(en,e, & G. Given the closed-world KG, we have all knowledge of the world, including both the positive and negative one. Conversely, if KG is open- world, we do not know whether the triplet is false or unknown when r(en,e)) e4) E other words, an open-world KG only contains positive knowledge.
In the rest of the paper, we denote the closed-world KG as G Because we want to study the evaluation, we denote the existing open-world dataset as Gtest, and extract the training set Gtroin from Glest. Here, Gtrain S Grest S full and the facts in Girain- Gtest \ Gerain Gfult Gtest are training facts, test facts and missing facts respectively. In addition, we also call the facts in G Graain full test facts and Geest \ Giraan sparse test facts.
Now, we can formally define the open-world problem. We believe the actual strength of a model should be evaluated on the full test facts G Gull Gtrain- However, because the closed-world KG G fult is unavailable, the evaluation is often performed over Grest \ Gtrain- The question is:
Whether the conclusions from evaluation on the sparse test facts Gtest \ Gtrain lead consistent conclusions from evaluation on the full test facts Gfull \ Grrain
4 Theoretical analysis on metric degradation and inconsistency
To study the open-world problem, we theoretically analyze the behavior of ranking- based metrics with missing facts. All the proofs are in Appendix [A. The randomness comes from two sources: the missing of facts and the predictions of the model. We model them as two random events.
Missing Fact Model: For a full test fact r(en, ex) E Gfutt \ Gtrain X means it is a missing fact with P(X)= = 3 while X means it is included in the sparse test set Grest \ Gerain with P(X)=1- B = a. 33 is called the sparsity of the KG.
Prediction Model: For simplicity of analysis, we model KGC as a classification task. In fact, an ideal (oracle) KGC model is exactly classification model, which identifies all the correct facts. Here, for full test fact r(en, et) E Gull \ Gtrain, Y means the answer e, is correctly classified as positive with P(Y) f. É is called the strength of a model. We break ties uniformly at random for entities classified into the same class.
Note that one of our basic assumptions is 'set answer' followed [Ren al., 2020), where we believe the answer for query should be set or concept instead of exactly one entity. For the open- world problems we care about, we assume that the number of elements in the answer set should be larger than one.
4.1 Expectation degradation
We first assume the independence of the random events X and Y. We show that the expectation of the metrics will degrade with missing facts. Specifically, the increasing of the metrics shows logarithmic trend, so that could be too flat to reflect the true increasing of the model strength.
Assume the number of entities is Nentity in the KG. For given query r(en, ?), let N be the number of full test answers. The random variant mn is the number of missing answers Gfuul \ Grests and follows the binomial distribution B(N, 3). The other N- m answers are test answers. We denote the filtered ranking of the entity e as r (e). Then we have the lemma.
Lemma 4.1 (Expectation of ranking- based metrics). With the modeling of missing fact and prediction Nm 1 as above, the expectation of ranking- aanking-based metric M N-m EN-". s(r(e))) can be expressed as
N
E(WI
f(k + 1) (1-)(()) + 8,
1
3(N +1
1)
K=D
where o is the cumulative distribution function (cdf) of binomial distribution B(N + 1,13) and Ind Nentityy N) N Nentity
0 << 8 < (1 -1)

---

Generally, the Nentity is large and the answer rate item d is negligible. In the rest of the paper, we denote E M(++)) 2x (b)))/ which is good approximation of R.
< 10% in almost all queries, so the
With this lemma, we get a closed-form expression of the expectation of the ranking- based metric Wt. However, this expression cannot explain why the metrics will degrade. Next, derive the form of derivative of the expectation E w.r.t the model strength to account for its degradation.
Corollary 4.1 (Derivative of Expectation w.r.t Model Strength). Let g(r) = (r) E N+ and g(0) Under the condition of 4.1 the derivative of the expectation w.rt the model strength & is
di
1R- (k)).
(2)
de
LB(N +1
And for the most-used metrics MRR and Hits K, their derivative are expressed as follows.
Corollary 4.2 (Derivative of MRR w.r.t strength f). For MRR where f(r) = r, vr E N+. its derivative w.r.. f is
dÉ(MRR) de
1-E 8B(N +1)
where E = (1 N+1
When EB and N are not too small, the term is negligible. In this situation, the derivative of the metric MRR w.r. the model strength is approximately of (1/NNE), which will result in insignificant changes in the metric with the increasing of the model strength.
Corollary 4.3 (Derivative of Hits@ K w.r. strength f). For Hits@ where f = for r & k and f= +000 otherwise, the derivative is
di(Hiis@K) +(K - 1),
(4)
de
where & is the cdf of the binomial distribution B(N,EB)
The behavior of Hits @ K is similar MRR when K < N. When f3 is not small and K is too large, the derivative 4(K 1) is so small that the increase could be insignificant.
Finally, we further approximate Equation (T) by more intuitive expression with tolerable error. Theorem 4.1 (Expectation of MRR). For MRR, we can further approximate its expectation by
B(MRR)+ (n(e) In(3) + +nn(N + 2) +
E,
3(N +1)
(1- E max 28(N+1)2 1- (1)1-88)8+1
where y = 0.577 is the Euler's constant and the error ln(1/(E9)) }. B(N+1)
Firstly, we explain the rationales of the approximation È as follows.
. is large enough. For many KGs, especially those commonsense KGs which are not limited to certain field, the number of answers is often quite large. In the experiment conducted by Ren
and Leskovec 2020 there are many tests queries with dozens or hundreds of answers.
Sparsity is not too small. For most real-world KGs, although we do not exactly know their sparsity, we expect many of them could have rather high sparsity 3 due to the incompleteness of knowledge extraction and the long-tail distribution of commonsense knowledge.
Model strength & is too small. Here we are more concerned with how select and evaluate those models that perform well.
Under the above conditions, the relative error is negligible. To further show that our approximation is reliable, we do numerical simulations as shown in Figure For 1 - a 2 0.2 and é > 0.3, the analytical and numerical curves almost overlap, which means the log approximation is accurate. At the same time, we point out the log trend is just the reason why the curve becomes flatter and flatter. The details of the simulation is in Appendix
A.2 A.2
5

---

illustrates the metric degradation intuitively. There are some conclusions about the MRR under the open-wer gpen-world assumption: 1) Although the theoretical maxi- mum of MRR 1, the expectation of the MRR of a perfect model & = is still much lower than 1 and depends on the sparsity of the KG. 2) With the sparsity 3 not very small,
Theorem 4.1 [.
Approxi stion and Simulation of E(ARR)
Sensity alpha
0.8s
0.5g
0.35
the MRR will be a log function of the strength é times the answer number N which means that as the model gets stronger, the increase of the metric MRR will be less and less significant. The sparser the KG is, the more severe the degradation problem is. Note that in the closed-world KG, the curve should be very closed to y x.
0.3
0.4
0.5
0.5
0.2
300
strangth
Figure 1: Theoretical log approxima- tion (a) and numerical simulation (s). The shadow shows the [-2o, 20] inter- val, where a is the numerical std.
4.2 Inconsistency due to high variance
In Figure D another notable phenomenon is the vibrated curves, which suggests instability of the metric and relatively high variance. This phenomenon combined with the flattening of the expectation might not mean stronger models unless the difference of the metric is large enough, because the increasing of expectation could be easily overwhelmed by the variance.
lead to inconsistency, which means higher MRR
One trivial method solve the problem is to use more test queries. Here we show the number of queries required to ensure the reliability of conclusions can be very large.
Theorem 4.2 (Consistence with High Probability). Assuming the number of test queries N₂ is large enough (Ng > 50), we can approximate the average MRR Di E' MRR((g) to follow normal distribution. Given two independent models M1 and M2 whose strength is and + AE respectively. The probability of inconsistency between two models can be approximated as follows.
/N In(1 4
P ((R(MM)) 2 -M(M2)] -V 3(N +
(5)
where V the edf of the standard normal distribution.
Note for given KG, the sparsity 3 and the answer number N are fixed. Assuming 0 Af < 1, we At have V(8,E) R V(3, 8 + AE) == and In(1 40 7. Then we have the following corollary.
Corollary 4.4 (Lower Bound of the Number of Queries). Under the above assumption of df & 1, with the upper bound of inconsistency probability p. the number of test queries required N, has lower-bound as follows.
N₂ N cB,,,N.p)
(6)
(A0)2
where c(8,e, = 2(3E(N + +))0-
Note that the required number is of the second order ((1)/l)3), which means one should be particularly careful when comparing two models with close strength. For example, when we set
0.35, & = 0.7, N = 43 and p = 5% we have Rs 2.85 where we use the numerical variance V 7.4 x 10-3 In this situation, when Af = 0.05, N₂ 2 1140, while when Al 0.01,
N 28500 which cannot be easily satisfied.
4.3 Correlation between missing and misclassification
In the previous two subsections, we analyze the degradation and inconsistency with independence assumption between missing facts and model predictions. In some conditions, there could be correlation between the missing data and the trained models. Let us give some examples:
The missing facts in closed-world KG G follow some non-uniform distribution. For example, in some KGs, the missing facts are more frequently related to some certain entities. The model could be under-trained on these entities because there are more missing facts related to them when training. And when the model tested, the queries with more missing test answers correspond to the lower predicting capacity.

---

phe 5.8
E14
1.3
Compaton confirest
839
4.1
42A
04
8.5
03
8.5
Figure 2: Theoretical approximation (a) and numerical simulation (s) of the expectation with correlation coefficient p. Details of the figures are the same as in Figure
The target KG has been preliminarily complemented by some models. In this situation, the missing facts show a negative correlation with the predictive power this type of models.
Next, we will extend the previous analysis to the situation without the independence assumption. For this goal, we use the correlation efficient to model the correlation between random event X: fact missing and Y: this fact is predicted by the model.
Definition 4.1 (Correlation between fact missing and model prediction). The correlation coefficient between two random events X and Y can be defined as follows.
P(XY) P(X)
((X)))))
With the correlation coefficient p, the prediction accuracy on missing answers e G Grest and on test answers e E Gtest \ Girain can be calculated as the conditional probability as P(Y
(+ @+vE( -
()a11111-3333-111111 3.0//-pppp and P(Y[X) = f- ELvE(111) 0)3/a.p. We denote them as f and &g respectively.
Theorem 4.1 can then be generalized as follows:
Theorem 4.3. We have the approximation for MRR
L2 In((1) + In(3) + In(N + + E.
B(MRR)
(8)
E1
3(N +1) 11)+1)
The theoretical error analysis is in Appendix A.
We also evaluate the approximation by numerical
simulation and the results are shown in 2 The approximation fits the numerical simulation well. Comparing different models with the same model strength & but different correlation coefficient p. the models with smaller p have the higher MRR. The phenomenon consistent with Corollary 4.5
Corollary 4.5 (The derivative w.rt with correlation). If we have the inequality ( + 2) 2
exp(a [B01-8 -7), then the derivative @E(MRR)
< 0.
Op
The condition in Corollary 4.5 has requirements for lower bound & and If E is close to 0, the condition can be violated. This corollary suggests more severe inconsistency. In a reasonable range, the expectation of MRR is monotonically decreasing w.r. p. This conclusion suggests that the metric MRR may favor the models with smaller p instead of larger Note that the inconsistency of expectation, which cannot be solved by more test queries.
5 Relationship between focus-on-top and degradation
We have pointed out the degradation and inconsistency under the open-world assumption for some most-used ranking-basse metrics. Specifically, the derivative of the metrics w.r.t & can be too small to reflect the increasing of the true improvement of the model strength (degradation). According to Corollary 4.1 the derivative is related the expectation of g(r) r/f(r) where follows binomial distribution. We point out the degradation is due to the too small expectation of g relative to the denominator N, which is inherently caused by property of the metrics called focus-on-top.
The focus-on-top property means that the metrics are more sensitive ranking change in top places. For example, MRR changes from to 0.5 when the ranking changes from to 2, but only changes

---

from 1e-2 to 0.99c-2 when the ranking changes from 100 to 101. This property can simulate the human behavior that people pay more attention the top answers. However, under the open-world assumption, the focus-on-top property causes negative impacts by making the function 1 (r) decrease too fast so that the expectation of g too small relative to N. For example, according to Corollary a smaller K means more focus-on-top and smaller derivative.
We can also understand the relationship intuitively. Focusing-on-top means that few missing answers can have a large impact on the metric, especially when the model performance is already good and the rankings of the rest answers fall into the sensitive range. It is also consistent with our observation that the flatting problem is more severe when the strength l increases.
There is trade-off between focus-on-toy and consistency. Therefore, and inconsistency is to add in some less focus-on-top metrics as a verification when evaluating, which have a re relatively slower descending rate. For example, the log-MRR where fr) log2 (r + 1) and p-MRR where f(r) = rP 0 < < are less focus-on-top than the standard MRR. If the conclusions of these less focus-on-top metrics are consistent with the MRR or Hits @ K, the credibility of the conclusions will be greatly enhanced.
solution to the degradation
Experiments on an artificial KG
In this section, we aim to conduct experiments with practical KGC models on meaningful closed- world KG to further verify conclusions. The reason want closed-world KG is for comparing the reported MRR with the true model strength which should be measured on the full test set. To find boosed-worle KG, however, it is impractical to resort existing real-world ones since we have guarantee that the KG has no missing facts. Therefore, we must resort to some artificial KGs.
For this purpose, we generate artificial family tree KG, which contains 6,004 entities, 23 relations, and 192,532 facts. The relation set contains all common family relations such as parent, child, husband, wife, sister, and brother. The details are included in Appendix A.33 The generated KG is closed-world since all the facts can be deduced by a symbolic reasoning tool called DLV system [Leone et al. [006] (free for academic use). With the cloled-world KG, open-world setting by artificially controlling the degree of random fact missing, which is measured by density d = /test//|Gr f The relation between d and is explained in Appendix A.3
simulate the practical
The generated KG may be representative of a class of real-world KGs with rich rules and simple relations. However, we admit that for Wiki-KGs such as Freebase Bollacker et al., 2008), there may be a certain interval, but the closed-form solution KG corresponding to the latter is impossible to obtain.
With the closed-world KG, we aim verify our previous conclusions restated below:
1. There is metric degradation which means the curves of metric increasing become flatter and flatter with the increasing of model strength f. Further, the degradation may result in inconsistency, where stronger models report lower metric numbers.
2. Considering the correlation between fact missing and model prediction, if the correlation degrees vary among different models, the inconsistency problem may become more severe.
3. The degrees of degradation and inconsistency related to the focus-on- property of the metrics. With less focus-on-top metrics, these problems could be relieved.
Our code and data are available were on two clusters with four NVIDIA A40 and six NVIDIA Geforce 3090 GPUs respectively.
SOOrKK///Ope--ooodKGGG The experiments
6.1 Degradation and inconsistency under independence assumption
We train four KGC models with different hyperparameter settings (which results in 18 different models in total) and test them on full test set Gy \ Gtrain and sparse test set Gtest \ Gtrain respectively. The full test metric can considered as a measurement of model strength E which is what we really want to measure, while the sparse test metric is what we can observe in practice. We plot the sparse-full test curve under different densities in Figure 3 where each curve represents a model whose label is shown in the right legend, and the details of the models are given in Appendix A.4
8

---

derally 953
deriilyy 8536
density 75
0.5
MMA coparse test C481
0.4
MBM Isparee test sel
0.28
(0.03, 0.88
0.26
1054, 0.25)
0.3
0.24
0.0
0.0
022
0.4
0.6
08
1.0
0.2
0.0
0.2
0.4
0.6
0.5
0.22
MBA (full losk seQ
MRA ofull tcst so0)
dencity 75%
deralty 65%
0.50
0.55 0.60 0.65
0.35
MAR test set)
0030-
MER (ipeeeee beee 1ec
0.25
Figure 4: A zoom-in of two curves 4 and under density d = 0.75. The checkpoints of model lying on the red segment all have better full test MRR than the checkpoint M model 7, while reporting worse sparse test MRR under the open-world setting.
1020-
13
0.10
15
0.2
0.05
17
0.0
0.
MAX test se0
1438 (lul oe1)
Figure 3: Full test and sparse test MRR on the artificial family tree KG. Note the ranges of y-axis are different.
From the figure, we first observe that these curves are indeed shaped like log curves. The increasing of the sparse test MRR is slower and slower with the increasing of the full test MRR. Due to the flatting of the curves, the same sparse MRR has a rather broad interval of the corresponding full metric. This phenomenon indicates the degradation the metric MRR. And as the sparsity increases, the range of the y-axis shrinks (i.e., the curves become flatter), which means the degradation is more severe. Further, these results demonstrate the inconsistency problem MRR. To illustrate this point more clearly, we zoom in part of the full figure with two curves as shown in Figure 4 For the model checkpoint corresponding to point on curve 7, any model checkpoint corresponding to a point on the red segment of curve 4 is actually stronger than that model, but reports a lower sparse MRR.
6.2 Correlation between fact missing and model prediction
In this part, we will simulate the third example we provided in Section 4.3 to check our theory considering the correlation between fact missing and model prediction. Here we use one of the trained ComplEx model (labeled as 16) (Trouillon al. (016)] predict on the full test set G \ Gtrain and use its predictions to choose the test set Grest Gtrain and missing facts G Gtest- The missing facts are highly correlated with this ComplEx model and therefore could be correlated with other models according to the correlation between different frameworks and model settings. Then we test the other models except for this ComplEx model on the correlated test set. The results of density d 75% are shown in Figure 5a and others shown in Appendix A.5 Though the correlation coefficient is not available for these different models, we indeed observe the gaps between different models become larger than the independent setting, which suggests the inconsistency is more severe.
6.3 Less focus-on-top metrics
The next conclusion is that with less focus-on-top metrics, the degradation and inconsistency can be relieved. In Figure 5b we show the sparse-full curves with some less focus-on-top metrics (log-MRR and y-MRR) for the experiments from Section 6. Their curves are more close to y = æ instead of the log function. The flatting is less significant due to the wider range of y-axis. We also observe that the gaps between different models become smaller, which indicates inconsistency also relieved. Additional results with more metries, density d and correlation are shown in Appendix A.6
7 Conclusion and future work
In this paper, we study KGC evaluation under the open-world assumption. Theoretically, we model KGC as a positive-negative classification and then deduce an approximation of the expectation the ranking-based based metrics with or without the independence assumption. According to the approximation, we illustrate the degradation and inconsistency of these metrics under the open-world assumption. Furthermore, we point out the focus-on-top property of ranking-based metrics worsen the degradation

---

indesendent
log MRR
0.35
0.30
Min cepare tee
0.25
0.20
0.25
5par55
0.3
6.15
R..5
0.10
0.10
0.05
0.05
0.00
0.00
1.0
0.0
0.2
0.4
0.6
0.8
1.
full
full
Corre ated
0.5-MRR
0.25-M6k
0.5
0.7
MMN Iooven text se0
0.6
0.4
0.4
0.33
0.0
0.4 0.6
1.0
test
(a)
(b)
Figure 5: (a) Full test and sparse test MRR independent (above) and correlated (bottom) family
tree KG. (b) MRR, and less focus-on-top metrics. Both are under density d = 75%
and inconsistency. Finally, we generate closed-world family tree KG and do experiments to verify our theoretical conclusions.
There is still some future work. First, analysis is based the positive-negative classification model, which may be too idealistic. In practice, the ranking in positive and negative parts may not be uniformly random. A more realistic modeling of the KGC task direction for future research. In addition, the correlation between missing facts and prediction could be more complex than our analysis. Finally, we are curious about the possibility to find more fundamental solution to the open- spoldworld problem, which we leave for future work.
Acknowledgments
Z. Lin was supported by the major key project of PCL (grant no. PCL2021A12), the NSF China (No.s 62276004 and 61 61731018), and Project 2020BD006 supported by PKU-Baidu Fund. M. Zhang is supported by the NSF China (No. 62276003) and CCF-Baidu Open Fund
References
Ralph Abboud, Ismail Ceylan, Thomas Lukasiewicz, and Tommaso Salvatori. Boxe: A box embed- ding model for knowledge base completion. In Neural Information Processing Systems, 2020.
Farahnaz Akrami, Mohammed Samiul Saeef, Qingheng Zhang, Wei Hu, and Chengkai Li. Realistic Re-evaluation Knowledge Graph Completion Methods: An Experimental Study. Proceedings of the 2020 ACM SIGMOD International Conference Management of Data, 2020.
Kurt Bollacker, Colin Evans, Praveen Paritosh, Tim Sturge, and Jamie Taylor. Freebase: A collabora- tively created graph database for structuring human knowledge. In International Conference Management of Data, 2008
Antoine Bordes, Nicolas Usunier, Alberto Garcia-Duran, Jason Weston, and Oksana Yakhnenko. Translating embeddings for modeling multi-relational data. In Neural Information Processing Systems, 2013.
Yixin Cao, Xiang Ji, Xin Lv, Juanzi Li, Yonggang Wen, and Hanwang Zhang. Are missing links predictable? an inferential benchmark for knowledge graph completion. In Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the I 1th International Joint Conference on Natural Language Processing (Volume 1: Long Papers), 2021.
10

---

Rajarshi Das, Ameya Godbole, Nicholas Monath, Manzil Zaheer, and Andrew McCallum. Prob- abilistic case-based reasoning for open-world knowledge graph completion. In Findings of the Association for Computational Linguistics: EMNLP 2020, 2020.
Tim Dettmers, Pasquale Minervini, Pontus Stenetorp, and Sebastian Riedel. Convolutional 2D Knowledge Graph Embeddings. In Association for the Advancement of Artificial Intelligence Conference, 2018.
Luis Antonio Galárraga, Christina Teflioudi, Katja Hose, and Fabian Suchanek. Amie: rule mining under incomplete evidence ontological knowledge bases. In Proceedings of the 22nd International Conference on World Wide Web, 2013.
Association
Patrick Hohenecker and Thomas Lukasiewicz. Ontology reasoning with deep neural networks. In Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence, 2020.
Giarratano Joseph and Gary Riley. Expert systems: principles and programming. 1998.
Walid Krichene and Steffen Rendle. On Sampled Metrics for Item Recommendation. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, 2020.
Nicola Leone, Gerald Pfeifer, Wolfgang Faber, Thomas Eiter, Georg Gottlob, Simona Perri, and Francesco Scarcello. The dlv system for knowledge representation and reasoning. ACM Trans. Comput. Logic, 7(3):499-56,, jul 2006. ISSN 1529-3785.
Deepak Nathani, Jatin Chauhan, Charu Sharma, and Manohar Kaul. Learning attention-based embeddings for relation prediction knowledge graphs. Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics, 2019.
Dai Quoe Nguyen, Tu Dinh Nguyen, Dat Quoc Nguyen, and Dinh Phung. A novel embedding model for knowledge base completion based on convolutional neural network. In Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, 2018
Hongyu Ren and Jure Leskovec. Beta Embeddings for Multi-Hop Logical Reasoning in Knowledge Graphs. In Advances in Neural Information Processing Systems, 2020.
Hongyu Ren, Weihua Hu, and Jure Leskovec. Query2box: Reasoning over knowledge graphs in vector space using box embeddings. In International Conference on Learning Representations, 2020.
Matthew Richardson and Pedro Domingos. Markov logic networks. Machine Learning, 62(1): 107-136, Feb 2006.
Ali Sadeghian, Mohammadreza Armandpour, Patrick Ding, and Daisy Zhe Wang. DRUM: End-to- End Differentiable Rule Mining on Knowledge Graphs. 2019.
Zhiqing Sun, Zhi-Hong Deng, Jian-Yun Nie, and Jian Tang. Rotate: Knowledge graph embedding by relational rotation in complex space. In International Conference Learning Representations, 2019.
Zhiqing Sun, Shikhar Vashishth, Soumya Sanyal, Partha Talukdar, and Yiming Yang. A re-evaluation of knowledge graph completion methods. In Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics, 2020.
Kristina Toutanova and Danqi Chen. Observed versus latent features for knowledge base and text inference. In the 3rd workshop continuous vector space models and their compositionality, 2015.
Théo Trouillon, Johannes Welbl, Sebastian Riedel, Eric Gaussier, and Guillaume Bouchard. Complex embeddings for simple link prediction. In International Conference Machine Learning, 2016.
Shikhar Vashishth, Soumya Sanyal, Vikram Nitin, and Partha Talukdar. Composition multi- relational graph convolutional networks, In International Conference on Learning Representations, 2020.
11

---

Luke Vilnis, Xiang Li, Shikhar Murty, and Andrew McCallum. Probabilistic embedding of knowledge graphs with box lattice measures. In Annual Meeting of the Association for Computational Linguistics, 2018.
Hongwei Wang, Hongyu Ren, and Jure Leskovec. Relational message passing for knowledge graph completion. In the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining, 2021.
Yining Wang, Liwei Wang, Yuanzhi Li, Di He, and Tie- Liu. A theoretical analysis of ndeg type ranking measures. In Proceedings of the 26th Anmual Conference on Learning Theory, 2013.
Bishan Yang, Wen-tau Yih, Xiaodong He, Jianfeng Gao, and Li Deng. Embedding entities and relations for learning and inference knowledge bases. In International Conference on Learning Representations, 2015.
Fan Yang. Zhilin Yang, and William W Cohen. Differentiable learning of logical rules for knowledge base reasoning. In Advances Neural Information Processing Systems, 2017.
Zhanqiu Zhang, Jie Wang. Jiajun Chen, Shuiwang Ji, and Feng Wu. Cone: Cone embeddings for multi-hop reasoning over knowledge graphs. In Neural Information Processing Systems, 2021.
12


Reviews:
[{"review_id": "jSyjaYsntsp", "reviewer": "Reviewer_c8HZ", "summary": "This paper revisits the rank based metrics used for evaluating knowledge base completion (KBC).\n\nLarge KBs, by definition, are incomplete. Models for KBC are evaluated based on their ranking of all entities given a query entity (head entity) and a query relation with the model being penalized for ranking entities that are not present in the held-out test set higher above.\n\nHowever, the paradox lies in the fact that certain answers for which models are penalized are actually correct, since that fact might not just be present in the KB (open-world setting)\n\nThis paper shows that in the open-world setting, the metrics does not capture the true model improvement as the strength of the model increases. Specifically, as the model strength increases, the metrics show a logarithmic trend, i.e. it might be too flat to capture improvements of stronger models (gets worse as sparsity increases) (metric degradation problem)\n\nAlso, more importantly, the metrics might favor a model which would have lower performance than another model if evaluated on a KG with no additional missing edges other than the query (metric inconsistency problem).\n\nLastly, the paper proposes two metrics which focus less on “entities at top” and shows that they can reduce the degaradation and inconsistency problem.", "questions": "The MRR in fig 1 looks surprisingly low. For example, for the most powerful model (strength=1), and with high density, the best MRR only reaches around 0.3? But in practice for KGs such as WN18RR, the MRR goes over 0.5. How do you explain the discrepancy?\n\nIn Line 13 of abstract, shouldnt it say “with many missing facts”, instead of “with not many missing facts”?\n\nThere are certain papers that model open-world setting as a continuously increasing KB where unknown entities and facts are added. Worth citing them for completion - e.g. Probabilistic CBR for Open-world KBC.", "limitations": "Yes, the authors have addressed the limitations of their work.", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\nOriginality:\n\n1. This paper studies in detail the efficacy of the ranking of evaluation of KBC models in open-world setting. The analysis is well done and highly novel. The paper shows that the evaluations are not perfect and also proposes couple of metrics which can fix the problems. These are important contributions.\n\nQuality:\n\n2. The paper is high quality work in general. All the claims are justified by both theory, simulation and experiments\n\nClarity:\n\n3. Very clearly written. The paper was very easy to follow.\n\nSignificance:\n\n4. The paper makes fundamental contributions in understanding of evaluation metrics and I think the contributions are significant", "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": "YY1h1kSTvW", "reviewer": "Reviewer_Lj1a", "summary": "This paper studies the evaluation of KG completion under the open-world assumption. Its main contribution is to give a theoretical analysis of common evaluation metrics on the open-world knowledge graph and point out the shortcomings of focus-on-top metrics. In addition, experiments on a closed-world dataset validate the obtained conclusions. ", "questions": "If necessary, the authors can choose to discuss the proposed issues in the above *Strengths And Weaknesses* section to help me make a better assessment of this paper.", "limitations": "I would like this paper to be accepted, but there are several limitations of this article that need to be noted. This paper only analyzes several existing evaluation metrics, and does not propose a better solution. In addition, due to its rich set of high-quality rules, the relational pattern of Family Tree KG is much simpler than that of a large-scale knowledge graph, so some basic models can also get high scores. Experimental analysis on such toy KGs may be biased, although I understand that full labeling of large-scale knowledge graphs is impossible.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Pros：\n\n- The paper is well written and the theoretical analysis is easy to understand.\n\n- A fundamental problem of KGC is analyzed, which is beneficial for the development of the field.\n\nCons:\n\n- There is a work that investigates a similar problem (https://arxiv.org/abs/2108.01387, although its main contribution is not theoretical analysis), but a related discussion is missing.\n\n- Lack of discussion of specific relations. For example, 1-to-1 relations do not have the problem of degradation and inconsistency. However, some 1-to-n relations, especially when n is large, may have this problem. ", "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": "KX8RNgRammq", "reviewer": "Reviewer_DMNd", "summary": "This paper discusses the gap between close-world and open-world assumptions, which are two major assumptions for KGs. Even though the missing links in KGs are uncertain in advance, the current ranking-based evaluation metric such as MRR and Hits@K heavily relies on the close-world assumption. It may cause a wrong conclusion when comparing KG completion models. The theoretical analysis through the expectation for the rank of entities based on the model strength shows that when the links in a KG are sparse, the model gets stronger the increase of the metric MRR will be less and less significant. Thus, in this case, there is a possibility that the evaluation result is severely affected by its variance. It may cause inconsistent comparison results between models. Empirical analysis of the artificially created dataset shows that the theoretical analysis is consistent with the observed results.", "questions": "- Based on your conclusion that large $l$ can reduce the variance problem in the ranking-based metrics, Hits@K is more robust than MRR since it is the same as purging entities with low $l$ in predicted results. Is this understanding correct? Clearing this point is quite beneficial for readers comparing KG models.\n- Related to the first question, it seems that just using Hits@1 can avoid the problem. If so, Is there any problem with this choice?", "limitations": "- This paper reveals the unreliable behavior of the current ranking-based evaluation metrics. However, only increasing test queries are presented as a solution.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n- The stated problems are theoretically and empirically investigated.\n- The information in this paper is essential for creating appropriate test sets in the future since sparse relationships in the test set may make it difficult to evaluate models correctly.\n\nWeakness:\n\n- Although this paper reveals the problem in the current raking-based evaluation metrics, its solution is not presented, excluding the increase of queries in testing.", "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": "ION5AlubQ1f", "reviewer": "Reviewer_LAYz", "summary": "The paper investigated the KGC evaluation framework under the open-world assumption. This is a case where unknown triplets are considered to include many missing facts not included in the training or test sets. The paper consider KGC as a positive-negative classification and deduce an approximation of the expectation of the ranking-based metrics with or without the independence assumption. \n\nThe currently used metrics such as mean reciprocal rank (MRR) and Hits@K, show an unexpected behavior under the open-world assumption. \nAuthors point out the focus-on-top property of ranking-based metrics worsen the degradation and inconsistency. \nConsidering the variance, the paper shows that the degradation in the reported numbers result in incorrect comparisons between different models, where stronger models may have lower metric numbers. \n", "questions": "How to assume freshness, authority, accuracy when adding/detecting a triple when dealing with the open-world? \nHow to detect the accuracy of a triplet when dealing with open domain?\nHow to deal with bias, etc.?\n\n", "limitations": "Please refer to comments above", "rating": 4, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper discusses a very important research topic of big interest to the community. The comparison with current approach showd improvements point toward true north, which is nice to see. The paper consider KGC as a positive-negative classification and deduce an approximation of the expectation of the ranking-based metrics with or without the independence assumption. \n\nOpportunities:\nThe proposed evaluation is still not convincing yet, even though we see improvements to current techniques. The assumption of positive-negative classification model doesn’t seem ideal. Other assumptions doesn’t seems matching a real world problem. This include the ranking in positive and negative parts that is considered random uniformly. \nHow to assume freshness, authority, accuracy when adding/detecting a triple when dealing with the open-world.  \n\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": {}}]

Author rebuttal:

Decision: Accept