Network Embedding as Matrix Factorization: Unifying DeepWalk, LINE, PTE, and node2vec

By Jiezhong Qiu, Yuxiao Dong, Hao Ma, Jian Li, Kuansan Wang, Jie Tang. 2017

987 citations recorded by the source corpus.

Since the invention of word2vec, the skip-gram model has significantly advanced the research of network embedding, such as the recent emergence of the DeepWalk, LINE, PTE, and node2vec approaches. In this work, we show that all of the aforementioned models with negative sampling can be unified into the matrix factorization framework with closed forms. Our analysis and proofs reveal that: (1) DeepWalk empirically produces a low-rank transformation of a network's normalized Laplacian matrix; (2) LINE, in theory, is a special case of DeepWalk when the size of vertices' context is set to one; (3) As an extension of LINE, PTE can be viewed as the joint factorization of multiple networks» Laplacians; (4) node2vec is factorizing a matrix related to the stationary distribution and transition probability tensor of a 2nd-order random walk. We further provide the theoretical connections between skip-gram based network embedding algorithms and the theory of graph Laplacian. Finally, we present the NetMF method as well as its approximation algorithm for computing network embedding. Our method offers significant improvements over DeepWalk and LINE for conventional network mining tasks. This work lays the theoretical foundation for skip-gram based network embedding methods, leading to a better understanding of latent network representation learning.

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

In Statistical and Nonlinear Physics

In Representation & Self-Supervised Learning

In Graph Learning

Citations in the corpus

Unsupervised Inductive Whole-Graph Embedding by Preserving Graph Proximity (2019, methodology): “Many interesting insights and theoretical analysis have been discovered and presented, but since this work focuses on neural network based methods, the reader is referred to (Qiu et al., 2018) for a complete discussion.”
Unsupervised Inductive Graph-Level Representation Learning via Graph-Graph Proximity (2019, background): “There has been a rich body of work [Belkin and Niyogi, 2003; Tang et al., 2015; Qiu et al., 2018] on node-level embeddings that turn each node in a graph into a vector preserving node-node proximity (similarity/distance).”
Predict then Propagate: Graph Neural Networks meet Personalized PageRank (2018, background): “without leveraging node classes (Perozzi et al., 2014; Tang et al., 2015; Nandanwar & Murty, 2016; Grover & Leskovec, 2016; Qiu et al., 2018).”
Adversarially Regularized Graph Autoencoder (2018, background): “Recently it has been shown that many probabilistic algorithms are equivalent to matrix factorization approaches [Qiu et al., 2017].”
Self-Supervised Learning: Generative or Contrastive (2020, methodology): “In general, existing network embedding approaches are broadly categorized as (1) factorization-based approaches such as NetMF [110], [111], GraRep [18], HOPE [102], (2) shallow embedding approaches such as DeepWalk [106], LINE [134], HARP [21], and (3) neural network approaches [19], [86].”
Semi-supervised Learning on Graphs with Generative Adversarial Nets (2018, background): “To this end, GraphSGAN first uses network embedding methods (e.g., DeepWalk [23], LINE [29], or NetMF [24]) to learn latent distributed representation qi for each node, and then concatenates the latent distribution qi with the original feature vectorwi , i.e., xi = (wi , qi ).”
Learning Graph Embedding With Adversarial Training Methods (2019, positive): “It has been recently shown that many probabilistic algorithms including Deep-Walk [10], LINE [12], node2vec [11], are equivalent to matrix factorization approaches [17], and Qiu et al. propose a uni-ﬁed matrix factorization approach NetMF [17] for graph embedding.”
Adversarial Attacks on Node Embeddings via Graph Poisoning (2018, methodology): “Specifically, we use the results from Qiu et al. (2018) to sidestep the stochasticity induced by sampling random walks.”
Predicting Dynamic Embedding Trajectory in Temporal Interaction Networks (2019, background): “Accurate real-time recommendation of items and predicting change in the state of users are fundamental problems in these domains [5, 6, 22, 30, 36, 40, 43].”
Machine Learning on Graphs: A Model and Comprehensive Taxonomy (2020, methodology): “This relationship is discussed in depth by [94], who propose a general matrix factorization framework, NetMF, which uses the same underlying graph proximity information as DeepWalk, LINE, and node2vec.”
GPT-GNN: Generative Pre-Training of Graph Neural Networks (2020, methodology): “embedding,which directly parameterizes the node embedding vectors and optimizes them by preserving some similarity measures, such as the network proximity [33] or statistics derived from random walks [6, 11, 26]. However, the embeddings learned in this way cannot be used to initialize other models f”
DeepInf: Social Influence Prediction with Deep Learning (2018, methodology): “Examples include DeepWalk [36], LINE [41], node2vec [20], metap-ath2vec [13], NetMF [37], etc.”
Heterogeneous Graph Neural Network (2019, methodology): “Besides those methods, many other approaches have been proposed [1, 18, 21, 28, 32], such as NetMF [21] that learns node embedding via matrix factorization and NetRA [32] that uses adversarially regularized autoencoders to learn node embeddings, and so on.”
AliGraph: A Comprehensive Graph Neural Network Platform (2019, methodology): “NetMF [40] is a unified matrix factorization framework for theoretically understanding and improving DeepWalk and LINE.”
Knowledge Graph Completion: A Review (2020, methodology): “Based on this understanding, NetMF [82] gave a general framework for decomposing closed matrices, which can achieve consistent performance improvement compared with models such as DeepWalk and LINE.”
Multi-scale Attributed Node Embedding (2019, methodology): “Related network embedding methods (Perozzi et al., 2014; Grover & Leskovec, 2016; Tang et al., 2015; Qiu et al., 2018) also implicitly factorize PMI matrices based on the probability of encountering each (context) node on a random walk from each starting node (Qiu et al., 2018).”
Deep Representation Learning for Social Network Analysis (2019, background): “In addition, it has been shown that there exists a close relationship between skipgram models and matrix factorization algorithms (Levy and Goldberg, 2014; Qiu et al., 2018).”