論文の概要: Non-Adaptive Learning of Sparse Erdős--Rényi Graphs via Affine Splitting

• arxiv url: http://arxiv.org/abs/2609.33704v1
• Date: Sun, 27 Sep 2026 16:07:15 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-04 17:30:47.837578
• Title: Non-Adaptive Learning of Sparse Erdős--Rényi Graphs via Affine Splitting
• Title（参考訳）: アフィン分割によるスパースエルデシュ-レーニグラフの非適応学習
• Abstract要約: 我々は、全てのクエリが、結果が観測される前に固定される非適応的なスキームについて研究する。 我々のスキームは$O(barklog n)$クエリを使用し、$O(barklog n)$ decoding timeで正確なリカバリを実現する。 これにより、以前の$O(bark1+log n)$ decoding guarantee for any fixed $>0$, while maintain the same query order。
• 参考スコア（独自算出の注目度）: 1.0152838128195467
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Graph learning from edge-detecting queries concerns the reconstruction of an unknown edge set on a known vertex set. Each query reports whether a specified vertex subset contains at least one edge. We study non-adaptive schemes, in which all queries are fixed before any outcomes are observed, with the goal of achieving exact recovery using few queries and fast decoding. For general graphs on $n$ vertices with at most $k$ edges, non-adaptive recovery requires $Ω(\min\{k^2\log n,n^2\})$ queries in the worst case, even when a small error probability is allowed. In this paper, we consider Erdős--Rényi ($\mathrm{ER}$) graphs $G\sim \mathrm{ER}(n,q)$, with expected edge count $\bar{k}=q\binom{n}{2}$. Our scheme uses $O(\bar{k}\log n)$ queries and achieves exact recovery in $O(\bar{k}\log n)$ decoding time with probability tending to one throughout the regime $\bar{k}\to\infty$ and $\bar{k}=o(n^2)$. This improves the previous $O(\bar{k}^{1+δ}\log n)$ decoding guarantee for any fixed $δ>0$, while maintaining the same query order. The guarantee also extends beyond the previously studied regime $\bar{k}=Θ(n^{2θ})$ with fixed $θ\in(0,1)$. Our approach builds on the binary splitting method used in prior work, which organizes vertices into a hierarchy of successively smaller groups. We introduce three main changes: (i) we use random affine hash functions over a finite field to process each candidate pair in constant time; (ii) we apply the splitting procedure directly to the full graph, avoiding the need to combine solutions to multiple smaller graph-learning subproblems; and (iii) we bound the total decoding workload directly rather than deriving separate high-probability bounds on candidate counts at each level.
• Abstract（参考訳）: エッジ検出クエリからのグラフ学習は、既知の頂点セット上の未知のエッジセットの再構築に関するものだ。 各クエリは、指定された頂点サブセットが少なくとも1つのエッジを含むかどうかをレポートする。 提案手法は,任意の結果が観測される前に全てのクエリが固定される非適応型スキームについて検討し,クエリを少なくして正確なリカバリを実現し,高速な復号化を実現することを目的とする。 頂点が少なくとも$k$であるような$n$の頂点上の一般的なグラフに対して、非適応的回復は、たとえ小さなエラー確率が許されたとしても、最悪の場合において$Ω(\min\{k^2\log n,n^2\})$クエリを必要とする。 この論文では、エルデシュ=レーニ(英語版)$\mathrm{ER}$)グラフが$G\sim \mathrm{ER}(n,q)$であり、予想される辺数は$\bar{k}=q\binom{n}{2}$である。 我々のスキームは$O(\bar{k}\log n)$クエリを使用し、$O(\bar{k}\log n)$ decoding time with probability tending one to the regime $\bar{k}\to\infty$ and $\bar{k}=o(n^2)$で正確なリカバリを達成する。 これにより、以前の$O(\bar{k}^{1+δ}\log n)$ decoding guarantee for any fixed $δ>0$, while maintain the same query order。 この保証はまた、以前に研究された体制である $\bar{k}=(n^{2θ})$ に固定された $θ\in(0,1)$ を超えても拡張される。 提案手法は,先行作業で使用される二分分割法に基づいて,頂点を連続的に小さなグループの階層に整理する。 主な変更点は3つあります。 i) 有限体上のランダムなアフィンハッシュ関数を用いて、各候補ペアを一定時間に処理する。 (二)分割手順を全グラフに直接適用し、より小さなグラフ学習サブプロブレムに解を組み合わせる必要をなくす。 (3)各レベルにおける候補数に対する個別の高確率境界を導出するのではなく,総復号処理量を直接拘束する。

