Breaking the Small Cluster Barrier of Graph Clustering

Introduction

This paper considers a classic problem in machine learning and theoretical computer science, namely graph clustering, i.e., given an undirected unweighted graph, partition the nodes into disjoint clusters, so that the density of edges within one cluster is higher than those across clusters. Graph clustering arises naturally in many application across science and engineering. Some prominent examples include community detection in social network Mishra et al. 2007, submarket identification in E-commerce and sponsored search Yahoo!-Inc 2009, and co-authorship analysis in analyzing document database Ester et al. 1995, among others. From a purely binary classification theoretical point of view, the edges of the graph are (noisy) labels of similarity or affinity between pairs of objects, and the concept class consists of clusterings of the objects (encoded graphically by identifying clusters with cliques).

In this paper, we aim to break this small cluster barrier of graph clustering. Correctly identifying extremely small clusters is inherently hard as they are easily confused with ‘‘fake’’ clusters generated by noisy edges Indeed, even in a more lenient setup where one clique (i.e., a perfect cluster) of size $K$ is embedded in an Erdos-Renyi graph of $n$ nodes and $0.5$ probability of forming an edge, to recover this clique, the best known polynomial method requires $K=\Omega(\sqrt{n})$ and it has been a long standing open problem to relax this requirement., and is not the focus of this paper. Instead, in this paper we investigate a question that has not been addressed before: Can we still recover large clusters in the presence of small clusters? Intuitively, this should be doable. To illustrate, consider an extreme example where the given graph $G$ consists two disjoint subgraphs $G_{1}$ and $G_{2}$, where $G_{1}$ is a graph that can be correctly clustered using some existing method, and $G_{2}$ is a small-size clique. $G$ certainly violates the minimum cluster size requirement of previous results, but why should $G_{2}$ spoil our ability to cluster $G_{1}$?

The main implication of this result is that one can apply an iterative “peeling” strategy, recovering smaller and smaller clusters. The intuition is simple – suppose the number of clusters is limited, then either all clusters are large, or the sizes of the clusters vary significantly. The first case is obviously easy. The second one is equally easy: use the aforementioned convex formulation, the larger clusters can be correctly identified. If we remove all nodes from these larger clusters, the remaining subgraph contains significantly fewer nodes than the original graph, which leads to a much lower threshold on the size of the cluster for correct recovery, making it possible for correctly clustering some smaller clusters. By repeating this procedure, indeed, we can recover the cluster structure for almost all nodes with no lower bound on the minimal cluster size. We summarize our main contributions and techniques:

(2) We provide a converse of the result just described. More precisely, we show that if for some value of the knob $x$ an optimal solution appears to look as if the interval $(x/\log^{2}n,x)$ were indeed free of cluster sizes, then the solution is useful (in the sense that it correctly identifies big clusters) even if this weren’t the case.

(3) The last two points imply that if some interval of the form $(x/\log^{2}n,x)$ is free of cluster sizes, then an exhaustive search of this interval will constructively find big clusters (though not necessarily for that particular interval). This gives rise to an iterative algorithm, using a “peeling strategy”, to recover smaller and smaller clusters that are otherwise impossible to recover. Using the “knob”, we prove that as long as the number of clusters is bounded by $\Omega(\log n/\log\log n)$, regardless of the cluster sizes, we can correctly recover the cluster structure for an overwhelming fraction of nodes. To the best of our knowledge, this is the first result of provably correct graph clustering without any assumptions on the cluster sizes.

(4) We extend the result to the partial observation case, where only a faction of similarity labels (i.e., edge/no edge) is known. As expected, smaller observation rates allow identification of larger clusters. Hence, the observation rate serves as the “knob”. This gives rise to an active learning algorithm for graph clustering based on adaptively increasing the rate of sampling in order to hit a “forbidden interval” free of cluster sizes, and concentrating on smaller inputs as we identify big clusters and peel them off.

Beside these technical contributions, this paper provides novel insights into low-rank matrix recovery and more generally high-dimensional statistics, where data are typically assumed to obey certain low-dimensional structure. Numerous methods have been developed to exploit this a priori information so that a consistent estimator is possible even when the dimensionality of data is larger than the number of samples. Our result shows that one may combine these methods with a “peeling strategy” to further push the envelope of learning structured data – By iteratively recovering the easier structure and then reducing the problem size, it is possible to learn structures that are otherwise difficult using previous approaches.

The literature of graph clustering is too vast for a detailed survey here; we concentrate on the most related work, and in specific those provide theoretical guarantees on cluster recovery.

Correlation Clustering This problem, originally defined by Bansal, Blum and Chawla Bansal et al. 2004, also considers graph clustering but in an adversarial noise setting. The goal there is to find the clustering minimizing the total disagreement (intercluster edges plus intracluster nonedges), without there being necessarily a notion of true clustering (and hence no “exact recovery”). This problem is usually studied in the combinatorial optimization framework and is known to be NP-Hard to approximate to within some constant factor. Prominent work includes Demaine et al. 2006; Ailon et al. 2008; Charikar et al. 2005. A PTAS is known in case the number of clusters is fixed Giotis and Guruswami 2006.

Low rank matrix decomposition via trace norm: Motivated from robust PCA, it has recently been shown Chandrasekaran et al. 2011; Candès et al. 2011, that it is possible to recover a low-rank matrix from sparse errors of arbitrary magnitude, where the key ingredient is using trace norm (aka nuclear norm) as a convex surrogate of the rank. A similar result is also obtained when the low rank matrix is corrupted by other types of noise Xu et al. 2012.

