Negative Sampling

Negative sampling dramatically reduces the computational cost of training. Instead of scoring all possible negative triples (which scales with O(|E|² * |R|)), a small, fixed number of corrupted samples (e.g., 5-10) are generated per positive triple. This transforms an intractable problem into a manageable binary classification or pairwise ranking task, enabling the training of large-scale knowledge graphs on standard hardware.

The method for generating negative examples significantly impacts model performance. Common strategies include:

• Uniform Sampling: Corrupting the head or tail entity by randomly selecting from the entire entity set. Simple but can generate false negatives (triples that are actually true).
• Bernoulli Sampling: A relation-aware method that chooses whether to corrupt the head or tail based on the relation's mapping properties (one-to-one, many-to-many), reducing false negative rates.
• Adversarial Sampling: Dynamically generating harder negative samples that the current model struggles with, forcing it to learn more discriminative features.

Negative samples are integrated into the training objective via specific loss functions. The model learns to maximize the score for true triples and minimize the score for corrupted ones. Key loss functions include:

• Binary Cross-Entropy Loss: Treats the task as classification, where the model outputs a probability for a triple being true.
• Margin-Based Ranking Loss (e.g., Hinge Loss): Directly enforces a margin between the scores of positive and negative triples. A popular implementation is the TransE scoring function, where f(h, r, t) = -||h + r - t|| and the loss minimizes [γ + f(negative) - f(positive)]+, where γ is a margin hyperparameter.

Negative sampling is a defining feature of embedding-based inference models (e.g., TransE, DistMult, RotatE). It contrasts with:

• Tensor Factorization: Often uses full, dense factorization of the adjacency tensor, implicitly considering all negatives.
• Rule-Based Reasoning: Derives new facts through logical deduction without explicit negative evidence.
• Graph Neural Networks (GNNs): Models like R-GCNs learn from the graph structure via message passing; negative sampling is used during the link prediction training head but is not central to the GNN's feature aggregation mechanism.

The quality and difficulty of negative samples are crucial. High-quality negatives (plausible but false triples) teach the model fine-grained distinctions. If negatives are too easy or implausible, the model fails to learn meaningful semantics. Techniques like self-adversarial negative sampling, where the probability of selecting a negative triple is proportional to the current model's score, automatically generate harder negatives as training progresses, leading to more robust embeddings and better Hits@10 and MRR metrics.

Negative sampling operationalizes the Open World Assumption (OWA) prevalent in knowledge graphs. Since a KG only contains known true facts, any triple not present is unknown, not necessarily false. Negative sampling artificially generates assumed false examples for training. This creates a tension: the model must learn from these assumed negatives while remaining capable of predicting truly novel, correct facts not in the training set, which is the core objective of knowledge graph completion.

Knowledge Graph Embedding (KGE) is the foundational technique that enables negative sampling. It maps entities and relations to low-dimensional vector spaces, transforming discrete graph structures into continuous representations. This allows models to perform mathematical operations (e.g., calculating similarity scores) to predict missing links. Negative sampling is the primary method for training these embedding models by providing contrastive examples.

• Purpose: Enables link prediction via geometric relationships.
• Core Models: Include TransE, ComplEx, and RotatE.
• Dependency: Most KGE models are trained using a loss function that requires both positive and negative triples.

Link prediction is the primary machine learning task that negative sampling directly serves. It involves predicting a missing relationship between two entities (e.g., predicting (Paris, capitalOf, ?)). During training, the model learns to distinguish true triples (positives) from corrupted ones (negatives generated via sampling). The quality of negative sampling critically impacts the model's ability to generalize and make accurate predictions on unseen data.

• Objective: Infer missing (head, relation, tail) facts.
• Training Paradigm: A binary classification task framed by positive/negative example contrast.
• Evaluation: Measured by metrics like Hits@K and Mean Reciprocal Rank (MRR).

TransE is a foundational translational embedding model where relationships are interpreted as vector translations (i.e., head + relation ≈ tail). It is a canonical example of a model trained using negative sampling. Simple corruption methods, like randomly replacing the head or tail entity of a true triple, are used to generate negative examples. TransE's training objective maximizes the score for true triples while minimizing it for these corrupted samples.

• Mechanism: Models relations as translations in vector space.
• Training: Relies heavily on contrastive loss with generated negatives.
• Limitation: Struggles with complex relation patterns like one-to-many, which influenced advanced sampling strategies.

Tensor factorization is a family of knowledge graph completion models that treat the entire set of triples as a 3D binary tensor and decompose it to learn latent factors for entities and relations. Negative sampling is implicitly central to this approach, as the factorization model is trained to approximate a tensor where most entries are zeros (negative examples). Techniques like DistMult and ComplEx are bilinear factorization models that learn to assign high scores to observed triples and low scores to unobserved ones.

• Representation: Models the KG as a 3D (entity, relation, entity) tensor.
• Learning Goal: Reconstruct the tensor, distinguishing 1s (true facts) from 0s (negatives).
• Connection: The '0s' in the tensor represent the universe of potential negative samples.

Hits@K is a standard evaluation metric for link prediction models trained with negative sampling. It measures the proportion of test queries where the correct entity is ranked among the top K predictions. The ranking is generated by scoring the correct triple against a set of corrupted candidate triples—typically all entities in the vocabulary. This directly tests the model's ability, learned via negative sampling, to place true facts above plausible negatives.

• Function: Evaluates ranking quality of KGC models.
• Process: For a query (h, r, ?), rank all possible tail entities.
• Interpretation: A Hits@10 of 0.85 means 85% of correct answers were in the top 10 ranked candidates.

The Closed World Assumption (CWA) is a semantic principle where any fact not explicitly stated in the knowledge graph is assumed to be false. This stands in contrast to the Open World Assumption (OWA). Negative sampling operationalizes the CWA for training by treating all non-observed triples as potential negative examples. However, this introduces the false negative problem, as some unobserved triples may actually be true (under OWA), which advanced sampling strategies aim to mitigate.

• Training Implication: Provides a practical basis for generating negative examples.
• Risk: Can lead to model confusion if sampled negatives are actually true facts.
• Balance: Effective negative sampling must navigate the tension between CWA (for training) and OWA (for real-world truth).