论文标题
通过随机抽样未观察到的链接快速评估无监督的链接预测
Towards Fast Evaluation of Unsupervised Link Prediction by Random Sampling Unobserved Links
论文作者
论文摘要
链接预测引起了广泛的关注，因为它既可以发现隐藏的连接并预测网络中的未来链接。已经提出了许多无监督的链接预测算法，以在各种网络中找到这些链接。但是，在无监督的链接预测中存在评估难题。未观察到的链接在大型网络中观察到的链接众多，因此量化所有未观察到的链接的存在可能是不现实的，以评估这些算法。在本文中，我们提出了一种新的评估范式，该范式正在对未观察到的链接进行采样以解决此问题。首先，我们证明所提出的范式在理论上是可行的。然后，我们在不同上下文和大小的现实世界网络中执行广泛的评估实验。结果表明，即使在大型网络中，基于相似性的链接预测算法的性能也很稳定，并且通过采样引起的评估时间降解令人惊讶。我们的发现对链接预测具有广泛的影响。
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.
