{"ID":2839204,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2511.16613","arxiv_id":"2511.16613","title":"Rate-optimal community detection near the KS threshold via node-robust algorithms","abstract":"We study community detection in the \\emph{symmetric $k$-stochastic block model}, where $n$ nodes are evenly partitioned into $k$ clusters with intra- and inter-cluster connection probabilities $p$ and $q$, respectively. Our main result is a polynomial-time algorithm that achieves the minimax-optimal misclassification rate \\begin{equation*} \\exp \\Bigl(-\\bigl(1 \\pm o(1)\\bigr) \\tfrac{C}{k}\\Bigr), \\quad \\text{where } C = (\\sqrt{pn} - \\sqrt{qn})^2, \\end{equation*} whenever $C \\ge K\\,k^2\\,\\log k$ for some universal constant $K$, matching the Kesten--Stigum (KS) threshold up to a $\\log k$ factor. Notably, this rate holds even when an adversary corrupts an $η\\le \\exp\\bigl(- (1 \\pm o(1)) \\tfrac{C}{k}\\bigr)$ fraction of the nodes. To the best of our knowledge, the minimax rate was previously only attainable either via computationally inefficient procedures [ZZ15] or via polynomial-time algorithms that require strictly stronger assumptions such as $C \\ge K k^3$ [GMZZ17]. In the node-robust setting, the best known algorithm requires the substantially stronger condition $C \\ge K k^{102}$ [LM22]. Our results close this gap by providing the first polynomial-time algorithm that achieves the minimax rate near the KS threshold in both settings. Our work has two key technical contributions: (1) we robustify majority voting via the Sum-of-Squares framework, (2) we develop a novel graph bisection algorithm via robust majority voting, which allows us to significantly improve the misclassification rate to $1/\\mathrm{poly}(k)$ for the initial estimation near the KS threshold.","short_abstract":"We study community detection in the \\emph{symmetric $k$-stochastic block model}, where $n$ nodes are evenly partitioned into $k$ clusters with intra- and inter-cluster connection probabilities $p$ and $q$, respectively. Our main result is a polynomial-time algorithm that achieves the minimax-optimal misclassification r...","url_abs":"https://arxiv.org/abs/2511.16613","url_pdf":"https://arxiv.org/pdf/2511.16613v1","authors":"[\"Jingqiu Ding\",\"Yiding Hua\",\"Kasper Lindberg\",\"David Steurer\",\"Aleksandr Storozhenko\"]","published":"2025-11-20T18:11:01Z","proceeding":"stat.ML","tasks":"[\"stat.ML\",\"cs.CC\",\"cs.DS\",\"cs.LG\"]","methods":"[]","has_code":false}