Knowledge Graph Completion (KGC)

Knowledge Graph Embedding (KGE) models map entities and relations into a continuous vector space, enabling link prediction via geometric operations. These models learn latent representations where the existence of a triple (h, r, t) is scored by a function of their embeddings.

• Translational Models (e.g., TransE): Treat relations as translations: head + relation ≈ tail. Simple and effective for hierarchical relations.
• Bilinear/Complex Models (e.g., DistMult, ComplEx): Use multiplicative scoring functions. ComplEx, operating in complex space, can model symmetric, asymmetric, and inverse relations.
• Rotational Models (e.g., RotatE): Model relations as rotations in complex vector space, capable of expressing multiple relation patterns like composition.

These models are computationally efficient and form the backbone of modern KGC, powering tasks like triple classification and link prediction.

Graph Neural Networks (GNNs) operate directly on the graph structure by recursively aggregating and transforming features from a node's local neighborhood. For KGC, they capture multi-hop relational dependencies that pure embedding models may miss.

• Relational GCNs (R-GCN): Extend GCNs by applying relation-specific transformations during neighbor aggregation, explicitly modeling different edge types.
• Graph Attention Networks (GAT): Use attention mechanisms to weigh the importance of neighboring nodes dynamically, improving the model's focus on relevant connections.
• Message-Passing Frameworks: Systems where nodes exchange and update information across the graph's edges, iteratively refining entity representations.

GNN-based approaches are particularly powerful for inductive KGC, where the model must make predictions for entities not seen during training, by leveraging the graph's connective structure.

This methodology uses logical, human-interpretable rules to infer new facts. It operates under formal semantics, making it highly explainable and compatible with the Open World Assumption (OWA).

• Rule Mining: Algorithms like AMIE+ automatically discover logical Horn rules (e.g., bornIn(X, Y) ∧ capitalOf(Y, Z) → nationality(X, Z)) from the observed graph facts.
• Symbolic Inference: A deductive reasoning engine applies these mined or hand-crafted rules to the known graph to derive logically entailed conclusions.
• Neural Theorem Proving: A neuro-symbolic hybrid where neural networks guide the search for proofs over a symbolic knowledge base, making the reasoning process differentiable.

Rule-based methods provide deterministic, auditable inferences and are foundational for applications requiring high trust and explicit logical justification.

Tensor Factorization approaches treat the entire knowledge graph as a 3D binary tensor, where two dimensions represent entities and the third represents relations. A '1' at coordinate (h, r, t) indicates a true fact. KGC is framed as decomposing this sparse tensor into lower-dimensional latent factors.

• The core idea is to approximate the original tensor as a product of factor matrices representing entities and relations.
• Models like RESCAL perform full tensor factorization, capturing rich interactions but at high computational cost.
• Simpler models like DistMult are special, restricted cases of tensor factorization.

This framework provides a unified mathematical perspective for many embedding models and is closely linked to recommender system algorithms applied to graph data.

Neural-symbolic integration combines the statistical pattern recognition of neural networks with the structured, compositional reasoning of symbolic logic. This hybrid approach aims to overcome the limitations of purely statistical or purely symbolic methods.

• Differentiable Rule Learning: Systems that jointly learn neural parameters and logical rule weights in an end-to-end fashion.
• Logic-Guided Embeddings: Embedding models whose architecture or loss function is constrained by first-order logic rules, ensuring predictions are logically consistent.
• Neural Theorem Provers: Models that treat logical inference as a search problem, using neural networks to predict the most promising inference steps.

These methodologies are essential for complex multi-hop reasoning tasks and for building KGC systems that are both data-efficient and explainable.

Path-based models perform multi-hop reasoning by explicitly considering the paths of relationships that connect two entities in the graph. Prediction is based on the existence and semantics of these connecting paths.

