Recovering Unbalanced Communities in the Stochastic Block Model with Application to Clustering with a Faulty Oracle
Authors: Chandra Sekhar Mukherjee
Pan Peng
Jiapeng Zhang
Venue: NeurIPS 2023 poster (2023)
Keywords: SBM
Unbalanced SBM
Spectral algorithms
Small cluster barrier
TL;DR: An algorithm to recover large clusters in the SBM model in presence of small cluster, improving on the state-of-the art by removing restrictive assumptions

Abstract: The stochastic block model (SBM) is a fundamental model for studying graph clustering or community detection in networks. It has received great attention in the last decade and the balanced case, i.e., assuming all clusters have large size, has been well studied. 
However, our understanding of SBM with unbalanced communities (arguably, more relevant in practice) is still limited. In this paper, we provide a simple SVD-based algorithm for recovering the communities in the SBM with communities of varying sizes.
We improve upon a result of Ailon, Chen and Xu [ICML 2013; JMLR 2015] by removing the assumption that there is a large interval such that the sizes of clusters do not fall in, and also remove the dependency of the size of the recoverable clusters on the number of underlying clusters. We further complement our theoretical improvements with experimental comparisons.
Under the planted clique conjecture, the size of the clusters that can be recovered by our algorithm is nearly optimal (up to poly-logarithmic factors) when the probability parameters are constant. 

As a byproduct, we obtain an efficient clustering algorithm with sublinear query complexity in a faulty oracle model, which is capable of detecting all clusters larger than $\tilde{\Omega}({\sqrt{n}})$, even in the presence of $\Omega(n)$ small clusters in the graph. In contrast, previous efficient algorithms that use a sublinear number of queries are incapable of recovering any large clusters if there are more than $\tilde{\Omega}(n^{2/5})$ small clusters.

