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

Keywords

• Graph representation learning
• Node embedding
• Linear embedding

Ağ gömülümü için yüksek boyutlu yakınsaklık ölçüsü

Öz

Ağ gömülümü öğrenme problemi bir çok ağ analizi gerektiren problemin ifade ve çözümlenmesi için çok büyük önem arz etmektedir. Bu bağlamda, ağ içerisinde bulunan düğümlerin birbirleri ile olan gizli ilişkilerini açığa çıkarmak için, son yıllarda ağ gömülümü öğrenme problemi çokça çalışılmaktadır. Bu gizli ilişkinin açığa çıkarılması, bağlantı tahminleme, öbekleme ve sınıflandırma gibi öğreme problemlerinin daha iyi çözümlenmesinde kullanılmaktadır. Ağ gömülümünü öğrenmek için, farklı yaklaşım ve algoritmalar geliştirilmiş olsada, matris ayrışımı bazlı algoritmalar hızlı olmasından dolayı araştırmacılar tarafından büyük ilgi görmekteler. Matris ayraşım bazlı ağ gömülümü öğrenmede genel anlamı ile yüksek dereceli yakınlık ölçüleri kullanılmaktadır, örneğin random walk with restart (RWR) ve Katz ölçüleri. Ancak, bu ölçülerle yapılan ağ benzerlik ölçüleri matris ayrışımında sıfıra karşılık gelen eigenvectors (özvektörler) üretebilmektedir. Bu ise öğrenilen ağ gömülümün yanlış olmasına sebeb olmaktadır. Bu prolemi aşmak için, bu makalede shift-and-invert (kaydır ve tersini al) yaklaşımına dayanarak bir yaklaşım önerdik. Bağlantı tahimini baz problemi alarak, geliştirdiğimiz algoritmayı üç gerçek veride kullanık ve sonuçların var olan matris ayrışımlı algoritmasını bütün metrik değerlendirmelerinde var olan algoritmanın performansını ciddi miktarda artırdığını gözlemledik.

Anahtar Kelimeler

• Ağ gömülümü
• Düğüm gömülümü
• Lineer ağ gömülümü

Kaynakça

1. X. Yue, Z. Wang, J. Huang, S. Parthasarathy, S. Moosavinasab, Y. Huang, S. M. Lin, W. Zhang, P. Zhang and H. Sun, Graph embedding on biomedical networks: methods, applications and evaluations. Bioinformatics, 36(4), 1241–1251, 2020. https://doi. org/10.1093/bioinformatics/btz718
2. B. Perozzi, R. Al-Rfou and S. Skiena, Deepwalk: online learning of social representations. In The 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 701–710. ACM, New York, NY, 2014.
3. J. Tang, M. Qu, M. Wang, M. Zhang, J. Yan and Q. Mei, Line: large-scale information network embedding. In: Proceedings of the 24th International Conference on World Wide Web, pp. 1067–1077, ACM, Florence, Italy, 2015.
4. T. N. Kipf and M. Welling, Semi-supervised classification with graph convolutional networks. 4th International Conference on Learning Representations (ICLR), 2016.
5. P. Veličković, W. Fedus, W. L. Hamilton, P. Liò, Y. Bengio and R. D. Hjelm, Deep graph infomax. 7th International Conference on Learning Representations (ICLR), 2019
6. M. Ou, P. Cui, J. Pei, Z. Zhang and W. Zhu, Symmetric transitivity preserving graph embedding. In: Proceedings of the 22nd ACMSIGKDD International Conference on Knowledge Discovery and DataMining, pp. 1105–1114, ACM, San Francisco, CA, 2016.
7. Y. Saad, Iterative Methods for Sparse Linear Systems. PWS Publishing Co., Boston, 1996.
8. M. Balasubramanian, et al., The isomap algorithm and topological stability. Science 295.5552, pp. 7–7, 2002. doi: 10.1126/science.295.5552.7a

9. L. K. Saul and S. T. Roweis, An introduction to locally linear embedding. In:unpublished. Available at: http://www.cs.toronto.edu/roweis/lle/publications, 2000. Accessed 27 May 2022.
10. M. Belkin and P. Niyogi, Laplacian eigenmaps for dimensionality reduction anddata representation. Neural Computation,15(6), 1373–1396, 2003.
11. A. Grover and J. Leskovec, node2vec: Scalable feature learning for networks. In:Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 855–864, ACM, San Francisco, CA, 2016
12. L. FR. Ribeiro, P. HP. Saverese and D. R. Figueiredo, struc2vec: Learningnode representations from structural identity. In:Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 385–394, 2017.
13. M. Coskun and M. Koyutürk, Link prediction in large networks by comparing the global view of nodes in the network. In 2015 IEEE International Conference on Data Mining Workshop (ICDMW), pages 485–492. IEEE, NJ, USA, 2015.
14. Z. Stanfield, M. Coskun and M. Koyuturk, Drug response prediction problem as link prediction problem. Scientific Reports, 7, 40321, 2017. https://doi. org/10.1038/srep40321.
15. X. Huang, J. Li and X. Hu, Label informed attributed network embedding. In Proceedings of the Tenth ACM International Conference on Web Search and Data Mining. 731–739, 2017.
16. L. FR. Ribeiro, P. HP. Saverese and D. R. Figueiredo, struc2vec: Learningnode representations from structural identity. In:Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. pp. 385–394, 2017.
17. M. Coskun and M. Koyutürk, Node similarity-based graph convolution for link prediction in biological networks. Bioinformatics, 37(23), 4501-4508, 2021. https://doi.org/10.1093/bioinformatics/btab464
18. J. Klicpera, A. Bojchevski and S. Günnemann, Predict then propagate: Graph neural networks meet personalized pagerank. International Conference on Learning Representations, 2018.
19. J. Gilmer, et al., Neural message passing for quantum chemistry. In Proceedings of the 34th International Conference on Machine Learning, Volume 70, pages 1263–1272. JMLR., 2017.
20. Q. Li, et al., Deeper insights into graph convolutional networks for semi-supervised learning. In Thirty-Second AAAI Conference on Artificial Intelligence, April 29, 2018
21. D. Liben-Nowell and J. Kleinberg, The link-prediction problem for social networks. Journal of the American Society for Information Science and Technology, 58(7), 1019–1031, 2007. https://doi.org/10.1002/ asi.20591