A high order proximity measure for linear network embedding

Abstract

Graph representationion learning (network embedding) is at the heart of network analytics techniques to reveal and examine the complex dependencies among nodes. Owing its importance, many computational methods have been proposed to solve a large volume of learning tasks on graphs, such as node classification, link prediction and clustering. Among various network embedding techniques, linear Matrix Factorization-based (MF) network embedding approaches have demonstrated to be very effective and efficient as they can be stated as singular value decomposition (SVD) problem, which can be efficiently solved by off-the-shelf eigen-solvers, such as Lanczos method. Despite the effectiveness of these linear methods, they rely on high order proximity measures, i.e., random walk restarts (RWR) and/or Katz, which have their own limitations, such as degree biasness, hyper-parameter dependency. In this paper, to alleviate the RWR and Katz depended high proximity usage in the linear embedding methods, we propose an algorithm that uses label propagation and shift-and-invert approach to resort RWR and Katz related problems. Testing our methods on realnetworks for link prediction task, we show that our algorithm drastically improves link prediction performance of network embedding comparing against an embedding approach that uses RWR and Katz high order proximity measures.