Active learning/Active clustering Another line of work that motivates this paper is study of active learning algorithms (a settings in which labeled instances are chosen by the learner, rather than by nature), and in particular active learning for clustering. The most related work is Ailon et al. 2012, who investigated active learning for correlation clustering. The authors obtain a $(1+\varepsilon)$-approximate solution with respect to the optimal, while (actively) querying no more than $O(n\operatorname{poly}(\log n,k,\varepsilon^{-1}))$ edges. The result imposed no restriction on cluster sizes and hence inspired this work, but differs in at least two major ways. First, Ailon et al. 2012 did not consider exact recovery as we do. Second, their guarantees fall in the ERM (Empirical Risk Minimization) framework, with no running time guarantees. Our work recovers true cluster exactly using a convex relaxation algorithm, and is hence computationally efficient. The problem of active learning has also been investigated in other clustering setups including clustering based on distance matrix Voevodski et al. 2012; Shamir and Tishby 2011, and hierarchical clustering Eriksson et al. 2011; Krishnamurthy et al. 2012. These setups differ from ours and cannot be easily compared.

Notation and Setup

Throughout, $V$ denotes a ground set of elements, which we identify with the set $[n]=\{1,\dots,n\}$. We assume a true ground truth clustering of $V$ given by a pairwise disjoint covering $V_{1},\dots,V_{k}$, where $k$ is the number of clusters. We say $i\sim j$ if $i,j\in V_{a}$ for some $a\in[k]$, otherwise $i\not\sim j$. We let $n_{i}=|V_{i}|$ for all $i\in[k]$. For any $i\in[n]$, $\langle i\rangle$ is the unique index satisfying $i\in V_{\langle i\rangle}$.

The ground truth clustering matrix, denoted $K^{*}$, is defined so that $K^{*}(i,j)=1$ is $i\sim j$, otherwise $0$. This is a block diagonal matrix, each block consisting of $1$’s only. Its rank is $k$. The input is a symmetric matrix $A$, a noisy version of $K^{*}$. It is generated using the well known planted clustering model, as follows. There are two fixed edge probabilities, $p>q$. We think of $A$ as the adjacency matrix of an undirected random graph, where edge $(i,j)$ is in the graph for $i>j$ with probability $p$ if $i\sim j$, otherwise with probability $q$, independent of other choices. The error matrix is denoted by $B^{*}:=A-K^{*}$. We let $\Omega:=\Gamma(B^{*})$ denote the noise locations.

Note that our results apply to the more practical case in which the edge probability of $(i,j)$ is $p_{ij}$ for each $i\sim j$ and $q_{ij}$ for $i\not\sim j$, as long as $(\min p_{ij})=:p>q:=(\max q_{ij})$.

Results

There exist constants $b_{1},b_{3},b_{4}>0$ such that the following holds with probability at least $1-n^{-3}$. For any parameter $\kappa\geq 1$ and $t\in[\frac{1}{4}p+\frac{3}{4}q,\frac{3}{4}p+\frac{1}{4}q]$, define

then $(\hat{K},\hat{B})=({\mathcal{P}}_{\sharp}K^{*},A-\hat{K})$, where for a matrix $M$, ${\mathcal{P}}_{\sharp}M$ is the matrix defined by

An $n\times n$ matrix $K$ is a partial clustering matrix if there exists a collection of pairwise disjoint sets $U_{1},\dots,U_{r}\subseteq[n]$ (the induced clusters) such that $K(i,j)=1$ if and only if $i,j\in U_{s}$ for some $s\in[r]$, otherwise $0$. If $K$ is a partial clustering matrix then $\sigma_{\operatorname{min}}(K)$ is defined as $\min_{i=1}^{r}|U_{i}|$.

In order for this fact to be useful algorithmically, we also need a type of converse: there exists an event with high probability (in the random process generating the input), such that for all values of $\kappa$, if an optimal solution to the corresponding (CP1) looks like the solution $(\hat{K},\hat{B})$ defined in Theorem 1, then the blocks of $\hat{K}$ correspond to actual clusters.

There exists constants $C_{1},C_{2}>0$ such that with probability at least $1-n^{-2}$, the following holds. For all $\kappa\geq 1$ and $t\in[\frac{3}{4}q+\frac{1}{4}p,\frac{1}{4}q+\frac{3}{4}p]$, if $(K,B)$ is an optimal solution to (CP1) with $c_{1},c_{2}$ as defined in Theorem 1, and additionally $K$ is a partial clustering induced by $U_{1},\dots,U_{r}\subseteq V$, and also

then $U_{1},\dots,U_{r}$ are actual ground truth clusters, namely, there exists an injection $\phi:[r]\mapsto[k]$ such that $U_{i}=V_{\phi(i)}$ for all $i\in[r]$.

(Note: Our proof of Theorem 3 uses Hoeffding tail bounds for simplicity, which are tight for $p,q$ bounded away from $0$ and $1$. Bernstein tail bounds can be used to strengthen the result for other classes of $p,q$. We elaborate on this in Section 3.1.)

The combination of Theorems 1 and 3 implies that, as long as there exists a relatively small interval which is disjoint from the set of cluster sizes, and such that at least one cluster size is larger than this interval (and large enough), we can recover at least one (large) cluster using (CP1). This is made clear in the following.

Assume we have a guarantee that there exists a number $\alpha\geq b_{4}\frac{\sqrt{p(1-q)n}}{p-q}$, such that no cluster size falls in the interval $(\alpha,\frac{b_{3}}{b_{4}}\alpha\log^{2}n)$ and at least one cluster size is of size at least $s:=\max\{\frac{b_{3}}{b_{4}}\alpha\log^{2}n,(C_{1}k\log n)/(p-q)^{2},C_{2}\sqrt{p(1-q)n\log n}/(p-q)\}$. Then with probability at least $1-n^{-2}$, we can recover at least one cluster of size at least $s$ efficiently by solving (CP1) with $\kappa=\alpha/\left(b_{4}\frac{\sqrt{p(1-q)n}}{p-q}\right)$.

There exists $C_{3}(p,q),C_{4}(p,q),C_{5}>0$ such that the following holds. Assume that $n>C_{4}(p,q)$, and that we are guaranteed that $k\leq k_{0}$, where $k_{0}=\frac{C_{3}(p,q)\log n}{\log\log n}$. Then with probability at least $1-n^{-2}$ Algorithm 1 will recover at least one cluster in at most $C_{5}k_{0}$ iterations.

