Optimal Cluster Recovery in the Labeled Stochastic Block Model

• The paper asks when an LSBM clustering algorithm can achieve at most any prescribed s=o(n) misclassified items, extending prior recovery objectives.Source: §1 · p. 2
• The LSBM assigns independently sampled labels between cluster pairs according to distributions p(i,j), with cluster proportions α fixed as n grows.Source: §1 · pp. 1–2
• The divergence D(α,p) summarizes separation among label distributions and underlies the paper’s recovery conditions.Source: §1 · pp. 2–3
• Any algorithm achieving fewer than s average errors must satisfy the lower-bound condition of Theorem 1, whose bound was previously unknown even for the SBM [2].Source: §1 · p. 3
• Under (A3), the Spectral Partition algorithm misclassifies at most s items with high probability whenever the fundamental condition holds.Source: §1 · p. 3
• The optimal error scale is n exp(−nD(α,p)(1 + o(1))), achieved by a polynomial-time algorithm requiring O(n^2 p̄ log(n)) operations; exact recovery also has a necessary and sufficient condition.Source: §1 · p. 3

2.1 Related work

• Prior SBM work addresses detectability, asymptotically accurate recovery, exact recovery, and optimal recovery rates, whereas this paper targets the minimal errors for general LSBMs.Source: §2.1 · p. 4
• For asymptotically accurate recovery, prior SBM conditions require nD(α,p)=ω(1), while the present results characterize the achievable misclassification count more precisely and for generic LSBMs.Source: §2.1 · p. 4
• The paper’s optimal-recovery result is model-specific, applies to generic LSBMs, and improves prior algorithmic complexity from O(n^3 log(n)) to O(n^2 p̄ log(n)).Source: §2.1 · p. 5

2.2 Applications

• In the hidden-community application, the minimum errors scale as n exp(−h(α,a,b)f(n)(1 + o(1))), and exact recovery for f(n)=log(n) requires h(α,a,b)≥1.Source: §2.2 · pp. 5–6
• For sampled dense binary networks, the error exponent becomes l(δ,a,b), with exact recovery under f(n)=log(n) when l(α,a+,a−,b+,b−)≥1.Source: §2.2 · p. 6
• Signed networks and binary SBMs likewise yield explicit exponential error rates, including m(α,a+,a−,b+,b−) and g(α1,a,b), with exact-recovery thresholds at exponent at least 1.Source: §2.2 · pp. 5–6

Change of measures through coupling

• The change-of-measure proof constructs a perturbed model Ψ and relates the true-model error E[επ(n)] to the expected log-likelihood ratio Q under Ψ.The argument shows, roughly, that log(n/EΦ[επ(n)]) must be smaller than EΨ[Q].Source: §3 · p. 6

Coupling and the perturbed model Ψ

• Ψ preserves the random clusters and all labels not incident to a selected item v⋆, while replacing labels incident to v⋆ with probabilities q.The selected pair of clusters minimizes the divergence DL+(p(i),p(j)).Source: §3 · pp. 6–7

Likelihood-ratio analysis

• The likelihood ratio Q is defined from the observed labels under PΦ and PΨ, providing the statistic used to compare the two models.The proof then bounds the probability of small Q in terms of the expected number of misclassified items.Source: §3 · p. 7

Analysis of Q

• The analysis approximates EΨ[Q] by nD(α, p) and shows its variance is O(n p̄), which is negligible relative to nD(α, p) under the stated assumptions.This concentration controls the likelihood-ratio fluctuations needed for the lower bound.Source: §3 · p. 7

Fundamental lower bound

• Consequently, any algorithm achieving E[επ(n)]≤s must satisfy the theorem’s asymptotic necessary condition derived from the likelihood-ratio bounds.The condition applies to arbitrary clustering algorithms.Source: §3 · p. 7

4 The Spectral Partition Algorithm and its Optimality

