論文の概要: Query-Limited Community Recovery in Stochastic Block Models

• arxiv url: http://arxiv.org/abs/2606.02055v1
• Date: Mon, 01 Jun 2026 10:44:00 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-06-02 21:34:31.872626
• Title: Query-Limited Community Recovery in Stochastic Block Models
• Title（参考訳）: 確率ブロックモデルにおけるクエリ制限付きコミュニティリカバリ
• Authors: Sabyasachi Basu, Manuj Mukherjee, Lutz Oettershagen, Suhas Thejaswi,
• Abstract要約: 我々は,ネットワークデータへのアクセスが制限されうる条件下で,$n$の頂点上での2つのコミュニティブロックモデルにおけるコミュニティの正確な回復について検討した。 我々は、オラクルのみのアクセスと、学習者が基礎となるグラフの1つのサブサンプルコピーを観察する統合モデルを考える。 2段階の適応戦略が$n+o(n)$クエリで成功することを示す。
• 参考スコア（独自算出の注目度）: 6.498092697159669
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study exact community recovery in the two-community stochastic block model on $n$ vertices under limited and noisy access to network data. The learner may query a noisy neighborhood oracle that reveals each true neighbor of a queried vertex independently with fixed probability and never returns non-neighbors, subject to a finite query budget. We consider both oracle-only access and a combined model where the learner also observes a single subsampled copy of the underlying graph. For oracle-only access, balanced uniform querying gives a sharp non-adaptive benchmark: when each vertex is queried the same integer number of times, the observations reduce to an SBM with attenuated edge probabilities and the Abbe-Bandeira-Hall exact-recovery threshold applies. We show that this benchmark is not adaptively optimal: a two-stage adaptive strategy succeeds with $n+o(n)$ queries in a regime where balanced uniform querying requires $m n$ queries for some $m>1$. With an additional subsampled graph, we prove a sublinear-query adaptivity gap: balanced data-independent uniform querying with a sublinear budget does not improve over the subsampled graph alone, whereas adaptive querying can target a small set of uncertain vertices and achieve exact recovery. Thus adaptive data acquisition can strictly improve the information-theoretic limits of exact recovery.
• Abstract（参考訳）: 本研究では,2つのコミュニティ確率ブロックモデルにおけるコミュニティの正確な回復を,限定的かつノイズの多いネットワークデータアクセスの下で,$n$の頂点上で検討する。 学習者は、特定の確率でクエリされた頂点の各真の隣人を独立して明らかにするノイズの多い近所のオラクルを問い合わせることができ、有限なクエリ予算を条件として隣人を返すことはない。 我々は、オラクルのみのアクセスと、学習者が基礎となるグラフの1つのサブサンプルコピーを観察する統合モデルを考える。 オラクルのみのアクセスの場合、バランスの取れた均一なクエリは、鋭い非適応的なベンチマークを与える: それぞれの頂点が同じ整数数回クエリされると、観測は減衰したエッジ確率を持つSBMに減少し、Abe-Bandeira-Hallの正確な回復しきい値が適用される。 このベンチマークは適応的に最適でないことを示す: 2段階の適応戦略は、バランスの取れた均一なクエリが約$m>1$に対して$m n$クエリを必要とする状態において$n+o(n)$クエリで成功する。 サブサンプルグラフを付加することにより、サブライン・クエリ適応性ギャップが証明される: サブラインの予算とのバランスのないデータ独立な一様クエリは、サブサンプルグラフだけでは改善されないが、アダプティブクエリは、少数の不確実な検証をターゲットとし、正確な回復を達成することができる。 したがって、適応データ取得は、正確な回復の情報理論的限界を厳密に改善することができる。

関連論文リスト

• Post-Training with Policy Gradients: Optimality and the Base Model Barrier [27.674563695368665]
  結果とプロセス報酬を伴う線形自己回帰モデルの訓練後評価について検討する。 我々は、ポリシー勾配(PG)の変種が、本質的に最小限の報酬クエリ数を持つ1-varepsilon$を実現できることを証明した。
  論文  参考訳（メタデータ） (2026-03-07T00:25:53Z)
• Non-Stationary Online Resource Allocation: Learning from a Single Sample [5.81028169940199]
  最低限のオフラインデータ要求で,非定常要求下でのオンラインリソース割り当てについて検討する。 本稿では,この問題をモジュラーコンポーネントに分解する,型依存型量子型メタ政治を提案する。
  論文  参考訳（メタデータ） (2026-02-20T10:07:35Z)
• Almost Asymptotically Optimal Active Clustering Through Pairwise Observations [59.20614082241528]
  そこで本研究では, ノイズと能動的に収集された応答を用いて, M$アイテムを未知数の$K$個別グループにクラスタリングするための新しい分析フレームワークを提案する。 クラスタリングの精度に対する望ましい信頼性を達成するのに必要なクエリ数の基本的下位境界を確立する。 我々は、一般化された同値比統計の計算可能な変種を開発し、その下限に対する性能ギャップを正確に推定できることを実証的に示す。
  論文  参考訳（メタデータ） (2026-02-05T14:16:47Z)
• 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)
• Optimal and exact recovery on general non-uniform Hypergraph Stochastic Block Model [0.0]
  非一様ハイパーグラフ化ブロックモデル(HSBM)に基づくランダムハイパーグラフにおけるコミュニティ検出問題の検討 文献ではじめて、この一様でないケース下での正確な回復のための鋭いしきい値が、小さな制約の下で確立された。 しきい値を超えると正確な回復を達成でき、正確な回復が不可能な場合には最小の確率で達成できる2つの効率的なアルゴリズムを提供する。
  論文  参考訳（メタデータ） (2023-04-25T20:30:33Z)
• Optimal Clustering with Bandit Feedback [57.672609011609886]
  本稿では,バンディットフィードバックを用いたオンラインクラスタリングの問題点について考察する。 これは、NPハード重み付きクラスタリング問題をサブルーチンとして解決する必要性を回避するための、シーケンシャルなテストのための新しい停止規則を含む。 合成および実世界のデータセットの広範なシミュレーションを通して、BOCの性能は下界と一致し、非適応的ベースラインアルゴリズムよりも大幅に優れることを示す。
  論文  参考訳（メタデータ） (2022-02-09T06:05:05Z)
• Non-Adaptive Adaptive Sampling on Turnstile Streams [57.619901304728366]
  カラムサブセット選択、部分空間近似、射影クラスタリング、および空間サブリニアを$n$で使用するターンタイルストリームのボリュームに対する最初の相対エラーアルゴリズムを提供する。 我々の適応的なサンプリング手法は、様々なデータ要約問題に多くの応用をもたらしており、これは最先端を改善するか、より緩和された行列列モデルで以前に研究されただけである。
  論文  参考訳（メタデータ） (2020-04-23T05:00:21Z)

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

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