The proof is deferred to the supplemental material section. Lemma 5 ensures that by trying at most a logarithmic number of values of $\kappa$, we can recover at least one large cluster, assuming the number of clusters is roughly logarithmic in $n$. The next proposition tells us that as long as this step recovers the clusters covering at most all but a vanishing fraction of elements, the step can be repeated.

A pair of numbers $(n^{\prime},k^{\prime})$ is called good if $n^{\prime}\leq n,k^{\prime}\leq k$ and $k^{\prime}\leq\frac{C_{3}(p,q)\log n^{\prime}}{\log\log n}$. If $(n^{\prime},k^{\prime})$ is good, then $(n^{\prime\prime},k^{\prime\prime})$ is good for all $n^{\prime\prime},k^{\prime\prime}$ satisfying $n^{\prime}\geq n^{\prime\prime}\geq n^{\prime}/(\log n)^{1/C_{3}(p,q)}$ and $k^{\prime}-1\geq k^{\prime\prime}\geq 1$.

The proof is trivial. The proposition implies an inductive process in which at least one big (with respect to the current unrecovered size) cluster can be efficiently removed as long as the previous step recovered at most a $(1-(\log n)^{-1/C_{3}(p,q)})$-fraction of its input. Combining, we proved the following:

Assume $n,k$ satisfy the requirements of Lemma 5. Then with probability at least $1-2n^{-2}$ Algorithm 2 recovers clusters covering all but at most a $((\log n)^{-1/C_{3}(p-q)})$ fraction of the input in the full observation case, without any restriction of the minimal cluster size. Moreover, if we assume that $k$ is bounded by a constant $k_{0}$, then the algorithm will recover clusters covering all but a constant number of input elements.

We now consider the case where the input matrix $A$ is not given to us in entirety, but rather that we have oracle access to $A(i,j)$ for $(i,j)$ of our choice. Unobserved values are formally marked with $A(i,j)=?$.

Consider a more particular setting in which the edge probabilities defining $A$ are $p^{\prime}$ (for $i\sim j$) and $q^{\prime}$ (for $i\not\sim j$), and we observe $A(i,j)$ with probability $\rho$, for each $i,j$, independently. More precisely: For $i\sim j$ we have $A(i,j)=1$ with probability $\rho p^{\prime}$, $0$ with probability $\rho(1-p^{\prime})$ and $?$ with remaining probability. For $i\not\sim j$ we have $A(i,j)=1$ with probability $\rho q^{\prime}$, $0$ with probability $\rho(1-q^{\prime})$ and $?$ with remaining probability. Clearly, by pretending that the values $?$ in $A$ are $0$, we emulate the full observation case with $p=\rho p^{\prime}$, $q=\rho q^{\prime}$.

Of particular interest is the case in which $p^{\prime},q^{\prime}$ are held fixed and $\rho$ tends to zero as $n$ grows. In this regime, by varying $\rho$ and fixing $\kappa=1$, Theorem 1 implies the following:

There exist constants $b_{1}(p^{\prime},q^{\prime}),b_{3}(p^{\prime},q^{\prime}),b_{4}(p^{\prime},q^{\prime}),b_{5}(p^{\prime},q^{\prime})>0$ such that for any sampling rate parameter $\rho$ the following holds with probability at least $1-n^{-3}$. define

then $(\hat{K},\hat{B})=({\mathcal{P}}_{\sharp}K^{*},A-\hat{K})$, where ${\mathcal{P}}_{\sharp}$ is as defined in Theorem 1.

(Note: We’ve abused notation by reusing previously defined global constants (e.g. $b_{1}$) with global functions of $p^{\prime},q^{\prime}$ (e.g. $b_{1}(p^{\prime},q^{\prime})$).) Notice now that the observation probability $\rho$ can be used as a knob for controlling the cluster sizes we are trying to recover, instead of $\kappa$. We would also like to obtain a version of Theorem 3. In particular, we would like to understand its asymptotics as $\rho$ tends to $0$.

There exist constants $C_{1}(p^{\prime},q^{\prime}),C_{2}(p^{\prime},q^{\prime})>0$ such that for all observation rate parameters $\rho\leq 1$, the following holds with probability at least $1-n^{-2}$. If $(K,B)$ is an optimal solution to (CP1) with $c_{1},c_{2}$ as defined in Theorem 8, and additionally $K$ is a partial clustering induced by $U_{1},\dots,U_{r}\subseteq V$, and also

then $U_{1},\dots,U_{r}$ are actual ground truth clusters, namely, there exists an injection $\phi:[r]\mapsto[k]$ such that $U_{i}=V_{\phi(i)}$ for all $i\in[r]$.

The proof can be found in the supplemental material. Using the same reasoning as before, we derive the following:

Let $g=b_{3}(p^{\prime},q^{\prime})/b_{4}(p^{\prime},q^{\prime})\log^{2}n$ (with $b_{3}(p^{\prime},q^{\prime}),b_{4}(p^{\prime},q^{\prime})$ defined in Corollary 8). There exists a constant $C_{4}(p^{\prime},q^{\prime})$ such that the following holds. Assume the number of clusters $k$ is bounded by some known number $k_{0}\leq C_{4}(p^{\prime},q^{\prime})(\log n)/(\log\log n)$. Let $\rho_{0}=\frac{b_{3}(p^{\prime},q^{\prime})^{2}k_{0}^{2}\log^{4}n}{n}$. Then there exists $\rho$ in the set $\{\rho_{0},\rho g,\dots,\rho g^{k_{0}}\}$ for which, if $A$ is obtained with observation rate $\rho$ (zeroing $?$’s), then with probability at least $1-n^{-2}$, any optimal solution $(K,B)$ to (CP1) with $c_{1},c_{2}$ from Corollary 8 satisfies (4).

values of $A(i,j)$. On the other end of the spectrum, if $k_{0}\leq\delta(\log n)/(\log\log n)$ and $n$ is large enough (exponential in $1/\delta$), then we can recover at least one large cluster after querying no more than $n^{1+O(\delta)}$ values of $A(i,j)$. (We omit the details of the last fact from this version.) This is summarized in the following:

