PaperlayerView exact revision on arXiv

Source-linked AI summary

Knowledge Graph Embedding for Link Prediction: A Comparative Analysis

Andrea Rossi, Donatella Firmani, Antonio Matinata, Paolo Merialdo, Denilson Barbosa

arXiv:2002.00819v4cs.LGcs.DBstat.ML

TL;DR

Knowledge Graphs remain incomplete, while existing Link Prediction research leaves the effects of model design choices and evaluation practices insufficiently examined. The paper conducts an extensive comparative analysis of embedding-based LP methods and reports evidence about when models perform satisfactorily and where research remains open. Its conclusions also identify evaluation policies that can produce incomparable or misleading results.

  • Problem

    Knowledge Graphs are incomplete, and the literature insufficiently examines model design choices, entity over-representation in aggregated evaluation, and what makes facts easy or hard to predict.

  • Method

    The paper comparatively analyzes KG-embedding LP models using a taxonomy, popular datasets, effectiveness and efficiency measures, structural features, and a rule-based baseline.

  • Results

    The analysis provides experimental evidence about circumstances associated with satisfactory model performance and identifies areas where research still has room for improvement.

  • Takeaways & Limitations

    Evaluation choices matter because some policies can produce incomparable and, in some cases, misleading results.

  • Takeaways & Limitations

    The analysis identifies graph-structure-related areas where current techniques show unsatisfactory performance and future research has room for improvement.

Abstract

from arXiv · show

Knowledge Graphs (KGs) have found many applications in industry and academic settings, which in turn, have motivated considerable research efforts towards large-scale information extraction from a variety of sources. Despite such efforts, it is well known that even state-of-the-art KGs suffer from incompleteness. Link Prediction (LP), the task of predicting missing facts among entities already a KG, is a promising and widely studied task aimed at addressing KG incompleteness. Among the recent LP techniques, those based on KG embeddings have achieved very promising performances in some benchmarks. Despite the fast growing literature in the subject, insufficient attention has been paid to the effect of the various design choices in those methods. Moreover, the standard practice in this area is to report accuracy by aggregating over a large number of test facts in which some entities are over-represented; this allows LP methods to exhibit good performance by just attending to structural properties that include such entities, while ignoring the remaining majority of the KG. This analysis provides a comprehensive comparison of embedding-based LP methods, extending the dimensions of analysis beyond what is commonly available in the literature. We experimentally compare effectiveness and efficiency of 16 state-of-the-art methods, consider a rule-based baseline, and report detailed analysis over the most popular benchmarks in the literature.

1 INTRODUCTION

Knowledge Graphs support broad applications but remain incomplete, motivating Link Prediction and embedding-based approaches. This paper compares these methods extensively while examining evaluation practices and factors associated with predictive performance.

  • Knowledge Graphs represent structured information about entities and relations and are used across domains including question answering, information retrieval, and recommendation.
  • Even state-of-the-art Knowledge Graphs are incomplete, with over 70% of person entities lacking a known place of birth and over 99% lacking known ethnicity.
  • Link Prediction infers missing facts from existing graph facts, while embedding-based models learn low-dimensional representations of KG elements for this task.
  • Existing evaluations aggregate many test facts with over-represented entities, allowing methods to perform well while ignoring much of the remaining graph.
  • The analysis compares 16 embedding-based LP models across diverse architectures, adds a rule-mining baseline, and introduces a taxonomy of KG embedding techniques.
  • It evaluates five popular datasets, efficiency and effectiveness, and structural training-data features linked to each model’s predictive performance on test facts.

2 THE LINK PREDICTION PROBLEM

Link Prediction ranks candidate entities to complete incomplete KG triples, using learned embeddings and scoring functions. Evaluation varies by prediction direction, filtering treatment, tie policy, and ranking metric.

  • Link Prediction completes ⟨h, r, ?⟩ or ⟨?, r, t⟩ by predicting the missing tail or head entity.
  • KG embeddings represent entities and relations as learned numerical vectors that encode graph semantics and support identifying new links.
  • Embedding models score candidate triples, train by increasing positive-fact plausibility and decreasing corrupted negative-fact plausibility, and may learn shared parameters.
  • During prediction, the candidate completing an incomplete triple with the highest score is selected; head prediction is analogous.
  • Evaluation ranks the target entity against all candidates for both head and tail prediction, using raw or filtered treatment of other valid answers.
  • Tie policies range from permissive minimum rank to strict maximum rank, and minimum-rank handling can artificially boost performance.
  • Mean Rank rewards lower averages, whereas Mean Reciprocal Rank and Hits@K reward higher values; H@1 measures first-try correctness.

