PaperlayerView exact revision on arXiv

Source-linked AI summary

NSCaching: Simple and Efficient Negative Sampling for Knowledge Graph Embedding

Yongqi Zhang, Quanming Yao, Yingxia Shao, Lei Chen

arXiv:1812.06410v2cs.AIcs.CLcs.LG

TL;DR

KG embedding needs informative negative triplets, but fixed sampling can produce vanishing gradients and GAN-based approaches add training complexity. NSCaching maintains high-quality negatives in a dynamically updated cache, and experiments report improvements over GAN-based negative-sampling methods across KG embedding settings.

  • Problem

    Fixed negative-sampling schemes can select easily classified triplets and cause vanishing gradients, while GAN-based alternatives add parameters and unstable, high-variance training.

    Source: §I · pp. 1–2

  • Method

    NSCaching stores high-quality negative triplets in a cache, samples from it, and uses importance sampling to update it while balancing exploration and exploitation.

    Source: §I · p. 2

  • Results

    Experiments report improved effectiveness over IGAN and KBGAN across four datasets, with state-of-the-art performance on FB15K.

    Source: §I · p. 2, §VI · p. 12

  • Takeaways & Limitations

    The scheme can be injected into popular KG embedding models and trained with gradient descent as the original models are.

    Source: §I · p. 2

    At million-scale KGs, cache memory becomes a problem, and theoretical convergence remains future work.

    Source: §VI · p. 12

Abstract

from arXiv · show

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.

I. INTRODUCTION

Knowledge graph embeddings represent entities and relations in low-dimensional vectors, but effective training depends on sampling informative negative triplets. NSCaching keeps high-quality negatives in a cache and dynamically updates it, addressing shortcomings of fixed sampling and GAN-based methods.

I. INTRODUCTION

  • Uniform and Bernoulli sampling are fixed schemes that can select easily classified negatives, causing vanishing gradients and impeding training.The paper attributes this to most sampled negatives becoming low-scoring as training progresses.Source: §I · pp. 1–2
  • GAN-based negative sampling targets dynamic, high-quality negatives but adds parameters and unstable, high-variance REINFORCE training that makes pretraining necessary.The paper identifies instability, degeneracy, and high-variance gradients as drawbacks of IGAN and KBGAN.Source: §I · p. 2
  • NSCaching stores high-quality negative triplets and uses importance sampling to update the cache while balancing exploration and exploitation.The update strategy is intended to capture changing score distributions efficiently.Source: §I · p. 2
  • NSCaching is designed as a general scheme for popular KG embedding models, with fewer parameters than IGAN and KBGAN and gradient-descent training.The paper reports experiments with four datasets and describes gains in efficiency and effectiveness over IGAN and KBGAN.Source: §I · p. 2
  • The paper connects NSCaching to self-paced learning: it can learn easily classified samples first and then gradually switch to harder ones.This progression is presented as an analysis of the method’s behavior.Source: §I · p. 2
  • NSCaching outperforms state-of-the-art GAN-based negative-sampling methods across experiments on WN18, FB15K, WN18RR, and FB15K237.The reported comparison is with IGAN and KBGAN; the paper also describes the method as efficient.Source: §I · p. 2

II. PRELIMINARY: FRAMEWORK OF KG EMBEDDING

The preliminary section frames KG embedding as learning entity and relation representations from observed facts. Its general framework uses a scoring objective and stochastic updates, with negative sampling supplying non-observed triplets for training.

A. The General Framework

  • KG embedding learns entity and relation representations by scoring observed facts above non-observed triplets.The framework uses embeddings and a scoring function to capture interactions between entities under a relation.Source: A. The General Framework · p. 2
  • Each stochastic-gradient iteration samples a minibatch, draws negatives, and updates embedding parameters using the model objective.The framework applies this procedure to translational-distance and semantic-matching models.Source: A. The General Framework · pp. 2–3
  • For each positive triplet, training forms a corresponding negative-sample set and samples a negative triplet because the observed set contains only positive facts.The sampled negative is used alongside the positive in the objective.Source: A. The General Framework · p. 2

B. Negative Sampling

Negative sampling supplies the absent triplets needed to train KG embeddings, but fixed sampling can keep drawing easy negatives as training changes. GAN-based samplers adapt to the distribution, while introducing training costs and complexity.

1) Sample from fixed distributions:

  • Bernoulli sampling reduces false negatives in one-to-many, many-to-many, and many-to-one relations, but fixed schemes still miss changing distributions and high-scoring negatives.Uniform sampling is simple and efficient, but both uniform and Bernoulli sampling can suffer vanishing gradients.Source: 1) Sample from fixed distributions · p. 3

2) Sample from dynamic distributions:

  • IGAN samples over all entities, whereas KBGAN first forms a random candidate set and selects a relatively high-quality triplet from it.Both use GAN generators to approximate negative-sample distributions dynamically.Source: 2) Sample from dynamic distributions · p. 3
  • GAN-based negative sampling faces instability and degeneracy, requires high-variance REINFORCE gradients and pretraining, and adds parameters and training costs.Source: 2) Sample from dynamic distributions · p. 3

