The goal is to learn embeddings so that the equation roughly holds:
$Dec(z_u,z_v)=\frac{e^{z_u^T z_v}}{\sum_{v_k \in V} e^{z_u^T z_k}}$

Goal of Random Walk Embeddings

They often minimize a following cross-entropy loss:
$L = \sum_{u,v \in D} -log(DEC(z_u,z_v))$

General Strategy of Random Walk Embeddings

$L = \sum_{u,v \in D} -log(\sigma (z_u^T z_v)) - \gamma E_{v_n \sim P_n(v)}[log(-\sigma (z_u^T z_{v_n}))]$

Noise Contrastive Approximation Approach of Node2Vec

The LINE approach does not explicitly leverage random walks, but it shares conceptual motivations with DeepWalk and node2vec. The basic idea in LINE is to combine two encoderdecoder objectives.

Large-scale Information Network Embeddings(LINE)

Those two methods are closely related. The key difference is that the DeepWalk embeddings control the influence of different eigenvalues through a hyperparameter.

Relationships between Random Walk Methods and Matrix Factorization

1. The first issue is that shallow embedding methods do not share any parameters between nodes in the encoder, since the encoder directly optimizes a unique embedding vector for each node.
2. A second key issue with shallow embedding approaches is that they do not leverage node features in the encoder.
3. Shallow embedding methods are inherently transductive.

Limitations of Shallow Embeddings

Node embeddings are optimized so that two nodes have similar embeddings
if they tend to co-occur on short random walks over the graph.

University of Michigan - Ann Arbor

Node embeddings is a way of graph representation. The goal of node embeddings is to map the nodes in the graph into a low-dimensional vector space, where the relations of the nodes in graph can be reflected by the geometric relations in the embedding space. Compared with hand-engineered features, node embeddings are more flexible and they are learned through learning processes.

Node Embeddings

Hamilton, W.L. Graph Representation Learning. *Synthesis Lectures on Artificial Intelligence and Machine Learning*. 2020, 14(3), 1–159. https://doi.org/10.2200/S01045ED1V01Y202009AIM046

Graph Representation Learning by William Hamilton

Summary of Shallow Embedding Algorithms.

Encoder and decoder graph framework is used for learning node embeddings for graph representation learning.

Encoder maps node in a graph to a low dimensional vector space.

Decoder uses the low dimensional node embeddings to reconstruct the node's position in the original graph.

Encoder and Decoder Graph Framework 

Matrix factorization is used  to learn a low-dimensional approximation of a node-node similarity matrix S, where S generalizes the adjacency matrix and captures some user defined notion of node-node similarity.

Learn Before

Related

Learn After