Since the invention of word2vec, the skip-gram model has significantly advanced the research of network embedding, such as the recent emergence of 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 the normalized Laplacian matrix of a network; (2) LINE, in theory, is a special case of DeepWalk when the size of vertex context is set to one; (3) As an extension to LINE, PTE can be viewed as the joint factorization of multiple Laplacian matrices; (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 (up to 38% relatively) in several 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 representations.

本研究提出了NetMF方法，通过矩阵分解的方式实现skip-gram网络嵌入方法的统一框架，并将各种经典的skip-gram方法（DeepWalk、LINE、PTE和node2vec）统一到该框架下。此方法是目前常规网络挖掘任务中优于DeepWalk和LINE的最新算法。

网络嵌入作为矩阵分解：DeepWalk、LINE、PTE和node2vec的统一