Knowledge Graph Completion

The fundamental objective of KGC is link prediction: determining the probability that a missing edge (triple) should exist. This is formalized as a ranking problem where a scoring function $f(h, r, t)$ assigns a plausibility score to a candidate triple $(h, r, t)$. The system ranks all possible tail entities for a given head and relation, with the goal of placing the true missing entity at rank 1. Evaluation metrics include Mean Reciprocal Rank (MRR) and Hits@K.

Modern KGC relies on knowledge graph embedding (KGE) models that map entities and relations into a continuous, low-dimensional vector space. Key model families include:

• Translational models (TransE, TransR): Model relations as translations from head to tail embeddings.
• Semantic matching models (DistMult, ComplEx): Use tensor factorization to capture interactions.
• Neural models (ConvE, R-GCN): Employ convolutional or graph neural networks to learn non-linear feature representations. These embeddings preserve the graph's structural and relational properties.

Relational Graph Convolutional Networks (R-GCNs) are a specialized class of GNNs designed for KGC. Unlike standard GCNs, R-GCNs apply relation-specific weight matrices during message passing, allowing the model to differentiate how information flows across different edge types. This enables the encoder to generate entity embeddings that are contextually aware of the multi-relational neighborhood, significantly outperforming shallow embedding methods on inductive link prediction tasks where entities are unseen during training.

Beyond embeddings, symbolic approaches infer missing links through logical rule mining. Systems like AMIE+ and NeuralLP extract Horn clauses from the graph (e.g., bornIn(X, Y) ∧ locatedIn(Y, Z) → nationality(X, Z)). These rules provide explainability, a critical advantage over black-box embeddings. Hybrid neuro-symbolic models combine the pattern-recognition power of neural networks with the precision and interpretability of logical rules, enabling robust reasoning over long relational paths.

KGC systems must operate under the Open-World Assumption (OWA), which states that a missing fact is not necessarily false—it is simply unknown. This contrasts with the Closed-World Assumption (CWA) used in traditional databases. Under OWA, negative examples for training are generated via negative sampling (e.g., corrupting the head or tail of a true triple). The sampling strategy—uniform, Bernoulli, or adversarial—directly impacts model calibration and the quality of learned embeddings.

Static KGC is being extended to handle dynamic knowledge. Temporal KGC incorporates timestamps or time intervals into the quadruple $(h, r, t, \tau)$, using models like TComplEx or RE-NET to predict facts at specific points in time. Multimodal KGC fuses structural graph data with external modalities such as text descriptions, images, or numerical attributes. This is critical for aligning entity embeddings with pre-trained language models, enabling zero-shot completion using semantic similarity from textual encoders.

The core machine learning task within knowledge graph completion that aims to predict whether a missing relationship (edge) exists between two entities (nodes). Given a head entity and a relation, the model scores all candidate tail entities to find the most plausible completion. This is often framed as a ranking problem, where the goal is to rank the true missing entity higher than all other candidates.

• Head Entity: The subject of the triple (e.g., 'Albert Einstein').
• Relation: The predicate (e.g., 'wonAward').
• Tail Entity: The object to be predicted (e.g., 'Nobel Prize in Physics').

A technique that learns low-dimensional, dense vector representations (embeddings) for all entities and relations in a graph while preserving its structural information. These embeddings map symbolic triples into a continuous vector space where geometric operations can model interactions. A scoring function, such as TransE (translating head + relation ≈ tail) or RotatE (rotating in complex space), measures the plausibility of a triple.

• TransE: Interprets relations as translations in the embedding space.
• DistMult: Uses a bilinear diagonal tensor for fast, scalable scoring.
• ComplEx: Extends DistMult into complex space to model asymmetric relations.

Modern approaches that use Graph Neural Networks (GNNs) to learn entity representations by recursively aggregating information from neighboring nodes. Unlike shallow embedding methods, GNNs can incorporate node features (attributes) and the local graph structure. Models like R-GCN (Relational Graph Convolutional Network) apply relation-specific transformations during message passing, enabling them to handle multi-relational data and generalize to unseen entities during inference.

• Message Passing: Nodes update their state by receiving transformed messages from their neighbors.
• Encoder-Decoder: A GNN encoder generates embeddings, and a decoder (e.g., DistMult) scores triples.

A critical training technique for knowledge graph completion models. Since knowledge graphs only contain positive facts (true triples), the model must be taught to distinguish true facts from false ones. Negative sampling generates corrupted triples by randomly replacing the head or tail entity of a true fact. The model is trained to assign high scores to positive triples and low scores to negative ones. Common strategies include uniform sampling and Bernoulli sampling, which adjusts the corruption probability based on relation cardinality to reduce false negatives.

The standard protocol for evaluating link prediction models uses a filtered ranking setup. For each test triple, the model ranks the true tail entity against all other candidate entities, ignoring other known true triples. Key metrics include:

• MRR (Mean Reciprocal Rank): The average of the inverse of the rank assigned to the true entity. Sensitive to top-ranked results.
• Hits@K (e.g., Hits@10): The fraction of test triples where the true entity is ranked in the top K positions.
• Mean Rank: The average rank of the true entity, though it is sensitive to outliers.

A more challenging variant of knowledge graph completion where the model must predict links for entirely new entities not seen during training. This requires models that do not rely on memorizing a static embedding matrix. GNN-based encoders are essential here, as they can compute an embedding for a new node on-the-fly based on its initial features and connections. This capability is critical for dynamic, real-world knowledge bases where new entities are constantly being added.