論文の概要: Seeded graph matching for the correlated Wigner model via the projected
power method
- arxiv url: http://arxiv.org/abs/2204.04099v1
- Date: Fri, 8 Apr 2022 14:31:26 GMT
- ステータス: 処理完了
- システム内更新日: 2022-04-11 13:33:30.047283
- Title: Seeded graph matching for the correlated Wigner model via the projected
power method
- Title（参考訳）: 投影パワー法による相関ウィグナーモデルに対するシードグラフマッチング
- Authors: Ernesto Araya, Guillaume Braun and Hemant Tyagi
- Abstract要約: 我々は、シードグラフマッチングアルゴリズムとして、投影電力法(PPM)の性能を解析する。
PPMが一定の$sigma$のレギュレーションでも機能することを証明します。
我々の分析の副産物として、PPMフレームワークはシードグラフマッチングのための最先端アルゴリズムのいくつかを一般化する。
- 参考スコア（独自算出の注目度）: 4.8986598953553555
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In the graph matching problem we observe two graphs $G,H$ and the goal is to
find an assignment (or matching) between their vertices such that some measure
of edge agreement is maximized. We assume in this work that the observed pair
$G,H$ has been drawn from the correlated Wigner model -- a popular model for
correlated weighted graphs -- where the entries of the adjacency matrices of
$G$ and $H$ are independent Gaussians and each edge of $G$ is correlated with
one edge of $H$ (determined by the unknown matching) with the edge correlation
described by a parameter $\sigma\in [0,1)$. In this paper, we analyse the
performance of the projected power method (PPM) as a seeded graph matching
algorithm where we are given an initial partially correct matching (called the
seed) as side information. We prove that if the seed is close enough to the
ground-truth matching, then with high probability, PPM iteratively improves the
seed and recovers the ground-truth matching (either partially or exactly) in
$\mathcal{O}(\log n)$ iterations. Our results prove that PPM works even in
regimes of constant $\sigma$, thus extending the analysis in (Mao et al.,2021)
for the sparse Erd\"os-Renyi model to the (dense) Wigner model. As a byproduct
of our analysis, we see that the PPM framework generalizes some of the
state-of-art algorithms for seeded graph matching. We support and complement
our theoretical findings with numerical experiments on synthetic data.
- Abstract（参考訳）: グラフマッチング問題では、2つのグラフが$g,h$ で観察され、ゴールは頂点間の割り当て(またはマッチング)を見つけることである。
この研究において、観察された対 $g,h$ は、相関付き重み付きグラフの一般的なモデルである、相関付きウィグナーモデル(英語版)(relationeded wigner model)から引き出され、このモデルでは、$g$ と $h$ の隣接行列のエントリは独立ガウス行列であり、$g$ の各辺は、パラメータ $\sigma\in [0,1)$ で記述された辺相関と相関していると仮定する。
本稿では,予測パワー法(PPM)の性能をシードグラフマッチングアルゴリズムとして解析し,初期部分的正マッチング(シードと呼ぶ)を副次情報として与える。
この結果から, 種子が接地構造マッチングに十分近い場合, 高い確率でPPMは種子を反復的に改良し, 地上構造マッチングを$\mathcal{O}(\log n)$繰り返しで回収することを示した。
我々の結果は、PPMが定数$\sigma$のレギュレーションでも機能することを証明し、スパース Erd\"os-Renyi モデルに対する (Mao et al.,2021) 解析を (dense) ウィグナーモデルに拡張した。
我々の分析の副産物として、PPMフレームワークはシードグラフマッチングのための最先端アルゴリズムの一部を一般化している。
我々は, 合成データに関する数値実験を行い, 理論的知見を補完する。
関連論文リスト
- 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) - Matching Correlated Inhomogeneous Random Graphs using the $k$-core
Estimator [5.685589351789462]
我々は、両グラフの大きな共通部分グラフを誘導する対応を出力するいわゆるemph$k$-core推定器について検討する。
相関ブロックモデル,Chung-Lu幾何グラフ,および相関ランダムグラフの精度と部分的回復に関する新たな結果を導出するために,我々の一般的な枠組みを専門化している。
論文 参考訳（メタデータ） (2023-02-10T18:21:35Z) - Random graph matching at Otter's threshold via counting chandeliers [16.512416293014493]
そこで本研究では,各木に根付いた重み付き木を数えることで構築した類似度スコアに基づく,グラフマッチングの効率的なアルゴリズムを提案する。
これは、明示的な一定の相関で成功し、スパースグラフと密度グラフの両方に適用する最初のグラフマッチングアルゴリズムである。
論文 参考訳（メタデータ） (2022-09-25T20:00:28Z) - Causal Bandits for Linear Structural Equation Models [58.2875460517691]
本稿では,因果図形モデルにおける最適な介入順序を設計する問題について検討する。
グラフの構造は知られており、ノードは$N$である。
頻繁性(UCBベース)とベイズ的設定に2つのアルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-08-26T16:21:31Z) - Efficient Signed Graph Sampling via Balancing & Gershgorin Disc Perfect
Alignment [51.74913666829224]
強い反相関を持つデータセットに対して、適切なグラフは正および負のエッジ重みの両方を含むことを示す。
本稿では,平衡符号グラフの概念に着目した線形時間符号グラフサンプリング手法を提案する。
実験結果から, 署名付きグラフサンプリング手法は, 各種データセットにおいて, 既存の高速サンプリング方式よりも優れた性能を示した。
論文 参考訳（メタデータ） (2022-08-18T09:19:01Z) - 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) - Correlation detection in trees for partial graph alignment [3.5880535198436156]
グラフのアライメントは,エッジの大部分を保存する2つのグラフのノード間のマッピングを探索する。
我々のアプローチは、2つのグラフの局所構造を比較し、その近傍が相関グラフに対して「十分近い」場合、2つのノードをマッチングすることである。
この問題は、一対の分岐木が積分布または相関分布から引き出されるかどうかの検定の観点から説明できる。
論文 参考訳（メタデータ） (2021-07-15T22:02:27Z) - Solving correlation clustering with QAOA and a Rydberg qudit system: a
full-stack approach [94.37521840642141]
量子近似最適化アルゴリズム(QAOA)とクォーディットを用いた相関クラスタリング問題について検討する。
具体的には、中性原子量子コンピュータを検討し、相関クラスタリングのためのフルスタックアプローチを提案する。
ゲート数によって定量化されるように、quditの実装はqubitエンコーディングよりも優れていることを示す。
論文 参考訳（メタデータ） (2021-06-22T11:07:38Z) - Adversarial Linear Contextual Bandits with Graph-Structured Side
Observations [80.95090605985042]
学習エージェントは、$d$-dimensionalコンテキストベクトルで提示された後、一連の$k$アクションから繰り返し選択する。
エージェントは選択されたアクションの損失を誘発し、観察するが、観察構造における隣り合うアクションの損失も観察する。
textttEXP3に基づく2つの効率的なアルゴリズムが開発された。
論文 参考訳（メタデータ） (2020-12-10T15:40:07Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。