Revisiting Instance-Optimal Cluster Recovery in the Labeled Stochastic Block Model
Authors: Kaito Ariu
Alexandre Proutiere
Se-Young Yun
Venue: ICML 2025 poster (2025)
Keywords: Stochastic Block Model
Clustering
Community Detection
Primary area: general_machine_learning->clustering
TL;DR: We establish the necessary and sufficient conditions for clustering in the LSBM by introducing IAC, the first algorithm to achieve the sufficient condition.

Abstract: In this paper, we investigate the problem of recovering hidden communities in the Labeled Stochastic Block Model (LSBM) with a finite number of clusters whose sizes grow linearly with the total number of nodes. We derive the necessary and sufficient conditions under which the expected number of misclassified nodes is less than $ s $, for any number $ s = o(n) $. To achieve this, we propose IAC (Instance-Adaptive Clustering), the first algorithm whose performance matches the instance-specific lower bounds both in expectation and with high probability.
IAC is a novel two-phase algorithm that consists of a one-shot spectral clustering step followed by iterative likelihood-based cluster assignment improvements. This approach is based on the instance-specific lower bound and notably does not require any knowledge of the model parameters, including the number of clusters. By performing the spectral clustering only once, IAC maintains an overall computational complexity of $ \mathcal{O}(n\, \text{polylog}(n)) $, making it scalable and practical for large-scale problems.

Revisiting Instance-Optimal Cluster Recovery in the Labeled Stochastic Block Model
Kaito Ariu Alexandre Proutiere
2 Se- Ye-Yo Yun
Abstract
for detailed overview, see (Abbe, 2018). However, it of- fers somewhat simplistic representation of how nodes interact. In real-world applications, interactions can vary in type-such as ratings in recommender systems or proximity levels in social networks. To capture this richer, more nu- anced interaction data, the Labeled Stochastic Block Model (LSBM) was introduced and analyzed (Heimlicher et al., 2012; Lelarge et al., 2013; Yun & Proutiere, 2016). LSBM represents interactions through labels drawn from arbi- trary set. The aim of this paper is to illustrate the tightest condition under which clustering is possible based on ob- serving these labels. For that purpose, we develop a clus- tering algorithm that minimizes the expected number of misclassified nodes. In the following sections, we formally introduce LSBMs and summarize our results.
In this paper, we investigate the problem of recov- ering hidden communities in the Labeled Stochas- tic Block Model (LSBM) with finite number of clusters whose sizes grow linearly with the total number nodes. We derive the necessary and suf- ficient conditions under which the expected num- ber of misclassified nodes is less than s, for any number onn). To achieve this, propose IAC Austance-Adaptii Clustering), the first al- gorithm whose performance matches the instance- specific lower bounds both in expectation and with high probability. IAC is a novel two-phase algorithm that consists of one-shot spectral clus- tering step followed by iterative likelihood- -asee cluster assignment improvements. This approach is based the instance-specific lower bound and notably does not require any knowledge of the model parameters, including the number of clus- ters. By performing the spectral clustering only once, IAC maintains an overall computational complexity of O(n polylog(n)) (n)), making it scal- able and practical for large-scale problems.
The Labeled Stochastic Block Model. In the LSBM, the set I consisting of items or nodes is randomly partitioned into K unknown disjoint clusters ,,, Ik. The cluster index of the node is denoted by (i). Let a = (01, .2,.... .,. (kk) represent the probabilities of nodes belonging to each cluster, i.c., for all k e [K] and i e I. P(i Ix) ag- We assume that a1.-... OgK strictly positive constants and that K and large. The number of clusters K is initially unknown. With- out loss of generality, we also assume that a1 .... S ag. Let = {0, 1.......,, L} be the finite set of labels. For each edge (v,w) E I, x Iy. the learner observes the label with probability p(i, E). independently of the labels observed in other edges. We have Vi,j [K] EtEc p(i, j, 1. Without loss of generality, O is the most frequent la- bel: 0 = arg max, Σ Σx sx Let max (t..j. be the maximum probability of observ- ing a label different from O. We will mostly consider the challenging sparse regime where P = O(log n)/n) and pn - 0o as n -> oo, but we will precise the assumptions made on and p for each of our results. We further assume for all i, [K]:
fixed as grows
1. Introduction
Community detection or clustering refers to the task of gathering similar nodes into a few groups from the data that, most often, correspond to observations of pair-wise interactions between nodes (Newman & Girvan, 2004). A benchmark commonly used to assess the performance of clustering algorithms is the celebrated Stochastic Block Model (SBM) (Holland et al., 1983), where pair-wise inter- actions are represented by a random graph. In this graph, the vertices correspond to nodes, and the presence of an edge between two nodes indicates their interaction.
The SBM has been widely studied over the past decades;
(AI) WA E C, (.
'CyberAgent FKTH Digital Futures 2 *KAIST. Correspondence to: Kaito Ariu <kaito_ ariu @ eyybrageen.cco.pp>
In and pli, k)
(A2) -p 2
Proceedings of the 42nd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).
where 7) and e are positive constants independent of n. (A1)

---

