Abstract Aiming at the incomplete network data and missing nodes in graph data structure, a network node completion algorithm based on graph convolutional network is proposed. Firstly, the observed network is sampled in pairs to construct the closed subgraph and feature matrix of the target node pair. Then, the graph convolutional neural network is employed to extract the representation vectors of subgraphs and their feature matrices for two purposes. One is to infer whether there are missing nodes between target node pairs of each subgraph, and the other is whether the missing nodes between different target node pairs are the same node. Finally, experiments on real network datasets and artificially generated network datasets show that the proposed model can solve the problem of network completion well and recover the network even when half of the nodes in the network are missing.
Fund:National Natural Science Foundation of China(No.71774111,71804047,71401107), Program for Professor of Special Appointment(Eastern Scholar) at Shanghai Institutions of Higher Learning(No.1021303601)
Corresponding Authors:
ZHOU Lixin, Ph.D. His research interests include link prediction and deep learning.
About author:: LIU Chen, Ph.D., associate professor. His research interests include web data mi-ning, internet user behavior analysis and deep learning. LI Ziran, master student. Her research interests include network completion and link prediction.
[1] ACQUISTI A, BRANDIMARTE L, LOEWENSTEIN G. Privacy and Human Behavior in the Age of Information. Science, 2015, 347(6221): 509-514. [2] ANNIBALE A, COOLEN A C C. What You See Is Not What You Get: How Sampling Affects Macroscopic Features of Biological Networks. Interface Focus, 2011, 1(6): 836-856. [3] PAPAGELIS M, DAS G, KOUDAS N. Sampling Online Social Networks. IEEE Transactions on Knowledge and Data Engineering, 2013, 25(3): 662-676. [4] BENEVENUTO F, RODRIGUES T, CHA M, et al. Characterizing User Navigation and Interactions in Online Social Networks. Information Sciences, 2012, 195: 1-24. [5] SARUKKAI R R. Link Prediction and Path Analysis Using Markov Chains. Computer Networks, 2000, 33(1/2/3/4/5/6): 377-386. [6] ZHU J H, HONG J, HUGHES J G. Using Markov Chains for Link Prediction in Adaptive Web Sites // Proc of the 1st International Conference on Computing in an Imperfect World. Berlin, Germany: Springer, 2002: 60-73. [7] LIBEN-NOWELL D, KLEINBERG J. The Link-Prediction Problem for Social Networks // Proc of the 20th International Conference on Information and Knowledge Management. Berlin, Germany: Sprin-ger, 2003: 556-559. [8] ZAREIE A, SAKELLARIOU R. Similarity-Based Link Prediction in Social Networks Using Latent Relationships between the Users. Scientific Reports, 2020, 10(1). DOI: 10.1038/s41598-020-76799-4. [9] KIM M, LESKOVEC J. The Network Completion Problem: Inferring Missing Nodes and Edges in Networks // Proc of the 11th SIAM International Conference on Data Mining. New York, USA: ACM, 2011: 47-58. [10] GUIMERÀ R, SALES-PARDO M. Missing and Spurious Interactions and the Reconstruction of Complex Networks. Proceedings of the National Academy of Sciences of the United States of America, 2009, 106(52): 22073-22078. [11] EYAL R, ROSENFELD A, SINA S, et al. Predicting and Identifying Missing Node Information in Social Networks[C/OL]. [2021-01-05]. https://u.cs.biu.ac.il/~sarit/data/articles/tkdd-final.pdf. [12] FORSATI R, BARJASTEH I, ROSS D, et al. Network Completion by Leveraging Similarity of Nodes. Social Network Analysis and Mining, 2016, 6. DOI: 10.1007/s13278-016-0405-2. [13] BRUNA J, ZAREMBA W, SZLAM A, et al. Spectral Networks and Locally Connected Networks on Graphs[C/OL]. [2021-01-05]. https://arxiv.org/pdf/1312.6203.pdf. [14] NIEPERT M, AHMED M, KUTZKOV K. Learning Convolutional Neural Networks for Graphs // Proc of the 33rd International Conference on Machine Learning. Berlin, Germany: Springer, 2016: 2014-2023. [15] DEFFERRARD M, BRESSON X, VANDERGHEYNST P. Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering // Proc of the 30th International Conference on Neural Information Processing Systems. Cambridge, USA: The MIT Press, 2016: 3844-3852. [16] KIPF T N, WELLING M. Semi-Supervised Classification with Graph Convolutional Networks[C/OL]. [2021-01-05]. https://arxiv.org/pdf/1609.02907.pdf. [17] ZHANG M H, CHEN Y X. Weisfeiler-Lehman Neural Machine for Link Prediction // Proc of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York, USA: ACM, 2017: 575-583. [18] FAN J C, CHOW T. Deep Learning Based Matrix Completion. Neurocomputing, 2017, 266: 540-549. [19] ZHANG M H, CHEN Y X. Link Prediction Based on Graph Neural Networks // Proc of the 32nd Conference on Neural Information Processing Systems. Cambridge, USA: The MIT Press, 2018: 5171-5181. [20] WEI Q. Network Completion via Deep Metric Learning. Journal of Physics: Conference Series, 2020, 1656. DOI: 10.1088/1742-6596/1656/1/012026. [21] WANG X, CHAI Y B, LI H, et al. Link Prediction in Heterogeneous Information Networks: An Improved Deep Graph Convolution Approach. Decision Support Systems, 2021, 141. DOI: 10.1016/j.dss.2020.113448. [22] GAO H, LI B H, XIE W B, et al. CSIP: Enhanced Link Prediction with Context of Social Influence Propagation[C/OL]. [2021-01-05]. https://doi.org/10.1016/j.bdr.2021.100217. [23] LIN T Y, GOYAL P, GIRSHICK R, et al. Focal Loss for Dense Object Detection // Proc of the IEEE International Conference on Computer Vision. Washington, USA: IEEE, 2017: 2999-3007. [24] NEWMAN M E J. Finding Community Structure in Networks Using the Eigenvectors of Matrices. Physical Review E, 2006, 74(3). DOI: 10.1103/PhysRevE.74.036104. [25] LÜ L Y, ZHOU T. Link Prediction in Complex Networks: A Survey. Physica A: Statistical Mechanics and Its Applications, 2011, 390(6): 1150-1170. [26] WANG M X, LOU X Y, CUI B T. A Degree-Related and Link Clustering Coefficient Approach for Link Prediction in Complex Networks. The European Physical Journal B, 2021, 94. DOI: 10.1140/epjb/s10051-020-00037-z. [27] AZIZ F, GUL H, MUHAMMAD I, et al. Link Prediction Using Node Information on Local Paths. Physica A: Statistical Mechanics and its Applications, 2020, 557. DOI: 10.1016/j.physa.2020.124980. [28] SCELLATO S, NOULAS A, MASCOLO C. Exploiting Place Features in Link Prediction on Location-Based Social Networks // Proc of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York, USA: ACM, 2011: 1046-1054. [29] DUAN Y R, GUAN Q. Predicting Potential Knowledge Convergence of Solar Energy: Bibliometric Analysis Based on Link Prediction Model. Scientometrics, 2021, 126: 3749-3773.
2021, Vol. 34 
