  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, improving the MAP (Mean Average Precision) by up to 15.8% on the best
competitor.
