[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ skip to main content
10.1145/3589334.3645646acmconferencesArticle/Chapter ViewAbstractPublication PagesthewebconfConference Proceedingsconference-collections
research-article
Open access

Link Prediction on Multilayer Networks through Learning of Within-Layer and Across-Layer Node-Pair Structural Features and Node Embedding Similarity

Published: 13 May 2024 Publication History

Abstract

Link prediction has traditionally been studied in the context of simple graphs, although real-world networks are inherently complex as they are often comprised of multiple interconnected components, or layers. Predicting links in such network systems, or multilayer networks, require to consider both the internal structure of a target layer as well as the structure of the other layers in a network, in addition to layer-specific node-attributes when available. This problem poses several challenges, even for graph neural network based approaches despite their successful and wide application to a variety of graph learning problems. In this work, we aim to fill a lack of multilayer graph representation learning methods designed for link prediction. Our proposal is a novel neural-network-based learning framework for link prediction on (attributed) multilayer networks, whose key idea is to combine (i) pairwise similarities of multilayer node embeddings learned by a graph neural network model, and (ii) structural features learned from both within-layer and across-layer link information based on overlapping multilayer neighborhoods. Extensive experimental results have shown that our framework consistently outperforms both single-layer and multilayer methods for link prediction on popular real-world multilayer networks, with an average percentage increase in AUC up to 38%. We make source code and evaluation data available at https://mlnteam-unical.github.io/resources/.

Supplemental Material

MP4 File
Supplemental video

References

[1]
Lada A Adamic and Eytan Adar. 2003. Friends and neighbors on the web. Social networks, Vol. 25, 3 (2003), 211--230.
[2]
Alberto Aleta, Marta Tuninetti, Daniela Paolotti, Yamir Moreno, and Michele Starnini. 2020. Link prediction in multiplex networks via triadic closure. Physical Review Research, Vol. 2, 4 (2020).
[3]
Albert-László Barabási and Réka Albert. 1999. Emergence of scaling in random networks. Science, Vol. 286, 5439 (1999), 509--512.
[4]
Vincent D Blondel, Jean-Loup Guillaume, Renaud Lambiotte, and Etienne Lefebvre. 2008. Fast unfolding of communities in large networks. Journal of statistical mechanics: theory and experiment, Vol. 2008, 10 (2008), P10008.
[5]
Stefano Boccaletti, Ginestra Bianconi, Regino Criado, Charo I Del Genio, Jesús Gómez-Gardenes, Miguel Romance, Irene Sendina-Nadal, Zhen Wang, and Massimiliano Zanin. 2014. The structure and dynamics of multilayer networks. Physics reports, Vol. 544, 1 (2014), 1--122.
[6]
Shaked Brody, Uri Alon, and Eran Yahav. 2022. How Attentive are Graph Attention Networks?
[7]
Lei Cai and Shuiwang Ji. 2020. A multi-scale approach for graph link prediction. In Procs. of the AAAI conference on artificial intelligence. 3308--3315.
[8]
Yukuo Cen, Xu Zou, Jianwei Zhang, Hongxia Yang, Jingren Zhou, and Jie Tang. 2019. Representation learning for attributed multiplex heterogeneous network. In Procs. of the 25th ACM SIGKDD international conference on knowledge discovery and data mining. 1358--1368.
[9]
Benjamin Paul Chamberlain, Sergey Shirobokov, Emanuele Rossi, Fabrizio Frasca, Thomas Markovich, Nils Yannick Hammerla, Michael M. Bronstein, and Max Hansmire. 2023. Graph Neural Networks for Link Prediction with Subgraph Sketching.
[10]
Beth Chen, David Hall, and Dmitri Chklovskii. 2006. Wiring optimization can relate neuronal structure and function. Proceedings of the National Academy of Sciences of the United States of America, Vol. 103 (04 2006), 4723--8.
[11]
Xiaokai Chu, Xinxin Fan, Di Yao, Zhihua Zhu, Jianhui Huang, and Jingping Bi. 2019. Cross-Network Embedding for Multi-Network Alignment. In Procs. of The World Wide Web Conference. 273--284.
[12]
J. Coleman, E. Katz, and H. Menzel. 1957. The diffusion of an innovation among physicians. Sociometry, Vol. 20, 4 (1957), 253--270.
[13]
Michele Coscia, Christian Borgelt, and Michael Szell. 2022. Fast Multiplex Graph Association Rules for Link Prediction. arxiv: 2211.12094
[14]
Manlio De Domenico, Andrea Lancichinetti, Alex Arenas, and Martin Rosvall. 2015. Identifying modular flows on multilayer networks reveals highly overlapping organization in interconnected systems. Physical Review X, Vol. 5, 1 (2015), 011027.
[15]
Chaofan Fu, Guanjie Zheng, Chao Huang, Yanwei Yu, and Junyu Dong. 2023. Multiplex Heterogeneous Graph Neural Network with Behavior Pattern Modeling. In Procs. of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining. 482--494.
[16]
Justin Gilmer, Samuel S. Schoenholz, Patrick F. Riley, Oriol Vinyals, and George E. Dahl. 2017. Neural Message Passing for Quantum Chemistry. In Proc. 34th Int. Conf. on Machine Learning. 1263--1272.
[17]
Aditya Grover and Jure Leskovec. 2016. node2vec: Scalable feature learning for networks. In Procs. of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining. 855--864.
[18]
Desislava Hristova, Anastasios Noulas, Chloë Brown, Mirco Musolesi, and Cecilia Mascolo. 2016. A multilayer approach to multiplexity and link prediction in online geo-social networks. EPJ Data Sci., Vol. 5, 1 (2016), 24.
[19]
Mahdi Jalili, Yasin Orouskhani, Milad Asgari, Nazanin Alipourfard, and Matjavz Perc. 2017. Link prediction in multiplex online social networks. Royal Society open science, Vol. 4, 2 (2017), 160863.
[20]
Glen Jeh and Jennifer Widom. 2002. Simrank: a measure of structural-context similarity. In Procs. of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining. 538--543.
[21]
Baoyu Jing, Chanyoung Park, and Hanghang Tong. 2021. Hdmi: High-order deep multiplex infomax. In Procs. of the Web Conference. 2414--2424.
[22]
Thomas N. Kipf and Max Welling. 2016. Variational Graph Auto-Encoders. arxiv: 1611.07308
[23]
Mikko Kivel"a, Alex Arenas, Marc Barthelemy, James P Gleeson, Yamir Moreno, and Mason A Porter. 2014. Multilayer networks. Journal of complex networks, Vol. 2, 3 (2014), 203--271.
[24]
Matthew Kraatz, Nina Shah, and Emmanuel Lazega. 2003. The Collegial Phenomenon: The Social Mechanisms of Cooperation among Peers in a Corporate Law Partnership. Administrative Science Quarterly, Vol. 48 (09 2003), 525. https://doi.org/10.2307/3556688
[25]
Kyu-Min Lee, Byungjoon Min, and Kwang-Il Goh. 2015. Towards real-world complexity: an introduction to multiplex networks. The European Physical Journal B, Vol. 88 (2015), 1--20.
[26]
David Liben-Nowell and Jon Kleinberg. 2003. The link prediction problem for social networks. In Procs. of the twelfth international conference on Information and knowledge management. 556--559.
[27]
Matteo Magnani, Obaida Hanteer, Roberto Interdonato, Luca Rossi, and Andrea Tagarelli. 2022. Community Detection in Multiplex Networks. ACM Comput. Surv., Vol. 54, 3 (2022), 48:1--48:35. https://doi.org/10.1145/3444688
[28]
Matteo Magnani, Barbora Micenkova, and Luca Rossi. 2013. Combinatorial Analysis of Multiple Networks. arxiv: 1303.4986 [cs.SI]
[29]
V'ictor Mart'inez, Fernando Berzal, and Juan-Carlos Cubero. 2016. A Survey of Link Prediction in Complex Networks. Comput. Surveys, Vol. 49, 4 (2016).
[30]
Liliana Martirano, Lorenzo Zangari, and Andrea Tagarelli. 2022. Co-MLHAN: contrastive learning for multilayer heterogeneous attributed networks. Appl. Netw. Sci., Vol. 7, 1 (2022), 65. https://doi.org/10.1007/S41109-022-00504--9
[31]
Ryuta Matsuno and Tsuyoshi Murata. 2018. Mell: effective embedding method for multiplex networks. In Companion Proceedings of the The Web Conference 2018. 1261--1268.
[32]
Vincenzo Nicosia, Ginestra Bianconi, Vito Latora, and Marc Barthelemy. 2013. Growing multiplex networks. Physical review letters, Vol. 111, 5 (2013), 058701.
[33]
Vincenzo Nicosia and Vito Latora. 2015. Measuring and modeling correlations in multiplex networks. Physical Review E, Vol. 92, 3 (2015), 032805.
[34]
Chanyoung Park, Donghyun Kim, Jiawei Han, and Hwanjo Yu. 2020. Unsupervised attributed multiplex network embedding. In Procs. of the AAAI Conference on Artificial Intelligence, Vol. 34. 5371--5378.
[35]
Bryan Perozzi, Rami Al-Rfou, and Steven Skiena. 2014. Deepwalk: Online learning of social representations. In Procs. of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining. 701--710.
[36]
Manisha Pujari and Rushed Kanawati. 2015. Link prediction in multiplex networks. Networks and Heterogeneous Media, Vol. 10 (03 2015), 17--35.
[37]
Uday Shankar Shanthamallu, Jayaraman J. Thiagarajan, Huan Song, and Andreas Spanias. 2019. GrAMME: Semi-Supervised Learning using Multi-layered Graph Attention Models. arxiv: 1810.01405 [stat.ML]
[38]
Jian Tang, Meng Qu, Mingzhe Wang, Ming Zhang, Jun Yan, and Qiaozhu Mei. 2015. Line: Large-scale information network embedding. In Procs. of the 24th international conference on world wide web. 1067--1077.
[39]
Komal Teru, Etienne Denis, and Will Hamilton. 2020. Inductive relation prediction by subgraph reasoning. In Procs. of the International Conference on Machine Learning. 9448--9457.
[40]
Petar Velickovic, William Fedus, William L. Hamilton, Pietro Liò, Yoshua Bengio, and R. Devon Hjelm. 2019. Deep Graph Infomax. In Procs. of the 7th International Conference on Learning Representations.
[41]
Xiao Wang, Nian Liu, Hui Han, and Chuan Shi. 2021. Self-supervised heterogeneous graph neural network with co-contrastive learning. In Procs. of the 27th ACM SIGKDD conference on knowledge discovery and data mining. 1726--1736.
[42]
Xiyuan Wang, Haotong Yang, and Muhan Zhang. 2023. Neural Common Neighbor with Completion for Link Prediction. arxiv: 2302.00890
[43]
Pengyang Yu, Chaofan Fu, Yanwei Yu, Chao Huang, Zhongying Zhao, and Junyu Dong. 2022. Multiplex heterogeneous graph convolutional network. In Procs. of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining. 2377--2387.
[44]
Seongjun Yun, Seoyoon Kim, Junhyun Lee, Jaewoo Kang, and Hyunwoo J Kim. 2021. Neo-GNNs: Neighborhood Overlap-aware Graph Neural Networks for Link Prediction. In Advances in Neural Information Processing Systems, Vol. 34. 13683--13694.
[45]
Lorenzo Zangari, Roberto Interdonato, Antonio Caliò, and Andrea Tagarelli. 2021. Graph convolutional and attention models for entity classification in multilayer networks. Appl. Netw. Sci., Vol. 6, 1 (2021), 87. https://doi.org/10.1007/s41109-021-00420--4
[46]
Muhan Zhang. 2022. Graph Neural Networks: Link Prediction. In Graph Neural Networks: Foundations, Frontiers, and Applications, Lingfei Wu, Peng Cui, Jian Pei, and Liang Zhao (Eds.). Springer Singapore, Singapore, 195--223.
[47]
Muhan Zhang and Yixin Chen. 2018. Link prediction based on graph neural networks. Advances in neural information processing systems, Vol. 31 (2018).
[48]
Muhan Zhang and Yixin Chen. 2020. Inductive Matrix Completion Based on Graph Neural Networks.
[49]
Muhan Zhang, Pan Li, Yinglong Xia, Kai Wang, and Long Jin. 2021. Labeling trick: A theory of using graph neural networks for multi-node representation learning. Advances in Neural Information Processing Systems, Vol. 34 (2021), 9061--9073.
[50]
Tao Zhou, Linyuan Lü, and Yi-Cheng Zhang. 2009. Predicting missing links via local information. The European Physical Journal B, Vol. 71 (2009), 623--630.
[51]
Boyao Zhu and Yongxiang Xia. 2015. An information-theoretic model for link prediction in complex networks. Scientific reports, Vol. 5, 1 (2015), 13707. io

Cited By

View all
  • (2024)An Integrated Method for Cooperation Prediction in Complex Standard NetworksSystems10.3390/systems1207025712:7(257)Online publication date: 15-Jul-2024
  • (2024)Relation-aware multiplex heterogeneous graph neural networkKnowledge-Based Systems10.1016/j.knosys.2024.112806(112806)Online publication date: Dec-2024
  • (2024)Link prediction for multi-layer and heterogeneous cyber-physical networksInternational Journal of Machine Learning and Cybernetics10.1007/s13042-024-02412-zOnline publication date: 14-Oct-2024

Index Terms

  1. Link Prediction on Multilayer Networks through Learning of Within-Layer and Across-Layer Node-Pair Structural Features and Node Embedding Similarity

      Recommendations

      Comments

      Please enable JavaScript to view thecomments powered by Disqus.

      Information & Contributors

      Information

      Published In

      cover image ACM Conferences
      WWW '24: Proceedings of the ACM Web Conference 2024
      May 2024
      4826 pages
      ISBN:9798400701719
      DOI:10.1145/3589334
      This work is licensed under a Creative Commons Attribution International 4.0 License.

      Sponsors

      Publisher

      Association for Computing Machinery

      New York, NY, United States

      Publication History

      Published: 13 May 2024

      Check for updates

      Author Tags

      1. graph neural networks
      2. graph representation learning
      3. link prediction
      4. multilayer networks

      Qualifiers

      • Research-article

      Conference

      WWW '24
      Sponsor:
      WWW '24: The ACM Web Conference 2024
      May 13 - 17, 2024
      Singapore, Singapore

      Acceptance Rates

      Overall Acceptance Rate 1,899 of 8,196 submissions, 23%

      Contributors

      Other Metrics

      Bibliometrics & Citations

      Bibliometrics

      Article Metrics

      • Downloads (Last 12 months)581
      • Downloads (Last 6 weeks)105
      Reflects downloads up to 25 Dec 2024

      Other Metrics

      Citations

      Cited By

      View all
      • (2024)An Integrated Method for Cooperation Prediction in Complex Standard NetworksSystems10.3390/systems1207025712:7(257)Online publication date: 15-Jul-2024
      • (2024)Relation-aware multiplex heterogeneous graph neural networkKnowledge-Based Systems10.1016/j.knosys.2024.112806(112806)Online publication date: Dec-2024
      • (2024)Link prediction for multi-layer and heterogeneous cyber-physical networksInternational Journal of Machine Learning and Cybernetics10.1007/s13042-024-02412-zOnline publication date: 14-Oct-2024

      View Options

      View options

      PDF

      View or Download as a PDF file.

      PDF

      eReader

      View online with eReader.

      eReader

      Login options

      Media

      Figures

      Other

      Tables

      Share

      Share

      Share this Publication link

      Share on social media