論文の概要: Seeded graph matching for the correlated Wigner model via the projected
power method
- arxiv url: http://arxiv.org/abs/2204.04099v2
- Date: Tue, 1 Aug 2023 12:20:02 GMT
- ステータス: 処理完了
- システム内更新日: 2023-08-02 18:27:06.488813
- Title: Seeded graph matching for the correlated Wigner model via the projected
power method
- Title（参考訳）: 投影パワー法による相関ウィグナーモデルに対するシードグラフマッチング
- Authors: Ernesto Araya, Guillaume Braun and Hemant Tyagi
- Abstract要約: グラフマッチングアルゴリズムとして,Emphprojected Power Method (PPM) の性能解析を行った。
我々の分析の副産物として、PPMフレームワークはシードグラフマッチングのための最先端アルゴリズムのいくつかを一般化する。
- 参考スコア（独自算出の注目度）: 4.8986598953553555
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In the \emph{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 \emph{projected power method} (PPM) as
a \emph{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 \citep{MaoRud} for the sparse Erd\H{o}s-R\'enyi 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（参考訳）: emph{graph matching}問題では、2つのグラフをg,h$ で観察し、その頂点間の代入(またはマッチング)を見つけ出すことが目的であり、ある辺合意の測度が最大化される。
この研究において、観察された対 $g,h$ は、相関付き重み付きグラフの一般的なモデルである、相関付きウィグナーモデル(英語版)(relationeded wigner model)から引き出され、このモデルでは、$g$ と $h$ の隣接行列のエントリは独立ガウス行列であり、$g$ の各辺は、パラメータ $\sigma\in [0,1)$ で記述された辺相関と相関していると仮定する。
本稿では,初期部分的正のマッチング(シードと呼ばれる)をサイド情報として与えた,<emph{seed}グラフマッチングアルゴリズムである<emph{projected power method>(ppm)の性能解析を行う。
この結果から, 種子が接地構造マッチングに十分近い場合, 高い確率でPPMは種子を反復的に改良し, 地上構造マッチングを$\mathcal{O}(\log n)$繰り返しで回収することを示した。
この結果から, ppm は定値 $\sigma$ のレジームでも作用することが明らかとなり, スパース erd\h{o}s-r\'enyi モデルに対する \citep{maorud} の解析を (dense) wigner モデルに拡張した。
我々の分析の副産物として、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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。