I have a very large graph and a function of its vertices, and want to estimate mean value of this function. It's not possible to sample vertices uniformly in this problem, so a reasonable choice for estimation would be simple random walk. The problem is that for any vertex I can only pick a random neighbour of it; finding the whole neighbourhood of a vertex is extremely hard. So I don't know degrees of sampled vertices, can't find stationary probabilities and can't use standard random walk estimators. Are there still any ways to get unbiased estimate of mean function value?