Instance-Optimal Cluster Recovery in the Labeled Stochastic Block Model
Kaito Ariu Alexandre Proutiere Se-Young Yun
We consider the problem of recovering hidden communities in the Labeled
Stochastic Block Model (LSBM) with a finite number of clusters, where cluster
sizes grow linearly with the total number $n$ of items. In the LSBM, a label is
(independently) observed for each pair of items. Our objective is to devise an
efficient algorithm that recovers clusters using the observed labels. To this
end, we revisit instance-specific lower bounds on the expected number of
misclassified items satisfied by any clustering algorithm. We present
Instance-Adaptive Clustering (IAC), the first algorithm whose performance
matches these lower bounds both in expectation and with high probability. IAC
consists of a one-time spectral clustering algorithm followed by an iterative
likelihood-based cluster assignment improvement. This approach is based on the
instance-specific lower bound and does not require any 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))$. We illustrate the effectiveness of our approach through
numerical experiments.