論文の概要: Recovering Unbalanced Communities in the Stochastic Block Model With
Application to Clustering with a Faulty Oracle
- arxiv url: http://arxiv.org/abs/2202.08522v3
- Date: Sat, 21 Oct 2023 07:27:33 GMT
- ステータス: 処理完了
- システム内更新日: 2023-10-25 15:16:20.694415
- Title: Recovering Unbalanced Communities in the Stochastic Block Model With
Application to Clustering with a Faulty Oracle
- Title（参考訳）: 確率的ブロックモデルにおける不均衡コミュニティの回復と欠陥オラクルによるクラスタリングへの応用
- Authors: Chandra Sekhar Mukherjee, Pan Peng and Jiapeng Zhang
- Abstract要約: オラクルブロックモデル(英: Oracle block model、SBM)は、ネットワークにおけるグラフクラスタリングやコミュニティ検出を研究するための基礎モデルである。
我々は,SBMのコミュニティを様々な大きさのコミュニティで復元する,シンプルなSVDベースのアルゴリズムを提供する。
- 参考スコア（独自算出の注目度）: 9.578056676899203
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: The stochastic block model (SBM) is a fundamental model for studying graph
clustering or community detection in networks. It has received great attention
in the last decade and the balanced case, i.e., assuming all clusters have
large size, has been well studied. However, our understanding of SBM with
unbalanced communities (arguably, more relevant in practice) is still limited.
In this paper, we provide a simple SVD-based algorithm for recovering the
communities in the SBM with communities of varying sizes. We improve upon a
result of Ailon, Chen and Xu [ICML 2013; JMLR 2015] by removing the assumption
that there is a large interval such that the sizes of clusters do not fall in,
and also remove the dependency of the size of the recoverable clusters on the
number of underlying clusters. We further complement our theoretical
improvements with experimental comparisons. Under the planted clique
conjecture, the size of the clusters that can be recovered by our algorithm is
nearly optimal (up to poly-logarithmic factors) when the probability parameters
are constant.
As a byproduct, we obtain an efficient clustering algorithm with sublinear
query complexity in a faulty oracle model, which is capable of detecting all
clusters larger than $\tilde{\Omega}({\sqrt{n}})$, even in the presence of
$\Omega(n)$ small clusters in the graph. In contrast, previous efficient
algorithms that use a sublinear number of queries are incapable of recovering
any large clusters if there are more than $\tilde{\Omega}(n^{2/5})$ small
clusters.
- Abstract（参考訳）: 確率ブロックモデル(SBM)は,ネットワークにおけるグラフクラスタリングやコミュニティ検出の基本的なモデルである。
過去10年間で大きな注目を集めており、バランスの取れた場合、すなわち全てのクラスターが大きければ、十分に研究されている。
しかし、不均衡なコミュニティとのSBMの理解(おそらく実際はより関連性が高い)は依然として限られている。
本稿では,SBMのコミュニティを様々な大きさのコミュニティで復元するための,SVDに基づく簡単なアルゴリズムを提案する。
我々は, Ailon, Chen, Xu (ICML 2013; JMLR 2015) の結果として, クラスタのサイズが低下しないような大きな間隔が存在するという仮定を排除し, 下位クラスタ数に対するリカバリ可能なクラスタのサイズ依存性を取り除くことにより, 改善を行った。
さらに理論的な改善を実験的比較で補う。
植込み傾き予想の下では、確率パラメータが定数である場合、我々のアルゴリズムによって復元できるクラスタのサイズはほぼ最適である(多対数因子まで)。
副産物として、グラフに$\Omega(n)$の小さなクラスタが存在する場合でも、$\tilde{\Omega}({\sqrt{n}})$より大きいすべてのクラスタを検出することができる、欠陥オラクルモデルにおけるサブ線形クエリの複雑さを持つ効率的なクラスタリングアルゴリズムを得る。
対照的に、クエリのサブ線形数を使用する従来の効率的なアルゴリズムは、$\tilde{\Omega}(n^{2/5})$小クラスタがある場合、大きなクラスタを復元できない。
関連論文リスト
- Gap-Free Clustering: Sensitivity and Robustness of SDP [6.996002801232415]
ブロックモデル(SBM)におけるグラフクラスタリングについて,大クラスタと小クラスタの両方の存在下で検討した。
以前の凸緩和アプローチは正確な回復を達成するため、$o(sqrtn)$の小さなクラスタを許可しないか、最小の回復クラスタと最大の非回復クラスタの間のサイズギャップを必要とする。
本研究では,これらの要求を除去し,クラスタサイズによらず,大規模クラスタを確実に復元する半定値プログラミング(SDP)に基づくアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-08-29T21:27:21Z) - Instance-Optimal Cluster Recovery in the Labeled Stochastic Block Model [79.46465138631592]
観測されたラベルを用いてクラスタを復元する効率的なアルゴリズムを考案する。
本稿では,期待値と高い確率でこれらの下位境界との性能を一致させる最初のアルゴリズムであるIACを提案する。
論文 参考訳（メタデータ） (2023-06-18T08:46:06Z) - Dink-Net: Neural Clustering on Large Graphs [59.10189693120368]
ディープグラフクラスタリング法 (Dink-Net) は, 拡張と縮小という概念を用いて提案される。
ノードを識別することにより、拡張によって劣化しても、表現は自己教師された方法で学習される。
クラスタリング分布は、提案したクラスタ拡張損失とクラスタ縮小損失を最小化することにより最適化される。
ランナアップと比較して、Dink-Net 9.62%は1100万ノードと16億エッジを持つogbn-papers100MデータセットでNMIの改善を実現している。
論文 参考訳（メタデータ） (2023-05-28T15:33:24Z) - Convex Clustering through MM: An Efficient Algorithm to Perform
Hierarchical Clustering [1.0589208420411012]
本稿では,クラスタ融合と高効率更新方式を用いた反復アルゴリズムCCMMによる凸クラスタリングを提案する。
現在のデスクトップコンピュータでは、CCMMは、7次元空間に100万以上のオブジェクトを含む凸クラスタリング問題を効率的に解決する。
論文 参考訳（メタデータ） (2022-11-03T15:07:51Z) - Optimal Clustering with Bandit Feedback [57.672609011609886]
本稿では,バンディットフィードバックを用いたオンラインクラスタリングの問題点について考察する。
これは、NPハード重み付きクラスタリング問題をサブルーチンとして解決する必要性を回避するための、シーケンシャルなテストのための新しい停止規則を含む。
合成および実世界のデータセットの広範なシミュレーションを通して、BOCの性能は下界と一致し、非適応的ベースラインアルゴリズムよりも大幅に優れることを示す。
論文 参考訳（メタデータ） (2022-02-09T06:05:05Z) - Lattice-Based Methods Surpass Sum-of-Squares in Clustering [98.46302040220395]
クラスタリングは教師なし学習における基本的なプリミティブである。
最近の研究は、低次手法のクラスに対する低い境界を確立している。
意外なことに、この特定のクラスタリングモデルのtextitdoesは、統計的-計算的ギャップを示さない。
論文 参考訳（メタデータ） (2021-12-07T18:50:17Z) - Correlation Clustering Reconstruction in Semi-Adversarial Models [70.11015369368272]
相関クラスタリングは多くのアプリケーションにおいて重要なクラスタリング問題である。
本研究では,ランダムノイズや対向的な修正によって崩壊した潜伏クラスタリングを再構築しようとする,この問題の再構築版について検討する。
論文 参考訳（メタデータ） (2021-08-10T14:46:17Z) - On Margin-Based Cluster Recovery with Oracle Queries [22.672233769934845]
1組の$n$ポイントのオラクルと"これらの2つのポイントは同じクラスタ内にあるのか?
本稿では,任意の凸クラスタを正確な時間で復元するアルゴリズムを提案する。
一般の擬計量空間では、クラスターが凸でない場合や、形状の概念が存在しない場合、$O(log n)$クエリ境界を達成し、確実に最適に近いアルゴリズムを与える。
論文 参考訳（メタデータ） (2021-06-09T08:48:23Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。