A high order proximity measure for linear network embedding


Creative Commons License

COŞKUN M.

Niğde Ömer Halisdemir Üniversitesi Mühendislik Bilimleri Dergisi, cilt.11, sa.3, ss.477-483, 2022 (Hakemli Dergi) identifier

  • Yayın Türü: Makale / Tam Makale
  • Cilt numarası: 11 Sayı: 3
  • Basım Tarihi: 2022
  • Doi Numarası: 10.28948/ngumuh.957488
  • Dergi Adı: Niğde Ömer Halisdemir Üniversitesi Mühendislik Bilimleri Dergisi
  • Derginin Tarandığı İndeksler: Directory of Open Access Journals, TR DİZİN (ULAKBİM)
  • Sayfa Sayıları: ss.477-483
  • Abdullah Gül Üniversitesi Adresli: Evet

Özet

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.