A simple SVD algorithm for finding hidden partitions

Van Vu

The problem and a new algorithm

The hidden partition problem is the following: let $X$ be a set of $n$ vertices with a partition $X=\cup_{i=1}^{k}X_{i}$ ; for all $1\leq i\leq j\leq n$ and any $x\in X_{i},y\in X_{j}$ , we put a random edge between $x$ and $y$ with probability $p_{ij}$ . Given one such random graph, the goal is to recover the sets $X_{i}$ . This problem is of importance in computer science and statistics and contains as special cases several well-studied problems such as the hidden clique, hidden bisection, hidden coloring, clustering etc (see, for instance, and the references therein). In what follows, we refer to $X_{i}$ as clusters.

In an influential paper , Mc Sherry provided a (randomized) polynomial time algorithm that solves the general hidden partition problem for a large range of parameters. As corollary, he derived several earlier results obtained for special cases.

The general idea (and in many earlier works on clustering) is to find a good geometric representation of the vertices. We say that a representation is perfect if there is a number $r>0$ such that

Vertices in the same cluster have distance at most $r$ from each other.

Vertices from different clusters have distance at least $4r$ from each other.

Once a perfect representation is obtained, it is easy to find the clusters. If $r$ is known, then the solution is obvious. If $r$ is not known, then there are several simple algorithms. For instance, one can create a minimal spanning tree (with respect to the distances) on the vertices and then remove the largest $k-1$ edges. In what follows, we put all these simple algorithms under a subroutine called Clustering by Distances and the reader can choose his/her favorite to implement. Our main goal is to present a simple way to obtain a perfect representation.

In the rest of the paper, let $s_{u}:=|X_{i}|$ if $u\in X_{i}$ and $s:=\min_{u\in X}s_{u}=\min_{i}|X_{i}|$ . We assume that $n$ is sufficiently large, whenever needed. Asymptotic notation are used under the assumption $n\rightarrow\infty$ . All explicit constants (such as the $4$ above) are adhoc and we make no attempt to optimize them.

Let $P$ be the probability matrix $(p_{ij})_{1\leq i,j\leq n}$ . For a vertex $u\in X$ , ${\mathbf{u}}$ denotes the corresponding column in $P$ . Define

where the minimum is taken over all pairs $u,v$ belonging to different clusters. Mc Sherry proved

Assume that $\sigma^{2}\gg\log^{6}n/n$ is an upper bound on the variances of the entries. There is a constant $C>0$ such that if

the above algorithm (with a proper choice of the threshold $\tau$ ) recovers the partition with probability $1-\epsilon$ with respect to the random graph and $k^{-1}$ with respect to the auxiliary random bits.

The main open question raised by Mc Sherry in is to find a more natural and simpler algorithm, which does not involve the subroutine CPROJ (see [24, Section 4.4]). The goal of this paper is to answer this question.

To this end, $M_{k}$ denotes the subspace spanned by the first $k$ left singular vectors of a matrix $M$ . Let $\hat{P}$ be our input, namely the adjacency matrix of a random graph generated by $P$ . Arguably, the most natural choice for $H$ would be $\hat{P}_{k}$ (SVD), which leads to the algorithm below

While SVD I could well win the contest for being the simplest algorithm, it is not easy to analyze in the general case. In what follows, we analyze a slightly more technical alternative, SVD II, which is a variant of an algorithm proposed in [24, Section 1].

Compared to SVD I, the extra steps in SVD II are the random partitions in Step $(0)$ done in order to reduce the correlation. (A careful reading of reveals that one also need an extra partition in Algorithm 2 to make the analysis go through.)

Notice that SVD II gives a partition of $Y_{2}$ , not $X$ . There are many ways to extend it to a partition of $X$ . For instance, we can run the algorithm $l$ times (for some small $l$ ) and find partitions of $Y_{2}^{1},\dots,Y_{2}^{l}$ , where $Y_{2}^{i}$ are random subsets of $X$ with density $1/4$ (the input graph is the same, only the random partitions are different). If a cluster $C$ in $Y_{2}^{i}$ and a cluster $C^{\prime}$ in $Y_{2}^{i^{\prime}}$ intersect, then they must belong to the same cluster in $X$ and we can merge them. If we choose $l=3\log n$ , say, then with probability $1-o(n^{-1})$ , all vertices of $X$ must belong to some $Y_{2}^{i}$ and we recover the clusters $X_{1},\dots,X_{k}$ at the end. We can also first find the partitions of $Y_{1},Y_{2}$ and $Z_{1},Z_{2}$ by reversing the role of $Y_{1}$ and $Y_{2}$ and $Y$ and $Z$ and find which four clusters must belong to an original cluster by looking at the edge densities; we omit the details.

