論文の概要: Structure-Aware Spectral Sparsification via Uniform Edge Sampling

• arxiv url: http://arxiv.org/abs/2510.12669v1
• Date: Tue, 14 Oct 2025 16:05:02 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-10-15 19:02:32.385125
• Title: Structure-Aware Spectral Sparsification via Uniform Edge Sampling
• Title（参考訳）: 一様エッジサンプリングによる構造認識スペクトルスペーサー化
• Authors: Kaiwen He, Petros Drineas, Rajiv Khanna,
• Abstract要約: スペクトルクラスタリングにおける一様エッジサンプリング-単純な構造に依存しない戦略-が有効かどうかを考察する。 我々は、$O(gamma2 n log n / epsilon2)$ edges, where $gamma$ is the Laplacian condition number, yield a sparsifier that top $(n-k)$-dimensional eigenspace is almost to the cluster indicators。
• 参考スコア（独自算出の注目度）: 12.266977096773472
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Spectral clustering is a fundamental method for graph partitioning, but its reliance on eigenvector computation limits scalability to massive graphs. Classical sparsification methods preserve spectral properties by sampling edges proportionally to their effective resistances, but require expensive preprocessing to estimate these resistances. We study whether uniform edge sampling-a simple, structure-agnostic strategy-can suffice for spectral clustering. Our main result shows that for graphs admitting a well-separated $k$-clustering, characterized by a large structure ratio $\Upsilon(k) = \lambda_{k+1} / \rho_G(k)$, uniform sampling preserves the spectral subspace used for clustering. Specifically, we prove that uniformly sampling $O(\gamma^2 n \log n / \epsilon^2)$ edges, where $\gamma$ is the Laplacian condition number, yields a sparsifier whose top $(n-k)$-dimensional eigenspace is approximately orthogonal to the cluster indicators. This ensures that the spectral embedding remains faithful, and clustering quality is preserved. Our analysis introduces new resistance bounds for intra-cluster edges, a rank-$(n-k)$ effective resistance formulation, and a matrix Chernoff bound adapted to the dominant eigenspace. These tools allow us to bypass importance sampling entirely. Conceptually, our result connects recent coreset-based clustering theory to spectral sparsification, showing that under strong clusterability, even uniform sampling is structure-aware. This provides the first provable guarantee that uniform edge sampling suffices for structure-preserving spectral clustering.
• Abstract（参考訳）: スペクトルクラスタリングはグラフ分割の基本的な方法であるが、固有ベクトル計算への依存はスケーラビリティを巨大なグラフに制限する。 古典的なスペーシフィケーション法は、エッジを有効抵抗に比例してサンプリングすることでスペクトル特性を保存するが、これらの抵抗を推定するためには高価な前処理が必要である。 スペクトルクラスタリングにおける一様エッジサンプリング-単純な構造に依存しない戦略-が有効かどうかを考察する。 我々の主な結果は、十分に分離された$k$-クラスタリングを許容するグラフに対して、大きな構造比 $\Upsilon(k) = \lambda_{k+1} / \rho_G(k)$ が特徴である。 具体的には、$O(\gamma^2 n \log n / \epsilon^2)$ edges, where $\gamma$ is the Laplacian condition number, yield a sparsifier that top $(n-k)$-dimensional eigenspace is almost orthogonal to the cluster indicators。 これにより、スペクトル埋め込みが忠実に保たれ、クラスタリングの品質が維持される。 解析では, クラスタ内エッジに対する新しい抵抗境界, ランク=(n-k)$有効抵抗定式化, 支配固有空間に適応した行列チャーノフを導入する。 これらのツールによって、重要なサンプリングを完全に回避できます。 概念的には、我々の結果は近年のコアセットに基づくクラスタリング理論とスペクトルスペーサー化を結びつけ、強いクラスタビリティの下では、一様サンプリングでさえ構造を意識していることを示す。 これは、構造保存スペクトルクラスタリングのための一様エッジサンプリングサフィスを保証できる最初の保証を提供する。

関連論文リスト

• Graph-based Clustering Revisited: A Relaxation of Kernel $k$-Means Perspective [73.18641268511318]
  本稿では,クラスタリング結果を導出するための正規制約のみを緩和するグラフベースのクラスタリングアルゴリズムを提案する。 二重制約を勾配に変換するために、非負の制約をクラス確率パラメータに変換する。
  論文  参考訳（メタデータ） (2025-09-23T09:14:39Z)
• Scalable Context-Preserving Model-Aware Deep Clustering for Hyperspectral Images [51.95768218975529]
  ハイパースペクトル画像(HSI)の教師なし解析にサブスペースクラスタリングが広く採用されている。 近年のモデル対応深層空間クラスタリング手法では、O(n2)の複雑性を持つ自己表現行列の計算とスペクトルクラスタリングを含む2段階のフレームワークを用いることが多い。 本稿では,HSIクラスタリングを効率的に行うために,局所構造と非局所構造を協調的にキャプチャする,ベース表現に基づく拡張性のあるコンテキスト保存深層クラスタリング手法を提案する。
  論文  参考訳（メタデータ） (2025-06-12T16:43:09Z)
• Near-Optimal Clustering in Mixture of Markov Chains [74.3828414695655]
  我々は、長さ$H$の軌跡を、大きさ$S$の有限状態空間上の未知のエルゴードマルコフ鎖の1つによって生成される、$T$ trajectories of length $H$の問題を研究する。 我々は、連鎖の遷移核間の重み付きKL分散によって支配されるクラスタリングエラー率に基づいて、インスタンス依存で高い確率の低い境界を導出する。 次に,新しい2段階クラスタリングアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2025-06-02T05:10:40Z)
• On the Robustness of Spectral Algorithms for Semirandom Stochastic Block Models [11.137244714693779]
  半ランダムな敵に対するスペクトルアルゴリズムの堅牢性について検討する。 我々は,_unnormalized_Laplacian を用いたスペクトル二分法が強い整合性を持つ半ランダム逆数クラスを同定した。
  論文  参考訳（メタデータ） (2024-12-18T20:35:02Z)
• Revisiting Instance-Optimal Cluster Recovery in the Labeled Stochastic Block Model [85.51611950757643]
  IAC (Instance-Adaptive Clustering, インスタンス適応クラスタリング) を提案する。 IACは$ MathcalO(n, textpolylog(n) $の計算複雑性を維持しており、大規模問題に対してスケーラブルで実用的なものである。
  論文  参考訳（メタデータ） (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)
• An $\ell_p$ theory of PCA and spectral clustering [23.90245234027558]
  主成分分析は統計と機械学習において強力なツールである。 本稿では、ヒルベルト空間におけるPCAの中空バージョンに対する$ell_p$理論を開発する。 文脈的コミュニティ検出のために、$ell_p$理論は、正確な回復のための情報しきい値を達成する単純なスペクトルアルゴリズムに導かれる。
  論文  参考訳（メタデータ） (2020-06-24T21:30:28Z)
• Average Sensitivity of Spectral Clustering [31.283432482502278]
  入力グラフにおけるエッジ摂動に対するスペクトルクラスタリングの安定性について検討する。 その結果,入力グラフにクラスタ構造が存在する場合,スペクトルクラスタリングはエッジ摂動に対して安定であることが示唆された。
  論文  参考訳（メタデータ） (2020-06-07T09:14:44Z)

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

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