  Embedding entities and relations of a knowledge graph in a low-dimensional
space has shown impressive performance in predicting missing links between
entities. Although progresses have been achieved, existing methods are
heuristically motivated and theoretical understanding of such embeddings is
comparatively underdeveloped. This paper extends the random walk model (Arora
et al., 2016a) of word embeddings to Knowledge Graph Embeddings (KGEs) to
derive a scoring function that evaluates the strength of a relation R between
two entities h (head) and t (tail). Moreover, we show that marginal loss
minimisation, a popular objective used in much prior work in KGE, follows
naturally from the log-likelihood ratio maximisation under the probabilities
estimated from the KGEs according to our theoretical relationship. We propose a
learning objective motivated by the theoretical analysis to learn KGEs from a
given knowledge graph. Using the derived objective, accurate KGEs are learnt
from FB15K237 and WN18RR benchmark datasets, providing empirical evidence in
support of the theory.

Computation and Language