論文の概要: Revisiting Instance-Optimal Cluster Recovery in the Labeled Stochastic Block Model

• arxiv url: http://arxiv.org/abs/2306.12968v2
• Date: Mon, 03 Feb 2025 02:32:16 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-02-04 16:06:13.588049
• Title: Revisiting Instance-Optimal Cluster Recovery in the Labeled Stochastic Block Model
• Title（参考訳）: ラベル付き確率ブロックモデルにおけるインスタンス・最適クラスタ・リカバリの再検討
• Authors: Kaito Ariu, Alexandre Proutiere, Se-Young Yun,
• Abstract要約: IAC (Instance-Adaptive Clustering, インスタンス適応クラスタリング) を提案する。 IACは$ MathcalO(n, textpolylog(n) $の計算複雑性を維持しており、大規模問題に対してスケーラブルで実用的なものである。
• 参考スコア（独自算出の注目度）: 69.15976031704687
• License:
• Abstract: In this paper, we investigate the problem of recovering hidden communities in the Labeled Stochastic Block Model (LSBM) with a finite number of clusters whose sizes grow linearly with the total number of nodes. We derive the necessary and sufficient conditions under which the expected number of misclassified nodes is less than $ s $, for any number $ s = o(n) $. To achieve this, we propose IAC (Instance-Adaptive Clustering), the first algorithm whose performance matches the instance-specific lower bounds both in expectation and with high probability. IAC is a novel two-phase algorithm that consists of a one-shot spectral clustering step followed by iterative likelihood-based cluster assignment improvements. This approach is based on the instance-specific lower bound and notably does not require any knowledge of the 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)) $, making it scalable and practical for large-scale problems.
• Abstract（参考訳）: 本稿では,ラベル付き確率ブロックモデル (LSBM) における隠れたコミュニティを有限個のクラスタで復元する問題について検討する。 我々は、任意の数 $ s = o(n) $ に対して、非分類ノードの期待数が $ s $ 未満である必要十分条件を導出する。 そこで本研究では,インスタンス固有の下位境界と高い確率で一致した最初のアルゴリズムであるIAC(インスタンス適応クラスタリング)を提案する。 IACは1ショットのスペクトルクラスタリングステップと反復的確率に基づくクラスタ割り当ての改善からなる新しい2フェーズアルゴリズムである。 このアプローチはインスタンス固有の下位境界に基づいており、特にクラスタ数を含むモデルパラメータに関する知識は必要ない。 スペクトルクラスタリングを一度だけ行うことで、IACは$ \mathcal{O}(n\, \text{polylog}(n))$の計算複雑性を保ち、大規模問題に対してスケーラブルで実用的である。

関連論文リスト

• Gap-Free Clustering: Sensitivity and Robustness of SDP [6.996002801232415]
  ブロックモデル(SBM)におけるグラフクラスタリングについて,大クラスタと小クラスタの両方の存在下で検討した。 以前の凸緩和アプローチは正確な回復を達成するため、$o(sqrtn)$の小さなクラスタを許可しないか、最小の回復クラスタと最大の非回復クラスタの間のサイズギャップを必要とする。 本研究では,これらの要求を除去し,クラスタサイズによらず,大規模クラスタを確実に復元する半定値プログラミング(SDP)に基づくアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-08-29T21:27:21Z)
• Recovering Unbalanced Communities in the Stochastic Block Model With Application to Clustering with a Faulty Oracle [9.578056676899203]
  オラクルブロックモデル(英: Oracle block model、SBM)は、ネットワークにおけるグラフクラスタリングやコミュニティ検出を研究するための基礎モデルである。 我々は,SBMのコミュニティを様々な大きさのコミュニティで復元する,シンプルなSVDベースのアルゴリズムを提供する。
  論文  参考訳（メタデータ） (2022-02-17T08:51:19Z)
• Optimal Clustering with Bandit Feedback [57.672609011609886]
  本稿では,バンディットフィードバックを用いたオンラインクラスタリングの問題点について考察する。 これは、NPハード重み付きクラスタリング問題をサブルーチンとして解決する必要性を回避するための、シーケンシャルなテストのための新しい停止規則を含む。 合成および実世界のデータセットの広範なシミュレーションを通して、BOCの性能は下界と一致し、非適応的ベースラインアルゴリズムよりも大幅に優れることを示す。
  論文  参考訳（メタデータ） (2022-02-09T06:05:05Z)
• Personalized Federated Learning via Convex Clustering [72.15857783681658]
  本稿では,局所凸型ユーザコストを用いた個人化フェデレーション学習のためのアルゴリズム群を提案する。 提案するフレームワークは,異なるユーザのモデルの違いをペナル化する凸クラスタリングの一般化に基づいている。
  論文  参考訳（メタデータ） (2022-02-01T19:25:31Z)
• Lattice-Based Methods Surpass Sum-of-Squares in Clustering [98.46302040220395]
  クラスタリングは教師なし学習における基本的なプリミティブである。 最近の研究は、低次手法のクラスに対する低い境界を確立している。 意外なことに、この特定のクラスタリングモデルのtextitdoesは、統計的-計算的ギャップを示さない。
  論文  参考訳（メタデータ） (2021-12-07T18:50:17Z)
• On Margin-Based Cluster Recovery with Oracle Queries [22.672233769934845]
  1組の$n$ポイントのオラクルと"これらの2つのポイントは同じクラスタ内にあるのか? 本稿では,任意の凸クラスタを正確な時間で復元するアルゴリズムを提案する。 一般の擬計量空間では、クラスターが凸でない場合や、形状の概念が存在しない場合、$O(log n)$クエリ境界を達成し、確実に最適に近いアルゴリズムを与える。
  論文  参考訳（メタデータ） (2021-06-09T08:48:23Z)
• Scalable Hierarchical Agglomerative Clustering [65.66407726145619]
  既存のスケーラブルな階層的クラスタリング手法は、スピードの質を犠牲にする。 我々は、品質を犠牲にせず、数十億のデータポイントまでスケールする、スケーラブルで集約的な階層的クラスタリング法を提案する。
  論文  参考訳（メタデータ） (2020-10-22T15:58:35Z)
• Exact Recovery of Mangled Clusters with Same-Cluster Queries [20.03712152278538]
  半教師付きアクティブクラスタリングフレームワークにおけるクラスタリカバリ問題について検討する。 我々は、$n$ポイントを$k$クラスタに分割するアルゴリズムを設計し、$O(k3 ln k ln n)$oracleクエリと$tildeO(kn + k3)$でクラスタを非分類エラーで復元する。
  論文  参考訳（メタデータ） (2020-06-08T15:27:58Z)
• Computationally efficient sparse clustering [67.95910835079825]
  我々はPCAに基づく新しいクラスタリングアルゴリズムの有限サンプル解析を行う。 ここでは,ミニマックス最適誤クラスタ化率を,体制$|theta infty$で達成することを示す。
  論文  参考訳（メタデータ） (2020-05-21T17:51:30Z)

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

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