論文の概要: Average Sensitivity of Spectral Clustering

• arxiv url: http://arxiv.org/abs/2006.04094v1
• Date: Sun, 7 Jun 2020 09:14:44 GMT
• ステータス: 処理完了
• システム内更新日: 2022-11-24 08:40:09.025845
• Title: Average Sensitivity of Spectral Clustering
• Title（参考訳）: スペクトルクラスタリングにおける平均感度
• Authors: Pan Peng, Yuichi Yoshida
• Abstract要約: 入力グラフにおけるエッジ摂動に対するスペクトルクラスタリングの安定性について検討する。 その結果,入力グラフにクラスタ構造が存在する場合,スペクトルクラスタリングはエッジ摂動に対して安定であることが示唆された。
• 参考スコア（独自算出の注目度）: 31.283432482502278
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Spectral clustering is one of the most popular clustering methods for finding clusters in a graph, which has found many applications in data mining. However, the input graph in those applications may have many missing edges due to error in measurement, withholding for a privacy reason, or arbitrariness in data conversion. To make reliable and efficient decisions based on spectral clustering, we assess the stability of spectral clustering against edge perturbations in the input graph using the notion of average sensitivity, which is the expected size of the symmetric difference of the output clusters before and after we randomly remove edges. We first prove that the average sensitivity of spectral clustering is proportional to $\lambda_2/\lambda_3^2$, where $\lambda_i$ is the $i$-th smallest eigenvalue of the (normalized) Laplacian. We also prove an analogous bound for $k$-way spectral clustering, which partitions the graph into $k$ clusters. Then, we empirically confirm our theoretical bounds by conducting experiments on synthetic and real networks. Our results suggest that spectral clustering is stable against edge perturbations when there is a cluster structure in the input graph.
• Abstract（参考訳）: スペクトルクラスタリングは、グラフ内のクラスタを見つけるための最も一般的なクラスタリング方法の1つであり、データマイニングに多くの応用がある。 しかし、これらのアプリケーションにおける入力グラフは、測定の誤り、プライバシの理由の保持、データ変換の任意性などにより、多くのエッジが不足している可能性がある。 スペクトルクラスタリングに基づく信頼性と効率的な決定を行うために,エッジのランダム除去前後の出力クラスタの対称差の予測サイズである平均感度の概念を用いて,入力グラフのエッジ摂動に対するスペクトルクラスタリングの安定性を評価する。 まず、スペクトルクラスタリングの平均感度が$\lambda_2/\lambda_3^2$に比例することを証明し、$\lambda_i$は(正規化)ラプラシアンの最小固有値である。 私たちはまた、グラフを$k$クラスタに分割する$k$-wayスペクトルクラスタリングに対する類似のバウンドを証明します。 次に, 合成および実ネットワーク実験を行い, 理論境界を実証的に確認する。 その結果,入力グラフにクラスタ構造がある場合,スペクトルクラスタリングはエッジ摂動に対して安定であることが示唆された。

関連論文リスト

• On the Robustness of Spectral Algorithms for Semirandom Stochastic Block Models [11.137244714693779]
  半ランダムな敵に対するスペクトルアルゴリズムの堅牢性について検討する。 我々は,_unnormalized_Laplacian を用いたスペクトル二分法が強い整合性を持つ半ランダム逆数クラスを同定した。
  論文  参考訳（メタデータ） (2024-12-18T20:35:02Z)
• HeNCler: Node Clustering in Heterophilous Graphs through Learned Asymmetric Similarity [55.27586970082595]
  HeNClerは、Heterophilous Node Clusteringの新しいアプローチである。 HeNClerは異種グラフコンテキストにおけるノードクラスタリングタスクの性能を大幅に向上させることを示す。
  論文  参考訳（メタデータ） (2024-05-27T11:04:05Z)
