Brief Announcement: Congested Clique Counting for Local Gibbs Distributions

Our central contribution is an algorithm to draw many samples at once from the distributed Metropolis-Hastings Markov chain. Beyond counting, this result may be useful in other algorithms where several samples are needed.

As a corollary to the previous theorem and the results of [10], under mild locality and mixing conditions which we will describe later, there is an $\tilde{O}\left(\frac{n^{1/3}}{{ϵ}^2}\right)$ round counting algorithm. As the most interesting example, we obtain a fast algorithm for approximating the number of q-colorings of an input graph with degree $\mathrm{\Delta }$. In addition, our full paper demonstrates a much faster algorithm for the hardcore model with low fugacity.

We also give a conditional lower bound for approximating a partition function, Theorem 10. Even under our locality and mixing assumptions, counting when $ϵ\le \frac{1}{32n^2}$ is as hard as triange detection.

Consider a traditional graph labeling problem, where each vertex receives a label from some underlying alphabet $𝒜$. We focus on randomly sampling from a subset, $𝒮$, of such labelings, given a distribution. In particular, we want to sample from a Gibbs distribution. Borrowing terminology from physics, we have the Hamiltonian, a function $H:𝒮\to \{0,1,\mathrm{\dots },h\}$, for some integer $h\ge 0$.

In the trivial case, if we choose $H=0$, we get a uniform distribution over $𝒮$.

We will make the assumption that $|𝒜|$ and $h$ are bounded by a polynomial in $n$. This is not a significant restriction and is necessary both algorithmically and to ensure messages are of size $O(\log n)$.

For this paper we will focus heavily on the well studied Potts model.

Note that when $\beta =\mathrm{\infty }$, the Potts model simply becomes the uniform distribution over proper colorings.¹¹1We treat the infinite case in the sense of the limit as $\beta \to \mathrm{\infty }$. Furthermore, $Z(\mathrm{\infty })$ counts the number of proper colorings. On the other hand, when $\beta =0$, the model is uniform over all proper and improper colorings. Then $Z(0)=q^n$. More precisely, when $\beta >0$, this model is called the antiferromagnetic Potts model, since neighboring vertices favor not having the same color.

We would now like to estimate $Z(\beta )$, for a given choice of $\beta$. We call this the generalized counting problem, as $Z$ gives the weighted count over all labelings. As discussed in the introduction, it is often sufficient to take $\tilde{O}(\frac{n}{{ϵ}^2})$ samples. More precisely, the result from Liu, Yin, and Zhang [10] is summarized by the next theorem.

The theorem implies that we can approximate $Z(\beta )$, as long as $Z({\beta }^{\prime })$ is known in advance for some ${\beta }^{\prime }\ge 0$ and that we can draw $\tilde{O}(\frac{n}{{ϵ}^2})$ samples for inverse temperatures in the range $[\min (\beta ,{\beta }^{\prime }),\max (\beta ,{\beta }^{\prime })]$.

The traditional way to sample from a Gibbs distribution is using a rapidly mixing Markov chain. We begin from an arbitrary state (a graph labeling) and simulate transitions until the chain is mixed, meaning that the current state is roughly drawn from the desired distribution. Here we will focus on sampling from the probability space defined by a pairwise Markov random field. A pairwise Markov random field on a graph consists of vertex constraints and edge constraints.

For each vertex $v$, we have a constraint $b_v:𝒜\to {ℝ}_{\ge 0}$. For each edge $e=(u,v)$ we also have a constraint $A_e:𝒜\times 𝒜\to {ℝ}_{\ge 0}$. Here the edges are undirected, but the function $A_e$ is not necessarily symmetric. The probability of graph vertex labeling $l$ is defined to be proportional to

The third condition is needed to initialize the Markov chain.

Feng, Sun, and Yin [5] found a preliminary distributed Markov chain to sample from pairwise Markov random fields. In the case of $q$-colorings, this was improved simultaneously by Fischer and Ghaffari [6] and Feng, Hayes, and Yin [4]. The improved chain can be generalized beyond colorings, see [11] by Pemmaraju and Sobel for the chain explicitly given in full generality. One transition of the chain, for some yet to be determined probability $p$, is defined in the following pseudocode. Every vertex $v$ has its current label $X_v$. For ease of notation, in the edge acceptance step, any fraction that is not well defined (because certain vertices may not be active) equals $1$. Note that on some pairwise Markov random fields this chain may have a very large mixing time, $\gg \log n$ and possibly infinite.

For the Potts model, the distributed Metropolis-Hastings Markov chain has a mixing time of $O(\log \frac{n}{\delta })$. As the proof technique is standard, we defer the proof to the appendix of the full version of our paper.

We would now like to estimate the partition function of a local Gibbs distribution. As described earlier, we need to know the Hamiltonian of $k=\tilde{O}(\frac{n}{{ϵ}^2})$ samples from the Gibbs distribution. This can be found by running $k$ instances of the distributed Metropolis-Hastings Markov chain. We can simulate one transition of $n$ instances of the chain in parallel.

We can show that even in the case where the distributed Metropolis-Hastings chain has mixing time $O(\log \frac{n}{\delta })$, we still have conditional hardness results.

Consider the following Gibbs distribution. $𝒜=V\cup [3n]$. $𝒮$ are the labelings such that every vertex’s label is either in $[3n]$ or is a neighboring vertex. We let the Hamiltonian count the number of edges $\{u,v\}$ such that the labels of $u$ and $v$ are the same vertex. It is not hard to show that this is a local Gibbs distribution and that the mixing time of the distributed Metropolis-Hastings chain is $O(\log \frac{n}{\delta })$ for $\beta \ge 0$.

As always, when $\beta =0$, all labelings in $𝒮$ are equally likely. $Z(0)={\prod }_{v}3n+\mathrm{deg}(v)$. On the other hand, when $\beta =\mathrm{\infty }$, we remove labelings where two neighboring vertices are labeled the same mutually neighboring vertex. This can only happen if there is a triangle in the graph. Thus, $Z(0)>Z(\mathrm{\infty })$ if and only if there is a triangle in the graph. In fact, if the graph has at least one triangle, $a,b,c$, then $1-\frac{Z(\mathrm{\infty })}{Z(0)}\ge \frac{1}{16n^2}$, since that is a lower bound on the probability that vertices $a$ and $b$ both choose $c$ in a uniform random labeling. Rearranging, $Z(\mathrm{\infty })\le Z(0)(1-\frac{1}{16n^2})\le Z(0){(1-\frac{1}{32n^2})}^2$.

Note that we can easily compute $Z(0)$ exactly. We can choose $ϵ=\frac{1}{32n^2}$ and take an approximate count of $Z(\mathrm{\infty })$, $\overline{Z}$. Suppose the graph doesn’t have a triangle. Then, $Z(\mathrm{\infty })=Z(0)$. Thus, $\overline{Z}\ge (1-\frac{1}{32n^2})Z(0)$. Otherwise, the graph has a triangle. Then, . Thus, we can use $\overline{Z}$ to determine if the graph has a triangle.

Note that the best known algorithm for triangle detection takes $O(n^{0.157})$ rounds [2, 14].