• Path Encoding: Models like PTransE compose the vector representations of relations along a path to create a path embedding, which is then compared to a direct relation embedding.
• Reinforcement Learning (RL) Agents: RL agents learn to navigate the graph from a head entity to a target tail entity by selecting a sequence of relations, treating path finding as a Markov Decision Process.
• Recurrent Neural Networks (RNNs): Used to encode variable-length sequences of relations (paths) into a fixed-size vector for prediction.

This methodology directly models relational chains, making it highly interpretable and effective for answering complex queries that require traversing several facts.

Hits@K is a ranking-based metric that measures the proportion of test queries where the correct entity appears within the top K predicted candidates. It is the most commonly reported metric for link prediction tasks.

• Interpretation: A higher Hits@K score indicates better model performance. Common values for K are 1, 3, and 10.
• Example: Hits@10 = 0.85 means that for 85% of test queries, the true tail (or head) entity was ranked in the top 10 predictions.
• Limitation: It treats all ranks within the top K equally; ranking the correct entity 1st or 10th yields the same score.
• Use Case: Primary metric for evaluating the practical utility of a model where retrieving a shortlist of plausible candidates is sufficient.

Mean Reciprocal Rank (MRR) is the average of the reciprocal ranks of the first correct answer for a set of test queries. It provides a finer-grained measure of ranking quality than Hits@K.

• Calculation: MRR = (1/|Q|) * Σ (1 / rank_i), where rank_i is the position of the first correct entity for the i-th query.
• Interpretation: Values range from 0 to 1. A higher MRR indicates the correct answer is consistently ranked higher. An MRR of 0.5 suggests the correct entity is, on average, ranked 2nd.
• Advantage: More sensitive than Hits@K; rewards models that place the correct answer at the very top of the list.
• Use Case: Critical for applications where the single best prediction is required, such as in automated fact-checking or answer retrieval systems.

Mean Rank (MR) is the arithmetic mean of the ranks assigned to the correct entities for all test queries. It was an early standard metric but has significant limitations.

• Interpretation: A lower mean rank indicates better performance. A perfect score would be 1.0.
• Major Flaw: The metric is highly sensitive to the corruption strategy used during evaluation (e.g., filtering vs. raw). A single bad ranking on a large dataset can artificially inflate the mean.
• Example: If a model ranks the correct entity at positions 1, 5, and 100 for three queries, the MR is (1+5+100)/3 = 35.33.
• Current Use: Largely deprecated in favor of Hits@K and MRR, but still reported in historical comparisons.

This is not a single metric but a critical evaluation protocol that drastically affects reported scores like MR and Hits@K. It addresses the Open World Assumption.

