論文の概要: Detection of local geometry in random graphs: information-theoretic and computational limits
- arxiv url: http://arxiv.org/abs/2603.24545v1
- Date: Wed, 25 Mar 2026 17:20:01 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-03-26 21:06:11.407292
- Title: Detection of local geometry in random graphs: information-theoretic and computational limits
- Title（参考訳）: ランダムグラフにおける局所幾何学の検出:情報理論と計算限界
- Authors: Jinho Bok, Shuangping Li, Sophie H. Yu,
- Abstract要約: ランダムグラフにおける局所幾何学の検出問題について検討する。
平均サイズ$k$の隠れコミュニティがランダムな幾何グラフとして描画されるようなモデル$mathcalG(n, p, d, k)$を導入する。
残りのすべての辺はアーズ=レーニモデル $mathcalG(n, p)$ に従う。
- 参考スコア（独自算出の注目度）: 4.67223325681232
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study the problem of detecting local geometry in random graphs. We introduce a model $\mathcal{G}(n, p, d, k)$, where a hidden community of average size $k$ has edges drawn as a random geometric graph on $\mathbb{S}^{d-1}$, while all remaining edges follow the Erdős--Rényi model $\mathcal{G}(n, p)$. The random geometric graph is generated by thresholding inner products of latent vectors on $\mathbb{S}^{d-1}$, with each edge having marginal probability equal to $p$. This implies that $\mathcal{G}(n, p, d, k)$ and $\mathcal{G}(n, p)$ are indistinguishable at the level of the marginals, and the signal lies entirely in the edge dependencies induced by the local geometry. We investigate both the information-theoretic and computational limits of detection. On the information-theoretic side, our upper bounds follow from three tests based on signed triangle counts: a global test, a scan test, and a constrained scan test; our lower bounds follow from two complementary methods: truncated second moment via Wishart--GOE comparison, and tensorization of KL divergence. These results together settle the detection threshold at $d = \widetildeΘ(k^2 \vee k^6/n^3)$ for fixed $p$, and extend the state-of-the-art bounds from the full model (i.e., $k = n$) for vanishing $p$. On the computational side, we identify a computational--statistical gap and provide evidence via the low-degree polynomial framework, as well as the suboptimality of signed cycle counts of length $\ell \geq 4$.
- Abstract（参考訳）: ランダムグラフにおける局所幾何学の検出問題について検討する。
モデル $\mathcal{G}(n, p, d, k)$ を導入すると、平均サイズ $k$ の隠れたコミュニティは、$\mathbb{S}^{d-1}$ 上のランダムな幾何学グラフとして描画されるが、残りのすべてのエッジはエルデシュ-レーニモデル $\mathcal{G}(n, p)$ に従う。
ランダム幾何グラフは、潜在ベクトルの内部積を$\mathbb{S}^{d-1}$でしきい値にすることで生成される。
これは、$\mathcal{G}(n, p, d, k)$ と $\mathcal{G}(n, p)$ が辺辺のレベルで区別不能であり、信号は局所幾何学によって誘導されるエッジ依存に完全に属していることを意味する。
本稿では,情報理論と計算的検出の限界について検討する。
情報理論面では、我々の上界は、符号付き三角形数に基づく3つのテスト、すなわち、大域的テスト、スキャンテスト、制約付きスキャンテスト、および下限は、Wishart--GOE比較による2つの相補的な方法、KLの発散のテンソル化の2つから従う。
これらの結果は共に$d = \widetilde'(k^2 \vee k^6/n^3)$ for fixed $p$で検出しきい値に落ち着き、全モデル(すなわち$k = n$)から、$p$を消すための最先端境界を拡張する。
計算面では,計算統計的ギャップを同定し,低次多項式フレームワークによる証明と,符号付きサイクル数の長さが$$\ell \geq 4$であることを示す。
関連論文リスト
- 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) - Neural network learns low-dimensional polynomials with SGD near the information-theoretic limit [75.4661041626338]
単一インデックス対象関数 $f_*(boldsymbolx) = textstylesigma_*left(langleboldsymbolx,boldsymbolthetarangleright)$ の勾配勾配勾配学習問題について検討する。
SGDに基づくアルゴリズムにより最適化された2層ニューラルネットワークは、情報指数に支配されない複雑さで$f_*$を学習する。
論文 参考訳（メタデータ） (2024-06-03T17:56:58Z) - Provably learning a multi-head attention layer [55.2904547651831]
マルチヘッドアテンション層は、従来のフィードフォワードモデルとは分離したトランスフォーマーアーキテクチャの重要な構成要素の1つである。
本研究では,ランダムな例から多面的注意層を実証的に学習する研究を開始する。
最悪の場合、$m$に対する指数的依存は避けられないことを示す。
論文 参考訳（メタデータ） (2024-02-06T15:39:09Z) - 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) - Planted Bipartite Graph Detection [13.95780443241133]
ランダムグラフに隠れた二部グラフを検出するタスクについて検討する。
ヌル仮説の下では、このグラフは、エッジ密度$q$の$n$上のアードホスラーイランダムグラフの実現である。
k_mathsfR times k_mathsfL$ bipartite subgraph with edge density $p>q$。
論文 参考訳（メタデータ） (2023-02-07T18:18:17Z) - Random Graph Matching in Geometric Models: the Case of Complete Graphs [21.689343447798677]
本稿では, エッジ重み付き2つの完全グラフが潜在測地によって相関する問題について検討する。
近似最大極大推定器を導出し、高い確率で$pi*$の完全回復を確実に達成する。
副次的な発見として、[Ume88] の有望なスペクトルアルゴリズムが幾何モデルにおける最大可能性のさらなる近似として現れることを示す。
論文 参考訳（メタデータ） (2022-02-22T04:14:45Z) - Random Subgraph Detection Using Queries [29.192695995340653]
植込み高密度部分グラフ検出問題は、与えられた(ランダム)グラフに異常に密度の高い部分グラフが存在するかどうかをテストするタスクを指す。
本稿では,適応的なエッジクエリを用いてグラフの比較的小さな部分のみを観測できる,上記の問題の自然な変形について考察する。
このモデルでは,植込み部分グラフの存在を検出するのに必要なクエリ数と十分なクエリ数(準多項式最適アルゴリズムを伴う)を決定する。
論文 参考訳（メタデータ） (2021-10-02T07:41:17Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。