🤖 machine learning

Link Prediction or Perdition: the Seeds of Instability in Knowledge Graph Embeddings

This paper reveals that high-performing Knowledge Graph Embedding models suffer from significant instability across random seeds and hyperparameter configurations, challenging the reliability of current rank-based evaluation metrics and the robustness of link prediction results.

Original authors: Guillaume Méroué, Fabien Gandon, Pierre Monnin

Published 2026-06-03

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Guillaume Méroué, Fabien Gandon, Pierre Monnin

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Picture: The "Magic Crystal Ball" Problem

Imagine you have a massive, incomplete encyclopedia of facts (a Knowledge Graph). It knows that "Paris is the capital of France," but it doesn't know who the current president of a specific country is.

To fill in the blanks, scientists use Knowledge Graph Embedding Models (KGEMs). Think of these models as magic crystal balls. You ask the crystal ball, "Who is the president?" and it looks at all the facts it knows, does some complex math, and predicts the answer.

The paper argues that while these crystal balls are great at getting the right answer on average, they are incredibly unreliable when you look at the specific details. If you ask the same question to the same crystal ball twice, but you flip a coin to decide how to start the process (a "random seed"), you might get two completely different lists of top candidates, even though the crystal ball claims it is equally confident both times.

The Core Problem: The "Same Score, Different Story"

In the world of machine learning, we usually judge these models by a single score, like MRR (Mean Reciprocal Rank). Think of this score as a report card grade.

The Paper's Finding: If you train a model five times with different random seeds, they all get an "A" (a high MRR score).
The Catch: Even though they all got an "A," the specific answers they give are totally different.

The Analogy: The Restaurant Review
Imagine three food critics (the models) reviewing a restaurant.

Critics 1, 2, and 3 all give the restaurant a 5-star rating (High MRR).
However, when you ask them to list their top 3 favorite dishes:
- Critic 1 says: Steak, Salad, Soup.
- Critic 2 says: Pizza, Tacos, Sushi.
- Critic 3 says: Burger, Fries, Ice Cream.

If you were a customer trying to decide what to order based only on the 5-star rating, you'd think they all agree. But in reality, they are recommending completely different meals. If you are a doctor trying to find a treatment for a disease (a real-world use case mentioned in the paper), getting a list of "Burgers" instead of "Medicine" because of a random coin flip is dangerous.

The Investigation: What Causes the Chaos?

The authors acted like detectives to figure out why these models change their minds. They isolated the "random ingredients" in the training process:

Initialization: How the model starts its brain (like rolling dice to set the initial weights).
Triple Ordering: The order in which the model reads the facts (like reading a book from page 1 to 100 vs. page 100 to 1).
Negative Sampling: How the model learns what is wrong (like a teacher giving you wrong answers to correct).
Dropout: Randomly turning off parts of the model's brain during training (like a student taking a test with their eyes closed for a few seconds).
Hardware: The actual computer chip (GPU) used to run the model.

The Shocking Discovery:
The paper found that changing just one of these ingredients is enough to cause massive instability.

The Analogy: Imagine baking a cake. If you change the brand of flour, the oven temperature, or the order you mix the eggs, you might end up with a cake that tastes exactly the same (same MRR score) but has a completely different texture or shape (different predictions).
The Hardware Twist: They even found that using a different brand of computer chip (GPU) caused the same level of chaos as changing the random seeds. This means if you train a model on a computer in New York and run it on a computer in Tokyo, you might get different results, even if you use the exact same code.

The "Voting" Fix: Does It Work?

The authors tested a common solution called Voting. This is like asking five different critics to vote on the best dish and taking the majority.

The Result: Voting helped a little bit. It made the models slightly more consistent.
The Limit: It didn't fix the problem completely. The models still disagreed on many details. Plus, it costs more time and money to train five models instead of one.

The Bottom Line: Performance $\neq$ Stability

The most important takeaway is this: A high score does not guarantee reliability.

Old Way: "This model has the highest score, so it's the best."
New Reality: "This model has the highest score, but it's a gamble. It might give you the right answer today and a completely different (but equally 'high-scoring') answer tomorrow."

The paper concludes that we need to stop just looking at the "report card grade" (MRR) and start checking if the model is stable. If we are using these models to make real-world decisions (like finding drug treatments or completing knowledge bases), we need to know that the model isn't just guessing randomly every time we run it.

Summary in One Sentence

Just because a Knowledge Graph model gets a high score on a test doesn't mean it's trustworthy; tiny random changes in how it's trained can cause it to give completely different answers, making it risky to rely on for important decisions.

Technical Summary: Link Prediction or Perdition: the Seeds of Instability in Knowledge Graph Embeddings

1. Problem Statement

Knowledge Graph Embedding Models (KGEMs) are the dominant approach for Knowledge Graph Completion (KGC) via link prediction. Standard evaluation protocols rely heavily on aggregate rank-based metrics such as Mean Reciprocal Rank (MRR) and Hits@K. However, these metrics often overlook the influence of random seeds on result stability.

