論文の概要: Sharp threshold for alignment of graph databases with Gaussian weights
- arxiv url: http://arxiv.org/abs/2010.16295v2
- Date: Tue, 18 May 2021 14:46:09 GMT
- ステータス: 処理完了
- システム内更新日: 2022-10-01 16:27:50.085872
- Title: Sharp threshold for alignment of graph databases with Gaussian weights
- Title（参考訳）: ガウス重み付きグラフデータベースのアライメントのためのシャープしきい値
- Authors: Luca Ganassali
- Abstract要約: 重み付きグラフ(行列)データベースアライメントにおける再構成の基本的限界について検討する。
我々は、$pi*$の正確なリカバリには鋭いしきい値が存在することを証明している。
- 参考スコア（独自算出の注目度）: 1.6752182911522522
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study the fundamental limits for reconstruction in weighted graph (or
matrix) database alignment. We consider a model of two graphs where $\pi^*$ is
a planted uniform permutation and all pairs of edge weights $(A_{i,j},
B_{\pi^*(i),\pi^*(j)})_{1 \leq i<j \leq n}$ are i.i.d. pairs of Gaussian
variables with zero mean, unit variance and correlation parameter $\rho \in
[0,1]$. We prove that there is a sharp threshold for exact recovery of $\pi^*$:
if $n \rho^2 \geq (4+\epsilon) \log n + \omega(1)$ for some $\epsilon>0$, there
is an estimator $\hat{\pi}$ -- namely the MAP estimator -- based on the
observation of databases $A,B$ that achieves exact reconstruction with high
probability. Conversely, if $n \rho^2 \leq 4 \log n - \log \log n - \omega(1)$,
then any estimator $\hat{\pi}$ verifies $\hat{\pi}=\pi$ with probability
$o(1)$.
This result shows that the information-theoretic threshold for exact recovery
is the same as the one obtained for detection in a recent work by Wu et al.
(2020): in other words, for Gaussian weighted graph alignment, the problem of
reconstruction is not more difficult than that of detection. Though the
reconstruction task was already well understood for vector-shaped database
alignment (that is taking signal of the form $(u_i, v_{\pi^*(i)})_{1 \leq i\leq
n}$ where $(u_i, v_{\pi^*(i)})$ are i.i.d. pairs in $\mathbb{R}^{d_u} \times
\mathbb{R}^{d_v}$), its formulation for graph (or matrix) databases brings a
drastically different problem for which the hard phase is conjectured to be
wide.
The proofs build upon the analysis of the MAP estimator and the second moment
method, together with the study of the correlation structure of energies of
permutations.
- Abstract（参考訳）: 重み付きグラフ(行列)データベースアライメントにおける再構成の基本的限界について検討する。
2つのグラフのモデルを考えると、$\pi^*$は植込みされた一様置換であり、すべてのエッジウェイトが$(A_{i,j}, B_{\pi^*である。
(i)\pi^*
(j)})_{1 \leq i<j \leq n}$ は、ゼロ平均、単位分散、相関パラメータ $\rho \in [0,1]$ を持つガウス変数の対である。
もし$n \rho^2 \geq (4+\epsilon) \log n + \omega(1)$ for some $\epsilon>0$なら、正確な再構成を達成するデータベース$a,b$の観測に基づいて、$\hat{\pi}$ --すなわちmap estimator -- が存在することを証明する。
逆に、$n \rho^2 \leq 4 \log n - \log \log n - \omega(1)$ ならば、任意の推定器 $\hat{\pi}$ は確率 $o(1)$ で $\hat{\pi}=\pi$ を検証する。
この結果から, 精度回復のための情報理論しきい値が, Wuらによる最近の研究(2020年)で得られたものと同一であること, 言い換えればガウス重み付きグラフアライメントでは, 再構築の問題は検出のそれよりも難しくないことがわかった。
復元作業はベクトル型データベースアライメント(これは$(u_i, v_{\pi^*)の信号を取る)に対して既によく理解されていた。
(i)})_{1 \leq i\leq n}$ ここで$(u_i, v_{\pi^*)
(i)})$ は$\mathbb{r}^{d_u} \times \mathbb{r}^{d_v}$ の i.i.d.ペアであり、グラフ(または行列)データベースの定式化は、ハードフェーズが広く予想されるような、劇的に異なる問題をもたらす。
これらの証明は、置換のエネルギーの相関構造の研究とともに、写像推定器と第二モーメント法の解析に基づいている。
関連論文リスト
- The Umeyama algorithm for matching correlated Gaussian geometric models
in the low-dimensional regime [0.0]
2つの相関したランダムな幾何グラフのマッチングの問題に触発され、潜在ノード置換によって相関した2つのガウス幾何学モデルのマッチング問題を研究する。
A_i,j=langle X_i,X_j rangle$, $B_i,j=langle Y_i,Y_j rangle$ で与えられるエッジウェイトを持つ2種類の(相関した)重み付き完全グラフを考える。
論文 参考訳（メタデータ） (2024-02-23T04:58:54Z) - 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) - Efficient Signed Graph Sampling via Balancing & Gershgorin Disc Perfect
Alignment [51.74913666829224]
強い反相関を持つデータセットに対して、適切なグラフは正および負のエッジ重みの両方を含むことを示す。
本稿では,平衡符号グラフの概念に着目した線形時間符号グラフサンプリング手法を提案する。
実験結果から, 署名付きグラフサンプリング手法は, 各種データセットにおいて, 既存の高速サンプリング方式よりも優れた性能を示した。
論文 参考訳（メタデータ） (2022-08-18T09:19:01Z) - Learning a Single Neuron with Adversarial Label Noise via Gradient
Descent [50.659479930171585]
モノトン活性化に対する $mathbfxmapstosigma(mathbfwcdotmathbfx)$ の関数について検討する。
学習者の目標は仮説ベクトル $mathbfw$ that $F(mathbbw)=C, epsilon$ を高い確率で出力することである。
論文 参考訳（メタデータ） (2022-06-17T17:55:43Z) - Structure Learning in Graphical Models from Indirect Observations [17.521712510832558]
本稿では、パラメータ法と非パラメトリック法の両方を用いて、Rp$における$p$次元ランダムベクトル$Xのグラフィカル構造を学習する。
温和な条件下では、グラフ構造推定器が正しい構造を得ることができることを示す。
論文 参考訳（メタデータ） (2022-05-06T19:24:44Z) - Random Graph Matching in Geometric Models: the Case of Complete Graphs [21.689343447798677]
本稿では, エッジ重み付き2つの完全グラフが潜在測地によって相関する問題について検討する。
近似最大極大推定器を導出し、高い確率で$pi*$の完全回復を確実に達成する。
副次的な発見として、[Ume88] の有望なスペクトルアルゴリズムが幾何モデルにおける最大可能性のさらなる近似として現れることを示す。
論文 参考訳（メタデータ） (2022-02-22T04:14:45Z) - Fast Graph Sampling for Short Video Summarization using Gershgorin Disc
Alignment [52.577757919003844]
高速グラフサンプリングの最近の進歩を利用して,短い動画を複数の段落に効率よく要約する問題について検討する。
実験結果から,本アルゴリズムは最先端の手法と同等の映像要約を実現し,複雑さを大幅に低減した。
論文 参考訳（メタデータ） (2021-10-21T18:43:00Z) - Exact Matching of Random Graphs with Constant Correlation [2.578242050187029]
本稿では, ErdHos--R'enyi グラフに対するグラフマッチングやネットワークアライメントの問題を扱う。
これはグラフ同型問題のうるさい平均ケース版と見なすことができる。
論文 参考訳（メタデータ） (2021-10-11T05:07:50Z) - A Randomized Algorithm to Reduce the Support of Discrete Measures [79.55586575988292]
離散確率測度が$N$原子と$n$実数値関数の集合で成り立つと、元の$N$原子の$n+1$の部分集合で支えられる確率測度が存在する。
我々は、負の円錐によるバリセンターの簡単な幾何学的特徴付けを与え、この新しい測度を「グリード幾何学的サンプリング」によって計算するランダム化アルゴリズムを導出する。
次に、その性質を研究し、それを合成および実世界のデータにベンチマークして、$Ngg n$ regimeにおいて非常に有益であることを示す。
論文 参考訳（メタデータ） (2020-06-02T16:38:36Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。