論文の概要: Strong Consistency, Graph Laplacians, and the Stochastic Block Model

• arxiv url: http://arxiv.org/abs/2004.09780v1
• Date: Tue, 21 Apr 2020 07:16:46 GMT
• ステータス: 処理完了
• システム内更新日: 2022-12-11 06:31:05.637984
• Title: Strong Consistency, Graph Laplacians, and the Stochastic Block Model
• Title（参考訳）: 強一貫性, グラフラプラシアン, 確率ブロックモデル
• Authors: Shaofeng Deng, Shuyang Ling, Thomas Strohmer
• Abstract要約: ブロックモデルを学ぶために,古典的な2段階のスペクトルクラスタリングの性能をグラフラプラシアンを用いて検討する。 スペクトルクラスタリングは,情報理論の限界に合致する条件下で,植民コミュニティ構造を正確に復元できることを示す。
• 参考スコア（独自算出の注目度）: 1.2891210250935143
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Spectral clustering has become one of the most popular algorithms in data clustering and community detection. We study the performance of classical two-step spectral clustering via the graph Laplacian to learn the stochastic block model. Our aim is to answer the following question: when is spectral clustering via the graph Laplacian able to achieve strong consistency, i.e., the exact recovery of the underlying hidden communities? Our work provides an entrywise analysis (an $\ell_{\infty}$-norm perturbation bound) of the Fielder eigenvector of both the unnormalized and the normalized Laplacian associated with the adjacency matrix sampled from the stochastic block model. We prove that spectral clustering is able to achieve exact recovery of the planted community structure under conditions that match the information-theoretic limits.
• Abstract（参考訳）: スペクトルクラスタリングは、データクラスタリングとコミュニティ検出において最も人気のあるアルゴリズムの1つとなっている。 グラフラプラシアンによる古典的2段階スペクトルクラスタリングの性能について検討し,確率ブロックモデルについて考察する。 グラフラプラシアンによるスペクトルクラスタリングは、いつ、根底にある隠れたコミュニティの正確な回復という、強い一貫性を達成することができるのか? 我々の研究は、確率ブロックモデルからサンプリングされた隣接行列に付随する非正規化ラプラシアンと正規化ラプラシアンの両方の fielder eigenvector のエントリワイズ解析($\ell_{\infty}$-norm摂動境界)を提供する。 スペクトルクラスタリングは,情報理論上の限界に適合する条件下で,植栽されたコミュニティ構造を正確に回復できることを実証する。

関連論文リスト

• Graph Generation via Spectral Diffusion [51.60814773299899]
  本稿では,1)グラフラプラシア行列のスペクトル分解と2)拡散過程に基づく新しいグラフ生成モデルGRASPを提案する。 具体的には、固有ベクトルと固有値のサンプリングにデノナイジングモデルを用い、グラフラプラシアン行列と隣接行列を再構成する。 我々の置換不変モデルは各ノードの固有ベクトルに連結することでノードの特徴を扱える。
  論文  参考訳（メタデータ） (2024-02-29T09:26:46Z)
• Latent Random Steps as Relaxations of Max-Cut, Min-Cut, and More [30.919536115917726]
  クラスタリングと単純化を統一する非負行列分解に基づく確率モデルを提案する。 ハードクラスタリングをソフトクラスタリングに緩和することにより、ハードクラスタリングの潜在的な問題をトラクタブルクラスタに緩和する。
  論文  参考訳（メタデータ） (2023-08-12T02:47:57Z)
• 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)
• Robustness of Community Detection to Random Geometric Perturbations [16.575947847660778]
  我々は、頂点間の接続が、潜在(かつ観測されていない)ランダムな幾何グラフによって摂動されるブロックモデルを考える。 目的は、スペクトル法がランダムグラフの存在(あるいはそうでない)に非依存であっても、この種のノイズに対して堅牢であることを証明することである。
  論文  参考訳（メタデータ） (2020-11-09T10:15:40Z)
• Average Sensitivity of Spectral Clustering [31.283432482502278]
  入力グラフにおけるエッジ摂動に対するスペクトルクラスタリングの安定性について検討する。 その結果,入力グラフにクラスタ構造が存在する場合,スペクトルクラスタリングはエッジ摂動に対して安定であることが示唆された。
  論文  参考訳（メタデータ） (2020-06-07T09:14:44Z)
• Robust spectral clustering using LASSO regularization [0.0]
  本稿では,ブロックモデルと密接な関係を持つ新しいランダムモデルを用いて,スペクトルクラスタリングの一種である1スペクトルクラスタリングを提案する。 その目標は、グラフの自然な構造を明らかにする1の最小化問題のスパース固有基底解を促進することである。
  論文  参考訳（メタデータ） (2020-04-08T07:12:56Z)

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

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