3 OVERVIEW OF LINK PREDICTION TECHNIQUES

The paper organizes embedding-based link-prediction models into three families and compares their diverse scoring architectures. Tensor decomposition models use learned embeddings to score incomplete-graph facts, while geometric models transform head embeddings and compare them with tails; model constraints create distinct strengths and limitations.

  • Model taxonomy: Sixteen models spanning extremely diverse architectures are used in the comparative analysis, with publication years and received influences also reported.The taxonomy is intended to facilitate understanding of the models and subsequent experiments.
  • Model taxonomy: The taxonomy divides link-prediction models into Tensor Decomposition, Geometric, and Deep Learning families, with smaller color-coded groups.The analysis selects representative models prioritizing state-of-the-art performance and publicly available implementations.
  • Tensor Decomposition Models: Tensor decomposition models treat a knowledge graph as a partially observable 3D adjacency tensor and learn low-dimensional entity and relation vectors.Their scoring functions operate on the embeddings involved in each fact and are optimized over training facts to generalize to unseen true facts.
  • Tensor Decomposition Models: Bilinear models differ through constraints and parameterizations: DistMult is efficient but symmetric, whereas ComplEx and SimplE can model asymmetric relations.ANALOGY imposes normal-matrix and commutative-composition constraints, while TuckER learns a shared tensor core and HolE compresses the full matrix product.
  • Tensor Decomposition Models: HolE is less expensive than an unconstrained bilinear model in both time and space, while TuckER uses a learned shared core with independently sized entity and relation embeddings.HolE obtains this reduction by replacing the full matrix product with circular correlation.
  • Geometric Models: Geometric models transform the head embedding using relation parameters and score facts by measuring distance to the tail embedding.TransE cannot correctly handle one-to-many, many-to-one, symmetric, and transitive relations, whereas relation-specific head and tail embeddings alleviate its many-to-many issues.

4 METHODOLOGY

The methodology combines standardized datasets, efficiency measures, model comparisons, and structural analyses of test facts to study embedding-based link prediction.

  • 4.2 Models: The comparison covers 16 state-of-the-art embedding methods, a rule-based baseline, and model families organized into a taxonomy.The models’ loss functions, constraints, and space complexities are summarized in Table 1.
  • 4.1 Datasets: FB15k-237 and WN18RR remove inverse or equivalent relations to reduce test leakage, while WN18RR still contains 212 unseen test entities affecting about 6.7% of test facts.The datasets were designed as more challenging alternatives to FB15k and WN18.
  • 4.2 Evaluation: Efficiency is evaluated through training time and prediction time, which depend on architecture, hyperparameters, and dataset size.Training time covers learning entity and relation embeddings; prediction time covers full head-and-tail rankings for one test fact.
  • 4.3 Effectiveness Analysis: Effectiveness analysis measures four structural features: source and target peers, relational path support, relation properties, and reified-relation degree.Each feature is treated as a separate research direction and related to model performance across datasets.
  • 4.3.1 Number of Peers: Source peers provide training examples for predicting a target, whereas target peers are alternative targets conditioned on the source and relation.The paper illustrates these peer sets using family relations involving Barack, Michelle, Malia, and Natasha Obama.
  • 4.3.2 Relational Path Support: Relational Path Support estimates how similar a test fact is to training facts with the same relation based on co-occurring relation paths.It is computed using cosine similarity between TF-IDF vectors.
  • 4.3.3 Relation Properties: The study systematically evaluates how relation properties affect the performance of all included models.The analysis defines a comprehensive set of relation properties and groups test facts according to those properties.

5 EXPERIMENTAL RESULTS

This section reports the experiments and comparisons conducted in the analysis.

  • 5 Experimental Results: The paper provides a detailed report of its experiments and model comparisons.The passage introduces the experimental-results section without stating specific outcomes.

5.1 Experimental set-up

The study evaluates 16 link-prediction models and AnyBURL under a standardized experimental setup, reporting effectiveness across common metrics and addressing implementation and evaluation-policy differences.

  • Environment and implementations: The experiments train and evaluate all models from scratch using publicly available implementations whenever possible.ConvR is the only included model without an online implementation.
  • Hyperparameter selection: Hyperparameters are taken from authors’ reports when available; otherwise, the authors hand-tune within published search spaces.Large search spaces and multi-hour training make exhaustive grid or random search generally unfeasible.
  • Evaluation metrics: Global evaluation reports filtered H@1, H@10, MR, and MRR for every model and dataset.The global results are displayed in Table 3.
  • Evaluation policies: Average tie handling replaces min policy for affected models because min policy can produce results that are not directly comparable.The study separately investigates how tie policies alter results.

