論文の概要: A Fast Binary Splitting Approach for Non-Adaptive Learning of Erdős--Rényi Graphs

• arxiv url: http://arxiv.org/abs/2511.17240v2
• Date: Mon, 24 Nov 2025 03:13:19 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-11-25 16:30:37.513492
• Title: A Fast Binary Splitting Approach for Non-Adaptive Learning of Erdős--Rényi Graphs
• Title（参考訳）: Erdés--Rényiグラフの非適応学習のための高速バイナリ分割手法
• Authors: Hoang Ta, Jonathan Scarlett,
• Abstract要約: ノードサブセット上のグループクエリを用いて未知のグラフを学習する問題について検討し、各クエリは、クエリされたノード間に少なくとも1つのエッジが存在するかどうかを報告する。 Erds--Rényi (ER) graphs $GsimmathrmER(n,q)$ in the non-adaptive set, where the expected number of edges is $bark=qbinomn2$。 我々は、最近非適応型グループテストのために開発されたバイナリ分割アプローチをERグラフ設定に拡張し、それを証明した。
• 参考スコア（独自算出の注目度）: 33.51066694357509
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study the problem of learning an unknown graph via group queries on node subsets, where each query reports whether at least one edge is present among the queried nodes. In general, learning arbitrary graphs with $n$ nodes and $k$ edges is hard in the non-adaptive setting, requiring $Ω\big(\min\{k^2\log n,\,n^2\}\big)$ tests even when a small error probability is allowed. We focus on learning Erdős--Rényi (ER) graphs $G\sim\mathrm{ER}(n,q)$ in the non-adaptive setting, where the expected number of edges is $\bar{k}=q\binom{n}{2}$, and we aim to design an efficient testing--decoding scheme achieving asymptotically vanishing error probability. Prior work (Li--Fresacher--Scarlett, NeurIPS 2019) presents a testing--decoding scheme that attains an order-optimal number of tests $O(\bar{k}\log n)$ but incurs $Ω(n^2)$ decoding time, whereas their proposed sublinear-time algorithm incurs an extra $(\log \bar{k})(\log n)$ factor in the number of tests. We extend the binary splitting approach, recently developed for non-adaptive group testing, to the ER graph learning setting, and prove that the edge set can be recovered with high probability using $O(\bar{k}\log n)$ tests while attaining decoding time $O(\bar{k}^{1+δ}\log n)$ for any fixed $δ>0$.
• Abstract（参考訳）: ノードサブセット上のグループクエリを用いて未知のグラフを学習する問題について検討し、各クエリは、クエリされたノード間に少なくとも1つのエッジが存在するかどうかを報告する。 一般に、$n$ノードと$k$エッジを持つ任意のグラフを学ぶことは非適応的な設定では困難であり、小さな誤差確率が許される場合でも、$Ω\big(\min\{k^2\log n,\,n^2\}\big)$テストを必要とする。 我々は、予測されるエッジの数が$\bar{k}=q\binom{n}{2}$である非適応的セッティングにおいて、Erdés--Rényi (ER)グラフを学習することに集中し、漸近的にエラー確率を減少させる効率的なテスト-デコードスキームを設計することを目指している。 我々は、最近、非適応型グループテストのために開発されたバイナリ分割アプローチをERグラフ学習設定に拡張し、任意の固定された$δ>0$に対して、復号時間$O(\bar{k}^{1+δ}\log n)$に達しながら、$O(\bar{k}\log n)$テストを用いてエッジセットを高い確率で復元できることを証明した。

関連論文リスト

• Improved Robust Estimation for Erdős-Rényi Graphs: The Sparse Regime and Optimal Breakdown Point [3.793609515750114]
  我々は、ErdHos-R'enyiランダムグラフのエッジ密度を強く推定する問題を、$G(n, dcirc/n)$で検討する。 我々のアルゴリズムは2乗の総和階層に基づいている。
  論文  参考訳（メタデータ） (2025-03-05T21:45:17Z)
