# NSCaching: Simple and Efficient Negative Sampling for Knowledge Graph Embedding

arXiv: https://arxiv.org/abs/1812.06410 · HTML: https://mlsanity.com/paper/1812.06410/

## Key facts

- Cited by 42 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 16 Dec 2018.

## Built on by (most cited first, 30 of 42)

- [Knowledge Graph Reasoning with Relational Digraph](https://mlsanity.com/paper/2108.06040/) (2021)
- [Temporal Knowledge Graph Completion: A Survey](https://mlsanity.com/paper/2201.08236/) (2022)
- [A Review of Biomedical Datasets Relating to Drug Discovery: A Knowledge Graph Perspective](https://mlsanity.com/paper/2102.10062/) (2021)
- [Knowledge Graph Completion with Pre-trained Multimodal Transformer and Twins Negative Sampling](https://mlsanity.com/paper/2209.07084/) (2022)
- [AutoGEL: An Automated Graph Neural Network with Explicit Link Information](https://mlsanity.com/paper/2112.01064/) (2021)
- [Does Negative Sampling Matter? A Review with Insights into its Theory and Applications](https://mlsanity.com/paper/2402.17238/) (2024)
- [Efficient Non-Sampling Knowledge Graph Embedding](https://mlsanity.com/paper/2104.10796/) (2021)
- [CAKE: A Scalable Commonsense-Aware Framework For Multi-View Knowledge Graph Completion](https://mlsanity.com/paper/2202.13785/) (2022)
- [Positive-Unlabeled Learning with Adversarial Data Augmentation for Knowledge Graph Completion](https://mlsanity.com/paper/2205.00904/) (2022)
- [MMKGR: Multi-hop Multi-modal Knowledge Graph Reasoning](https://mlsanity.com/paper/2209.01416/) (2022)
- [Relation-aware Graph Attention Model With Adaptive Self-adversarial Training](https://mlsanity.com/paper/2102.07186/) (2021)
- [Medical Entity Disambiguation Using Graph Neural Networks](https://mlsanity.com/paper/2104.01488/) (2021)
- [Negative Sampling in Knowledge Graph Representation Learning: A Review](https://mlsanity.com/paper/2402.19195/) (2024)
- [Modality-Aware Negative Sampling for Multi-modal Knowledge Graph Embedding](https://mlsanity.com/paper/2304.11618/) (2023)
- [Negative Sampling with Adaptive Denoising Mixup for Knowledge Graph Embedding](https://mlsanity.com/paper/2310.09781/) (2023)
- [Learning Explicit User Interest Boundary for Recommendation](https://mlsanity.com/paper/2111.11026/) (2021)
- [Heterogeneous Graph Contrastive Learning with Meta-path Contexts and Adaptively Weighted Negative Samples](https://mlsanity.com/paper/2212.13847/) (2022)
- [MixKG: Mixing for harder negative samples in knowledge graph](https://mlsanity.com/paper/2202.09606/) (2022)
- [Mixture of Length and Pruning Experts for Knowledge Graphs Reasoning](https://mlsanity.com/paper/2507.20498/) (2025)
- [Exploring the Learning Difficulty of Data Theory and Measure](https://mlsanity.com/paper/2205.07427/) (2022)
- [Entity Aware Negative Sampling with Auxiliary Loss of False Negative Prediction for Knowledge Graph Embedding](https://mlsanity.com/paper/2210.06242/) (2022)
- [Treat Different Negatives Differently: Enriching Loss Functions with Domain and Range Constraints for Link Prediction](https://mlsanity.com/paper/2303.00286/) (2023)
- [HaSa: Hardness and Structure-Aware Contrastive Knowledge Graph Embedding](https://mlsanity.com/paper/2305.10563/) (2023)
- [A Comprehensive Analytical Survey on Unsupervised and Semi-Supervised Graph Representation Learning Methods](https://mlsanity.com/paper/2112.10372/) (2021)
- [LEMON: LanguagE ModeL for Negative Sampling of Knowledge Graph Embeddings](https://mlsanity.com/paper/2203.04703/) (2022)
- [Noisy Positive-Unlabeled Learning with Self-Training for Speculative Knowledge Graph Reasoning](https://mlsanity.com/paper/2306.07512/) (2023)
- [Bayesian Negative Sampling for Recommendation](https://mlsanity.com/paper/2204.06520/) (2022)
- [Leveraging Wikidata's edit history in knowledge graph refinement tasks](https://mlsanity.com/paper/2210.15495/) (2022)
- [Importance of negative sampling in weak label learning](https://mlsanity.com/paper/2309.13227/) (2023)
- [Personalized Negative Reservoir for Incremental Learning in Recommender Systems](https://mlsanity.com/paper/2403.03993/) (2024)

## Abstract (arXiv)

Knowledge Graph (KG) embedding is a fundamental problem in data mining research with many real-world applications. It aims to encode the entities and relations in the graph into low dimensional vector space, which can be used for subsequent algorithms. Negative sampling, which samples negative triplets from non-observed ones in the training data, is an important step in KG embedding. Recently, generative adversarial network (GAN), has been introduced in negative sampling. By sampling negative triplets with large scores, these methods avoid the problem of vanishing gradient and thus obtain better performance. However, using GAN makes the original model more complex and hard to train, where reinforcement learning must be used. In this paper, motivated by the observation that negative triplets with large scores are important but rare, we propose to directly keep track of them with the cache. However, how to sample from and update the cache are two important questions. We carefully design the solutions, which are not only efficient but also achieve a good balance between exploration and exploitation. In this way, our method acts as a "distilled" version of previous GA-based methods, which does not waste training time on additional parameters to fit the full distribution of negative triplets. The extensive experiments show that our method can gain significant improvement in various KG embedding models, and outperform the state-of-the-art negative sampling methods based on GAN.