What are graph embedding?
What are graph Embeddings ?
"Graph Embeddings" is a hot area today in machine learning. It basically means finding "latent vector representation" of graphs which captures the topology (in very basic sense) of the graph. We can make this "vector representation" rich by also considering the vertex-vertex relationships, edge-information etc. There are roughly two levels of embeddings in the graph (of-course we can anytime define more levels by logically dividing the whole graph into subgraphs of various sizes):


Vertex Embeddings - Here you find latent vector representation of every vertex in the given graph. You can then compare the different vertices by plotting these vectors in the space and interestingly "similar" vertices are plotted closer to each other than the ones which are dissimilar or less related. This is the same work that is done in "DeepWalk" by Perozzi.
Graph Embeddings - Here you find the latent vector representation of the whole graph itself. For example, you have a group of chemical compounds for which you want to check which compounds are similar to each other, how many type of compounds are there in the group (clusters) etc. You can use these vectors and plot them in space and find all the above information. This is the work that is done in "Deep Graph Kernels" by Yanardag.


Applications -
By looking carefully, embeddings are "latent" representations  which means if a graph has a |V| * |V| adjacency matrix where |V| = 1M, its hard to use or process a 1M * 1M numbers in an algorithm. So, latent embedding of dimension 'd', where d &lt;&lt; |V|, would make the adjacency matrix |V| * d and relatively easier to use. Another application could be - Consider a simple scenario where we want to recommend products to the people who have similar interests in a social network. By getting vertex embeddings (here it means vector representation of each person), we can find the similar ones by plotting these vectors and this makes recommendation easy. These are some applications and there are others. You can refer to a nice survey paper - Graph Embedding Techniques, a Survey.

Where from it all came ? There has been a lot of works in this area and almost all comes from the groundbreaking research in natural language processing field - "Word2Vec" by Mikolov. If you want to get started with the research on graph embeddings, I would recommend to first understand how Word2Vec works. You can find nice explanations - Word2Vec parameter learning explained and Stanford Lecture. Then you can jump to the papers that you listed. Those works can be categorized as:


Works based on "Vertex Embeddings": - DeepWalk, Node2Vec, LINE.
Works based on "Graph Embeddings": - Deep Graph Kernels, Subgraph2Vec.