LINE: Large-scale
Network Embedding

Chapter 1: First-Order Proximity

First-order proximity is the simplest notion of similarity: two nodes are similar if there is a direct edge between them. If Alice and Bob are connected, their embeddings should be close in vector space. Nodes with no edge between them can be anywhere.

LINE defines a joint probability distribution over observed pairs and a predicted distribution from the embeddings. The first-order objective minimizes the KL divergence between them:

This is just the sigmoid function applied to the dot product of the two embedding vectors. The predicted probability that node i and node j are connected is high when their embeddings point in the same direction (positive dot product) and low when they don't.

The empirical distribution is:

Where w_ij is the edge weight (1 for unweighted graphs) and W = Σ w_ij over all edges. The objective minimizes KL divergence: O₁ = −Σ w_ij log p₁(i,j).

Chapter 2: Second-Order Proximity

Second-order proximity captures shared context: two nodes are similar if they connect to similar neighbors. Bob and Carol might never interact, but if they both follow the same 200 accounts, they're contextually similar. This is exactly the distributional hypothesis from NLP — words that appear in similar contexts have similar meanings.

LINE adopts the Word2Vec skip-gram intuition: for each node v, predict its neighbors' identities from its embedding. Specifically, define two embedding vectors per node: a vertex embedding u_v (v as a source) and a context embedding u'_v (v as a neighbor of others).

This is a softmax over all nodes. Given node i's embedding u_i, the probability that node j is a neighbor equals how well u_i predicts u'_j relative to all other context embeddings. The empirical distribution is again the edge-weight proportion: p̂₂(j|i) = w_ij / d_i, where d_i is the out-degree (or weighted sum) of node i.

Chapter 3: Combined Objective

LINE trains two separate models — one optimizing the first-order objective, one optimizing the second-order objective — then concatenates the resulting embeddings. If each model produces d/2-dimensional embeddings, the final embedding is d-dimensional.

The separate-then-concatenate approach also has a practical benefit: you can train each model independently, possibly on different hardware, and merge the results. This is important at scale — if you have 128 machines, you can assign 64 to first-order and 64 to second-order training in parallel.

The paper uses d=128 total (64+64). In ablation studies, LINE(1st)+LINE(2nd) concatenated outperforms either alone by significant margins on node classification tasks, confirming that the two objectives capture genuinely complementary information.

python
import numpy as np

# After training two separate LINE models:
emb_first  = train_line_first_order(G, dim=64)   # [N, 64]
emb_second = train_line_second_order(G, dim=64)  # [N, 64]

# Final embedding: concatenate
emb_line = np.concatenate([emb_first, emb_second], axis=1)  # [N, 128]

# Normalize (optional but common)
emb_line = emb_line / np.linalg.norm(emb_line, axis=1, keepdims=True)

Chapter 4: Negative Sampling — Showcase

The second-order softmax has a fatal flaw: the denominator sums over all nodes. For a 5-million-node graph, each gradient step requires computing e^(u'_k · u_i) for all 5 million k values. This is O(|V|) per update — completely intractable.

Negative sampling replaces the full softmax with a simpler binary classification. Instead of predicting which node is a neighbor, learn to distinguish real neighbors from random "noise" nodes:

The first term says: for the real neighbor j, maximize the sigmoid of u'_j · u_i (make real pairs score high). The second term says: for K randomly sampled "noise" nodes n, maximize the sigmoid of −u'_n · u_i (make fake pairs score low). Together, this is binary cross-entropy between real edges (label=1) and sampled fake edges (label=0).

With K=5 noise samples per real edge, you've replaced an O(|V|) denominator with O(K) = O(5) work. The gradient computation becomes thousands of times faster, enabling training on billion-edge graphs.

Chapter 5: Scalability

LINE is designed around edge sampling: instead of iterating over nodes and their neighbors, iterate over edges. Sample an edge (i,j) proportional to its weight, apply a gradient update. This is a crucial distinction for weighted graphs where high-weight edges should contribute more updates.

For unweighted graphs, edge sampling is equivalent to uniform edge selection. But for weighted graphs (like trust networks where edge weight = interaction frequency), sampling proportional to weight w_ij naturally gives more training signal to strong connections. The expected number of times edge (i,j) is sampled equals its weight proportion — which matches what the objective is trying to optimize.

The complete training loop for LINE(2nd) is:

python
for step in range(total_steps):
    # 1. Sample an edge proportional to weight (alias method: O(1))
    i, j = alias_sample(edges, weights)

    # 2. Sample K negative nodes proportional to degree^(3/4)
    negatives = alias_sample(nodes, degree_pow_075, K)

    # 3. Compute gradient of binary cross-entropy loss
    grad = compute_neg_sampling_gradient(u[i], u_ctx[j], u_ctx[negatives])

    # 4. Update only the involved vectors (sparse update)
    u[i] -= lr * grad.vertex
    u_ctx[j] -= lr * grad.context_pos
    for n in negatives:
        u_ctx[n] -= lr * grad.context_neg[n]

Notice step 4: only 1 vertex + (K+1) context vectors are updated per step. No matrix multiply, no batch normalization, no full forward pass. This sparse update is why LINE can train on a single machine with 50 threads and embed 5 million nodes in a few hours.

Chapter 6: Results

LINE is evaluated on three tasks across very different graph types: multi-label classification on social networks (Flickr, YouTube), sentiment classification on a word-word co-occurrence network (DBLP), and link prediction. The graphs range from 7K to 1.7M nodes.

LINE(1st+2nd) outperforms all baselines on all datasets. Second-order is consistently stronger than first-order alone — shared neighborhood captures richer signal than direct connection for classification tasks. The combination dominates both.

On link prediction, LINE achieves AUC of 91.4% on directed networks where edge direction matters — significantly outperforming methods that ignore direction. LINE handles directed graphs naturally by using separate source and target embeddings, while random-walk methods implicitly treat graphs as undirected.

Chapter 7: Connections

LINE established the vocabulary of first- and second-order proximity that subsequent methods built on. Understanding where it fits helps locate what each method improved.

LINE's biggest limitation is that it's shallow: first-order looks 1 hop away, second-order looks at the distribution over 1-hop neighbors. It never captures 3-hop or longer patterns. Methods like node2vec and GraphSAGE extend this to longer ranges, but at higher cost.

LINE also doesn't use node features — only graph structure. For networks where nodes have rich attributes (text descriptions, images, metadata), GraphSAGE and GAT can leverage features directly in the aggregation. LINE treats all nodes as featureless ids.

"The key to network embedding is to preserve the network structure and properties in a low-dimensional space."
— Tang et al. (2015)