論文の概要: On consistency of constrained spectral clustering under
representation-aware stochastic block model
- arxiv url: http://arxiv.org/abs/2203.02005v1
- Date: Thu, 3 Mar 2022 20:41:14 GMT
- ステータス: 処理完了
- システム内更新日: 2022-03-07 14:17:25.270052
- Title: On consistency of constrained spectral clustering under
representation-aware stochastic block model
- Title（参考訳）: 表現型確率ブロックモデルにおける制約スペクトルクラスタリングの整合性について
- Authors: Shubham Gupta and Ambedkar Dukkipati
- Abstract要約: 制約付きスペクトルクラスタリングは、与えられたテクスト類似性グラフ$mathcalG$でバランスの取れたクラスタを見つけることを目的として研究される。
この環境では、スペクトルクラスタリングの非正規化および正規化の変種を開発する。
これらのアルゴリズムは$mathcalR$を使用して、提案された制約をほぼ満たした$mathcalG$のクラスタを見つける。
- 参考スコア（独自算出の注目度）: 20.6072287343024
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Spectral clustering is widely used in practice due to its flexibility,
computational efficiency, and well-understood theoretical performance
guarantees. Recently, spectral clustering has been studied to find balanced
clusters under population-level constraints. These constraints are specified by
additional information available in the form of auxiliary categorical node
attributes. In this paper, we consider a scenario where these attributes may
not be observable, but manifest as latent features of an auxiliary graph.
Motivated by this, we study constrained spectral clustering with the aim of
finding balanced clusters in a given \textit{similarity graph} $\mathcal{G}$,
such that each individual is adequately represented with respect to an
auxiliary graph $\mathcal{R}$ (we refer to this as representation graph). We
propose an individual-level balancing constraint that formalizes this idea. Our
work leads to an interesting stochastic block model that not only plants the
given partitions in $\mathcal{G}$ but also plants the auxiliary information
encoded in the representation graph $\mathcal{R}$. We develop unnormalized and
normalized variants of spectral clustering in this setting. These algorithms
use $\mathcal{R}$ to find clusters in $\mathcal{G}$ that approximately satisfy
the proposed constraint. We also establish the first statistical consistency
result for constrained spectral clustering under individual-level constraints
for graphs sampled from the above-mentioned variant of the stochastic block
model. Our experimental results corroborate our theoretical findings.
- Abstract（参考訳）: スペクトルクラスタリングは、その柔軟性、計算効率、そしてよく理解された理論的性能保証のために、実際に広く使われている。
近年,人口レベルの制約下でのバランスの取れたクラスターを見つけるためにスペクトルクラスタリングが研究されている。
これらの制約は、補助分類ノード属性の形式で利用可能な追加情報によって指定される。
本稿では,これらの属性を観測可能ではなく,補助グラフの潜在特徴として表現できるシナリオについて考察する。
これを動機としたスペクトルクラスタリングは、与えられた \textit{similarity graph} $\mathcal{G}$ において、各個人が補助グラフ $\mathcal{R}$ に対して適切に表現されるようなバランスのとれたクラスタを見つけることを目的として研究される(これを表現グラフと呼ぶ)。
この考え方を定式化する個別レベルのバランス制約を提案する。
我々の研究は、与えられたパーティションを$\mathcal{G}$に配置するだけでなく、表現グラフ$\mathcal{R}$に符号化された補助情報を植え付ける興味深い確率的ブロックモデルにつながります。
この環境では、非正規化および正規化スペクトルクラスタリングの変種を開発する。
これらのアルゴリズムは$\mathcal{R}$を使って、提案された制約をほぼ満たす$\mathcal{G}$のクラスタを見つける。
また,上述の確率的ブロックモデルの変種からサンプリングしたグラフの個々レベルの制約の下での制約付きスペクトルクラスタリングに対する最初の統計的一貫性を定式化する。
実験結果は理論的な結果と相関する。
関連論文リスト
- Interpretable Multi-View Clustering Based on Anchor Graph Tensor Factorization [64.00146569922028]
アンカーグラフの分解に基づくマルチビュークラスタリング法では,分解行列に対する適切なクラスタ解釈性が欠如している。
複数のビューからアンカーグラフを合成するアンカーグラフテンソルを分解するために、非負のテンソル因子分解を用いることにより、この制限に対処する。
論文 参考訳（メタデータ） (2024-04-01T03:23:55Z) - 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) - Nonbacktracking spectral clustering of nonuniform hypergraphs [2.408714894793063]
非一様ハイパーグラフに対するスペクトルクラスタリングをハイパーグラフ非追跡演算子を用いて検討する。
本稿では,線形化された信念伝達を用いたハイパーグラフブロックモデルにおける推論の交互化アルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-04-27T01:14:06Z) - Lattice-Based Methods Surpass Sum-of-Squares in Clustering [98.46302040220395]
クラスタリングは教師なし学習における基本的なプリミティブである。
最近の研究は、低次手法のクラスに対する低い境界を確立している。
意外なことに、この特定のクラスタリングモデルのtextitdoesは、統計的-計算的ギャップを示さない。
論文 参考訳（メタデータ） (2021-12-07T18:50:17Z) - Spectral-Spatial Global Graph Reasoning for Hyperspectral Image
Classification [50.899576891296235]
畳み込みニューラルネットワークは、ハイパースペクトル画像分類に広く応用されている。
近年の手法は空間トポロジのグラフ畳み込みによってこの問題に対処しようとしている。
論文 参考訳（メタデータ） (2021-06-26T06:24:51Z) - Average Sensitivity of Spectral Clustering [31.283432482502278]
入力グラフにおけるエッジ摂動に対するスペクトルクラスタリングの安定性について検討する。
その結果,入力グラフにクラスタ構造が存在する場合,スペクトルクラスタリングはエッジ摂動に対して安定であることが示唆された。
論文 参考訳（メタデータ） (2020-06-07T09:14:44Z) - Computationally efficient sparse clustering [67.95910835079825]
我々はPCAに基づく新しいクラスタリングアルゴリズムの有限サンプル解析を行う。
ここでは,ミニマックス最適誤クラスタ化率を,体制$|theta infty$で達成することを示す。
論文 参考訳（メタデータ） (2020-05-21T17:51:30Z) - Strong Consistency, Graph Laplacians, and the Stochastic Block Model [1.2891210250935143]
ブロックモデルを学ぶために,古典的な2段階のスペクトルクラスタリングの性能をグラフラプラシアンを用いて検討する。
スペクトルクラスタリングは,情報理論の限界に合致する条件下で,植民コミュニティ構造を正確に復元できることを示す。
論文 参考訳（メタデータ） (2020-04-21T07:16:46Z) - Robust spectral clustering using LASSO regularization [0.0]
本稿では,ブロックモデルと密接な関係を持つ新しいランダムモデルを用いて,スペクトルクラスタリングの一種である1スペクトルクラスタリングを提案する。
その目標は、グラフの自然な構造を明らかにする1の最小化問題のスパース固有基底解を促進することである。
論文 参考訳（メタデータ） (2020-04-08T07:12:56Z) - Embedding Graph Auto-Encoder for Graph Clustering [90.8576971748142]
グラフ自動エンコーダ(GAE)モデルは、半教師付きグラフ畳み込みネットワーク(GCN)に基づく
我々は、グラフクラスタリングのための特定のGAEベースのモデルを設計し、その理論、すなわち、埋め込みグラフオートエンコーダ(EGAE)と整合する。
EGAEは1つのエンコーダと2つのデコーダで構成される。
論文 参考訳（メタデータ） (2020-02-20T09:53:28Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。