1) Translational distance model:

  • Translational models such as TransE score triplets by negative translational distance; TransE struggles with one-to-many, many-to-one, and many-to-many relations.TransH, TransR, and TransD address this issue by projecting entity embeddings into different spaces.Source: 1) Translational distance model · p. 3

2) Semantic matching model:

Semantic matching models score triplets by similarity rather than requiring h + r ≈ t. The paper observes that high-scoring negative triplets are rare and proposes NSCaching to track and sample them from a dynamically updated cache.

2) Semantic matching model:

  • Semantic matching models measure triplet plausibility by similarity rather than assuming h + r ≈ t; RESCAL represents each relation with a matrix.DistMult constrains that matrix to be diagonal, while HolE and ComplEx model asymmetric relations.Source: 2) Semantic matching model · pp. 3–4

III. PROPOSED MODEL

  • The proposed-model section also identifies a connection between NSCaching and self-paced learning as a further explanation of its performance.Source: §III · p. 4

A. Closer Look at Distribution of Negative Triplets

  • Regardless of training stage or positive triplet, only a few negative triplets have large scores, while the distribution changes during training.Figure 1 plots the proportion of negatives with distance D ≥ x and marks margin γ; beyond that margin, gradients vanish.Source: A. Closer Look at Distribution of… · p. 4, Figure 1 · p. 4

B. NSCaching: the Proposed Method

  • NSCaching maintains caches of high-scoring negative samples for each positive triplet and samples negatives directly from those caches.The scheme is independent of the scoring function and can be used with previously described scoring functions.Source: B. NSCaching: the Proposed Method · pp. 4–5
  • NSCaching is presented as a discriminative, distilled alternative to GAN-based methods that focuses on high-scoring negatives, has fewer parameters, and trains from random initialization.The paper reports that experiments show NSCaching achieves the best performance.Source: B. NSCaching: the Proposed Method · p. 5

1) Uniform sampling strategy from the cache (step 6):

The cache sampler chooses negatives uniformly from candidates already retained in the cache, balancing exploration and exploitation rather than always selecting the highest-scoring candidate.

1) Uniform sampling strategy from the cache (step 6):

2) Importance sampling strategy to update the cache (step 8):

NSCaching refreshes its cache by combining retained candidates with uniformly sampled entities, then resampling without replacement according to candidate scores. The design balances exploration and exploitation while keeping cache-related costs bounded by candidate-set size.

2) Importance sampling strategy to update the cache (step 8):

  • Cache refresh unions the existing cache with N2 uniformly sampled entities, scores the candidates, then samples N1 entries without replacement using score-based probabilities.The resulting subset becomes the updated cache.Source: 2) Importance sampling strategy to… · pp. 5–6
  • Larger N1 increases exploitation and larger N2 increases exploration; score-weighted resampling avoids uniform selection and deterministic top-score selection.The paper cites false negatives as a reason not to keep only the top-scoring candidates.Source: 2) Importance sampling strategy to… · p. 6

3) Space and time complexities:

  • O((N1 + N2)d) is the cache-update time cost per triplet, compared with O(|E|d) for IGAN and O(N1d) for KBGAN.The cache-update cost can be reduced to O((N1 + N2)d/(n + 1)) by updating lazily every n epochs.Source: 3) Space and time complexities · p. 6
  • O(|S|N1) space stores cache indices, and the experiments use N1 = N2 = 50 on WN18 and FB15K.Because of repeated relation patterns, the authors say the actual index-storage cost is smaller than O(|S|N1).Source: 3) Space and time complexities · p. 6

4) Discussion on the Convergence:

The discussion links NSCaching’s larger-magnitude gradients to its empirical convergence behavior and explains how its cache shifts learning from easier to harder negatives. The experiments evaluate four datasets on link prediction, alongside their dataset properties and task setup.

4) Discussion on the Convergence:

  • NSCaching’s larger-magnitude gradients are described as preventing early stopping by sampling and helping it converge to higher testing performance than baseline models.The authors say these claims are empirically shown and studied in Section IV.Source: 4) Discussion on the Convergence · p. 6

C. Connection to Self-Pace Learning

  • The cache supports self-paced learning: easy negatives are learned first and removed as their scores fall, shifting attention toward harder negatives.Experiments reportedly show the cache changing from easy to hard negatives, and NSCaching trained from scratch outperforming pretrained IGAN and KBGAN.Source: C. Connection to Self-Pace Learning · p. 6

IV. EXPERIMENTS

  • The empirical study runs its algorithms in Python with PyTorch on a TITAN Xp GPU.Source: §IV · p. 6