5.2 Efficiency

Efficiency varies substantially across models and datasets: embedding-model training can take up to hundreds of hours, while AnyBURL trains quickly, and prediction-time comparisons depend on ranking requirements.

  • Training time: Training times range from around 1 hour to approximately 200–300 hours, with YAGO3-10 usually requiring the longest training.The figure reports training time in hours on a logarithmic y-axis.
  • Training time: AnyBURL reaches state-of-the-art performance after 100 seconds on FB15k and WN18 and 1,000 seconds on the other listed datasets.The baseline treats training time as a configuration parameter.
  • Prediction time: ConvKB and CapsE require multiple evaluation batches for one prediction, which may negatively affect prediction performance.The experiments use evaluation batch size 2048, the maximum allowed in the setting.
  • Prediction time: ANALOGY performs particularly well in prediction time among the evaluated models.Prediction time is measured for generating full rankings in both head and tail prediction for one fact.
  • Prediction time: AnyBURL’s full-ranking prediction times are significantly higher than those of embedding models because it was not designed to generate full rankings.Using top-k policy with lower k values would make its computations much faster.

5.3 Effectiveness

Fine-grained effectiveness analyses show that performance depends on graph structure: more source peers and relational-path support generally help, whereas many target peers often hurt, with patterns varying by dataset and relation type.

  • 5.3.1 Peer Analysis: Predictions with more source peers almost always achieve better H@1, while more target peers very often lead to worse H@1.Source peers provide training examples for the target entity’s role, whereas target peers can confuse models with many competing valid entities.
  • 5.3.1 Peer Analysis: These peer-performance correlations are strongest in FB15k and FB15k-237, visible to a lesser extent in YAGO3-10, and less evident in WN18RR.In WN18, most models achieve above 90% H@1, while over 60% of predictions in WN18RR involve fewer than one source or target peer.
  • 5.3.2 Relational Path Support: Greater RPS values generally correspond to better performance, indicating that most models benefit to some extent from longer-range dependencies.The correlation is particularly evident in WN18, WN18RR, and YAGO3-10.
  • 5.3.2 Relational Path Support: Test leakage strengthens the RPS-performance correlation in FB15k and WN18 but weakens it in FB15k-237, WN18RR, and YAGO3-10.The latter pattern indicates that 3-step relational paths are associated with correct predictions in those datasets.

5.4 Reified Relation Degree

The analysis examines how reified-relation degree and evaluation ties affect reported performance, finding degree-dependent H@1 patterns and substantial policy sensitivity for several neural models.

  • Reified Relation Degree: Test facts are partitioned into buckets by the degree of their original FreeBase reified relation, with a separate degree-1 bucket for non-reified facts.H@1 and each bucket’s percentage of the test set are reported separately.
  • Reified Relation Degree: In FB15k, higher reified-relation degree generally corresponds to better H@1 for most models, except TransE, CrossE, and STransE.All models improve under more permissive H@K metrics, including the exceptions.
  • Reified Relation Degree: For TransE, STransE, and CrossE, symmetric relations crowd candidate embeddings, often lowering H@1 while preserving inclusion among larger top-K lists.The analysis links this behavior to their representation of symmetric relations with very small vectors.
  • Tie-policy sensitivity: Tie-policy results can differ substantially: ConvKB and CapsE show huge discrepancies on FB15k and FB15k-237, whereas differences are almost absent on WN18 and WN18RR.CrossE is also sensitive, though less consistently.
  • Tie-policy sensitivity: Replacing ReLU with Leaky ReLU greatly reduces CapsE’s min-versus-average discrepancies, while removing CrossE’s sigmoid eliminates all such discrepancies.The results support saturation as a main cause of the evaluation-policy issue.

6 KEY TAKEAWAYS AND RESEARCH DIRECTIONS