• When n p̄=ω(1), spectral initialization estimates the correct number of clusters and produces asymptotically accurate cluster estimates with high probability.The rank is estimated by singular-value thresholding, using an iterative power method rather than direct SVD.Source: §4 · pp. 8–9
• The first spectral stage adapts SBM algorithms to multiple labels and unknown K, whereas the iterative parameter-estimation stage is the paper’s novel component.The first stage is adapted from prior SBM methods, while the second stage performs successive likelihood-based improvements.Source: §4 · p. 8
• The SP algorithm’s novel second stage estimates model parameters from the initial clusters and iteratively improves assignments using log-likelihoods.It runs ⌊log(n)⌋ improvement iterations and is critical to optimality.Source: §4 · p. 8
• The spectral approximation has Frobenius error O(n p̄) with high probability, yielding O(1/p̄) misclassified items for the initial two-step procedure.This establishes the initialization scale before successive cluster improvements.Source: §4 · p. 8
• The refinement analysis isolates a large good set H satisfying degree, likelihood, and external-connectivity conditions, then shows only items outside H remain misclassified after log(n) iterations.The excluded set is at most s with high probability under the theorem’s divergence condition.Source: §4 · p. 9

A The SP Algorithm

• The first stage forms a random-weight matrix from observed labels, trims high-degree items, and applies spectral decomposition to initialize the clusters.The construction uses A = Σℓ wℓAℓ and removes items with unusually many observed labels before decomposition.Source: §4 · pp. 7–8, A The SP Algorithm · p. 12

B.1 Proof of Claim 4

• The convex objective is minimized in the regime where each candidate label probability has vanishing total mass across labels ℓ≥1.The objective diverges when that mass is Ω(1), whereas matching the relevant label probabilities gives a smaller asymptotic value.Source: §B.1 · p. 13
• Using log(1+x)=x for x=o(1), the proof evaluates the minimum objective and obtains its asymptotic equivalent.The resulting expression is the quantity used in the divergence analysis.Source: §B.1 · p. 14

B.2 Proof of Claim 5

• Using p(i, i, ℓ) = p(ℓ) and p(i, j, ℓ) = q(ℓ) from Claim 4, the proof concludes the claim from (8) and (9).Source: §B.2 · pp. 14–15

B.3 Other properties

• For the pair (i⋆,j⋆) minimizing DL+(p(i),p(j)), Lemma 7 guarantees a distribution q with the required divergence comparison properties.The proof obtains q by contradiction and continuity of the KL divergence.Source: §B.3 · p. 15
• The same minimizer construction is used to derive the divergence expression needed for the theorem’s asymptotic analysis.The calculation relies on the sparse-probability approximation log(1+x)=x(1+o(1)).Source: §B.3 · p. 16

C Proof of Theorem 1

• The proof couples the true model Φ to a perturbed model Ψ that changes only labels incident to a selected node, enabling a change-of-measure lower bound.Under Ψ, clusters remain unchanged, while labels on edges incident to v⋆ are generated from q rather than p.Source: C Proof of Theorem 1 · p. 17
• A pseudo-log-likelihood ratio Q connects the clustering error E[ε_π(n)] under Φ to the probability of Q under Ψ.The argument uses node exchangeability and indistinguishability of alternative cluster assignments to derive the generic relationship.Source: C Proof of Theorem 1 · pp. 17–18
• The resulting inequality supplies a necessary condition for any algorithm with E[ε_π(n)]≤s, yielding the theorem’s lower bound on expected misclassified items.The condition follows by combining the generic relationship with the moment bounds and choosing f(n) according to E[ε_π(n)].Source: C Proof of Theorem 1 · pp. 18–20
• The likelihood-ratio analysis evaluates E_Ψ[Q] and its variance, with the mean approximated by nD(α,p) and the variance controlled using independent labels.The approximation exploits that v⋆ is small with high probability; the conditional second-moment bound is O(n p̄).Source: C Proof of Theorem 1 · pp. 19–20

D Performance of the SP Algorithm – Proof of Theorem 2

• The SP proof begins by controlling item degrees and spectral noise, then analyzes the algorithm’s initial clustering and its log(n) improvement iterations.The preliminary lemmas bound degree concentration and the norm of the noise matrices before the algorithmic performance analysis.Source: D Performance of the SP Algorithm –… · pp. 20–21, §D.1 · p. 21

D.2 Part 1 of the SP algorithm – Proof of Theorem 6