The core problem identified is that high aggregate performance does not guarantee stability at the triple level or within the embedding space. Two models trained with different random seeds may achieve identical MRR scores yet produce significantly different top-K predictions. In operational settings (e.g., drug discovery or automated graph completion), this seed-dependent variability leads to divergent completed graphs, undermining the reliability of KGEMs for downstream decision-making. Furthermore, existing literature has rarely examined the stability of the learned embedding space itself with respect to randomness, despite its reuse in tasks like entity similarity and clustering.

2. Methodology

The authors conducted a systematic stability analysis across multiple KGEMs and datasets using a controlled experimental protocol.

Experimental Setup:

Models: Representative models from three families were selected: Geometric (TransE, RotatE), Tensor Factorization (DistMult, ComplEx), and Neural Networks (ConvE, RGCN, Transformer).
Datasets: Standard benchmarks including WN18RR, FB15k-237, and CoDEx-S.
Randomness Sources: The study isolated four independent stochastic factors common in ML training:
1. Parameter Initialization ( $I$ )
2. Triple Ordering ( $O$ )
3. Negative Sampling ( $N$ )
4. Dropout ( $D$ )
- Additionally, Hardware (GPU type) was identified as a source of randomness.
Hyperparameter Search: A grid search was performed to identify configurations with varying performance levels (Best, Median, Worst) to test the correlation between performance and stability.

Proposed Metrics:
To move beyond aggregate ranks, the authors introduced metrics focusing on the similarity of predictions and embedding spaces:

Pred-Overlap@K: Measures the intersection of the top-K predicted entities for a given query across different model instances.
Space-Overlap@K: Measures the intersection of the $K$ nearest neighbors in the embedding space for each entity, assessing the stability of the learned latent structure.
Consistency@K & Homogeneity@K: Aggregate metrics quantifying the proportion of entities appearing in the top-K lists of all runs simultaneously and the dispersion of candidates, respectively.

3. Key Contributions

Systematic Stability Analysis: The paper provides the first comprehensive quantification of how random seeds affect both the predictive behavior (top-K candidates) and the internal organization (embedding space) of KGEMs.
Decoupling Performance and Stability: The study demonstrates that high MRR scores do not guarantee stable predictions or embedding spaces.
Identification of Hardware Instability: The authors identify hardware (specifically GPU architecture) as a significant source of instability comparable to random seed variation, challenging reproducibility in cloud environments.
Limitations of Remediation: The paper evaluates "voting" (ensemble methods) as a mitigation strategy, finding it offers only limited enhancement and fails to stabilize the embedding space.

4. Key Results

Aggregate Metrics Mask Instability: While MRR and Hits@K show low variance across seeds, the actual predictions are highly divergent. For example, on FB15k-237, two RotatE instances with different seeds shared only ~4.3 of the top-10 predicted entities on average.
Triple-Level Divergence: Even when the ground-truth entity is ranked similarly, the non-ground-truth candidates differ drastically. In some cases, runs with identical MRR produced entirely different sets of top-10 entities (Pred-Overlap@10 as low as 0.17).
Embedding Space Instability: The organization of the embedding space is also unstable. Neighbors in the latent space vary significantly between runs, suggesting models learn different latent structures despite similar global performance.
Sources of Randomness: Varying any single source of randomness (initialization, ordering, sampling, dropout) independently induces instability of comparable magnitude. No single source dominates; the instability is inherent to the training process.
Hardware Impact: Training identical configurations on different GPUs (e.g., RTX 2080 Ti vs. A100) resulted in instability levels comparable to varying random seeds.
Performance vs. Stability Correlation: Poorly performing models are generally less stable. However, among high-performing and median-performing models, there is no clear correlation; a higher MRR does not guarantee greater stability.
Model Variance: TransE exhibited notably higher stability compared to other architectures (e.g., RotatE, ConvE), suggesting architectural differences play a role.
Voting Limitations: While ensemble voting improved prediction overlap, it did not eliminate instability and was not applicable to stabilizing the embedding space.

5. Significance and Claims

The paper claims that current benchmarking protocols are insufficient for assessing the reliability of KGEMs in operational settings. The findings highlight critical limitations:

Reliability Concerns: Seed-dependent instability means that adding top-K predictions to a knowledge graph can yield substantially different completed graphs, potentially leading to inconsistent or unreliable downstream decisions.
Embedding Space Validity: The instability of embedding spaces questions the validity of downstream tasks relying on these spaces, such as entity similarity assessment, conceptual clustering, and logical rule mining, which assume a stable latent structure.
Reproducibility Crisis: The sensitivity to hardware and minor stochastic choices poses a significant challenge for reproducibility, particularly in cloud computing scenarios.
Evaluation Reform: The authors argue for a shift in evaluation practices, treating stability as a distinct dimension from performance. They suggest that model selection should not rely solely on MRR but must consider robustness across random seeds and hardware configurations.

The paper concludes that while KGEMs are effective for ranking, their current lack of stability makes them risky for applications requiring consistent, deterministic graph completion or reliance on the geometric properties of the embedding space. Future work should focus on designing stability-aware architectures or training procedures.