Graph Embedding: A Methodological Survey

Embedding a high dimensional combinatorial object like tokens in text or nodes in graphs into a lower dimensional Euclidean space is a form of (lossy) data compression. We will demonstrate a class of procedures to embed vertices of a (connected) graph into a low-dimensional Euclidean space. We explore two kinds of embedding, one node2vec, similar to word2vec, which deploys a shallow network and a recurrent network which remembers past moves and takes [sic] spatial correlations into an account. We also explore the extent in which graph embedding preserves information and the practicality of using the information stored in a compressed form to discern meaningful patterns. With growth in their popularity, we too make an extensive use of the neural networks computational frameworks; we propose the usage of various neural network architectures to implement an encoder-decoder scheme to learn 'hidden' features. Since training a network requires data, we describe various sampling techniques including novel methods to sample from a graph; one using a vertex cover and another is an Eulerian tour of a (possibly) modified graph.