The comparative analysis finds substantial differences across model families, datasets, structural conditions, and evaluation choices. It identifies strong performers and highlights unresolved challenges for future LP research.

  • Model-family findings: Tensor Decomposition models show the most solid results across datasets, with ComplEx plus N3 consistently comparable to AnyBURL.Most included Tensor Decomposition systems display uniform performance across metrics and datasets, although ANALOGY and SimplE fluctuate more.
  • Model-family findings: RotatE delivers remarkably consistent performance across datasets, while translation-only models are generally outclassed by roto-translational models.TransE and STransE particularly struggle on WN18RR, especially for H@1 and MRR.
  • Model-family findings: AnyBURL consistently ranks among the best models across almost all datasets and metrics, making it a remarkably strong rule-based baseline.Deep-learning results vary widely by architecture and implementation; ConvR and RSN achieve similar state-of-the-art performance on several datasets, while ConvKB and CapsE show metric-specific weaknesses and tie-policy issues.
  • Structural effects: Graph structure strongly influences prediction performance: source peers and relational paths help, whereas relatively numerous target peers create difficult scenarios.Source peers provide examples for characterizing relations and targets, while target peers can force embeddings to fit too many answers for one question.
  • Structural effects: Leakage changes the evidence models use: leaked datasets correlate with short paths, whereas leakage-free datasets also involve three-step paths and peer counts.Short inverse or same-meaning relations can provide overwhelming evidence and lead models to disregard other reasoning forms; more balanced settings encourage longer dependencies and analogical reasoning.
  • Evaluation and open problems: Inferring relations with cardinality greater than two remains an open problem, while S2C transformation of FreeBase alters graph structure and semantics.The authors suggest extracting FB15k and FB15k-237 in their original reified structure to assess the effects of avoiding S2C.
  • Evaluation and open problems: Tie-handling policies can produce huge performance differences, making results computed under different policies incomparable or potentially misleading.The analysis recommends using the same policy across studies and considers the average policy the most reasonable choice; saturating activations can contribute to tied scores.

7 RELATED WORKS

Related work includes surveys and targeted analyses of KG embedding and LP methods. This paper differs by experimentally comparing diverse model families, design choices, benchmarking practices, and graph-structural effects.

  • Benchmarking practices: Entity-Pair Ranking evaluates all combinations in E × R × E, but the authors found it infeasible when full rankings are required across all models and datasets.The approach aims to evaluate questions with and without answers, rather than only ranking existing test facts.
  • Analyses: Earlier work questioned whether apparent progress reflects better LP models or better hyperparameter tuning, while other studies unified matrix-factorization models through multi-embedding interactions.The latter analyses combine vectors with trilinear products and introduce a quaternion-based multi-embedding model.
  • Analyses: Prior analyses typically address specific issues or vertical hypotheses, whereas this work conducts an extensive comparison across substantially different model families.Its scope includes design choices, benchmarking practices, and the importance of graph structure.
  • Surveys: Existing surveys organize models by features, scoring functions, architectural properties, complexities, applications, or graph type, but mainly report results from original papers.Relevant surveys cover KG embeddings, broader graph embeddings, and models using observable or latent features.
  • Benchmarking practices: Results from original papers are difficult to interpret and compare because they often use different settings and aggregate global metrics over whole test sets.This motivates the paper’s experimentally designed evaluation rather than a survey-only synthesis.

8 CONCLUSIONS

The paper presents an extensive comparative analysis of KG-embedding LP models, combining broad empirical evaluation with structural and evaluation-focused analysis. It finds that structural properties and low-level evaluation policies substantially affect reported performance.

  • Contributions: The study analyzes 16 representative LP models across diverse techniques and architectures, evaluating their efficiency and effectiveness on five popular datasets.This establishes the paper’s broad comparative scope.
  • Structural analysis: Structural properties of training data produce paramount effects on prediction performance, revealing circumstances associated with satisfactory model behavior and areas needing further research.The analysis uses these effects to identify open research directions.
  • Evaluation: Different low-level evaluation policies can produce incomparable and sometimes misleading performance results.The paper analyzes which model components are most sensitive to these policies and reports observations intended to support future research.

A HYPERPARAMETERS

The appendix reports the hyperparameter settings used to train the evaluated models and defines the notation for their search and training configurations.

  • Hyperparameter table: The appendix reports manually found settings and the size of their corresponding combination spaces.These settings are highlighted separately from the other reported configurations.
  • Hyperparameter table: Table 6 lists the hyperparameters used to train all models, including batch size, epochs or steps, embedding dimensions, learning rate, margin, regularization, smoothing, optimizer, filters, kernels, and dropout.It also distinguishes alternative notation for batch count, training steps, and entity and relation dimensions.

A RPS WITH PATHS OF MAXIMUM LENGTHS 1 AND 2

Figures 18–20 report H@1 results for LP models while varying the RPS of test facts, with RPS computed using paths up to length 1 or 2 across FB15k-237, WordNet, and Yago datasets.

  • On FB15k-237, H@1 is evaluated across test facts grouped by RPS computed with paths up to length 1 and up to length 2.
  • On WordNet datasets, H@1 is evaluated across test facts grouped by RPS computed with paths up to length 1 and up to length 2.
  • On Yago datasets, H@1 is evaluated across test facts grouped by RPS computed with paths up to length 1 and up to length 2.
Loading 2002.00819v4…