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

The goal of random walk embeddings is to optimize node representations so that the pairwise decoder, defined via a softmax function, approximates the probability of co-occurrence on random walks:

$$Dec(z_u, z_v) = \frac{e^{z_u^T z_v}}{\sum_{v_k \in V} e^{z_u^T z_k}} \approx p_R(v | u)$$

where $$p_R(v | u)$$ is the probability of visiting node $$v$$ on a short random walk starting from node $$u$$.

Softmax Decoder Objective in Random Walk Embeddings

Random walk embedding methods often minimize the following cross-entropy loss: $$L = \sum_{u,v \in D} -\log(DEC(z_u,z_v))$$

Cross-Entropy Loss in Random Walk 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

Learn After

Related