論文の概要: Simplify to Amplify: Achieving Information-Theoretic Bounds with Fewer Steps in Spectral Community Detection
- arxiv url: http://arxiv.org/abs/2602.17104v1
- Date: Thu, 19 Feb 2026 06:02:27 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-02-20 15:21:28.717993
- Title: Simplify to Amplify: Achieving Information-Theoretic Bounds with Fewer Steps in Spectral Community Detection
- Title（参考訳）: Simplify to Amplify:Achieving information-theoretic bounds with less steps in Spectral Community Detection
- Authors: Sie Hendrata Dharmawan, Peter Chin,
- Abstract要約: 本稿では,2つのコミュニティブロックモデルにおいて,コミュニティ検出のためのスペクトルの合理化手法を提案する。
本手法は,非定常前処理ステップの除去によるアルゴリズム複雑性の低減により,隣接行列のスペクトル特性を直接活用する。
この結果から,アルゴリズムの単純化は,複雑性を増大させるのではなく,計算効率とスペクトルコミュニティ検出性能の向上に繋がる可能性が示唆された。
- 参考スコア（独自算出の注目度）: 4.486629113012585
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We propose a streamlined spectral algorithm for community detection in the two-community stochastic block model (SBM) under constant edge density assumptions. By reducing algorithmic complexity through the elimination of non-essential preprocessing steps, our method directly leverages the spectral properties of the adjacency matrix. We demonstrate that our algorithm exploits specific characteristics of the second eigenvalue to achieve improved error bounds that approach information-theoretic limits, representing a significant improvement over existing methods. Theoretical analysis establishes that our error rates are tighter than previously reported bounds in the literature. Comprehensive experimental validation confirms our theoretical findings and demonstrates the practical effectiveness of the simplified approach. Our results suggest that algorithmic simplification, rather than increasing complexity, can lead to both computational efficiency and enhanced performance in spectral community detection.
- Abstract（参考訳）: 本研究では, 境界密度の一定条件下での2コミュニティ確率ブロックモデル(SBM)において, コミュニティ検出のための合理化スペクトルアルゴリズムを提案する。
本手法は,非定常前処理ステップの除去によるアルゴリズム複雑性の低減により,隣接行列のスペクトル特性を直接活用する。
提案アルゴリズムは,情報理論の限界に近づいた誤差境界の改善を実現するために,第2の固有値の特性を利用する。
理論的解析により、我々の誤差率は、文献で以前報告された境界よりも厳密であることが示された。
総合的な実験的検証を行い,本手法の有効性を実証した。
この結果から,アルゴリズムの単純化は,複雑性を増大させるのではなく,計算効率とスペクトルコミュニティ検出性能の向上に繋がる可能性が示唆された。
関連論文リスト
- Spectral Algorithms under Covariate Shift [4.349399061959293]
スペクトルアルゴリズムはスペクトル正則化技術を利用してデータを分析・処理する。
トレーニングデータとテストデータの分布が異なる場合のスペクトルアルゴリズムの収束挙動について検討する。
本稿では,密度比情報を学習プロセスに組み込んだ正規化重み付き新しい重み付きスペクトルアルゴリズムを提案する。
論文 参考訳（メタデータ） (2025-04-17T04:02:06Z) - Efficient Model-Free Exploration in Low-Rank MDPs [76.87340323826945]
低ランクマルコフ決定プロセスは、関数近似を持つRLに対して単純だが表現力のあるフレームワークを提供する。
既存のアルゴリズムは、(1)計算的に抽出可能であるか、または(2)制限的な統計的仮定に依存している。
提案手法は,低ランクMPPの探索のための最初の実証可能なサンプル効率アルゴリズムである。
論文 参考訳（メタデータ） (2023-07-08T15:41:48Z) - Bounded Projection Matrix Approximation with Applications to Community
Detection [1.8876415010297891]
我々は,新たな微分可能凸ペナルティを導入し,乗算器の交互方向法(ADMM)を導出する。
数値実験により,アルゴリズムの競争相手に対する優位性を実証した。
論文 参考訳（メタデータ） (2023-05-21T06:55:10Z) - Scalable Bayesian Meta-Learning through Generalized Implicit Gradients [64.21628447579772]
Inlicit Bayesian Meta-learning (iBaML) 法は、学習可能な事前のスコープを広げるだけでなく、関連する不確実性も定量化する。
解析誤差境界は、明示的よりも一般化された暗黙的勾配の精度と効率を示すために確立される。
論文 参考訳（メタデータ） (2023-03-31T02:10:30Z) - Optimal Algorithms for the Inhomogeneous Spiked Wigner Model [89.1371983413931]
不均一な問題に対する近似メッセージパッシングアルゴリズム(AMP)を導出する。
特に,情報理論の閾値よりも大きい信号と雑音の比を必要とする既知のアルゴリズムが,ランダムよりも優れた処理を行うための統計的・計算的ギャップの存在を同定する。
論文 参考訳（メタデータ） (2023-02-13T19:57:17Z) - Reinforcement Learning from Partial Observation: Linear Function Approximation with Provable Sample Efficiency [111.83670279016599]
部分観察決定過程(POMDP)の無限観測および状態空間を用いた強化学習について検討した。
線形構造をもつPOMDPのクラスに対する部分可観測性と関数近似の最初の試みを行う。
論文 参考訳（メタデータ） (2022-04-20T21:15:38Z) - Amortized Implicit Differentiation for Stochastic Bilevel Optimization [53.12363770169761]
決定論的条件と決定論的条件の両方において、二段階最適化問題を解決するアルゴリズムのクラスについて検討する。
厳密な勾配の推定を補正するために、ウォームスタート戦略を利用する。
このフレームワークを用いることで、これらのアルゴリズムは勾配の偏りのない推定値にアクセス可能な手法の計算複雑性と一致することを示す。
論文 参考訳（メタデータ） (2021-11-29T15:10:09Z) - Deep Unfolding of Iteratively Reweighted ADMM for Wireless RF Sensing [22.467957268653077]
我々は,MIMO無線レーダを用いた層状材料構造中の材料欠陥の検出に対処する。
多くのシナリオでは、階層構造に挑戦する欠陥の数は、低ランク構造としてモデル化できる。
論文 参考訳（メタデータ） (2021-06-07T15:00:33Z) - Jointly Modeling and Clustering Tensors in High Dimensions [6.072664839782975]
テンソルの合同ベンチマークとクラスタリングの問題を考察する。
本稿では,統計的精度の高い近傍に幾何的に収束する効率的な高速最適化アルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-04-15T21:06:16Z) - Consistency of Anchor-based Spectral Clustering [0.0]
アンカーベースの手法は、スペクトルクラスタリングアルゴリズムの計算複雑性を低減する。
厳密な分析が可能であり,実践に有効であることを示す。
我々はChenとCaiの最先端のLCC法と競合することが判明した。
論文 参考訳（メタデータ） (2020-06-24T18:34:41Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。