論文の概要: Exact Selective Inference for Spectral Clustering via Piecewise-Constant Graph Perturbation
- arxiv url: http://arxiv.org/abs/2611.04995v1
- Date: Tue, 03 Nov 2026 14:45:53 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-11-07 15:11:47.282764
- Title: Exact Selective Inference for Spectral Clustering via Piecewise-Constant Graph Perturbation
- Title（参考訳）: 経時的グラフ摂動によるスペクトルクラスタリングのための厳密な選択推論
- Abstract要約: クラスタラベルは、まずグループを発見し、次に発見されたグループが異なるかどうかをテストするために、しばしば2回使用される。
非重み付き $varepsilon$- または $k$-nearest-nebor グラフに基づくスペクトルクラスタリングでは、障害は親和性の構成である。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Cluster labels are often used twice: first to discover groups, and then to test whether the discovered groups differ. This double use of the data makes ordinary two-sample $p$-values anti-conservative. Selective inference fixes this by conditioning on the clustering event, but for spectral clustering the event appears difficult because the algorithm combines an affinity map, an eigendecomposition, and a rounding step. We show that, for spectral clustering based on unweighted $\varepsilon$- or $k$-nearest-neighbor graphs, the obstruction is the affinity construction rather than the eigendecomposition. Along the one-dimensional perturbation used by the truncated-$χ$ selective test, graph changes occur only at finitely many real roots of data-dependent quadratic distance comparisons. Between these breakpoints, the graph, Laplacian spectrum, embedding, rounding, and reported cluster pair are deterministic functions of a finite graph state. Consequently, in real arithmetic and under a known-scale spherical Gaussian model, the selection set is an exact finite union of intervals, yielding finite-sample selective $p$-values for selected spectral-cluster pairs. The same argument gives feature-wise truncated-normal tests. We also record direct extensions to known feature covariance, eigengap-selected $K$, and auxiliary-coordinate graphs. We validate null and partial-null calibration, operational power, numerical sensitivity, and model-scope diagnostics, and give a working-model PBMC algorithmic illustration. Smooth kernels such as RBF affinities fall outside the finite-state guarantee.
- Abstract（参考訳）: クラスタラベルは、まずグループを発見し、次に発見されたグループが異なるかどうかをテストするために、しばしば2回使用される。
このデータの二重利用は、通常の2サンプルの$p$-valuesを反保守的にする。
選択推論はクラスタリングイベントを条件付けすることでこれを修正するが、スペクトルクラスタリングでは、アルゴリズムが親和性マップ、固有分解、丸めステップを組み合わせたため、イベントは難しいように見える。
非重み付き $\varepsilon$- または $k$-nearest-nebor グラフに基づくスペクトルクラスタリングにおいて、障害は固有分解ではなく親和性構造であることを示す。
truncated-$$選択テストで用いられる一次元摂動とともに、グラフの変化はデータ依存二次距離比較の有限個の実根でのみ起こる。
これらのブレークポイントの間、グラフ、ラプラシアスペクトル、埋め込み、丸め、および報告されたクラスタペアは有限グラフ状態の決定論的関数である。
したがって、実算術と既知の球面ガウスモデルの下では、選択集合は区間の完全有限和であり、選択されたスペクトルクラスタ対に対して有限サンプル選択$p$-値が得られる。
同じ引数は、機能的にトランケートされた正規テストを与える。
また、既知の特徴共分散、固有ギャップ選択$K$、補助座標グラフへの直接拡張も記録する。
我々は、ヌルと部分ヌルの校正、演算力、数値感度、モデル顕微鏡診断を検証し、ワーキングモデルPBMCアルゴリズムの図示を与える。
RBFアフィニティのような滑らかなカーネルは有限状態保証の外にある。
関連論文リスト
- On Statistical-Computational Gaps in Graph Combinatorial Testing Problems [58.85882035098977]
未知のサブグラフのエッジセット上で信号が支持される高次元グラフ仮説試験問題について検討する。
ガウス観測では、強い検出に必要な信号の大きさについて、鋭い統計的および計算的な閾値を特徴付ける。
論文 参考訳（メタデータ） (2026-10-30T16:41:47Z) - On Conditional Independence Graph Learning From Multi-Attribute Gaussian Dependent Time Series [16.481440561437307]
多属性データから高次元多変量時系列の条件独立グラフ(CIG)を推定する。
本稿では,情報基準に基づくパラメータのベイズ的選択について検討し,合成データと実データの両方を用いたアプローチについても述べる。
論文 参考訳（メタデータ） (2025-12-08T13:48:25Z) - On the Robustness of Spectral Algorithms for Semirandom Stochastic Block Models [11.137244714693779]
半ランダムな敵に対するスペクトルアルゴリズムの堅牢性について検討する。
我々は,_unnormalized_Laplacian を用いたスペクトル二分法が強い整合性を持つ半ランダム逆数クラスを同定した。
論文 参考訳（メタデータ） (2024-12-18T20:35:02Z) - Generating Graphs via Spectral Diffusion [48.70458395826864]
本稿では,1)グラフラプラシア行列のスペクトル分解と2)拡散過程に基づく新しいグラフ生成モデルGGSDを提案する。
合成グラフと実世界のグラフの両方に関する広範な実験は、最先端の代替品に対する我々のモデルの強みを実証している。
論文 参考訳（メタデータ） (2024-02-29T09:26:46Z) - A Unified Framework for Center-based Clustering of Distributed Data [46.86543102499174]
我々は、ユーザのネットワーク上で動作する分散センターベースのクラスタリングアルゴリズムのファミリーを開発する。
私たちのフレームワークは、$K$-meansやHuber Losといった一般的なクラスタリング損失を含む、スムーズな凸損失関数の幅広いクラスを可能にします。
ブレグマン損失の特別の場合、固定点がロイド点の集合に収束することを示す。
論文 参考訳（メタデータ） (2024-02-02T10:44:42Z) - 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) - On consistency of constrained spectral clustering under
representation-aware stochastic block model [20.6072287343024]
制約付きスペクトルクラスタリングは、与えられたテクスト類似性グラフ$mathcalG$でバランスの取れたクラスタを見つけることを目的として研究される。
この環境では、スペクトルクラスタリングの非正規化および正規化の変種を開発する。
これらのアルゴリズムは$mathcalR$を使用して、提案された制約をほぼ満たした$mathcalG$のクラスタを見つける。
論文 参考訳（メタデータ） (2022-03-03T20:41:14Z) - Spatially relaxed inference on high-dimensional linear models [48.989769153211995]
本研究では,空間的に制約されたクラスタリング,統計的推論,アンサンブルを組み合わせ,複数のクラスタリング推論解を集約するアンサンブルクラスタリング推論アルゴリズムの特性について検討する。
アンサンブルクラスタ推論アルゴリズムは,最大クラスター径に等しい$delta$-FWERの標準仮定で$delta$-FWERを制御することを示す。
論文 参考訳（メタデータ） (2021-06-04T16:37:19Z) - 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) - Improved guarantees and a multiple-descent curve for Column Subset
Selection and the Nystr\"om method [76.73096213472897]
我々は,データ行列のスペクトル特性を利用して近似保証を改良する手法を開発した。
我々のアプローチは、特異値減衰の既知の速度を持つデータセットのバウンダリが大幅に向上する。
RBFパラメータを変更すれば,改良された境界線と多重発振曲線の両方を実データセット上で観測できることが示される。
論文 参考訳（メタデータ） (2020-02-21T00:43:06Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。