How to uniformly sample vertices from a large graph with given distance from a fixed vertex?

Question

Given an undirected graph $G=(V,E)$ and some vertex $v_0\in V$, let $V_k=\{\,v\mid v\in V,d(v_0,v)=k\,\}$ be the set of all vertices with distance $k$ to $v_0$.

How can I quickly draw uniform samples from $V_k$ for a given $k$? In my case, $G$ is implicitly defined as the state transition graph of some combinatorial puzzle and has about $10^{25}$ vertices with $|V_k|\approx 2.3676^k$, so enumerating the vertices in $V_k$ is not an option. I am mostly interested in values of $k$ from $30$ to $50$ and would like to draw about $10^6$ samples for every $k$ in this range.

Answer 1

Given the information you've provided here is an approach I think works.

I will extend your notation to have $V_r(v)$ be the set of vertices of exactly distance $r$ from vertex, $v$. For convenience let $N(v)$ be the neighbours of $v$.

We note that for a given vertex, it has 2, 3 or 4 neighbours, which are easily determinable (constant time); i.e. $V_1(v)$ is trivial. We likewise assume that there is some constant cost for calculating $d(v_0, v)$ for all $v$ for which $d(v_0, v) \leq k$.

Assume that we have an efficient algorithm for all distances $\leq i$, we now show how to solve for $i+1$.

The algorithm is easy to explain - we choose some starting vertex $v_s$ uniformly at random from $V_i$. We then find its neighbours, and check their distance from $v_0$. Let $C(v_s) = V_{i+1} \bigcap N(v_s)$. We note that, at least one vertex in $N(v_s)$ must be in $V_{i-1}$. Thus $|C(v_s)| \leq 3$. Then, with probability $\frac{3 - |C(v_s)|}{3}$ we reject $v_s$ and start again.

Otherwise, we choose a candidate $v_c$ from $C(v)$ uniformly at random: Let $n_c$ be the number of its neighbours which are in $V_i$. Then, we accept $v_c$ with probability $\frac{1}{n_c}$. Otherwise, reject $v_s$ and start again.

Correctness: Define $I(v) = V_i \bigcap N(v)$. Then, the probability of accepting a given $v \in V_{i+1}$ in a round is $$ \sum_{v_s \in I(v)} P[v_s] P[v | v_s] $$ where $P[v_s]$ is the probability of choosing $v_s$ in $V_i$ and is $1/|V_i|$, and $P[v | v_s]$ is the probability of accepting $v$ given that we chose $v_s$. $$ P[v |v_s] = \left(1 - \frac{3 - |C(v_s)|}{3}\right)\frac{1}{|C_v(s)|}\frac{1}{|I(v)|} = \frac{1}{3|I(v)|} $$ Plugging this back in gives us a probability to accept $v$ of $\frac{1}{3V_i}$. Thus, the probability that an iteration accepts any member of $V_{i+1}$ is $\frac{V_{i+1}}{3V_i}$. Assuming the original poster's estimate that $V_i \approx 2.3676^i$, gives us that the probability an iteration succeeds is approximately $\frac{2.3676}{3}$.

Let the cost of determining neighbours be N, the cost of checking distance bound by $i+1$ be $D_{i+1}$, the cost of drawing from $V_i$ be $T_i$, then a round of the algorithm (which may or may not succeed) costs up to: $T_i + N + 4*D_{i+1} + N + 4*D_{i+1}$. Unfortunately, this does mean that the cost of this algorithm to generate a single point is still exponential, albeit with a sizable improvement over enumeration, if one desires a small sample. If we assume that we can swallow the $D_i$ values into reasonable sized constants (in particular since the higher $i$ values where it is more costly they are calculated much less frequently than for lower $i$ values), we have an overall expected complexity of $O\left(\left(\frac{3}{2.3676}\right)^{k-1}\right)$.

Since for each $k$ we need to draw a point from a sub-sample, we get lower values of $k$ for free. For $k=30$, this works out to a complexity of about $10^3$, for $k=40$, this is roughly $10^4$, for $k=50$, this is $10^5$.

So determining whether this is feasible for you to sample $10^6$ points will depend on the horsepower you can bring to bear. For $k=50$ (which would give you all $k \leq 50$) it would be on the order of magnitude of $10^{11}$ work.

Answer 2

After reading MotiN's nice answer, I have decided to modify his procedure as follows:

Let $N(v)=\{\,w\mid w\in V, v\sim w\,\}$ be the neighborhood of $v$. Let $d(v,w)$ be the length of the shortest path between $v$ and $w$.

We draw samples from $V_k$ by means of a random walk from $v_0$ with $k$ steps. At each step $i$, we pick a random edge from $v_{i+1}\in N(v_i)\setminus\{v_{i-1}\}$ with $v_1$ picked from $N(v_0)$, i.e. we do not pick the edge we just came from. Further restrictions can be made (e.g. by means of FSM pruning) to improve the yield.

For each sample $v_k$, we determine all shortest paths to $v_0$ and thus $d(v_0, v_k)$. If $d(v_0, v_k)=k$, we accept the sample, otherwise we reject it. The probability of a sample being accepted is the yield $y=P\big(d(v_0, v_k)=k\big)$ which we compute during the sampling process.

For each accepted sample $v_k$, we have a set of shortest paths $S$ leading from $v_0$ to it. We can use this set to compute the probability $P(v_k)$ of having chosen this sample by summing over all shortest paths to $v_k$:

$$P(v_k)=\sum_{v_0,\dots,v_k\in S}{1\over|N(v_0)|}\prod_{i=1}^{k-1}{1\over|N(v_i)|-1}$$

Using the yield $y$, we can compute the chance $p$ of having chosen $v_k$ from all accepted samples:

$$p=P\big(v_k\mid d(v_0,v_k)=k\big)={P[v_k]\over y}$$

If $|V_k|$ is known, this can be used to compute a bias $b$ for the sample $v_k$

$$b=p\,|V_k|$$

This method allows us to sample vertices from $V_k$ and to compute the bias of each path leading to the sample picked. While we do not get a uniform sample this way, we can compensate for the bias later on.