Recovering Unbalanced Communities in the Stochastic Block Model with Application to Clustering with a Faulty Oracle*
Chandra Sekhar Mukherjee chandrasekhar muk.hereeee @ usc.edu
Pan Peng : ppeng wanng@uutcc.eu.c.
Jiapeng Zhang' jiapeng@uusc.cv
Abstract
The stochastic block model (SBM) is a fundamental model for studying graph clustering community detection in networks. It has received great attention in the last decade and the balanced case, i.c., assuming all clusters have large size, has been well studied. However, our understanding of SBM with unbalanced communities (arguably, more relevant in practice) is still limited. In this paper, we provide simple SVD-based algorithm for recovering the communities in the SBM with communities of varying sizes. We improve upon a result of Ailon, Chen and Xu [ICML. 2013; JMLR 2015] by removing the assumption that there is large interval such that the sizes of clusters do not fall in, and also remove the dependency of the size of the recoverable clusters the number of underlying clusters. We further complement our theoretical improvements with experimental comparisons. Under the planted clique conjecture, the size of the clusters that can be recovered by our algorithm is nearly optimal (up to poly-logarithmic factors) when the probability parameters are constant.
As a byproduct, we obtain an efficient clustering algorithm with sublinear query complexity in a faulty oracle model, which is capable of detecting all clusters larger than 22( (n), even in the presence of ((n) small clusters in the graph. In contrast, previous efficient algorithms that use a sublinear number queries are incapable of recovering any large clusters if there are more than 222255) small clusters.
Introduction
Graph clustering (or community detection) is a fundamental problem in computer science and has wide applications in many domains, including biology, social science, and physics. Among others, the stochastic block model (SBM) is one of the most basic models for studying graph clustering, offering both a theoretical arena for rigorously analyzing the performance different types of clustering algorithms, and synthetic benchmarks for evaluating these algorithms in practice. Since the 1980s (e.g., 19 15 ), there has been much progress towards the understanding of the statistical and computational tradeoffs for community detection in SBM with various parameter regimes. We refer to the recent survey 1 for a list of such results.
AAtthors in alphabetical order.
Thomas Lord Department of Computer Science, University of Southern California. Rescarch supported by
NSF CAREER award 2141536.
1 School of Computer Science and Technology, University Science and Technology of China. Research supported in part by NSFC grant 62272431 and "the Fundamental Research Funds for the Central Universities".
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

In this paper, we focus on a very basic version of the stochastic block model.
Definition 1.1 (The SBM(n, k. p) q) model), In this model, given an n-vertex set with a hidden partition V = -س= V; such that Vanv= = 0 for all # J. we say a graph G = (V, is sampled from SBM(n, k. p. q), for all pairs of vertices vs. E V, (1) an edge (Vi, U1) is added independently with probability p. if U3 Vi for some t; (2) an edge (v1,0g) is added independently with probubility otherwise.
We are interested the problem of fully recovering all or some of the clusters, given graph that is sampled from SBM(n, k. P. p.g.. A cluster V, is said to be fully recovered if the algorithm outputs a set S that is exactly V₁. Most of the previous algorithms on the full recovery of SBM either just work for the nearly balanced case (i.e., each cluster has size 52( + {)) when & is small, say & = ollog n.) (see
e.g. 12).. or only work under the following assumption:
All of the latent clusters are sufficiently large i.e., for each j. [V (n) (see e.g..
[25] 6 10
28
From a practical perspective, many real-world graphs may have many communities of different sizes, that is, large and small clusters co-exist in these graphs. This motivates to investigate how to recover the communities SBM if the latent communities have very different sizes. In particular, we are interested in efficiently recovering all the large clusters in the presence of small clusters. However, such a task can be quite difficult, as those small clusters may be confused with noisy edges. Indeed, most previous algorithms try to find all the k-clusters in one shot, which always computes some structuee/infoommation of the graph that are sensitive to noise (and small clusters). For example, the classical SVD-based algorithms (e.g.. 25 28) first compute the first i singular vectors of some matrix associated with the graph and then use these k vectors to find clusters. Such singular vectors are sensitive to edge insertions or deletions (e.g. [13). In general, this difficulty was termed by Ailon et al. k as "small cluster barrier" for graph clustering.
To overcome such a barrier, Ailon al. clusters in the presence of small clusters under the following assumptions (see 4.).
proposed an algorithm that recovers all large latent
none of the cluster sizes falls in the interval (a/ce a:) for a number a ~ o <P(1-1g)
and
p-g
C is some universal constant;
there exists a large cluster, say of size least T := θ mmax
y yp(1-g)> g)n p-v
& (p-o)²
The algorithm in 4 then has exhaustively search for such gap, and then apply a convex program- based algorithm to find a large cluster of size at least Y. As we discuss in the Appendix [D] the assumption of the recoverable cluster being larger than (2 //vpp1 - (pnn/p-4)) is (relatively) natural as any polynomial time algorithm can only recover clusters of size D( (n), under the planted clique conjecture. Still, two natural questions that remain are
1. Can we break the small cluster barrier without making the first assumption on the existence of a gap between the sizes of some clusters?
2. Can we remove the dependency of the size of the recoverable cluster on the number is of
clusters? In particular, when k >> Vn, can we still recover a cluster of size 51 (((/))?
The above questions are inherently related to the clustering problem under the faulty oracle model which was recently proposed by Mazumdar and Saha (23), as an instance from the faulty oracle model is exactly the graph that is sampled from SBM with corresponding parameters. Thus, it is natural to ask if one can advance the state-of the-art algorithm for recovering large clusters for the graph instance from the faulty oracle model using an improved algorithm for the SBM?
1.1 Our contributions
We affirmatively answer all three questions mentioned above. Specifically, we demonstrate that clusters of size $2(vn) can be successfully recovered in both the standard SBM and the faulty oracle model, regardless of the number of clusters present in the graph. This guarantee surpasses any previous achievements in related studies. The practical implications of this finding are significant
'The assumption is sometimes implicit, E.g., in (28 in their Theorem 1, the lower bound on their parameter A implies lower bound on the smallest cluster size.
2

---

since real-world networks often exhibit substantial number of clusters (see e.g. (29 varying in size from large to small.
1.1.1 Recovering large clusters in the SBM
We first provide a singular value decomposition (SVD) based algorithm, without assuming there is gap between the sizes of some clusters, for recovering large latent clusters. Furthermore, the recoverability of the largest cluster is unaffected by the number of underlying clusters.
Theorem 1.2 (Recovering one large cluster). Let G be a graph that is generated from the //(l-1))
SBM(n, k. p, p) with max (V If both of the following conditions are
satisfied: (1) the size of the largest cluster, denoted by 8max is at least 8 == 2)3 pppppp( /p((p-))) qg (2)
(p-q)
x² = 220og n//n). There exists a polynomial time algorithm that exactly recovers a cluster of size at least Smax with probability 1 n²*
We have the following remarks about Theorem 1.2 (1) By the assumption that o² 22(log n n/n), we obtain that p = 2M( Log ), which further implies that expected degrees are at least logarithmic in n. This is necessary as exact recovery in SBM requires the node degrees to be at least logarithmic even in the balanced case (i.c. when all the clusters have the same size; sec c.g. []]. (2) In contrast to the work [4), our algorithm breaks the small cluster barrier and improves upon the result of [4] in the following sense: we do not need to assume there is a large interval such that the sizes clusters do not fall in, nor do bounds get affected with increasing number of small clusters. (3) As byproduct of Theorem 1.2 we give an algorithm that improves a result of (28) on partially recovering clusters in the SBM in the balanced case. We refer Appendix (eanndix(oooo for details.
In addition, the tradeoff of the parameters in our algorithm in Theorem 1.2 is nearly optimal up to polylogarithmic factors for constant y and g under the planted clique conjecture (see Appendix D).
Recovering more elusters. We can apply the above algorithm to recover even more clusters, using "peeling strategy" (see (3). That is, we first recover the largest cluster (under the preconditions of Theorem 1.2). , say Vi. Then we can remove V1 and all the edges incident them and obtain the induced subgraph of G on the vertices V := V (V1 denoting it as G'. Note that G' is graph generated from SBM(n', k- 1. P. q) where n' n [V1 Then we can invoke the previous algorithm on G' to find the largest cluster again. We can repeat the process until the we reach a point where the recovery conditions no longer hold on the residual graph. Formally, we introduce the following definition of prominent clusters.
Definition 1.3 (Prominent clusters). Let Vi,..., Vv be the k latent clusters and $1...., be the size of the clusters. WLOG we assume 81 Z Z Sk- Let k' 2 O be the small-
213. /Pll- Ei
est integer such that one of the following true. (1) 88'41
(p-9)
(2) o² < log(E 81) (2 81). We call Vi...., Ver prominent clusters V.
By the above definition, Theorem 1.2 and the aforementioned algorithm, which we call RECUR- SIVECLUSTER, we can efficiently recover all these prominent clusters.
Corollary 1.4 (Recovering all the prominent communities). Let G be graph that is generated from the SBM(n, k p. q) model. Then there exists a polynomial time algorithm RECURSIVECLLSSEER that correctly recovers all the prominent clusters of G, with probability 1 - (1).
Experimental Comparisons. We evaluate the performance of our algorithm in the simulation settings outlined in 4 and confirm its effectiveness. Moreover, the experiments conducted in [ established that their gap constraint is an observable phenomenon. We demonstrate that our algorithm can accurately recover clusters even without this gap constraint. Specifically, we succeed in identifying large clusters in scenarios where there were ?(n) single-vertex clusters, situation where the guarantees provided by 4 are inadequate. We observed that simpler spectral algorithms, such 288] also failed to perform well in this scenario. Furthermore, we observe that the run-time of our algorithm is significantly faster than the SDP based approach of [3] 4. Finally, we present empirical evidence of the efficacy of our techniques beyond their theoretical underpinnings.

---

1.1.2
An algorithm for clustering with faulty oracle
We apply the above algorithm to give improved algorithm for clustering problem in a faulty oracle model, which was proposed by [23). The model is defined as follows:
Definition 1.5. Given a set V [n]
:= (1...... n of n items which contains & latent clusters Vi, V& such that U,V, = V and for any 1 S siysjjje k, V, V,nv, = 0. The clusters Vi,..., Vn are unknown. We wish to recover them by making pairwise queries to an oracle O which answers if the queried two vertices belong to the same cluster or not. This oracle gives correct answer with probability 2 + 2. where ō E (0, 1) is a bias parameter. It is assumed that repeating the same question to the oracle O, it always returns the same answer Our goal is recover the latent clusters efficiently (i.e., within polynomial time) with high probability by making as few queries to the oracle O as possible. One crucial limitation of all the previous
@ number of queries is that they cannot recover large clusters, if there are at least (((2255) small clusters. Now we present our result
polynomial -omommme--tmeeeaee algorithms ([23 21 27
20
14)
that make sublineat
for the problem of clustering with faulty oracle.
Theorem 1.6. In the faulty oracle model with parameters n. k. 6, there exists a polynomial time algorithm NOSIYCLUSTERINGE 6), such that for any n 2 s 2 C-vThlog"" n it recovers all clusters of size larger than by making O(" n" log" n2 n² no2lo""" ") queries in the faulty oracle model.
5".g"
We remark that our algorithm works without the knowledge of k, i.e., the number of clusters. Note that Theorem 1.6 says even if there are ((n)) small clusters, efficient algorithm still find all
clusters of size larger than 22( v l) with sublinear number of queries. We note that the size of clusters that our algorithm can recover is nearly optimal under the planted clique conjecture. Due to space constraints, all the missing algorithms, analyses, and proof' are deferred to Appendix E and
1.2 Our techniques
Now we describe our main idea for recovering the largest cluster in graph G (V, E) that is generated from SBM(n, k. p. 9)
Previous SBM algorithms 'he starting point of our algorithm is a Singular Value Decomposition
(SVD) based algorithm by [28), which in turn is built upon the seminal work of 25 The main idea underlying this algorithm is as follows: Given the adjacency matrix A of G. project the columns of A to the space Ag. which is the subspace spanned by the first left singular vectors of Ag. Then is shown that for appropriately chosen parameters, the corresponding geometric representation of the vertices satisfies separability condition. That is, there exists a number r > 0 such that I) vertices in the same cluster have distance at most r from each other; 2) vertices from different clusters have a distance at least 4r from each other. This is proven by showing that each projected point Pu is close to its center, which is point corresponding a column in the expected adjacency matrix E[A] There are exactly k centers corresponding to the & clusters. Then one can easily find the clusters according to the distances between the projected points.
The above SVDD-based algorithm aims to find all the k clusters at once. Since the distance between two projected points depends on the sizes of the clusters they belong to, the parameter r is inherently related to the size of the smallest cluster. Slightly more formally, in order to achieve the above separability condition, the work (28) requires that the minimum distance (which is roughly vē(p- (((p-g)) x)) between any two centers is at least 22( ((/ns))), which essentially leads the requirement that the minimum cluster size is large, say 2( in order to recover all the l clusters.
High-level idea of our algorithm In comparison to the work (28), we do not attempt to find all the k clusters at once. Instead, we focus on finding large clusters, one at a time. As in (28), we first project the vertices to points using the SVD. Then instead of directly finding the "perfect" clusters from the projected points, we first aim to find a set S that is somewhat close to a latent cluster that is large enough. Formally, we introduce the following definition of Vi-plural set.
Definition 1.7 (Plural set). We call a set S C V as a Vi-plural set (1) |S Vil 2 213 Vn n; (2)
For any V, * V; we have S Vgl S 0.1 1.1-|Sm n V/l.
'This was known as persistent noise the literature; see e.g. 17
SSince there are On2²) number of possible queries, by "sublinear" number of queries, we mean the number of queries made by the algorithm is o(n²).
4

---

That is, a plural set contains sufficiently many vertices from one cluster and much fewer vertices from any other cluster.
Recall that s* := CVP((1-g)-n-oog for = 213, and mmax 2 8" We will find a Vi-plrra set for any (p-4)
cluster Vú that is large enough, i.e., [V]] > Amps. To recover large clusters, our crucial observation is that it suffices to separate vertices of one large cluster from other large clusters, rather than trying to separate it from all the other clusters. This is done by setting an appropriate distance threshold L to separate points from any two different and large clusters. Then by refining Vu's analysis, we can show that for any E V, with |V|| 2 Euys the set S that consists of all vertices whose projected points belong to the ball surrounding u with radius L is a Vi-plural set, for some appropriately chosen L. It is highly non-trivial to find such radius L. To do so, carefully analyze the geometric properties of the projected points. In particular, we show that the distances between a point and its projection can be bounded in terms of the k'-th largest eigenvalue of the expected adjacency matrix of the graph (see Lemma 2.2). for a carefully chosen parameter K'. To bound this eigenvalue, we make use of the fact that We refer to Section 2 for more details.
sum of many rank matrices and Weyl's inequality (see Lemma 2.3)
Now suppose that the Vi-pural set S is independent of the edges in V x V (which is not true and we will show how to remedy this later). Then given S, we can run a statistical test to identify all the vertices in Vi To do so, for any vertex E V. observe that the subgraph induced by S U {v} is also sampled from a stochastic block model. For each vertex u E Vi, the expected number of its neighbors in S is
p. p. Vil + tq. \ Vil = + q) -IS Vil.
On the other hand, for each vertex u E Vj for some different cluster V, & V,, the expected number of its neighbors in S is
p. ISS n V3++ --- 18 V3I = =s|S| + (p () -SSnns q|S (p q) 0.1 1S
since |S n Vyl S 0.1 IS n Vil for any V2 * V₁. Hence there exists @((p 9) IS Vil) gap between them. Thus, as long as |S Vi is sufficiently large, with high probability, we can identify vertex belong to V; not by counting the number of its neighbors in S.
To address the issue that the set S does depend on the edge set on V, we use a two-phase approach: that is, we first randomly partition V into two parts U, W (of roughly equal size), and then find Vi-plural set S from U, then use the above statistical test to find all the vertices of V, in W (i.e., W, 3) (i.e. Algorithm
V \ (U), as described in IDENTIFYCL.USTER,
Note that the output, say Ti. of this test is also Vi-plural set. Then we can find all vertices of V4 in U by rumning the statistical test again using Ti and U, i.c., invoking ODENTIFYCLUSTERRR Then the union of the outputs of these two tests gives us V,, We note that there correlation between Ti and U, which makes our analysis bit more involved. We solve it by taking union bound over a set of carefully defined bad events; see the proof of Lemma 2.7
U, 3).
1.3 Other related work
In [ (which improves upon 12).. the author also gave a clustering algorithm for SBM that recovers a cluster at a time, while the algorithm only works under the assumption that all latent clusters are of size l(vT), thus they do not break the "small cluster barrier".
The model for clustering with a faulty oracle captures some applications in entity resolution (also known as the record linkage) problem [46. the signed edges prediction problem in a social network [2 [26] and the correlation clustering problem [5]. sequence of papers has studied the problem
of query- query-efficient (and computationally efficient) algorithms for this model 23 21 27 20
[4]. We
refer to references 23 21 27
for more discussions of the motivations for this model.
2 The algorithm in the SBM
We start by giving high-level view of our algorithm (i.e., Algorithm 1. Let G (V,E) be graph generated from SBM(n, k p. q). For a vertex e and a set T C V, we let NT) denote the number of neighbors of in T.
We first preprocess (in Line [ the graph G by invoking Algorithm 2 randomly partitions V into four subsets Y1, Y2, Z, W such that each vertex is added to Y,, Y2, Z, W
PREPROCESSING, which
5

---

with probability
1/2, respectively, Let = -UUY--U,,,--UUU See Figure foor =
visual presentation of the partition. Let À (resp. B3 be the bi-adjacency matrix between Y1 (resp. Y2) and Z. This part is to reduce the correlation between some random variables in the analysis, similar to in [25] and 28 Then we invoke (in Line 2 Algorithm 3 ESTMATINGSIZE to estimate the size of the largest cluster. It first samples v log n vertices from Y2 and then counts their number of neighbors in W. These counters allow us obtain good approximation 3 of Smax.
We then repeat the following process to find large cluster (or stop when the number of iterations is large enough). In Line 7 we sample vertex и Y2 and consider the column vector i corresponding to in the bi-adjacency matrix Á between Y/ and Z. Then consider the projection Pxg â of u onto the subspace of the first k singular vectors of Á for some appropriately chosen k', and the set S all vertices
Y2 whose projections are within distance L/20 from Pu. for some parameter L. In Lines 1 we give process that completely recovers large cluster when S is a plural set. More precisely, we first test if [S] 2 8/21 and if so, we invoke Algorithm 4 to obtain Ti IDENTIFYCLUSTER//
3), which simply defines Ti be the set of all vertices with (s( 2 S + (p q) 36 Then we check (Line 10) if the set Ii satisfies few conditions to test if u is indeed a good center (so that is a plural set) and test if Ti = V1 n W. so, we then invoke IDENTIFY CLUSTER U,3) to find V1 N. Note that we use two-step process to find Ví. as (u) is not a sum of independent events for u E U.
W
Algorithm 1 CLUSTER(G (V, E), g): Recovering one large cluster
1: Á, B,Y, Y, Z,W PREPROCESSSING g)
2: 6 ESTIMATINGSSIEE(C p, q. W, Y2)
3: for i 1,..,, h /n log do
4: sample vertex u from Yn
5: u tte column vector consisting of the edges between u and Z
6: Pu + PA. ú. the projection of ú onto the subspace of the first ke singular vectors of Å.
where K' = (p= /V/ p(L q)
7:
S - f 12: [|pm Pvll S ). where Pv f- P7 v and L v0.004(p v)
8:
if | 3 then
9:
Invoke IDENTIFYCLUSTER(S, W. to get set Tj
if Ti S I
6 or 3e Ti s.t. Nr, (v) I (0.9p + 0.1q) [Til or Ee W T1 s.t.
N1, (v) 2 (0.9p + 0.1q) [Ti] then
11:
continue
12:
else
Invoke IDENTIFYCLUSSTRRCT U, (T) to obtain set T2 Merge the two sets to form 7 =T; UT2 Return
14:
15:
16:
Return 0
2.1
The analysis
We first show that ESTIMATINGSIZE outputs an estimator approximating the size of the largest cluster within factor of 2 with high probability.
Lemma 2.1. Let 3 be as defined in Line 6 Algorithm 0.48 5max I 3 < 0.52 5max.
Then with probability 1 1 we have
Recall that À (resp. /3) is the bi-adjacency matrix between Yi (resp. Y2) and Z. Let A and B be the corresponding matrices of expectations. That is, A = A + E, where E is a random matrix consisting of independent random variables with O means and standard deviations either vp(1 p) or V1(1 9).
For vertex u Yi, let and u represent the column vectors corresponding in the matrices A and A respectively (We define analogous notations for B and B when u E Y2.). We let en = û u, i.e., is the random vector with zero mean in each of its entries. Recall that Pa. = P û.

---

Algorithm (V, E), p.p.p. p. W, the largest cluster
3 ESTIMATINGSIZEGG
Estimating the size of
W
1: 8" < 213 V pppppp1100001 vnll-g)-/n-loga
for i = 1,... (p-4)
vn log
3: sample u, from V2 uniformly at random.
4: Nw(u,) t # of neighbors of u, in W.
5: f arg max (ws)
(w)
(p-9)
7: 8 < 8 /3 then
Figure 1: Partition of the vertices
8: Exit(O)
9: else
Algorithm 2 PREPROCESSSIGGG. P, g):): Parti- tion and projection
10:
Return
1: Randomly partitions V into four sub- sets Y1, Y2 Z, W such that each vertex is added to Y1, Y2, Z, W with probability 1/8, 1/8, 1/4, 1/2, respectively.
Algorithm 4 IDENTIFYCLUSTER(S, R, 8): Find- ing subcluster Rn Vi using Vi-plural set S
T
2: Let Y Y1 U U22,4 =
2: for each v E R do
3: Let Å (resp. B) be the bi-adjacency matrix
Ny.s 2 q (p 9) 56 then
between Y1 (resp. Y2) and Z.
4:
add to T
4:
Return A, B, Y2, Y1, Z.W
Return T
Now bound the distance between Px ú and the expectation vector u. We 0.002 in the following.
Lemma 2.2. Follows the setting of Algorithm
2 fix Y, Y2, Z, W. For any vector E Y2 and 2 we have [ (ū) - u/ v Vsn. IP T) [P (ew).ll
Furthermore, for some constant Cz. and E as described above we have
1. [1(PA - A] = Il(PAr - -T) (Pāy. FII S 2020 /n d (A) with probability
) for a random Å, where (A) is the t-th largest sigular value of A.
2. For any set V C Y2 [V Llogn, with probability n we have Agg. (ew)ll S
LoVE for at least (1 2c) fraction of the points V'.
We have the following result regarding the 1-th largest singular value (A) of A. Lemma 2.3. For any > 1, (x) & (p- q)n/t.
Now introduce the definition of good center, the ball of which induces a plural set. Definition 2.4 (Good center). We call vector û B a good center if belongs to a cluster such > Sups and Pa (ew) < LoVK.
that [V|
That is, a good center is a vertex that belongs to a large cluster and has a low & norn after the projection. Then by Lemma 2.2] we have the following corollary the number of good centers.
Corollary 2.5. If Smax 2 1 llggo n, then with probability n- there are (1 (s) 8max many good centers in
This implies that if sample 100m logn many vertices independently at random, shall sample good center with probability
Good center leads to plural set We show that if at line a good center from a cluster V, is chosen, then the set S formed in line is a Vi-plural set. Recall that L v0.004(p q) V3. Let L: = L.

---

Lemma 2.6. Let u be a good center belonging to Vin Y2 and S = {u Y2: Pu Le/20 20) Then it holds with probability 1 (n 5) that [V; 8 2 s/21 and for any other cluster V₂ with L + 1, SS n V I 1.05es. Thus S is a V; plural set as 1 /221 1/10 2 1.05s.
Piural set leads cluster recovery We now prove that given plural set for large cluster Vi we can recover the whole cluster. This is done by two invocations of Algorithm 4
Lemma 2.7. Let U, W be the random partition as specified in Algorithm 7 Let S C Y2 be the
Vy-plural set where [Va| Smax/4. Let Ti IDENTIFYLLUSTER W,3) 3) and T == Ti IDENTIFYCLUSTER (Ti, U,3). Then with probability 1 - On )), it holds that Ti = V1 n n.,
T 2 ge and T ===;, Vi.
Testing if Ti is sub-cluster Since S may not be plural set, show that we can test if T = W n Vi for some large cluster V, using the conditions of Line of Algorithm !|
Lemma 2.8. Let v be a good center from Ve n Y2 such that [Vi] Z Smge and let S = {u E Y2 : 1lluu -Pvll S 30 Let T1 be the set returned by IDENTIFY W, 3). Then with probability at least 1 n= 8, [Til 2 and NT. (u) 2 (0.9p + 0.1g)]Ti| any E Ti and Nr,(u)= S (0.9p + (. any u E T1.
Finally, we show that if the set Ti + V. n W for some large cluster Vi, then it satisfies one of the Together with the previous results this guarantees correct
conditions at line 10 of Algorithm| 1 recovery of large set at every round.
Corollary 2.9. Let Ti-
W,8) be a set such that Ti # V; n W for any underlying community V. of size |V.| 2 mmax/ /7. Then with probability 1 1- n either [Ti S or there is a vertex u E Ti such that Nr, (u) S (0.9p + (Tll
ODENTIFYCLUSTERR
Remark 2.10. Note that in Lemma 2.8 and Corollary 2.9 the quantity NT, (u) for any u E Ti is a sum of independent events. This is because the event that vertex in v E W is chosen in Ti is solely based on N5, where S SNT = O. Thus, for any u1, ug E T, there is an edge between them (as per underlying cluster identities) independent of other edges in the graph.
The proof's of the above results are deferred to Appendix 2.1
Now we are ready to prove Theorem 1.2
Proof of Theorem 1.2
By the precondition, we have that maxx 2 s" First, in Line 2 Lemma 2.
guarantees that 0.48 S max S S 0.528maxx By Corollary 2.3 and the fact that we iteratively sampled vertices Q(vn log n) times, with probability 1 1-n -8, one such vertex u is good center. Given such a good center, by Lemma 2.6 we know with probability - O(n 2), a Vi-plural set is recovered on Line 7 Then by Lemma 2.7 given such V/,plural set, the two invocations of IDENTIFY recovers the cluster VÚ with probability 1 - O(n Furthermore, Lemma 2.8 shows that if the sampled vertex v is good center, then with probability 1 - - none of the conditions of line 10 are satisfied, and we are able to recover a cluster. On the other hand, Corollary 2.9 shows that if T o V1 W for any large cluster V4, (V/ [V] 2 smax/ then one of the conditions of line I0 is satisfied with probability 1 - n and the algorithm goes to the next iteration to sample new vertex in line 4 Taking a union bound on all the events for at most O(ynlog n) iterations guarantees that algorithm| ! finds a cluster of size smax/7 with probability - Onn This completes the correctness of Algorithm I
3 The algorithm in the faulty oracle model
We describe the main ideas of our algorithm NOISYCLUSTERING for clustering with faulty oracle. Let V be the set of items that contains k latent clusters Vi...., Vi and O be the faulty oracle. Following the idea of (27), we first sample a subset T C V of appropriate size and query Olu, v) for all pairs u, v E T. Then apply our SBM clustering algorithm (i.e. Algorithm [ CLUSTER)) on the graph (with all the edges for the pairs that are reported to belong to the same cluster) induced by T to obtain clusters X1,- XI...., X, for some S k. We can show that each of these sets is a subcluster of some large cluster V. Then we can use majority voting to find all other vertices that belong to X,, for each < t. That is, for each X; and v E V. we check if the number of neighbors of in X; is at least [xd] In this way, we can identify all the large clusters V, corresponding to X,, 1 - i < t.
8

---

Furthermore, we can just choose a small subset of X; of size O ((( for majority voting to reduce query complexity. Then we can remove all the vertices in V and remove all the edges incident to them from both V and 7 and then we can use the remaining subsets T and V and corresponding subgraphs to find the next sets of large clusters. The algorithm NOISYCL.USTERIN then recursively finds all the large clusters until we reach point where the recovery condition on the current graph no longer holds. The pseudocode and the analysis of NOISYCLUSTERING are deferred to Appendix
4 Experiments
Now we exhibit various properties of our algorithms by running it on several unbalanced SBM instantiations and also compare improvement w.r.t the state-of-the-art. We start by running our algorithm RECURSIVECLUSTER on the instances used by the authors of [4]. WLOG, we assume that
|Vil V2- 2 Vvll We denote the algorithm in 4 by ACX.
Recovery by ACX
Exp.
n
P. Q
Cluster sizes
Recovery by us
1100
0.7, 0.3
4
(800, 200, 80, 2
Largest cluster
All clusters
2
3200
0.8, 0.2
5
{800, 200, 200, 50, 50}
Largest cluster
All clusters
Incorrect
3
750
0.8, 0.2
4
(500, 150, 70, 30}
Largest cluster
Recovery
Incorrect
4
800
0.2
4
(500, 200, 70, 303
Two largest clusters
Recovery
Table 1: Comparing RECURSIVECLUSTER with ACX 4
Comparison with ACX In Exp-1 (abbreviated for Experiment #1) and Exp-2, our algorithm recovers the largest cluster while ACX recovers all the clusters. This is because we have a large, constant lower bound on the size of the clusters we can recover. If we scale up the size of the clusters by a factor of 20 in those instances, then we are also able to recover all clusters.
Overcoming the gap constraint in practice Exp-3 is the "mid-size-clustedr experiment in [ In this case, ACX recovers the largest cluster completely, but only some fraction of the recond-larges cluster, which is an incorrect outcome. In [4]. the authors used this experiment to emphasize that their "gap-constraint" is not only theoretical artifact but also observable in practice. In comparison, we recover the largest cluster while do not make any partial recovery of the rest of the clusters. In Exp-4, modify the instance in Exp-3 by changing the size of the second cluster 200. Note that this further reduces the gap, and ACX fails in this case as before. In comparison, we are able to recover both the largest and the second largest cluster. This exhibits that we are indeed able to overcome the experimental impact of the gap constraint observed in 4 in the settings of Table |
Exp. #
n
q
k
Cluster sizes
Recovery by us
5
2900
0.7, 0.3
1000
{1000, 903) U (1)927
Large clusters
6
12300
0.85, 0.15
4
(12000, 100, 100, 100)
All clusters
Table 2: Further Evaluation of RECURSIVECH..STRR
We then run some more experiments in the settings of Table 2 to describe other properties of our algorithms as well as demonstrate the practical usefulness of our "plural-set" technique.
Many clusters Exp-5 covers situation where ls (()) (specifically n/3), which can not be handled by ACX, as the size of the recoverable cluster in 4 is lower bounded by k log n/(p g)² > n. In comparison, our algorithm can recover the two main clusters. We also remark, in this setting, the spectral algorithm in (88 with k- 1000 can not geometrically separate the large clusters.
Recovery of small clusters Exp-6 describes situation where the peeling strategy successfully recovers clusters that were smaller than v n in the original graph. Once the largest cluster is removed, the smaller cluster then becomes recoverable in the residual graph. Finally, we discuss the usefulness of the plural set.
Run-time comparison Here, note that our method is combination of a (p- (0--V/n/v// VP( g) dimensional SVD projection, followed by some majority voting steps. Furthermore, we have

---

ip-9)/Vp(L-q) S 2VD. This implies that the time complexity of our algorithm is O (2/p.1 n2.5). In comparison, the central tool used in the algorithms by [ is an SDP relaxation, which scales as (nn)). This implies that the asymptotic time complexity of our method is also an improvement on the state-of-the-an for small values of n. For example, our algorithm recovers the largest cluster in Experiment 1 (with n = 1100) of table in 1.4 seconds. In comparison, 3 recovers all 4 clusters, but takes 44 seconds.
We also confirm that the difference in the run-time becomes observable even
On the importance of plural sets Recall that in Algorithm I (which is the core part of RECUR- SIVECLUSTER), we first obtain a plural-set S in the partition Y2 of V (see Figure I to recall the partition). S is not required to be V, n Y2 for any cluster V,, but the majority of the vertices in S must belong to a large cluster V, (which is the one we try to recover). We have the following observations:
1. In Exp-3 of Table D in the first round recover cluster V1. Here in first step, recover a plural set S, where S C. V1 n Yg. That is, we do not recover all the vertices of Vi in Y/ when forming the plural-set.
2. In Exp-4 of Table [ in the second iteration recover cluster V22 However, the plural set S E V2, and in fact contains a few vertices from Vi! This is in fact the exact situation that motivates the plural-set method.
In both cases, the plural-set is then used to recover S := V1 n W and 1/2 n W respectively, and then S1 is used to recover the vertices of the corresponding cluster U. Thus, our technique enables us to completely recover the largest cluster even though in the first round we may have some misclassifications. A more thorough empirical understanding of the Plural sets in different applications is an interesting future work.
We conclude our paper with some more discussion and future directions.
Conclusion
In this work, we design spectral algorithm that recovers large clusters in the SBM model in the presence of arbitrary numbers of small clusters and compared to previous work, we do not require gap constraint in the size of consecutive clusters. Some interesting directions that remain open are as follows.
1. We note that both our algorithm and 4 require knowledge of the probability parameters and q (4) also need the knowledge of k. the number of clusters). Thus, whether parameter- free community recovery algorithms can be designed with similar recovery guarantees is very interesting question.
2. Both our result (Algorithm [ as well as 4 have multiplicative log n term our recovery guarantees. In comparison, the algorithm by Vu (28). which is the state-of-the-ard algorithm in the dense case when "all" clusters are large, only has an additive logarithmic term. This raises the question of whether this multiplicative logarithmic factor can be further optimized when recovering large clusters in the presence of small clusters.
Additionally, we note that the constant in our recovery bound is quite large (213), and we have not made efforts optimize this constant. We believe this constant can be optimized significantly, such as through more careful calculation of the Chernoff bound in Theorem A.2
References
[1] Emmanuel Abbe. Community detection and stochastic block models: recent developments. The Journal of Machine Learning Research, 18(1):6446-653) 6531, 2017.
[2] Emmanuel Abbe and Colin Sandon. Community detection in general stochastic block models: Fundamental limits and efficient algorithms for recovery. In 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, pages 670-688. IEEE, 2015.
[3] Nir Ailon, Yudong Chen, and Huan Xu. Breaking the small cluster barrier of graph clustering. In International conference on machine learning, pages 995-1003, PMLR, 2013.
10

---

[4] Nir Ailon, Yudong Chen, and Huan Xu. Iterative and active graph clustering using trace norm minimization without cluster size constraints. J. Mach. Learn. Res., 16:455-490, 2015.
[5] Nikhil Bansal, Avrim Blum, and Shuchi Chawla. Correlation clustering. Machine learning. 56(1-3):89- 113, 2004.
[6] Béla Bollobás and Alex Scott. Max cut for random graphs with a planted partition. Combina- torics Probability and Computing, 13(4-5):451-477 2004.
[7] Ravi B Boppana. Eigenvalues and graph bisection: An average-cast analysis. In 28th Annual Symposium on Foundations of Computer Science (sfes 1987), pages 280-285. IEEE, 1987.
[8] Thang Nguyen Bui, Soma Chaudhuri, Frank Thomson Leighton, and Michael Sipser. Graph bisection algorithms with good average case behavior. Combinatorica, 7(2):171-11, 1987.
[9] Kamalika Chaudhuri, Fan Chung, and Alexander Tsiatas. Spectral clustering of graphs with general degrees in the extended planted partition model. In Conference Learning Theory, pages 35-1. JMLR Workshop and Conference Proceedings, 2012.
[10] Yudong Chen, Sujay Sanghavi, and Huan Xu. Clustering sparse graphs. In Proceedings of the 25th International Conference on Neural Information Processing Eestems-Volumme 2, pages 2204-2218 12, 2012.
[11] Sam Cole. Recovering nonuniform planted partitions via iterated projection. Linear Algebra and its Applications, 576(1):79-107,, 2019.
[12] Sam Cole, Shmuel Friedland, and Lev Reyzin. A simple spectral algorithm for recovering planted partitions. Special Matrices, 5(1): 1573399-7771111 2017.
[13] Chandler Davis and William M Kahan. Some new bounds on perturbation of subspaces. Bulletin of the American Mathematical Society, 75(4):863-868, 1969.
[14] Alberto Del Pia, Mingchen Ma, and Christos Tzamos. Clustering with queries under semi- random noise, arXiv preprint arXiv:2206.04583 To appear at Conference on Learning Theory (COLT) 2022, 2022.
[15] Martin E. Dyer and Alan M. Frieze. The solution of some random np-hard problems in polynomial expected time. Journal of Algorithmss 10(4):451-489, 1989.
[16] Ivan P Fellegi and Alan B Sunter. A theory for record linkage. Journal of the American Statistical Association, (43328):1133-2210 1969.
[17] Sally A Goldman, Michael J Kearns, and Robert E Schapire. Exact identification of circuits using fixed points of amplification functions. In Proceedings [1990] 31st Annual Symposium on Foundations of Computer Science, pages 193-202 IEEE, 1990.
[18) Wassily Hoeffding. Probability inequalities for sums of bounded random variables. Journal of the American Statistical Association, 58(301): 1963.
[19] Paul W Holland, Kathryn Blackmond Laskey, and Samuel Leinhardt. Stochastic blockmodels: First steps. Social networks, 109- 1983.
[20] Zengfeng Huang Jinghui Xia. Optimal clustering with noisy queries via multi-armed bandit. To appear the 39th International Conference on Machine Learning (ICML 2022), 2022.
[21] Kasper Green Larsen, Michael Mitzenmacher, and Charalampos Tsourakakis. Clustering with a faulty oracle. In Proceedings of The Web Conference 2020, pages 2831-2834, 2020.
[22] Jure Leskovee, Daniel Huttenlocher, and Jon Kleinberg. Predicting positive and negative links in online social networks. In Proceedings of the 19th international conference on World wide web, pages 641-650 2010.
[23] Arya Mazumdar and Barna Saha. Clustering with noisy queries. In Advances in Neural Information Processing Systems, pages 5788-5799, 2017.

---

[24] Arya Mazumdar and Barna Saha. A theoretical analysis of first heuristics of crowdsourced entity resolution, In Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence. pages 970-976, 2017.
[25] Frank McSherry. Spectral partitioning of random graphs. In Proceedings 42nd IEEE Symposium on Foundations of Computer Science, pages 529-5 537.. IEEE, 2001.
[26] Michael Mitzemmacher and Charalampos E Tsourakakis. Predicting signed edges with o(n log n) queries. arXiv preprint (ef:::6600000000 2016.
[27] Pan Peng and Jiapeng Zhang. Towards a query-optimal and time-efficient algorithm for clustering with faulty oracle. In Conference Learning Theory, 2021.
(28) Van Vu. A simple svd algorithm for finding hidden partitions. Combinatorics, Probability & Computing, 1221) 2018.
[29] Jaewon Yang and Jure Leskovec. Defining and evaluating network communities based on ground-truth, Proceedings of the ACM SIGKDD Workshop on Mining Data Semantics, pages
1 1-8, 2012.
12

---

A Preliminary Notations and Tools
Notations for vectors. Let M be the adjacency matrix of the graph G = (V, E) that sampled from SBM(n, k, q). We denote M the matrix of expectations, where M if the i-th and j-th vertices belong to the same underlying cluster, and M[i,j] = otherwise. Going forward, we shall work with several sub-matrices of M and for any submatrix M'' we denote by M' and M' the random matrix and the corresponding matrix of expectations.
We also use the norm operator || frequently in this paper. We use the operator both for vectors and matrices. Given vector (Z1...., Id)) let ||x|| := v Σ, x² denote its Euclidean norm. When the input a matrix M, || || denotes the spectral norm of M, which its largest singular value.
We describe the well-known Weyl's inequality.
Theorem A.1 (Weyl's inequality). Let Å = A E' be matrix. Then (A41(A) S )4+1(A) + | where is the spectral norm operator as described above.
We will make use of the following general Chernoff Hoeffding bound.
Theorem A.2 (Chernoff Hoeffding bound (18). Let X1,..., Xn be i.id random variables that can take values in {0, 1}, with E[X;] for sis n. Then we have
1. Pr 1 E.
X, 2 p+ c) S D(p+elle)n
2. Pr (E X, p s) S é e D(p p)n
Here (> the KI. divergence of x and y.. We recall the KI. divergence between Bernoulli random variables z, y (x
(z/v) + (1-x) In((1 - z)/(1 v)). it is easy that If [x [x-v) and D( y) 2 (z-2)² otherwise.
& 2 y, then D(x (v) 2
2x
also note down a random projection Lemma that we use in our proof.
Lemma A.3 (Expected random projection (28).. Let Pag. be a k' -dimensional projection matrix, and cu be an dimensional random vector where each entry is 0 mean and has variance of at most σ². Then we have E[[| P (cw))l²]= < o² k..
B Deferred Proofs from Section 2
We first give general concentration bound concerning neighbors of vertices in the different partitions. Lemma B.1. Let be a set of n vertices sampled according to the SBM k. p.9) model. Let V' C V where the vertices in V are selected independently each other. Let V, be a latent cluster with V -V, V' We denote by Ny.(u) the number of neighbors of u in V". Then with probability 1 O(n 77) we have for every V!
(0-+)0-0)V <Nv.(u) S s0l41 - VV' n V/l + 48 vp logon.
16 VD- Vn logn
We look two different sums of random variables. The first is Nyy which the sum of IV; n VlI many random 0 variables with probability of 1 being p. The second is Nv which is the sum of [V' V/l variables with probability of 1 being q.
Proof of Lemma B.
Then we have (u)] = P|V n V'l and E[Nv = =q V' V/ Finally the Chernoff bound implies,
Pr
Ny (u)
< - S e - D(p-al eI| We fix a
8/ and then the term MT
D(p -allp) VV' evaluates
V.
8 n 2 2logn
[
log n n
D(p v/l 2
2
2 8 88log n.
2p
2 2p
V
13

---

This gives us
Pr (Nv; < SVDVnlogn) S 5n8
2. Pr
(w) TWAI
<9 S
se-
We fix 3 SyDvilogg TVA and the term
Dgg B11g) V Vi
evaluates to
8²
8. 2log
p. p-8logn
D(q - V
2 8logn.
24
2/
g
V
This gives
Pr (N (u) < V 1 - 8/FVnlogg) sn
(2)
Combining Equation and
gives us
Pr (Nv;(u) Nv < p|V log///loogntt ggV' \ V 8/P/nlogg) S 2n Pr (N) < o v/ + (p- q) - 16 16 - 2n -8
Now we study the event (u) 2 V + (p 2)( n V + 48 vp- / log n again by breaking into two terms.
The probability bounds for two terms Nyy(u) and Nv 3 |D] and e -Pa++3/lla) VAVI respectively. Here note that we use 3a instead of a, to make cal- culations easier.
For the first case have D(p 3allp)) 2
2(p+3a) If 2 then D(p + al|p)|(? >
9a 9a? 8p which implies we get the same bound as above. If < a then D(p+alpp)l
9
Sa 2 aVVi Now we have a /.FuRlogm Since p = ((logn/n) we have
[V'
alV'' 2 8 log n. Combining we get that -D(pt2allpiiV < n
-.Р As before, if q 2 8 we have 2(++3))
Next we analyze D(q 3
V/I
D(g + V
V 93
2
933|V| and the result follows as before. Otherwise D(g
84
33 [V) \ 1/11= Z
z 3 \ ViI 2 8/DVnlogr 2 llggn, which completes
8D
the proof.
Then Lemma 2.1 can be proved as follows.
Proof of Lemma 2. We know that 8max v (Pllg)ynn log from the problem definition. Let
p-y
the corresponding cluster be V,, Then a simple application of Hoeffding bounds gives us that with probability 1 8 0.51 Smax n W| 2 0.49 8max.
Furthermore, we are interested in the regime where p S 3/4 so VI q 2 1/2.
Then if we sample u E [V, n Ygl. Lemma B.1 states that with probability n
(p q) 96 v p(1 g) Vn
(w) - g/Wl- (p- 4)ll4 n W < 48/pv/llogn S
(p (p-4) 4)
(p nww
(Nw(u) g W| (p 9) W|| <
100
This implies with probability -8, g + 1.01 w| 2 (w) 2 g/W| V. n W which coupled with the fact 0.49 < |K' from the largest cluster, get estimate of s max described.
< 0.51 implies that if we are able to sample vertex
14

---

Since n 2 1 n. if we sample lo vertices, we sample a vertex u from V2 with probability 1 Now, for vertices belonging to smaller clusters, the same bounds apply, and this implies that as long as we are able to sample vertex from the largest cluster, we get an estimate of Smax between a factor of 0.48 and 0.52.
These results follow directly from Vu (28 with some minor modifications. In their paper, decomposes the matrix into and
Proof of Lemma 2.2
comparison, we decompose the matrix to U and W first, and then U is decomposed into Y and Z. Thus the size of Y and Z in our framework is roughly half as compared to [88. However, since the size of the clusters we are concerned about are all larger than 128 vn log the results follow in the same way with change of a factor of 2.
Now we describe the results and how we deviate from Vu's analysis to get our result. For the first part, in (28) page 132] it was proved that for any fixed û B,
Pr ④ - ul = [P (ū 2) + (Pā - -l)lll
< PA. (ea)ll + II(PA Ax - -Tulll S PL (en)ll + 1 1p - 1)
VBu
Furthermore, it was proven (also in page 132 of (28) that
(P
1A
(Pxx I)Å (Pxr 1)E
was observed that (P%, - r) - Ax+1 $ Ax+1 (A) + |E|| | as A has rank at most k;
and (Pa, -)E S ||| Then from Lemma 2.2 in 28 we have that with probability 1 - On
||_| S 1/2 for some constant C2 > 0.
Next, we observe that for any k' 2 it still holds that
P Ag @ ul
P Ag (ū- u) + (PA T)ull
- || 11 (ew)l + 11(Px r'ulll S [1 (ew)l + +1((Xx - -1)All/ V
Furthermore,
11 [1(P - -)A = 11(Pr - 1)A - (PAN - 1)EEll
$ 11(PA - -1)AlI + 11(Px 1)E1
S A + ||
S \ + 2 ||ll|
Again, with probability at least 1 - 1/n²3, || & C20 which further implies that
|l(PA l| I 2n + (1A).
This is simple but crucial step that removes dependency on k and allows to treat all clusters of size o( o(yn)) as noise.
Now, we analyze the first term. From Lemma A.3 we have Bill Agl (e.)) S o²k' for any u E Y2.
Then for any u, Markov's inequality gives us Pr [I (ew)l )1 2 oVF
S..
Now let us consider any set V C Y2 such that [V' 2 16ynlogn. n. For any u V we define X, to be the indicator random variable that gets if [1 Av. (ew))l < ove and 0 otherwise. Then E[X,] 2 E. Now, since V" Y2, the variables X, are independent of each other (as e, are the Chernoff bound gives us independent of each other). Then, using the fact that [V' > es
1 IV
Pr
Σ X < - -) - -e1") se
I
uEV'
That is, with probability at least 1 - - for at least (1 - 2s) fraction of the points u E V', [| Ag (ew)ll < Lovk.
15

---

Proof of Lemma 2.3 Let there be k many clusters Vi..... V& in the SBM problem. Then we define n2 matrix where n1 Ei=1 ai
a, IV. n Z and b,- |V4 n Yil- Then we have that A is
and n2 -i= b,. The matrix can be then written as a sum of lo + many rank matrices:
A Σ +
Here Mo is the all matrix, and M, a block matrix with I's in a o, x b, sized diagonal block. Since M, is a a; 6; block diagonal matrix of rank 1, with each entry being (p q), its singular value is (p a.,b. Now we define A1 Σi= 9). As M,'s 's are non-overlapping block diagonal matrices, the singular vectors of M, are also singular vectors of A1, with the same singular values.
Thus, the sum of singular values of A1 is (p 9) E Va,b; S (p 2) ming S (p-g)m where the first inequality follows from the Cauchy- Sechar- inquuality. Thus, for any 2 1
2
(p g)m
Ax(A)) S Ai()) + Ae(A)) S
which gives (A11 <
(m-g)m 2t
Since Mg has rank 1, A2 Mo) and thus for t >
we have
(p g)m
(p 9)m
(A) s (A1) X2 Mo) v
2t
t ++1
where the first inequality follows from the Weyl's inequality.
The guarantee of obtaining plural set is consequence of Lemma B.2
Lemma B.2. Let k' (p-glyn and 0.002. Let E Y2 be good center belonging V,, then vp(1-q)
1. There a set V C Y2 Vv such that |V/| 2 (1 - 2s) Ye n Vil so that for all v E Vi, we with probability - O(n ))
have [| (u v)ll S 30
2. For any V3 + V; which e-large cluster, there is a set V C V2 nY, s. [V] Z
(1 V_ n Y2) that for all v E Ví have [| (u v)ll 2
Le with probability
O(n 3)
First note that Lg 2 /22-211. (p-q) (p(l -1) 10g 1/2
Proof of Lemma B.2
132,000
(p-q)
4)2/2 (p(1 //4
2/4 Vlog n.
When and belong to the same cluster we have || |/ (ύ-v)ll s | Ag. (ū) - 10]-u/1+ uul+ (V) uV)-ull
Now, since us is a good center, from Lemma 2.2 we have
|P i ull S OVW
12Coo (w41(A))
V
1
V Vp(1 DVF +
1
(2C2vpl p(1 Vvn (A) + [[E1)
(2C
8
1
1
Vp(1 V) +
C2vp(11-)) Ne414))
VSy
1
1
(p (pm9)m) k'
Vo(1 OVF +
[Substituting Aw+1(A) from Lemma 2.3)
VBu
(p(1 1/46 122 1/4 (C2(())
(22(1 9)) 1/4 log 1/2
(p(1 4) 14((p 1/2 1/4
10, 000L
L
<
for n 2 64
132, 000 1/2
60
16

---

Now from Lemma 2.2 we also know that at least (1 11-22 2:) fraction of the vertices e E are also "good centers" with probability 1-n For all such vertices Ap. (ū-V)l < 2/ Ax (ū (ū-u)l - 56 with probability n=3
On the other hand when they belong to different clusters we have
| (ū 1) 2 ||u mll Px. (ū u)ll -I (v w)ll-
Since Vj a e-large cluster, [V] 2 256 n log n and thus [V, n n22 2 16 n with probability
1 1n R)) In that case for at least 1 2 fraction of points e E VG VynY2 we have Px. (V ---0) v) < 60
Now uu vl| 2 (p-9)) V5 s, 2 126-(p-g)v/Bm /mmmm 22 v0.52.6
Ly with probability 1-n
3
from Lemma 2.1 Thus with probability n we get
L
L
A (u w)ll u w1| - || (ū Q)I 1122 (v w)ll
5
60
6
for 1 2: fraction of points v E Y2 n V for any e-large cluster Vj. This completes the proof.
Proof of Lemma 2.6 By Lemma 2.1 we have [Vi] 2 Emax 2 with probability - Then the following events happen.
2.1
1. Since u E VVnY, is good center, for 2a fraction of points in V; Y2, ll - pv| <
/e0 with probability 1 O(n as per Lemma B.2 All such points are selected to S. Furthermore, 1V; n Y2 is lower bounded by V/1/9 with probability
Therefore,
with probability 1 - O(n we have
[VSS| 2 (1 22 Y2 (1 V 2 (1 2 2 3/21.
2. For other clusters Vz, if [V/] > mmax, we have ||pm pv
< Le for only 2s fraction of T
points v in V2 n Y2 from Lemma B.2 Thus 15 n Vol S 2$
V2 n Y2). On the other hand
V22 nYl S |Vel66. Thus, with probability - n we have
2. Smax
2 3
|S Vol S V2/66 <
0.78
6
0.48 6
3. Otherwise, if V2 is such that 5 Smax 2
|/ > smax, then VV/ n Y/ S |Vil66 with
probability 1 - n 8 Then IS n Vzl S 88 / S E3.
4. Otherwise, if Vil S Smax then |S V2 S Vi Smax I
1.05
2-0.18 0.96
Now, note that for any 1/2 with l A it holds with probability 1 1-0 O( that S < 11.55 < (21 1.05-115-- -055-5)... 8) 27
< 0.05 _
27
We first show that if 5 is a Vi-plural set with V; 2 9,ax/4, then T = V4 n W where T₁ is the outcome of IDENTIFYCLUSTER (S, W, 8). Since S is V. plural set, for any vertex v E W n V., from Lemma B.1 we have that with probability 1 - (O 3).
Proof of Lemma 2.7
Ns(v) 2 d + (p - 1)
48 /P DVV logn
3
48
(p 4) V p(1 4) Vn log
Ns(v) g (p (p-
21
VI
q
(p 4)
96 v p(1 g) logn
= Ns(v) 2 g (p g)
(p q)
21
(p 9)
96
= Ns(v) 2 g (p ( 9)
(p q)
21
213
8
= Ns(v) 2 2 (p 9)
28
17

---

Now, let us consider the case when v E V, n W
where j + i. Then we know from Lemma 2.6
|S Vgl & 1.05es I 210
3
Then using Lemma B.1 we have that with probability - O(
Ns(v) - g|5] + (p v)lV n 24/pv/
3
24
Ns(1) S g/8| (p 9)
(p ?)
210
213
3
Ns(r) S g|8 + (p g) 128
Now note that in the IDENTIFYCLUSTERR W 3) algorithm, select all vertices from W that have
g|S + (p- q) neighbors in S. Thus, the above analysis implies with probability 1- On 3) T = IDENTIFYCLUSTER(S 3. = V, n W. Furthermore, since |Vil 2 Smax /4, we have
| WOWi W -
88.18 22 3/6.
We then use Ti as plural set to recover Vi n U so that we are able to recover all the vertices of V., but now Ti and are not completely independent and thus we cannot proceed simply as before.
We overcome this by an union bound based argument. Let's consider TV = V n W for any i such that T 8/6. Then have the following facts.
1. Let U n V, Then [[Nr p|T Then Lemma B.1 shows that Pr(Nr(") s q + + 0.99(p - 1) S n
2. Similarly, let a E U n Vj. Then Pr(NT, (u) 2 q T + 0.01 9) T') S n n0
If either of this is true for a vertex over all Vi2 and all u E U gives us that no vertex u E U is bad w.r.t any TV with probability 1 -
then we call it bad vertex w.r.t TV Then union bound
Then make this argument for TV = Ti. Since [V] > mmax/4. /4, we have |V; n W 2 V1/3 with probability - n n-88 Then with probability
n 8 no vertex u E is bad w.r.t Ti.
Then applying Lemma B.1 to Ti w.r. vertices in U we get, with probability O(n
1. If E E then N7; (v) 2 7i + (p v) Ti - (v 4)
2. If Vynu, then No, (v) I 7i + (p -
Ti
96
Thus IDENTIFCCLUSTER(I,, U,3) only selects the set of vertices T3 in V42 n U. Then taking the union of Ti and T3 gives us V.
Proof of Lemma 2.8 Since [V] > 256 log n and every vertex of Vi will be assigned to W with
with probability - Furthermore if VVI 2 T then Lemma 2.7 shows Ti = V n W and [T
probability 1/2, we have that 1V: n W
>
Vi
Suma 10
Z 0.52-10 2 Gi
2.5
Furthermore, for any vertex u Ti {c). we can calculate Nr, (w) in the following way.
We have E[N,, (w) = p Ti.. Then a simple application of Lemma B.1 give us that with probability
1 - n 5, Ny. (u) 2 p - (p- 4) Th 2 (0.9p + 0.1g)/Til-
Similarly, since Ti = V/2 n W for any vertex E W Ti, we have E|,Y, (w) g/Zi| and Lemma B.1 implies that with probability 1
T
T
< (0.33p 0.674) < (0.9p + 0.1g) Ti
Nv, (w) < q + (p 4)
<
+
96
3
3
Proof of Corollary
2.9 If Ti is pure subset of some V,, such that [V] S Smax 7, then with
probability 1 - Onn ). (Yg n Vil < 3/6. If [Ti] < E. the first condition is satisfied.
18

---

Otherwise if [Ti] 2 8 and Ti is not a pure set, there exists V, such that gI =
Fi
In that case
for any vertex V2 Ti have E[Nr, (v)) with probability n
- o Ti + (p- q)²² 2 and Lemma B. implies that
T 2
Tr
Nr, (w) - g/zil+(p-g)))
+(p ②)
- (0.5+1/99)) (05-
(0.9p+
96
Finally Ii C Vi is large pure set and Ti A Vi W, then for vertex E V2 n (W (i) we have Nr,(1) (v) 2 (0.9p + Til
C An improved algorithm in the balanced case
Our algorithm is built upon 28 and 25 However, even in the balanced case, our algorithm improves result of (28 on partially recovering clusters in the SBM. More precisely, we can use Theorem 1.2 to prove the following theorem.
Theorem C.I. Let G EV of each cluster is (2m/k)). Then there exists polynomial time algorithm that exactly recovers all C'a log for some constant C².
E) be sampled SBM(n, k. p, q) for o² = Q2 n/n) where size
clusters if (p- 9) / E
In 28 (see Lemma 1.4 therein), Vu gave algorithm that partially recovers all the clusters in the sense that with probability at least 1 - E, each cluster output by the algorithm contains at fraction of any one underlying communities, for any constant holds under the assumption that o² > C' log n/n, and (p /) > Covk. In comparison, we obtain a full recovery of all the clusters under Vu's partial recovery assumptions at the cost of an extra log n factor in the tradeoff of parameters.
0. For the balanced case, his result
Proof of Theorem C.I We have (p VV/kk C'oVklogu Let C' = 2C. Since S 3/4, we have p-p- 2 1/4 and then 2 Vm(lo)) Thus (p ))
(1 logn. This That is the size of each cluster is at least s* Then we can run Algorithm [ to recover one such cluster. Now, since the size of each cluster is same, can run this iteratively k times, recovering a cluster at each round with probability - O(n -2). Using union bound we get that we are able to recover all clusters with probability (m.
implies l: CVr(1-g)logw
(p-g)vm and n/k
p-q
1 - O(kn
D
D Lower bounds
First, we show that our algorithm is optimal up to logarithmic factors when p and q are constant. To do so, we make use of the well-known planted clique conjecture.
Conjecture D.1 (Planted clique hardness). Given Erdös-Rényi random graph G(n, q) with q = 1/2, if we plant in G(n, q) a clique of size where t E [3 log n, of /n)), then there exists no polynomial time algorithm recover the largest clique in this planted model.
Under the planted clique conjecture, we note that there is no polynomial time algorithm for the SBM problem that recovers clusters of size o( /n) irrespective of the number & of clusters present in the graph, for any constants p and q. This can be seen by defining the partition of V as U V, where V1 is clique of size f = olvn), and V/2 Then an algorithm for finding a cluster of size of o(vn) in graph that sampled from the SBM with the above partition solves the planted clique problem.
Vi2 are singleton vertices, k = n t. Finally, let
p 1. q
Thus, the dependency of our algorithm in Theorem 1.2 n is optimal under the planted clique conjecture up to logarithmic factors.
The following result was given in (23), we give proof here for the sake of completeness.
19

---

Theorem D.2 ([23). Let A be polynomial time algorithm in the faulty oracle model with parameters n. k, 6. Suppose that A finds cluster of size t irrespective of the value of k. Then under the planted clique conjecture, it holds that & = n.
Proof. Let G be a graph generated from the planted clique problem with parameter 6. Note that each potential edge in the size-t clique, say K, appears with probability 1, and each of the remaining potential edges appear with probability } Now we delete each edge G with probability 3. Then the resulting graph can be viewed as an instance generated from the faulty oracle model with parameters n, k = n 1 + 1 and 5 = 3: there are l clusters, one being H, and 1 clusters being singleton vertices. Furthermore, each intra-cluster edge is removed with probability & and each inter-cluster is added with probability 1/2 (1 - }) = 3. If there is a polynomial time algorithm that recovers the cluster H, no matter how many queries it performs, then it also solves the planted clique problem with clique size t. Under the planted clique conjecture, = S((n)).
2-
E High-level ideas of the algorithm for the faulty oracle
Discussion about the previous algorithm in the faulty oracle model One crucial limitation of all the previous polynomial-time algorithms that make sublinear number of queries is that they cannor recover large clusters, if there are at least 22(2255) small clusters. The reason is that the query complexities of all these algorithms are at least (A.).). and if there are f1(12/55 small clusters, then k ((n2/5), which further implies that these polynomial time algorithms have to make ((k5)) = ((n²)) queries.
Main ideas of our algorithm Now we apply our algorithm in the SBM to the faulty oracle model. Consider the faulty oracle model with and parameters n, k 6. Assume that the oracle O outputs '+' to indicate the queried two vertices belong to the same cluster, and otherwise.
Observe that if we make queries on all pairs u, E V, then the graph G that is obtained by adding all + edges answered by the oracle O is exactly the graph that is generated from the SBM(n, k, p. i) with parameters n, k p = y 2 and q = 3 S. However, the goal is to recover the clusters by making sublinear number of queries, i.e., without seeing the whole graph.
1 + 5
We now describe our algorithm NOISYCLASSTERING (i.e., Algorithm 55 for clustering with faulty oracle. Let V be the items which contains A latent clusters Vi,..., Vx and O be the faulty oracle. Following the idea of [27), we first sample a subset T' S V of appropriate size and query Olu, v) CLUSTER)) on the graph induced by T to obtain clusters X1..... X2, for some S k. We can show that each of these sets is a subcluster of some large cluster V4. Then we can use majority voting to find all other vertices that belong to X,, for each < That is, for each X; and E V, we check the number of neighbors of u in X; is at least |x,] In this way, we can identify all the large clusters Vi note that we can choose a small subset of X; of size O log for majority voting reduce query complexity. Then we can remove all the vertices in Vi's and remove all the edges incident to them from both V and T and then we can use the remaining subsets T and V and corresponding subgraphs to find the next sets of large clusters. The algorithm COISYCLUSTERING then recursively find all the large clusters until we reach a point where the recovery condition on the current graph no longer holds.
for all pairs u, E T. Then apply our SBM clustering algorithm (i.e. Algorithm [
2
corresponding to X,, 1 S iis S t. Furthermore,
F The algorithm in faulty oracle model
Now we turn to the faulty oracle model and give the corresponding algorithm Algorithm 5 To analyze the algorithm NOISYCL.USTEIING (i.e., Algorithm 5). we first describe results.
Lemma F.I. Let [V|
= n and V; C V [Vi = s 2 Cyrr-log" for some constant C. 1. If 1 logn is sampled randomly, then with probability 1 -8, we have 8"
a set T C V of size
I Vn > CVIT log
Clog 82
20

---

Algorithm 5 NOISYCLUSSTERING(Y 8): recover all clusters of size more than 8 2 8
V" < V=+++0
2: Randomly sample a subset T C size [T]
C log"
2282
3: Query all pairs u, T and let G(T) be graph vertex set T with only positive edges from the query answers
4: for each l from to |n/s| do
5:
Apply CLUSTER(G[TT) 2 + 6, - 6) to obtain a cluster Ti
6: T' 0 then
7:
continue
8:
else
9:
t'
Find an arbitrary subset T7 S Te of size
4
11:
Cj. {u E V T N (v) [T]]/]]
12:
Cr Ce
13:
T T Tr.
V' V Ce
15:
Return C,, CC
Proof. We use Hoeffding bound to obtain these bounds. We have [7] 2 For every vertex u E we define X,, the indicator random variable which is 1 E V4.
16C 1oo""="og"n 2 16 16log" n.
8"x²
Then E[X.] = |Vll/V// Thus applying Hoeffding bound we get
0.5 TIV V
Pr
Σ X. WET
S e e--8og 8lg S n2
Now, substituting value of [T' we get 0.5.
8 8.C log n.s
4C-n-log
C-log
$2.82.n
O C-
CVITTORRIT
Furthermore, the last equation shows
0.5.17/IV/ IV
CV/Tlog [T]
On ing 8-0-0
Clogn 6"
Now the proof follows by noting that |T EnEr X
Lemma F.2. Let V be partitioned into two sets U and W. where each vertex E V is independently
assigned to either set with equal probability. Let S c V.n U be set such that (S] 2 52 Then
Isl for all V. W, and Ns(u) < 1s1 for all with probability 1 O(n (8), we have Ns(u)= 2 VG n W for any j + i.
Proof. Let u E V; W. Then ([Ns(m)) (0.5 5) |S]. Then
Pr(Ns(u) & (0.5+6)-|57) 8|51) (w) - 0.5[Sl) - 28 28 < -25 <e- log
The last inequality holds [S] 2 4log n/82. Thus if VnW then Ns(u) 0.5|S| with probability 1-
Similarly, if & V., then with probability - 8 we have Ns(u) S 0.5]S|.
F.1 Proof of Theorem 1.6
Given s, first we randomly sample n'
O log" 6252
many vertices from V. and denote this set as T.
Then Lemma E2 proves that for any cluster Vi [V| 2 s", we have [T] = [TVV > CV7 loga'
with probability n For any underlying cluster V,, we denote T, = T V,
Next query all the pair of edges for vertices in T. which amounts O resultant graph G' is an SBM graph on n' vertices with p 0.5 + 8 and g 0, 5 8.
12 log 8*54
queries. The
21

---

Thus, if we run Algorithm | with parameters G', 6, 6, then Theorem 1.2 implies that we recover cluster T; such that [T:] Cn' log n' with probability n
Once we get such set Tú we can take 4 logn/88 many vertices from it, calling it set S. Then for every vertex v E V \ T. we obtain (u),), which requires [S] many queries, and select all vertices such that (u) S| Lemma F.I shows that recover V n (V (T') with probability 1 n together recovering V, Thus this step requires 4n log n/8² queries for each iteration.
Once we have recovered V,, we can then remove T; from T and run [ again the residual graph, followed by the sample-and recovery step of Line [T]] Note that once we remove recovered cluster, all sets 7 that satisfied the recovery requirement of Theorem 1.2 in the graph G' defined on T. also satisfies it on the graph G" defined on T; and we do not need to sample any more edges.
/T log [T/82. Here have VT log This upper bounds the number of iterations and thus the number of times the voting system Line 10 is applied.
Finally, there are most VT many clusters T; E T' such that [T] 2
Thus the query complexity O finishes the proof of Theorem 1.6
log 6
log n
log 12 8
= O
n log n
n2 log
This
8.0"
22


Reviews:
[{"review_id": "sSNfSpEuG2", "reviewer": "Reviewer_Ajy4", "summary": "The paper deals with the problem of community detection for unbalanced community sizes. Specifically, the paper concentrates on the situation where both large (O(\\sqrt{n})) and small communities exist in the network. The paper proposes a stepwise method of recovering the large clusters in the presence of small clusters for planted clique SBM and faulty oracle models.", "questions": "(1) Does the proposed algorithm assume the knowledge of p and q?\n\n(2) Does the proposed algorithm assume the knowledge of the number of communities, or is there a stopping criteria of the proposed algorithm for recovery of the number of large communities?", "limitations": "N/A", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The main strengths of the paper are as follows - \n\n(1) The paper addresses a gap in the literature on the simultaneous recovery of large and small communities in networks.\n\n(2) The paper deals with the problem of community recovery of large communities in the presence of small communities. The paper provides a stepwise method of recovering large communities in planted clique SBM and faulty oracle models.\n\n(3) The paper provides theoretical results supporting the recovery of large communities by overcoming the \"small cluster barrier\" of the size of the remaining small clusters.\n\n(4) The paper is well-written.", "weaknesses": "The main weaknesses of the paper are as follows - \n\n(1) The paper misses some relevant literature. Such as - Li, Tianxi, et.al. \"Hierarchical community detection by recursive partitioning.\" Journal of the American Statistical Association 117, no. 538 (2022): 951-968. It describes an algorithm that is very similar to the algorithm proposed in this work.\n\n(2) Algorithms 2 and 3 assumes the knowledge of p and q, which are very strong assumptions. It is not immediately clear how the algorithm can be extended for general SBM.\n\n(3) The stopping criterion of the proposed algorithm is not clear. \n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank you for your detailed review. Please find our comments on the weakness and the answers to your question below. \n\n\n### Knowledge of $p,q,k$:\nOur algorithm necessitates knowledge of the parameters $p$ and $q$ but not the number $k$ of communities. However, it is worth noting that even the previously state-of-the-art algorithms by Ailon, Chen, and Xu (ICML 2013 and JMLR 2015) **also** rely on knowing $p, q$, as well as $k$ (or in some special cases, an upper bound on $k$). This observation highlights the inherent difficulty of theoretically addressing the ``small cluster barrier.'' An open question arises: Can our algorithm be made parameter-free? Exploring this possibility remains an interesting direction for future research.\n\n\n### Stopping Criterion of the algorithm:\n\n1) The *EstimatingSize* subroutine (Algorithm 3) calculates $\\bar{s}$, which is approximately \n$\n\\max ( 100\\sqrt{p(1-q)}\\sqrt{n} \\log n/(p-q), 0.5\\cdot s_{\\max} ).\n$\n\nWithin the *RecursiveCluster* algorithm, in each iteration, we can check if the $\\bar{s}$ value is sufficiently large and use that as the stopping criterion to determine if the algorithm should halt its iterative process.\n\n\n2) To address the confusion of the unclear stopping criteria, we will add an explanatory line following line 2 in Algorithm 1, stating that if *EstimatingSize* does not return a valid $\\bar{s}$ (i.e. when Exit(0) occurs in Algorithm 3), then Algorithm 1 will simply return an empty set.\n\n\n### Relevant literature:\nWe appreciate the reference to the paper (where the analysis is on the binary tree SBM model) you mentioned, and upon careful examination, we have noticed some fundamental differences between the referred algorithm and ours, despite being related. (We will also add the comparison to this relevant literature in the future version.)\n\ni) The algorithm in the mentioned paper utilizes the well-known eigenvector+K-Means approach, whereas our approach involves a distinct SVD+ ``plural-set-purification'' strategy.\n\nii) Notably, the binary tree SBM problem comprises small clusters as \"sub-clusters\" within larger clusters, whereas in the SBM model (as studied in our paper), very small clusters can be considered as potential noise as the cluster sizes can be arbitrarily unbalanced.\n\niii) Furthermore, it appears that their algorithm requires knowledge of the number of sub-clusters at each level (they can estimate whether there are any more levels), which is inherently different from the problem we are addressing, and we do not require the knowledge of cluster sizes and number of clusters.\n\n\n### Extension to general SBM:\nTo extend our findings to the general SBM, we propose adapting our algorithm by setting $p$ to represent the minimum intra-cluster probability and $q$ to denote the maximum inter-cluster probability. In a future extended version, we plan to explore this in depth. To achieve this, we will devise a more refined and nuanced method for estimating the largest cluster size. Then by leveraging the aforementioned approach, we aim to identify the largest cluster within general SBM efficiently.\n\n"}, {"review_id": "GUE0Kc4uZg", "reviewer": "Reviewer_tK15", "summary": "The authors consider the problem of perfect recovery in a stochastic block model where the average degree is large and where the groups are not balanced. They provide an algorithm based on singular value decomposition to recover recursively the largest clusters. They provide a few numerical experiments illustrating their claims. The authors apply their results to the problem of clustering with a faulty oracle.", "questions": "Maybe the authors could precise the complexity of the algorithm 1. In experiment 6 it seems the authors are able to run this algorithm for n substantially larger than the other experiments. The authors could go to higher n and test how tight are their bounds; in particular taking p and q smaller.\n\nA small section to conclude the article and for future work would be appreciable.\n\nSome references are ill-formatted. Eg ref. 27 \"svd\" –> \"SVD\".\nInconsistency: plural set vs plural-set.", "limitations": "The same.", "rating": 5, "confidence": 1, "soundness": 3, "presentation": 4, "contribution": 2, "strengths": "I have little knowledge as to this problem of perfect recovery in a dense SBM and I am not able to assess the correctness of the claims and their relevance.\n", "weaknesses": "The same.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank you for your efforts! We will definitely add a concluding section highlighting some future works that we think will be of interest. "}, {"review_id": "nsrXTfkzzY", "reviewer": "Reviewer_MiyQ", "summary": "This work studies stochastic block models where blocks/clusters can have different sizes. It proposed a simple SVD algorithm which recovers communities in this setting. The main technical improvement of this work is that the assumption is removed which requires there to be a ‘size interval’ where no clusters appear. \nA secondary result is a efficient clustering algorithm with sublinear query complexity. \n", "questions": "-\tHow does the algorithm compare with respect to the previous work in terms of running time?\n- In practice the Spectral Clustering algorithm performs well in practice on graphs with clusters of unbalanced size. Even though not many bounds are known of spectral clustering with respect to SBMs, did you try to compare your algorithm experimentally with Spectral Clustering?", "limitations": "none", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "-\tThis work is a clear improvement over the previous state-of-the-art. As I understand it, a key technical contribution of this work that might influence future work is instead of finding $k$ clusters as is done using the SVD approach, the algorithm first aims to find large clusters one-by-one. Although these are not perfect (they form a so-called plural set), using some non-trivial techniques perfect recovery can be obtained. \n- Experiments on synthetic data indicate that the algorithm not only works well in theory but also in practice.\n- The write-up of this work is excellent.", "weaknesses": "-\tGiven that the aim of the studied setting is to look at more realistic settings, I would have expected to find experimental results on real-world datasets as well. Although this work does provide better bounds for SBMs generated with differently sized clusters, SBMs still have a highly symmetric structure compared to real-world graphs. It would be interesting to see the performance of the proposed algorithm on some real-world graphs. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks a lot for your thorough and detailed review! Please find the answers to your questions below.\n\n### Run time comparison:\nRegarding the asymptotic running time of Algorithm 1, a major contributing factor is the computation of the $(p-q)\\sqrt{n}/\\sqrt{p(1-q)}$ dimensional SVD projection, which can be significantly more efficient than the previous state-of-the-art algorithm by Ailon, Chen, and Xu (JLMR 2015). The latter involves solving a convex programming problem with $n^2$ constraints, rendering it computationally prohibitive. \n\nFor instance, in experiment 3A of the JLMR 2015 paper, the authors mentioned that for an instance with $n=3500$ and $k=4$, they required $182$ seconds to recover the clusters. In contrast, our method finishes in approximately $2.5$ seconds. Thus, this is another empirical improvement over the state-of-the-art algorithms!\n\n\n### Spectral Clustering:\nSpectral clustering is indeed a powerful tool. However, in this specific problem, some instances may be hard. For example, we ran a version of spectral clustering for the parameters of  Experiment 5 of Table 2 of our paper, both with $K=2$ (which is the number of large clusters) as well as $K=1000$ (which is the number of total clusters). The algorithm failed to recover a ground truth cluster in either case.\n\n\n\n"}, {"review_id": "UeRoWPxBX7", "reviewer": "Reviewer_5GRr", "summary": "This paper studies a classic problem of recovering clusters in a random graph. Concretely, the authors consider the stochastic block model. Here there is an underlying graph on n nodes. The n nodes are partitioned into k unknown clusters. There is then an edge independently between any two nodes in the same cluster with probability p and between any two in different clusters with probability q < p.\n\nThis is an extensively studied problem and many algorithms have been designed that allow the recovery of all clusters of a reasonable size (somewhat larger than sqrt(n), which is anyway a requirement for computational efficiency under the planted clique conjecture). The previous state of the art allows recovering clusters under two assumptions (here simplified for clarity and brevity):\n\n1. The clusters to recover have size at least max(sqrt(n), k)/(p-q).\n2. There is a number alpha of about sqrt(n)/(p-q) such that no cluster has size in the interval [alpha/C, alpha] for a constant C.\n\nThe assumption that the cluster sizes are at least sqrt(n) for those to be recovered is natural as mentioned above. However, the dependency on k is unfortunate when there are many small clusters. These would prevent the recovery of medium sizes clusters when k >> sqrt(n). Secondly, the assumption about the empty interval is quite unnatural.\n\nThe main contribution of this work is to remove the dependency on k in 1. and to remove the assumption 2. all together.\n\nThe authors also present applications of their algorithm in the related problem of clustering with a faulty oracle. Here one can ask whether two nodes v, w are in the same cluster or not. One is then returned a noise answer. Here the paper also improves over the state of the art in terms of the cardinality of clusters that can be recovered.", "questions": "-Could you say a bit about the running time of your algorithm in practice compared to previous work?\n-Can you comment on whether the 2^13 constant can be reduced to a more reasonable constant without too much effort?", "limitations": "Yes", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "-The problem studied is fundamental in graph clustering.\n-Removing the dependency on k and the requirement of an empty interval of cluster sizes is significant and the algorithm guarantees of the algorithm much more natural than previously\n-The authors have implemented their algorithm and compared experimentally to previous work. The comparison is overall in favour of the new algorithm.", "weaknesses": "-I know this is a theoretical contribution, and also the authors probably did not attempt to optimize constants that much, but a factor 2^13 in the guarantees is quite severe in practice. Hopefully and probably, this constant is smaller in practice.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks a lot for your thorough and detailed review! Please find the answers to the questions below.\n\n\n\n### Run time comparison:\nFrom our experiments, we find our algorithm to be much faster compared to the state-of-the-art algorithms of Ailon, Chen, and Xu (JLMR 2015).\n\nFor example, in experiment 3A of the JLMR 2015 paper, they mention that when dealing with an instance with $n=3500, k=4$, they need $182$ seconds to recover the clusters. In comparison, our method requires around $2.5$ seconds. Thus, this is another empirical improvement over the state-of-the-art algorithms!\n\n\n### Value of constants:\nWe acknowledge that $2^{13}$ might seem like a large constant, and we agree that it is an artifact of our current proof. However, based on extensive experimentation, we estimate that this value could be significantly reduced to around $10-20$, which we consider a considerable improvement. Moreover, we firmly believe that the constant $2^{13}$ can be further optimized in various aspects of our analysis through more meticulous calculations. Specifically, a tighter analysis of the ``low probability Chernoff bound'' that we employ could lead to more refined and improved results. \n"}]

Author rebuttal:

Meta-review: The paper studies the exact recovery problem in the SBM when the input community are unbalanced. This setting introduces some interesting technical challenges and it received a bit less attention in the literature(despite being probably the most realistic scenario).

In this setting the paper is a nice improvement on the state-of-the-art. Furthermore, in contrast with previous work the authors do not need to know the number of clusters as an input parameters.

Overall, the paper will be a nice addition to the conference program.

The reviewers have some interesting suggestions that the authors should address in the final version. For example:
- adding experiments on real world data
- adding runtime experimental benchmark
- mention and explain idea of how the 2^13 factor could be improved
Decision: Accept (poster)