Link Prediction

These models interpret a relationship as a translation operation in a low-dimensional vector space. The core principle is that for a true triple (head, relation, tail), the embedding of the head entity plus the embedding of the relation should be close to the embedding of the tail entity.

• TransE: The foundational model where h + r ≈ t. It excels at modeling 1-to-1 relations but struggles with complex patterns like many-to-many.
• TransH & TransR: Address TransE's limitations by projecting entities onto relation-specific hyperplanes or spaces before translation.
• Key Advantage: Computational simplicity and efficiency, making them highly scalable for large graphs.

Also known as bilinear models, these approaches score a triple by measuring the semantic similarity between the head and tail entities after a relation-specific transformation. They perform a multiplicative matching in the embedding space.

• RESCAL: Represents relations as full matrices, capturing all pairwise interactions but requiring many parameters.
• DistMult: A simplified, efficient variant where relations are diagonal matrices, effective for symmetric relations.
• ComplEx: Extends DistMult into complex-valued space, enabling the modeling of asymmetric and inverse relations, which is critical for real-world knowledge.
• Key Use Case: Effective for capturing latent semantic similarities and compositional relation patterns.

This family models relations as geometric transformations—specifically rotations, reflections, or other operations in complex vector spaces. This provides a natural framework for capturing logical relation patterns.

• RotatE: Models each relation as a rotation from the head entity to the tail entity in complex space. It can inherently model symmetry, asymmetry, inversion, and composition.
• HAKE: Maps entities to polar coordinates (modulus and phase), separating hierarchical (modulus) and semantic (phase) information.
• Key Strength: Strong theoretical grounding for modeling fundamental relational axioms, leading to superior performance on benchmark datasets like FB15k-237.

These models use deep neural architectures to learn complex, non-linear scoring functions for triples, moving beyond simple geometric or linear operations.

• ConvE: Applies 2D convolutions over reshaped embeddings of the head and relation to predict the tail. It captures rich local interaction patterns.
• ConvKB: Uses 1D convolutions over the concatenated triple embedding to capture global translational characteristics.
• Graph Neural Networks (GNNs): Models like R-GCNs aggregate neighbor information across the graph structure, directly incorporating multi-hop evidence into the entity representation.
• Key Advantage: Ability to learn highly expressive, data-driven patterns without strong geometric priors.

This methodology uses symbolic logic and rule mining to perform deterministic inference. It complements statistical models with explicit, interpretable rules.

• Rule Mining: Algorithms like AMIE+ automatically extract logical rules (e.g., bornIn(X, Y) ∧ cityIn(Y, Z) ⇒ nationality(X, Z)) from the observed graph.
• Neural Theorem Provers: Neuro-symbolic systems that use neural networks to guide the search for proofs of a query over a set of logical rules.
• Key Benefit: Provides fully explainable predictions. A predicted link is supported by a chain of logical deductions, which is essential for auditability in regulated industries.

This methodology frames the entire knowledge graph as a 3D binary tensor, where slices correspond to relations. Link prediction becomes the task of decomposing this sparse tensor into low-rank matrices.

• Canonical Polyadic (CP) Decomposition: Approximates the tensor as a sum of rank-one tensors, directly analogous to models like DistMult.
• Tucker Decomposition: A more flexible factorization using a core tensor, related to models like RESCAL.
• Key Perspective: Provides a unified linear algebra framework for understanding many embedding models. Optimization focuses on reconstructing the entire adjacency structure, not just individual triples.

A technique that maps entities and relations in a knowledge graph to low-dimensional vector spaces (embeddings). This transformation enables mathematical operations for link prediction, such as measuring the plausibility of a triple (head, relation, tail).

• Purpose: To create a continuous, geometric representation of discrete graph data.
• Core Idea: Similar entities and relations have similar vector representations.
• Example Models: TransE, ComplEx, RotatE, DistMult.

A foundational translational embedding model where relationships are interpreted as translations in the vector space. For a true triple (h, r, t), the model learns embeddings such that h + r ≈ t.

• Key Strength: Simple and effective for modeling one-to-one relations.
• Limitation: Struggles with complex patterns like one-to-many or many-to-one relations.
• Impact: Inspired many subsequent translational and rotational models.

A class of neural networks designed to operate directly on graph-structured data. For link prediction, GNNs aggregate features from a node's local neighborhood to learn rich, context-aware representations.

• Mechanism: Iteratively updates a node's embedding by combining its own features with those of its neighbors.
• Common Variants: Graph Convolutional Networks (GCNs), Graph Attention Networks (GATs).
• Use Case: Relational GCNs (R-GCNs) extend this for knowledge graphs by using relation-specific transformations.

The automated discovery of logical rules that capture patterns within a knowledge graph. These symbolic rules (e.g., bornIn(X, Y) ∧ locatedIn(Y, Z) ⇒ nationality(X, Z)) can be used for deductive reasoning to infer new links.

• Process: Algorithms like AMIE+ scan the graph for frequent, high-confidence patterns.
• Integration: Often combined with embeddings in neural-symbolic systems for more robust reasoning.
• Output: Human-interpretable rules that explain predicted links.

A critical training technique for embedding models where non-existent (corrupted) triples are generated as negative examples. This provides a contrast for the model to learn what constitutes a false fact.

• Method: For a true triple (h, r, t), create false triples by corrupting the head or tail (e.g., (h', r, t) or (h, r, t')).
• Objective: The model learns to score true triples higher than corrupted ones.
• Challenge: Generating high-quality, hard negatives that are plausible but incorrect improves model discriminative power.

The two primary evaluation metrics for link prediction models, measuring the quality of ranked predictions.

• Hits@K: The percentage of test queries where the correct entity appears in the top K ranked predictions. Common values are Hits@1, Hits@3, Hits@10. Higher is better.
• Mean Reciprocal Rank (MRR): The average of the reciprocal ranks of the first correct answer for each query. It heavily penalizes models where the correct answer is ranked low. Closer to 1.0 is better.
• Usage: Standard benchmarks like FB15k-237 and WN18RR report these metrics.