論文の概要: Random Graph Matching in Geometric Models: the Case of Complete Graphs
- arxiv url: http://arxiv.org/abs/2202.10662v1
- Date: Tue, 22 Feb 2022 04:14:45 GMT
- ステータス: 処理完了
- システム内更新日: 2022-02-23 17:02:48.406318
- Title: Random Graph Matching in Geometric Models: the Case of Complete Graphs
- Title（参考訳）: 幾何学モデルにおけるランダムグラフマッチング:完全グラフの場合
- Authors: Haoyu Wang, Yihong Wu, Jiaming Xu, Israel Yoloh
- Abstract要約: 本稿では, エッジ重み付き2つの完全グラフが潜在測地によって相関する問題について検討する。
近似最大極大推定器を導出し、高い確率で$pi*$の完全回復を確実に達成する。
副次的な発見として、[Ume88] の有望なスペクトルアルゴリズムが幾何モデルにおける最大可能性のさらなる近似として現れることを示す。
- 参考スコア（独自算出の注目度）: 21.689343447798677
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: This paper studies the problem of matching two complete graphs with edge
weights correlated through latent geometries, extending a recent line of
research on random graph matching with independent edge weights to geometric
models. Specifically, given a random permutation $\pi^*$ on $[n]$ and $n$ iid
pairs of correlated Gaussian vectors $\{X_{\pi^*(i)}, Y_i\}$ in $\mathbb{R}^d$
with noise parameter $\sigma$, the edge weights are given by
$A_{ij}=\kappa(X_i,X_j)$ and $B_{ij}=\kappa(Y_i,Y_j)$ for some link function
$\kappa$. The goal is to recover the hidden vertex correspondence $\pi^*$ based
on the observation of $A$ and $B$. We focus on the dot-product model with
$\kappa(x,y)=\langle x, y \rangle$ and Euclidean distance model with
$\kappa(x,y)=\|x-y\|^2$, in the low-dimensional regime of $d=o(\log n)$ wherein
the underlying geometric structures are most evident. We derive an approximate
maximum likelihood estimator, which provably achieves, with high probability,
perfect recovery of $\pi^*$ when $\sigma=o(n^{-2/d})$ and almost perfect
recovery with a vanishing fraction of errors when $\sigma=o(n^{-1/d})$.
Furthermore, these conditions are shown to be information-theoretically optimal
even when the latent coordinates $\{X_i\}$ and $\{Y_i\}$ are observed,
complementing the recent results of [DCK19] and [KNW22] in geometric models of
the planted bipartite matching problem. As a side discovery, we show that the
celebrated spectral algorithm of [Ume88] emerges as a further approximation to
the maximum likelihood in the geometric model.
- Abstract（参考訳）: 本稿では, エッジ重み付きグラフとエッジ重み付きグラフのマッチング問題について検討し, エッジ重み付きランダムグラフマッチングに関する最近の研究を幾何学モデルに拡張する。
具体的には、ランダムな置換 $\pi^*$ on $[n]$ と $n$ iid の相関ガウスベクトルの対 $\{X_{\pi^*(i)}, Y_i\}$ in $\mathbb{R}^d$ with noise parameters $\sigma$ が与えられたとき、エッジウェイトは、あるリンク関数 $\kappa$ に対して $A_{ij}=\kappa(X_i,X_j)$ と $B_{ij}=\kappa(Y_i,Y_j)$ によって与えられる。
目標は、$a$ と $b$ の観測に基づいて、隠れた頂点対応 $\pi^*$ を回復することである。
我々は,$\kappa(x,y)=\langle x,y \rangle$ のドット生成モデルと$\kappa(x,y)=\|x-y\|^2$のユークリッド距離モデルに注目した。
高確率で$\pi^*$の完全回復、$\sigma=o(n^{-2/d})$の完全回復、$\sigma=o(n^{-1/d})$のほぼ完全回復を確実に達成する近似的極大推定器を導出する。
さらに,2成分マッチング問題の幾何モデルにおける [dck19] と [knw22] の最近の結果を補完して,潜在座標 $\{x_i\}$ と $\{y_i\}$ が観測された場合でも,これらの条件は情報理論的に最適であることが示されている。
副次的な発見として、[Ume88] の有望なスペクトルアルゴリズムが幾何モデルにおける最大可能性のさらなる近似として現れることを示す。
関連論文リスト
- Optimal Sketching for Residual Error Estimation for Matrix and Vector Norms [50.15964512954274]
線形スケッチを用いた行列とベクトルノルムの残差誤差推定問題について検討する。
これは、前作とほぼ同じスケッチサイズと精度で、経験的にかなり有利であることを示す。
また、スパースリカバリ問題に対して$Omega(k2/pn1-2/p)$低いバウンダリを示し、これは$mathrmpoly(log n)$ factorまで厳密である。
論文 参考訳（メタデータ） (2024-08-16T02:33:07Z) - 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) - Structure Learning in Graphical Models from Indirect Observations [17.521712510832558]
本稿では、パラメータ法と非パラメトリック法の両方を用いて、Rp$における$p$次元ランダムベクトル$Xのグラフィカル構造を学習する。
温和な条件下では、グラフ構造推定器が正しい構造を得ることができることを示す。
論文 参考訳（メタデータ） (2022-05-06T19:24:44Z) - 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) - Improved Reconstruction of Random Geometric Graphs [3.930410971186142]
ランダムな幾何グラフの古典的モデルを考えると、$n$の点が一様に領域$n$の正方形に散らばっている。
グラフ距離と近距離推定のハイブリッドを用いてユークリッド距離を推定する。
本手法は, グラフ距離と近辺点数に基づく短距離推定のハイブリッドを用いてユークリッド距離を推定する。
論文 参考訳（メタデータ） (2021-07-29T20:37:28Z) - Sharp threshold for alignment of graph databases with Gaussian weights [1.6752182911522522]
重み付きグラフ(行列)データベースアライメントにおける再構成の基本的限界について検討する。
我々は、$pi*$の正確なリカバリには鋭いしきい値が存在することを証明している。
論文 参考訳（メタデータ） (2020-10-30T14:42:17Z) - 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) - Curse of Dimensionality on Randomized Smoothing for Certifiable
Robustness [151.67113334248464]
我々は、他の攻撃モデルに対してスムースな手法を拡張することは困難であることを示す。
我々はCIFARに関する実験結果を示し,その理論を検証した。
論文 参考訳（メタデータ） (2020-02-08T22:02:14Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。