Source-linked AI summary
How Many and How Much? Contrastive Learning with Negative Samples for Knowledge Graph Embedding
Sooho Moon, Yunyong Ko
TL;DR
Contrastive KGE must choose how many negatives to sample for each positive and how much each negative contributes, while open-world uncertainty makes unobserved facts potentially true. RADAR models this uncertainty to adapt budgets and calibrates weights using score dispersion and concentration. Across the evaluated models and KGs, it achieves the best average KGC performance and reduces sampled false negatives by over 90% versus fixed-budget methods.
Problem
Contrastive KGE must choose a negative-sample budget per positive and each negative’s learning weight, while open-world KGs make unobserved facts potentially true and false-negative risk varies.
Source: §1 · pp. 1–2Method
RADAR models an open-world KG as a stochastic partial observation of its closed-world counterpart to allocate budgets by risk, and calibrates negative weights using score dispersion and concentration.
Source: §1 · p. 2Results
Takeaways & Limitations
Experiments across four KGE models and three real-world KGs support RADAR’s effectiveness and report improved training efficiency.
Source: §6 · p. 8The risk analysis assumes uniform observability and shared entity and relation sets; heterogeneous observability and inductive settings with unseen entities or relations remain future directions.
Source: §4.1 · p. 3, §6 · p. 8
Abstract
from arXiv · showhide
Knowledge graph embedding (KGE), a fundamental technique for knowledge-centric Web and KG-augmented AI applications, is commonly trained through contrastive learning with negative samples to learn discriminative representations. Despite its empirical success, two crucial questions regarding negative samples remain underexplored: (Q1) how many negative samples should be used for each positive sample and (Q2) how much should each negative sample contribute to learning? To answer these questions, we propose RADAR, a novel contrastive learning framework for KGE models with two effective strategies, respectively: (1) Risk-aware negative budget allocation quantifies false-negative sampling risk by modeling an open-world KG as a stochastic partial observation of its closed-world counterpart and adaptively assigns a negative budget to each positive sample based on its risk; (2) Distribution-calibrated negative weighting assigns negative weights by calibrating the weighting strength for each positive based on two complementary characteristics of the negative-score distribution: dispersion and concentration. Extensive experiments on 3 real-world KGs with 4 KGE models reveal that RADAR achieves the best KGE performance on average across all model--KG combinations and reduces sampled false negatives by over 90% compared with conventional fixed-budget methods.
1 Introduction
The introduction frames negative-sample count and weight as unresolved choices in contrastive KGE, where open-world uncertainty makes sampling risk vary across positives. RADAR addresses both choices through risk-aware budget allocation and weighting calibrated to score dispersion and concentration.
1 Introduction
- KGE learns entity and relation representations from triples; contrastive training corrupts positives into negatives to distinguish true facts from false ones for downstream applications.The introduction names KG completion, recommendation, enzyme prediction, and KG-augmented AI among uses of learned representations.Source: §1 · p. 1
- Under the open-world assumption, unobserved facts may be true, so more negatives raise false-negative risk while too few may limit supervision.The number of false negatives varies significantly across positive triples, and estimating the risk requires unavailable closed-world knowledge.Source: §1 · pp. 1–2
- Self-Adv [29] bases weighting strength on negative-score dispersion, which can underweight concentrated high-scoring negatives when overall dispersion is low.The introduction contrasts P1’s larger dispersion with P2’s more concentrated top-10% scores and lower weights.Source: §1 · p. 2
- RADAR models an open-world KG as a stochastic partial observation of its closed-world counterpart and assigns fewer negatives to higher-risk positives.It estimates false-negative risk from observed degree and assigns more negatives to lower-risk positives.Source: §1 · p. 2
- RADAR combines dispersion with entropy-based score concentration to calibrate negative weights for each positive triple.The paper treats concentration as complementary to dispersion because the two are not strongly correlated.Source: §1 · p. 2
- Across 3 real-world KGs and 4 KGE models, RADAR achieves the best performance on average across model–dataset combinations and reduces sampled false negatives by over 90% versus fixed-budget methods.The evaluation reports both outcomes as contributions of RADAR.Source: §1 · p. 2
2 Related Work
Related work spans KGE model families and methods for selecting or weighting contrastive negatives. RADAR differs from prior adaptive allocation by explicitly accounting for open-world false-negative risk.
2 Related Work
- KGE models include translation-based approaches such as TransE and RotatE [29], and tensor-decomposition approaches such as DistMult [39], ComplEx, and TuckER [2].The review also describes HousE, DGS, and IVR.Source: §2 · p. 2
- Prior negative-sample methods vary in selection and utilization, including adversarial generation, hard-negative reuse, structure-based sampling, and score-based weighting.Examples include KBGAN [5], NSCaching [47], SANS [1], and Self-Adv [29].Source: §2 · p. 2
- ERDNS reallocates a fixed batch-level budget by degree, whereas RADAR accounts for open-world false-negative risk rather than adapting only within a batch.Other reviewed methods mitigate or synthesize negatives through score mixing, semantic matching, influence, or diffusion.Source: §2 · pp. 2–3
- RADAR’s overview separates negative quantity, addressed by risk-aware budget allocation, from negative contribution, addressed by distribution-calibrated weighting.These correspond to challenges C1 and C2, respectively.Source: Figure 3 · p. 3
3 Preliminary: Contrastive Learning for KGE
The preliminary section describes contrastive KGE as a pipeline from negative sampling through scoring and weighting to loss-based model updates. It focuses on choosing the negative count and contribution, then evaluates learned representations on knowledge graph completion.
3 Preliminary: Contrastive Learning for KGE
- The setup represents a KG as G = (E, R, T), with entity, relation, and observed-triple sets.The contrastive-learning pipeline is defined for a KG and KGE model.Source: §3 · p. 3
- For each positive triple, the pipeline generates negatives by replacing its head or tail, scores the positive and negatives, assigns negative weights, and computes a contrastive loss to update the model.A higher score indicates a triple is more likely to be true.Source: §3 · p. 3
- In practice, each positive typically receives a fixed 128 or 256 negatives, while weighting may be uniform or score-based as in Self-Adv [29].Negative selection depends on the sampling strategy.Source: §3 · p. 3
- The loss uses positive and negative scores and their weights; the paper focuses on choosing the number of negatives in Step (1) and their contribution in Step (3).The learned representations are evaluated for KGC by ranking candidate entities for missing-head or missing-tail queries.Source: §3 · p. 3
4 Proposed Framework: RADAR
RADAR combines risk-aware allocation of negatives with distribution-calibrated weighting. It estimates false-negative risk from observed anchor degree and sets weighting strength using both dispersion and concentration of negative scores.
4 Proposed Framework: RADAR
- RADAR integrates risk-aware negative-budget allocation and distribution-calibrated negative weighting to address how many negatives to sample and how much they contribute.Source: §4 · p. 3, §4.3 · p. 5
4.1 Bridging Open-World and Closed-World KGs
- Under a stochastic partial-observation model with uniform observability, RADAR estimates false-negative risk from observed anchor degree, which increases with that degree.The model treats each latent fact as independently observed and assumes the open- and closed-world KGs share entity and relation sets.Source: §4.1 · pp. 3–4
4.2 How Many? Risk-Aware Negative Budget Allocation
- The negative budget decreases as observed anchor degree increases, with γ controlling sensitivity; uncertainty- and relation-aware adjustments can refine the degree estimate.Setting γ = 0 recovers fixed-size sampling, while the uncertainty adjustment is recovered at τ = 0 and the relation-aware adjustment at ω = 0.Source: §4.2 · p. 4
4.3 How Much? Distribution-Calibrated Negative Weighting
- RADAR calibrates weighting strength using both score dispersion and concentration, which are not strongly correlated and can show distinct training patterns.Its budget-aware adjustment controls how allocated budget changes average per-negative weights; β = 1 compensates fully for budget size, and RADAR includes fixed-uniform and Self-Adv as special cases.Source: §4.3 · p. 5, Figure 4 · p. 5
5 Experimental Validation
Experiments evaluate RADAR across four KGE models and three KGs using MRR and H@10; results cover benchmark performance, false-negative sampling, efficiency, component ablations, and hyperparameter sensitivity.
5.1 Experimental Setup
- The evaluation uses TransE, RotatE, DistMult, and ComplEx on FB15k237, WN18RR, and YAGO3-10, comparing RADAR with 15 negative-sample methods using filtered MRR and H@10.Results are means over five random seeds; some baselines use results reported in original works, unavailable for YAGO3-10.Source: §5.1 · pp. 5–6
5.2 EQ1. KGE Performance
- RADAR achieves the best average rank on all three KGs; on WN18RR, it ranks first on all eight model–metric combinations, with average rank 1.0 versus 4.1 for the runner-up.RADAR also improves both MRR and H@10 over Uniform in every model–KG combination.Source: Table 1 · p. 6, §5.2 · p. 6
- RADAR samples fewer false negatives than all baselines on FB15k237 and WN18RR; it also outperforms baselines on multi-valued relations, while gains are less consistent for 1-to-1 relations.The 1-to-1 category accounts for 1.6% of triples; Figure 5 uses a maximum budget of 256 negatives.Source: §5.2 · pp. 6–7, Figure 5 · p. 6, Figure 6 · p. 7
5.3 EQ2. Training Efficiency
- On RotatE and DistMult across two KGs, RADAR reaches the highest performance in the shortest time; on RotatE/FB15k237, it cuts training time by 30.0% and memory cost by 34.2% versus Uniform and Self-Adv.The resource comparison uses 1,024 positives, a maximum negative budget of 256, and embedding dimension 1,000; RADAR achieves the highest MRR without costly auxiliary procedures.Source: Figure 7 · p. 7, §5.3 · p. 7, Table 2 · p. 7
5.4 EQ3. Ablation Study
- Removing risk-aware allocation (RA) decreases MRR by 1.6–8.4% (4.5% on average); removing either RA or distribution weighting (DW) degrades KGE performance across all model–dataset combinations.Source: §5.4 · p. 7
- With fixed budgets, distribution-calibrated weighting outperforms Self-Adv; with uniform weights, risk-aware allocation yields larger gains over Uniform across all model–dataset combinations.Figure 8 compares each ablated strategy with its corresponding existing counterpart.Source: §5.4 · p. 8, Figure 8 · p. 8
5.5 EQ4. Sensitivity Analysis
- Sensitivity tests favor positive budget adaptation, intermediate dispersion–concentration balance, and budget-aware weight normalization; overly aggressive budget reduction can discard useful negative supervision.Performance typically peaks around γ=0.6–1.0, but on YAGO3-10 it tends to peak around γ=0.6 before decreasing.Source: §5.5 · p. 8, Figure 9 · p. 8
6 Conclusion and Future Work
RADAR addresses negative-budget allocation and negative-importance estimation with risk-aware budgets and distribution-calibrated weights. Experiments show improved average KGC performance and training efficiency, while the analysis leaves broader observability and inductive settings open.
6 Conclusion and Future Work
- Across four KGE models and three real-world KGs, RADAR achieves the best average KGC performance, improves training efficiency, and benefits from complementary gains from both strategies.Risk-aware allocation adapts budgets to false-negative sampling risk; distribution-calibrated weighting uses dispersion and concentration of negative scores.Source: §6 · p. 8
- The risk analysis assumes uniform observability and shared entity and relation sets; heterogeneous observability and inductive settings with unseen entities or relations remain future work.The authors also leave joint optimization of the negative-sampling strategy itself as a direction for further improvement.Source: §6 · p. 8
A.1 Implementation Details
The appendix specifies the experimental hardware, training schedule, and evaluation protocol used for reproducibility.
A.1 Implementation Details
- Experiments run on an NVIDIA RTX 5000 PRO GPU with dual Intel Xeon Gold 6526Y CPUs, 32 physical cores, 64 threads, and 256 GB of main memory.Baselines use the same hardware environment and memory configuration.Source: §A.1 · p. 10
- Each model trains for 100K steps, is evaluated every 5K steps, and has its learning rate reduced by 10% after 50K steps.Hyperparameters are selected using the configuration with the highest validation MRR.Source: §A.1 · p. 10
- Evaluation uses filtered rank-based metrics and Sun et al.’s tie-breaking protocol [30] to resolve identical scores.The filtered setting excludes other ground-truth candidate triples from ranking.Source: §A.1 · p. 10
A.2 Description of Datasets
The experiments use three real-world KGs drawn from Freebase, WordNet, and YAGO.
A.2 Description of Datasets
- FB15k237 is a diverse-domain Freebase subset, WN18RR is a WordNet subset of semantic word relations, and YAGO3-10 is a Wikipedia-based YAGO subset.FB15k237 and WN18RR remove inverse relations from their respective source datasets.Source: §A.2 · p. 10, Table 4 · p. 10
A.3 Description of Baselines
The baselines span uniform, adversarial, and score-weighted sampling, as well as approaches using graph structure, embedding similarity, or false-negative mitigation.
A.3 Description of Baselines
- Uniform Sampling, KBGAN, NSCaching, and Self-Adv use random corruption, adversarial generation, cached high-scoring negatives, and score-based weighting, respectively.Self-Adv gives higher weights to higher-scoring negatives.Source: §A.3 · p. 10
- SANS and RW-SANS sample from graph neighborhoods or random-walk approximations, with Uniform and Self-Adv weighting variants.Source: §A.3 · p. 10
- EANS, ERDNS, DeMix-Adv, M2ixKG, IF-NS, BigramKG, and ConDNS use embedding similarity, entity–relation frequencies, suspected false negatives, interpolation, influence functions, semantic matching, or diffusion.Their methods include auxiliary false-negative mitigation, dynamically updated candidate repositories, and control of negative difficulty through denoising timesteps.Source: §A.3 · p. 10
A.4 Sensitivity Analysis: 𝜏and 𝜔
The sensitivity analysis finds stable performance across broad adjustment ranges, while relation-category and performance–efficiency analyses report strong results across diverse settings. RADAR’s gains are especially consistent for multi-valued relations, and it pairs high performance with short training times on two datasets.
A.4 Sensitivity Analysis: 𝜏and 𝜔
- Performance remains largely stable across τ values and up to around ω=0.8, but degrades above ω=0.8 as relation-level information can obscure anchor-specific risk.τ controls uncertainty adjustment to observed anchor degree; ω controls the emphasis placed on relation-level degree.Source: §A.4 · pp. 10–11, Figure 10 · p. 11
A.5 Relation Category Analysis
- RADAR shows particularly consistent gains on 1-to-N, N-to-1, and N-to-N relations, but limited gains on 1-to-1 relations, which account for around 1% of triples.The results support risk-aware negative budget allocation for multi-valued relations, where false-negative risk is higher.Source: §A.5 · p. 11, Figure 11 · p. 12
A.6 Performance–Efficiency Trade-Off
- RADAR achieves the highest KGE performance in the shortest training time on FB15k237 and WN18RR, while achieving the highest performance on YAGO3-10 despite not always being fastest.The reported performance–efficiency trade-off spans all KGE models and datasets.Source: §A.6 · p. 11, Figure 12 · p. 12