LINE: Large-scale Information Network Embedding
By Jian Tang, Meng Qu, Mingzhe Wang, Ming Zhang, Jun Yan, Qiaozhu Mei. 2015
5,660 citations recorded by the source corpus.
This paper studies the problem of embedding very large information networks into low-dimensional vector spaces, which is useful in many tasks such as visualization, node classification, and link prediction. Most existing graph embedding methods do not scale for real world information networks which usually contain millions of nodes. In this paper, we propose a novel network embedding method called the ``LINE,'' which is suitable for arbitrary types of information networks: undirected, directed, and/or weighted. The method optimizes a carefully designed objective function that preserves both the local and global network structures. An edge-sampling algorithm is proposed that addresses the limitation of the classical stochastic gradient descent and improves both the effectiveness and the efficiency of the inference. Empirical experiments prove the effectiveness of the LINE on a variety of real-world information networks, including language networks, social networks, and citation networks. The algorithm is very efficient, which is able to learn the embedding of a network with millions of vertices and billions of edges in a few hours on a typical single machine. The source code of the LINE is available online\footnote{\url{https://github.com/tangjianpku/LINE}}.
Subfields: Artificial Intelligence, Statistical and Nonlinear Physics, Representation & Self-Supervised Learning, Graph Learning
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Artificial Intelligence
- Yoshua Bengio
- Mohit Bansal
- Percy Liang
- Jianfeng Gao
- Quoc V. Le
- Sergey Levine
- Philip S. Yu
- Dacheng Tao
In Statistical and Nonlinear Physics
- William L. Hamilton
- Jure Leskovec
- Stephan Günnemann
- Chengqi Zhang
- Shirui Pan
- Huan Liu
- Peng Cui
- Xiao Wang
In Representation & Self-Supervised Learning
- William L. Hamilton
- Jure Leskovec
- Yoshua Bengio
- Stephan Günnemann
- Aleksandar Bojchevski
- Bryan Perozzi
- Jian Tang
- Philip S. Yu
In Graph Learning
- William L. Hamilton
- Jure Leskovec
- Stephan Günnemann
- Aleksandar Bojchevski
- Michael M. Bronstein
- Rex Ying
- Bryan Perozzi
- Jian Tang
Citations in the corpus
- Semi-Supervised Classification with Graph Convolutional Networks (2016, background): “LINE (Tang et al., 2015) and node2vec (Grover & Leskovec, 2016) extend DeepWalk with more sophisticated random walk or breadth-first search schemes.”
- Inductive Representation Learning on Large Graphs (2017, positive): “The majority of these approaches directly optimize the embeddings for each node using matrix-factorization-based objectives, and do not naturally generalize to unseen data, since they make predictions on nodes in a single, fixed graph [5, 11, 23, 28, 35, 36, 37, 39].”
- Improving Question Answering with External Knowledge (2019, methodology): “After constructing the knowledge graph, we apply the graph embedding framework proposed by Tang et al. (2015) to generate knowledge representations for all entities in the KB. Coherence between two entities coh ( e i , e j ) is modeled using cosine similarity between the vector representations of…”
- node2vec: Scalable Feature Learning for Networks (2016, methodology): “Recent attempts in this direction [24, 28] propose efficient algorithms but rely on a rigid notion of a network neighborhood, which results in these approaches being largely insensitive to connectivity patterns unique to networks.”
- Revisiting Semi-Supervised Learning with Graph Embeddings (2016, background): “Existing results show that graph embeddings are effective at classifying the nodes in a graph, such as user behavior prediction in a social network (Perozzi et al., 2014; Tang et al., 2015).”
- Predicting multicellular function through multi-layer tissue networks (2017, methodology): “However, approaches that neglect the existence of tissues or collapse tissue-specific protein interaction networks into a single network discard important informationabouttherichhierarchyofbiologicalsystems, giving OhmNet a 14.0% gain over Collapsed LINE, and a 8.5% gain over Collapsed Node2vec in AU”
- Geometric Deep Learning on Graphs and Manifolds Using Mixture Model CNNs (2016, methodology): “Finally, in the network analysis community, several works constructed graph embeddings [28, 38, 12, 17, 44] methods inspired by the Word2Vec technique [27].”
- Stochastic Training of Graph Convolutional Networks (2017, background): “…Welling, 2016; Berg et al., 2017) and knowledge graphs (Schlichtkrull et al., 2017), outperforming multi-layer perceptron (MLP) models that do not use the graph structure and graph embedding approaches (Perozzi et al., 2014; Tang et al., 2015; Grover & Leskovec, 2016) that do not use node features.”
- Variational Graph Auto-Encoders (2016, methodology): “In contrast to most existing models for unsupervised learning on graph-structured data and link prediction [5, 6, 7, 8], our model can naturally incorporate node features, which significantly improves predictive performance on a number of benchmark datasets.”
- On Sampling Strategies for Neural Network-based Collaborative Filtering (2017, methodology): “, LINE [29]) tasks, negative sampling is utilized.”
- Strategies for Pre-training Graph Neural Networks (2019, methodology): “In the first category are methods that use local random walk-based objectives (Grover & Leskovec, 2016; Perozzi et al., 2014; Tang et al., 2015) and methods that reconstruct a graph’s adjacency matrix, e.”
- SHINE: Signed Heterogeneous Information Network Embedding for Sentiment Link Prediction (2017, background): “Another promising approach called network embedding [8, 17, 23, 26], which automatically learns features of users in network, seems plausible to solve the task.”
- Attacking Graph-based Classification via Manipulating the Graph Structure (2019, methodology): “Moreover, our attacks can also transfer to other collective classification methods including random walk based methods [34], Loopy Belief Propagation based methods [23], and recent Joint Weight Learning and Propagation method [63] that learns edge weights, as well as graph neural network methods inc”
- Auto-GNN: Neural architecture search of graph neural networks (2019, methodology): “Graph neural networks (GNN) [1, 2] has been demonstrated that it could achieve superior performance in modeling graph-structured data, within various domains such as social media [3–6] and bioinformatics [7, 8].”
- Relational inductive biases, deep learning, and graph networks (2018, background): “cused on building generative models of graphs (Li et al., 2018; De Cao and Kipf, 2018; You et al., 2018; Bojchevski et al., 2018), and unsupervised learning of graph embeddings (Perozzi et al., 2014; Tang et al., 2015; Grover and Leskovec, 2016; Garca-Duran and Niepert, 2017). The works cited above ”
- Unsupervised Inductive Whole-Graph Embedding by Preserving Graph Proximity (2019, methodology): “In LINE1ST, the loss function is similar to the Skip-gram objective proposed in WORD2VEC.”
- Unsupervised Inductive Graph-Level Representation Learning via Graph-Graph Proximity (2019, methodology): “Classic works including NETMF [Qiu et al., 2018], LINE [Tang et al., 2015], DeepWalk [Perozzi et al., 2014], etc., which typically generate an embedding for each node in one graph.”
- Deep Graph Infomax (2018, methodology): “…unsupervised representation learning with graph-structured data rely on random walk-based objectives (Grover & Leskovec, 2016; Perozzi et al., 2014; Tang et al., 2015; Hamilton et al., 2017a), sometimes further simplified to reconstruct adjacency information (Kipf & Welling, 2016b; Duran & Niepert,…”
- Representation Learning on Graphs with Jumping Knowledge Networks (2018, neutral): “2017; Grover & Leskovec, 2016; Tang et al., 2015).”