  Knowledge Graph (KG) is a flexible structure that is able to describe the
complex relationship between data entities. Currently, most KG embedding models
are trained based on negative sampling, i.e., the model aims to maximize some
similarity of the connected entities in the KG, while minimizing the similarity
of the sampled disconnected entities. Negative sampling helps to reduce the
time complexity of model learning by only considering a subset of negative
instances, which may fail to deliver stable model performance due to the
uncertainty in the sampling procedure. To avoid such deficiency, we propose a
new framework for KG embedding -- Efficient Non-Sampling Knowledge Graph
Embedding (NS-KGE). The basic idea is to consider all of the negative instances
in the KG for model learning, and thus to avoid negative sampling. The
framework can be applied to square-loss based knowledge graph embedding models
or models whose loss can be converted to a square loss. A natural side-effect
of this non-sampling strategy is the increased computational complexity of
model learning. To solve the problem, we leverage mathematical derivations to
reduce the complexity of non-sampling loss function, which eventually provides
us both better efficiency and better accuracy in KG embedding compared with
existing models. Experiments on benchmark datasets show that our NS-KGE
framework can achieve a better performance on efficiency and accuracy over
traditional negative sampling based models, and that the framework is
applicable to a large class of knowledge graph embedding models.