Assume an upper bound $k_{0}$ on the number of clusters $k$. As long as $n$ is larger than some function of $k_{0},p^{\prime},q^{\prime}$, Algorithm 4 will recover, with probability at least $1-n^{-1}$, at least one cluster of size at least $n/k_{0}$, regardless of the size of other (small) clusters. Moreover, if $k_{0}$ is a constant, then clusters covering all but a constant number of elements will be recovered with probability at least $1-n^{-1}$, and the total number of observation queries is (5), hence almost linear.

Note that unlike previous results for this problem, the recovery guarantee does not impose any lower bound on the size of the smallest cluster. Also note that the underlying algorithm is an active learning one, because more observations fall in smaller clusters which survive deeper in the recursion of Algorithm 4.

Experiments

We experimented with simplified versions of our algorithms. Here we did not make an effort to compute the various constants defining the algorithms in this work, creating a difficulty in exact implementation. Instead, for Algorithm 1, we increase $\kappa$ by a multiplicative factor of $1.1$ in each iteration until a partial clustering matrix is found. Similarly, in Algorithm 3, $\rho$ is increased by an additive factor of $0.025$. Still, it is obvious that our experiments support our theoretical findings. A more practical “user’s guide” for this method with actual constants is subject to future work.

In all experiment reports below, we use a variant of the Augmented Lagrangian Multiplier (ALM) method Lin et al. 2009 to solve the semi-definite program (CP1). Whenever we say that “clusters $\{V_{i_{1}},V_{i_{2}},\dots\}$ were recovered”, we mean that a corresponding instantiation of (CP1) resulted in an optimal solution $(K,B)$ for which $K$ was a partial clustering matrix induced by $\{V_{i_{1}},V_{i_{2}},\dots\}$.

Consider $n=1100$ nodes partitioned into $4$ clusters $V_{1},\ldots,V_{4}$, of sizes $800,200,80,20$, respectively. The graph is generated according to the planted partition model with $p=0.5$, $q=0.2$, and we assume the full observation setting. We apply a simplified version of Algorithm 2, which terminates in $4$ steps. The recovered clusters at each step are detailed in Table 1.

Experiment 2 (Partial Observation - Fixed Sample Rate)

We have $n=1100$ with clusters $V_{1},\dots,V_{4}$ of sizes $800,200,50,50$. The observed graph is generated with $p^{\prime}=0.7$, $q^{\prime}=0.1$, and observation rate $\rho=0.3$. We repeatedly solved (CP1) with $c_{1},c_{2}$ as in Corollary 8. At each iteration, at least one large cluster (compared to the input size at that iteration) was recovered exactly and removed. This terminated in exactly $3$ iterations. Results are shown in Table 1.

Experiment 3 (Partial Observation - Incremental Sampling Rate)

We tried a simplified version of Algorithm 4. We have $n=1100$ with clusters $V_{1},\dots,V_{4}$ of sizes $800,200,50,50$. The observed graph is generated with $p^{\prime}=0.7$, $q^{\prime}=0.3$, and an observation rate $\rho$ which we now specify. We start with $\rho=0$ and increase it by $0.025$ incrementally until we recover (and then remove) at least one cluster, then repeat. The algorithm terminates in $3$ steps. Results are shown in Table 1.

Experiment 3A

We repeat the experiment with a larger instance: $n=4500$ with clusters $V_{1},\dots,V_{6}$ of sizes $3200,800,200,200,50,50$, and $p^{\prime}=0.8,q^{\prime}=0.2$. Results are shown in Table 1. Note that we recover the smallest clusters, whose size is below $\sqrt{n}$.

Experiment 4 (Mid-Size Clusters)

Discussion

Our study was mainly theoretical, focusing on the planted partition model. As such, our experiments focused on confirming the theoretical findings with data generated exactly according to the distribution we could provide provable guarantees for. It would be interesting to apply the presented methodology to real applications, particularly big data sets merged from web application and social networks.

Another interesting direction is extending the “peeling strategy” to other high-dimensional learning problems. This requires understanding when such a strategy may work. One intuitive explanation of the small cluster barrier encountered in previous work is ambiguity – when viewing the input at the “big cluster resolution”, a small cluster is both a low-rank matrix and a sparse matrix. Only when “zooming in” (after recovering big clusters), small clusters patterns emerge. There are other formulations with similar property. For example, in Xu et al. 2012, the authors propose to decompose a matrix into the sum of a low rank one and a column sparse one to solve an outlier-resistant PCA task. Notice that a column sparse matrix is also a low rank matrix. We hope the “peeling strategy” may also help with that problem.

References

Appendix A Notation and Conventions

We use the following notation and conventions throughout the supplement. For a real $n\times n$ matrix $M$, we use the unadorned norm $\|M\|$ to denote its spectral norm. The notation $\|M\|_{F}$ refers to the Frobenius norm, $\|M\|_{1}$ is $\sum_{i,j}|M(i,j)|$ and $\|M\|_{\infty}$ is $\max_{ij}|M(i,j)|$.

We will also study operators on the space of matrices. To distinguish them from the matrices studied in this work, we will simply call these objects “operators”, and will denote them using a calligraphic font, e.g. $\mathcal{P}$. The norm $\|\mathcal{P}\|$ of an operator is defined as

For a fixed, real $n\times n$ matrix $M$, we define the matrix linear subspace $T(M)$ as follows:

In words, this subspace is the set of matrices spanned by matrices each row of which is in the row space of $M$, and matrices each column of which is in the column space of $M$.

For a matrix $M$, we let $\Gamma(M)$ denote the set of matrices supported on a subset of the support of $M$. Note that for any matrix $X$,

It is a well known fact that $\mathcal{P}_{T(X)}$ is given as follows:

where $P_{C(X)}$ is projection (of a vector) onto the column space of $X$, and $P_{R(X)}$ is projection onto the row space of $X$.

