LINE

Abstract

This paper studies the problem of embedding very large information networks\ninto low-dimensional vector spaces, which is useful in many tasks such as\nvisualization, node classification, and link prediction. Most existing graph\nembedding methods do not scale for real world information networks which\nusually contain millions of nodes. In this paper, we propose a novel network\nembedding method called the "LINE," which is suitable for arbitrary types of\ninformation networks: undirected, directed, and/or weighted. The method\noptimizes a carefully designed objective function that preserves both the local\nand global network structures. An edge-sampling algorithm is proposed that\naddresses the limitation of the classical stochastic gradient descent and\nimproves both the effectiveness and the efficiency of the inference. Empirical\nexperiments prove the effectiveness of the LINE on a variety of real-world\ninformation networks, including language networks, social networks, and\ncitation networks. The algorithm is very efficient, which is able to learn the\nembedding of a network with millions of vertices and billions of edges in a few\nhours on a typical single machine. The source code of the LINE is available\nonline.\n

Affiliated Institutions

• University of Michigan US
• Microsoft Research Asia (China) CN
• Peking University CN

Related Publications