• Rethinking k-means from manifold learning perspective [122.38667613245151]
  平均推定なしで直接データのクラスタを検出する新しいクラスタリングアルゴリズムを提案する。 具体的には,バタワースフィルタを用いてデータ点間の距離行列を構成する。 異なる視点に埋め込まれた相補的な情報をうまく活用するために、テンソルのSchatten p-norm正規化を利用する。
  論文  参考訳（メタデータ） (2023-05-12T03:01:41Z)
• Spectral Clustering on Large Datasets: When Does it Work? Theory from Continuous Clustering and Density Cheeger-Buser [0.17188280334580194]
  現代の機械学習では、多くのデータセットは確率密度関数から引き出された多数の点としてモデル化される。 我々の研究は、ラプラス分布の混合から引き出されたデータに対して、シマリクスペクトルクラスタリングがうまく働くことを示唆している。 私たちのキーとなるツールは、不連続なものを含む全ての確率密度に対する新しいCheeger-Buser不等式です。
  論文  参考訳（メタデータ） (2023-05-11T03:08:49Z)
• A parameter-free graph reduction for spectral clustering and SpectralNet [1.5469452301122175]
  本稿では,パラメータを必要としないグラフ削減手法を提案する。 第一に、各点$p$からその近傍までの距離は、同じ周囲密度を持つ隣人にのみ適応しきい値を用いてフィルタリングされる。 2つのステップを生き残るエッジは、スペクトルクラスタリングであるSpectralNetに渡された構築されたグラフを形成する。
  論文  参考訳（メタデータ） (2023-02-25T21:19:30Z)
• Refining a $k$-nearest neighbor graph for a computationally efficient spectral clustering [1.5469452301122175]
  近似スペクトルクラスタリング(ASC)はサンプリングまたは量子化を使用してデータ代表を選択する。 我々は、データポイントを保持し、エッジ数を積極的に削減する、$k$-nearest 隣のグラフの洗練されたバージョンを提案する。 ASC法と比較して,提案手法はエッジの大幅な削減に拘わらず一貫した性能を示した。
  論文  参考訳（メタデータ） (2023-02-22T11:31:32Z)
• Perfect Spectral Clustering with Discrete Covariates [68.8204255655161]
  本稿では,大規模なスパースネットワークのクラスにおいて,高い確率で完全クラスタリングを実現するスペクトルアルゴリズムを提案する。 本手法は,スペクトルクラスタリングによる一貫した潜在構造回復を保証する最初の方法である。
  論文  参考訳（メタデータ） (2022-05-17T01:41:06Z)
• Improving Spectral Clustering Using Spectrum-Preserving Node Reduction [1.52292571922932]
  我々は、スペクトル保存ノード還元を用いて固有分解を加速し、データセットの簡潔な表現を生成する。 実験の結果,最先端手法と比較してクラスタリング性能が劇的に向上した。
  論文  参考訳（メタデータ） (2021-10-24T01:43:12Z)
• Spectral clustering under degree heterogeneity: a case for the random walk Laplacian [83.79286663107845]
  本稿では,ランダムウォークラプラシアンを用いたグラフスペクトル埋め込みが,ノード次数に対して完全に補正されたベクトル表現を生成することを示す。 次数補正ブロックモデルの特別な場合、埋め込みはK個の異なる点に集中し、コミュニティを表す。
  論文  参考訳（メタデータ） (2021-05-03T16:36:27Z)
• Computationally efficient sparse clustering [67.95910835079825]
  我々はPCAに基づく新しいクラスタリングアルゴリズムの有限サンプル解析を行う。 ここでは,ミニマックス最適誤クラスタ化率を,体制$|theta infty$で達成することを示す。
  論文  参考訳（メタデータ） (2020-05-21T17:51:30Z)
• Local Graph Clustering with Network Lasso [90.66817876491052]
  局所グラフクラスタリングのためのネットワークLasso法の統計的および計算的性質について検討する。 nLassoによって提供されるクラスタは、クラスタ境界とシードノードの間のネットワークフローを通じて、エレガントに特徴付けられる。
  論文  参考訳（メタデータ） (2020-04-25T17:52:05Z)

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

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