Slightly abusing notation, we will use the set complement operator $(\cdot)^{c}$ to formally define $\Gamma(M)^{c}$ to be $\Gamma(M)^{\perp}$ (by this we are stressing that the space $\Gamma(M)^{\perp}$ is given as $\Gamma(M^{\prime})$ where $M^{\prime}$ is any matrix such that $M$ and $M^{\prime}$ have complementary supports). Note that $\mathcal{P}_{T(X)^{\perp}}M=M-\mathcal{P}_{T(X)}M=(I-P_{C(X)})M(I-P_{R(X)})\ .$

For a matrix $M$, $\operatorname{sgn}M$ is defined as the matrix satisfying:

Appendix B Proof of Theorem 1

The proof is based on Chen et al. 2012. We prove it for $\kappa=1$. The adjustment for $\kappa>1$ is done using a padding argument, presented at the end of the proof.

We remind the reader that the projection ${\mathcal{P}}_{\sharp}$ is defined as follows:

The projection ${\mathcal{P}}_{\flat}$ is defined as follows:

In words, ${\mathcal{P}}_{\flat}$ projects onto the set of matrices supported on $V_{\flat}\times V_{\flat}$. Note that by the theorem assumption, ${\mathcal{P}}_{\sharp}+{\mathcal{P}}_{\flat}={\mathcal{I}d}$ (equivalently, ${\mathcal{P}}_{\sharp}$ projects onto the set of matrices supported on $(V\times V)\setminus(V_{\flat}\times V_{\flat})$).

which contains all feasible deviation from $\hat{K}$.

For simplicity we write $T:=T(\hat{K})$ and $\Gamma:=\Gamma(\hat{B}),\Gamma^{c}:=\Gamma(\hat{B})^{c}=\Gamma^{\perp}$.

${\mathcal{I}d}=\mathcal{P}_{\Gamma}+\mathcal{P}_{\Gamma^{c}}=\mathcal{P}_{\Gamma(A)}+\mathcal{P}_{\Gamma(A)^{c}}$.

${\mathcal{P}}_{\sharp},{\mathcal{P}}_{\flat},\mathcal{P}_{\Gamma},\mathcal{P}_{\Gamma^{c}},\mathcal{P}_{\Gamma(A)},$ and $\mathcal{P}_{\Gamma(A)^{c}}$ commute with each other.

$\left\|\mathcal{P}_{T}(Q)\right\|_{\infty}\leq\frac{\epsilon}{2}\min\left\{c_{1},c_{2}\right\}$

$\left\langle UU^{\top}+Q,\mathcal{P}_{\Gamma(A)}\mathcal{P}_{\Gamma}{\mathcal{P}}_{\sharp}\Delta\right\rangle=(1+\epsilon)c_{1}\left\|\mathcal{P}_{\Gamma(A)}P_{\Gamma}{\mathcal{P}}_{\sharp}\Delta\right\|_{1}$

$\left\langle UU^{\top}+Q,\mathcal{P}_{\Gamma(A)^{c}}\mathcal{P}_{\Gamma}{\mathcal{P}}_{\sharp}\Delta\right\rangle=(1+\epsilon)c_{2}\left\|\mathcal{P}_{\Gamma(A)^{c}}P_{\Gamma}{\mathcal{P}}_{\sharp}\Delta\right\|_{1}$

$\left\langle UU^{\top}+Q,\mathcal{P}_{\Gamma(A)}\mathcal{P}_{\Gamma^{c}}\mathcal{P}_{\sharp}\Delta\right\rangle\geq-(1-\epsilon)c_{1}\left\|\mathcal{P}_{\Gamma(A)}P_{\Gamma^{c}}{\mathcal{P}}_{\sharp}\Delta\right\|_{1}$

$\left\langle UU^{\top}+Q,\mathcal{P}_{\Gamma(A)^{c}}\mathcal{P}_{\Gamma^{c}}\mathcal{P}_{\sharp}\Delta\right\rangle\geq-(1-\epsilon)c_{2}\left\|\mathcal{P}_{\Gamma(A)^{c}}P_{\Gamma^{c}}{\mathcal{P}}_{\sharp}\Delta\right\|_{1}$

$\mathcal{P}_{\Gamma}{\mathcal{P}}_{\flat}(UU^{\top}+Q)=c_{1}{\mathcal{P}}_{\flat}\hat{B}$

$\left\|\mathcal{P}_{\Gamma^{c}}{\mathcal{P}}_{\flat}(UU^{\top}+Q)\right\|_{\infty}\leq c_{2}$

Consider any feasible solution to (CP1) $(\hat{K}+\Delta,\hat{B}-\Delta)$; we know $\Delta\in\mathfrak{D}$ due to the inequality constraints in (CP1). We will show that this solution will have strictly higher objective value than $\left\langle\hat{K},\hat{B}\right\rangle$ if $\Delta\neq 0$.

For this $\Delta$, let $G_{\Delta}$ be a matrix in $T^{\bot}\cap\mbox{Range}({\mathcal{P}}_{\flat})$ satisfying $\left\|G\right\|=1$ and $\left\langle G_{\Delta},\Delta\right\rangle=\left\|\mathcal{P}_{T^{\bot}}{\mathcal{P}}_{\flat}\Delta\right\|_{*}$ ; such a matrix always exists because $\mbox{Range}{\mathcal{P}}_{\flat}\subseteq T^{\bot}$. Suppose $\left\|Q\right\|=b$. Clearly, $\mathcal{P}_{T^{\bot}}Q+(1-b)G\in T^{\bot}$ and, due to desideratum 1, we have $\left\|\mathcal{P}_{T^{\bot}}Q+(1-b)G_{\Delta}\right\|\leq\left\|Q\right\|+(1-b)\left\|G_{\Delta}\right\|=b+(1-b)=1$. Therefore, $UU^{\top}+\mathcal{P}_{T^{\bot}}Q+(1-b)G_{\Delta}$ is a subgradient of $f(K)=\left\|K\right\|_{*}$ at $K=\hat{K}$. On the other hand, define the matrix $F_{\Delta}=-\mathcal{P}_{\Gamma^{c}}\mbox{sgn}(\Delta)$. We have $F_{\Delta}\in\Gamma^{c}$ and $\left\|F_{\Delta}\right\|_{\infty}\leq 1$. Therefore, $\mathcal{P}_{\Gamma(A)}(\hat{B}+F_{\Delta})$ is a subgradient of $g_{1}(B)=\left\|\mathcal{P}_{\Gamma(A)}B\right\|_{1}$ at $B=\hat{B}$, and $\mathcal{P}_{\Gamma(A)^{c}}(\hat{B}+F_{\Delta})$ is a subgradient of $g_{2}(B)=\left\|\mathcal{P}_{\Gamma(A)^{c}}B\right\|_{1}$ at $B=\hat{B}$. Using these three subgradients, the difference in the objective value can be bounded as follows:

