A Re-evaluation of Knowledge Graph Completion Methods

1 Introduction

• Knowledge Graph Completion predicts missing links in incomplete knowledge bases, commonly by embedding entities and relations and scoring candidate triplets.Knowledge bases are represented as multi-relational graphs of factual triplets.Source: §1 · p. 1
• Recent neural KGC papers report unusually high performance gains that vary across datasets, and these results are often unanalyzed and misleading to the research community.The methods use complex black-box CNN, RNN, GNN, and capsule-network score functions.Source: §1 · p. 1
• The proposed evaluation protocol addresses a flaw that gives a perfect score to a model that outputs a constant regardless of its input, enabling fair comparisons across score functions.The authors use it to re-examine recent methods and compare them with existing approaches.Source: §1 · p. 1

Background

• Table 1 reports inconsistent MRR improvements relative to ConvE across methods on FB15k-237 and WN18RR.Source: Table 1 · p. 2
• KGC predicts missing facts from known triplets; common methods embed entities and relations and score valid triplets above invalid ones.A score function maps each (head, relation, tail) triplet to a score.Source: §2 · p. 2
• Evaluation ranks the true triplet against candidates, while the filtered setting removes other known correct triplets from the candidate set.The filtered setting removes known correct triplets from training, validation, and test data except the triplet being evaluated.Source: §2 · p. 2

Related Work

• Kadlec et al. (2017) and Jain et al. (2020) questioned whether model gains stem from architecture rather than tuning or training objectives; this paper instead scrutinizes evaluation procedures.Chandrahas et al. (2018) studied embedding geometry and task performance, while Nayyeri et al. (2019) examined loss functions.Source: §2 · p. 2
• Jain et al. (2018) studied protocols for out-of-vocabulary entities, but their analysis was limited to non-neural approaches.Source: §2 · p. 2

Background

• In one ConvKB example, 58.5% of negative samples received the same score as the valid triplet.Scores are normalized to [0, 1], with lower scores better.Source: Figure 1 · p. 2

3.1 Inconsistent Improvements over Benchmark Datasets

• ConvKB improves MRR by 21.8% over ConvE on FB15k-237 but degrades by 42.3% on WN18RR, while RotatE and TuckER improve consistently across both datasets.These inconsistent gains occur for several recent neural-network methods.Source: §3.1 · p. 2

3.2 Observations on Score Functions

• On FB15k-237, ConvKB and CapsE average 125 and 197 entities tied with valid-triplet scores, respectively, versus around 0.002 for ConvE.For one triplet, 8,520 of 14,541 negatively sampled triplets received exactly the same score as the valid triplet.Source: Figure 2 · p. 3, §3.2 · p. 3
• ReLU zeros 87.3% of ConvKB neurons and 92.2% of CapsE neurons, versus around 41.1% for ConvE, making several triplet representations similar and their scores identical.At least 14.2% of ConvKB neurons and 22.0% of CapsE neurons are zeroed.Source: §3.2 · p. 3, Figure 3 · p. 3

4 Evaluation Protocols for KGC

• The proposed scheme breaks ties by placing the correct triplet at the beginning (TOP), end (BOTTOM), or a random position (RANDOM) in T ′.It assumes that triplets are sorted in a stable manner.Source: §4 · p. 3
• TOP can advantage models biased toward equal scores, while BOTTOM can penalize them by assigning the correct triplet the least possible rank among tied candidates.Under BOTTOM, this occurs when many triplets share the correct triplet’s score.Source: §4 · p. 4
• RANDOM is recommended for model comparisons because it is both rigorous and fair when multiple candidates receive the same score.The authors say this reflects the real-world choice among equally scored candidates: select one randomly.Source: §4 · p. 4

5.1 Datasets

• The evaluation uses FB15k-237, a subset of FB15k with inverse relations deleted to prevent direct inference of test triples from training.Source: §5.1 · p. 4

5.2 Methods Analyzed

• The study classifies ConvE, RotatE, and TuckER as non-affected, and ConvKB, CapsE, TransGate2, and KBAT as affected methods.Source: §5.2 · p. 4

5.3 Evaluation Metrics

• Using authors’ code and hyperparameters, the authors evaluate filtered Mean Reciprocal Rank (MRR), Mean Rank (MR), and Hits@10 (H@10).Source: §5.3 · p. 4

5.4 Evaluation Results

• Affected methods varied considerably by protocol, scoring best with TOP and worst with BOTTOM, while ConvE, RotatE, and TuckER remained consistent.The RANDOM protocol was robust to random seeds; results averaged five runs with standard deviations, and the authors could not re-evaluate TransGate because no open-source implementation was available.Source: §5.4 · pp. 4–5

• The proposed RANDOM protocol can distinguish KGC methods affected by score-function issues and inappropriate evaluation from other methods.The study encourages the research community to use RANDOM for all KGC evaluation purposes.Source: §6 · p. 5
• Many recent neural network-based KGC methods have score-function issues that, alongside inappropriate evaluation protocols, inflated their reported performance.Source: §6 · p. 5
• The study reexamines recent neural network-based KGC techniques extensively.Source: §6 · p. 5

A Results on WN18RR dataset

• The protocols are evaluated on WN18RR, a WN18 subset containing lexical relations between words, with inverse relations removed.The paper says the WN18RR results support conclusions similar to those in Section 5, but those conclusions are not specified in the supplied passages.Source: A Results on WN18RR dataset · p. 6
• Table 3 compares performance under different evaluation protocols, reporting TOP and BOTTOM changes relative to RANDOM.The supplied passage gives the table’s scope but not its result values.Source: Table 3 · p. 7
• On WN18RR, CapsE uses pre-trained 100-dimensional Glove embeddings for initialization, while KBAT’s test-data leakage is fixed in these experiments.The table caption notes that CapsE’s initialization makes its comparison on WN18RR still unfair.Source: Table 3 · p. 7
• Only ConvKB has a large number of negative triplets assigned the same score as valid triplets on WN18RR.Figure 4 plots the frequency of negative triplets with the same score as the valid triplet during evaluation.Source: Figure 4 · p. 7