Towards Fast Evaluation of Unsupervised Link Prediction by Random Sampling Unobserved Links

Abstract

Link prediction has aroused extensive attention since it can both discover hidden connections and predict future links in the networks. Many unsupervised link prediction algorithms have been proposed to find these links in a variety of networks. However, there is an evaluation conundrum in unsupervised link prediction. Unobserved links heavily outnumber observed links in large networks, so it is unrealistic to quantify the existence likelihood of all unobserved links to evaluate these algorithms. In this paper, we propose a new evaluation paradigm that is sampling unobserved links to address this problem. First, we demonstrate that the proposed paradigm is feasible in theory. Then, we perform extensive evaluation experiments in real-world networks of different contexts and sizes. The results show that the performance of similarity-based link prediction algorithms is highly stable even at a low sampling ratio in large networks, and the evaluation time degradation caused by sampling is striking. Our findings have broad implications for link prediction.

22 pages, 8 figures

References in corpus (12)

• Finding community structure in networks using the eigenvectors of matrices
• Predicting Missing Links via Local Information
• Modeling polypharmacy side effects with graph convolutional networks
• Effective and Efficient Similarity Index for Link Prediction of Complex Networks
• Evaluating Link Prediction Methods
• Statistical properties of sampled networks by random walks
• TransGCN:Coupling Transformation Assumptions with Graph Convolutional Networks for Link Prediction
• Incorporating GAN for Negative Sampling in Knowledge Representation Learning
• Bounded link prediction for very large networks
• Multi-Task Graph Autoencoders
• Link Prediction in Dynamic Graphs for Recommendation
• What you see is not what you get: how sampling affects macroscopic features of biological networks