  Negative sampling, which samples negative triplets from non-observed ones in
knowledge graph (KG), is an essential step in KG embedding. Recently,
generative adversarial network (GAN), has been introduced in negative sampling.
By sampling negative triplets with large gradients, these methods avoid the
problem of vanishing gradient and thus obtain better performance. However, they
make the original model more complex and harder to train. In this paper,
motivated by the observation that negative triplets with large gradients are
important but rare, we propose to directly keep track of them with the cache.
In this way, our method acts as a "distilled" version of previous GAN-based
methods, which does not waste training time on additional parameters to fit the
full distribution of negative triplets. However, how to sample from and update
the cache are two critical questions. We propose to solve these issues by
automated machine learning techniques. The automated version also covers
GAN-based methods as special cases. Theoretical explanation of NSCaching is
also provided, justifying the superior over fixed sampling scheme. Besides, we
further extend NSCaching with skip-gram model for graph embedding. Finally,
extensive experiments show that our method can gain significant improvements on
various KG embedding models and the skip-gram model, and outperforms the
state-of-the-art negative sampling methods.