Beside being simple, SVD II is also very convenient to implement, as its main step, the computation of the projection onto $\hat{A}_{k}$ (given $\hat{A}$ as input) is a routine operation (SVD) which appears in most standard mathematical packages.

Let us now analyze SVD II. For convenience, we assume that $P$ has rank $k$ . The general case when $P$ can have a smaller rank is discussed later. Let $\lambda$ be the least non-trivial singular value of $P$ .

There is a constant $C>0$ such that the following holds. Assume that $\sigma^{2}\geq C\frac{\log n}{n}$ and $s\geq C\log n,k=o((n/\log n)^{1/2})$ . Then SVD II clusters $Y_{2}$ correctly with probability $1-o(n^{-1})$ if one of the following two conditions is satisfied

Condition 1. $\Delta\geq C(\sigma\sqrt{\frac{n}{s}}+\sqrt{\log n}).$

Condition 2. $\Delta\geq C(\sigma\sqrt{\frac{n}{s}}+\sigma\sqrt{k\log n}+\frac{\sigma\sqrt{nk}}{\lambda})$

If we omit the assumption $s\geq C\log n$ , the statement still holds but with probability

The lower bound $\sigma^{2}\geq C\log n/n$ is optimal, up to the value of $C$ . If $\sigma^{2}<\log n/n$ , then there are many isolated points, which can be assigned to any cluster.

We can reduce the failure probability $O(n^{-1})$ to $O(n^{-K})$ for any constant $K$ at the cost of increasing the constant $C$ .

Let us now consider the performance of SVD II on various subproblems. We allow the value of $C$ to be flexible in order to omit smaller order terms for convenience. It is instructive to compare the corollaries below with Corollaries 1,2,3 from .

Hidden clique. In this problem, $k=2$ , $s$ is the size of the clique, and $\Delta=(1-p)\sqrt{s}$ , where $p$ is the density of the random graph. Condition 1 becomes

which is satisfied if $s\geq C(\sqrt{np}+\sqrt{\log n})$ . As $np=\Theta(\sigma^{2}n)=\Theta(\log n)$ , this simplifies to $s\geq C\sqrt{np}$ .

There is a constant $C$ such that for any $p\geq C\frac{\log n}{n}$ and $s\geq C\sqrt{np}$ , SVD II finds the hidden clique of size $s$ with probability $1-o(1)$ .

Hidden Coloring. Here $k$ is the number of color classes, each has size $n/k$ ; $\Delta=p\sqrt{2n/k}$ ; $s=n/k$ ; $\sigma^{2}=p(1-p)$ . The singular values of $P$ are $\frac{k-1}{k}n,\frac{1}{k}n,\dots,\frac{1}{k}n$ . If $p\geq 1/k$ , Condition 1 is

which is satisfied for $k=o((n/\log n))^{1/3})$ .

If $p<1/k$ , then the bound $\lambda\geq\sigma\sqrt{ns}$ holds, and the $\Delta$ bound in Condition 2 is

which is satisfied if $p\geq C\frac{k^{3/2}\log n}{n}$ .