• Provable Scaling Laws for the Test-Time Compute of Large Language Models [84.00141420901038]
  本研究では,大規模言語モデルのテスト時間計算において,証明可能なスケーリング法則を享受する2つのアルゴリズムを提案する。 1つは2段階ノックアウト方式のアルゴリズムで、各候補は複数の相手に対して平均勝利率で評価される。 もう1つは2段階のリーグ方式のアルゴリズムで、各候補は複数の相手に対して平均勝利率で評価される。
  論文  参考訳（メタデータ） (2024-11-29T05:29:47Z)
• Finite-Time Error Bounds for Greedy-GQ [20.51105692499517]
  We show that Greedy-GQ algorithm converges fast-time error。 我々の分析は、ステップサイズを選択するために、より高速な収束ステップサイズを提供する。
  論文  参考訳（メタデータ） (2022-09-06T15:04:57Z)
• Inferring Hidden Structures in Random Graphs [13.031167737538881]
  本研究では,ランダムなグラフ上に植えられた群集群集の検出と復元の2つの推論問題について検討する。 我々は、パラメータ $(n,k,q)$ や $Gamma_k$ の特定の性質の観点から、構造を検出・復元するための下限を導出し、これらの下限を達成するための計算学的に最適なアルゴリズムを示す。
  論文  参考訳（メタデータ） (2021-10-05T09:39:51Z)
• Random Subgraph Detection Using Queries [29.192695995340653]
  植込み高密度部分グラフ検出問題は、与えられた(ランダム)グラフに異常に密度の高い部分グラフが存在するかどうかをテストするタスクを指す。 本稿では,適応的なエッジクエリを用いてグラフの比較的小さな部分のみを観測できる,上記の問題の自然な変形について考察する。 このモデルでは,植込み部分グラフの存在を検出するのに必要なクエリ数と十分なクエリ数(準多項式最適アルゴリズムを伴う)を決定する。
  論文  参考訳（メタデータ） (2021-10-02T07:41:17Z)
• Random Graph Matching with Improved Noise Robustness [2.294014185517203]
  本稿では確率モデルに基づくグラフマッチングの新しいアルゴリズムを提案する。 我々のアルゴリズムは、$alpha le 1 / (log log n)C$ のとき、その基礎となるマッチングを高い確率で復元する。 これにより、以前の作業で達成された条件 $alpha le 1 / (log n)C$ が改善される。
  論文  参考訳（メタデータ） (2021-01-28T02:39:27Z)
• Optimal network online change point localisation [73.93301212629231]
  オンラインネットワーク変化点検出の問題点について検討する。 この設定では、独立したベルヌーイネットワークの集合が順次収集され、基礎となる変化点が生じる。 目的は、虚偽のアラームの数または確率の制約に応じて、それが存在する場合、変更点をできるだけ早く検出することです。
  論文  参考訳（メタデータ） (2021-01-14T07:24:39Z)
• Adversarial Linear Contextual Bandits with Graph-Structured Side Observations [80.95090605985042]
  学習エージェントは、$d$-dimensionalコンテキストベクトルで提示された後、一連の$k$アクションから繰り返し選択する。 エージェントは選択されたアクションの損失を誘発し、観察するが、観察構造における隣り合うアクションの損失も観察する。 textttEXP3に基づく2つの効率的なアルゴリズムが開発された。
  論文  参考訳（メタデータ） (2020-12-10T15:40:07Z)
• Hybrid Stochastic-Deterministic Minibatch Proximal Gradient: Less-Than-Single-Pass Optimization with Nearly Optimal Generalization [83.80460802169999]
  HSDMPGは、学習モデル上で過大なエラーの順序である$mathcalObig(1/sttnbig)$を達成可能であることを示す。 損失係数について、HSDMPGは学習モデル上で過大なエラーの順序である$mathcalObig(1/sttnbig)$を達成できることを示す。
  論文  参考訳（メタデータ） (2020-09-18T02:18:44Z)

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

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