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?

  • 3
    $\begingroup$ (+1) Nice question. I've seen work on similar problems from a few years ago; I'll try to find it and dig it out of my notes. It would be a very nice addition if you could add some detail to explain how you can randomly sample an outlink of a given vertex without knowing the corresponding outdegree! Such additional detail may help readers provide better guidance. Welcome to the site. Cheers. $\endgroup$ – cardinal Feb 3 '13 at 21:26
  • $\begingroup$ Thank you! Well, I'm studying arrangements of hyperplanes. Each cell of such arrangement corresponds to a vertex in my graph; two vertices are incident iff corresponding cells are adjacent. It's very easy to get one random neighbour of a vertex --- I just pick any point within corresponding cell and send a ray from it in a random direction. This ray intersects some of my hyperplanes; any point between first and second intersections will lie in neighbour cell. But finding all neighbours involves algorithms which are too slow for high dimensions. $\endgroup$ – esokolov Feb 4 '13 at 1:05
  • $\begingroup$ @esokolov: This sounds an awful lot like algebraic geometry, specifically Schubert Calculus. Could you elaborate some more on how these arrangements arise? $\endgroup$ – Alex R. Apr 3 '18 at 22:12
  • $\begingroup$ Otherwise, I'm skeptical this is workable. One thing is if the graph is irreducible (and positive recurrent), then the stationary distribution satisfies $\pi_i=cd_i$, where $d_i$ is the vertex degree, and $c$ depends only on the graph $G$. So this way you can try to estimate $c$, and get away without knowing $d_j$. This gives you $m_i=1/\pi_i$, where $m_i$ is the mean return time to $i$. But you're interested in function values on vertices, so to answer this question better, you need some sort of regularity conditions on $f$, for example $|f(i)-f(j)|<K$, where $i,j$ are neighboring vertices. $\endgroup$ – Alex R. Apr 3 '18 at 22:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.