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

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))$$

Learn Before

Related