• Raw Setting: The model ranks the correct entity against all other entities in the graph, including other true facts. This unfairly penalizes the model for ranking other valid facts higher.
• Filtered Setting: During ranking for a query (h, r, ?), all other known true triples that share the same head and relation (e.g., (h, r, t')) are removed from the candidate list before ranking. This is the standard, fair protocol.
• Impact: Filtered MR and Hits@K scores are always better (lower MR, higher Hits@K) than raw scores. Papers must specify which protocol was used.
• Best Practice: The filtered setting is the community standard for reporting results on benchmarks like FB15k-237 and WN18RR.

AUC-ROC (Area Under the Receiver Operating Characteristic Curve) measures a model's ability to discriminate between true and false triples in a triple classification task.

• Process: The model scores a set of positive (true) and negative (false) triples. The ROC curve plots the True Positive Rate against the False Positive Rate at various classification thresholds.
• Interpretation: AUC ranges from 0 to 1. A score of 0.5 represents random guessing, while 1.0 represents perfect discrimination.
• Use Case: Preferred for evaluation tasks framed as binary classification (true/false), rather than ranking. It is less common for standard link prediction but useful for assessing a model's calibration and discriminative power.
• Consideration: Requires careful construction of a high-quality negative test set, often through manual annotation or reliable heuristics.

Standard metrics are used, but the evaluation setup changes fundamentally for Inductive Knowledge Graph Completion and Few-Shot Relation Learning.

• Inductive KGC: The model is evaluated on triples containing entities not seen during training. Metrics (Hits@K, MRR) measure generalization to entirely new nodes, testing the model's ability to infer based on graph structure and relation patterns alone.
• Few-Shot Relation Learning: The model is evaluated on predicting triples for relations with only K examples (e.g., 1-shot, 5-shot). Performance is typically measured as the mean Hits@N or MRR across many few-shot tasks (episodes).
• Key Difference: These settings prevent simple memorization of entity embeddings, pushing models to learn transferable relational semantics. Reported results are typically lower than for standard transductive (seen-entity) settings.
• Benchmarks: Datasets like ILPC (Inductive) and FewRel are designed for this evaluation.

Knowledge Graph Embedding (KGE) is a foundational technique for KGC that maps entities and relations into a continuous, low-dimensional vector space. This transformation enables mathematical operations for link prediction, such as measuring the plausibility of a triple (head, relation, tail).

• Purpose: Converts discrete graph structures into numerical representations for machine learning models.
• Core Models: Includes TransE, DistMult, ComplEx, and RotatE, each with different geometric interpretations (e.g., translations, rotations).
• Application: The learned embeddings serve as features for downstream tasks like entity ranking and triple classification.

Link prediction is the primary subtask of KGC focused on predicting the existence of a missing relationship between two known entities in a graph. It is the direct operationalization of KGC models.

• Input: A pair of entities (e.g., (Albert_Einstein, ?)).
• Output: A ranked list of plausible relations or a probability score for a candidate relation (e.g., wonPrize).
• Evaluation: Measured using metrics like Hits@K and Mean Reciprocal Rank (MRR) to assess ranking accuracy.
• Example: Predicting the educatedAt link between a person entity and a university entity.

A Graph Neural Network (GNN) is a class of deep learning models designed to operate directly on graph-structured data. For KGC, GNNs aggregate information from an entity's local neighborhood to generate rich, context-aware node embeddings.

• Mechanism: Iteratively updates a node's representation by combining its features with those of its connected neighbors.
• Key Architectures: Graph Convolutional Networks (GCNs), Graph Attention Networks (GATs), and Relational GCNs (R-GCNs) which handle multiple relation types.
• Advantage: Captures multi-hop relational patterns and structural dependencies beyond pairwise connections.

Rule mining is a symbolic, logic-based approach to KGC that involves the automated discovery of logical rules from existing graph facts. These rules can then infer new, missing triples.

• Rule Form: Typically expressed as Horn clauses (e.g., bornIn(X, Y) ∧ locatedIn(Y, Z) → nationality(X, Z)).
• Process: Algorithms scan the graph for frequent relational patterns to generate candidate rules with associated confidence scores.
• Integration: Often used in neural-symbolic integration systems, where learned rules provide interpretable, explainable inferences to complement statistical embeddings.

Negative sampling is a critical training technique for embedding-based KGC models. It generates non-existent (corrupted) triples as negative examples to contrast with the positive facts in the knowledge graph.

• Purpose: Provides a learning signal by teaching the model to assign lower scores to false triples than to true ones.
• Methods: Common strategies include corrupting the head or tail entity of a true triple (e.g., (Paris, capitalOf, France) → (London, capitalOf, France)).
• Challenge: Generating high-quality, plausible negatives ("hard negatives") is essential for model performance and robustness.

Inductive knowledge graph completion is an advanced KGC setting where a model must make predictions for entities that were completely unseen during training. This tests a model's ability to generalize to new nodes.

• Contrast with Transductive Learning: Standard KGC is often transductive, assuming all entities are known at training time.
• Requirement: Models must rely on the relational structure and features of new entities, rather than pre-learned embeddings for them.
• Solution Approaches: Utilize GNNs that can generate embeddings for new nodes based on their local graph topology and attributes.