論文の概要: On the Robustness of Spectral Algorithms for Semirandom Stochastic Block Models
- arxiv url: http://arxiv.org/abs/2412.14315v1
- Date: Wed, 18 Dec 2024 20:35:02 GMT
- ステータス: 翻訳完了
- システム内更新日: 2024-12-20 13:32:44.170058
- Title: On the Robustness of Spectral Algorithms for Semirandom Stochastic Block Models
- Title（参考訳）: 半ランダム確率ブロックモデルに対するスペクトルアルゴリズムのロバスト性について
- Authors: Aditya Bhaskara, Agastya Vibhuti Jha, Michael Kapralov, Naren Sarayu Manoj, Davide Mazzali, Weronika Wrzos-Kaminska,
- Abstract要約: 半ランダムな敵に対するスペクトルアルゴリズムの堅牢性について検討する。
我々は,_unnormalized_Laplacian を用いたスペクトル二分法が強い整合性を持つ半ランダム逆数クラスを同定した。
- 参考スコア（独自算出の注目度）: 11.137244714693779
- License:
- Abstract: In a graph bisection problem, we are given a graph $G$ with two equally-sized unlabeled communities, and the goal is to recover the vertices in these communities. A popular heuristic, known as spectral clustering, is to output an estimated community assignment based on the eigenvector corresponding to the second smallest eigenvalue of the Laplacian of $G$. Spectral algorithms can be shown to provably recover the cluster structure for graphs generated from certain probabilistic models, such as the Stochastic Block Model (SBM). However, spectral clustering is known to be non-robust to model mis-specification. Techniques based on semidefinite programming have been shown to be more robust, but they incur significant computational overheads. In this work, we study the robustness of spectral algorithms against semirandom adversaries. Informally, a semirandom adversary is allowed to ``helpfully'' change the specification of the model in a way that is consistent with the ground-truth solution. Our semirandom adversaries in particular are allowed to add edges inside clusters or increase the probability that an edge appears inside a cluster. Semirandom adversaries are a useful tool to determine the extent to which an algorithm has overfit to statistical assumptions on the input. On the positive side, we identify classes of semirandom adversaries under which spectral bisection using the _unnormalized_ Laplacian is strongly consistent, i.e., it exactly recovers the planted partitioning. On the negative side, we show that in these classes spectral bisection with the _normalized_ Laplacian outputs a partitioning that makes a classification mistake on a constant fraction of the vertices. Finally, we demonstrate numerical experiments that complement our theoretical findings.
- Abstract（参考訳）: グラフ分岐問題では、2つの同じ大きさの未ラベルのコミュニティを持つグラフ$G$が与えられ、これらのコミュニティの頂点を復元することが目的である。
スペクトルクラスタリングとして知られる一般的なヒューリスティックは、ラプラシアンの第二の最小固有値である$G$に対応する固有ベクトルに基づいて、推定されたコミュニティ割り当てを出力することである。
スペクトルアルゴリズムは確率的ブロックモデル(SBM)のような確率論的モデルから生成されたグラフのクラスタ構造を確実に復元することができる。
しかし、スペクトルクラスタリングは誤特定をモデル化するのに不便であることが知られている。
半定値プログラミングに基づく手法はより堅牢であることが示されているが、計算上のオーバーヘッドは大きい。
本研究では,半ランダムな敵に対するスペクトルアルゴリズムのロバスト性について検討する。
インフォーマルに、半ランダムな敵は「helpfully」で、基底的真理解と整合した方法でモデルの仕様を変更することが許される。
特に我々のセミランダムの敵は、クラスタ内にエッジを追加することや、クラスタ内にエッジが現れる確率を高めることができる。
セミランダムの敵は、アルゴリズムが入力に対する統計的仮定に過度に適合している範囲を決定するのに有用なツールである。
正の面では、_unnormalized_Laplacian を用いたスペクトル二分法が強く一貫した半ランダム逆数(英語版)のクラスを同定する。
負の面では、これらのクラスにおいて、_normalized_Laplacian のスペクトル二分法は、頂点の一定部分の分類ミスを生じさせる分割を出力することを示す。
最後に, 理論的知見を補完する数値実験を行った。
関連論文リスト
- Robustness for Spectral Clustering of General Graphs under Local Differential Privacy [2.4447259440166302]
ソーシャルネットワークはブロックモデル(SBM)から派生していないと我々は主張する。
私たちの主な焦点は、エッジフリップメソッド -- ローカルな差分プライバシーを保護するための一般的なテクニック -- にあります。
クラスタリングの結果は、SBMから生成される密集グラフやクラスタリンググラフに対して安定しているが、一般に、スペクトルクラスタリングは特定の密集グラフやクラスタリンググラフに対して非常に不規則な結果をもたらす可能性があることを示す。
論文 参考訳（メタデータ） (2023-09-13T10:23:29Z) - Instance-Optimal Cluster Recovery in the Labeled Stochastic Block Model [79.46465138631592]
観測されたラベルを用いてクラスタを復元する効率的なアルゴリズムを考案する。
本稿では,期待値と高い確率でこれらの下位境界との性能を一致させる最初のアルゴリズムであるIACを提案する。
論文 参考訳（メタデータ） (2023-06-18T08:46:06Z) - Perfect Spectral Clustering with Discrete Covariates [68.8204255655161]
本稿では,大規模なスパースネットワークのクラスにおいて,高い確率で完全クラスタリングを実現するスペクトルアルゴリズムを提案する。
本手法は,スペクトルクラスタリングによる一貫した潜在構造回復を保証する最初の方法である。
論文 参考訳（メタデータ） (2022-05-17T01:41:06Z) - On consistency of constrained spectral clustering under
representation-aware stochastic block model [20.6072287343024]
制約付きスペクトルクラスタリングは、与えられたテクスト類似性グラフ$mathcalG$でバランスの取れたクラスタを見つけることを目的として研究される。
この環境では、スペクトルクラスタリングの非正規化および正規化の変種を開発する。
これらのアルゴリズムは$mathcalR$を使用して、提案された制約をほぼ満たした$mathcalG$のクラスタを見つける。
論文 参考訳（メタデータ） (2022-03-03T20:41:14Z) - 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) - Spectral clustering under degree heterogeneity: a case for the random
walk Laplacian [83.79286663107845]
本稿では,ランダムウォークラプラシアンを用いたグラフスペクトル埋め込みが,ノード次数に対して完全に補正されたベクトル表現を生成することを示す。
次数補正ブロックモデルの特別な場合、埋め込みはK個の異なる点に集中し、コミュニティを表す。
論文 参考訳（メタデータ） (2021-05-03T16:36:27Z) - Shaping Deep Feature Space towards Gaussian Mixture for Visual
Classification [74.48695037007306]
視覚分類のためのディープニューラルネットワークのためのガウス混合損失関数(GM)を提案する。
分類マージンと可能性正規化により、GM損失は高い分類性能と特徴分布の正確なモデリングの両方を促進する。
提案したモデルは、追加のトレーニング可能なパラメータを使わずに、簡単かつ効率的に実装できる。
論文 参考訳（メタデータ） (2020-11-18T03:32:27Z) - Average Sensitivity of Spectral Clustering [31.283432482502278]
入力グラフにおけるエッジ摂動に対するスペクトルクラスタリングの安定性について検討する。
その結果,入力グラフにクラスタ構造が存在する場合,スペクトルクラスタリングはエッジ摂動に対して安定であることが示唆された。
論文 参考訳（メタデータ） (2020-06-07T09:14:44Z) - Strong Consistency, Graph Laplacians, and the Stochastic Block Model [1.2891210250935143]
ブロックモデルを学ぶために,古典的な2段階のスペクトルクラスタリングの性能をグラフラプラシアンを用いて検討する。
スペクトルクラスタリングは,情報理論の限界に合致する条件下で,植民コミュニティ構造を正確に復元できることを示す。
論文 参考訳（メタデータ） (2020-04-21T07:16:46Z) - Randomized Spectral Clustering in Large-Scale Stochastic Block Models [13.366036495177923]
統計的観点からランダム化されたスケッチアルゴリズムを用いてスペクトルクラスタリングについて検討する。
弱い条件下では、ランダム化されたスペクトルクラスタリングアルゴリズムは、元のスペクトルクラスタリングアルゴリズムと同じ理論的境界に導かれる。
Rclustと呼ばれる新しいRパッケージが開発され、一般に公開されている。
論文 参考訳（メタデータ） (2020-01-20T04:15:25Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。