There is a constant $C$ such that the following holds. For any $k=o((n/\log n)^{1/3}$ and edge density $.99>p\geq C\frac{k^{3/2}\log n}{n}$ , SVD II finds the hidden $k$ -coloring with probability $1-O(n^{-1})$ .

Hidden Bipartition. Let the two densities be $.99\geq p>q>0$ . We have $k=2$ , $\Delta=|p-q|n^{1/2}$ , $s=n/2$ , $\sigma^{2}=\Theta(p)$ . The two singular values of $P$ are $(p+q)n$ and $(p-q)n$ . Condition 2 requires $\frac{p-q}{p^{1/4}}\geq C\sqrt{\frac{\log n}{n}}.$

There is a constant $C$ such that the following holds Let $.99>p>q\geq C\log n/n$ be edge densities such that $\frac{p-q}{p^{1/4}}\geq C\sqrt{\frac{\log n}{n}}$ then SVD II finds the hidden bipartition with probability $1-o(n^{-1})$ .

One can replace $p^{1/4}$ in the denominator by a better term $p^{1/2}$ by considering an approximate algorithm; see Corollary 11.

The rest of the paper is organized as follows. In the next section, we present a few technical lemmas and prove Theorem 2 and Theorem 10 in Section 3. In Section 4, we discuss variants of SVD II, including an approximate version which works under weaker assumptions.

Technical lemmas

Furthermore, if $H$ has an orthornormal bases $v_{1},\dots,v_{d}$ such that $\max_{1\leq i\leq d}\|v_{i}\|_{\infty}\leq\alpha$ , then

There is a constant $C_{0}>0$ such that the following holds. Let $E$ be a symmetric matrix whose upper diagonal entries $e_{ij}$ are independent random variables where $e_{ij}=1-p_{ij}$ or $-p_{ij}$ with probabilities $p_{ij}$ and $1-p_{ij}$ , respectively, where $0\leq p_{ij}\leq 1$ . Let $\sigma^{2}:=\max_{ij}p_{ij}(1-p_{ij}$ . If $\sigma^{2}\geq C_{0}\log n/n$ , then

If $\sigma^{2}\geq\frac{\log^{4}n}{n}$ , the statement is a corollary of [26, Theorem 1.4]. For smaller $\sigma$ , one can prove this lemma using the $\epsilon$ -net approach by Kahn and Szemeredi . We omit the details, which is very similar to the proof of Feige and Ofek for [14, Theorem 1.1].

Let $M,N$ be matrices where $\delta:=\lambda_{k}(M)-\lambda_{k+1}M>0$ . Then

This lemma is a well known result in numerical linear algebra, known as Davis-Kahan-Wedin theorem; see .

Proof of Theorems 2

Let $A$ be the probability matrix $p_{ij}$ corresponding to $\hat{A}$ . As $A$ is a large random submatrix of $P$ , it is not hard to show that $\lambda_{k}(A)=\Theta(\lambda_{k}(P))$ with high probability (we provide a verification of this fact at the end of the proof). In the rest of this proof, we assume

We view the adjacency matrix $\hat{A}$ (between $Y_{1}$ and $Z$ ) as a random perturbation of $A$ , $\hat{A}:=A+E$ , where the entries $e_{ij}$ of $E$ are independent and $e_{ij}=1-p_{ij}$ with probability $p_{ij}$ and $-p_{ij}$ with probability $1-p_{ij}$ . We denote by $\hat{\mathbf{u}},{\mathbf{u}},e_{u}$ the columns corresponding to a vertex $u$ in $\hat{A},A,E$ , respectively. All matrices are of size approximately $n/2\times n/4$ by the definitions of $Y,Z$ and $Y_{1},Y_{2}$ .

Our leading idea is that the random perturbation $E$ does not change $A_{k}$ too much, thus hopefully the projections onto $\hat{A}_{k}$ and $A_{k}$ differ by only a small amount. The heart of the matter, of course, is to bound this error term. While inviting, a straightforward application of Lemma 9 is too crude in the general case (it does lead to some simple solution for some subproblems in certain range of parameters). We will still make use of this lemma, but for a quite different purpose.

For simplicity, we assume in the rest of the proof that $s\geq C\log n$ . For a sufficiently large $C$ , this implies that with probability $1-o(n^{-1})$ , each cluster $X_{i}$ intersects $Z$ in at least $|X_{i}|/3$ elements. Thus, the distance between two columns (belonging to different clusters) in $A$ is at least $\Delta/3$ . We aim to show that with high probability $\|P_{\hat{A}_{k}}\hat{\mathbf{u}}-{\mathbf{u}}\|<\Delta/12$ for all $u\in Y_{2}$ ; this will provide a perfect geometric representation. If there is no lower bound on $s$ , then the probability that the random partition has this property is at least $1-c\sum_{i=1}^{k}e^{-|X_{i}|/c}$ for some constant $c>0$ .

For a fixed $u$ , by the triangle inequality

To bound the second term, we follow an argument from and consider

The spectral norm of the first term is $\lambda_{k+1}(A_{k})\leq\lambda_{k+1}(A)+\|E\|=\|E\|$ , as $A$ has rank at most $k$ . The spectral norm of the second term is also at most $\|E\|$ . Thus, by Lemma 8, by probability at least $1-n^{-3}$

Let $\chi_{u}$ be the unit vector $s_{u}^{-1/2}{\mathbf{I}}_{u}$ where ${\mathbf{I}}_{u}$ is the indicator vector for the cluster containing $u$ , we have

Combining the last two inequalities and using the union bound, we conclude that with probability at least $1-n^{-2}$

Now we tend to the first term, whose analysis is more involved. By the first part of Lemma 7,

with probability $1-o(n^{-2})$ , for a properly chosen constant $C_{1}$ . As $sk\leq n$ , the term $\sigma k^{1/2}$ is at most $\sigma\sqrt{n/s}$ and can be omitted. This yields that if

then the algorithm succeeds with probability at least $1-o(n^{-1})$ . This proves the first part of the theorem concerning Condition 1.

To prove the second part of the theorem, let us reconsider the distance $P_{\hat{A}_{k}}e_{u}$ . Notice that if $s\leq 10k\log n$ , then Condition 2 implies Condition 1 (with some modification on the value of $C$ ). Thus, in what follows, we can assume $s\geq 10k\log n$ .

Rewrite $\hat{A}=A+E$ and let $v$ be a singular vector of $A$ . Recall that $|X_{i}\cap Z|\geq\frac{1}{3}|X_{i}|=s_{i}/3$ for all $i$ By symmetry, each coordinate in $v$ is repeated at least $s/3$ times, thus $\|v\|_{\infty}\leq 2s^{-1/2}$ . Furthermore, by Lemma 9 and Lemma 8, we have with probability $1-o(n^{-2})$ that

which implies that for any unit vector $v\in\hat{A}_{k}$ ,

by the condition on $\lambda$ , with some properly chosen constant $C_{0}^{\prime}$ . Using the second part of Lemma 7, we conclude that with probability $1-o(n^{-2})$ , $\|P_{\hat{A}_{k}}e_{u}\|\leq C(\sigma k^{1/2}+s^{-1/2}\log n)$ for all $u$ and some properly chosen constant $C$ , concluding the proof.

To make the argument precise, we need to remove the assumption $|X_{i}\cap Y|=|X_{i}|/2$ . Using (3), we can create a matrix $P^{\prime}$ such that

Variants

In the case $\operatorname{rank}A=l<k$ , it makes more sense to project onto $\hat{A}_{l}$ rather than onto $\hat{A}_{k}$ ; the rest of the algorithm and analysis remains the same.

If we do not know either $k$ or $l$ in advance. we can modify SVD II slightly as follows. The idea is to define the essential rank of $\hat{A}$ to be the largest index $l$ such that $\lambda_{l}(\hat{A})\geq C_{3}\sigma n^{1/2}$ , for a properly chosen $C_{3}$ , and replace the projection onto $\hat{A}_{k}$ by the projection onto $\hat{A}_{l}$ . After redefining $\lambda:=\lambda_{l}P$ , the content of Theorem 2 remains the same. Its proof also remains the same, expect few nominal changes. The error term caused by smaller singular values is not going to effect the final conclusion.

The only information we need in SVD II (using essential dimension) is the value of $\sigma$ . Even if this information is not known, we can still solve the problem by considering a sequence of $O(\log n)$ trials with $\sigma_{1}=\frac{\log n}{\sqrt{n}},\sigma_{i}=2\sigma_{i-1}$ and run SVD II in each case. Each trial will output a clustering and it is easy to decide which one is correct by considering the degree densities of the vertices from one cluster to the others.

2. An approximate Solution.

In practice, one is often satisfied with an approximate solution. We say that a partition $X=\cup_{i=1}^{k}X_{i}^{\prime}$ is $\epsilon$ -correct if $|X_{i}\backslash X_{i}^{\prime}|\leq\epsilon|X_{i}|$ . Similarly, we say that a geometric representation of $X$ is $\epsilon$ -perfect if there are points $x_{1},\dots,x_{k}$ with distance at least $4r$ from each other so that at least $(1-\epsilon)|X_{i}|$ points from $X_{i}$ has distance at most $r$ to $x_{i}$ . One can use an $\epsilon$ -perfect representation to find an $\epsilon$ -correct partition.

Given $\epsilon>0$ , there is a constant $C>0$ such that the following holds. If $\sigma^{2}\geq C\frac{\log n}{n}$ and

then with probability $1-o(n^{-1})$ the projection in SVD II produce an $(1-\epsilon)$ -perfect representation of the point sin $Y_{2}$ .

It is worth mentioning that in various situations, an $\epsilon$ -correct partition can be upgraded to a fully correct one by a simple “correction” procedure, as shown in the following example:

Hidden bipartition. Assume $p>q$ . Let $X=X_{1}^{\prime}\cup X_{2}^{\prime}$ be an $\epsilon$ -correct partition, for some small $\epsilon$ (say $\epsilon=.1$ ). Then both $X_{i}^{\prime}$ have size at most $\frac{1}{2}(1-\epsilon)n$ . Assume $|X_{i}\backslash X_{i}^{\prime}|\leq\epsilon n/2$ ; it follows that $|X_{1}^{\prime}\backslash X_{1}|\leq\epsilon n$ . With probability $1-n^{-2}$ , the following holds. For any $u\in X$ , let $d_{u}$ be the number of its neighbors in $X_{1}^{\prime}$ . If $u\in X_{1}$ , then

It is clear that if $(p-q)\geq 30\sqrt{\frac{p\log n}{n}}$ , then $D_{1}>D_{2}$ . Thus, one can correct the partition by defining $X_{1}$ be the set of $n/2$ vertices $u$ with largest $d_{u}$ .

There is a constant $C$ such that the following holds Let $.99>p>q\geq C\log n/n$ be edge densities such that $\frac{p-q}{p^{1/2}}\geq C\sqrt{\frac{\log n}{n}}$ then the approximation algorithm with correction finds the hidden bipartition with probability $1-o(n^{-1})$ .

Proof of Theorem 10. We first bound $\|P_{\hat{A}_{k}}e_{u}\|$ . Recall that

By Markov’s inequality, it follows that ${\mathbf{P}}(\|P_{\hat{A}_{k}}e_{u}\|\geq K\sigma k^{1/2})\leq K^{-2}$ . We call a vertex $u$ good if $\|P_{\hat{A}_{k}}e_{u}\|\leq K\sigma k^{1/2}$ . For a sufficiently large $C$ (depending on $K$ ), all good vertices will be clustered correctly. Moreover, choosing $K\geq 2\epsilon^{-1/2}$ , the probability for $u$ being good is at least $1-\epsilon/4$ , thus the expectation of the number of good elements in $X_{i}$ is at least $|X_{i}|(1-\epsilon/4)$ . As the good events are independent, Chernoff’s bound implies that with probability $1-n^{-2}$ , at least $|X_{i}|(1-\epsilon)$ points from $X_{i}$ are good. This completes the proof.

Appendix A Proof of Lemma 7

Notice that the function $\Pi_{H}(X)$ is $1$ -Lipschitz and convex, thus by Talagrand’s inequality for any $t>0$

where $\mu$ is the mean of $\Pi_{H}(X)$ . We do not know $\mu$ ; however, we can bound from above. Slightly abusing the notation, let $\Pi:=(\pi_{ij})$ denote the projection matrix onto $H$ , then

Combining this with the concentration inequality, it is not hard to show that $\mu\leq\sigma d^{1/2}+O(1)$ , concluding the proof of the first part of the lemma.

Let $(a_{1},\dots,a_{n})$ be real numbers such that $\sum_{i}a_{i}^{2}=1$ and $|a_{i}|\leq\alpha$ for all $i$ . Let $\xi_{i}$ be independent random variables with mean 0 and ${\mathbf{E}}|\xi_{i}|^{k}\leq\sigma^{2}$ for all $k\geq 2$ . Let $S:=\sum_{i=1}^{n}a_{i}\xi_{i}$ . Then

To prove Claim 12, notice that for any $0<t\leq\alpha^{-1}$ we have

Since ${\mathbf{E}}\xi_{i}^{k}\leq\sigma^{2}$ for all $k\geq 2$ and $t|a_{i}|\leq 1$ , the right most formula is

To optimize the RHS, let us consider two cases

Case 1. $\sigma\geq\alpha\sqrt{\log n}$ . Take $T=4\sigma\sqrt{\log n}$ and $t=\frac{\sqrt{\log n}}{\sigma}\leq\alpha^{-1}$ . With this setting $-tT+t^{2}\sigma^{2}=-3\log n$ .

Case 2. $\sigma<\alpha\sqrt{\log n}$ . Take $T=4\alpha\log n$ and $t=\alpha^{-1}$ . In this setting, $-tT+t^{2}\sigma^{2}\leq-4\log n+\log n=-3\log n$ .

One can bound ${\mathbf{P}}(-S\leq T)$ the same way.