Network Embedding For Link Prediction in Bipartite Networks

Abstract

Many social networks have a bipartite nature. Link prediction in social networks has been the focus of interest for many researchers recently. Network embedding, which maps each node in the network to a low-dimensional feature vector is used to solve many problems. The aim of this study is to investigate how network embedding enhance the link prediction performance in bipartite networks. A network embedding and a supervised learning based link prediction model has been presented for bipartite networks. The input of the supervised learning model is learned embedding vectors of node pairs obtained from network embedding method. The target feature of prediction is a binary label indicating the existence or absence of a link between these node pairs. Ensemble learning algorithms have been applied for supervised link prediction. The experiments performed on two bipartite social networks built from public datasets led promising results with 0.939 and 0.974 AUC values. Random Forest models trained with embedding vectors obtained from BiNE method achieved the highest performances.

Keywords

• Network embedding
• node2vec
• BiNE
• Link prediction
• Bipartite network
• Ensemble learning

İki Parçalı Ağlarda Bağlantı Tahmini için Çizge Gömme

Öz

Birçok sosyal ağ doğası gereği iki parçalı yapıdadır. Sosyal ağlarda bağlantı tahmini, son zamanlarda birçok araştırmacının ilgi odağı olmuştur. Ağdaki her düğümü düşük boyutlu bir özellik vektörüne eşleyen ağ gömme islemi birçok problemin çözümü için kullanılmaktadır. Bu çalışma, çizge (ağ) gömme yöntemlerinin iki parçalı ağlarda makine öğrenimi tabanlı bağlantı tahmin modelinin performansını nasıl iyileştirdiğini incelemeyi amaçlamaktadır. Makine öğrenme modelinin girdisi, düğüm çiftlerinin çizge gömme yönteminden elde edilen öğrenilmiş gömme vektörleridir. Tahminleme işleminin hedef özniteliği, bu düğüm çiftleri arasında bir bağlantının varlığını veya yokluğunu gösteren ikili bir etikettir. Gözetimli bağlantı tahmini için topluluk öğrenme algoritmaları uygulanmıştır. Herkese açık veri kümelerinden oluşturulan iki parçalı iki sosyal ağ üzerinde gerçekleştirilen deneyler, 0.939 ve 0.974 AUC değerleriyle umut verici sonuçlara ulaşmıştır. BiNE yönteminden elde edilen gömme vektörleri ile eğitilen Random Forest modelleri en yüksek performansları elde etmiştir.

Anahtar Kelimeler

• Çizge gömme
• node2vec
• BiNE
• Bağlantı tahmini
• İki parçalı ağ
• Topluluk öğrenmesi

Kaynakça

1. Breiman, L. (2001). 2001 4_Method_Random_Forest. Machine Learning.
2. Bütün, E., Kaya, M., & Alhajj, R. (2018). Extension of neighbor-based link prediction methods for directed, weighted and temporal social networks. Information Sciences, 463–464, 152–165. https://doi.org/10.1016/j.ins.2018.06.051
3. Chen, T., & Guestrin, C. (2016). XGBoost: A scalable tree boosting system. Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. https://doi.org/10.1145/2939672.2939785
4. Erdem, E., & Bozkurt, F. (2021). A comparison of various supervised machine learning techniques for prostate cancer prediction. Avrupa Bilim ve Teknoloji Dergisi, 21, 610–620.
5. Fawcett, T. (2006). An introduction to ROC analysis. Pattern recognition letters, 27(8), 861-874.
6. Gao, M., He, X., Chen, L., Liu, T., Zhang, J., & Zhou, A. (2018). Learning Vertex Representations for Bipartite Networks. 1–14.
7. Goodreads. (2021). https://www.goodreads.com/
8. Gori, M., & Pucci, A. (2007). ItemRank: A random-walk based scoring algorithm for recommender engines. IJCAI International Joint Conference on Artificial Intelligence, 2766–2771.

9. Goyal, P., & Ferrara, E. (2018). Knowle dge-Base d Systems Graph emb e dding techniques , applications , and performance : A survey. Knowledge-Based Systems, 151, 78–94. https://doi.org/10.1016/j.knosys.2018.03.022
10. Grover, A., & Leskovec, J. (2016). node2vec. https://doi.org/10.1145/2939672.2939754
11. Hasan, M. Al, & Zaki, M. J. (2011). A Survey of Link Prediction in Social Networks. In Social Network Data Analytics. https://doi.org/10.1007/978-1-4419-8462-3_9
12. Kart, O., Ulucay, O., Bingol, B., & Isik, Z. (2020). A machine learning-based recommendation model for bipartite networks. Physica A: Statistical Mechanics and Its Applications. https://doi.org/10.1016/j.physa.2020.124287
13. Kelleher, J., Mac Namee, B., & D’arcy, A. (2015). Fundamentals of machine learning for predictive data analytics: algorithms, worked examples, and case studies. MIT Press.
14. Li, Z., Fang, X., & Sheng, O. R. L. (2017). A survey of link recommendation for social networks: Methods, theoretical foundations, and future research directions. ACM Transactions on Management Information Systems. https://doi.org/10.1145/3131782
15. Lü, L., & Zhou, T. (2011). Link prediction in complex networks: A survey. Physica A: Statistical Mechanics and Its Applications, 390(6), 1150–1170. https://doi.org/10.1016/j.physa.2010.11.027
16. MovieLens. (2021). https://grouplens.org/datasets/movielens/
17. Ou, M., Cui, P., Pei, J., Zhang, Z., & Zhu, W. (2016). Asymmetric transitivity preserving graph embedding. Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. https://doi.org/10.1145/2939672.2939751
18. Peng, W., Baowen, X. U., Yurong, W. U., & Xiaoyu, Z. (2015). Link Prediction in Social Networks : the State-of-the-Art arXiv : 1411 . 5118v2 [ cs . SI ] 8 Dec 2014. 58(January), 1–38. https://doi.org/0.1007/s11432-014-5237-y
19. Perozzi, B., Al-Rfou, R., & Skiena, S. (2014). DeepWalk: Online learning of social representations. Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. https://doi.org/10.1145/2623330.2623732
20. Wang, D., Cui, P., & Zhu, W. (2016). Structural deep network embedding. Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. https://doi.org/10.1145/2939672.2939753