論文の概要: 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) - 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) - Random graph matching at Otter's threshold via counting chandeliers [16.512416293014493]
そこで本研究では,各木に根付いた重み付き木を数えることで構築した類似度スコアに基づく,グラフマッチングの効率的なアルゴリズムを提案する。
これは、明示的な一定の相関で成功し、スパースグラフと密度グラフの両方に適用する最初のグラフマッチングアルゴリズムである。
論文 参考訳(メタデータ) (2022-09-25T20:00:28Z) - Efficient Signed Graph Sampling via Balancing & Gershgorin Disc Perfect
Alignment [51.74913666829224]
強い反相関を持つデータセットに対して、適切なグラフは正および負のエッジ重みの両方を含むことを示す。
本稿では,平衡符号グラフの概念に着目した線形時間符号グラフサンプリング手法を提案する。
実験結果から, 署名付きグラフサンプリング手法は, 各種データセットにおいて, 既存の高速サンプリング方式よりも優れた性能を示した。
論文 参考訳(メタデータ) (2022-08-18T09:19:01Z) - Matching recovery threshold for correlated random graphs [9.12788494573002]
共通 ErdHos-R'enyi グラフ $mathbfG(n, p)$ から独立にサブサンプリングされた2つの相関グラフに対して、これらの2つのグラフのアンフィグアウトラベルの観測からそれらのエンフィラテントマッチングを回復したい。
この結果は,近年のWu,Xu,Yuによる研究において一定の要因を導出する。
論文 参考訳(メタデータ) (2022-05-29T13:04:20Z) - Collaborative likelihood-ratio estimation over graphs [55.98760097296213]
グラフに基づく相対的制約のない最小二乗重要度フィッティング(GRULSIF)
我々はこの考え方を、グラフベースの相対的非制約最小二乗重要度フィッティング(GRULSIF)と呼ばれる具体的な非パラメトリック手法で開発する。
我々は、ノード当たりの観測回数、グラフのサイズ、およびグラフ構造がタスク間の類似性をどの程度正確にエンコードしているかといった変数が果たす役割を強調する、協調的なアプローチの収束率を導出する。
論文 参考訳(メタデータ) (2022-05-28T15:37:03Z) - 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) - The Performance of the MLE in the Bradley-Terry-Luce Model in
$\ell_{\infty}$-Loss and under General Graph Topologies [76.61051540383494]
我々はBradley-Terry-Luceモデルの$ell_infty$推定誤差に関する新しい一般上限を導出する。
導出された境界は良好に機能し、場合によっては既知の結果よりもシャープであることを示す。
論文 参考訳(メタデータ) (2021-10-20T23:46:35Z) - Correlation detection in trees for partial graph alignment [3.5880535198436156]
グラフのアライメントは,エッジの大部分を保存する2つのグラフのノード間のマッピングを探索する。
我々のアプローチは、2つのグラフの局所構造を比較し、その近傍が相関グラフに対して「十分近い」場合、2つのノードをマッチングすることである。
この問題は、一対の分岐木が積分布または相関分布から引き出されるかどうかの検定の観点から説明できる。
論文 参考訳(メタデータ) (2021-07-15T22:02:27Z) - Adversarial Linear Contextual Bandits with Graph-Structured Side
Observations [80.95090605985042]
学習エージェントは、$d$-dimensionalコンテキストベクトルで提示された後、一連の$k$アクションから繰り返し選択する。
エージェントは選択されたアクションの損失を誘発し、観察するが、観察構造における隣り合うアクションの損失も観察する。
textttEXP3に基づく2つの効率的なアルゴリズムが開発された。
論文 参考訳(メタデータ) (2020-12-10T15:40:07Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。