Revisiting Instance-Optimal Cluster Recovery in the Labeled Stochastic Block Model
imposes some homogeneity on the edge existence prob- ability, and (A2) implies certain separation among the clusters. In summary, the LSBM is parametrized by and p = (p(i. (il,i,)))ssse (ssssssssss
the worst possible LSBM, but could potentially yield poor performance for most other instances of the LSBM.
Instance-specific lower bound. To reveal the necessary condition, we first need to revisit an instance-specific lower bound on the error rate satisfied by any algorithm. The following theorem from (Yun & Proutiere, 2016) provides a necessary condition as lower bound on the expected number of misclassified nodes E[s (n)]--
1.1. Notation
We denote p(i) as the K x (L + 1) matrix whose ele- ment on j-th row and (E + 1)thh column is j,i, E) and denote p(i,j) E [0, 1) the vector describing the prob- ability of the label of a pair of nodes in I, and Iz. Let pXx(L+11 denote the set of all K x (L + 1) matrices such that each row represents a probability distribution. Define the divergence D(a, p) of the parameter (a.p) as: p(a,p) = jek]it] DL+ (a, p(i), p(j)), with
Theorem 1.1 (Yun & Proutiere (2016)). Let
((n). Under the assumptions of (AI), (A2), and pn = w(1), for any clustering algorithm æ that satisfies lim supn-soc [() 11.
lim inf DD log (n/8) 2 1.
(r.(a,((0),P())
min max VEPRX(++))
K Or p(((k)),(iiA)))
K
The lower bound essentially states that under any algorithm, the expected number of misclassified nodes must be larger than n exp(-nD(ax, p)). The proof of Theorem 1.1 is based on the change-of-measure argument frequently used in on- line stochastic optimization and multi-armed bandit prob- lems (Kaufmann al., 2016; Lai & Robbins, 1985).
Σ on kl(v(())
and where kl denotes the Kullback-Leibler divergence between two label distributions, i.e., p((,())) 2(k.0)
vkk f) log p(i.k.f)' Dr. (())) can be inter- preted as the hardness in distinguishing whether a node be- longs to cluster i or cluster j based on the data. For any clus- tering algorithm т, we denote by (T)) the number of mis- classified nodes under æ. This quantity is defined up to a per- mutation of the cluster IDs. Specifically, if æ returns (Ix)&, then exd (n) is calculated as mine | UA L. \ Tocayl. where the minimum is over all permutations 0 of [K]] To simplify the notation throughout the paper, we assume that the permu-
An instance-optimal algorithm (upper bound). The main contribution of this paper is to provide sufficient condition for cluster recovery. Specifically, we propose an algorithm with performance guarantees that match those of the above lower bound and with computational complexity scaling as rıpolylog(1). This algorithm, referred to as Instance- Adaptive Clustering (IAC) and presented in Section 3, first applies spectral clustering algorithm to initially guess the clusters and then runs likelihood-basae local improve- ment algorithm to refine the estimated clusters. To analyze the performance of the algorithm, we make the following assumption.
tation achieving the minimum is given by 0(k) l for all
k E [K].
1.2. Main Results
We consider the problem of clustering, or recovering com- munities, in the LSBM as described above. We reveal the necessary and sufficient conditions for the asymptotic re-
np(j,i, 2 (np) for all i and E 1, (A3) for some constant O.
covery of the communities. Specifically, we reveal that the
Assumption (A3) excludes the existence of labels that are too sparse compared to p. The following theorem establishes the performance guarantee of IAC. Its full proof is given in Appendix C.
necessary and sufficient condition on the parameters (a. p) to achieve lim sups
(l)(())) < 1, for any s = o(n). is
(D p)
inf n0 log(n/s) 2 1.
Theorem 1.2. Assume that (Al), (A2), and (A3) hold, and that P O(log n/n),, pn w(1.. Let o(n). If the parameters (o.,p) of the LSBM satisfy
To this aim, we design a computationally efficient algorithm that recovers the clusters in the LSBM with a minimal error rate. By minimal, we mean that for any given LSBM, the al- gorithm achieves the best possible error rate for this specific LSBM. In other words, the algorithm is instance-optimal and truly adapts to the hardness of the LSBM it faces. This contrasts with algorithms with minimax performance guar- antees only: those algorithms provably perform well for
nD p) 2 1.
lim inf 700000
(1)
log(n/s)
then IAC (Algorithm 1) misclassifies at most s nodes in high probability and in expectation, i.e.,
B(ClAC(()) (n)
lim Plc PICIAC (n) I s] = 1 and lim sup n-000
<
n-000
2

---

Revisiting Instance-Optimal Cluster Recovery in the Labeled Stochastic Block Model
IAC requires O(n(logn) )) floatiing-point operations.
(1/n), there is a positive fraction of isolated nodes, and we cannot do much better than merely detecting the clus- ters. In this paper, we focus on scenarios where the edge probabilities are w(1/n), where an asymptotically accurate recovery of the clusters may be achieved.
As far as we are aware, IAC is the first algorithm achieving a performance that matches the lower bound presented in Theorem 1.1.
To obtain an mestance-optimna guarantee in expectation, we had (i) reshape parts of the algorithm, and (ii) develop new tools to analyze its performance. Specifically, to assess the expected number of misclassified nodes after the first spectral clustering phase, we needed tighter guarantee for the probability of a failure event of the spectral clustering algorithm with the iterative power method and singular value thresholding. Analyzing the second phase (the likelihood- based improvement step) of the algorithm in expectation was also challenging. All intermediate statements had to hold with sufficiently high probability and quantify the number of misclassified nodes for any number s = o(n.). Furthermore, as reflected in the definition of the divergence D(a,)), p). the optimal clustering boundary is asymmetric, necessitating that both the improvement step and its analysis account for the nonlinear information geometry.
A Asymptotically accurate recovery. Our results can also be interpreted a generalization of the necessary and suffi- cient condition for asymptotically accurate recovery of the communities in the labeled stochastic block model (LSBM), namely n pa,
wI1). Under this condition, we can achieve asymptotically accurate recovery of the clusters, meaning that the proportion of misclassified nodes tends to zero as n grows large. A necessary and sufficient condition for asymptotically accurate recovery in the SBM (with any number of clusters of different but linearly increasing sizes) has been derived in (Yun & Proutiere, 2014b) and (Mossel et al., 2015b). In our work, we performed a more precise analysis and succeeded in generalizing this condition. Our results are characterized by our divergence D(a,p) p). which makes the condition instance-specipn Our analysis thus pro- vides more accurate results than those derived in a minimax framework (Gao et al., 2017; Xu et al., 2020; Fei & Chen, 2020; Zhang & Zhou, 2020). An extensive comparison with (Gao et al., 2017), where we also strengthen their analysis, is provided in Section 2.2.
2. Related Work
In this section, we review existing literature on community detection in stochastic block models (SBMs) and their ex- tensions, focusing on performance guarantees and optimal recovery rates relevant to our analysis.
Asymptotically exact recovery. An algorithm achieves an asymptotically exact recovery if no nodes are misclassified asymptotically. By choosing
1/2 in our theorems, our results provide the necessary and sufficient condition for such exact recovery. Conditions for asymptotically exact recovery have also been studied in the binary symmetric SBM (Yun & Proutiere, 2014a; Abbe et al., 2016; Mossel et al., 2015b; Hajek et al., 2016). For instance, when K = 2, 01 = 02 1, = p(2, 2, 1) = a log and p(1, 1) = p(2, 1) blog where a and b are some constants with >>> b. cluster recovery is possible if and only if 2
2.1. Community Detection in the SBM
Community detection in the stochastic block model (SBM) and its extensions has received considerable attention over the last decade. We first briefly outline existing results be- low, and then focus on few papers that are most relevant to our analysis. The results for the SBM can be categorized according to the type of performance guarantee targeted. We distinguish three types of guarantees: detectability, asymp- totically accurate recovery, and exact recovery. Most results are concerned with the standard SBM, which can be ob- tained as a special case of the LSBM (with I, 1, where the intra- and inter-cluster probabilities are denoted by p(i,ú, 1)
v ab 2 1. There are also extensions to more general SBMs (Abbe & Sandon, 2015a;b; Wang et al., 2021). Our results are in a form that generalizes these results.
2.2. Comparison with Previous Work on Optimal Recovery Rates
and p(i,j, 1) for i + j E [K).
Detectability. Detectability refers to the requirement of returning clusters that are positively correlated with the true clusters. It is typically studied in the sparse binary SBM where K= 2, 01 a2 p(1, 1, 1) = p(2, = a/n and p(L, 2, 1) = p(2, 1) = b/T, for some constants a > b independent of n. For such SBM, detectability can be achieved if and only if (a- ((-b) b) > 22(a- + b) (Decelle et al., 2011; Mossel et al., 2015a; Massoulié, 2013). Detectability conditions in more general sparse SBMs have been inves-
Next, we discuss three papers (Zhang & Zhou, 2016; Gao et al., 2017: Xu et al., 2020) that are directly related to our analysis. These papers study the standard SBM homoge- neous LSBM in the regime where asymptotically accurate recovery is possible. (Zhang & Zhou, 2016; Gao et al., 2017) present the minimal expected number of misclassified nodes, but in a minimax setting, whereas (Xu et al., 2020) presents the instance-specific analysis.
tigated in (Krzakala et al., 2013; Bordenave et al., 2015). In the sparse SBM, when the edge probabilities scale as
The authors of (Zhang & Zhou, 2016) characterize the min-
3

---

Revisiting Instance-Optimal Cluster Recovery in the Labeled Stochastic Block Model
imal expected number of misclassified nodes in the worst possible SBM within the class (n,, a, b) of SBMs satisfy- ing, using our notation, p(i, i, 1) 2 & and jii, 1) s & for all i * E [K], where a and b are positive constants. To simplify the exposition here, we assume that all clusters are of equal size (refer to (Zhang & Zhou, 2016) for more details). The minimal expected number of misclassified nodes is defined through the Rényi divergence of order 1 between the Bernoulli random variables of respective means and & given by
The proof is presented in Appendix E.10. The assumptions of Corollary 2.1 are satisfied when our assumptions (A1) and (A2) hold.
The algorithm presented in (Gao et al., 2017), which has established performance guarantees, comes with a high com- putational cost. It requires applying spectral clustering n times, where for each node u, the algorithm builds a modi- fied adjacency matrix by removing the w-th column and the u-th row and then computes a spectral clustering of this trix. In contrast, our algorithm performs spectral clustering only once. (Gao et al., 2017) also proposed an algorithm with reduced complexity (running in I((2)) )) but without performance guarantees. Our algorithm not only performs spectral clustering once but also requires just On((log n)) operations. Additionally, our algorithm empirically exhibits better classification accuracy than the penalized local maxi- mum likelihood estimation algorithm from (Gao et al., 2017) in several simple scenarios (see Appendix F).
1" (",, = -2log
a V V
a
1
b
n
When nI" (n, a, b) = (1). Ele" (n)) scales as n exp(-(1+ (1+
(1)) nl al"(n..b)) (Zhang & Zhou, 2016) established that the so-called penalized Maximum Likelihood Estimator (MLE)
achieves this minimax optimal recovery rate but does not provide any algorithm to compute it.
To conclude, compared to (Gao et al., 2017), our analysis provides an instance-specifie lower bound for the classifica- tion error probability (rather than minimax) and introduces low-complexity algorithm that matches this lower bound, Additionally, our analysis is applicable to the generic La- beled SBMs. It is worth noting, however, that (Gao et al., 2017) derives upper bounds for classification error proba- bility under slightly more general assumptions than ours for the SBMs. Specifically, their high probability guarantee also holds for dense regimes (p- wlog n/n)), and their number of clusters K can depend on n. whereas we consider fixed K.
The authors of (Gao et al., 2017) present an algorithm that runs in polynomial time and achieves this minimax lower bound with high probability'. Again, for simplicity, we assume that all clusters are of equal size and that K is a fixed constant. Their performance guarantee can be stated as follows (see Theorem in (Gao et al., 2017)):
sup (o.p)=0(n.a.b)
P P(a.p)
2 nexp (-(L+ nI (I (abbii
)) 0, K
E" (2nn)
(Xu et al., 2020) presents an instance-specific analysis for the homogeneous LSBM, in which the distribution of an edge depends solely on whether the corresponding nodes are in the same cluster or not, Specifically, there exist distri- butions P and Q such that for each edge label f, the proba- bilities are defined as p(i, i, E) = P(t) for all i [K]] and p(..j, E) = Q()) for all + j. In contrast, not impose such restrictions; the edge label probabilities can vary heterogencously depending on the cluster indices. Similar to the algorithm in (Gao et al., 2017), the algorithm proposed in (Xu et al., 2020) executes spectral clustering n times (see lines 8-10 in Algorithm 3 of (Xu et al., 2020)).
where P(a.p) denotes the distribution of the observations generated under the SBM (a,p). One could argue that the above guarantee does not match the minimax lower bound valid for the expected number of misclassified nodes. However, by carefully inspecting the proof of Theorem 4 in (Gao et al., 2017), it is easy to see that the guarantee also holds in expectation:
model does
Corollary 2.1. Assume that a/b = O(1), (a - 6)2//a (1), and a = (log(n)). Let Ann be the observation for the pair of nodes (u, v). Under Algorithum I in (Gao et al., 2017) initialized with USC(T) in (Gao et al., 2017) for T =C_ Enein) Ene())>ne(n)) Evein) Ann with some large enough
2.3. Other Related Work
constant C' > 0,
Spectral methods. Recent studies also suggest that there are clustering instances where the spectral clustering al- gorithm alone is optimal without the improvement step. (Zhang, 2024) provides detailed analysis of the spectral method without any improvement steps in the setting of simple SBMs for asymptotically accurate recovery. Their work establishes lower bounds on the performance achiev- able by spectral clustering algorithms. However, these lower
sup (k.,) ([a))
S <exp ((11+ ((1)
nI (n,a,b)
K
RRfer to (Gao et al., 2017) for the class of SBMs consid- ered. Compared to our assumptions (A1)-(22)((33) specialized to SBMs, this class of SBMs slightly more general.
4

---

Revisiting Instance-Optimal Cluster Recovery in the Labeled Stochastic Block Model
bounds are specific the spectral method and thus do not represent the fundamental limits of community detection that we have been considering. As a result, the focus of their work is not on developing algorithms that achieve optimal rates but rather on providing a tight analysis of the spectral method's performance. We also conjecture that in the gen- eral (L)SBM, spectral clustering alone cannot achieve the optimal rates due to the asymmetry of the optimal decision boundary, as reflected in the definition of the divergence p),, This necessitates the use of non-Euclidean dis- tances within the algorithm. In (Zhang, 2024), the k-means algorithm is based on the Euclidean distance (see Eq. (2) of Algorithm in (Zhang, 2024)), which would be insufficient to achieve our optimal result.
Algorithm Instance-Adaptixy Clustering
Input:
Observed adjacency matrices (A")eEz)
(where A = 1 if E is observed between u and v)
1: 1. Estimate average degree:
2: 5 < E
Sew)/n(nn
3: Trimming:
Compute (Aff))e(1)) where I is the set of remain- ing nodes after removing the nodes with the top [eepp-nnp) largest values of Σ Emez Af 5: For all E E [L] and w, V I:
A if wf
6:
(Aft) 0, u
3. Spectral Clustering:
8: Run Algorithm 2 with input (Af))e(L) f and output
For the exact recovery regime, (Dhara et al., 2024; Gaudio & Liu, 2024) discuss the optimality of the spectral algorithm for the Censored SBM (which is an instance of LSBM) or LSBM. They only provided iigh-rrobability guarantees and the algorithms require weights that depend on the statistical parameters.
R { k=1
9: 4. Estimation of the Statistical Parameters:
10: for each j E [K] and l E (0. 1.......,], L} do
11: p(i.j, + ( Eves, A
12: end for
13: 5. Likelihood-basee local improvements:
Related models. LSBM generalizes the SBM, the Censored SBM (Abbe et al., 2014; Dhara et al., 2024), and signed networks (Traag & Bruggeman, 2009: Leskovec et al., 2010; Tzeng et al., 2020), and has many applications. Our results provide necessary and sufficient conditions for cluster recov- ery in all of these models for any 8 = o(n). The Multiplex Stochastic Block Model (Barbillon et al., 2016) and the node-attributed Stochastic Block Model (Dreveton et al., 2023) are interesting because they can capture cluster struc- tures that cannot be represented by the SBM or the LSBM. Extending our work to such models is an important future direction.
14: ((0) <- S₁ for all h: E [K]
15: for t to log n do
16: for each k E [K] do
17:
s + 0 18: end for
19: for each v E I do
20:
h- + arg max Σ
Σ
Σ A
ISkSR VE[R] wES F=0
pg, i)} (tie broken uniformly at random)
5 + ((t) u utu
21:
22: end for
23: end for
24: In + S(log for all & [R] Output: Clusters (Ix) R
3. Instance-Adaptive Clustering Algorithm
In this section, we introduce the Instance-Adaptive Clus- tering (IAC) algorithm, outlined in Algorithm The IAC algorithm is two-step algorithm consisting of initial spec- tral clustering and iterative likelihood-base improvements. The algorithm aims to improve clustering performance by adapting to the instances.
iff label É is observed on edge (u, r)). After the trimming process, which eliminates rows and columns corresponding to nodes with an excessive number of observed labels (as these could distort the spectral properties of A²) as Af., we apply spectral clustering to (Af)ee()) Specifically, we con- catenate the matrices ( (Af-)ee(t) as Á = [A,, A2....,, AF] and use the iterative power method (instead of using a direct SVD) combined with singular value thresholding (Chatter- jee, 2015). This approach allows us to control the com- putational complexity of the algorithm and to accurately estimate the number of clusters.
3.1. Algorithms
The Destance-Adaptvee Clustering (IAC), whose pseudo- code is presented in Algorithm 1, consists of two phases: a spectral clustering initialization phase and a likelihood- based improvement phase.
Spectral clustering initialization. The algorithm relies simple spectral techniques to obtain rough estimates of the clusters. For details, refer to lines 1-4 in Algorithm 1 and Algorithm 2. The algorithm first constructs an observation matrix A (Aam)a, for each label e (where Af,- = 1
Notable differences compared to the spectral clustering phase of the algorithm presented in (Yun & Proutiere, 2016) include (i) a change in the number of matrix multiplications required in the iterative power method, which is now ap-
5

---

Revisiting Instance-Optimal Cluster Recovery in the Labeled Stochastic Block Model
proximately (logn) n):: (ii) an expansion of the set of centroid candidates in the k-means algorithm, which now includes [logn)² randomly selected nodes; and (iii) the use of the concatenated matrix A = [A]. .f......4f4 In contrast, (Yun & Proutiere, 2016 uses a randomly weighted matrix Σeely W with i.i.d. uniform distribution wy for clus- tering, which prevents us from obtaining the guarantee in expectation. Our new approach allows for tighter control of the probability of failure events and provides guarantees in expectation.
M and E Vj. Let M [M² M ,..., M and Mr [M] MB.................... MH] [0,1] be the corresponding trimmed matrix, where (Mf)) M fw,
Algorithm 2 Spectral Clustering
Input: (Af) $
1: 1. Concatenation:
2: A <
AF] 3: 2. Iterative Power Method with Singular Value
Thresholding: X +tn, n, k
<- O, Ú t g
Likelihood-basee improvements. Using the initial cluster estimates S,, we can also estimate p from the data. For any i, j, we calculate the empirical estimate:
4: while x 2 Vnplog(np) do + k+1
() Eves, EveS; Aue
6:
Up + random Gaussian vector of size nL x 1
7: (Iterative power method) U, + (A) n) 1 Uo
|S,1
8: (Orthonormaliiing) Uk s
Based on p. the log- liglliklihood of node e belonging to cluster Sy is computed as Lie[k] Wess, Σ/ A log p(k, i, e). Subsequently, u is assigned to the cluster that maximizes this log-likelihood over [K. This process is applied to all nodes and iterated log n times. One iteration of this process is fast: by taking advantage of sparsity and computing by traversing only the node pairs for which label exists, the computational complexity can be reduced to (log nt). The improvement step corresponds to improving the cluster as- signment along the nonlinear decision boundary, as reflected in the definition of our divergence D(a,p).
9: U, - (O - (1s-I(U(RR110
10: (Estimated k-th singular value) x + ||AUis]1
11: end while
12: K < k- Ú A
1.k A.K
13: 3. k-means Clustering:
14: In + a subset of I obtained by randomly selecting [[og n) nodes
15: for to [log n| do
16: for each v E IR do
17:
2 00 -
w E
| A
||
I P
100
4. Theoretical Guarantees
18:
end for T(())
19:
0 for all &s E [R]
In this section, we provide a sketch of the proof of its per- formance guarantees, with the full proof available in Ap- pendix C.2.
20:
for = 1 to K do
(1)
U
T
21:
"t f- arg max
wEIR
Th - Q
(t)
I (1)
22:
oz
4.1. Spectral Clustering Initialization
23:
Sk
(())
(T(00)
Σ A
The following theorem establishes performance guarantees for the cluster estimates returned by the spectral clustering algorithm (refer to Algorithm 2 for details). Specifically, we show that the number of clusters is correctly predicted as K K= K, and the number of misclassified nodes is ((1/)) which is on)) as np- = (1).
VET!!))
24:
end for
25:
for each v E I
U k== T(()) do
26:
k- + arg min
A
(1)
2
5k
ISkSk
T
- ((() U cfo}
27:
k-
Theorem 4.1. Assume that (AI) and (A2) hold. After Algo-
28: end for
rithm 2, for any > 0, there exists a constant C. > 0 such that
Σ - ?
29: It
FET(()
K U
C S
30: end for
R-K K and
min
Se Iock) k=1
31: 1x x- arg
min Tt
p'
IstS [logn]
32: S T((() for all l: E [R]
with probability at least 1 - exp(-enp) where the mini-
Output: Clusters {
R
mization is performed over the permutation 0 of [K].
Proof Sketch of Theorem 4.1. Let 2 denote the expec- tation of the matrix A Mc. = j,i,j,() when u V.
(a) The first ingredient of the proof is to use an upper bound
6

---

Revisiting Instance-Optimal Cluster Recovery in the Labeled Stochastic Block Model
on the norm of the noise matrix X Af- Mf. which holds with sufficiently high probability, stated in the following lemma from (Le et al., 2017, Theorem 2.1).
with Lemma 4.4, this indicates that K K with probability at least exp(- Therefore, we can assume in the remainder of the proof that K = =K
Lemma 4.2. For any l E [L], for any C > O, there exists
Without loss of generality, let us denote as the permu- tation of [K] such that the set of misclassified nodes is U Sk \ In(z)- Based on Lemma 4.3, we can prove that: with probability at least 1 - ex)p(w()))
C" > O such that:
1x S C² nnp
with probability at least 1 - exp( CCp).
K U k=1
Sk I ('mp)""'pp
We note that such tight guarantee was also observed in (Gao et al., 2017) for the simple SBM using differ- ent algorithms. We also note that proof techniques like the symmetrization argument (e.g., Hajek et al. (2016)) cannot be directly applied for the sparse regime (p ((logn)/m)) Recall that we defined the concatenated matrix À = [A,,AR.
K
|M Mihh--Mr,iiee Mr
Aom
DES (Z,(0))
S 8|| All + 8r.
....... Af...., Af]. Based the above lemma,
where Mr.,(k) = Mr. for w E I,),). and where Te. is defined in Algorithm 2. Furthermore, for any C' > 0, using Lemmas 4.2 and 4.4, we can establish that there exists a constant Co > such that
we deduce that for any C > O, there exists C² > 0 such that
A Mrll S C² Vnp,
with probability at least - exp)-Cnp).
Mr - Al S Comp
(b) The second ingredient of the proof is the following lemma, whose proof is provided in Appendix E.6. The lemma provides a lower bound on the distance between two columns of Mr corresponding two nodes in distinct clusters.
with probability at least 1 - exp(-eppppppppeeeee Through a refined analysis of the k-means algorithm, we can also prove the existence of a constant C1 0 such that r+- S Cinp. For details, please refer to Appendix D.
Lemma 4.3. There exists a constant C > such that with probability at least - ex)(-w(n)),
4.2. Likelihood- -Based Improvements
To complete the proof of Theorem 1.2, we analyze the likelihood-basee improvement phase of the IAC algorithm. For this purpose, we define the set of well-behaved nodes H. We denote the total number of node pairs with observed la- bel l including the node v and a node from S by e(v, S, E) =
||Mr,. Mr Cemp²,
uniformly over all v, w. E I' with (l)) + a(w).
(c) The final proof ingredient, which is proved in Ap- pendix E.7, concerns the performance of the iterative power method with singular value thresholding that outputs the rank- K approximation Å (see Algorithm 2).
Σ Ewes A and let e(v, S) Ete e(v, S, Let H be the largest set of nodes v E I that meet the following three conditions with some constant CHi > 0:
Lemma 4.4. For any e >>0 0, there exists a constant C' >>> 0 such that with probability at least 1 - 1/n".
(HI) e(v,Z) S CHIMp:
(H2) when E In. E Eieo (v, log p(k. np
|| - A S COK+1,
p(...e)
for all j + k;;
log" ny
where 0++1 is the (K+ +1)-th singular value of the matrix A.
(H3) e(v.I H
2np log (mp)
The challenge is that all these Lemmas require quantified high-probabilityy guarantees. We are now ready to prove the theorem. We first explain why the number of clusters is accurately estimated. is straightforward verify that there exist two strictly positive constants, C1 and C2, such that with probability at least 1 - (n)) Ciğ S P < Czū (refer to Lemma C.5). Consequently, from Lemma 4.2, we deduce that for any C. > O, with probability at least 1 1- exp(-Crp). the (K + 1)-th singular value of Ar is significantly smaller than / ppn log(n)). In conjunction
We will show that all nodes in H are correctly clustered with high probability, and that the expected number of nodes not in I matches the lower bound on the expected number of misclassified nodes. Each condition in the definition of H can be interpreted as follows: (H1) imposes some regularity in the degree of the node, (H2) implies that E H is correctly classified when using the likelihood, and the last condition (H3) implics that the node does not have too many labels pointing outside of the set H.
7

---

Revisiting Instance-Optimal Cluster Recovery in the Labeled Stochastic Block Model
First, we show that the number of nodes not in H can be upper bounded by a number that is of the same order as n exxp(=nD(a.p) p)), both in expectation and with high probability.
4.3. Technical Challenges in Instance-Specific Analysis
The design principles behind IAC build upon existing stud- ies that have proposed two-phase algorithms employing initial spectral clustering followed by iterative improvement steps (Yun & Proutiere, 2016; Gao et al., 2017; Gao & Zhang, 2022; Xie & Xu, 2023). However, their analyses are either (i) minimax in nature or limited to the simple SBM-with no analysis for general number 5 = o(n) (Gao et al., 2017: Gao & Zhang, 2022; Xie & Xu, 2023) or (ii) provide only high-probability guarantees (Yun & Proutiere, 2016).
Proposition 4.5. When
$ 2 nexp -nD((a,)) +
np
we have
log" 3 np
BIIZ' \ H|
3np
< + exp
+ expl exp(-w(np))
4 log" ni
Moreover, lim P(ZZ)
H S =1
1.
The proof of Proposition 4.5 can be found in Appendix C.3. The proof reveals that the probability of node satisfying (H2) is dominant compared to the probabilities of the other two conditions and is of the order of exp( -nD((n,
Most of the existing analyses are limited to the simple SBM or minimax frameworks and hence do not readily transfer to the instance-specific analysis. If we consider the general (L)SBM, the optimal decision boundary of the cluster as- signment is asymmetric and should take into account the information geometry, reflected in the definition of our divergence D(a,p).
Next, we examine the performance of the likelihood- based improvement step (Line 6 in the IAC algorithm) for nodes in H. In the following proposition, we quantify the improve- ment achieved with one iteration of this step.
The exception is (Yun & Proutiere, 2016), who provided an instance-optimal analysis under the general LSBM. How- ever, their analysis limited to high-probability guarantees. More precisely, this algorithm misclassifies fewer than 8 nodes with a probability that tends to as n grows large, provided that and the parameters satisfy the condition (1). The probability of the failure event (which corresponds to the case where the algorithm misclassifies more than s nodes) is not quantified, but is necessary if one wishes to derive guarantees in expectation.
Proposition 4.6. Assume that there exists a constant C' >>
such that
K U L
k=1
Then, for any constant C' > O, with probability at least 1 1-exp (-C'np), the following statement holds:
U ((+1)) \ n
I
for all t2 O.
UUEE (1))) [
5. Conclusion
The proof of Proposition 4.6 can be found in Appendix C.4 and takes advantage of the fact that likelihood-basse test using the estimator ý(j, i, E) matches the test that would use the true likelihood, with high probability. Next, we present the sketch of the proof of Theorem 1.2 (refer to Appendix C.2 for a complete proof).
In this paper, investigate the problem of recovering hid- den communities in the Labeled Stochastic Block Model (LSBM) with a finite number of clusters whose sizes grow linearly with the total number of nodes. We reveal the nec- essary and sufficient conditions under which the expected number of misclassified nodes is less than s, for any number o(n):
Proof sketch of Theorem 1.2. we can now complete the proof by observing that from Proposition 4.6, after the [log n.] iterations of the likelihood-baat based improvement step.
(aD p) log(n/s) 2 1.
lim inf
JuK (s( ([(ogg)) m)) \ Ix) H 0,
To achieve this, we propose IAC (Instance- Adaptive Cluster- ing), the first algorithm whose performance matches these lower bounds both in expectation and with high probabil- ity. IAC is a novel two-phase algorithm that consists of one-shot spectral clustering step followed by iterative likelihood- cluster assignment improvements. No- tably, this approach is based on instance-specife non- linear lower bound and does not require any knowledge of the model parameters, including the number of clusters. By performing the spectral clustering only once, IAC maintains an overall computational complexity of O(n (olylool) making it scalable and practical for large-scale problems.
with probability at least 1 - exp(-Cnp) for any constant C > 0. Combining this result with Proposition 4.5, when
nexp (n, + log" mp
E| IAC (n)) <
1 o(1) BIIT HI] + +(1)
$ 1 - o(1 (1 + exp
3np
log np
+ expp( (pp(-w((pp)) o11)
and (AAC(n) S o(1), with high probability.
8

---

Revisiting Instance-Optimal Cluster Recovery in the Labeled Stochastic Block Model
Our results bridge the gap between existing upper and lower bounds for cluster recovery in the LSBM, providing tight necessary and sufficient conditions.
Backstrom, L.., Huttenlocher, D., Kleinberg, J., and Lan, X. Group formation in large social networks: member- ship, growth, and evolution. In Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 44-54, 2006.
Future work could explore extending these results to models with more complex cluster structures (e.g., the Multiplex Stochastic Block Model) or consider robustness to model misspecification and adversarial noise.
Barbillon, P., Donnet, S., Lazega, E., and Bar-Hen, A. Stochastic block models for multiplex networks: An ap- plication to multilevel network of researchers. Journal of the Royal Statistical Society Series A: Statistics in So- ciery, 180(1) (880())295--111 -14, 2016
Acknowledgements
Kaito Ariu is supported by JSPS KAKENHI Grants No. 23K19986 and No. 25K21291. Alexandre Proutiere is sup- ported by the Wallenberg AI, Autonomous Systems and Software Program (WASP) funded by the Knut and Al- ice Wallenberg Foundation, the Swedish Research Coun- cil (VR) and Digital Futures. S. Yun is supported by the Institute of Information & Communications Technology Planning & Evaluation (ITPP) grant funded by the Korea government (MSIT) (No. RS-2022-11220311 Development of Goal-Oriented Reinforcement Learning Techniques for Contact- Robotic Manipulation of Everyday Objects, Al Research Hub Project, and No. RS-2019-11190077 Artificial Intelligence Graduate School Program (KAIST)).
Bordenave. C., Lelarge. M., and Massoulié. L. Non- backtracking spectrum of random graphs: Community detection and non-regular ramanujan graphs. In FOCS, 2015.
Chatterjee, Matrix estimation by universal singular value thresholding. The Annals of Statistics, 43(1):177-214, 2015.
Coja-Oghlan, A. Graph partitioning via adaptive spectral techniques. Combinatorics, Probability and Computing, 19(2):277224,, 2010.
No. RS-
Decelle, A., Krzakala, F., Moore, C., and Zdeborová, L.. In- ference and phase transitions in the detection of modules in sparse networks. Physical Review Letters, 107, 2011.
Impact Statement
Dhara, S., Gaudio, J., Mossel, E., and Sandon, C. The power of two matrices in spectral algorithms for community recovery. IEEE Transactions on Information Theory, 70 (5):3599-362) 2024. doi: 10. 00110999TT.202233346690
This paper presents work whose goal is to advance the field of machine learning. There are many potential societal consequences of our work, none of which feel must be specifically highlighted here.
Dreveton, M., Fernandes, F., and Figueiredo, D. Exact recovery and bregman hard clustering of node-attributed stochastic block model. NeurlPS, 36:37877-37888, 2023.
References
Abbe, E. Community detection and stochastic block mod- els. Foundations and Trends in Communications and Information Theory, 14(1-2):1-12,, 2018.
Fei, Y. and Chen, Y. Achieving the bayes error rate in synchronization and block models by sdp, robustly. IEEE Transactions on Information Theory, 66(6))3929-399) 2020.
Abbe, E. and Sandon, C. Community detection in general stochastic block models: fundamental limits and efficient recovery algorithms. In FOCS, 2015a.
Feige, U. and Ofek, E. Spectral techniques applied to sparse random graphs. Random Structures Allgrithmss 27(2): 251-275, 2005.
Abbe, E. and Sandon, C. Recovering communities in the general stochastic block model without knowing the pa- rameters. In NewrIPS, 2015b.
Gao, C. and Zhang, A. Y. Iterative algorithm for discrete structure recovery. The Annals of Statistics, 50(2):0000))))) 1094, 2022.
Abbe, E., Bandeira, A. S., Bracher, A., and Singer, A. De- coding binary node labels from censored edge measure- ments: Phase transition and efficient recovery. IEEE Transactions Network Science and Engineering, 1(1): 10-22, 2014.
Gao, C., Ma, 7.,, Zhang, A. Y., and Zhou, H. Achieving optimal misclassification proportion in stochastic block models. Journal of Machine Learning Research, 18(1): 1980-2024, 2017.
Abbe, E.,, Bandeira, A. S., and Hall, G. Exact recovery in the stochastic block model. IEEE Transactions on Information Theory, 62(1):471-49)) 2016.
Gaudio, J. and Liu, H. Spectral recovery in the labeled sbm. arXiv preprint arXiv:2408. 13075, 2024.
9

---

Revisiting Instance-Optimal Cluster Recovery in the Labeled Stochastic Block Model
Hajek, B., Wu, Y., and Xu, J. Achieving exact cluster recovery threshold via semidefinite programming- IEEE Transactions on Information Theory, 62(5))2788-2797, 2016.
Tao, T. Topics in random matrix theory, volume 132. Amer- ican Mathematical Society, 2012.
Traag, V. and Bruggeman, J. Community detection in net- works with positive and negative links. Physical Review E, 80(3):036115 2009.
Halko, N., Martinsson, P.-G., and Tropp. J. A. Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions. SIAM review, 53(2):217-288, 2011.
Tsybakov, A. B. Introduction to Nonparametric Estimation. Springer Series in Statistics. Springer New York, NY, 2008.
Heimlicher, S., Lelarge, M., and Massoulié, L. Community detection in the labelled stochastic block model. arXiv preprint 1rXiv:1209.0 2900,,.990.... 2012.
Tzeng, R.-C., Ordozgoiti, B., and Gionis, A. Discovering conflicting groups in signed networks. Advances in Neu- ral Information Processing Systems, 33:10974-10999 10985, 2020.
Holland, W., Laskey, K. B., and Leinhardt, S. Stochastic blockmodels: First steps. Social Networks, 5(2):109-137, 1983.
Vershynin, R. High-dimensional probability: An introduc- tion with applications in data science, volume 47. Cam- bridge University Press, 2018
Kaufmann, E., Cappé, O., and Garivier, A. On the com- plexity of best arm identification in multi-armed bandit models. Journal of Machine Learning Research, 17:1-42, 2016.
Wang. P., Liu, H., Zhou, Z., and So, A. M.-C. Optimal non-convex exact recovery in stochastic block model via projected power method. In ICML, 2021.
Krzakala, F., Moore, C., Mossel, E., Neeman, J., Sly, A., Zdeborová, L., and Zhang, P. Spectral redemption in clustering sparse networks. Proceedings of the National Academy of Sciences,
Xie, F. and Xu, Y. Efficient estimation for random dot product graphs via one-step procedure. Journal of the American Statistical Association, 118(541):651-664 2023.
2013.
Lai, T. L. and Robbins, H. Asymptotically efficient adaptive allocation rules. Advances in applied mathematics, 6(1):
Xu, M., Jog, V., and Loh, P.L. Optimal rates for community estimation in the weighted stochastic block model. The Annals of Statistics, 48pp):pp. 183-204, 2020.
4 4-22, 1985.
Le, C. M., Levina, E., and Vershynin, R. Concentration and regularization of random graphs. Random Structures & Algorithms, 51(3):538-561, 2017.
Yun, S.-Y. and Proutiere, A. Accurate community detection in the stochastic block model via spectral algorithms. arXiv preprint arxiv:1412.7255 2014a.
Lelarge, M., Massoulié, L., and Xu, Reconstruction in the labeled stochastic block model. In 2013 IEEE Information Theory Workshop, 2013.
Yun, S.-Y. and Proutiere, A. Community detection via
random and adaptive sampling. In COLT, 2014b.
Leskovec, J.. Huttenlocher, D., and Kleinberg, J. Signed net- works in social media. Proceedings of the SIGCHI Con- ference Human Factors in Computing Systems, CHI '00, pp. 1361-1370, New York, NY, USA, 2010. Associa- tion for Computing Machinery. ISBN 978 1605589299.
Yun, S.-Y and Proutiere, A. Optimal cluster recovery in the labeled stochastic block model. In NewrIPS, 2016.
Zhang, A. Y. Fundamental limits of spectral clustering in stochastic block models. IEEE Transactions Informa- tion Theory, 70(10):7300-7344 2024.
Massoulié, I.. Community detection thresholds and the weak ramanujan property. In STOC, 2013.
Zhang, Y. and Zhou, H. H. Minimax rates of commu- nity detection in stochastic block models. The Annals of Statistics, 44(5):2252 2280, 2016.
Mossel, E., Neeman, J., and Sly, A. Reconstruction and estimation in the planted partition model. Probability Theory and Related Fields, 162(3):433-485) 2015a.
Zhang, A. Y. and Zhou, H. Theoretical and computa- tional guarantees of mean field variational inference for community detection. The Annals of Statisties, 48(5): 2575 2598 2020.
Mossel, E., Neeman, J., and Sly, A. Consistency thresholds for the planted bisection model. In STOC, 2015b.
Newman, M. E. J. and Girvan, M. Finding and evaluating community structure in networks. Physical Review E, 69: 0261 13, 2004.
10

