LINE

Published 18 May 2015Open access

Jian Tang, Meng Qu, Mingzhe Wang, Ming Zhang, Jun Yan, Qiaozhu Mei

Citations4,592

TL;DR

A novel network embedding method called the ``LINE,'' which is suitable for arbitrary types of information networks: undirected, directed, and/or weighted, and optimizes a carefully designed objective function that preserves both the local and global network structures.

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

Keywords

Computer SciencePhysics and Astronomy

arXiv (Cornell University)Distributed Representations of Words and Phrases and their Compositionality

18,086 Citations2013Tomáš Mikolov, Ilya Sutskever +3 more

This paper presents a simple method for finding phrases in text, and shows that learning good vector representations for millions of phrases is possible and describes a simple alternative to the hierarchical softmax called negative sampling.

View PDF

ScienceNonlinear Dimensionality Reduction by Locally Linear Embedding

15,035 Citations2000Sam T. Roweis, Lawrence K. Saul

Locally linear embedding (LLE) is introduced, an unsupervised learning algorithm that computes low-dimensional, neighborhood-preserving embeddings of high-dimensional inputs that learns the global structure of nonlinear manifolds.

ScienceA Global Geometric Framework for Nonlinear Dimensionality Reduction

13,740 Citations2000Joshua B. Tenenbaum, Vin de Silva +1 more

An approach to solving dimensionality reduction problems that uses easily measured local metric information to learn the underlying global geometry of a data set and efficiently computes a globally optimal solution, and is guaranteed to converge asymptotically to the true structure.

Cambridge University Press eBooksIntroduction to Information Retrieval

10,873 Citations2008Christopher D. Manning, Prabhakar Raghavan +1 more

This textbook teaches classical and web information retrieval, including web search and the related areas of text classification and text clustering from basic concepts, making it perfect for introductory courses in information retrieval for advanced undergraduates and graduate students in computer science.

DeepWalk

8,526 Citations2014Bryan Perozzi, Rami Al-Rfou +1 more

DeepWalk is an online learning algorithm which builds useful incremental results, and is trivially parallelizable, which make it suitable for a broad class of real world applications such as network classification, and anomaly detection.

View PDF

arXiv (Cornell University)Distributed Representations of Sentences and Documents

5,128 Citations2014Quoc V. Le, Tomáš Mikolov

Paragraph Vector is an unsupervised algorithm that learns fixed-length feature representations from variable-length pieces of texts, such as sentences, paragraphs, and documents, and its construction gives the algorithm the potential to overcome the weaknesses of bag-of-words models.

View PDF

The MIT Press eBooksLaplacian Eigenmaps and Spectral Techniques for Embedding and Clustering

4,535 Citations2002Mikhail Belkin, Partha Niyogi

The algorithm provides a computationally efficient approach to nonlinear dimensionality reduction that has locality preserving properties and a natural connection to clustering.

ArnetMiner

2,084 Citations2008Jie Tang, Jing Zhang +4 more

The architecture and main features of the ArnetMiner system, which aims at extracting and mining academic social networks, are described and a unified modeling approach to simultaneously model topical aspects of papers, authors, and publication venues is proposed.

Neural Information Processing SystemsNeural Word Embedding as Implicit Matrix Factorization

1,592 Citations2014Omer Levy, Yoav Goldberg

It is shown that using a sparse Shifted Positive PMI word-context matrix to represent words improves results on two word similarity tasks and one of two analogy tasks, and conjecture that this stems from the weighted nature of SGNS's factorization.

Neural Information Processing SystemsHogwild: A Lock-Free Approach to Parallelizing Stochastic Gradient Descent

1,101 Citations2011Benjamin Recht, Christopher Ré +2 more

This work aims to show using novel theoretical analysis, algorithms, and implementation that SGD can be implemented without any locking, and presents an update scheme called HOGWILD! which allows processors access to shared memory with the possibility of overwriting each other's work.