論文の概要: Statistical-computational gap in multiple Gaussian graph alignment

• arxiv url: http://arxiv.org/abs/2512.00610v1
• Date: Sat, 29 Nov 2025 19:52:12 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-12-02 19:46:34.322572
• Title: Statistical-computational gap in multiple Gaussian graph alignment
• Title（参考訳）: 多重ガウスグラフアライメントにおける統計的-計算的ギャップ
• Authors: Bertrand Even, Luca Ganassali,
• Abstract要約: 複数のガウスグラフアライメントにおける統計的-計算的ギャップの存在について検討する。 相関$$が1ドル未満のとき、対数項まで、低次非自明な推定は失敗する。
• 参考スコア（独自算出の注目度）: 30.808382005699055
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We investigate the existence of a statistical-computational gap in multiple Gaussian graph alignment. We first generalize a previously established informational threshold from Vassaux and Massoulié (2025) to regimes where the number of observed graphs $p$ may also grow with the number of nodes $n$: when $p \leq O(n/\log(n))$, we recover the results from Vassaux and Massoulié (2025), and $p \geq Ω(n/\log(n))$ corresponds to a regime where the problem is as difficult as aligning one single graph with some unknown "signal" graph. Moreover, when $\log p = ω(\log n)$, the informational thresholds for partial and exact recovery no longer coincide, in contrast to the all-or-nothing phenomenon observed when $\log p=O(\log n)$. Then, we provide the first computational barrier in the low-degree framework for (multiple) Gaussian graph alignment. We prove that when the correlation $ρ$ is less than $1$, up to logarithmic terms, low degree non-trivial estimation fails. Our results suggest that the task of aligning $p$ graphs in polynomial time is as hard as the problem of aligning two graphs in polynomial time, up to logarithmic factors. These results characterize the existence of a statistical-computational gap and provide another example in which polynomial-time algorithms cannot handle complex combinatorial bi-dimensional structures.
• Abstract（参考訳）: 複数のガウスグラフアライメントにおける統計的-計算的ギャップの存在について検討する。 まず、Vassaux and Massoulié (2025) から以前に確立された情報しきい値(英語版)を、観測されたグラフの数$p$がノード数$n$: if $p \leq O(n/\log(n))$、Vassaux and Massoulié (2025) と $p \geq Ω(n/\log(n))$ から結果を回復すると、ある未知の「符号」グラフとの整合が難しい状態に対応する。 さらに、$\log p = ω(\log n)$ の場合、部分的および正確な回復のための情報しきい値は、$\log p=O(\log n)$ で観測されたオール・オー・ナッシング現象とは対照的に、もはや一致しない。 次に、(多重)ガウスグラフアライメントのための低次フレームワークにおいて、最初の計算障壁を提供する。 相関$ρ$が1ドル未満のとき、対数項まで、低次非自明な推定は失敗する。 この結果から、多項式時間における$p$グラフの整列化は、対数的因子まで、多項式時間における2つのグラフの整列化の問題と同じくらい難しいことが示唆された。 これらの結果は統計計算的ギャップの存在を特徴付け、多項式時間アルゴリズムが複雑な組合せの2次元構造を扱えない別の例を提供する。

関連論文リスト

• Efficient Graph Matching for Correlated Stochastic Block Models [7.320365821066744]
  2つのバランスの取れたコミュニティを持つ相関ブロックモデルの学習問題について検討する。 我々の主な成果は、この設定におけるグラフマッチングのための最初の効率的なアルゴリズムである。 我々はこれを情報理論的に可能であれば、正確なグラフマッチングのための効率的なアルゴリズムに拡張する。
  論文  参考訳（メタデータ） (2024-12-03T18:36:45Z)
• 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)
• Detection-Recovery Gap for Planted Dense Cycles [72.4451045270967]
  期待帯域幅$n tau$とエッジ密度$p$をエルドホス=R'enyiグラフ$G(n,q)$に植え込むモデルを考える。 低次アルゴリズムのクラスにおいて、関連する検出および回復問題に対する計算しきい値を特徴付ける。
  論文  参考訳（メタデータ） (2023-02-13T22:51:07Z)
• Statistical limits of correlation detection in trees [0.7826806223782055]
  本稿では,2本の観測木$(t,t')$が独立に標本化されているか,あるいは相関関係のある関節分布から採取されているかを調べる。 グラフアライメントにより,片側テストの存在条件について検討する。 このようなテストは$s leq sqrtalpha$に対して存在せず、そのようなテストは$s > sqrtalpha$, for $lambda$十分に大きいときに存在します。
  論文  参考訳（メタデータ） (2022-09-27T22:26:53Z)
• Seeded graph matching for the correlated Gaussian Wigner model via the projected power method [5.639451539396459]
  グラフマッチングアルゴリズムとして,Emphprojected Power Method (PPM) の性能解析を行った。 PPM は定数 $sigma$ の反復でも機能し、(Mao et al. 2023) のスパース相関エルドス・レニー(CER) モデルに対する解析を (dense) CGW モデルに拡張する。
  論文  参考訳（メタデータ） (2022-04-08T14:31:26Z)
• Accelerated Gradient Tracking over Time-varying Graphs for Decentralized Optimization [59.65871549878937]
  実用的な単一ループ加速勾配追跡には$O(fracgamma1-sigma_gamma)2sqrtfracLepsilon)$が必要であることを証明している。 我々の収束率は$O(frac1epsilon5/7)$と$O(fracLmu)5/7frac1(1-sigma)1.5logfrac1epsilon)$よりも大幅に改善した。
  論文  参考訳（メタデータ） (2021-04-06T15:34:14Z)
• Classical algorithms for Forrelation [2.624902795082451]
  1対の$n$-bit Boolean 関数 $f$ と $g$ が与えられたとき、$f$ と $g$ のフーリエ変換の間の相関を推定する。 この問題は、クエリの複雑さの観点から最大の量子スピードアップをもたらすことが知られている。 グラフに基づく回帰問題は、任意の二部グラフに対して時間$O(n)$で解けることを示す。
  論文  参考訳（メタデータ） (2021-02-13T17:25:41Z)
• 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)

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

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