The last six terms of the last RHS satisfy:

$c_{1}\left\langle{\mathcal{P}}_{\flat}\mathcal{P}_{\Gamma(A)}\hat{B},-\Delta\right\rangle+c_{2}\left\langle{\mathcal{P}}_{\flat}\mathcal{P}_{\Gamma(A)^{c}}\hat{B},-\Delta\right\rangle=c_{1}\left\langle{\mathcal{P}}_{\flat}\hat{B},-\Delta\right\rangle$, because ${\mathcal{P}}_{\flat}\hat{B}\in\Gamma(A)$.

$\left\langle{\mathcal{P}}_{\sharp}\mathcal{P}_{\Gamma(A)}\hat{B},-\Delta\right\rangle\geq-\left\|{\mathcal{P}}_{\sharp}\mathcal{P}_{\Gamma(A)}\mathcal{P}_{\Gamma}\Delta\right\|_{1}$ and $\left\langle{\mathcal{P}}_{\sharp}\mathcal{P}_{\Gamma(A)^{c}}\hat{B},\Delta\right\rangle\geq-\left\|{\mathcal{P}}_{\sharp}\mathcal{P}_{\Gamma(A)^{c}}\mathcal{P}_{\Gamma}\Delta\right\|_{1}$, because $\hat{B}\in\Gamma$ and$\left\|\hat{B}\right\|_{\infty}\leq 1$.

$\left\langle\mathcal{P}_{\Gamma(A)}F_{\Delta},-\Delta\right\rangle=\left\|\mathcal{P}_{\Gamma(A)}\mathcal{P}_{\Gamma^{c}}\Delta\right\|_{1}$ and $\left\langle\mathcal{P}_{\Gamma(A)^{c}}F_{\Delta},-\Delta\right\rangle=\left\|\mathcal{P}_{\Gamma(A)^{c}}\mathcal{P}_{\Gamma^{c}}\Delta\right\|_{1}$, due to the definition of $F$.

Consider the second term in the last RHS, which equals $\left\langle UU^{\top}+\mathcal{P}_{T^{\bot}}Q,\Delta\right\rangle=\left\langle UU^{\top}+Q,{\mathcal{P}}_{\sharp}\Delta\right\rangle+\left\langle UU^{\top}+Q,{\mathcal{P}}_{\flat}\Delta\right\rangle-\left\langle\mathcal{P}_{T}Q,\Delta\right\rangle$. We bound these three separately.

Third term: Due to the block diagonal structure of the elements of $T$, we have $\mathcal{P}_{T}={\mathcal{P}}_{\sharp}\mathcal{P}_{T}$

Combining the above three bounds with Eq. (6), we obtain

which is strictly greater than zero for $\Delta\neq 0$. ∎

B.2 Constructing QQ.

${\mathcal{P}}_{\sharp}Q$ is given by ${\mathcal{P}}_{\sharp}Q={\mathcal{P}}_{\sharp}Q_{1}+{\mathcal{P}}_{\sharp}Q_{2}+{\mathcal{P}}_{\sharp}Q_{3}$, where for $(i,j)\notin V_{\flat}\times V_{\flat}$,

Note that these matrices have zero-mean entries.

${\mathcal{P}}_{\flat}Q$ as follows. For $(i,j)\in V_{\flat}\times V_{\flat}$,

B.3 Validating QQ

Note that $\left\|Q\right\|\leq\left\|{\mathcal{P}}_{\sharp}Q_{\sim}\right\|+\left\|{\mathcal{P}}_{\sharp}Q_{\not\sim}\right\|+\left\|{\mathcal{P}}_{\flat}Q_{\sim}\right\|+\left\|{\mathcal{P}}_{\flat}Q_{\not\sim}\right\|$. We show that all four terms are upper-bounded by $\frac{1}{4}$.

(b) ${\mathcal{P}}_{\flat}Q_{\not\sim}$ is a random matrix supported on $V_{\flat}\times V_{\flat}$, whose entries are i.i.d., zero mean, bounded almost surely by $\max\{c_{1},c_{2}\}$, and have variance $\frac{b_{1}^{2}}{n\log n}\cdot\frac{t^{2}+q-2tq}{(1-t)t}$. It follows from Lemma 16 that

because $n_{\flat}\leq n$ and $\max\{c_{1},c_{2}\}\leq\frac{1}{48\log^{2}n}$, which holds under the assumption of the theorem.

(d) Note that ${\mathcal{P}}_{\sharp}Q_{\not\sim}={\mathcal{P}}_{\sharp}Q_{3}$ is a random matrix with i.i.d. zero-mean entries which are bounded almost surely by $B_{\not\sim}:=\frac{2c_{1}}{1-q}$ and have variance bounded by $\sigma_{\not\sim}^{2}:=\frac{4q}{1-q}c_{1}^{2}$. Lemma 16 gives $\left\|{\mathcal{P}}_{\sharp}Q_{\not\sim}\right\|\leq 6\max\left\{\sqrt{n}\cdot\sigma_{\not\sim},B_{\not\sim}\log^{2}n\right\}\leq\frac{1}{4}$.

