University of Southern California, Los Angeles, California, United States of America.
Seoul National University, Seoul, Korea.
PLoS One. 2019 Mar 20;14(3):e0213857. doi: 10.1371/journal.pone.0213857. eCollection 2019.
Given a real-world graph, how can we measure relevance scores for ranking and link prediction? Random walk with restart (RWR) provides an excellent measure for this and has been applied to various applications such as friend recommendation, community detection, anomaly detection, etc. However, RWR suffers from two problems: 1) using the same restart probability for all the nodes limits the expressiveness of random walk, and 2) the restart probability needs to be manually chosen for each application without theoretical justification. We have two main contributions in this paper. First, we propose Random Walk with Extended Restart (RWER), a random walk based measure which improves the expressiveness of random walks by using a distinct restart probability for each node. The improved expressiveness leads to superior accuracy for ranking and link prediction. Second, we propose SuRe (Supervised Restart for RWER), an algorithm for learning the restart probabilities of RWER from a given graph. SuRe eliminates the need to heuristically and manually select the restart parameter for RWER. Extensive experiments show that our proposed method provides the best performance for ranking and link prediction tasks.
给定一个真实世界的图，我们如何衡量排名和链接预测的相关性得分？重新启动随机游走 (RWR) 为此提供了一个极好的度量标准，并已应用于各种应用，如朋友推荐、社区检测、异常检测等。然而，RWR 存在两个问题：1）对所有节点使用相同的重新启动概率限制了随机游走的表达能力，2）重新启动概率需要针对每个应用手动选择，没有理论依据。本文有两个主要贡献。首先，我们提出了基于随机游走的扩展重新启动 (RWER)，这是一种随机游走度量标准，通过为每个节点使用不同的重新启动概率来提高随机游走的表达能力。改进的表达能力为排名和链接预测带来了更高的准确性。其次，我们提出了 SuRe（RWER 的监督重新启动），这是一种从给定图中学习 RWER 重新启动概率的算法。SuRe 消除了对 RWER 重新启动参数进行启发式和手动选择的需要。广泛的实验表明，我们提出的方法在排名和链接预测任务中提供了最佳性能。
