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.

University of Michigan - Ann Arbor

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

Random Walk 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

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

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.

Learn Before

Related