How to find a random cycle in a large graph?

Question

Suppose we have a large directed graph $G$ with no self-cycle and no more than one edge between two nodes, for example, containing about 2000 nodes and about 10 edges per node. Now we need to achieve these goals as quickly as possible:

1. Find a random cycle $R$ in this graph. The 'Random' means no matter how big the cycle is, all the possible cycles should be picked with the same probabilities. (To be clear, a cycle means a directed close cycle) If there is no cycle in this graph, then stop and exit.

2. After finding the random cycle, we reverse this cycle $R$, which means this cycle will be changed to another direction. Now how should we find a random cycle on this new graph $G'$.

3. The step 1 and step 2 can be invoked for many times, please find a proper way to store the graph and find a random cycle easily.

It's okay to preprocess the graph for a long time, but what I want is to ensure that the step 1 and step 2 could be as quickly as possible.

For example, now we have a graph:

$$ \require{AMScd} \begin{CD} 1 @>>> 2\\ @AAA \nwarrow @VVV\\ 4 @<<< 3 \end{CD} $$

First we need to find a random cycle, and there are two cycles in this graph. Suppose we get this one.

$$ \require{AMScd} \begin{CD} 1 @>>> 2\\ & \nwarrow @VVV\\ & & 3 \end{CD} $$

Then, after reversing the first cycle, the graph becomes:

$$ \require{AMScd} \begin{CD} 1 @<<< 2\\ @AAA \searrow @AAA\\ 4 @<<< 3 \end{CD} $$

When we get a random cycle on this graph, there are two cycles that we can choose:

1. $$ \require{AMScd} \begin{CD} 1 @<<< 2\\ & \searrow @AAA\\ & & 3 \end{CD} $$

2. $$ \require{AMScd} \begin{CD} 1 & \\ @AAA \searrow &\\ 4 @<<< 3 \end{CD} $$

Answer 1

Since "it's okay to preprocess the graph for a long time", one can base the cycle sampling on the (exponential-time) enumeration of cycles/paths, e.g., described in my paper Making Walks Count: From Silent Circles to Hamiltonian Cycles.

This way, pick the first edge $(u,v)$ of a cycle randomly based on the proportion of cycles that contain this edge. Then, pick the second edge $(v,w)$ based on the proportion of cycles that contain path $(u,v,w)$ among those that contain edge $(u,v)$, and so on.

Answer 2

This answer is about directed simple cycles, meaning that the only repeated vertices are the first and last ones.

First, there's no general efficient algorithm to sample uniformly a directed simple cycle unless RP = NP. Such a consequence is essentially on the same order as P = NP, so it is strong evidence that there is no such algorithm. This is Jerrum-Valiant-Vazirani's Random generation of combinatorial structures from a uniform distribution, proposition 5.1.

The moral of that proposition is that usually when the corresponding "spanning structure" problem is hard, the sampling problem is hard. In this case, the "spanning structure" problem is Hamiltonian directed cycle. The reduction involves modifying the underlying graph $G$ to get graph $G'$ so that a random directed cycle in $G'$ corresponds to a very long directed cycle in $G$. This is achieved by replacing the edges of $G$ with chains of diamonds that allow for exponentially many ways to use each edge in a cycle. Please check the linked paper for further details.

Despite this worst case result, there are still tools you can use. The following is a non-exhaustive list:

1. Binary decision diagrams / zero suppressed binary decision diagrams. This is a way to construct a branching program that efficiently represents some set of combinatorial objects. You can construct these algorithmically, although they can get very large. If you can construct one for your instance, you could count or uniformly sample directed simple cycles, among other things. This tends to work for 'medium' sized problems. There is a python library for this tool called graphillion.

2. You can sample if you can compute the marginal probabilities by following the equivalence between sampling and counting self-reducible structures (for completeness sake I wrote this out in appendix B.1 in this paper about a related but different sampling problem). All of these marginal counts can be encoded as SAT problems, and you can feed it to a #SAT solver. I don't know how well this works in practice, but its seems worth trying given the incredible success of SAT solvers on real world problems.

3. If the underlying graph has small treewidth, you can use a (complicated) dynamic program. This follows from Courcelle's theorem -- you can encode directed simple cycles on G into certain kinds of objects in an associated graph.

   For instance, define a spoon to be a 3 cycle with an edge sticking out, and a spoon cycle to be a cycle of these glued spoon to handle... then take your directed graph G, and get an undirected graph G' by replacing directed edges with a spoon pointing in the direction of the arrow. Once this is done, directed simple cycles in G correspond to spoon cycles in G'. You can represent a spoon cycle as an $MSO_2$ formula, so you can count them fixed parameter tractably in the treewidth of $G'$, which basically the treewidth of the underlying graph of $G$. (I had to write this out in the appendix of a project I'm working on, so I'll eventually update this with a link that is hopefully clearer.)

   In general the algorithm you get from Courcelle's is not practical, but with some grit and creativity you can write down a dynamic program that can be useful.

4. It's plausible that there are some Markov chains on directed simple cycles that will run well on your graph. I didn't think of any, but instead...

