4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ (1) Can you quickly evaluate $d(v_0,v)$ for a given $v$? (2) Can you quickly pick a random neighbor for a given $v$? (3) Does it matter if among the sample for a given $k$, there are some vertices that actually have $d(v_0,v)<k$? (You may see where I am heading.) $\endgroup$ – Stephan Kolassa Jul 14 '18 at 19:01
  • $\begingroup$ @StephanKolassa (1) the amount of time needed to evaluate this is proportional to $b^{d(v_0,v)}$. Feasible for $k\le80$, instantly for $k\le40$. (2) Yes. Each vertex has between $2$ and $4$ neighbors, computing neighbors can be done instantly. (3) No, if those vertices are also uniformly distributed and independent of each other and if I know the distribution of distances. It would be better if such vertices would not be present. For the $V_k$ I am interested in, membership can be decided quickly, so filtering out wrong vertices is feasible. $\endgroup$ – fuz Jul 14 '18 at 19:05
  • $\begingroup$ @StephanKolassa Though I do not see where you are going. I tried random walks before, but I couldn't figure out how to make the resulting vertices uniformly distributed. $\endgroup$ – fuz Jul 14 '18 at 19:05
  • $\begingroup$ Ah, if you have regions with higher density, then a random walk may have a low(er) probability of traversing them... looks like you have a hard problem. Good luck! $\endgroup$ – Stephan Kolassa Jul 14 '18 at 19:08
  • $\begingroup$ @StephanKolassa The density is pretty uniform with the graph having six equally sized equivalence classes for its vertices (it's the state transition graph of the 24 puzzle, which is like the 15 puzzle but on a 5x5 grid). The main difficulty lies in some vertices in $V_k$ having more than one path of length $k$ from $v_0$ to them and thus being picked with higher probability. I wonder if it is possible to compensate for that. The other difficulty is paths on which nodes overall have lower degree being picked less likely. $\endgroup$ – fuz Jul 14 '18 at 19:13
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I'm sure you mean “note that, at least one vertex in $N(v_s)$ must be in $V_{i-1}$” instead $\endgroup$ – fuz Jul 15 '18 at 0:19
  • $\begingroup$ This algorithm makes sense. I'm not entirely sure if the proof of correctness holds and I am a bit skeptical that the yield is high enough. It seems like the yield of samples decreases by a constant factor with every iteration; seems like we have to start with quite a few samples to get enough in later iterations. $\endgroup$ – fuz Jul 15 '18 at 0:25
  • $\begingroup$ You are right regarding the complexity - I will update the answer to reflect the correct calculation $\endgroup$ – MotiN Jul 15 '18 at 6:01
  • $\begingroup$ Note that this is basically a random walk starting from $v_0$ - we abandon the current path when either we can't move further away from $v_0$ from the current vertex, or probabilistically, to ensure that a uniform distribution for each distance. $\endgroup$ – MotiN Jul 17 '18 at 8:36
  • $\begingroup$ The key point of your answer is that you found a way to account for bias gained throughout the random walk. I propose the following modification to your algorithm: instead of discarding walks, always perform each walk to the end. Then compute the probability you would have taken it with proper bias compensation. Finally, do a weighted random sample on the resulting vertices where each vertex' weight is the reciprocal of the probability of taking it. This should iron out the bias without throwing away too many samples. $\endgroup$ – fuz Jul 19 '18 at 10:20
1
$\begingroup$

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$. For $v\in V_i$ let $C(v)=N(v)\cap V_{i+1}$ be the neighbors of $v$ that are farther away from $v_0$ as in MotiN's answer and let $\bar C(v)=N(v)\cap V_{i-1}$ be the vertices that are nearer to $v_0$. The graph I care about is bipartite so $C(v)\mathbin{\dot\cup}\bar C(v)=N(v)$, but that's not particularly important to the algorithm.

The algorithm works as follows:

  1. Compute $W$ as a set of $n$ vertices reached from $k$ step random walks from $v_0$ such that $W\subset V_k$.
  2. For each $v_n\in W$ with $v_0\sim v_1\sim \ldots\sim v_n$ being the path taken to reach $v_n$, let $$b(v_n)=\frac{|\bar C(v_1)|}{|C(v_0)|}\frac{|\bar C(v_2)|}{|C(v_1)|}\cdots\frac{|\bar C(v_n)|}{|C(v_{n-1})|}$$ be the bias of $v_n$.
  3. Let $c>1$ be the oversampling factor and take $n\over c$ weighted random samples $S\subset W$ with weights $w(v)=b(v)^{-1}$ for each $v\in W$.
  4. Return $S$.

The key idea behind this algorithm is to instead of rejecting samples during the random walk (and thus getting a very low yield), we compute the bias of each sample and compensate for it by taking a random sample weighted by reciprocal bias out of the samples gained through the random walk. This should cancel the bias, giving uniformly random samples.

I am not exactly sure how to choose $c$ though.

$\endgroup$
  • $\begingroup$ Can you add subscripts to the $C(\dot)$ functions to reflect the $i$ of $V_i$ they are for? it will make things clearer, thank you. $\endgroup$ – MotiN Jul 22 '18 at 7:27
  • $\begingroup$ As well, I'd really suggest you do a calculation of the probability of selecting a vertex. This is really the only way to know if your algorithm is correct, rather than a gut feeling about it. $\endgroup$ – MotiN Jul 22 '18 at 8:21
  • $\begingroup$ @MotiN it is $v_i\in V_i$ for all $i$. I have used the same bias values as in your answer, except that I don't lose a factor of $3$ because I am not constrained to actual probabilities. $\endgroup$ – fuz Jul 22 '18 at 10:08
  • $\begingroup$ I don't think that $\sum_{v \in W} b(v)^{-1} = 1$ (of course you can reweight). And what happens with vertices not appearing in $W$? The result of your random walks will of course not include a lot of those; I think you really must do a proper calculation to include the probability of a node appearing in $W$ times the chance of it being chosen by the bootstrap sampling procedure. That first probability seems very difficult to me to calculate directly. $\endgroup$ – MotiN Jul 22 '18 at 10:19
  • $\begingroup$ @MotiN Do you mean $S$ by set of vertices chosen by the bootstrap sampling procedure? $\endgroup$ – fuz Jul 22 '18 at 10:43

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.