An Optimal Clustering Algorithm for the Labeled Stochastic Block Model

This paper considers the clustering problem in the Labeled Stochastic Block Model (LSBM) from the observations of labels. For this model, we assume that the cluster size increases linearly with the number of nodes $n$. Our goal is to develop an efficient algorithm to identify the clusters based on the observed labels. We reexamine instance-specific lower bounds on the expected number of misclassified items. These bounds must be satisfied by any clustering algorithm. We propose Instance-Adaptive Clustering (IAC), the first algorithm that matches the lower bounds in expectation. IAC combines a one-time spectral clustering method with an iterative likelihood-based cluster assignment refinement procedure. This technique relies on the instance-specific lower bound and does not necessitate any model parameters, including the number of clusters. IAC retains an overall computational complexity of $\mathcal{O}(n \text{polylog}(n))$. We demonstrate the efficacy of our approach through numerical experiments.