Finding Hidden Cliques in Linear Time with High Probability

Introduction

A clique in a graph $G$ is a subset of its vertices any two of which are connected by an edge. The problem of determining the size of the maximum clique in a graph is known to be NP-complete . It has also been proved that assuming P $\neq$ NP, there exists a constant $b>0$ for which it is hard to approximate the size of the maximum clique within a factor of $n^{b}$. Therefore, it is natural to investigate the hardness of this problem in the average case.

The Erdös Rényi random graph model, also denoted $G(n,\tfrac{1}{2})$, is a probability measure on graphs with $n$ vertices. In this model, a random graph is generated by choosing each pair of vertices independently with probability $\tfrac{1}{2}$ to be an edge. It is known that with probability tending to $1$ as $n$ tends to infinity, the size of the largest clique in $G(n,\tfrac{1}{2})$ is $(2+o(1))\log n$. There exists a polynomial time algorithm (see for example ) that finds a clique of size $(1+o(1))\log n$ in $G(n,\tfrac{1}{2})$ with high probability, but even though in expectation $G(n,\tfrac{1}{2})$ contains many cliques of size $(1+\varepsilon)\log n$ for any fixed $0<\varepsilon<1$, there is no known polynomial time algorithm that finds one. It is plausible to conjecture that this problem is computationally hard, and this hardness has been used in several cryptographic applications .

Numerical calculations show that $c_{0}$ is close to $1.65$. For a mathematical definition of $c_{0}$ see Definition 2.2. A refinement of the algorithm that works with high probability for all $c\geq 1.261$ is presented in Sec. 3.1.

Since , there have been many papers describing algorithms that solve various variants of the hidden clique problem. In an algorithm for finding hidden cliques of size $\Omega(\sqrt{n})$ based on the Lovász theta function is given, that has two advantages. The first is being able to find the clique also in a semi-random hidden clique model, in which an adversary can remove edges that are not in the clique, and the second is being able to certify the optimality of its solution by providing an upper bound on the size of the maximum clique in the graph.

McSherry gives an algorithm that solves the more general problem of finding a planted partition. In the random graph model described there, we are given a graph where the vertices are randomly partitioned into $m$ classes, and between every pair of vertices where one is in class $i$ and the other in class $j$ there is an edge with probability $p_{ij}$. With the appropriate parameters, this model can be reduced both to the hidden clique model and to the hidden dense graph model that we describe in Sec. 3.2. For both these cases, the result is a polynomial time algorithm that finds the hidden clique (dense graph) with high probability for $k=c\sqrt{n}$.

Several attempts have been made to develop polynomial time algorithms for finding hidden cliques of size $k=o(\sqrt{n})$, so far with no success. For example, Jerrum described the Metropolis process and proved that it cannot find the clique when $k=o(\sqrt{n})$. Feige and Krauthgamer explain why the algorithm described in fails when $k=o(\sqrt{n})$. Frieze and Kannan give an algorithm to find a hidden clique of size $k=\Omega\left(n^{1/3}\log^{4}n\right)$, however, the algorithm maximizes a certain cubic form, and there are no known polynomial time algorithms for maximizing cubic forms. In Sec. 2.1.3 we give an algorithm that finds the hidden clique when we are given a small part of it by an oracle or an adversary. We prove, that for any $k=\omega(\log n\log\log n)$, knowing only $\log n+1$ vertices of the hidden clique enables us to find the rest of them with high probability. For smaller $k$’s, $\log n+1$ is not enough, but $(1+\varepsilon)\log n$ is.

There are many problems in different fields of computer science that are related to the hidden clique problem. Among others, there are connections to cryptography, testing and game theory. For connections to cryptography, see for example where an encryption scheme based on hiding an independent set in a graph is described or where the function whose input is a graph $G$ and a set $K$ of $k$ vertices and whose output is $G$ with a clique on $K$ is proposed as a one way function for certain values of $k$. For connections to testing, see where Alon et al. prove that if there is no polynomial time algorithm to find hidden cliques of size $t>\log^{3}n$ then there is no polynomial time algorithm that can test $k$-wise independence of a distribution even when given a polynomial number of samples from it, for $k=\Theta(\log n)$. For connections to game theory, see , where Hazan and Krauthgamer prove that if there is a polynomial time algorithm that finds a Nash equilibrium of a two player game whose social-welfare is close to the maximum, then there is a randomized polynomial time algorithm that finds the hidden clique for $k=O(\log n)$. The hidden clique model is also related to the planted-SAT model and some models in computational biology .

Proof of Thm. 1.1

Throughout the paper we use the following notations.

Given a graph $G=(V,E)$, for every $v\in V$ and $S\subseteq V$ we denote by $d_{S}(v)$ the number of neighbors $v$ has in $S$. Formally,

All logarithms in the paper are base $2$.

We use the shorthand “whp($f(n)$)” to mean: “with probability at least $1-f(n)$”.

Given $0<\alpha<1$ and $\beta>0$, we define

