{"id":8540,"date":"2025-11-21T07:02:26","date_gmt":"2025-11-21T07:02:26","guid":{"rendered":"https:\/\/mailitics.com\/index.php\/2025\/11\/21\/2511-16613\/"},"modified":"2025-11-21T07:02:26","modified_gmt":"2025-11-21T07:02:26","slug":"2511-16613","status":"publish","type":"post","link":"https:\/\/mailitics.com\/index.php\/2025\/11\/21\/2511-16613\/","title":{"rendered":"Rate-optimal community detection near the KS threshold via node-robust algorithms"},"content":{"rendered":"<p>    Rate-optimal community detection near the KS threshold via node-robust algorithms<br \/>\n \t<BR><br \/>\n<BR><\/BR><br \/>\n    <!-- no image --><br \/>\n \t<BR><br \/>\n<BR><\/BR><\/p>\n<div>arXiv:2511.16613v1 Announce Type: new<br \/>\nAbstract: 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.<br \/>\n  Our main result is a polynomial-time algorithm that achieves the minimax-optimal misclassification rate<br \/>\n  begin{equation*}<br \/>\n  exp Bigl(-bigl(1 pm o(1)bigr) tfrac{C}{k}Bigr),<br \/>\n  quad text{where } C = (sqrt{pn} &#8211; sqrt{qn})^2,<br \/>\n  end{equation*}<br \/>\n  whenever $C ge K,k^2,log k$ for some universal constant $K$, matching the Kesten&#8211;Stigum (KS) threshold up to a $log k$ factor.<br \/>\n  Notably, this rate holds even when an adversary corrupts an $eta le expbigl(- (1 pm o(1)) tfrac{C}{k}bigr)$ fraction of the nodes.<br \/>\n  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].<br \/>\n  In the node-robust setting, the best known algorithm requires the substantially stronger condition $C ge K k^{102}$ [LM22].<br \/>\n  Our results close this gap by providing the first polynomial-time algorithm that achieves the minimax rate near the KS threshold in both settings.<br \/>\n  Our work has two key technical contributions:<br \/>\n  (1) we robustify majority voting via the Sum-of-Squares framework,<br \/>\n  (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.<\/div>\n<p> \t<BR><br \/>\n <BR><\/BR><br \/>\n    Jingqiu Ding, Yiding Hua, Kasper Lindberg, David Steurer, Aleksandr Storozhenko<br \/>\n \t<BR><br \/>\n<BR><\/BR><br \/>\n<a href=\"https:\/\/arxiv.org\/abs\/2511.16613\">Go to original source<\/a><br \/>\n \t<BR><br \/>\n <BR><\/BR><\/p>\n","protected":false},"excerpt":{"rendered":"<p>Rate-optimal community detection near the KS threshold via node-robust algorithms arXiv:2511.16613v1 Announce Type: new 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 [&hellip;]<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[62,1190,413,113,112],"tags":[4261,1933,4260],"class_list":["post-8540","post","type-post","status-publish","format-standard","hentry","category-aimldsaimlds","category-cs-cc","category-cs-ds","category-cs-lg","category-stat-ml","tag-ks","tag-rate","tag-via"],"_links":{"self":[{"href":"https:\/\/mailitics.com\/index.php\/wp-json\/wp\/v2\/posts\/8540"}],"collection":[{"href":"https:\/\/mailitics.com\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/mailitics.com\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/mailitics.com\/index.php\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/mailitics.com\/index.php\/wp-json\/wp\/v2\/comments?post=8540"}],"version-history":[{"count":0,"href":"https:\/\/mailitics.com\/index.php\/wp-json\/wp\/v2\/posts\/8540\/revisions"}],"wp:attachment":[{"href":"https:\/\/mailitics.com\/index.php\/wp-json\/wp\/v2\/media?parent=8540"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/mailitics.com\/index.php\/wp-json\/wp\/v2\/categories?post=8540"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/mailitics.com\/index.php\/wp-json\/wp\/v2\/tags?post=8540"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}