A high order proximity measure for linear network embedding

Creative Commons License


Niğde Ömer Halisdemir Üniversitesi Mühendislik Bilimleri Dergisi, vol.11, no.3, pp.477-483, 2022 (Peer-Reviewed Journal) identifier

  • Publication Type: Article / Article
  • Volume: 11 Issue: 3
  • Publication Date: 2022
  • Doi Number: 10.28948/ngumuh.957488
  • Journal Name: Niğde Ömer Halisdemir Üniversitesi Mühendislik Bilimleri Dergisi
  • Journal Indexes: Directory of Open Access Journals, TR DİZİN (ULAKBİM)
  • Page Numbers: pp.477-483
  • Abdullah Gül University Affiliated: Yes


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 real-networks 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.