関連論文リスト

• Dense Weak Hiding: Closing Complexity Gaps in Nonconvex and PL Finite-Sum Optimization under Individual Smoothness [8.428362872515416]
  我々は、各$_maxgeq 3$に対して、個々の滑らかさの下で下界に一致することを証明した。 また、各$_maxgeq 3$に対して、個々の滑らかさの下で下界が一致することを証明する。
  論文  参考訳（メタデータ） (2026-08-30T02:47:24Z)
• Achieving Almost Exact Recovery in Almost Quadratic Time: Rank-Based Graph Matching via Local Tree Correlation Tests [27.444325804941773]
  本稿では,相関した $textErds-Rényi$ (ER) グラフペアモデルに基づくグラフマッチングについて検討する。 本稿では,n2+o(1)の時間複雑性を持つグラフマッチングアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2026-07-10T04:08:08Z)
• Faster quantum linear system solver beyond the condition number [50.84794327094274]
  線形系の正規化解 $|xrangle$ を生成する2つの量子アルゴリズムを、条件数$=lVert A-1rVert$ に依存しない複雑性を持つ精度 $Ax=| b rangle$ に提示する。 フィルタベースのソルバは非常にシンプルで、実行時プレファクタが適しています。
  論文  参考訳（メタデータ） (2026-07-08T17:49:40Z)
• A Fast Binary Splitting Approach for Non-Adaptive Learning of Erdős--Rényi Graphs [33.51066694357509]
  ノードサブセット上のグループクエリを用いて未知のグラフを学習する問題について検討し、各クエリは、クエリされたノード間に少なくとも1つのエッジが存在するかどうかを報告する。 Erds--Rényi (ER) graphs $GsimmathrmER(n,q)$ in the non-adaptive set, where the expected number of edges is $bark=qbinomn2$。 我々は、最近非適応型グループテストのために開発されたバイナリ分割アプローチをERグラフ設定に拡張し、それを証明した。
  論文  参考訳（メタデータ） (2025-11-21T13:34:29Z)
• 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)
• On the Unlikelihood of D-Separation [69.62839677485087]
  解析的な証拠として、大きなグラフ上では、d-分離は存在が保証されたとしても珍しい現象である。 PCアルゴリズムでは、その最悪ケース保証がスパースグラフで失敗することが知られているが、平均ケースでも同じことが言える。 UniformSGSでは、既存のエッジに対してランニング時間が指数的であることが知られているが、平均的な場合、それは既存のほとんどのエッジにおいても期待されるランニング時間であることを示す。
  論文  参考訳（メタデータ） (2023-03-10T00:11:18Z)
• Fast Graph Sampling for Short Video Summarization using Gershgorin Disc Alignment [52.577757919003844]
  高速グラフサンプリングの最近の進歩を利用して,短い動画を複数の段落に効率よく要約する問題について検討する。 実験結果から,本アルゴリズムは最先端の手法と同等の映像要約を実現し,複雑さを大幅に低減した。
  論文  参考訳（メタデータ） (2021-10-21T18:43:00Z)
• Private Stochastic Convex Optimization: Optimal Rates in $\ell_1$ Geometry [69.24618367447101]
  対数要因まで $(varepsilon,delta)$-differently private の最適過剰人口損失は $sqrtlog(d)/n + sqrtd/varepsilon n.$ です。 損失関数がさらなる滑らかさの仮定を満たすとき、余剰損失は$sqrtlog(d)/n + (log(d)/varepsilon n)2/3で上界(対数因子まで)であることが示される。
  論文  参考訳（メタデータ） (2021-03-02T06:53:44Z)
• Agnostic Q-learning with Function Approximation in Deterministic Systems: Tight Bounds on Approximation Error and Sample Complexity [94.37110094442136]
  本稿では,決定論的システムにおける関数近似を用いたQ$学習の問題について検討する。 もし$delta = Oleft(rho/sqrtdim_Eright)$なら、$Oleft(dim_Eright)$を使って最適なポリシーを見つけることができる。
  論文  参考訳（メタデータ） (2020-02-17T18:41:49Z)

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

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