# Are We Wasting Time? A Fast, Accurate Performance Evaluation Framework for Knowledge Graph Link Predictors

arXiv: https://arxiv.org/abs/2402.00053 · HTML: https://mlsanity.com/paper/2402.00053/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 38 of its 70 references that are in the map.
- First posted on arXiv 25 Jan 2024.

## Builds on (most cited first, 30 of 38)

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Open Graph Benchmark: Datasets for Machine Learning on Graphs](https://mlsanity.com/paper/2005.00687/) (2020)
- [Embedding Entities and Relations for Learning and Inference in Knowledge Bases](https://mlsanity.com/paper/1412.6575/) (2014)
- [Complex Embeddings for Simple Link Prediction](https://mlsanity.com/paper/1606.06357/) (2016)
- [RotatE: Knowledge Graph Embedding by Relational Rotation in Complex Space](https://mlsanity.com/paper/1902.10197/) (2019)
- [Convolutional 2D Knowledge Graph Embeddings](https://mlsanity.com/paper/1707.01476/) (2017)
- [Knowledge Graphs](https://mlsanity.com/paper/2003.02320/) (2020)
- [OGB-LSC: A Large-Scale Challenge for Machine Learning on Graphs](https://mlsanity.com/paper/2103.09430/) (2021)
- [TuckER: Tensor Factorization for Knowledge Graph Completion](https://mlsanity.com/paper/1901.09590/) (2019)
- [Neural Bellman-Ford Networks: A General Graph Neural Network Framework for Link Prediction](https://mlsanity.com/paper/2106.06935/) (2021)
- [Inductive Relation Prediction by Subgraph Reasoning](https://mlsanity.com/paper/1911.06962/) (2019)
- [Query2box: Reasoning over Knowledge Graphs in Vector Space using Box Embeddings](https://mlsanity.com/paper/2002.05969/) (2020)
- [Beta Embeddings for Multi-Hop Logical Reasoning in Knowledge Graphs](https://mlsanity.com/paper/2010.11465/) (2020)
- [CoDEx: A Comprehensive Knowledge Graph Completion Benchmark](https://mlsanity.com/paper/2009.07810/) (2020)
- [SimKGC: Simple Contrastive Knowledge Graph Completion with Pre-trained Language Models](https://mlsanity.com/paper/2203.02167/) (2022)
- [PyKEEN 1.0: A Python Library for Training and Evaluating Knowledge Graph Embeddings](https://mlsanity.com/paper/2007.14175/) (2020)
- [Open-World Knowledge Graph Completion](https://mlsanity.com/paper/1711.03438/) (2017)
- [Relational Message Passing for Knowledge Graph Completion](https://mlsanity.com/paper/2002.06757/) (2020)
- [InGram: Inductive Knowledge Graph Embedding via Relation Graphs](https://mlsanity.com/paper/2305.19987/) (2023)
- [Relation Prediction as an Auxiliary Training Objective for Improving Multi-Relational Graph Representations](https://mlsanity.com/paper/2110.02834/) (2021)
- [Type-Constrained Representation Learning in Knowledge Graphs](https://mlsanity.com/paper/1508.02593/) (2015)
- [An Open Challenge for Inductive Link Prediction on Knowledge Graphs](https://mlsanity.com/paper/2203.01520/) (2022)
- [EARL: Joint Entity and Relation Linking for Question Answering over Knowledge Graphs](https://mlsanity.com/paper/1801.03825/) (2018)
- [Candidate Generation with Binary Codes for Large-Scale Top-N Recommendation](https://mlsanity.com/paper/1909.05475/) (2019)
- [KGLM: Integrating Knowledge Graph Structure in Language Models for Link Prediction](https://mlsanity.com/paper/2211.02744/) (2022)
- [Efficient Non-Sampling Knowledge Graph Embedding](https://mlsanity.com/paper/2104.10796/) (2021)
- [Transformer-based Entity Typing in Knowledge Graphs](https://mlsanity.com/paper/2210.11151/) (2022)
- [Beyond NED: Fast and Effective Search Space Reduction for Complex Question Answering over Knowledge Bases](https://mlsanity.com/paper/2108.08597/) (2021)
- [RecPipe: Co-designing Models and Hardware to Jointly Optimize Recommendation Quality and Performance](https://mlsanity.com/paper/2105.08820/) (2021)
- [Re-thinking Knowledge Graph Completion Evaluation from an Information Retrieval Perspective](https://mlsanity.com/paper/2205.04105/) (2022)

## Abstract (arXiv)

The standard evaluation protocol for measuring the quality of Knowledge Graph Completion methods - the task of inferring new links to be added to a graph - typically involves a step which ranks every entity of a Knowledge Graph to assess their fit as a head or tail of a candidate link to be added. In Knowledge Graphs on a larger scale, this task rapidly becomes prohibitively heavy. Previous approaches mitigate this problem by using random sampling of entities to assess the quality of links predicted or suggested by a method. However, we show that this approach has serious limitations since the ranking metrics produced do not properly reflect true outcomes. In this paper, we present a thorough analysis of these effects along with the following findings. First, we empirically find and theoretically motivate why sampling uniformly at random vastly overestimates the ranking performance of a method. We show that this can be attributed to the effect of easy versus hard negative candidates. Second, we propose a framework that uses relational recommenders to guide the selection of candidates for evaluation. We provide both theoretical and empirical justification of our methodology, and find that simple and fast methods can work extremely well, and that they match advanced neural approaches. Even when a large portion of true candidates for a property are missed, the estimation barely deteriorates. With our proposed framework, we can reduce the time and computation needed similar to random sampling strategies while vastly improving the estimation; on ogbl-wikikg2, we show that accurate estimations of the full, filtered ranking can be obtained in 20 seconds instead of 30 minutes. We conclude that considerable computational effort can be saved by effective preprocessing and sampling methods and still reliably predict performance accurately of the true performance for the entire ranking procedure.