[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content

Advertisement

Springer Nature Link
Log in

Deep non-negative matrix factorization with edge generator for link prediction in complex networks

  • Published:
Applied Intelligence Aims and scope Submit manuscript

Abstract

Link prediction aims to infer missing links or predict future links based on observed topology or attribute information in the network. Many link prediction methods based on non-negative matrix factorization (NMF) have been proposed to solve prediction problem. However, due to the sparsity of real networks, the observed topology information is probably very limited, which affects the performance of existing link prediction methods. In this paper, we utilize Deep Non-negative Matrix Factorization (DNMF) models with Edge Generator to address the network sparsity problem and propose link prediction methods EG-DNMF and EG-FDNMF. Under the framework of DNMF, several representative potential edges are incorporated so as to reconstruct the original network for link prediction. Specifically, in order to explore the potential structural features of the network in a more fine-grained manner, we first divide the original network into three sub-networks. Then, the DNMF models are employed to mine complex and nonlinear interaction relationships in sub-networks, thereby guiding the network reconstruction process. Finally, the NMF algorithm is applied on the reconstructed original network for link prediction. Experiment results on 12 different networks show that our methods have comparable performance with respect to 13 representative link prediction methods which include 6 NMF/DNMF-based approaches and 7 heuristic-based approaches. In addition, experiments also show that the sub-networks after partitioning are beneficial for capturing the underlying features of the network. Codes are available at https://github.com/yabingyao/EGDNMF4LinkPrediction

Graphical abstract

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Algorithm 1
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9
Fig. 10

Similar content being viewed by others

Explore related subjects

Discover the latest articles, news and stories from top researchers in related subjects.

Data availability and access

The dataset analyzed during the experiments conducted in this paper can be obtained at the following URL: http://konect.uni-koblenz.de/ and http://networkrepository.com/networks.php.

References

  1. Wahid-Ul-Ashraf A, Budka M, Musial K (2019) How to predict social relationships-physics-inspired approach to link prediction. Physica A 523:1110–1129

    Google Scholar 

  2. Yao Y, Cheng T, Li X, He Y, Yang F, Li T, Liu Z, Xu Z (2023) Link prediction based on the mutual information with high-order clustering structure of nodes in complex networks. Physica A 610:128428

    MathSciNet  Google Scholar 

  3. Zhou T (2021) Progresses and challenges in link prediction. Iscience 24(11):103217

    Google Scholar 

  4. Lü L, Zhou T (2011) Link prediction in complex networks: A survey. Physica A 390(6):1150–1170

    Google Scholar 

  5. Li S, Song X, Lu H, Zeng L, Shi M, Liu F (2020) Friend recommendation for cross marketing in online brand community based on intelligent attention allocation link prediction algorithm. Expert Syst Appl 139:112839

    Google Scholar 

  6. Su Z, Zheng X, Ai J, Shen Y, Zhang X (2020) Link prediction in recommender systems based on vector similarity. Physica A 560:125154

    Google Scholar 

  7. Liu G (2022) An ecommerce recommendation algorithm based on link prediction. Alex Eng J 61(1):905–910

    Google Scholar 

  8. Nasiri E, Berahmand K, Rostami M, Dabiri M (2021) A novel link prediction algorithm for protein-protein interaction networks by attributed graph embedding. Comput Biol Med 137:104772

    Google Scholar 

  9. Li Z, Zhu S, Shao B, Zeng X, Wang T, Liu T-Y (2023) Dsn-ddi: an accurate and generalized framework for drug–drug interaction prediction by dual-view representation learning. Briefings in Bioinformatics 24(1)

  10. Kumar A, Singh SS, Singh K, Biswas B (2020) Link prediction techniques, applications, and performance: A survey. Physica A 553:124289

    MathSciNet  Google Scholar 

  11. Chen G, Wang H, Fang Y, Jiang L (2022) Link prediction by deep non-negative matrix factorization. Expert Syst Appl 188:115991

    Google Scholar 

  12. Daud NN, Ab Hamid SH, Saadoon M, Sahran F, Anuar NB (2020) Applications of link prediction in social networks: A review. J Netw Comput Appl 166:102716

    Google Scholar 

  13. Newman ME (2001) Clustering and preferential attachment in growing networks. Phys Rev E 64(2):025102

    Google Scholar 

  14. Adamic LA, Adar E (2003) Friends and neighbors on the web. Social networks 25(3):211–230

    Google Scholar 

  15. Liu S, Ji X, Liu C, Bai Y (2017) Extended resource allocation index for link prediction of complex network. Physica A 479:174–183

    MathSciNet  Google Scholar 

  16. Vural H, Kaya M (2018) Prediction of new potential associations between lncrnas and environmental factors based on katz measure. Comput Biol Med 102:120–125

    Google Scholar 

  17. Liu W, Lü L (2010) Link prediction based on local random walk. Europhys Lett 89(5):58007

    Google Scholar 

  18. Zhou Y, Wu C, Tan L (2021) Biased random walk with restart for link prediction with graph embedding method. Physica A 570:125783

    Google Scholar 

  19. Aziz F, Gul H, Muhammad I, Uddin I (2020) Link prediction using node information on local paths. Physica A 557:124980

    Google Scholar 

  20. Rafiee S, Salavati C, Abdollahpouri A (2020) Cndp: Link prediction based on common neighbors degree penalization. Physica A 539:122950

    Google Scholar 

  21. Clauset A, Moore C, Newman ME (2008) Hierarchical structure and the prediction of missing links in networks. Nature 453(7191):98–101

    Google Scholar 

  22. Guimerà R, Sales-Pardo M (2009) Missing and spurious interactions and the reconstruction of complex networks. Proc Natl Acad Sci 106(52):22073–22078

    Google Scholar 

  23. Zhou J, Liu L, Wei W, Fan J (2022) Network representation learning: from preprocessing, feature extraction to node embedding. ACM Computing Surveys (CSUR) 55(2):1–35

    Google Scholar 

  24. Perozzi B, Al-Rfou R, Skiena S (2014) Deepwalk: Online learning of social representations. In: Proceedings of the 20th ACM SIGKDD international conference on knowledge discovery and data mining, pp 701–710

  25. Grover A, Leskovec J (2016) node2vec: Scalable feature learning for networks. In: Proceedings of the 22nd ACM SIGKDD International conference on knowledge discovery and data mining, pp 855–864

  26. Lei K, Qin M, Bai B, Zhang G, Yang M (2019) Gcn-gan: A non-linear temporal link prediction model for weighted dynamic networks. In: IEEE INFOCOM 2019-IEEE conference on computer communications, IEEE pp 388–396

  27. Hao Y, Cao X, Fang Y, Xie X, Wang S (2021) Inductive link prediction for nodes having only attribute information. In: Proceedings of the twenty-ninth international conference on international joint conferences on artificial intelligence, pp 1209–1215

  28. Samy AE, Kefato TZ, Girdzijauskas S (2023) Graph2feat: Inductive link prediction via knowledge distillation. Companion Proceedings of the ACM Web Conference 2023:805–812

    Google Scholar 

  29. Wu E, Cui H, Chen Z (2022) Relpnet: Relation-based link prediction neural network. In: Proceedings of the 31st ACM International conference on information & knowledge management, pp 2138–2147

  30. Guo Z, Shiao W, Zhang S, Liu Y, Chawla NV, Shah N, Zhao T (2023) Linkless link prediction via relational distillation. In: International conference on machine learning, PMLR pp 12012–12033

  31. Zhao Z, Gou Z, Du Y, Ma J, Li T, Zhang R (2022) A novel link prediction algorithm based on inductive matrix completion. Expert Syst Appl 188:116033

    Google Scholar 

  32. Wang W, Cai F, Jiao P, Pan L (2016) A perturbation-based framework for link prediction via non-negative matrix factorization. Sci Rep 6(1):1–11

    Google Scholar 

  33. Chen G, Xu C, Wang J, Feng J, Feng J (2020) Robust non-negative matrix factorization for link prediction in complex networks using manifold regularization and sparse learning. Physica A 539:122882

    MathSciNet  Google Scholar 

  34. Lei K, Qin M, Bai B, Zhang G (2018) Adaptive multiple non-negative matrix factorization for temporal link prediction in dynamic networks. In: Proceedings of the 2018 workshop on network meets AI & ML, pp 28–34

  35. Zhao Y, Wang H, Pei J (2019) Deep non-negative matrix factorization architecture based on underlying basis images learning. IEEE Trans Pattern Anal Mach Intell 43(6):1897–1913

    Google Scholar 

  36. Chen W-S, Zeng Q, Pan B (2022) A survey of deep nonnegative matrix factorization. Neurocomputing 491:305–320

    Google Scholar 

  37. Ye F, Chen C, Zheng Z (2018) Deep autoencoder-like nonnegative matrix factorization for community detection. In: Proceedings of the 27th ACM international conference on information and knowledge management, pp 1393–1402

  38. Zhang W, Zhang X, Wang H, Chen D (2019) A deep variational matrix factorization method for recommendation on large scale sparse dataset. Neurocomputing 334:206–218

    Google Scholar 

  39. He X, Liao L, Zhang H, Nie L, Hu X, Chua T-S (2017) Neural collaborative filtering. In: Proceedings of the 26th international conference on World Wide Web, pp 173–182

  40. Luo L, Xie H, Rao Y, Wang FL (2019) Personalized recommendation by matrix co-factorization with tags and time information. expert systems with applications 119:311–321

  41. Bhowmick AK, Meneni K, Danisch M, Guillaume J-L, Mitra B (2020) Louvainne: Hierarchical louvain method for high quality and scalable network embedding. In: Proceedings of the 13th international conference on web search and data mining, pp 43–51

  42. Zhao S, Du Z, Chen J, Zhang Y, Tang J, Yu P (2021) Hierarchical representation learning for attributed networks. IEEE Transactions on Knowledge and Data Engineering

  43. Wang Y, Zhao Y (2023) Arbitrary spatial trajectory reconstruction based on a single inertial sensor. IEEE Sensors Journal

  44. Zhu Z, Huang G, Deng J, Ye Y, Huang J, Chen X, Zhu J, Yang T, Du D, Lu J et al (2022) Webface260m: A benchmark for million-scale deep face recognition. IEEE Trans Pattern Anal Mach Intell 45(2):2627–2644

    Google Scholar 

  45. Yuliansyah H, Othman Z, Bakar AA (2023) A new link prediction method to alleviate the cold-start problem based on extending common neighbor and degree centrality. Physica A 616:128546

    Google Scholar 

  46. Stanley N, Bonacci T, Kwitt R, Niethammer M, Mucha PJ (2019) Stochastic block models with multiple continuous attributes. Applied Netw Sci 4(1):1–22

    Google Scholar 

  47. Kuang J, Scoglio C (2021) Layer reconstruction and missing link prediction of a multilayer network with maximum a posteriori estimation. Phys Rev E 104(2):024301

    MathSciNet  Google Scholar 

  48. Zhao H, Du L, Buntine W (2017) Leveraging node attributes for incomplete relational data. In: International Conference on Machine Learning, PMLR pp 4072–4081

  49. Makarov I, Kiselev D, Nikitinsky N, Subelj L (2021) Survey on graph embeddings and their applications to machine learning problems on graphs. PeerJ Comput Sci 7:357

    Google Scholar 

  50. Liu P, Yuan W, Fu J, Jiang Z, Hayashi H, Neubig G (2023) Pre-train, prompt, and predict: A systematic survey of prompting methods in natural language processing. ACM Comput Surv 55(9):1–35

    Google Scholar 

  51. Zhang M, Chen Y (2017) Weisfeiler-lehman neural machine for link prediction. In: Proceedings of the 23rd ACM SIGKDD international conference on knowledge discovery and data mining, pp 575–583

  52. Zhang M, Chen Y (2018) Link prediction based on graph neural networks. Advances in neural information processing systems 31

  53. Wang Z, Lei Y, Li W (2020) Neighborhood attention networks with adversarial learning for link prediction. IEEE Trans Neural Netw Learn Syst 32(8):3653–3663

    Google Scholar 

  54. Wang Z, Li W, Su H (2021) Hierarchical attention link prediction neural network. Knowl-Based Syst 232:107431

    Google Scholar 

  55. Qin M, Zhang C, Bai B, Zhang G, Yeung D-Y (2023) High-quality temporal link prediction for weighted dynamic graphs via inductive embedding aggregation. IEEE Transactions on Knowledge and Data Engineering

  56. Koren Y, Bell R, Volinsky C (2009) Matrix factorization techniques for recommender systems. Computer 42(8):30–37

    Google Scholar 

  57. Ahmed NM, Chen L, Wang Y, Li B, Li Y, Liu W (2018) Deepeye: link prediction in dynamic networks based on non-negative matrix factorization. Big Data Mining and Analytics 1(1):19–33

    Google Scholar 

  58. Liang J, Gurukar S, Parthasarathy S (2021) Mile: A multi-level framework for scalable graph embedding. Proceedings of the International AAAI Conference on Web and Social Media 15:361-372

    Google Scholar 

  59. Chen Z, Shi Y, Qi Z (2019) Constrained matrix factorization for semi-weakly learning with label proportions. Pattern Recogn 91:13–24

    Google Scholar 

  60. Varikuti DP, Genon S, Sotiras A, Schwender H, Hoffstaedter F, Patil KR, Jockwitz C, Caspers S, Moebus S, Amunts K et al (2018) Evaluation of non-negative matrix factorization of grey matter in age prediction. Neuroimage 173:394–410

    Google Scholar 

  61. Hanley JA, McNeil BJ (1982) The meaning and use of the area under a receiver operating characteristic (roc) curve. Radiology 143(1):29–36

    Google Scholar 

  62. Herlocker JL, Konstan JA, Terveen LG, Riedl JT (2004) Evaluating collaborative filtering recommender systems. ACM Trans Inform Syst (TOIS) 22(1):5–53

    Google Scholar 

  63. Batagelj V, Mrvar, A (2014) Pajek

  64. De Winter S, Decuypere T, Mitrović S, Baesens B, De Weerdt J (2018) Combining temporal aspects of dynamic networks with node2vec for a more efficient dynamic link prediction. In: 2018 IEEE/ACM International conference on advances in social networks analysis and mining (ASONAM), IEEE pp 1234–1241

  65. White JG, Southgate E, Thomson JN, Brenner S et al (1986) The structure of the nervous system of the nematode caenorhabditis elegans. Philos Trans R Soc Lond B Biol Sci 314(1165):1-340

    Google Scholar 

  66. Rossi R, Ahmed N (2015) The network data repository with interactive graph analytics and visualization. In: Proceedings of the AAAI conference on artificial intelligence, vol 29

  67. Adamic LA, Glance N (2005) The political blogosphere and the 2004 us election: divided they blog. In: Proceedings of the 3rd international workshop on link discovery, pp 36–43

  68. Jorgensen Z, Yu T, Cormode G (2016) Publishing attributed social graphs with formal privacy guarantees. In: Proceedings of the 2016 international conference on management of data, pp 107–122

  69. Spring N, Mahajan R, Wetherall D (2002) Measuring isp topologies with rocketfuel. ACM SIGCOMM Comput Commun Rev 32(4):133–145

  70. Martinez V, Berzal F, Cubero J-C (2019) Noesis: a framework for complex network data analysis. Complexity 2019:1–14

    Google Scholar 

Download references

Acknowledgements

This work was partly supported by the National Natural Science Foundation of China (No. 62366030, 62062010), the Gansu Provincial Natural Science Foundation (No. 23JRRA8222), the Science and Technology Planning Project of Guangxi (No. AD19245101), the Higher Education Innovation Fund project of Gansu (No. 2022A-022). Additionally, during the revision of this paper, we would like to express our sincere gratitude to Tongfeng Li and Ning Ma for their invaluable experimental support and writing guidance.

Funding

This work is supported by the following funding sources: the National Natural Science Foundation of China (No. 62366030, 62062010), the Gansu Provincial Natural Science Foundation (No. 23JRRA8222), the Science and Technology Planning Project of Guangxi (No. AD19245101), the Higher Education Innovation Fund project of Gansu (No. 2022A-022).

Author information

Authors and Affiliations

  1. School of Computer and Communication, Lanzhou University of Technology, Lanzhou, 730050, China

    Yabing Yao, Yangyang He, Zhentian Huang, Zhipeng Xu, Jianxin Tang & Kai Gao

  2. School of Computer Science and Technology, Guangxi University of Science and Technology, Liuzhou, 545006, China

    Fan Yang

Authors
  1. Yabing Yao
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Yangyang He
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Zhentian Huang
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Zhipeng Xu
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Fan Yang
    View author publications

    You can also search for this author in PubMed Google Scholar

  6. Jianxin Tang
    View author publications

    You can also search for this author in PubMed Google Scholar

  7. Kai Gao
    View author publications

    You can also search for this author in PubMed Google Scholar

Contributions

Yabing Yao: Methodology and Project administration. Yangyang He: Data analysis and Writing. Zhentian Huang: Software and Conducting experiment. Zhipeng Xu: Data curation and Graphing. Fan Yang: Conceptualization and Project administration. Jianxin Tang: Data collection. Kai Gao: Device support.

Corresponding author

Correspondence to Fan Yang.

Ethics declarations

Ethical and informed consent for data used

In our research, we emphasize the importance of ethical practices and informed consent in the acquisition and utilization of data. Firstly, we obtain the dataset used in our study following strict ethical guidelines. The data is sourced from http://konect.uni-koblenz.de/ and http://networkrepository.com/networks.php, and we ensure that the data is anonymized and stripped of any personally identifiable information to protect the privacy and confidentiality of the individuals or entities involved. Furthermore, we highlight the significance of informed consent in the process of data usage. As the data used in our study is pre-existing and publicly available, we adhere to the ethical standards and legal requirements set forth by the data source. It is important to emphasize that our research aligns with the principles of research ethics and integrity, complying with all regulations and guidelines related to data acquisition, storage, and usage. We acknowledge the importance of responsible data handling and are committed to maintaining the confidentiality and privacy of the data subjects.

Conflict of interest

We declare that there are no conflicts of interest in this work. Throughout the research process, we have not encountered any conflicts of interest that could have influenced the research outcomes. We are committed to upholding the highest standards of research ethics and integrity.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Yao, Y., He, Y., Huang, Z. et al. Deep non-negative matrix factorization with edge generator for link prediction in complex networks. Appl Intell 54, 592–613 (2024). https://doi.org/10.1007/s10489-023-05211-1

Download citation

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10489-023-05211-1

Keywords

Search

Navigation