Follows directly from Thm. A.3, by setting $t=n^{1-\varepsilon_{1}}$ for the bound on $|S_{0}|$ and $t=k^{1-\varepsilon_{2}}$ for the bound on $|S_{0}\cap K|$. ∎

Assume that the events $|S_{0}|=(1+o(1))\alpha n$ and $|S_{0}\cap K|=(1+o(1))\alpha k$ both occur. By Lemma 2.5 this happens with high probability. We can now apply Cor. A.4 twice.

For the vertices in $\left(V\setminus S_{0}\right)\setminus K$, the result follows directly from Cor. A.4 by setting $\varepsilon=\varepsilon_{1}$. For $v\in\left(V\setminus S_{0}\right)\cap K$, having $d_{S_{0}}(v)\geq\tfrac{1}{2}\alpha n+\beta\tfrac{\sqrt{\alpha n}}{2}$ is equivalent to having

So setting $\varepsilon=\varepsilon_{2}$ in Cor. A.4, gives that

In order to get a success probability that tends to $1$, we need to bound the sum of the probabilities of failing in each iteration by $o(1)$. We refer the reader to Sec. 2.2 for a detailed analysis of the failure probability of the algorithm.

1.2 Proving the correctness of the second phase of the algorithm

We start by bounding the probability that a hidden clique of size $k$ contains the $k$ largest degree vertices in the graph.

Define $x=\tfrac{1}{4}k$. Then by Thm. A.3

1.3 Proving the correctness of the third phase of the algorithm

In order to prove that $K^{*}$ is the hidden clique with high probability, we prove a more general Lemma. We prove that if an adversary reveals a subset of the clique that is not too small, we can use it to find the whole clique.

$k=O(\log n\log\log n)$ and $s\geq(1+\varepsilon)\log n$ for some $\varepsilon>0$, or

$k\geq\omega(\log n\log\log n)$ and $s\geq\log n+1$.

Consider an arbitrary subset of $K$ of size $s$. The probability that its vertices have at least $l_{0}$ non-clique common neighbors can be bounded by $\sum_{l=l_{0}}^{n-k}n^{l}2^{-sl}$. Taking union bound over all subsets of size $s$ of $K$ gives that the probability that there exists a subset with at least $l_{0}$ non-clique common neighbors is bounded by

If $k=\omega(\log n\log\log n)$ then letting $s=\log n+1$ gives l_{0}=2\big{(}\log n+\log n\log k+\log k\big{)}. Clearly, $\log n+\log k=o(k)$. To see that $\log n\log k=o(k)$, denote $k=\log nf(n)$ where $f(n)=\omega(\log\log n)$. Then \log n\log k=\log n\big{(}\log\log n+\log\big{(}f(n)\big{)}\big{)}. Clearly, $\log n\log(f(n))=o(\log nf(n))$, and from the definition of $f(n)$ we also have $\log n\log\log n=o(\log nf(n))$.

If $k\leq O(\log n\log\log n)$, then letting $s\geq(1+\varepsilon)\log n$ for some small $\varepsilon>0$ is enough, since then $l_{0}=\tfrac{2}{\varepsilon}+\tfrac{2(1+\varepsilon)}{\varepsilon}\log k=o(k)$. ∎

2 Bounding the failure probability

For any choice of $0<\varepsilon_{1},\varepsilon_{2}<\tfrac{1}{2}$ and $0<\varepsilon_{4}<\tfrac{1}{a}$, denote

Refinements

The subset of $S_{i}$ that we use in this variation is the set of all vertices $v\in S_{i}$ that have $d_{S_{i}}(v)\geq\tfrac{1}{2}|S_{i}|+\eta\tfrac{\sqrt{|S_{i}|}}{2}$, for some $\eta>0$. Since these degrees are not independent we cannot use the same concentration results we used before, so we first prove the following concentration result.

Let G\in G\big{(}n,\tfrac{1}{2}\big{)} and $a,c^{\prime}>0$. Define a random variable

Then for every $0<\varepsilon^{\prime}<\tfrac{1}{4}$ it holds that

For every $v\in V(G)$ define a random variable

Thus, we need to calculate the concentration of $F$ and $G$. Both are edge exposure martingales with Lipschitz constant $\tfrac{2}{\varepsilon\sqrt{n}}$. Therefore, by Azuma’s inequality (see, for example ) we get:

Choosing $\lambda=c^{\prime}n^{-\varepsilon^{\prime}}$ and $\varepsilon=\tfrac{1}{2}\sqrt{2\pi}c^{\prime}n^{-\varepsilon^{\prime}}$ concludes the proof. ∎

2 Finding hidden dense graphs in G​(n,p)𝐺𝑛𝑝G(n,p)

Define the random graph model $G(n,p,k,q)$ for $0<p<q<1$. Given a set of $n$ vertices, randomly choose a subset $K$ of $k$ vertices. For every pair of vertices $(u,v)$, the edge between them exists with probability $p$ if at least one of the two vertices is in $V\setminus K$, and with probability $q$ if they are both in $K$. The model discussed in the previous sections is equivalent to G\big{(}n,\tfrac{1}{2},c\sqrt{n},1\big{)}.