---

Revisiting Instance-Optimal Cluster Recovery in the Labeled Stochastic Block Model
A. Notation Summary
Please refer to Table for a summary of the notations we use.
Table Notations
Symbol
Description
I
Set of items or nodes
Number of nodes Number of clusters
K
I
Set of nodes in the cluster k:
(a1, 02 O(k) T,
Probability that nodes are in each cluster
Number of labels
C = {l,...,.u
+}
Set of labels
e) P
Probability that the label & is observed between nodes in I, and Ij
maxij,f2 1 p(t, j, E)
n
Positive constant in (A1)
Positive constant in (A2)
Positive constant in (A3)
((a,p)
Divergence defined as in Introduction
π
Clustering algorithm
("((n)
Number of misclassified nodes
(n, b)
-2 / + /1 /
A (A
Observation matrix for each label
M
Expected matrix of A
Af.
Trimmed observation matrix, (Aff))uv A wreer
M
Trimmed expected matrix, (MF) we M w,ver
A
A [A], AP ..... A4]
M, Mr
M = [M M ................................ M Mr = [M Mr. ..... Mf
K
Estimated number of clusters
Á
Rank- K approximation of A Af. - Mf
X
(S*)
Initial cluster estimates
kEs)
Final cluster estimates
We use ||
|| to denote the no-mr,m i.e., ||=||| = V2 |25// We use the standard matrix norm ||A|| sup
||
==]|=]|a=1
We denote by M the expectation of the matrix of A i.e. M p(i,j, when E I, and E Iy. Let M |M
We also denote by e(v, = Eves A the total number of node pairs with observed label É including the node v and node from S and p(c, S, e(v.8.0) the empirical density of label Let S(c, [S]
Eln (vv, e) and p(v, S) [u(v, S, (oosee.. In what follows, e(v, I) is referred as the degree of node v, which represents the number of observed labels that different from 0 for pairs of nodes that include v.
B. Lemmas Regarding the Divergence D(a,p) p)
In this part, we present several lemmas in (Yun & Proutiere, 2016) related to the divergence D(a, p). Lemma B.I. Let (i", j²) be the indices that minimize D1+(r(0),P()) with it < <" In this case, there exists q (kx(L++) such that
D(a, p) Σ an (l(g(k).p(() p(i", k)) Σ au kl(g(k)

---

Revisiting Instance-Optimal Cluster Recovery in the Labeled Stochastic Block Model
Proof. Let us prove the existence of such q by contradiction. Suppose that
(a,, E Og kl(g(()) k))
Σ Oe kl(((k))
In this case, there must be a ko for which ((((()))pp(" ko)) > kl(g(Ko), , ko)). Noting the positive nature of the Ki-diivegeenc,, ((ko) # p(i", ko). As result of the Kl-diivegencc''s continuity, we can create of such that g(k) = (k) for all k # ko. and the following conditions hold: kl(g(ko). ko)) E < (ko) p()) < (k))( p(i", ko)) and kl(q' (k)) ko)) < kl(g(ko). kk)) + for some < (kl(g(Ko). p(i", ko)) kl(g(ko). p(j", p(j",ko))) 4/))) With this selection of q', obtain:
K
D(a,p)> >
Σ on klld' (k)d ((" k))
Σ
on p(J",
which is in contradiction with the definition of D p).
Lemma B.2. When p = o(1)
D(a.p) p)
lim as EE EVp(iVi k,) kk()),
2
Σx=1
k=
Proof. Let (1") be the pair that minimizes DL+ (a, p()). with 8 < According to Lemma B.1, there exists such that
K
((a,p) Σ og p(((()).
kl(r(()),((i"k)))
Following this,
Ek= (l)k)(((()..(( 1:)) + ar kl(g(l)).
nD(a,p) = n
2
klit,k,, E)pli" k)
ak
g(k, 1)
((k,t)
2 n
O
((kk 6) - Vplii, ppli,,k k. Exp(p,
k=1
1=0
K
(oai ,kk E) + p(j", "odji,,,0 k)
=
atk
Σ
v p(i k. E)p(i,,k,)) kk
(1 (1- o(1)
2
k=1
Oik
VVp(it,,, k) kD(o",k,0))
(1 o(1))
Lemma B.3. Under (AI), when p o(1), lim supn-cc
Día.p) TpL. < 1.
Proof. Based the definition of D(a,p). for any i + j. we have:
K
K
D(a,p) < max
ay k(i,
Σ
au ((o(i
O (l(((pi(,)))). k()
(p(i,k, E) - p(j, E)) k)),
(1+0(1))
k=
Pml
12

---

Revisiting Instance-Optimal Cluster Recovery in the Labeled Stochastic Block Model
mP + o(1))
t=1
mpL( + o(1)),
where we employ log(1 + r) = xx1 + o(1) when x = o(1).
C. Performance Analysis of the IAC Algorithm Proof of Theorem 1.2
C.I. Preliminaries
Lemma C.1 (Chernof-Hooeffding theorem). Let X1y... Xn be i...d Bernoulli random variables with mean v. Then, for any 8 0,
P
Xi 2 v +
(exp(=nk((+t..0))
P
Xi 1 8
(exp(-nkl( - -011)
Lemma C.2 (Pinsker's inequality (Tsybakov, 2008)), For any p.q 2(p 9)² kl(p.g).
Lemma C.3. For each v E I, for any constant 0,
(e((v, 2 Cnp) 2 exp( (C )m)mp).
The proof is given in Appendix E.I.
Lemma C.4. For all In and D 2 0,
I kl(u(v I), 2 nD n (elv.2) s Cmmp)
Σ
100m2n1221 1.2
exp -nD KT. lo00n(107nmmpp
a1
The proof is given in Appendix E.2.
Regarding the estimation of p as p, we show that p has the same order as with high probability:
Lemma C.5. Let C1 and C2 be constants such that 0 < Ci < 1 (1 ) and C2 > et. Then,
C Cap
holds with probability at least cxp((w(m))
The proof is given in Appendix E.3.
C.2. Proof of Theorem 1.2
For each E [K]. from Chernoff- -oerifff--offfiing's theorem and Pinsker's inequality, for any constant
> O, we get:
(1 [&l agnl S nlg S cxp
-n
a4
log
Vni .ax .x)) exp
-nkkl ax
log
akk
Vn
< 2exp
(-2(logn)2)
1
(2)
c
13

---

Revisiting Instance-Optimal Cluster Recovery in the Labeled Stochastic Block Model
Hence, make the assumption that for every k [K], the inequality
| - a S /n
(3)
is maintained throughout the remainder of the proof.
With a positive constant CH1, let H be the largest set of nodes E I satisfying:
(H1) e(v,I) S Cinnp.
p(k.a.)) (H2) When v E Iks Ein Eiio e(u, fog p(a..)) 2 logingys for all j +
ng
(H3) e(v,I I H) < Tog"
(HI) controls degrees, (H2) implies that e E H! is accurately classified using the (true) log-likelihood, and (H3) indicates that e has limited number of shared labels with nodes not in H.
From Proposition 4.6 and Theorem 4.1, after the [logn] iterations in the further improvement step (remember that nğ = (1), so that 1/ nmp S e -2 when is large enough), for any > O, there exists C' > such that
(S (
H
( U
(np)
Jog
k=1
k=1
1
C
log
P
o(1)
(4)
with probability at least 1 - exp(-cnp), where the last equality is from np w1). Therefore, for any C 0, no node in H can be misclassified with probability least 1 - exp(-Cnp). Hence the number of misclassified nodes mp
cannot exceed II \ H), when 2 nexp (-nD(a,p) p) + log np
(the condition of Proposition 4.5 holds). When s 2
n exp (-nD(a.p) + log ap
ng
na p)
Tog(np)
nD p) log(n/s)
lim inf
lim inf 200
(5)
4-000
log(n/s)
where we used D(o, p) = (2pp) (from (A2) and Lemma B.2).
Let A an event defined as:
A = {1 | (S
I < c and (3) hold
where C' > 0 is some large enough constant. We upper bound the expected number of misclassified nodes as follows.
E IAC
(m)]
B|E TA (m)LAAI((A) ElE (I)AA)
(AI (m) +P((A)
BlELAC (n) + o(1)
E E || + ((1)
Σ
IP I H = z(|A) + (1)
2=.....
P(I H x. AA)
Σ
+ +0(1)
P(A)
0
14

---

Revisiting Instance-Optimal Cluster Recovery in the Labeled Stochastic Block Model
xP([ 11| - o
P(A)
E H|] o(1)
((1)
W
1
o(1) 8 (1+exp exp (-
log" np ) + +xx((-w(pp)) + o(1),
3np
where (a) is from Theorem 4.1, (2), and p Ollog n/n); (b) is from Proposition 4.6; (c) is from Theorem 4.1; and (d) is from Proposition 4.5, This concludes the proof.
C.3. Proof of Proposition 4.5
We quantify the number of nodes satisfying (H1) and (H2) in (6) and (7), respectively.
Number of nodes satisfying (HI): From Lemma C.3, for any constant CHI > for each I,
P()(u,I) & Chmpp} 2 1 exp(-(CHI - -e²))mp)
(6)
Number of nodes satisfying (H2): We aim to prove that when fulfills (HI), it also satisfies (H2) with probability of at least
exp (nDD(a.p) +
log(np)3 - exp( ((p))
up
To achieve this, we first assert that e meets the condition
I (M) S (1 log(n)²
nD(a,))
(8)
vn
log(np)**
then v complies with (H2). fact, assuming that (8) is true, we have the following:
(i) Σx ankklu(u p(), i)) S (1+ log(n)) v
E I [i), i)) EnD(a, p). because [|Z agnl S
Volog(n) (from (2)) and (8) holds with probability least 1 exp(-w(np)):
(ii) Σ (mn i)) 2 nD(,,,) p), since max EE a kl(u p(),(()))) E as (((((,,)),,(kk.1))) 2 D(a,p) and
K a kl(m(u,, p(k, 0) < Daa,));
(ii) Σ [Llkl p(j. 2 (1 log(n)² v
n nD(ax,)) p), from (ii) and the fact that [| - -ayn| S Volog(n);
(iv) from (8) and (iii), for all j +
E(k,i,))
Σ
cvu I, log
Σ I (K)
Kl(u(o,Z)). i)))
i(j,i,))
np
log(np)1
Therefore, v satisfies (H2). The remaining task to assess the probability of event (8), which can be done by applying
Lemma C.4 and proving (7).
Based on (6) and (7), the expected number of nodes that fail to meet either (H1) or (H2) can be upper bounded as follows.
The number of nodes that do not satisfy either (H1) or (H2)
15

---

Revisiting Instance-Optimal Cluster Recovery in the Labeled Stochastic Block Model
< mexx(=-(CHi mmp) + nexp (-nD(a, +
np
+ nexpp-=w(np)
2 np
From Markov's inequality.
P The number of nodes that do not satisfy either (H1) or (H2) >
p(np)5
s (np) exp(-(CHn -ed) (np) exp (-nD(a, + loog nip
np
+ (np) exp(-w(npp
(-nD(a.p)
np
S exp
4 logg np
We obtain the following upper bound on the expected number of [Z H.
Z
H
expp
(nnD(a,,)) + Tlog(ap)
ng
+ nexp (-w(np))
+
3np
+
exp
+ exp(-w(np)).
4 log" npp
This concludes the proof the guarantee in expectation as nă = (11.
Regarding the high probability guarantee, the subsequent Lemma C.6 instrumental finalizing the proof, and its proof can be found in Appendix E.4.
Lemma C.6. Let Φ < 1/(5(p)))) When the number of nodes that do not satisfy either (HI) or (H2) less than 0/3.
[I') H S Φ, with probability least -exp(-w(pp))
From Markov's inequality, for a sufficiently large choice of Cin
PP (The number of nodes that do not satisfy either (H1) or (H2) 2 s/3)
E The number of nodes that do not satisfy either (H1) or (H2)
8/3
mexp(-(CHi em)p)) + nxp (nDD(a,p) + 21og" up
aF
+
s/3
nexp(- e nexp
-nD(a,p) + 21og mp
ap
+ +nexp(-w(np)
exp
(nnD(a,p)
aF "og" np
< 6exp(-(Cr, cd)pp + nD(a, p)) + cxx
+ +3exp(-w(rp)
21og np
(a) o(1),
where for (a), we used nD(a.p) (np) from Lemma B.3. Combining with Lemma C.6, [Z H| S 8 with high probability. This concludes the proof.
C.4. Proof of Proposition 4.6
Recall that (5) JIsisK represents the partition after the i-th improvement iteration. Note that without loss of generality, we assume the set of misclassified nodes in H after the f-th step to be g(t) = =(ue(S))) \Ix)) n H (it should defined
through an appropriate permutation ? of (1...., K} as g() (S(( I,())) 0 H. but we omit 7). With this notation,
16

---

Revisiting Instance-Optimal Cluster Recovery in the Labeled Stochastic Block Model
we can define& 6 = (5 n Ix) n and g U
Uijzzz El. jkc During each improvement step, nodes move to the most likely cluster (according to the log- -eeliikl defined in the IAC algorithm), As result, for all i [K],
K
,0) log e(),i,))
05 Σ Σ
c(u, Su,
jkitt veg(t+1)
K
L
(0 .)) log i(),i,)
$ E kkist veglt+1) i=l t=
ΣΣ
c(u,S
i)) + ( {
(9)
K
e(u,TN In. E) log p(j i, E) p(k; i, E)
Σ Σ
fkitt vEE
i=l P=0
Σ
e(w, (lggg())))(((n) + 5 (1+1)
np log" mp
(10)
w
np
1g(++))
Σ
e(w, g(t), log(2n) ()((++1
np log np
(11)
log np
WEE(L41)
S
np
|g(++))
ppt0 log mp 6)
ni log nt
(12)
log
up
Hence, based on the aforementioned incqualities, we deduce that
((++)
log" np
1
|008]
np
/np
Subsequently, we will validate each step involved in the prior analysis.
Proof of (9): Utilizing the inequality log(1 1 + x) I x, when p(j. i, f) - (0(i,i,) p(j,i,)) > O.
f()
P(. () - p((,,EE)
log 2(),i, e)
b(),i,) i,
Therefore, to prove (9), we merely need to present an upper bound for 1,(j,,,)) - p(i. 8, E)-- Applying the triangle inequality,
P(ji,0) - p(j. 1)
(((s ,5 .) 2()..
1s 1
(((s! .5)0, - E (0) 2) + Ble(S,"), ,5) (001--(i,4 -0.
(13)
1s 1
Firstly, we determine an upper bound for ((s(()) ,. E) E S .0] Let S represent a partition such that
K U
I = 0 log(np)²
Is
Sp
for all (StheAcK S.
1=1
Following this,
|S| <
Ken
5
<
17

---

Revisiting Instance-Optimal Cluster Recovery in the Labeled Stochastic Block Model
= exp (0( (18((1)))
(14)
For every (SkS E S and for all { 2 and S 4,j S K, e(S,, E) represents the sum of [S:] | (or [s, when i= j) independent Bernoulli random variables. Given that the variance of e(S,, Sj, E) is less than n²p, by applying the
2
Chernoff inequality (for example, Theorem 2.1.3 in (Tao, 2012)), with a probability of least 1 - exp (-e [og(np)
le, - Eie(S,, O1I & n log(np)2 |
for all i,j.e
(15)
From (14) and (15) and union bound, with probability at least 1 - exp (-0) Log(ne)"
le(S;, Sy. - E[e(S,, Sy. 41 & n log(np)² for all i, e and {StheASK E S.
Since (Sh JICKKK S, from the above inequality,
155 .)) - Bie(s!") _.)" & nlo((pp) for all i,j,
(16)
with at least probability exp (-e ( (108(1))*)
We now devote to the remaining part of (13). Since for any C > 0, |_(0)] = [og[(nz)²) with at least probability
1 exp (-Cnp) from Theorem 4.1,
Ble(s(", S 0) 1s (p(...))) /n/E (mp(i. On log(n))
(17)
Observe that since p = (0( logn) and np = w(1)
np
(log n mp
log(ng))
log (17)
log n² log log(logn)) n
O
=().
(18)
Considering (13), (16), (17), and (18), for any C > 0, with probability of at least 1 (-ppp)ppp)
( p(j. i, 0) (log(mp)))/m /n) for all i,j,e
which leads to the conclusion that:
log f)
< b(j,i,e) -(.0))ppjji.... i()
O log(np)² p(. (0(,,,,,, p(j.i() np(j. i,
for all i,j.
f(j,i{)
Given that e(v, 500 .0) < e(v.I) I) I 10mpL as per (H1) and np(j,i, 2 (np)* according to (A3), for all I and i, j,j.k,
Σ c(v,, St .0) log p(j,i,)) log f(j.i,))
L
i(k,i,)) p(k, i, = (ID)()))))N))1-1))
t=
Proof of (10): As log p(j..0)
= O holds for all i, le and |g(0| 0log(nz)2//1)
p(k,i,0)
K
4
St (1)) , log i,)
Σ
p(k i,
1=1
0
18

---

Revisiting Instance-Optimal Cluster Recovery in the Labeled Stochastic Block Model
K
p(ú,i,()((k,,,0) p(k,i,()p(i,,,0)
|s/2 log
c(v,
S. e) log
p(k,2,0)
t=1
i)
plj.i plú,i,()(kk,,,0) pkk, i, f)p(2,2,0
[Z:] log
Σ
c(v, S
log
log
pkk, 0)
K
p)j,i,))
K 7
c(u, Ii {) log
ΣΣ
c(u,I, I \ S log(2n) + log(np)*
p(k,i,e)
t=1
p(j,i,))
(e(v,Et)) =e(u,I H)) log(2n) + log(np)
(I,I,,,)los
p(k,i,()
L
() p(k,i, + log((2)))((, (0) + 4np
c(u, (, log
log" np
where the last inequality arises from (H3), specifically, from the condition e(v, I () S
2np log" np
when u belongs H.
((+1) Proof of (11); Given that g(++1) c H and all E И fulfill (H2), every v in jk
meets the following condition:
K
e(v, Ii () log p). ikk
np
<
log mp
t=
Proof of (12): Define I = elu; S CHINp) and let Af. represent the modified matrix of A with elements in rows and columns corresponding to w & I set to O. I consists of all nodes that meet (H1), and H is subset of r. Consider Xp = E (Af - Mf). We obtain:
Σ vE
(e( Ble(v, {()) S 12:0 Xx Ig
where 1s denotes vector where the v-th component if E and otherwise. Given that E(e(u,E()) S (T) and for any > 0, the |rlll S vnp log np holds with probability of least 1 - cxp(-Cmpp according to Lemma 4.2,
Σ
c(v,E(9) = Σ (e(u,E()) Eje(v, e(1))) + pL. p
Xp Leatu ll2 + g((+)) log(np)
oo Iall + (g(++)) log(np)
(((+))) (nplog(n)) + log(p))
This concludes the proof.
D. Proof of Theorem 4.1
First, we show spectral analysis on Af Mf by extending the technique by (Feige & Ofek, 2005; Coja-Oghlan, 2010). Lemma D.I. For any e [L]. for any C' > there exists C" such that:
||xf _ C² Vnp.
with probability at least 1 (Cppp-
The proof of Lemma 4.2 is given in Appendix F.5.
19

---

Revisiting Instance-Optimal Cluster Recovery in the Labeled Stochastic Block Model
Therefore, for any C>> there exists C" such that:
|| - Mr
- Σ |
SC'
with probability at least - exp(-Cxppp Next, prove the lower bound the column distance of Mr. Lemma D.2. There exists a constant C such that with probability least 1 exp(-w(n)),
|M Mr 2012 2 Cemp",
uniformly over all v, w E I' with (v) # a(w).
The proof of Lemma 4.3 is given in Appendix E.6.
Furthermore, we can show that the iterative power method with the singular value thresholding procedure estimates the number of clusters correctly and the matrix an accurate rank- K approximation the matrix A with sufficiently high probability.
Lemma D.3. For any > there exists constant C > such that with probability at least 1/n²,
All S CoR+1:
where Øk+1 is the (K + 1)-th singular value of the matrix A.
The proof is in Appendix E.7.
We can prove the theorem as follows. The proof draws inspiration from the proof of Theorem 4 in (Yun & Proutiere, 2014b). However, we obtain a high probability certificate of 1 - exp(-Cnp) for any C' > 0. Throughout this section, we assume K- (for any c > 0, the event occurs with probability at least exp( - cnp) from Theorem 4.1) and let (kk arg min, U S& \ [m( Define Mr,y()) as Mr. == Mr,.. where is node that satisfies I_(k)) According to Lemma 4.3, there exists constant C > 0 such that, with probability least exp(-w(n)).
(n)) C'np²
U k=1
Sx \ I(x)
C''pp'
K
||Mr, - Mr.a012
k= vESi (T,(0
K
2
Σ
(IMM, - Exll2 + I1Ex - Mr
k= DE (T((())
K
Σ
||Mr, Exl13
K
<
Σ
(IAMr,0- 11AM.--A.11.
A.l + -1 Exl13)
1=
DE Sp (IN(M)
M|
Á + 8r
where || || denotes the Frobenius norm of a matrix. To complete the proof, we need:
|| Á = O (np)
(19)
Tr- = (np),
(20)
with the high probability guarantee.
20

---

Revisiting Instance-Optimal Cluster Recovery in the Labeled Stochastic Block Model
We first prove (19). From the equation (1.4) of (Halko et al., 2011),
0k++
min rank(X))
||A - X
where og is the k--th largest singular value of the matrix A.
For any matrix A of rank K, it holds that ||-|| & -- Since the rank of the matrix and Mr are K, the rank of the matrix À - Mr is at most 2K. Then, Lemma 4.4 implies, for any e O, there exist constants Ci C2 such that with probability least 1 - 1/n².
Mr - All? & | AlE
Mr Arllă A - AlE
4K|| Arll 4KC1ok+11
Mr Arl 4KC
min [ank(X)
|| X112
S 4K||Mr Ar +4KC || Ar12
S Mr - Arl2.
Therefore, together with Lemma 4.2, for any O, there exists constant C' > 0 such that
Mr - All S Cnp
with probability at least exp(-cnp)-
Next, we prove (20). It is sufficient to show that there exists i, E (1.2..., [logn]) such that r, = =O(np) First, by Lemma
4.2, for any C' > 0, there exists a positive constant D1 > 0 such that
|| Mr 1 8D1np
(21)
with probability least 1 exp (-Cnp). By Lemma C.5, for any constant D2 such that with probability least 1 exp (-w(n)),
20K a
there exists {l,..., [logn]}
p
64n
32D2Dı S it
<
D2Dip
100
1/e
Define sets of nodes 4g and W as
1 =
E IA : 11A, - Mr.xl
-
4
100
5
W = VET: ||A. Mr,x11 2 4i,
for all & E [K]
100
These sets have the following properties:
For all e E Ix. In C Q!!c)
For all v E Ts. A - A s 211A Mr.al1 + 2/ - Mr s i 1
For all v E W. (UK I+) (6+) =0
since for all o' E U U Jt. A Ar z 311
Mr. -11 Mr
F
100
From (21), we have
1 i
r
U k=
Is
Σ
11A
Mr,
100
uur 4)
21

---

Revisiting Instance-Optimal Cluster Recovery in the Labeled Stochastic Block Model
$ - Mr 2 - 2K || - Mr 12 16K Dinp,
with probability at least exp(-Cnp). Thus, we have
K
-1
r
U
I
S
16K
P 301100
2nK
D2
(n)
10"
with probablity at least
+ o(1)). Therefore, we can deduce that
For all v E W. 1Q! S n a1
10
For all e E U Jn 1Q!ht) 2 ain - (n 12 41 TU 2 0 72
with probability at least exp(-Cnp(1 + o(1)).
For each 1: E [K], the probability that Vn2 I is most:
[Olog n
(1 5
< n2 Glogg
where C' 0 is constant depends only on a1- Thus, for any d' > 0, VR contains at least node from 4. for all k [K] with probability at least exp(-c'nph) + o(1))). Therefore, any v E W will not be assigned as i with probability least exp(-Cnp(1 o(1))) It implies that ||Á.; MT 112 4i, TOU for all [K] with probability least
1 cxp(-Cnp(( (())). Regarding the centroid & of the clusters, since A, is within v 5is 100 Euclidean distance for all v E T
F from Mr.,(K) in the
15 Mr 5ig P 100
320m D2
p. Vk [K],
1 1/e
with probability at least exp(-Cxppp + o(1)) Thus,
K
Ι - E 11
k= BET((t))
K
Ι 1
1= DETAnI
K
Σ (114 Mr 115 +1c()
Mr,el 12)
k= DEIAN
640n D2
32KD;
1/ee np
with probability at least exp(-Cnp(( + o())) This concludes the proof of Theorem 4.1.
22

---

Revisiting Instance-Optimal Cluster Recovery in the Labeled Stochastic Block Model
E. Proofs of Lemmas and Corollary
E.1. Proof of Lemma C.3
Let } be Bernoulli i..d. random variable with mean p. First, for any C1 > and for every o E I, by Markov's inequality,
Elexp(Ae(v,2)]]
PP (e(r,,I) 2 Cinp)
inf
A20
exp(ACinp)
E (exp(AL Xi]
inf
X20
exp(ACinp)
I (p(exp(AL) - 1) + 1)
inf
A20
exp(ACinp)
I (pexp(AL) 11)
inf
X20
exp(ACrni))
I exp(pexp(AL)
inf X20
exp(ACimp)
exp(npexp(AL))
inf
X20
exp(ACinp)
S expl (C1 - mm))
This concludes the proof.
E.2. Proof of Lemma C.4
Consider X' as a collection of K x (L + 1) matrices, defined as follows:
K
L Fie S 10mpL, and Σ E=
x= = x E E
Fife
[Z,] for all isisk K
1=1
To simplify notation, we employ [ in place of [ losees to denote the probability mass vector for labels defined by 24. We also use e(u) to represent the K x (I+ 1) matrix, where the (i, f)-th element corresponds to e(v, Iz, e). Consequently, for u E Is.
) n (cle. s 10mpl) }
Σ I II(p(,,II)ppk.. i)) 2 mD)
K
= Σ mEN
Pe(v) = x} P
Σ
I kl(H(u,, p(k: i)) 2 nD c(u) = x
Σ [Tn] kl
(29 Fule (kk,)) 8))
exp
Σ P(e(v)= x}
exp(nD)
#E.
zut
Fie
1=0
P(e(v)= x
exp(nDD)
mE
K
$1.0
L
1
Di.E
expl
mir))
exp(nD)
Izl
TEXt 3m1
1=1
k
exp(nD)
II
exp
([Ig)
Σ
xxte)log log
1-
Di=1Iit
I
Σ ase
nEXi=i i=1
K
exp(nD)
cxp
[Z,]
xcN i=1
23

---

Revisiting Instance-Optimal Cluster Recovery in the Labeled Stochastic Block Model
(10mppL) KL exp(100n)np""22/omm
exp(nD)
(-nD) + KL log(10nLnp) +
100nj 2
nopp L2
exp
a1
where (a) comes from the subsequent inequality:
K i, i -
1.
[i,] (ii,))
P(e(u,I,,0 Iiee for all
II
p(k, 0)
II
p(k, i, eyane
i=1
E=1
[e[T]]
21.
II
pkk,
81,0 %).00
II
p(k; i, 1)00.
Fi,
i=1
E=1
This concludes the proof.
E.3. Proof of Lemma C.5
First, we evaluate the probability of the event 5 S C2p does not hold. Let {X:} be Bernoulli i.id. random variables with mean P. We have:
2
p 2 C2p)
P
A 2 C2p
n(n1
1)
1)/-1)/2
2L
IP
Xi C2p
n(n 1)
E exp
AL >
21=1
(n(nn11)/ 1)/2 X;
< inf
A20
n((n11 C2p)
exp
I m 11/2
(p(exp(AL) - 1)
inf
X20
A minn1)) C2p
exp
(in-1)/2 11/2
(pexp (L) + +1)
inf
X20
cxp
\ mn(n-1) 1) C21
m(n-1)
2 pexp(AL))
exp
inf A20
( A C2p
exp
((22 - ) n 1)
exp
2 1
C2 el n'p
S exxp
(22)
Next, we evaluate the probability that the event Cip < p does not hold. Letp:= min Let (Y,) be Bernoulli Li.d. random variables with mean p. We have:
P Cip) =P P.
2
Σ
Anw
-Cp
n(n E=1
n2n 12(n11)/2 1)/2
P...
2
L
Σ
Y -C15
nnn1
1=1
24

---

Revisiting Instance-Optimal Cluster Recovery in the Labeled Stochastic Block Model
-YL Σ 1 Y,
E exp
inf
-> "(1n(1 111
exp
ma(n-1/22 1)/2
(p (eexp(->11) 1) 1)
ii=1
< inf
A20
-X n(n C18)
exp
n(nn1) 1)
(exp( -AL) - -1)
exp
inf
X20
- n(n- C1p)
exp
1
n - 1)
n(n - 1)
+
C1P
eL
2
1
1)
1
n(n 1)
< exp
D+
C16
el
2
T
2
n(n -
1)
exp
C1
p
c
11
2
I exp
1
1
C1
n²
(23)
e
4
1
Combining (22) and (23), conclude the proof.
E.4. Proof of Lemma C.6
Define e(S, S) = E We now aim to prove the following intermediate assertion: with high probability, no
subset S C I exists such that S(S 2 Φ log" and inequality,
up
|S| = 6. For any subset S c I with | = 6. using Markov's
np
Elexp(e(S, S)Ø]
PP eS, S) 2 Φ
< inf 120
log np
Øt log" mp
(1 + Li ex))
inf
Øt up Tog" mp
LDLp
Φb mp
inf exp
exp(1)
2
log np
Φmp
2n
)
exp
log
log np
Φb. log np
(6)
dmp
2n
exp
2oo np
log
L log
6 mp
(24)
where we set t log(2n/(oLlog) log np)) for inequality (a) and utilize log (2n/ log" np) w(1 derived from
1/()(n))5) for inequality (b). Considering the number of subsets S c. I having size is (*) < en )o can infer the following from (24):
onp
}}
en
onp
2n
E
S e(S 2 (log 5 and |S|
exp
2 log 5 np
log
L log np
5
en
onp
2n
exp
blo
log
log
np
log' np
onp
2n
S exp
log
4 log
5
np
ΦL log
mp
Hence, applying the Markov inequality, there are subsets S I such that e(S, Φnp/ (log (p) and S ó with
probability of at least exp (- "Tolo np
anp
log
2n log" mp
25

---

Revisiting Instance-Optimal Cluster Recovery in the Labeled Stochastic Block Model
In order complete the proof of the lemma, construct the following series of sets. Let Z₁ represent the set of nodes that do not fulfill least of (H1) and (H2). Generate the sequence (Z( C Thiese follows:
(()) 71-
For 2 1, (1) = Z(L 1(1 v, E I exists such that e(vr, Z(1 1)) node exists, the sequence terminates.
2np log"(np)
and 2/ $ Z(1 - 1). If no such
The sequence concludes after constructing ((1)), which, according to the definition of (H3), is equivalent to I \ H. We now demonstrate that we assume the number of nodes that do not satisfy (H3) is strictly greater than &/2, then one of the sets the sequence (1) C Chggeee contradicts the claim we just established.
Suppose the number of nodes that do not meet (H3) is strictly greater than 6/2. At some point, these nodes will be incorporated into the sets (t), and according to the definition, each of these nodes contributes over log"(np) to ((Z(t), Z(t). Therefore, if we start with 2 and add 6/2 nodes that do not satisfy (H3), we obtain a set Z(t) with cardinality smaller than 0/3 + 2/2 and such that el (t)()), (()) > Tog"(ap))
2np
can further include arbitrary nodes to Z(t so that its cardinality becomes 6, resulting in set that contradicts the claim.
E.5. Proof of Lemma 4.2
We remark that the statement is taken directly from (Le et al., 2017, Theorem 2.1), but here we present an alternative proof which may be of independent interest. We will extend the proof strategy of (Feige & Ofek, 2005). Let us define discretized space that approximates the continuous unit sphere. Let & E (0, 1) be a fixed constant.
Σ r; = 00, $ }
T
n
where Z is the set of integers. From Claim 2.9 in (Feige & Ofek, 2005), |T| - exp(C(E)n) where C(E) is a constant only depends on s.
We first aim to prove that for all æ, E T, for any constant C >> 0, there exists a constant > such that
Ixc (Af Mf yl C² /np.
with probability at least - xxp(-Cnp).. Using this result and Claim 2.4 in (Feige & Ofek, 2005), we can deduce that for any C >> O, there exists a constant C" > such that
|4 Mfll
1x ToT(A (Af MF)ul
sup 1
1
C² Vnnp,
(1 2
with probability at least - exp(-Cnp).
Define set of light couples as:
C= (w,w) E I x I: I S
1
Also define set of heavy couples as its complement
L
(v, (v,w) E 1x (x.
Finally, let we define a subset of edges K. = (I x I) U (I x r Using these sets, by the triangular inequality,
xx T (Af. - 14
Note that this set is complement of l x
26

---

Revisiting Instance-Optimal Cluster Recovery in the Labeled Stochastic Block Model
(Af M x To (M* -MF)yl
E Aow
Σ FeA +
Σ (v,w)EC
x 22MMa x _M Mf)y
(O,W)E
(e,w)ERn2
s (,,,1 + P2(x,,) + Pa v) + (x),))
where
(1(2,))=
Σ
Iy Agonne
(v.ar)EKNC
Pa(2,
Σ
A.Abwth x M
(w:W)ER
P3(2,
E
A Tivotho
(u.w)EL=
Pa(2, J=T(M* CAM'-M())
We will show that for each fixed x, y T. for any constant C1 > 0,
Pz v) - 2C1 /np.
with probability at least - exp( We will also show that for each fixed x, y E T, for any C2 > 3,
P2 3) S C2v np with probability at least exp (- Ca-3 nn. Therefore, as [T| S exp(CCe)n), taking the union bound over T yields,
2
(r v) < 201 mp and
P2 v) S C2v npp,
C2-3 _,-3-20(6)n)) Therefore, for any constant C > 0, there
with probability at least - exp(-(Ci C(s))n) exp
exists constants C₁ and C2 such that for all x, y E T.
(1 v) - Civnp P2 v) & C2vRp,
with probability at least - exp(-Cn) Moreover, by extending the argument in (Feige & Ofek, 2005), we will prove that for any constant C' 0, there exists a constant C3 > 0 such that
Pa(a, S Cayep,
with probability at least - cepppcppppppp Furthermore, we will prove that for any constant C4 > for all ET, Px v) S np eepexp(-Crrpp
with probability least 1 exp(-x(()) Summarizing the bounds altogether using the union bound, get the statement of the lemma.
From now on, we will focus on proving each bound with the probability guarantees.
Bound on Pi (2, y): By Lemma C.5, with constant e > e, we have In 1 (x)(-w(n)) Let {X,) be i.i.d. Bernoulli random variables with mean p. When, [nexp(-npp] (xpp-cnp), the following incqualities hold:
S eex((-enp) with probability least
P
A 2 Cin [nexp(-nāi meep(-cnpp (x.
Σ
27

---

Revisiting Instance-Optimal Cluster Recovery in the Labeled Stochastic Block Model
P
2
Σ
A 2 Cin
[mexp(-nip] S -exx(--en))
(0,w)e x XI:
? eepp -mpp(
X 2 C n
S
P
1=1
exp(A E
exp( exp(-con)) Xi)
< inf
A20
exp (AC1
exppp=epp E [exp(AX;)]
inf
A20
exp (AC1 2)
expl cxup) ((E. - 1)p +1)
inf
X20
exp (AC1
exp nn exp( -enp) 1)p)
inf
X20
exp (1C1%)
exp
(n expl (-Cnp) - -1)
exp (C1 5m
(b)
< (cp(-2Cin).
where (a) and (b) are from the inequality 1 S Et Vo R and the fact that exp(-Cr) o(1) when w(1), respectively. Thus, we have
P
Σ
ALw 2 Cin
I expp(22c1n + exp(-w(n))
(U,w)Er'xC X
S exp(_CCnn)
Note that |r..llll S / for all (v, w) E Therefore, with probability at least exp(-Cin), we have
Pi(x,))
Σ (u,w)EKnne
Σ (w,w)Enne
$ 2
P
A (v,))E(T>xI)nE
Σ
s 201/np.
Bound on P2 y): Using X = 2 \/2 a positive constant C, and Bew == Felyu {(V, w) E L. + awwye 1 ((w, v) E L.) for
all (v, w) I x I, we have
E exp (a (I (EEr,w))IxIxx> A Aen
PP Σ
TyALnaaa -x xTM² 2 C/up
exp (A (Cp x My))
Io (M (exp(AAmuu) + 1)
exp (X Mty))
[ exp (M². %m (exp (X 1))
exp M¹ y))
28

---

Revisiting Instance-Optimal Cluster Recovery in the Labeled Stochastic Block Model
(y exp (M (A3ow + 2 2(A exp (A + x My))
exp
(Etr,))I M (A3w + (AA exp (A (Cppp + x xM
Σ
M ABow do M
exp
(U.m)ETxINUNM
exp
2
Σ
M
ow (Aorr)
-exp (PPC-)))Dp)) (25)
(v.w))Z
(i)
For (i) and (ii), we have following bounds.
(i): This term can be alternatively expressed as follows:
exp
Σ
M MennBoo Ax T M0y
=ex
Σ
M Aoooee
Σ
M Aowee
(26)
(
(N.w)E
(x,w)
exp
Xur Me vw
(27)
(N,w)EC=
Note that [rol
V 2 for all (v, w) L and Σ
((x,))IIII 2ive = 1. Therefore,
Σ a
(u,D]CC
(u,0)EC 1.
It implies
Σ
|awlMll S
1
(M.
Thus,
Σ
Mo Me ww
A/x MM
(NaN)Ec
2 mp Σ
(u.w)EC=
(28)
From (27) and (28), we have
exp
Σ
N Xx TT AM'y
S exp
(5)
29

---

Revisiting Instance-Optimal Cluster Recovery in the Labeled Stochastic Block Model
(ii):
Note that from the definition,
13ew 2 s 2(IrrWw) f(v, w) E C} 2(z {(w, v) E C
holds. Thus, we have
Σ
Mew vw (A )²
(v, L
2 2
Σ
4p
(v, Lon
71
Σ
2
n
Σ
(2(roD1)) {(V, w) E L) + 2(x {(wr,)) v) E E))
2
(v,0)eIXI:0>00
Σ (2io))n))
n
(O,))R
(a)
S n,
where in (a) we used ((,,)e (F (eee)eexzz( 1. Taking exponential of the previous inequalities, have:
Σ
M (N
S <exp(n)
exp
(uww)EIII:ww
Combining the bounds on (i) and (ii) with (25), we have:
3 - C'
P Σ
Z.Abubu x M Cvpp
S exp
2
(o,w)EL
Taking any O2 > 3, we have:
Σ (K.w)EL
ZnAlwbho - M S C2vnp,
with probability at least exp (- C2-3 n).
Bound on Pa y): We extend the proofs in (Feige & Ofek, 2005). For any A,B C I, let we define e(A, B) = EvEA EwEB A be the number positive labels between the nodes in A and the nodes in B and μ(A, B) Blp. u(A, B) is an upper bound of the expected number of labels between A and B. We call the adjacency matrix Af has the bounded degree property with a positive constant e₁ > if for all u In ((,,In)) S cinp holds. Furthermore, we state that the adjacency matrix Af. has the discrepancy property with constants C2 >> 0 and C3 0 if for every A, B c Inr, one of the following holds:
e(A, B)
S C2
(29)
(AA, B)
ce(A, B)
(
n
(ii) e(A, B) log
- cs B log
(30)
((A, B)
By Corollary 2.11 (Feige & Ofek, 2005), if the graph with the adjacency matrix Ar satisfies the discrepancy and the bounded degree properties, there exists a constant C" which depends on Cı, 02, and C3 such that
Pa y) S C' Vnp.
for all x, y E T.
First, we have the following lemma that guarantees the probability that the bounded degree property holds.
30

---

Revisiting Instance-Optimal Cluster Recovery in the Labeled Stochastic Block Model
Lemma E.1. For any constant C > 0, there exists constant Cj such that the bounded degree property of Ap with ej holds with probability at least exp(-Cni).
The proof is given in Appendix E.8.
Next, we have the following lemma that guarantees the probability that the discrepancy property holds.
Lemma E.2. For any C' 0, there positive constants 02 and c3 such that the discrepancy property holds with probability at least exp(-Crpp)
The proof of Lemma E.2 is given in Appendix E.9. Therefore, for any C 0, there exists C1, C22 and C3 such that the bounded degree property and discrepancy property hold with probability at least - exp(-Cnnp))
Bound on P1 y): We have, with constant C' > c², for all x, y E T, with probability at least 1 - exp((-(n)))
Pa v) |x TM Mf)y
S I MFlla
I Mille
I2 (O.w)EK
([nexp(-nii)
/(nexp(-Cnp)pp
mpexp(--Cnpp
where we used Lemma C.5 in (a). This concludes the proof.
E.6. Proof of Lemma 4.3
For all v, w E I such that (v) & oww), there exists a constant C >> 0 that depends on e in (A2) such that with probability at least 1 - ex)(-
|| Mr - Mr
Σ
iETNT 1m1
Σ
Σ
Σ
kK[ iETyNT
Σ (ar exp(-Cimp)) KE(K]
Σ
IV3
Cemp²,
where for (a). we used Lemma C.5 to replace ÿ with p in the cardinality T; and for (b), we used (A2).
E.7. Proof of Lemma 4.4
First, from Lemma 4.2, for any > 0, there exists constants C1, C2 > 0 such that σg 2 Cinp and Ø S C2vnp with probability at least exp(- - -cnp). Therefore, for any e > 0, we have Æ = K with probability at least exp( exp(-cnp(1 (1 + o(1)). From the analysis of the iterative power method in (Halko et al., 2011) (Theorem 9.2 and Theorem 9.1 in (Halko al., 201 I)), for any e > 0, with probability at least exp(-cnpll + o())),
|| Áll2 < (1+ + ||02 113 4[0 91 0k+11
31

---

Revisiting Instance-Optimal Cluster Recovery in the Labeled Stochastic Block Model
where 22 is K K standard Gaussian random matrix, S2 an Ln K K Gaussian random matrix, oK+1 is the K 1-th largest singular value of the matrix Ar. We use the following proposition from (Halko al., 2011).
Proposition E.3 (Proposition A.3. (Halko al., 2011)). Let G be K K standard Gaussian matrix with K 2. For each & 0,
K 2T t
P(I > S 6
From this proposition, for any e > 0, there exists a constant 1 1/n².
>
such that ||0T S Cn with probability at least
Theorem E.4 (Theorem 4.4.5 of (Vershynin, 2018).). Let A be an m x n random matrix whose entries are independent standard Gaussian random variables. For any > we have
|| I C(vn+ +),
with probability at least 1 2exp(-t²) where C > 0 is some constant.
Therefore, for any > 0, there exist constants C1, C2 0 such that
|A- < (1 + ||02|21117 112) aftio # Ø++1
< (1 + Cn nn) 4lclox 11
I C+
with probability at least 1/n.. This concludes the proof.
E.8. Proof of Lemma E.1
Recall that from Lemma 1, I, for each v E II for any > O, we have
(U, I Cnp,
(31)
with probability least exp(- )mp). Also, from Lemma C.S, for any constant C2 et, we have 8 < C2p with probability least 1 - exp(- ex)(-w(n)) The number of trimmed nodes is larger than exp(( exp(-C2np) with probability at least 1 - exp(-w(n)) With these C and C2, by Markov's inequality,
E [>ver {e(n,T) C'mp]]
I [The number of nodes that do not satisfy (31) 2 n exp( exp(pCCap)) s
n nexp(- (C2pp))2p)
E Ever P (e(u, C'npp
n exx( -C2np)
I exp (-(C - C2 C )
Therefore, by the union bound, for any C > 0, there exists a constant C' > O such that any E Inr satisfies e(v, I) S C'np, with probability at least exp(pppppec CCn) - (ep(-w(n)). This concludes the proof.
E.9. Proof of Lemma E.2
Let A and B be subsets of I. Without loss of generality, we assume that |A| < [B]. We prove the lemma by dividing it into two cases.
Case 1: when [B] 2 n/5. By Lemma E.1, for any constant C O, there exists a constant ei such that for all Inr, e(u, D) < cnp holds with probability at least 1 exp( Cnp). Therefore, for any constant > 0, there exists
constant c2 > 0 such that with probability least 1 expeeepriiip for all A, B In I such that B 2 [A],
e(A, S Se(A,InT)
32

---

Revisiting Instance-Optimal Cluster Recovery in the Labeled Stochastic Block Model
Alaap
||
50 561/A|1 BBp
(a) I (2 B);
where in (a) we put 02 2 5ct-
Case 2: when B < n/5. Let we define 71A, 1B) max(n", 02) where 17" is the solution that satisfies 17" (A, B) 1o 03 [] log(n/|B1) As ca B] (og(n/|Bl) > 0, it implies 170 > 1. Furthermore, as x log is an strictly increasing function when x: 2 1. 17 unique for fixed A and B.
When ((A, B) - 7A,, B)P(A, B) and (A,, BB- = c2. the condition (i) is satisfied. When c(A, S ((A, B), B) and (A, B) n7, using the definition of 170, we have
e (A, S 1 p0 A, B)
1
C3 cB|BBlogg log
log
{BB]
From B))(e,A, S logr/, we have
<(A, B) log
e(A, M(A, B)
S |ca|B| log
n
[
Hence, the condition (ii) is satisfied. Therefore, when e( B) S 11, B) (A, B), the discrepancy property holds. We quantifies the probability that e(A, B) S 1A, B)n(A, B) holds for any A, B Inr.
First, by Markov's inequality.
- inf E(exp(Ae( (A((, (A, B))]
(ee B) > B),A,)
X20 exp(An) A, (),(A, B))
< inf (p(exp(A) 1) + 1) 1||A|BB|
A20 exp(An A, (A, B))
(δexp(A) 1) IAIIIIII
S inf
X20 exp(An) A, (A, B))
< inf
X20 exp(An(( A, ()) B))
inf exp (exp(())((A))))) B) An(A,, B)n(A, B))
X20
(a)
exp (-n(A, B) B) (logn(A, B) - -1)),
where in (a), we set À = log (A, B). Next, we compute the probability as follows.
P P(c(A, B) > ((, B) for some A, InT, < 5 |A| }B}
= -P
n/5 U UAncrrmi ((A.B}) 1
n/5
exp (MP, (log ((A, 1))
a
(b)
2/5
ne
exp
(A, () B) (log (A, B) 1))
b
hm
1=1
33

---

Revisiting Instance-Optimal Cluster Recovery in the Labeled Stochastic Block Model
n/5
exp
2b + 2blog (6) (
1/5
exp
4blog
(),, (log (A, -1))
b=1
n/5
exp
((CC +
20 +
+ (C + 2) log n + 4b log
(T)
12 '(AA, () B) (Ao 1))
6=14 1aml
R/5
exp
(og
6)6 log
(5)
n
-nA, () B) (log (Io
1=1 ==1
n/5
exp
(CC+ + (C + 6)b log
n
(A, (),
log 17
2
a=1
n/5
72 (L (1,AA
B
((C' + (C 6)b
log m²
exp
n/5
exp
(- + log)
b=10=
n
where for (a) is from the union bound; for (b), we used b S n/5 and a S b; for (c), we again used b S n/5; for (d), we used the fact that x log(n/a an increasing function in [1, n/c] (Lemma 2.1 in (Feige Ofek, 2005)); for (e), we used (1A, B) 2 02 with sufficiently large constant cz; for (f), we used the fact that æ log x strictly increasing function when 1; (g) stems from the definition of r7" with C3 2 2(C + 6).
From the assumption p = (log n/n), for any C > 0, there exist constants 02 and such that the discrepancy property with constants C2 and c3 holds with probability at least 1 - exp(-Cnpi) This concludes the proof.
E.10. Proof of Corollary 2.1
Let (n) represent the number of misclassified nodes in the initial spectral clustering USC(T) as described in (Gao et al., 2017). Based on the node-wise refinement guarantee provided in the proof of Theorem 4 in (Gao et al., 2017) (specifically, Lemma 17 (Gao et al., 2017)), when K = O()).
sup (pa))0((,.a.))
max TP (p..a) (node is misclassified) VEI
n1
I exp
((11 + o(1))
+ +CP (s S sm),
(32)
K
(0)
where Yn is a positive sequence that satisfies lim In = According to Theorem in (Gao al., 2017), for any
C" >> 0, obtain
1 P P(p.a) S 7n) S 1707 (a-b)²
with an appropriate choice of the sequence 7n in (32). Since 1" assumptions a/b = (11) and a = Ollog n), we obtain
according to (Gao et al., 2017), using the
(a) 2 exp logn) n C
for some constant C >> 0. Therefore, since we can choose any constant C" > O, - ((1++((1)) o(1) nd" K
CP (P (n) I mm)
exp
34

---

Revisiting Instance-Optimal Cluster Recovery in the Labeled Stochastic Block Model
and
nl max (p.xa (node is misclassified) - exp (-(1+ - iEI
sup (0
K
Thus, we obtain
sup (p.
B(a.p) PLMLE (LLLLLL
sup (x,,))
Σ iEI
P (p.a) (node is misclassified)
sup (n.))E((n,a.))
max IP (p.o) (node is misclassified) IEI
nl K
< nexp
((L (11)
This concludes the proof.
F. Numerical Experiments
In this section, we present numerical evaluations of the proposed algorithm. Our experiments are based on the code of (Wang al., 2021), and we consider the three scenarios proposed in (Gao et al., 2017), well as additional scenario. The main focus of our comparison is the IAC algorithm (Algorithm 1) and computationally efficient version of the penalized local maximum likelihood estimation (PLMLE) algorithm (Algorithm 3 in (Gao et al., 2017)). Note that this version of PLMLE does not have performance guarantees, but it still requires (2(n²) floating-pon operations. As shown in Section 4 of (Gao et al., 2017), PLMLE and its simplified version (Algorithm 3) exhibit nearly identical performance in all considered scenarios. all experiments, we consider simple SBMs with
Table 2. Number of misclassified items. IAC and PLMLE indicate Algorithm 1 and Algorithm 3 in (Gao et al., 2017), respectively. Mcans and standard deviations are calculated from the results 100 experiment instances.
Model
Algorithm
Mean
Std
Model
IAC
2.8800
1.5909
PLMLE
2.9700
1.6542
Model 2
IAC
0.0000
0.0000
PLMLE
0.1850
0.4262
Model
IAC
29.4100
4.9789
PLMLE
31.0400
5,1775
Model 4
IAC
45.5600
9.2489
PEMLE
54.7400
10.5329
Model 1: Balanced Symmetric. First, consider the SBM corresponding to the "Balanced case" in (Gao al., 2017). Assume that 2500, K 10, and L 1. We fix the community size be equal Vk [10], [Tp] 250. We set the observation probability p(k, k 1) 0.48 for all & and p(i, k. 1) 0.32 for all * k.
Model 2: Imbalanced. The next SBM corresponds to the "Imbalanced case" in (Gao et al., 2017). We set = 2000, K = 4, and = 1. The sizes of the clusters are heterogenous: |Z| = 200, [Zzl 400, [Za = 600, and [Z4| 800. We set
the observation probability matrix (p(i, k, 1)) as in (Gao et al., 2017):
0.50
0.29
0.35
0.25
0.29
0.45
0.25
0.30
(p(i,k, 1))ka =
(33)
0.35
0.25
0.50
0.35
0.25
0.30
0.35
0.45)
Model 3: Sparse Symmetric. The last experimental setting from (Gao et al., 2017) the sparse and symmetric case. We generate networks with n = 4000, K = 10, and L = 1. Clusters are of equal sizes: Vk E [10], [Igl 400. We set the statistical parameter as p(k: k; 1) = 0.032 for all and p(i, kt 1) 0.005 for all + k.
35

---

Revisiting Instance-Optimal Cluster Recovery in the Labeled Stochastic Block Model
Model 4: Sparse Asymmetric. Lastly, we consider the cluster recovery problem with sparse and asymmetric statistical
parameter. We set 1200, K 4, and I. 1. Clusters of equal sizes: Vk [4], [ 300. We fix the statistical parameter (p(i, K 1))s,a
0.032
0.005
0.008
0.005
0.005
0.028
0.005
0.008
(p(i,); (00,,,1)))a 1))xx
0.008
0.005
0.032
0.005
0.005
0.008
0.005
0.028
The simulations presented in this paper conducted using the following computational environment.
Operating System: macOS Sonoma
Programming Language: MATLAB
Processor: Apple M3 Max
Memory: 128 GB
The average running time of our IAC algorithm is 0.177 + 0.037 seconds, while that of PLMLE is 0.915 + 0.752 seconds for Model 4.
The results of our experiments are summarized in Table The IAC algorithm consistently performs slightly better than Algorithm 3 in (Gao et al., 2017). Figures 1, 2, 3, and 4 display boxplots representing the number misclassified nodes for each Model and method.
7
Number iiscclassieed
5-
4-
PLMLE
Figure I. Number of misclassified nodes for the balanced symmetric case (Model 1). IAC and PLMLE indicate Algorithm and Algorithm (Gao et al., 2017), respectively. The figure plotted with MATLAB boxplot function with outliers (the crosses) for 100 experiment instances.
F.I Experiments with Real-World Dataset
We applied our algorithm to a real-world dataset, the DBLP citation network dataset (Backstrom et al., 2006). In this dataset, the nodes represent researchers. We focused on 246 researchers who have authored 20 or more papers, selected from a corpus of 50,000 papers. The edges represent co-authorship relationships: two researchers are connected if they have co-authored at least one paper. There are 1,118 such co-authorship connections in the network.
36

---

Revisiting Instance-Optimal Cluster Recovery in the Labeled Stochastic Block Model
1.8
Number of misclassified nodes
1.4
1.2
0.6
0.4
0.2
IAC
PLMLE
Figure Number of misclassified nodes for the imbalanced case (Model 2). TAC and PLML.E indicate Algorithm and Algorithm (Gao et al., 2017), respectively. The figure is plotted with MATLAB boxplot function with outliers (the red crosses) for 100 experiment instances.
The researchers in this network were clustered using both IAC and PLMLE, with the number of clusters 8 for simplicity, Network visualizations and statistics (community size distributions and the distributions of publications per author in each community) are shown in Figures 5 and 6, respectively. Interestingly, our IAC algorithm discovered larger communities without excessively small ones, resulting in a more continuous community size distribution.
37

---

Revisiting Instance-Optimal Cluster Recovery in the Labeled Stochastic Block Model
45
40
Number misclass
35
20
15
PLMLE
Figure 3. Number of misclassified nodes for the sparse symmetric case (Model 3). IAC and PLMLE indicate Algorithm and Algorithm 3 (Gao et al., 2017), respectively. The figure is plotted with MATLAB boxplot function with outliers (the red crosses) for 100 experiment instances.
70
Number misciass ind
60
40
30
PLMLE
Figure 4. Number of misclassified nodes for the sparse asymmetric case (Model 4). IAC and PLMLE indicate Algorithm and Algorithm 3 (Gao et al., 2017), respectively. The figure is plotted with MATLAB boxplot function with outliers (the red crosses) for 100 experiment instances.
38

---

Revisiting Instance-Optimal Cluster Recovery in the Labeled Stochastic Block Model
(a) IAC network
(b) PLMLE network
Figure 5. Visualization of clustered networks: (a) IAC, (b) PLMLE.
39

---

Revisiting Instance-Optimal Cluster Recovery in the Labeled Stochastic Block Model
Community Size Dist tautian UACI
str ibution of Pub libiication per Author in Each Communitty (IAC)
180
100
300
Numbhrr Autters
200
40-
100
8
Community
Communiy ID
(a) network statisties
(PUNLE)
Distribution Author Community (PLMLE)
80
300
Humber of Eppers
(b) PLMLE network statistics
Figure 6. Statistics of the clustered networks: (a) TAC, (b) PLMLE.
40


Reviews:
[{"review_id": "91xuGCIk0l", "reviewer": "Reviewer_SiLN", "summary": "This paper provides a detailed algorithm for clustering under the LSBM model, and theoretically shows that it achieves the known asymptotic lower bound on the number of miss-classifications (YP2016). Furthermore, the algorithm does not need to know the LSBM parameters, essentially showing that the bound in (YP2016) is min-max over the LSBM parameters. The algorithm is achieved in two stages, where in the first stage a refined version of the spectral clustering method is applied and an estimate of the hyper-parameters is achieved. In the second stage, maximum likelihood principle is applied cyclically to the nodes.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your positive feedback and for carefully reading our draft.\n\n> The authors could move some of the discussion to the supplementary material and instead present the numerical studies in the main body of the paper.\n\nThank you for the suggestion. We will take this into consideration when revising the manuscript.", "claims_and_evidence": "The claims of the paper are mainly theoretical and are rigorously proven. Some empirical evidence is provided in the supplement that confirms the optimality of the proposed algorithm.", "methods_and_evaluation_criteria": "The method provably provides exact bounds for clustering under SBML. It naturally makes sense!", "theoretical_claims": "I did not check the details of the proofs, but the steps generally follow standard arguments and should be correct.", "experimental_designs_or_analyses": "Experimentation is not the main purpose and approach of this paper.", "relation_to_broader_scientific_literature": "The paper establishes the sharpness of the error bounds for LSBM clustering. This is a significant result with potential application in similar problems related to graphs.", "essential_references_not_discussed": "No undiscussed reference.", "other_strengths_and_weaknesses": "Weakness: I cannot think of any remarkable weakness, but the steps used in the paper are heavily borrowed from other works. The paper is similar even in presentation to (YP2016) and the idea of refinement of the clusters have been frequently discussed in the past, e.g. in K-means clustering, although I am not aware of any paper in the context of LSBMs. The bounds are not also new, but establishing their sharpness is certainly important.", "other_comments_or_suggestions": "To me, the section on the related works is unnecessarily long and detailed. The authors could move some of the discussion to the supplementary material and instead present the numerical studies in the main body of the paper.", "questions_for_authors": "No major question to the authors.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "lpL8TRD9Te", "reviewer": "Reviewer_a7JY", "summary": "This paper considers the problem of community detection in the Labeled SBM, a generalization of the standard SBM in which each edge is associated with one of L+1 labels (where the zero label is most frequent). The authors study the case of a growing number of communities and propose an algorithm for achieving the minimal misclassification rate, without knowledge of the model parameters. The algorithm consists of two phases: the first performs spectral clustering to identify a preliminary classification and estimate the model parameters, while the second phase refines the initial labels by mimicking the MLE.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your positive feedback and for carefully reading our draft. \n\n> it would be nice to see an empirical validation of the threshold in Theorem 1.2.\n\nWe will include a comparison plot of the empirical error rates and the lower bound by varying $n$ in the appendix of the paper.\n\n> Dreveton, Fernandes, and Figueiredo from NeurIPS 2023. This paper develops very general impossibility results for SBM-type problems.\n\nThank you for pointing out this literature. This paper derives the necessary conditions for exact recovery with high probability for (possibly non-homogeneous) node-attributed SBMs. Although they provide the Bregman hard clustering algorithm, they do not derive a performance guarantee—that is, the sufficient condition for the existence of the optimal algorithm. Our result provides a guarantee for the IAC algorithm in expectation, and importantly, we have revealed conditions not only for exact recovery but also for the expected number of misclassified nodes to be less than $s$, for any number $s = o(n)$. We will cite their work and discuss it in the revised manuscript.\n\n> There is a grammar issue in the last line of the first paragraph of Section 2.1.\n\nThank you for pointing this out. We will fix it.", "claims_and_evidence": "Under Assumptions (1), (2), and (3), Theorem 1.2 bounds the misclassification rate. This claim is tight (up to Assumption (3)) in light of Theorem 1.1, which is cited from Yun & Proutiere (2016). The evidence is an algorithm achieving the expected misclassification rate.", "methods_and_evaluation_criteria": "Yes, though it would be nice to see an empirical validation of the threshold in Theorem 1.2.", "theoretical_claims": "I checked the outline in the main text, which follows reasonable steps. It makes sense to me that the misclassification rate is driven by the number of vertices that are not in the set H (defined in Section 4.2), since the main condition (H2) is related to the failure of the MLE.", "experimental_designs_or_analyses": "The supplementary material contains synthetic data experiments, showing that the new method performs similarly to the method of Gao et al (2011). It would be nice to see experimental validation of Theorem 1.2.", "relation_to_broader_scientific_literature": "There is a good comparison made to the closest papers, namely that of Gao et al (2017) and Yun and Proutiere (2016). The results are significant among the literature on misclassification rates for the SBM.", "essential_references_not_discussed": "“Exact recovery and Bregman hard clustering of node-attributed Stochastic Block Model” by Dreveton, Fernandes, and Figueiredo from NeurIPS 2023. \nThis paper develops very general impossibility results for SBM-type problems.", "other_strengths_and_weaknesses": "The paper is well-written.", "other_comments_or_suggestions": "There is a grammar issue in the last line of the first paragraph of Section 2.1.", "questions_for_authors": "N/A", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "TIaqMuJNHx", "reviewer": "Reviewer_sjJq", "summary": "The authors propose a new tractable algorithm for cluster recovery in the labeled stochastic block model. An upper bound for the asymptotic error rate is derived and is shown to match known lower bounds.\n\n## Update after rebuttal\nI maintain my score, thank you.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your positive feedback and for carefully reading our draft. Please let us know if you have any further questions.", "claims_and_evidence": "The proposed algorithm follows a popular two-phase approach (spectral clustering plus maximum likelihood) and is therefore believable. I did not check the proofs but the arguments as well as the results seem reasonable.", "methods_and_evaluation_criteria": "See \"Claims and evidence\" above.", "theoretical_claims": "See \"Claims and evidence\" above.", "experimental_designs_or_analyses": "Some empirical evaluation is given in the appendix. They seem adequate for this kind of work.", "relation_to_broader_scientific_literature": "The work should make valuable contribution to the literature on community detection and clustering in general.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "N/A", "other_comments_or_suggestions": "N/A", "questions_for_authors": "N/A", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Ms0jHPFkEb", "reviewer": "Reviewer_JfS5", "summary": "The authors study the labeled stochastic block model, which is similar to the regular SBM, but each edge is additionally assigned one label from a candidate set. 0 corresponds to no edge existing, and the authors study the sparse regime where the probability of a label not being 0 is small ($O(\\log n / n)$). \nIn this regime, the authors show that given some assumptions on the LSBM concerning homogeneity of the labels, cluster separation and the (non)existence of labels that are too sparse, there exists an instance optimal algorithm, meaning for any LBSM satisfying these assumptions the algorithm will misclassify a sublinear amount of vertices. This clustering algorithm matches a lower bound from the literature.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your positive feedback and for carefully reading our draft. \n\n> Additional data such as the running time would have been interesting to get a fuller picture on the practical properties of the algorithms.\n\nThank you for this suggestion. We have conducted additional experiments to measure the running times of the algorithms. For Model 4, the average running time of our IAC algorithm is 0.177 ± 0.037 seconds, while that of PMLE is 0.915 ± 0.752 seconds.\nIn the next revision, we will include these results, along with further scaling evaluations (by varying the model parameters and the sample size $n$), in the appendix of the paper.\n\n> Whether these results have implications for clustering on graphs in real-world instances is not entirely clear to me.\n\nWe have applied our algorithm to a real-world dataset, the DBLP citation network dataset. In this dataset, the nodes represent researchers. We focused on 246 researchers who have authored 20 or more papers, selected from a corpus of 50,000 papers. The edges (connections) represent co-authorship relationships. There are 1,118 co-authorship connections, where two researchers are connected if they have co-authored one or more papers. We clustered the researchers in this network using both IAC and PLMLE. We set the number of clusters to 8 for simplicity. The results are available at the following link: https://anonymous.4open.science/r/Rebuttal_ICML_8618-9FFF.\nInterestingly, our IAC algorithm found larger communities without excessively small ones, resulting in a more continuous community size distribution. We will include the results and the discussion in the next revision.", "claims_and_evidence": "I can not judge the evidence as all proofs are in the appendix and I did not have time to look at them in detail.", "methods_and_evaluation_criteria": "There are some experiments in the appendix, the authors compare their own algorithm to one algorithm from the literature over a benchmark dataset for various regimes of the SBM. The labeled SBM is not considered, likely due to the algorithm of Gao being for the regular SBM.\n\nThe results are evaluated based on the number of misclassified nodes.", "theoretical_claims": "I did not check the proofs of the theoretical claims.", "experimental_designs_or_analyses": "The experiments are performed for different regimes of the SBM, with both algorithms performing similar in the first three settings and the algorithm IAC performing better in the sparse asymmetric setting. IAC is also better in the first three settings, but the differences are very small. Additional data such as the running time would have been interesting to get a fuller picture on the practical properties of the algorithms.", "relation_to_broader_scientific_literature": "The SBM is a standard model for studying the theoretical limitations of clustering algorithms. I am not familiar with the labelled SBM and wish the authors would have motivated the uses of the model a bit more. The results may inform researchers in other areas of clustering about the theoretical limitations of algorithms, but whether these results have implications for clustering on graphs in real-world instances is not entirely clear to me.", "essential_references_not_discussed": "Not aware of any.", "other_strengths_and_weaknesses": "None", "other_comments_or_suggestions": "None", "questions_for_authors": "None", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The stochastic block model (SBM) is a natural random-graph model where similar nodes tend to cluster together. The authors study a labeled SBM, where in addition, each edge may be assigned a special label 0 (corresponding to no edge existing); the sparse regime where the probability of a label not being 0 is suitably vanishingly small---O((log n)/n), is considered. In this regime, the authors show that given some assumptions on the LSBM concerning homogeneity of the labels, cluster separation, and the (non)existence of labels that are too sparse, there exists an “instance-optimal algorithm” that will misclassify o(n) of the vertices: necessary and sufficient conditions are developed under which the expected number of misclassified nodes is less than s, for any parameter s = o(n). This algorithm matches a lower bound from the literature. The paper appears to make good progress on a fundamental random-clustering model.
Decision: Accept (poster)