LAUSR

Graphs are commonly used in various applications such as online social networks (OSNs), E-commerce systems and social recommender systems. Random walk sampling is often used to conduct statistical estimation over such graphs. This paper develops an algorithmic framework to reduce the mean square error of such statistical estimation. Our algorithmic framework is inspired by that the mean square error can be decomposed into a sum of the bias and variance of the estimator. More specifically, we apply the bootstrapping technique to design a bias reduction algorithm. Our bias reduction algorithm only utilizes a small number of “valid” sub-samples, which can reduce more bias of the estimator but may increase the variance of the estimator significantly. We use multiple parallel random walks to reduce this variance such that it can be reduced to arbitrarily small by deploying a sufficient number of random walks. We provide theoretical guarantees and computational complexity analysis of our proposed bias reduction algorithms. Our algorithmic framework enables one to attain different trade-offs between the sample complexity (i.e., number of parallel random walks) and the mean square error of the statistical estimation. Also, the proposed bias reduction algorithm is generic and can be applied to optimize a large class of random walk sampling algorithms. To demonstrate the versatility of the framework, we apply it to optimize the Metropolis random walk and simple random walk sampling. Extensive experiments on four public datasets confirm the effectiveness and computational efficiency of our proposed algorithmic framework under the mean square metric and beyond.