1) Datasets:

  • The experiments use WN18, FB15K, and their harder, more realistic variants WN18RR and FB15K237.WN18 and WN18RR are WordNet subsets; FB15K and FB15K237 are Freebase subsets.Source: 1) Datasets · pp. 6–7

2) Tasks:

  • Link prediction evaluates how highly the correct head or tail entity ranks among all entities for a positive triplet.Source: 2) Tasks · p. 7

3) Performance measurements:

The section defines the ranking metrics, identifies scoring functions and compares negative-sampling approaches. The comparison setup includes both scratch training and warm-started training.

3) Performance measurements:

  • MRR averages reciprocal ranks, Hit@10 measures the percentage ranked in the top 10, and MR averages ranks; higher MRR and Hit@10 and lower MR indicate better performance.Results use filtered evaluation; the authors caution that MR can be influenced by false positives.Source: 3) Performance measurements · p. 7

4) Choices of the scoring function:

  • The compared scoring functions include translational-distance models and semantic-matching models, with five selected for comparison: TransE, TransH, TransD, DistMult, and ComplEx.Source: 4) Choices of the scoring function · p. 7

B. Comparison with State-of-the-arts

1) Compared methods:

  • NSCaching samples replacement entities from head or tail caches and updates those caches; KBGAN selects candidates from a uniformly sampled entity set, while Bernoulli sampling varies head-versus-tail replacement probabilities.The study uses N1 = N2 = 50 and immediate cache updates unless otherwise specified; IGAN is not directly compared because its code was unavailable.Source: 1) Compared methods · p. 7
  • KBGAN and NSCaching are evaluated both from scratch and with pretraining that warm-starts entity and relation embeddings.Scratch training uses Xavier uniform initialization; pretraining first trains with Bernoulli sampling, then continues with the warm-started embeddings.Source: 1) Compared methods · pp. 7–8

2) Hyper-parameter settings:

Hyperparameters are selected by grid search and validation MRR, then held fixed across the baseline and negative-sampling methods.

2) Hyper-parameter settings:

  • Grid search varies embedding dimension, learning rate, and model-specific margin or penalty; the best setting is selected by validation MRR under Bernoulli sampling and held fixed for Bernoulli, KBGAN, and NSCaching.Adam uses its default settings except for learning rate; Bernoulli trains to 3000 epochs, while KBGAN and NSCaching are evaluated within 1000 epochs, from scratch or with pretraining.Source: 2) Hyper-parameter settings · pp. 8–9

3) Results on translational distance models:

Across translational and semantic matching models, NSCaching performs consistently better than the compared negative-sampling methods, and it also outperforms baselines on triplet classification. The cache-sampling analysis finds uniform sampling the best of the tested cache-sampling strategies.

3) Results on translational distance models:

  • NSCaching improves on Bernoulli and outperforms IGAN and KBGAN in translational-distance models, while working from either pretraining or scratch and converging faster and more stably.IGAN and KBGAN perform better with pretraining than from scratch; NSCaching can perform well in either setting.Source: 3) Results on translational distance… · p. 9

4) Results on semantic matching models:

  • NSCaching significantly outperforms Bernoulli and performs best across the tested settings for semantic-matching models; ComplEx results show stable NSCaching convergence while KBGAN turns down and overfits.The convergence comparison uses ComplEx as the representative semantic-matching model.Source: 4) Results on semantic matching models · pp. 9–10, Figure 5 · p. 10

5) Results on triplets classification:

1) Uniform sampling from the cache (step 6):

2) Importance sampling strategy to update the cache (step 8):

Importance sampling for cache updates outperforms top updates, which change fewer cache elements and update more slowly. The cache-size analysis reports stable performance across a range of sizes, with both sizes needing to avoid being too small.

2) Importance sampling strategy to update the cache (step 8):

  • Importance-sampling cache updates outperform top updates by a large margin, while changing more cache elements and keeping the cache fresh as the negative-sample distribution changes.The comparison evaluates performance, cache changes, and non-zero-loss ratios.Source: 2) Importance sampling strategy to… · p. 11, Figure 8 · p. 11

D. Sensitivity Analysis: Cache Size

E. Illustration of Vanishing Gradient

NSCaching maintains larger gradient norms than Bernoulli sampling and avoids gradients decreasing to zero in the reported experiment. The conclusion also identifies memory use on million-scale knowledge graphs and theoretical convergence as open issues.

E. Illustration of Vanishing Gradient

  • NSCaching's average gradient norm remains larger than Bernoulli's and does not decrease to zero, which the authors report as avoiding the vanishing-gradient problem.Both methods' norms become smaller; mini-batch sampling introduces noise into gradients.Source: E. Illustration of Vanishing Gradient · p. 12, Figure 10 · p. 12

F. Explanation of the connection to Self-Paced Learning

VI. CONCLUSION

  • For million-scale knowledge graphs, cache memory becomes a concern; distributed computation or hashing and theoretical convergence are left for future work.Source: §VI · p. 12
Loading 1812.06410v2…