Network Embedding as Matrix Factorization Article Swipe
YOU?
·
· 2018
· Open Access
·
· DOI: https://doi.org/10.1145/3159652.3159706
· OA: W4291474301
Since the invention of word2vec, the skip-gram model has significantly\nadvanced the research of network embedding, such as the recent emergence of the\nDeepWalk, LINE, PTE, and node2vec approaches. In this work, we show that all of\nthe aforementioned models with negative sampling can be unified into the matrix\nfactorization framework with closed forms. Our analysis and proofs reveal that:\n(1) DeepWalk empirically produces a low-rank transformation of a network's\nnormalized Laplacian matrix; (2) LINE, in theory, is a special case of DeepWalk\nwhen the size of vertices' context is set to one; (3) As an extension of LINE,\nPTE can be viewed as the joint factorization of multiple networks' Laplacians;\n(4) node2vec is factorizing a matrix related to the stationary distribution and\ntransition probability tensor of a 2nd-order random walk. We further provide\nthe theoretical connections between skip-gram based network embedding\nalgorithms and the theory of graph Laplacian. Finally, we present the NetMF\nmethod as well as its approximation algorithm for computing network embedding.\nOur method offers significant improvements over DeepWalk and LINE for\nconventional network mining tasks. This work lays the theoretical foundation\nfor skip-gram based network embedding methods, leading to a better\nunderstanding of latent network representation learning.\n
