論文の概要: Recovery thresholds for hidden weighted sparse graphs

• arxiv url: http://arxiv.org/abs/2606.14335v1
• Date: Fri, 12 Jun 2026 10:44:19 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-06-15 16:00:42.866518
• Title: Recovery thresholds for hidden weighted sparse graphs
• Title（参考訳）: 隠れ重み付きスパースグラフの回復しきい値
• Authors: Zhe Hou, Jingcheng Liu,
• Abstract要約: ランダムな重み付き完全グラフに隠されたグラフの回復しきい値について検討する。 ベルヌーイ系と指数型系では、オール・オー・ノーシング(AoN)しきい値現象を示すことができる。
• 参考スコア（独自算出の注目度）: 1.7159633200689228
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Recovering structural information from noisy high-dimensional data is a fundamental task in statistical inference. We investigate the recovery thresholds for a graph hidden in a randomly weighted complete graph. Specifically, an unknown graph $H^* \in H_n$ is chosen uniformly at random, and hidden in a complete graph of $n$ vertices as follows: the weight of an edge $e \in H$ is distributed independently according to $P_n$; otherwise the weight is distributed independently according to $Q_n$. The goal is to recover almost all of $H$ from these edge weights. Assuming a local Lipschitzness of the Rényi divergence between distributions $P_n$ and $Q_n$, and a mild density condition for the graphs $H_n$, we give a unified characterization of the information-theoretic limit for recovering almost all of $H$ (also known as almost exact recovery). Our characterization connects the KL divergence between $P_n$ and $Q_n$ to the logarithm of the first moment threshold of $H$ in the Erdős-Rényi random graph model $G(n,p)$. Our lower bound also extends to the task of partial recovery, in which only a constant $λ$-fraction of $H$ needs to be recovered. Last but not least, for certain Bernoulli and Exponential regimes, and for Gaussian distributions, we are able to show an All-or-Nothing (AoN) threshold phenomenon at the exponential scale.
• Abstract（参考訳）: ノイズの多い高次元データから構造情報を復元することは、統計的推測の基本的な課題である。 ランダムな重み付き完全グラフに隠されたグラフの回復しきい値について検討する。 具体的には、未知のグラフ $H^* \in H_n$ がランダムに一様に選択され、以下に示すように$n$頂点の完全なグラフに隠れる: エッジ $e \in H$ の重みは$P_n$ に従って独立に分布する。 目標は、これらのエッジウェイトからほぼすべての$H$を回収することだ。 分布 $P_n$ と $Q_n$ の間のレニイ微分の局所的なリプシッツ性とグラフ $H_n$ に対する穏やかな密度条件を仮定すると、ほぼすべての$H$(ほぼ正確な回復)を回復する情報理論の極限を統一的に特徴づける。 我々の特徴づけは、KL の$P_n$ と $Q_n$ の発散を、エルデシュ=レーニのランダムグラフモデル $G(n,p)$ の最初のモーメント閾値の対数に結びつける。 我々の下限は部分的回復のタスクにまで拡張され、そこでは$H$の定数$λ$-fractionだけを回復する必要がある。 最後に、ベルヌーイと指数系、およびガウス分布について、指数スケールでオール・オー・ナッシング(AoN)しきい値現象を示すことができる。

関連論文リスト

• How Neural Reward Models Learn Features for Policy Optimization: A Single-Index Analysis [53.063298916923976]
  r*(x) = *(langle *, xrangle)$ と $x sim N(0, I_d)$ でガウスの単一インデックスモデルでフィードバックを研究する。 まず、報酬重み付きサンプルから隠れた方向を*$で学習し、次に重み付きリッジ回帰により読み出し層に適合する2段階のニューラル報酬モデルを分析する。
  論文  参考訳（メタデータ） (2026-05-23T22:00:38Z)
• Joint estimation of smooth graph signals from partial linear measurements [5.2395896768723045]
  弱い一貫性は、個々の$G_t$sが非常に疎結合で非連結である場合でも、$G$の特定の選択に対して確立される。 結果は、$x_t$が$n$アイテムのコレクションの潜在強度に対応するマルチレイヤのランキング問題に拡張される。
  論文  参考訳（メタデータ） (2025-05-29T08:41:45Z)
• Detecting Arbitrary Planted Subgraphs in Random Graphs [7.320365821066746]
  本稿では,ErdHos-R'enyi乱数グラフ$mathcalG(n, q_n)$における仮設植木部分グラフ$Gamma = Gamma_n$の検出について検討する。 エッジ確率が$p_n$と$q_n$が固定された高密度な状態では、Gamma$を検出するための情報理論および計算しきい値が強く特徴付けられる。
  論文  参考訳（メタデータ） (2025-03-24T18:54:43Z)
• A Unified Framework for Uniform Signal Recovery in Nonlinear Generative Compressed Sensing [68.80803866919123]
  非線形測定では、ほとんどの先行結果は一様ではない、すなわち、すべての$mathbfx*$に対してではなく、固定された$mathbfx*$に対して高い確率で保持される。 本フレームワークはGCSに1ビット/一様量子化観測と単一インデックスモデルを標準例として適用する。 また、指標集合が計量エントロピーが低い製品プロセスに対して、より厳密な境界を生み出す濃度不等式も開発する。
  論文  参考訳（メタデータ） (2023-09-25T17:54:19Z)
• Detection of Dense Subhypergraphs by Low-Degree Polynomials [72.4451045270967]
  ランダムグラフにおける植込み高密度部分グラフの検出は、基本的な統計的および計算上の問題である。 我々は、$Gr(n, n-beta)ハイパーグラフにおいて、植えた$Gr(ngamma, n-alpha)$ subhypergraphの存在を検出することを検討する。 平均値の減少に基づく硬さが不明な微妙な対数密度構造を考えると,この結果はグラフの場合$r=2$で既に新しくなっている。
  論文  参考訳（メタデータ） (2023-04-17T10:38:08Z)
• On the Unlikelihood of D-Separation [69.62839677485087]
  解析的な証拠として、大きなグラフ上では、d-分離は存在が保証されたとしても珍しい現象である。 PCアルゴリズムでは、その最悪ケース保証がスパースグラフで失敗することが知られているが、平均ケースでも同じことが言える。 UniformSGSでは、既存のエッジに対してランニング時間が指数的であることが知られているが、平均的な場合、それは既存のほとんどのエッジにおいても期待されるランニング時間であることを示す。
  論文  参考訳（メタデータ） (2023-03-10T00:11:18Z)
• Causal Bandits for Linear Structural Equation Models [58.2875460517691]
  本稿では,因果図形モデルにおける最適な介入順序を設計する問題について検討する。 グラフの構造は知られており、ノードは$N$である。 頻繁性(UCBベース)とベイズ的設定に2つのアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-08-26T16:21:31Z)
• Causal Inference Despite Limited Global Confounding via Mixture Models [4.721845865189578]
  そのようなモデルの有限$k$-mixtureは、図式的により大きなグラフで表される。 空でないDAGの混合を学習するための最初のアルゴリズムを与える。
  論文  参考訳（メタデータ） (2021-12-22T01:04:50Z)
• Agnostic Learning of a Single Neuron with Gradient Descent [92.7662890047311]
  期待される正方形損失から、最も適合した単一ニューロンを学習することの問題点を考察する。 ReLUアクティベーションでは、我々の人口リスク保証は$O(mathsfOPT1/2)+epsilon$である。 ReLUアクティベーションでは、我々の人口リスク保証は$O(mathsfOPT1/2)+epsilon$である。
  論文  参考訳（メタデータ） (2020-05-29T07:20:35Z)

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

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