LINE: Large-scale Information Network Embedding

The paper studies embedding very large information networks into low-dimensional vector spaces to support tasks such as visualization, node classification, and link prediction. The proposed LINE method applies to arbitrary network types, undirected, directed, and weighted, and optimizes a carefully designed objective function that preserves both the local and the global structure of the network. To make inference effective and efficient, it introduces an edge-sampling algorithm that addresses limitations of classical stochastic gradient descent.

Empirical experiments on a variety of real-world networks, including language, social, and citation networks, demonstrate the method's effectiveness. The approach is also highly efficient, able to learn embeddings for a network with millions of vertices and billions of edges within a few hours on a single typical machine, and the authors released the source code, making large-scale network embedding broadly accessible.