5. By picking a good family of Markov chains, you can run a more sophisticated rejection sampling procedure than uniformly sampling a subset of edges. One way this can work is by designing a family of score functions $S_{\lambda} : \{0,1\}^E \to \mathbb{R}_{\geq 0}$, such that $S_{\lambda}$ is constant on $\{ \{ e \in \text{edges}(C) \} : C \in \text{set of simple cycles of } G\}$. Then, if you run the hypercube random walk on $\{0,1\}^E$ using $S_{\lambda}$ as the score function, a sample from the stationary distribution will be uniform over simple cycles whenever it outputs a simple cycle. You can then try to pick $S_{\lambda}$ to trade off between the mixing time being long, and the probability that stationary distribution outputs a simple cycle being small.

   Here is one way to do this. Suppose you had a function $f: \{0,1\}^E \to \mathbb{N}$ that measured how far a set was from being a directed simple cycle -- $f(S) = 0$ iff $S$ is the set of edges of a simple cycle, and $f(S) \geq 1$ otherwise. Then you could define $S_{\lambda}(S) = \lambda^{f(S)}$ for $\lambda > 0$. Setting $\lambda = 1$ would give you the hypercube random walk, which is rapidly mixing. Setting $\lambda = 2^{-100 |G|^3}$ would give you a stationary distribution that has most of its mass on the simple cycles, but which would mix very slowly. You could then try various MCMC techniques to get samples from $S_{ \lambda }$ for small $\lambda$, such as parallel tempering.

   Where to get such functions $f$? One way would be to define $f$ to be $0$ on directed simple cycles, and $1$ on subsets of edges that aren't directed simple cycles. You might be able to cook up better measurements -- e.g. if $f(S)$ grows in the right way as $S$ gets 'farther' from being a directed simple cycle, then the energy landscape of $S_{\lambda}$ might be more favorable to sampling.

   An excellent text for more on the Markov chain sampling paradigm was written by Mark Jerrum "Counting, Sampling and Integrating: Algorithms and Complexity." A draft is available on Jerrum's webpage: http://www.dcs.ed.ac.uk/home/mrj/pubs.html .

An advantage of 1-3 is that you know that you are getting uniform samples if the algorithm terminates. A disadvantage of 4-5 is that you don't know for sure -- there's no perfect test of whether or not a general Markov chain has mixed, so without analytical bounds you can't assert that you are getting samples from the stationary distribution.

Note that because of the aforementioned result from Jerrum-Valiant-Vazirani none of these heuristics will work efficiently and correctly in general, unless basically P = NP. However, they might work on your graph.

Answer 3

Here is what I thought:

1. First we need to define some terms:

$Out(V)$: the set of vertices which is the tail ends adjacent to vertex $V$

$In(V)$: the set of vertices which is the head ends adjacent to vertex $V$

Outdegree $deg^+(V)$: the size of $Out(V)$.

Indegree $deg^-(V)$: the size of $In(V)$.

Deadends: $\{V \mid deg^-(V) = 0 \text{ or } deg^+(V) = 0\}$

$V$ is Unobvious deadend: $\bigwedge_{u \in Out(V) \bigcup In(V)} \{u \text{ is deadend or unobvious deadend}\}$

2. Then we start to get a random cycle:

$Step1$: Calculate $Out(V)$ and $In(V)$ for all vertices. Check and put all the deadends in a set $Deadend$.

$Step2$: Pick a random vertex $V$ from the graph $G$ except $Deadend$, and put it into two queues $OutQueue$ and $InQueue$ to do two BFS searches. And there are also two sets $OutVisited$ and $InVisited$ to store what vertices we have already visited.

$Step3$: Pop the first vertex in $OutQueue$ as $outU$ and $InQueue$ as $inU$. Check whether $inU$ is in $OutVisited$ or $outU$ in $InVisited$, which means we have already find a cycle. If found, go to $Step6$. If not found, then put $outU$ in $OutVisited$ and $inU$ in $InVisited$.

$Step4$: Put all the vertices, which is not deadend and not unobvious deadend, in $Out(outU)$ into $OutQueue$. If all of the vertices in $Out(outU)$ are in $Deadend$, then put $outU$ into $Deadend$, and back to $Step3$. Do the same for $In(inU)$ and $InQueue$.

$Step5$: If $OutQueue$ or $InQueue$ is empty, this means we cannot find a cycle from this vertex $V$, then we put all the visited vertices in $Deadend$. Back to $Step2$ to start a new skimming.

$Step6$: If find a cycle, return this cycle. If all of the vertices are in the $Deadend$, then there's no cycle in this graph.

3. If we get a cycle, reverse the cycle, and find a new random cycle:

Reversing a cycle in the graph G will not change $Out(V)$ and $In(V)$.

And to find a new random cycle, do as the same as mentioned above.

However, there are some problems of this method:

1. This method cannot ensure that every cycles in graph $G$ will be equally picked.

2. I am not sure that only by checking outdegrees and indegrees will not miss a cycle.