2017 conference paper

On the rao-blackwellization and its application for graph sampling via neighborhood exploration

Ieee infocom 2017 - ieee conference on computer communications.

co-author countries: United States of America 🇺🇸
Source: NC State University Libraries
Added: August 6, 2018

We study how the so-called Rao-Blackwellization, which is a variance reduction technique via “conditioning” for Monte Carlo methods, can be judiciously applied for graph sampling through neighborhood exploration. Despite its popularity for Monte Carlo methods, it is little known for Markov chain Monte Carlo methods and has never been discussed for random walk-based graph sampling. We first propose two forms of Rao-Blackwellization that can be used as a swap-in replacement for virtually all (reversible) random-walk graph sampling methods, and prove that the ‘Rao-Blackwellized’ estimators reduce the (asymptotic) variances of their original estimators yet maintain their inherent unbiasedness. The variance reduction can translate into lowering the number of samples required to achieve a desired sampling accuracy. However, the sampling cost for neighborhood exploration, if required, may outweigh such improvement, even leading to higher total amortized cost. Considering this, we provide a generalization of Rao-Blackwellization, which allows one to choose a suitable extent of obtaining Rao-Blackwellized samples in order to achieve a right balance between sampling cost and accuracy. We finally provide simulation results via real-world datasets that confirm our theoretical findings.