Stopping Personalized PageRank without an Error Tolerance Parameter (preprint of accepted manuscript)

Personalized PageRank (PPR) is a popular scheme for ranking the relevance of network nodes to a set of seed ones through a random walk with restart process. Calculating the ranks of all network nodes often involves the power method, which iterates the PPR formula until convergence to an empirically selected numerical tolerance. However, finding a tolerance that is not so lax as to impact pairwise node comparisons but not so strict as to require a high number of iterations to converge requires time-consuming empirical investigation. In this work we aim to avoid this investigation by stopping power method iterations when node rank order is robust against subsequent changes. To do this, we analyse the expected fraction of random walks considered at a given iteration and identify a potential stopping point that depends on a (fixed) confidence level of future iterations preserving node order. Experiments on four real-world networks show that a confidence level of 98% runs in a fraction of the time and yields more than 0.999 Spearman correlation with the node order of 10^-20 numerical tolerance. Furthermore, that stopping point is comparable to empirically selecting a numerical tolerance that yields robust node order