To prove Thm. 3.4, as in the hidden clique case, we first prove the correctness of each of the phases of the algorithm, and then bound the failure probability. To prove the correctness of the first phase, we prove Lemmas B.1 and B.2, which are analogous to Lemmas 2.4 and 2.6. To prove the correctness of the second phase, we prove Lemma B.3 and Cor. B.4, which are analogous to Lemma 2.7 and Cor. 2.8. To prove the correctness of the third phase we prove Lemma B.5. The failure probability follows as in Lemma 2.10 by noticing that substituting $c\tfrac{\sqrt{p(1-p)}}{q-p}$ for $c$ in the definition of $\rho^{\prime}$ gives the exact definition of $\rho$.

Discussion

Our results bring up some interesting questions for future research. For example, one of the advantages of the algorithm presented here is a failure probability that is less than polynomially small in the size of the input. Experimental results shown in suggest that the failure probability of the algorithm described there may also be $o(1)$. Whether the analysis can be improved to prove this rigorously is an interesting open question. One can also ask whether the analysis in can be improved to show failure probability that is less than polynomially small.

Aside from the most interesting open question of whether there exists an algorithm that finds hidden cliques for $k=o(\sqrt{n})$, one can ask about ways to find hidden cliques of size $k=c\sqrt{n}$ as $c$ gets smaller. In , Alon, Krivelevich and Sudakov give a way to improve the constant for which their algorithm works, at the expense of increasing the running time. This technique can be used for any algorithm that finds hidden cliques, so we describe it here. Pick a random vertex $v\in V$, and run the algorithm only on the subgraph containing $v$ and its neighborhood. $v$ is a clique vertex, then the parameters of the algorithm have improved, since instead of having a graph with $n$ vertices and a hidden clique of size $c\sqrt{n}$ we now have a graph with $\tfrac{n}{2}$ vertices and a hidden clique of size $c\sqrt{n}$. The expected number of trials we need to do until we pick a clique vertex is $O(\sqrt{n})$. This means that if we have an algorithm that finds a hidden clique of size $c\sqrt{n}$, where $c\geq c_{0}$, we can also find a hidden clique for $c\geq\tfrac{c_{0}}{\sqrt{2}}$, while increasing the running time by a factor of $\sqrt{n}$. If we wish to improve the constant even further, we can pick $r$ random vertices and run the algorithm on the subgraph containing them and their common neighborhood. This gives an algorithm that works for constants smaller by up to a factor of $2^{r/2}$ than the original constant, at the expense of increasing the running time of the algorithm by a factor of $n^{r/2}$.

We have described a sequence of algorithms whose running times increase by factors of $\sqrt{n}$. It is not known whether the constant can be decreased if we can only increase the running time by a factor smaller than $\sqrt{n}$.

Given an algorithm that runs in time $O(n^{2})$ and finds hidden cliques of size $c\sqrt{n}$ for any $c\geq c_{0}$, is there an algorithm that runs in time $O(n^{2+\varepsilon})$, where $\varepsilon<\tfrac{1}{2}$, and finds hidden cliques of size $c\sqrt{n}$ where $c<c_{0}$? How small can $c$ be as a function of $\varepsilon$?

References

Appendix A Concentration inequalities

Throughout the paper, we use the central limit theorem for binomial random variables, and its rate of convergence that was independently discovered by Berry in 1941 and by Esseen in 1942 . For details, see, for example [9, §Sec. 3.4.4].

Let $S=X_{1}+\cdots+X_{n}$ where the $X_{i}$’s are independent Bernoulli random variables. Then for every $t>0$

Then for every $c^{\prime}>0$ and $0<\varepsilon<\tfrac{1}{2}$ it holds that

where the last inequality holds because \tfrac{n_{1}}{\sqrt{n_{2}}}\leq O\big{(}\sqrt{n_{1}}\big{)}=o(n_{1}^{1-\varepsilon}). ∎

Appendix B The G​(n,p,k,q)𝐺𝑛𝑝𝑘𝑞G(n,p,k,q) case

The proof is identical to the proof of Lemma 2.4. ∎

Follows from Cor. A.4 the same way as in the proof of Lemma 2.6. ∎

Let $G\in G(n,p,k,q)$ where $k\geq c_{0}\sqrt{n\log n}$. Denote the hidden dense graph by $K$ and the set of $k$ largest degree vertices by $M$. Then

Define $x=\tfrac{1}{2}(q-p)k$. Then by Thm. A.3

$k=O(\log n\log\log n)$ and s\geq\big{(}\tfrac{2}{(q-p)^{2}}+\varepsilon\big{)}\ln n for some $\varepsilon>0$, or

$k\geq\omega(\log n\log\log n)$ and $s\geq\tfrac{2}{(q-p)^{2}}\ln n+1$.