Now observe that $(UU^{\top}{\mathcal{P}}_{\sharp}Q_{m})(i,j)=\sum_{l\in V_{c(i)}}\frac{1}{n_{c(i)}}{\mathcal{P}}_{\sharp}Q_{m}(l,j)$ is the sum of i.i.d. zero-mean random variables with bounded magnitude and variance. Using Lemma 18, we obtain that for $i\in V_{\sharp}$,

On the other hand, under the definition of $c_{1},c_{2}$ and $\epsilon$, we have

Consider the two terms in the parenthesis in the last RHS. For the first term, we have

For the second term, we have the following

which implies $(1+\epsilon)c_{2}\frac{1-p}{p}\leq(1-2\epsilon)c_{1}$. We conclude that

Consider the factor before the norm in the last RHS. Similarly as before, we have

This implies $(1+\epsilon)c_{1}\frac{q}{1-q}\leq(1-\epsilon)c_{2}$. We conclude that

Properties 5) and 6): It is obvious that these two properties hold by construction of $Q$.

Note that properties 3)-6) hold deterministically.

B.4 The κ>1\kappa>1 case

Applying Theorem 1 with $\kappa=1$ (which we have proved) to $A^{\prime}$ and the padded program (CP1’), we conclude that the unique optimal solution $(\hat{K}^{\prime},\hat{B}^{\prime}=A^{\prime}-\hat{K}^{\prime})$ to (CP1’) has the form

We claim that $\hat{K}={\mathcal{P}}_{\sharp}K^{*}$ is the unique optimal solution to (CP1).

Proof by contradiction: suppose an optimal solution to (CP1) is $\hat{K}=K_{0}\neq{\mathcal{P}}_{\sharp}K^{*}$. By optimality we have

contradicting the fact that $(\hat{K}^{\prime},\hat{B}^{\prime}=A^{\prime}-\hat{K}^{\prime})$ is the unique optimal to (CP1’).

Appendix C Proof of Theorem 3

Fix $\kappa\geq 1$ and $t$ in the allowed range, let $(K,B)$ be an optimal solution to (CP1) , and assume $K$ is a partial clustering induced by $U_{1},\dots,U_{r}$ for some integer $r$, and also assume $\sigma_{\operatorname{min}}(K)=\min_{i\in[r]}|U_{i}|$ satisfies (3). Let $M=\sigma_{\operatorname{min}}(K)$.

We need a few helpful facts. First, note that any value of $t$ in the allowed range $[\frac{1}{4}p+\frac{3}{4}q,\frac{3}{4}p+\frac{1}{4}q]$ satisfies $q+\frac{1}{4}(p-q)\leq t\leq p-\frac{1}{4}(p-q)$. Also note that from the definition of $t,c_{1},c_{2}$,

We say that a pair of sets $Y\subseteq V,Z\subseteq V$ is cluster separated if there is no pair $(y,z)\in Y\times Z$ satisfying $y\sim z$.

There exists a constant $C^{\prime}>0$ such that for all pairs of cluster-separated sets $Y,Z$ of size at least $m:=\frac{C^{\prime}\log n}{(p-q)^{2}}$ each,

where $\hat{d}_{Y,Z}:=\frac{|(Y\times Z)\cap\Omega|}{|Y|\cdot|Z|}$.

This is proven by a Hoeffding tail bound and a union bound to hold with probability at least $1-n^{-4}$. To see why, fix the sizes $m_{Y},m_{Z}$ of $|Y|,|Z|$, assume $m_{Y}\leq m_{Z}$ w.l.o.g. For each such choice, there are at most $\exp\{C(m_{Y}+m_{Z})\log n\}\leq\exp\{2Cm_{Z}\log n\}$ possibilities for the choice of sets $Y,Z$, for some $C>0$. For each such choice, the probability that $(\ref{hatq})$ does not hold is

using Hoeffding inequality, for some $C^{\prime\prime}>0$. Hence, as long as $m_{Y}\geq m$ as defined above, for properly chosen $C^{\prime}$, using union bound (over all possibilities of $m_{Y},m_{Z}$ and of $Y,Z$) we obtain (8) uniformly.

(which can be done by setting $C_{1}\geq 3C^{\prime}$) the implication of the assumption is that it cannot be the case that some $U_{i}$ contains a subset $U_{i}^{\prime}$ of size in the range $\left[m,|U_{i}|-m\right]$ such that $U_{i}^{\prime}=V_{g}\cap U_{i}$ for some $g$. Indeed, if such a set existed, then we would find a strictly better solution to (CP1), call it $(K^{\prime},B^{\prime})$, which is defined so that $K^{\prime}$ is obtained from $K$ by splitting the block corresponding to $U_{i}$ into two blocks, one corresponding to $U_{i}^{\prime}$ and the other to $U_{i}\setminus U_{i}^{\prime}$. The difference $\Delta$ between the cost of $(K,B)$ and $(K^{\prime},B^{\prime})$ is (renaming $Y:=U_{i}^{\prime}$ and $Z:=U\setminus U_{i}^{\prime}$) $\Delta=c_{1}|(Y\times Z)\cap\Omega|-c_{2}|(Y\times Z)\cap\Omega^{c}|=(c_{1}+c_{2})\hat{d}_{Y,Z}|Y|\,|Z|-c_{2}|Y|\,|Z|$. But the sign of $\Delta$ is exactly the sign of $\hat{d}_{Y,Z}-\frac{c_{2}}{c_{1}+c_{2}}$ which is strictly negative by (8) and (7). (We also used the fact that the trace norm part of the utility function is equal for both solutions: $\|K^{\prime}\|_{*}=\|K\|_{*}$).

The conclusion is that for each $i$, the sets $(U_{i}\cap V_{1}),\dots,(U_{i}\cap V_{k})$ must all be of size at most $m$, except maybe for at most one set of size at least $|U_{i}|-m$. If we now also assume that

then we conclude that not all these sets can be of size at most $m$. Hence exactly one of these sets must have size at least $|U_{i}|-m$. From this we conclude that there is a function $\phi:[r]\mapsto[k]$ such that for all $i\in[r]$,

We now claim that this function is an injection. We will need the following assumption:

