  Vector representations of graphs and relational structures, whether
hand-crafted feature vectors or learned representations, enable us to apply
standard data analysis and machine learning techniques to the structures. A
wide range of methods for generating such embeddings have been studied in the
machine learning and knowledge representation literature. However, vector
embeddings have received relatively little attention from a theoretical point
of view.
  Starting with a survey of embedding techniques that have been used in
practice, in this paper we propose two theoretical approaches that we see as
central for understanding the foundations of vector embeddings. We draw
connections between the various approaches and suggest directions for future
research.
