Knowledge Graph Embedding

KGEs map discrete graph structures (nodes and edges) into a continuous vector space of significantly lower dimensionality than the original sparse adjacency matrix.

• Dimensionality Reduction: Typical embedding sizes range from 50 to 1000 dimensions, regardless of the graph's scale.
• Computational Efficiency: This dense representation allows for fast algebraic operations, replacing slow graph traversal with cosine similarity calculations.
• Noise Reduction: The compression forces the model to learn latent factors, acting as a regularizer that generalizes over sparse or noisy data.

A robust KGE model must capture the logical rules inherent in the graph's edges. The embedding space is structured to solve for specific relationship types.

• Symmetry: If (A, marriedTo, B) exists, the model must also score (B, marriedTo, A) highly. Models like ComplEx handle this via complex-valued vectors.
• Inversion: The model learns that (A, parentOf, B) implies (B, childOf, A).
• Composition: The model infers transitive relations, such that (A, locatedIn, B) and (B, locatedIn, C) implies (A, locatedIn, C). RotatE excels here by modeling relations as rotations in complex space.

Pioneered by the TransE model, this principle treats a relation as a geometric translation vector between the head and tail entity embeddings.

• Core Equation: The model optimizes for head + relation ≈ tail.
• Interpretability: This creates a highly intuitive vector space where the semantic meaning of a relationship is a simple spatial displacement.
• Limitations: While efficient, pure translation models struggle with complex patterns like 1-to-N relations, leading to the development of variants like TransH and TransR that project entities into relation-specific hyperplanes.

Every KGE model defines a scoring function f(h, r, t) that quantifies the plausibility of a triple. The embedding objective is to assign higher scores to true facts than to corrupted ones.

• Distance-Based: Models like TransE use the L1 or L2 norm: f = -||h + r - t||.
• Semantic Matching: Models like RESCAL and DistMult use bilinear tensor products: f = h^T M_r t, capturing multiplicative interactions.
• Neural Network-Based: Models like ConvE use 2D convolutions over reshaped embeddings to learn deep, non-linear feature interactions.

Training KGEs requires not only positive examples but also negative samples (false triples) to teach the model discriminative boundaries.

• Random Corruption: A standard method replaces the head or tail entity of a true triple with a random entity from the vocabulary.
• Bernoulli Sampling: An advanced technique that replaces the head or tail with different probabilities based on the relation's mapping property (e.g., 1-to-N vs. N-to-1) to avoid generating false negatives.
• Adversarial Sampling: The model dynamically selects 'hard' negative samples that the current model state scores highly, forcing it to learn more precise decision boundaries.

The embedding space exhibits continuity, where semantically similar entities are positioned in close proximity. This property is crucial for downstream generalization.

• Clustering: Entities of the same type (e.g., all cities) naturally form dense clusters in the vector space, even without explicit type labels.
• Analogical Reasoning: The vector offsets capture analogies. The classic example is king - man + woman ≈ queen, demonstrating the model's ability to encode gender as a consistent vector offset.
• Link Prediction: This smoothness allows the model to predict missing links by finding the entity whose embedding is closest to the predicted point h + r.

A foundational family of embedding methods that model relations as geometric translations in vector space.

• TransE: Interprets a relation as a simple vector translation from head to tail entity (h + r ≈ t). Highly efficient but struggles with complex relations.
• TransR: Projects entities into a relation-specific space before applying translation, capturing diverse relational patterns.
• RotatE: Models relations as rotations in complex space, naturally encoding symmetry, inversion, and composition.

Approaches that measure plausibility of triples using similarity-based scoring functions rather than distance.

• RESCAL: A bilinear model capturing pairwise interactions between entity and relation latent factors via a full rank tensor.
• DistMult: A simplified bilinear model restricted to diagonal matrices, reducing parameters but limited to symmetric relations.
• ComplEx: Extends DistMult into complex-valued space, handling asymmetry through the imaginary component of embeddings.
• TuckER: Applies Tucker decomposition to the knowledge graph tensor, enabling multi-task learning across relations.

Methods that generate embeddings by aggregating information from neighboring nodes using message-passing frameworks.

• R-GCN: Extends Graph Convolutional Networks to knowledge graphs by using relation-specific weight matrices for message transformation.
• CompGCN: A compositional GCN that jointly embeds entities and relations, applying relation-specific operations (subtraction, multiplication, circular correlation) during aggregation.
• HGT (Heterogeneous Graph Transformer): Leverages type-specific attention mechanisms to weigh the importance of different node and edge types during neighborhood aggregation.

The optimization strategies that govern how embeddings are learned from positive and negative triples.

• Negative Sampling: Generates corrupted triples by randomly replacing head or tail entities. Critical for efficient training without computing scores for all possible triples.
• Margin-Based Ranking Loss: Enforces that the score of a positive triple exceeds that of a negative triple by at least a fixed margin γ.
• Binary Cross-Entropy Loss: Treats link prediction as a binary classification task, pushing positive scores toward 1 and negative scores toward 0.
• Self-Adversarial Sampling: Weights negative samples by their current model score, focusing training on hard negatives that provide stronger gradient signals.

Standardized protocols for measuring embedding quality on link prediction and triple classification tasks.

• Mean Reciprocal Rank (MRR): The average inverse rank of the first correct entity across all test queries. Sensitive to top-ranked performance.
• Hits@K (K=1,3,10): The proportion of test triples where the correct entity appears in the top K ranked predictions. Hits@1 measures exact precision.
• Filtered Setting: Removes all other valid triples from the ranking before evaluation, preventing false penalization when multiple correct answers exist.
• WN18RR & FB15k-237: De-duplicated benchmark datasets that remove inverse relation leakage, providing a more rigorous test of true reasoning capability.

Embedding approaches that move beyond Euclidean space to capture hierarchical structures inherent in many knowledge graphs.

• Poincaré Embeddings: Represent entities in a hyperbolic space where distance grows exponentially toward the boundary, naturally modeling tree-like taxonomies.
• MuRP (Multi-Relational Poincaré): Extends hyperbolic embeddings to multi-relational data using Möbius transformations for relation-specific operations.
• AttH (Attentive Hyperbolic): Learns per-relation curvature parameters, allowing some relations to operate in hyperbolic space while others remain Euclidean.
• These methods excel on hierarchical relations like hypernym and partOf where Euclidean models suffer from crowding.