Source-linked AI summary
Oracle, will I ever learn? A study of prediction convergence and complementarity across link prediction models
Guillaume Méroué, Fabien Gandon, Pierre Monnin
TL;DR
Link prediction models and training runs can produce different predictions, raising the question of how much complementary knowledge model combinations can recover. The paper measures this with a per-query oracle that supplies an ensemble upper bound. Across architectures and benchmarks, individual-to-oracle gaps reveal complementarity, but performance rapidly saturates and some queries remain unresolved.
Problem
Different link prediction models and random-seed instances produce substantially different predictions, but prior work had not quantified their recoverable complementary knowledge or its scaling with ensemble size.
Method
The paper defines an oracle that selects, for each test query, the best prediction among model instances to estimate an upper bound on ensemble performance.
Results
Across architectures and benchmarks, substantial individual-to-oracle gaps reveal complementary knowledge, while cross-model gains rapidly saturate as more models are added.
Takeaways & Limitations
Model combination can recover knowledge missed by individual instances, but current models collectively leave a persistent subset of queries unsolved.
Takeaways & Limitations
With 240 instances, the oracle still fails on a non-negligible subset of queries, and extrapolation beyond evaluated group sizes only indicates how observed scaling may evolve.
Abstract
from arXiv · showhide
Knowledge graphs have become an important source of structured knowledge for Web applications, including search, question answering, and recommender systems. In these applications, link prediction can serve either as a prediction task itself or as a means to enrich incomplete knowledge graphs for downstream tasks. Interestingly, different link prediction models, or even different training runs of the same model, can produce substantially different predictions for the same query. This suggests a variability in the capture of the underlying knowledge by models, thus raising a fundamental question: to what extent do different models capture complementary knowledge, and how much of this knowledge could be recovered by combining them? We propose to measure model complementarity through the performance of an oracle that, for each query, selects the best prediction among a considered set of models, hence providing an upper bound on the performance achievable through model combination. Across several architectures and benchmarks, we find a substantial gap between individual models and their oracle, revealing that different models capture complementary knowledge. Yet, this complementarity rapidly saturates as more models are added, leaving a persistent subset of queries unsolved even by a large number of models. These findings reveal both the potential of model complementarity and a fundamental limit to what current link prediction models can collectively recover; thereby highlighting the need for further research to build robust Web applications.
1 Introduction
Link prediction addresses incomplete knowledge graphs, but different models and random-seed instances produce divergent query-level predictions. The paper introduces an oracle framework to quantify complementary knowledge, performance gains, and remaining limits.
- Knowledge graphs support Web applications including semantic search, question answering, and recommender systems.
- Link prediction infers missing entities in incomplete triples such as (h, r, ?) or (?, r, t).
- Different random-seed instances can substantially disagree in their top-K predictions, with some ranking the ground-truth entity while others fail.
- Prior ensemble work suggests complementary predictions improve link prediction, but the attainable upper bound and its evolution with group size remain unquantified.
- The oracle selects the best prediction for each test triple among a set of instances, providing an upper bound for instance selection and ensemble gains.
- Oracle analysis identifies instance–oracle, model–cross-model, and asymptotic performance gaps.
2 Related Work
Related work spans embedding, neural, symbolic, and ensemble approaches to link prediction. Existing ensembles improve over single instances, but their upper bound and proximity to that limit remain open questions.
- Link prediction completes knowledge graphs and supports downstream applications such as search, question answering, and recommendation.
- Knowledge graph models commonly use scoring functions over triples, with embedding methods learning representations from observed and corrupted triples.
- Neural alternatives formulate link prediction as graph path search, sequential decision-making, or differentiable logical inference.
- Symbolic methods mine explicit graph patterns using top-down confidence-guided search or bottom-up random walks.
- Same-model ensembles show that random-seed variability can outperform a single model and capture patterns theoretically inaccessible to individual instances.
- Prior model combinations improve predictive performance, but reported MRR gains remain relatively modest.
- The literature leaves open whether an aggregation upper bound is achievable and whether existing methods operate near it.
3 Measuring Performance Upper Bounds with Oracles
The paper formalizes link prediction, trained instances, model groups, cross-model groups, and an oracle that selects the best per-query rank. Oracle MRR measures the theoretical performance limit of a group.
- Link prediction ranks candidate entities for incomplete triples and evaluates results with Mean Rank, Mean Reciprocal Rank, and Hits@K.
- An instance is a model trained on a dataset with a hyperparameter configuration and random seed.
- Different seeds can produce divergent query-level predictions despite similar aggregate metrics, motivating ensembles for complementary knowledge.
- A model group contains independently trained instances of one model, while a cross-model group combines instances from different models.
- The oracle maps each query to the best ground-truth rank achieved by any instance in its group.
- Per-query selection lets the oracle form a pseudo-instance whose performance can be evaluated with standard metrics.
- Oracle MRR represents the upper-bound performance achievable if the best-performing instance could be selected a priori for every query.
- Illustratively, oracle MRR rises from individual values of 0.40 and 0.44 to 0.70 for two Model 1 instances and 0.83 for the full set.
4 Experimental Settings
The experiments evaluate diverse link-prediction models, datasets, and independently trained instances using standardized implementations, configurations, metrics, and oracle-based protocols. Three experiments measure gains from combining instances, combining models, and increasing group size.
- Models: The model suite spans knowledge graph embeddings, neural reasoning approaches, and symbolic rule-based methods.The embedding models include TransE, ComplEx, DistMult, ConvE, RotatE, RESCAL, and BoxE; neural methods include NeuralLP, NBFNet, and MINERVA; symbolic methods include AMIE and AnyBURL.
- Datasets: Experiments use WN18RR, FB15k-237, and CoDEx-S with standard dataset splits and filtering of test triples involving unseen entities.WN18RR is derived from WordNet, while FB15k-237 and CoDEx-S are derived from Freebase and Wikidata, respectively.
- Instances: For each model–dataset pair, 20 independent instances are trained with random seeds 0–19, excluding instances whose validation MRR is below 0.05.The exclusions affect NeuralLP on all three datasets: 1 instance on WN18RR and 9 instances each on FB15k-237 and CoDEx-S.
- Evaluation Metrics: The evaluation reports filtered MRR, Hit@1, and Hit@10 using the pessimistic tie convention.Filtering removes other known true triples from the candidate set, while tied candidates receive the worst rank in their tie group.
- Experimental Protocols: A greedy procedure additionally selects 20 instances by repeatedly choosing the instance that most increases oracle performance, then preserves the resulting model proportions during resampling.This separates the effect of model allocation from the effect of the particular instances selected.
5 Uncovering Performance Gaps
The oracle framework exposes three performance gaps: seed-induced diversity improves over individual instances, cross-model groups approach the best single-model oracle, and performance saturates with unresolved queries remaining.
- Instance–Oracle Gap: Across datasets, instance oracles substantially outperform average single-instance performance, with gains often exceeding 10 points and reaching nearly 20 points.On CoDEx-S, ConvE rises from 0.45 to 0.64, DistMult from 0.42 to 0.56, and ComplEx from 0.46 to 0.60.
- Instance–Oracle Gap: Oracle gains depend on prediction diversity, since ComplEx has higher average MRR than ConvE on CoDEx-S but lower oracle performance.ComplEx averages 0.46 versus ConvE's 0.45, while their oracle scores are 0.60 and 0.64, respectively.
- Model–Cross-Model Gap: Cross-model groups generally approach the best single-model oracle without requiring dataset-specific model selection, although they do not systematically outperform it.The best single-model oracle varies by dataset, while sampled cross-model oracle scores show remarkably low variance.
- Model–Cross-Model Gap: Greedy cross-model groups consistently exceed the best single-model oracle, reaching 0.69 versus 0.68 on WN18RR, 0.60 versus 0.58 on FB15k-237, and 0.67 versus 0.64 on CoDEx-S.The greedy procedure selects instances to maximize oracle performance and often favors NBFNet while retaining lower-performing models for complementarity.
- Model–Cross-Model Gap: Approximately one third of queries across all datasets are unsolved by any model oracle, while other queries are solved by only a small number of model oracles.This distribution reveals both overlap and complementarity among model predictions.
- Model–Cross-Model Gap: Instance similarity forms tight same-model clusters, while NBFNet separates from other models and exhibits diversity comparable to that across different KGE models.This diversity may explain NBFNet's frequent selection by the greedy procedure alongside its strong individual performance.
- Asymptotic Gap: Marginal gains from additional instances decrease rapidly, and extrapolation indicates that even k = 10,000 would usually not bring oracle performance close to 1.The underlying limitation is already visible with 240 instances, where a non-negligible subset of queries remains unresolved.
- Asymptotic Gap: The collectively captured knowledge remains incomplete, potentially reflecting limited model expressivity or benchmark information that statistical models cannot recover.This is the paper's asymptotic performance boundary for the considered models and benchmarks.
6 Discussion
The oracle framework exposes attainable ensemble gains while showing that current diversity leaves some queries unresolved. The discussion points toward better selection, aggregation, and diversity design.
- Ensemble limits: Oracle performance provides an upper bound for ensembles, but combining predictions might surpass it through voting or score aggregation.The oracle selects the best existing instance prediction, whereas aggregation can potentially create correct rankings absent from every individual instance.
- Diversity design: Instance diversity is induced through random seeds or architectures with fixed hyperparameters, suggesting group-level tuning could promote greater diversity.Alternative hyperparameter selection could target collective rather than individual performance.
- Shared failures: All models failing on the same queries may reflect shared training distributions, where models learn common signal and diversity emerges mainly at the margins.The paper considers specialization across graph regions or coordination mechanisms as possible alternatives.
- Future direction: Approaching oracle performance requires predicting which instance will best answer each query, motivating performance and complementarity signals for selection or weighting.The proposed direction is query-dependent routing rather than relying only on aggregate model quality.
7 Conclusion
The paper introduces an oracle framework to upper-bound ensemble performance in link prediction. It finds gains from stochastic and architectural diversity, but collective performance remains below perfect accuracy, motivating improved aggregation and diversity.
- Contribution: The oracle framework provides an upper bound on ensemble learning performance for link prediction.It selects the best prediction among instances for each test triple.
- Instance diversity: Multiple same-model instances trained with different random seeds yield substantial gains, showing that isolated instances do not represent attainable model performance.Seed-induced diversity exposes partially complementary query solutions.
- Model diversity: Cross-architecture aggregation matches or outperforms the best single-model oracle, indicating that combining architectures supplies diversity unavailable from one approach.The conclusion frames this as the Model–Cross-model Gap.
- Asymptotic limit: Increasing ensemble size still converges below perfect accuracy, indicating incomplete knowledge capture by current approaches or learnable knowledge in benchmarks.The unresolved performance gap motivates future aggregation and diversity research.
A Characterizing Difficult Queries
The analysis characterizes query difficulty using graph connectivity and relation-structure features, revealing that the dominant predictors differ across datasets. Connectivity dominates on FB15k-237 and CoDEx-S, whereas relation structure dominates on WN18RR.
- Query difficulties: Queries are classified as Easy, Medium, or Hard by how consistently model instances recover the correct answer at rank 1.Easy queries are solved by every instance, Hard queries by none, and Medium queries fall between these cases.
- Query features: Query features measure graph connectivity and relation structure from the training graph.Connectivity includes target and source occurrence; relation features capture structural patterns.
- Discrimination metric: AUC measures how well each feature distinguishes Easy from Hard queries, with 0.5 indicating no discrimination.Values farther from 0.5 provide stronger separation between the two groups.
- Dataset patterns: On FB15k-237 and CoDEx-S, target occurrence is most discriminative, with AUC 0.95 and 0.97 respectively, while more valid answers correspond to harder queries.Target-occurrence medians fall from 966 to 5 and from 516 to 8 between Easy and Hard queries.
- Dataset patterns: WN18RR shows the opposite pattern: connectivity is weak with maximum AUC 0.62, while symmetry reaches AUC 0.99 and N-N cardinality reaches 0.96.Relation structure is therefore highly discriminative for this dataset.
- Overall finding: Overall, entity connectivity dominates difficulty on FB15k-237 and CoDEx-S, whereas relation structure dominates on WN18RR.The analysis indicates that difficulty depends strongly on the underlying knowledge-graph structure.
B UpSet plot
The UpSet analysis shows how model subsets overlap in solving queries and reveals both shared and distinctive contributions. On FB15k-237 Hit@1, many queries remain unsolved, while some are solved uniquely or jointly by particular models.
- The plots show the proportions of queries jointly solved by each model subset and by no other models, exposing overlap and complementarity.They analyze the 20 most represented model combinations using Hit@1 and Hit@10.
- 38% of FB15k-237 Hit@1 queries are not correctly answered by any model.
- 10% of FB15k-237 Hit@1 queries are successfully solved by all models.
- 7% of queries are uniquely solved by NBFNet, highlighting its distinctive contribution.
- Adding RESCAL, MINERVA, NeuralLP, or TransE to the other models increases solved queries by more than 1% despite lower overall performance.The result indicates that weaker models can capture complementary signals missed by stronger models.
GenAI Usage Disclosure
The supplied passages disclose the use of generative AI and coding assistance during paper preparation, while also identifying a table about averaged and oracle Hit@1 results and an UpSet figure.
- ChatGPT was used as a writing assistant to improve language.
- Windsurf Editor, powered by Claude Sonnet 4.6, was used as a coding assistant.
- The authors state that all scientific contributions, analyses, and experimental results are their own.
- Table 4 reports averaged and oracle Hit@1 across datasets and models.
- Figure 7 uses UpSet plots to show correctly answered-query distributions across model combinations for FB15k-237 and WN18RR.The figure covers Hit@1 and Hit@10 evaluation thresholds.