  Knowledge graph embedding methods learn continuous vector representations for
entities in knowledge graphs and have been used successfully in a large number
of applications. We present a novel and scalable paradigm for the computation
of knowledge graph embeddings, which we dub PYKE . Our approach combines a
physical model based on Hooke's law and its inverse with ideas from simulated
annealing to compute embeddings for knowledge graphs efficiently. We prove that
PYKE achieves a linear space complexity. While the time complexity for the
initialization of our approach is quadratic, the time complexity of each of its
iterations is linear in the size of the input knowledge graph. Hence, PYKE's
overall runtime is close to linear. Consequently, our approach easily scales up
to knowledge graphs containing millions of triples. We evaluate our approach
against six state-of-the-art embedding approaches on the DrugBank and DBpedia
datasets in two series of experiments. The first series shows that the cluster
purity achieved by PYKE is up to 26% (absolute) better than that of the state
of art. In addition, PYKE is more than 22 times faster than existing embedding
solutions in the best case. The results of our second series of experiments
show that PYKE is up to 23% (absolute) better than the state of art on the task
of type prediction while maintaining its superior scalability. Our
implementation and results are open-source and are available at
http://github.com/dice-group/PYKE.