• The iterative power method produces a low-rank approximation whose embedded item vectors can be compared with cluster centers to bound misclassification.The proof relates distances between estimated embeddings to distances between rows of the approximated matrix.Source: §D.2 · pp. 22–24
• Degree concentration and spectral-noise bounds provide the high-probability controls needed for the first SP stage.The proof uses concentration of item degrees and an operator-norm bound for the random noise matrices.Source: §D.2 · p. 23
• The construction of sets I_k and Q_v establishes that correctly embedded items associate with one cluster, while misclassified items must violate a separation condition.These set relations imply that the estimated number of clusters equals K and yield the final classification bound.Source: §D.2 · p. 24

D.3 Proof of Theorem 2

• The set H enforces degree regularity, correct log-likelihood classification, and limited connectivity to items outside H.These properties are labeled (H1), (H2), and (H3), respectively.Source: §D.3 · p. 25
• If D(α,p) satisfies the theorem’s condition, then |V\H|≤s with high probability, so only at most s items lie outside the controlled set.The proof establishes this through a bound involving log(n/s) and the exceptional-set construction.Source: §D.3 · p. 25
• Each refinement iteration contracts the relevant error quantity, and after log(n) iterations no item in H is misclassified with high probability.Because n p̄=ω(1), the contraction factor is sufficiently small for the stated iteration count.Source: §D.3 · p. 25
• With high probability, no item in H is misclassified, so the total number of misclassified items is at most |V \ H|, which is bounded by s.Source: §D.3 · p. 25

D.3.1 Proof of Proposition 13 – Size of V \ H

• The H1 and H2 analyses connect regular item degrees with successful likelihood-based classification, completing the ingredients needed to control the exceptional set.The proof establishes that satisfying H1 implies H2 with high probability and evaluates the corresponding event using Lemma 12.Source: §D.3.1 · pp. 25–26
• The proof first bounds items violating H1 or H2, then uses Lemma 15 to show that |V\H|≤s with high probability.Lemma 15 applies when the number violating H1 or H2 is below s/3.Source: §D.3.1 · p. 26
• With high probability, no subset of s items has at least s log(n p̄)^2 internal observed-label incidences.This sparse-subset claim is established using Markov bounds and a union bound over subsets.Source: §D.3.1 · p. 27
• The construction starts from H1/H2 violators and repeatedly adds items having more than 2 log(n p̄)^2 connections to the current set.If more than s/2 items violated H3, the resulting set would contradict the sparse-subset claim.Source: §D.3.1 · p. 27

D.3.2 Proof of Proposition 14

• At each improvement step, items move to the cluster maximizing the SP algorithm’s log-likelihood.Source: §D.3.2 · p. 28
• The proof establishes uniform concentration of labeled edge counts around their expectations for all candidate partitions.The deviation is bounded by n log(n p̄)^2 with high probability.Source: §D.3.2 · p. 29
• Estimated label probabilities satisfy |p̂(j,i,ℓ) − p(j,i,ℓ)| = O(log(n p̄)^2/n) uniformly over cluster pairs and labels.Source: §D.3.2 · p. 29
• The proof uses trimming to control high-degree items, defining a trimmed matrix after removing rows and columns outside the bounded-degree set.Source: §D.3.2 · pp. 29–30
• The analysis tracks misclassified items across improvement iterations and bounds the next error set using current errors and concentration terms.The resulting bound includes terms proportional to |E(t)||E(t+1)| n p̄ log(n p̄) and |E(t+1)| log(n p̄).Source: §D.3.2 · p. 30

E Proof of Theorem 3

• When the exact-recovery condition holds, the SP algorithm finds the clusters exactly with high probability.The positive result is obtained by applying Theorem 2 with s = 1.Source: E Proof of Theorem 3 · p. 31
• When the corresponding condition fails, MAP estimation fails to recover the exact clusters with high probability.The proof constructs a hard-to-discriminate pair of clusters and shows that a misleading node exists with high probability.Source: E Proof of Theorem 3 · pp. 31–33
• The proof analyzes the node-level label-count matrix through a large-deviation lemma under cluster-size and Θ(n p̄) label-count conditions.Source: E Proof of Theorem 3 · p. 31
• The discriminability exponent satisfies log P{e(v)=x} ≥ −nD(1+o(1)) when v belongs to cluster i and D = Ω(p̄).Source: E Proof of Theorem 3 · p. 31
• The negative result applies to every clustering algorithm because MAP has access to the full model parameters and still incurs error.A local reassignment of one node yields a partition that MAP does not select when the misleading event occurs.Source: E Proof of Theorem 3 · pp. 31, 33