Link Prediction (LP) is the task of inferring relations between entities in a Knowledge Graph (KG). LP is dificult, due to the sparsity and incompleteness of real-world KGs. Recent advances in Machine Learning have led to a large and rapidly growing number of relation learning models, from the seminal work of Bordes et al. [4] to the recent model in [2]. Despite the flurry of papers in this area, just a few datasets and evaluation metrics have emerged as de facto benchmarking criteria. In our work, we question the efectiveness of these benchmarks in establishing the state-of-the-art. The use of unreliable benchmarking practices can have hidden ethical implications, as it may yield distorted evaluation results and overall lead the research community into adopting inefective design choices. To this end, we consider key desiderata of a benchmark formulated as specific questions relevant to the LP task, and provide empirical evidence to answer those questions. Our analysis shows that existing datasets and metrics fall short in capturing a model's capability of solving LP. Specifically, we show that a model can score very high by learning to predict facts about a small fraction of the entities in the training set. Our study provides a more robust evaluation direction for future research on relation learning models, stressing that understanding why LP models reach certain performances is a crucial step towards explaining predicted relations.
Knowledge Graphs (KG) are structured representations of facts
in the real world. In a KG, each node represents an entity, e.g. a
person, a place or a concept; each label represents a relationship
usable to link entities; each edge in the form ⟨ subject, predicate,
object ⟩, represents a fact connecting entity subject with entity
object through the relationship predicate. Examples of KGs are
FreeBase [
KG embeddings are a way of representing the components of a KG as vectors or matrices (embeddings) in a low-dimensional hyperspace, called latent space. Embeddings are computed by training a model on the KG data, and thus carry the semantic meaning of the original KG relations. In other words, given the embeddings of two elements, it should be possible to identify their semantic correlations.
Knowledge Graph Completion is the task of identifying
missing edges (facts) in KGs, by either extracting them from external
corpora, or inferring them from the ones already in the KG [
LP models can be queried by providing a subject (or an object), e.g., “Barack Obama”, and a predicate, e.g., “place of birth”, representing a question of the form “What is Barack Obama’s place of birth?”. Answering such a query amounts to compute the score of each potential object with respect to the current subject and predicate, and to find which one yields the best value. That is, the answer to a LP query is a ranking of the KG entities by decreasing plausibility.
This approach for was explored in the seminal work by Bordes
et al., describing the TransE LP model [
In this paper we critically analyze current benchmarks for LP models. Our study is motivated by the observation that, in current datasets, less than 15% of entities cover more than 80% of facts. Such a skew casts doubts on the suitability of these benchmarks for evaluating LP models. Indeed, we have empirically observed that a model can achieve state-of-the-art scores by learning to predict facts about a tiny fraction of the entities with highest degree in the training set, which are also the most mentioned entities in the test set as well. As an informative example, in FB15k, the most commonly used among the LP datasets, the entity node with the highest degree is by far “United States”, with ≈ 2% of all edges; the vast majority of the “nationality” facts in the test set refer to “United States” as well. Therefore a model that learns to predict U.S. citizens only can obtain results comparable or even better than one that attempts to learn the nationality relation in detail.
Our contribution. We argue that the research community is not best served by benchmarks that allow for such a discrepancy to go unnoticed. Therefore, we provide a constructive contribution towards the definition of more efective benchmarks for LP models: () we formulate some key questions to highlight some of the most desirable properties for LP benchmarks; () we conduct an extensive experimental analysis to understand whether the currently employed benchmarks satisfy such properties or not, and why. In doing this, we also highlight the ethical implications potentially connected with the limitations of the current benchmarks. 2
In this section we describe the currently employed LP
benchmarks; analogously to [
The most popular datasets for LP benchmarking consist of
facts sampled from the FreeBase [
The FB15K dataset has been extracted by the TransE authors selecting all facts containing the 100 most mentioned entities in FreeBase also featured in the Wikilinks database1 (thus including their low-degree neighbors). Defining a full-fledged benchmarking workload was beyond their intentions; nonetheless, most of the approaches inspired by TransE have been evaluated against the same dataset and metrics, making them a de facto benchmark.
The FB15K-237 dataset is a FB15K subset built by [
The WN18 dataset, analogously to FB15K, was built by the
authors of TransE. They used the WordNet ontology [
The WN18-RR dataset was built by [
FB15K WN18 FB15k-237
and the number of mentions of a relationship as, respectively, the number of times that this entity or relationship is mentioned in diferent facts of a dataset.
Both FB15K and WN18 show severe skew in both entity degrees and relationship mentions. Figures 1(a) and 1(b) plot their distributions, showing that the large majority of entities (relationships) have a very low degree (number of mentions), whereas a small minority of them can reach massive representation. 2.1
Evaluation for LP models is typically performed on the task of Entity Prediction. Given the number of entities , for any test fact ⟨, , ⟩: () s is removed from the triple, obtaining ⟨ ?, p, o ⟩; () all entities are tested as the triple subject and ranked according to 1https://code.google.com/archive/p/wiki-links/ (a) Distribution of entity degrees in FB15K and WN18. (b) Distribution of relationship mentions in FB15K. WN18 is omitted as it only features 18 relationships. the resulting score: the original subject s should thus rank as low as possible. An analogous pipeline is used for predicting object o.
These resulting rankings enable the following global metrics: • Mean Rank (MR), i.e. the average rank of the correct subject (object) over all predictions. • Mean Reciprocal Rank (MRR), i.e. the average of the inverse ranks of the correct subject (object) over all predictions. • Hits@K, i.e. the fraction of correct subject (object) predictions with rank equal or lesser than K. The most common choices for K are 10 and 1.
The above described metrics can be computed either in two different settings, dubbed raw scenario and filtered scenario. As a matter of fact, an incomplete triple ⟨ ?, p, o ⟩ might accept multiple entities as correct answers; an answer is correct if the resulting fact is already contained in the training, validation or test set. In raw scenario these entities are still considered “mistakes”, and therefore, if they outscore the expected answer, they afect the prediction rank. On the contrary, in filtered scenario they are considered acceptable, so if they outscore the expected entity they are just ignored. 3
In this section we define key questions that a good LP benchmark should answer in the afirmative, and investigate whether the current benchmarks satisfy them or not, providing experimental evidence to all our claims. We finally provide an overall discussion for the potential ethical implications of the defined questions and their extent in this research field.
In our experiments, we take into account two representative
models, namely TransE [
TransE is one of the first KG embedding systems, and has inspired dozens of successors. It represents facts as translations in the latent space: its scoring function uses the relationship embedding as a translation vector to move from the embedding of the subject to the one of the object.
DistMult is very popular due to its simplicity: its scoring
function is a bilinear product among the embedding of the subject,
a diagonal matrix based on the embedding of the relationship,
and the embedding of the object. If properly fine-tuned, it has
been recently shown to surpass most models in the state of the
art [
We stress that our goal is not to determine which one, among TransE and DistMult, is better: our purpose is rather to investigate the efectiveness of current benchmarks of highlighting their diferences.
TransE DistMult TransE DistMult TransE DistMult TransE DistMult
MR 70.6 156.3 MR 353.5 741.9 MR 494.5 928.9 MR 5304.3 9953.5
FB15K MRR
Our experiments have been performed on a server environment
with a CPU Intel Core(TM) i7-3820 at 3.60GH, 16GB RAM and
a GPU NVIDIA Quadro M5000. We have employed the
Tensorlfow implementation of TransE and DistMult provided by the
OpenKE toolkit [
TransE DistMult
Epochs Analysis. This question is related to the relevance of the benchmark. An LP benchmark is relevant if it actually measures how good the system is at learning relations.
A limitation of current benchmarks lies in their use of global metrics (Hits@K, Mean Rank, Mean Reciprocal Rank) that relate to the overall number of accurate predictions rather than their quality. This practice does not take into account that some facts may be inherently diferent than others. In other words, global metrics do not let the specific strengths and weaknesses of diferent models surface: this does not allow to investigate in which aspects a model performs better or worse than the others, and why. Ultimately, we believe that this hinders our understanding of what our systems are actually learning.
Furthermore, as pointed out by [
Finally, it has been recently observed [
To prove our claim we observe that most datasets display very skewed degree distributions. Our experiments show that the degree of an entity in training set largely afects the LP prediction accuracy in testing; nonetheless, this strong correlation is completely overlooked by the commonly employed global metrics. We plot in Figure 2 the correlation between the entity degree and the prediction performances for the entities with that degree. We measure performances with Hits@10 and MR metrics. Our results provide strong evidence that a higher degree yields better predictions; this pattern holds for the vast majority of entities, up to 1K mentions. We note that despite reaching comparable Hits@10 overall, DistMult can significantly outperform TransE on low degree entities, while TransE is better on the few high degree entities.
We believe that insights like these are vital to understand what our models are actually learning, and to choose the most suitable model for a specific setting; nonetheless, they are completely unobtainable by just relying on current benchmarking metrics.
In order to provide an explanation for the correlation between degree and LP performances, we have analyzed how the degree in training facts correlates to the average distance between the (a) Entity degree in training set and average Hits@10.
(b) Entity degree in training set and average Rank. entities with that degree and their closest neighbor. We report our findings in Figure 3a; in this chart, in order to yield more robust results, for each entity we actually consider an average of the distances from the top three closest neighbors. Interestingly, higher degrees typically correspond to more “isolated” embeddings in the latent space, with greater distances from their closest neighbors.
We interpret this as illustrated in Figure 3b: a "rich" entity such as United States has a very isolated embedding, while Washington and New York lie in a dense area. On the one hand, due to the lack of alternatives in the close neighborhood, it is reasonably easy to operate transformations in the latent space and answer correctly United States to the question ⟨ ℎ, _ , ?⟩. On the other hand, the inverse question ⟨ , , ?⟩ is much more dificult, because it requires to learn a very precise transformation, in order to disambiguate between Washington and New York.
Answer. Entities with high degree, like United States, can boost the ability of a model to predict relations mentioning them (e.g., capital_of ). Therefore, it is hard to understand whether a model has learned a given relation precisely or only its top mentioned entities, by looking only at global metrics like Hits@10.
Analysis. The fairness of a benchmark is the absence of unwanted biases in any operation of its workload. Fairness depends both on the metrics (i.e. what is measured) and on the composition of the test set (i.e., how the measure is computed). In the context of LP, fairness is compromised by the the same correlation observed in the previous section between entity degrees and prediction accuracy. Since both the training set and the test set are obtained from the same uniform sample of the KG, an entity with high degree in the training set will be mentioned more than the others in the test set too. The over-representation of some (a) Closest neighbours distance by degree (TransE, FB15K).
(b) Stylized example of the high entity degree efect. entities in the test set, combined to the fact that the same entities also enable better predictions, leads to an overall unfairness of the benchmark, favouring “easy” entities with high degrees over harder ones with medium and low degrees.
We demonstrate this by studying how progressively skipping test predictions for the top-degree entities afects global performances. We show our results in Figure 4: in both Mean Rank and Hits@10 curves, the more high-degree entities are ignored, the worse the performances become. At this regard, the Hits@10 graph also confirms the slightly diferent behaviours of TransE and DistMult, with the former seemingly more depending on the degree than the latter.
We have computed the number of entities that contribute the most to the global Hits@10 metrics. The results are impressive: in FB15K 80% of the global Hits@10 come from 24.1% entities in TransE, from 28.5% entities in DistMult. An even more extreme situation is witnessed in WN18, where 80% of the global Hits@10 come from 9.87% entities in TransE and 11.6% entities in DistMult.
Answer. High degree entities, in addition to be more easily inferred, are also over-represented in the test set and a model may obtain significantly good evaluations by just focusing on a small number of high-degree entities. (a) Global Hits@10 when progressively skipping tests on top degree entities (FB15K). (b) Global Mean Rank when progressively skipping tests on top degree entities (FB15K). Analysis. Overfitting takes place when a model matches its dataset too closely, conforming to noise and irrelevant correlations in its samples: an overfitted model fails to generalize, and will not behave correctly when dealing with unseen data. A good benchmark can highlight the emerging of overfitting.
In the LP scenario, as already pointed out by [
We have also observed that, when removing from both training and test sets the top-degree entities and retraining the model, performances improve instead of worsening as one would expect from the previous findings (note that in this experiment we are also retraining, diferently from the experiment reported in Figure 4). This counter-intuitive pattern is steadily visible in Table 4 when removing the top 10, 25 and 100 entities. This phenomenon may be partly caused by the fact that, when removing a high-degree entity, along with all of its facts, a large number of test “questions” about its low-degree neighbors (on which the model would perform badly) are removed as well. Nonetheless, obtaining paradoxically better results when removing training samples that the system would apparently learn well is a typical sign of overfitting. In our case, removing from the training set entities whose embeddings would take very large portions of the embedding space may allow the other entities to be placed in better positions; this can be seen as a form of regularization.
Complete Top 10 entities removed Top 25 entities removed Top 100 entities removed
MR
MRR 70 66 64 68
Finally, all the currently employed benchmarks display a static separation between training set, validation set and test set. This is known to be a bad practice, because in time it may favour models overfitted on this configuration. Running K-folding crossvalidation for the two models on both FB15K and WN18 we did not observe significant signs of this form of overfitting yet. Nonetheless, we advice to employ K-folding whenever possible as a way to prevent it in the future.
Answer. The counter-intuitive boost of performances when removing high-degree entities from both the training and test set suggests an undetected form of overfitting towards these entities.
The above mentioned observations on the relevance, fairness and capability to discourage overfitting of the current benchmarking practices can have interesting implications within the ethics of information processing.
Relying on inefective benchmarks undermines the capability to assess the quality of the software and of the data it should manage. We have highlighted that the current evaluation practices may not detect, or may even penalize desirable properties in LP models. For instance, the results currently yielded in evaluation can not tell whether a model is learning a large set of relations or, rather, a narrow set of entities. This can lead to systematic overlooking of underrepresented entities, because systems that actually reason on the the entire set of entities can be outranked by models that overfit on few over-represented ones.
We also point out that the opacity of current results, computed with global metrics over large batches of test facts, makes it almost impossible to interpret the behaviours of models. This, of course, has negative efects on their explainability and, ultimately, on their trustworthiness. 4
To the best of our knowledge, there are just a few papers
investigating the validity of current LP benchmarks, and providing
interpretation for the performances of relation-learning models.
Works related to ours can be roughly divided into two main
categories, depending on whether they address limitations of the
standard metrics or of the datasets used in this research field. For
instance, the already mentioned work by [
Limitations of standard metrics. The most similar work to
ours is [
Limitations of standard datasets. Some of the current LP
benchmarking workloads have been already put into discussion
by a few previous works, to which we refer in our analysis. In
general, these works do not aim at performing a systematic
investigation of the benchmark properties; on the contrary, they
just highlight a specific issue, often in the context of presenting
a new model or implementation. To the best of our knowledge,
[
Starting from their analysis, [
Other tasks. For the sake of completeness we also observe that,
when proposing new models for LP, many papers analyze their
applicability and performances on related tasks too. For instance,
the authors of [
We have analyzed the current LP benchmarks, observing that the training sets of their datasets display severely skewed distributions in both the degrees of entities and the mentions of relationships.
We have experimentally demonstrated that LP models are deeply afected by these unbalanced conditions; nonetheless, these efects go completely unnoticed by the current evaluation workloads, thus casting doubts on their relevance. We have also displayed that entities and relationships that are highly mentioned in training sets tend to be over-represented in test sets too, afecting the fairness of the evaluation workload. We have finally reported that, ignoring entities with high degree (and thus high performances), LP models show a counter-intuitive improvement in performances, potentially attributable to overfitting.
Overall, our results raise concerns on the efectiveness of these benchmarks. We demonstrate that relying on global metrics over heavily skewed distributions hinders our understanding of LP models; all in all, our results imply that at their current state these benchmarking practices may not be able to capture and fairly measure the capability of relation-learning models to efectively learn relations.
Work funded in part by Regione Lazio LR 13/08 Project “In Codice