For any $4$ pairwise disjoint subsets $(Y,Y^{\prime},Z,Z^{\prime})$ such that $(Y\cup Y^{\prime})\subseteq V_{i}$ for some $i$, $(Z\cup Z^{\prime})\subseteq[n]\setminus V_{i}$, $\max\{|Z|,|Z^{\prime}|\}\leq m$, $\min\{|Y|,|Y^{\prime}|\}\geq M-m$:

The assumption holds with probability at least $1-n^{-4}$ by using Hoeffding inequality, union bounding over all possible sets $Y,Y^{\prime},Z,Z^{\prime}$ as above. Indeed, notice that for fixed $m_{Y},m_{Y^{\prime}},m_{Z},m_{Z^{\prime}}$ (with, say, $m_{Y}\geq m_{Y^{\prime}}$), and for each tuple $Y,Y^{\prime},Z,Z^{\prime}$ such that $|Y|=m_{Y},|Y^{\prime}|=m_{Y^{\prime}},|Z|=m_{Z},|Z^{\prime}|=m_{Z^{\prime}}$, the probability that (12) is violated is at most

for some $C>0$. Using (10), this is at most

for some global $C^{\prime\prime}>0$. Now notice that the number of possibilities to choose such a $4$ tuple of sets is bounded above by $\exp\{C^{\prime\prime\prime}m_{Y}\log n\}$, for some global $C^{\prime\prime\prime}>0$. Assuming

for some $\hat{C}$, and applying a union bound over all possible combinations $Y,Y^{\prime},Z,Z^{\prime}$ of sizes $m_{Y},m_{Y^{\prime}},m_{Z},m_{Z^{\prime}}$ respectively, of which there are at most $\exp\{C^{\circ}m_{Y}\log n\}$ for some $C^{\circ}>0$, we conclude that (12) is violated for some combination with probability at most

for some $\hat{C}^{\prime}>0$. Apply a union bound now over the possible combinations of the tuple $(m_{Y},m_{Y^{\prime}},m_{Z},m_{Z^{\prime}})$ , of which there are at most $\exp\{4\log n\}$ to conclude that (12) holds uniformly for all possibilities of $Y,Y^{\prime},Z,Z^{\prime}$ with probability at least $1-n^{-4}$.

Now assume by contradiction that $\phi$ is not an injection, so $\phi(i)=\phi(i^{\prime})=:j$ for some distinct $i,i^{\prime}\in[r]$. Set $Y=U_{i}\cap V_{j},Y^{\prime}=U_{i^{\prime}}\cap V_{j}$, $Z=U_{i}\setminus Y,Z^{\prime}=U_{i^{\prime}}\setminus Y^{\prime}$. Note that $\max\{|Z|,|Z^{\prime}|\}\leq m$ and $\min\{|Y|,|Y^{\prime}|\}\geq M-m$. Consider the solution $(K^{\prime},B^{\prime})$ where $K^{\prime}$ is obtained from $K$ by replacing the two blocks corresponding to $U_{i},U_{i^{\prime}}$ with four blocks: $Y,Y^{\prime},Z,Z^{\prime}$. Inequality (12) guarantees that the cost of $(K^{\prime},B^{\prime})$ is strictly lower than that of $(K,B)$, contradicting optimality of the latter. (Note that $\|K\|_{*}=\|K^{\prime}\|_{*}$.)

We can now also conclude that $r\leq k$. Fix $i\in[r]$. We show that not too many elements of $V_{\phi(i)}$ can be contained in $V\setminus\{U_{1}\cup\cdots\cup U_{r}\}$. We need the following assumption.

For all pairwise disjoint sets $Y,X,Z\subseteq V$ such that $|Y|\geq M-m$, $|X|\geq m$, $(Y\cup X)\subseteq V_{j}$ for some $j\in[k]$, $|Z|\leq m$, $Z\cap V_{j}=\emptyset$:

The assumption holds with probability at least $1-n^{-4}$. To see why, first notice that $|X|/(c_{1}+c_{2})\leq\frac{1}{8}(p-q)|X|\cdot|Y|$ by (3), as long as $C_{2}$ is large enough. This implies that the RHS of (18) is upper bounded by

Proving that the LHS of (18) (denoted $f(X,Y,Z)$) is larger than (19) (denoted $g(X,Y,Z)$) uniformly w.h.p. can now be easily done as follows. By fixing $m_{Y}=|Y|,m_{X}=|X|$, the number of combinations for $Y,X,Z$ is at most $\exp\{C(m_{Y}+m_{X})\log n\}$ for some global $C>0$. On the other hand, the probability that $f(X,Y,Z)\leq g(X,Y,Z)$ for any such option is at most

for some $C^{\prime}>0$. Hence, by union bounding, the probability that some tuple $Y,X,Z$ of sizes $m_{Y},m_{X},m_{Z}$ respectively satisfies $f(X,Y,Z)\leq g(X,Y,Z)$ is at most

which is at most $\exp\{-10\log n\}$ assuming

for some $\bar{C}>0$. Another union bound over the possible choices of $m_{Y},m_{X},m_{Z}$ proves that (18) holds uniformly with probability at least $1-n^{-4}$.

Now for some $i\in[r]$ set $X:=V_{\phi(i)}\cap(V\setminus\{U_{1}\cup\cdots\cup U_{r}\})$ and assume by contradiction that $|X|>m$. Set $Y:=V_{\phi(i)}\cap U_{i}$ and $Z=U_{i}\setminus V_{\phi(i)}$. Define the solution $(K^{\prime},B^{\prime})$ where $K^{\prime}$ is obtained from $K$ by replacing the block corresponding to $U_{i}$ in $K$ with two blocks: $V_{\phi(i)}$ and $U_{i}\setminus V_{\phi(i)}$. Assumption 15 tells us that the cost of $(K^{\prime},B^{\prime})$ is strictly lower than that of $(K,B)$. Note that the expression $\frac{|X|}{c_{1}+c_{2}}$ in the RHS of (18) accounts for the trace norm difference $\|K^{\prime}\|_{*}-\|K\|_{*}=|X|$.