Overview

LINE is short for Large-scale Information Network Embedding. LINE is a graph embedding model, it uses the BFS neighborhood information (first-order or second-order proximity) of nodes to construct training samples, and train node embeddings by the method similar to Node2Vec. LINE is able to scale to very large, arbitrary types of networks, it was proposed by J. Tang et al. of Microsoft in 2015.

Related material of the algorithm:

• J. Tang, M. Qu, M. Wang, M. Zhang, J. Yan, Q. Zhu, LINE: Large-scale Information Network Embedding (2015)

Basic Concept

First-order Proximity and Second-order Proximity

First-order proximity between nodes in the graph depends on the connectivity, that is, the larger the edge weight (edge weight equals to 1 for unweighted graph; negative weight is not considered here) between nodes, the higher the first-order proximity they have. In case there is no link between two nodes, their first-order proximity is 0. First-order proximity reflects the local structure.

Second-order proximity reflects the global structure, and it is determined by the common neighbors two nodes share. The general notion of the second-order proximity is actually easy to understand, for instance, in social network, the more friends two people have in common, the higher the connection between the two people. In case two nodes have no common neighbors, their second-order proximity is 0.

As shown in the graph below, the thickness of edge represents the weight size. As the weight of the edge between nodes 6 and 7 is large, i.e., they have a high first-order proximity, they should be represented closely to each other in the embedded space. On the other hand, though there is no edge between nodes 5 and 6, they share many common neighbors, i.e., they have a high second-order proximity and therefore should also be represented closely to each other.

Model Description

We describe the LINE model to preserve the first-order proximity and second-order proximity separately, and then introduce a simple way to combine the two proximity.

LINE with First-order Proximity

For graph G = (V, E), to model the first-order proximity, LINE defines the joint probability between nodes v_i and v_j as follows:

where u is the low-dimensional vector representation of node. Empirical joint probability between node v_i and v_j can be defined as

where w_ij denotes the edge weight between nodes v_i and v_j.

To preserve the first-order proximity, a straightforward way is to minimize the difference between the two distributions (i.e., the value predicted by the model is close to the actual value). LINE adopts the KL (Kullback-Leibler) divergence to measure the difference (constants are omitted):

Note that first-order proximity is only applicable for undirected graphs, not for directed graphs.

LINE with Second-order Proximity

In graph, each node plays two roles: the node itself and a specific 'context' of other node. Nodes with similar distributions over the 'contexts' are assumed to have second-order proximity. We define the probability of context v_j generated by node v_i as follows (without loss of generality, we assume it is directed):

where u' is the representation of node when it is treated as a 'context', |V| is the number of nodes or 'contexts' in the graph. The corresponding empirical probability can be defined as

where w_ij denotes the edge weight between nodes v_i and v_j, d_i is the out-degree of node v_i.

Similarly, LINE adopts the KL (Kullback-Leibler) divergence to measure the difference (constants are omitted) between these two probability distributions:

Second-order proximity is applicable for both directed and undirected graphs.

Combining First-order and Second-order Proximities

To embed the networks by preserving both the first-order and second-order proximity, a simple and effective way we find in practice is to train the LINE model which preserves the first-order proximity and second-order proximity separately and then concatenate the embeddings trained by the two methods for each vertex.

Model Optimization

Optimizing objective O₂ is computationally expensive, which requires the summation over the entire set of nodes when calculating the conditional probability p2(·|v_i). To address this problem, LINE adopts the approach of negative sampling. More specifically, it specifies the following objective function for each edge from node v_i to v_j:

where σ is the sigmoid function. The first term models the observed edges, the second term models the negative edges drawn from the noise distribution and K is the number of negative edges. We set P_n(v) ∝ d_v^3/4, and d_v is the out degree of node v.

About negative sampling, readers may refer to Skip-gram Model Optimization.

Special Case

Lonely Node, Disconnected Graph

Lonely node has no adjacent node, hence it has no first-order or second-order proximity with any other nodes.

Nodes only has first-order or second-order proximity with nodes in the same connected component.

Self-loop Edge

Self-loop edges of node have nothing to do with the first-order or second-order proximity the node has with other nodes.

Directed Edge

First-order proximity is only applicable for undirected graphs, not for directed graphs. Second-order proximity is applicable for both directed and undirected graphs.

Command and Configuration

• Command：algo(line)
• Configurations for the parameter params():

Algorithm Execution

Task Writeback

1. File Writeback

2. Property Writeback

Not supported by this algorithm.

3. Statistics Writeback

This algorithm has no statistics.

Direct Return

Streaming Return

Real-time Statistics

This algorithm has no statistics.