論文の概要: Rate-optimal community detection near the KS threshold via node-robust algorithms

• arxiv url: http://arxiv.org/abs/2511.16613v1
• Date: Thu, 20 Nov 2025 18:11:01 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-11-21 17:08:52.781253
• Title: Rate-optimal community detection near the KS threshold via node-robust algorithms
• Title（参考訳）: ノードロバストアルゴリズムによるKSしきい値近傍の速度-最適コミュニティ検出
• Authors: Jingqiu Ding, Yiding Hua, Kasper Lindberg, David Steurer, Aleksandr Storozhenko,
• Abstract要約: 我々は,n$ノードを,クラスタ内およびクラスタ間接続を伴う$k$に均等に分割したEmphsymmetric $k$stochasticブロックモデルを用いて,コミュニティ検出について検討した。 我々の主な成果は、ロバストな多数決投票による新しいグラフ分割アルゴリズムであり、KS閾値付近での初期推定を行うために、誤分類率を1/mathrmpoly(k)に大幅に向上させることができる。
• 参考スコア（独自算出の注目度）: 43.490963168751364
• License: http://creativecommons.org/licenses/by/4.0/
• 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.
• Abstract（参考訳）: そこでは,$n$ノードを,クラスタ内およびクラスタ間接続確率が$p$と$q$で,それぞれ$k$クラスタに均等に分割する。 我々の主な結果は多項式時間アルゴリズムであり、最小値-最適誤分類率 \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*} if $C \ge K\,k^2\,\log k$ for some universal constant $K$, matching the Kesten-Stigum (KS) threshold to a $\log k$ factor。 この速度は、敵がノードの分数$η\le \exp\bigl(- (1 \pm o(1)) \tfrac{C}{k}\bigr)$ を破損しても保たれる。 我々の知る限り、ミニマックスレートは計算的に非効率な手順 [ZZ15] や、$C \ge K k^3$ [GMZZ17] のようなより強い仮定を必要とする多項式時間アルゴリズムによってしか達成できなかった。 ノード・ロバスト設定では、最もよく知られたアルゴリズムは、より強い条件である$C \ge K k^{102}$[LM22]を必要とする。 両設定のKS閾値付近で最小値を達成する最初の多項式時間アルゴリズムを提供することで,このギャップを埋めることができた。 我々は,(1) サム・オブ・スクエアズ(Sum-of-Squares) フレームワークによる多数決の堅牢化,(2) 頑健な多数決投票による新しいグラフ分割アルゴリズムを開発し,KS 閾値付近での初期推定値として 1/\mathrm{poly}(k)$ の誤分類率を大幅に向上させることができる。

関連論文リスト

• Near-Optimal Clustering in Mixture of Markov Chains [74.3828414695655]
  我々は、長さ$H$の軌跡を、大きさ$S$の有限状態空間上の未知のエルゴードマルコフ鎖の1つによって生成される、$T$ trajectories of length $H$の問題を研究する。 我々は、連鎖の遷移核間の重み付きKL分散によって支配されるクラスタリングエラー率に基づいて、インスタンス依存で高い確率の低い境界を導出する。 次に,新しい2段階クラスタリングアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2025-06-02T05:10:40Z)
• Improved Robust Estimation for Erdős-Rényi Graphs: The Sparse Regime and Optimal Breakdown Point [3.793609515750114]
  我々は、ErdHos-R'enyiランダムグラフのエッジ密度を強く推定する問題を、$G(n, dcirc/n)$で検討する。 我々のアルゴリズムは2乗の総和階層に基づいている。
  論文  参考訳（メタデータ） (2025-03-05T21:45:17Z)
• A Scalable Algorithm for Individually Fair K-means Clustering [77.93955971520549]
  Jung et al. と Mahabadi et al が導入した個別フェア (p$, $k$) クラスタリング問題に対するスケーラブルなアルゴリズムを提案する。 クラスタリングは、各$xin P$に対して$delta(x)$ of $x$の範囲内で中心となる場合、個別にフェアと呼ばれる。 我々は,従来よりもアルゴリズムがはるかに高速であるだけでなく,低コストのソリューションを生み出すことを実証的に示す。
  論文  参考訳（メタデータ） (2024-02-09T19:01:48Z)
• Do you know what q-means? [42.96240569413475]
  古典的な$varepsilon$-$k$-meansアルゴリズムは、ロイドのアルゴリズムの1つの反復の近似バージョンを時間的複雑さで実行する。 また,時間的複雑さを考慮した$q$-means量子アルゴリズムも提案する。
  論文  参考訳（メタデータ） (2023-08-18T17:52:12Z)
• Minimax Rates for Robust Community Detection [19.229475414802213]
  逆ノードの破損を伴うブロックモデルにおけるコミュニティ検出の問題点について検討する。 我々の主な結果は、$epsilon$-fraction of corruption and unbounded error $O(epsilon) + e-fracC2 (1 pm o(1))$ where $C = (sqrta - sqrtb)2$ is the signal-to-noise ratio。 アルゴリズムがさらに機能するという意味では、我々のアルゴリズムは2倍に損なわれていることを示す。
  論文  参考訳（メタデータ） (2022-07-25T04:45:16Z)
• Gaussian Process Bandit Optimization with Few Batches [49.896920704012395]
  有限腕バンディットアルゴリズムにインスパイアされたバッチアルゴリズムを導入する。 O(log T)$ batches in time horizon $T$.sqrtTgamma_T)$ using $O(log T)$ batches in time horizon。 さらに,アルゴリズムの修正版を提案し,バッチ数によって後悔がどう影響するかを特徴付ける。
  論文  参考訳（メタデータ） (2021-10-15T00:54:04Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。