Knowledge graph completion

Also known as: link prediction

On this page 7

Knowledge graph completion is the task of inferring missing facts in a knowledge graph by predicting which absent (head, relation, tail) triples are likely true, given the triples the graph already contains. In artificial intelligence, and in retrieval & knowledge systems in particular, it is often called link prediction, because the most common form asks which entity should fill the empty slot in a query such as (Marie Curie, educated at, ?).

Real knowledge graphs are incomplete by construction: they are assembled from text extraction, curated databases and user edits, and no source records every true relation. Completion models learn regularities in the graph structure, such as symmetry, inversion and composition of relations, and use them to rank candidate facts so that curators or downstream systems can add, review or query them.

How knowledge graph completion predicts missing triples

Knowledge graph completion works by assigning a plausibility score to every candidate triple and ranking the candidates for a given query. A model is trained on the known triples as positive examples and on corrupted triples, created by replacing the head or tail with a random entity, as negative examples. The training objective pushes true triples above corrupted ones by a margin or through a cross-entropy loss.

Most methods represent entities and relations as learned vectors, a family covered in depth by knowledge graph embedding. At query time the model scores the query against every entity in the graph, sorts the results and returns the top-ranked completions. Because the candidate space equals the number of entities, which can reach millions, efficient scoring and filtering matter as much as accuracy.

The task has three common variants, and the choice changes both the model and the evaluation protocol.

VariantQuery formTypical use
Tail prediction(h, r, ?)Finding a missing attribute or object
Head prediction(?, r, t)Finding which entities point to a target
Relation prediction(h, ?, t)Labeling a known link between two entities
Triple classification(h, r, t) true or falseValidating facts before insertion
Main variants of the completion task

Link prediction models fall into a few families that differ in how they combine entity and relation representations. Translational models such as TransE treat a relation as a vector offset from head to tail. Bilinear models such as DistMult and ComplEx score triples with a multiplicative interaction, and rotational models such as RotatE treat each relation as a rotation in complex space.

Newer approaches add graph neural networks that aggregate neighborhood information, rule-learning systems that extract logical patterns, and language-model methods that read entity names and descriptions as text. Each family captures different relation patterns, which explains why no single model dominates every benchmark.

FamilyExample modelsStrengthWeakness
TranslationalTransE, TransHSimple, fast, captures compositionFails on symmetric and one-to-many relations
BilinearDistMult, ComplEx, TuckERStrong accuracy, handles symmetryDistMult cannot model asymmetry
RotationalRotatEModels symmetry, inversion and compositionLarger memory per relation
Graph neural networkR-GCN, CompGCNUses multi-hop neighborhood contextCostly on very large graphs
Rule-basedAMIE, AnyBURLInterpretable rules with confidenceLimited coverage for sparse relations
Text-basedKG-BERT, generative LLM promptingWorks for unseen entitiesSlow scoring over large candidate sets
Representative model families and their strengths

Evaluating completion quality

Completion models are evaluated with ranking metrics on held-out test triples. For each test triple the model ranks the correct entity against all others, and the results are summarized as mean reciprocal rank (MRR) and Hits@k, the share of queries where the correct answer appears in the top k positions.

A crucial detail is the filtered setting: other true triples that also answer the query are removed from the ranking, so a model is not penalized for ranking a different correct answer first. Reported numbers that ignore filtering are not comparable with filtered results. Benchmark scores are also sensitive to test leakage; the original FB15k and WN18 datasets contained inverse relations that let trivial rules score highly, which led to the cleaned FB15k-237 and WN18RR benchmarks.

MetricWhat it measuresRange
MRRAverage of 1 divided by the rank of the true answer0 to 1, higher is better
Hits@1Share of queries with the true answer ranked first0 to 1
Hits@10Share of queries with the true answer in the top ten0 to 1
Mean rankAverage position of the true answer1 upward, lower is better
Common evaluation metrics

Knowledge graph completion adds facts to the graph itself, whereas neighboring retrieval tasks use an existing graph or corpus to answer questions. The distinction matters when deciding where predicted facts should go: completion outputs are candidate knowledge that usually needs a confidence threshold or human review before it becomes trusted data.

TaskInputOutput
Knowledge graph completionIncomplete graphNew scored triples
Knowledge graph question answeringNatural-language question and graphAnswer entities or values
GraphRAGQuestion, graph and documentsGrounded generated answer
Relation extractionUnstructured textTriples stated in the text
Entity resolutionDuplicate or variant recordsMerged entity identities
How completion differs from neighboring tasks

In practice these tasks reinforce each other. Relation extraction feeds new raw triples, completion fills gaps that text never states, and question answering or GraphRAG benefits from a denser, more connected graph that supports multi-hop reasoning.

Practical deployment and common pitfalls

Deploying knowledge graph completion requires a calibrated acceptance policy, because ranking scores are not probabilities. Teams typically calibrate scores on a validation set, accept only predictions above a precision target, and route borderline candidates to human curators. Predictions should be stored with provenance and model version so they can be audited or rolled back.

  • Closed-world bias: treating every absent triple as false produces noisy negatives, since many corrupted triples are actually true.
  • Popularity bias: models favor highly connected entities and underperform on the long tail of rare entities.
  • Transductive limits: classic embedding models cannot score entities added after training without retraining or an inductive method.
  • Temporal drift: facts such as employers or office holders change, so time-aware models or validity intervals are needed.
  • Error propagation: accepted false triples become training data for the next cycle and can amplify mistakes.

Choosing a method depends on graph size, update frequency and the need for explanations, as the following guide summarizes.

SituationRecommended approachReason
Large, stable graphBilinear or rotational embeddingsFast scoring and strong accuracy
Frequent new entitiesInductive GNN or text-based modelHandles entities unseen in training
Regulated domainRule learning plus reviewRules give auditable explanations
Rich entity descriptionsLanguage-model scoring with rerankingExploits textual knowledge
Choosing an approach

In simple terms

A knowledge graph is a large map of facts, such as which person was born in which city. Such maps always have holes, because nobody writes down everything. Knowledge graph completion fills those holes by noticing patterns in the facts that are present.

Think of a family tree where a grandparent is missing. If you know the parents and their parents for most people, you can make a confident guess. The software does the same at scale and then offers its best guesses with a confidence score, so people can decide which ones to keep.

A practical example

A pharmaceutical research team maintains a biomedical knowledge graph with about two million entities covering genes, proteins, diseases and approved drugs. Many drug-disease links are missing because the literature reports them only indirectly. The team trains a RotatE model on the existing triples and asks tail-prediction queries of the form (drug, may treat, ?).

The model reaches a filtered MRR of about 0.35 on held-out links, a typical level for biomedical graphs. Instead of inserting predictions automatically, the team takes the top twenty candidates per drug, discards those below a calibrated threshold, and sends the rest to pharmacologists. Several repurposing hypotheses reach laboratory testing, and every accepted triple keeps a flag showing that it was predicted, not observed.