射影パワー法による相関Gauss Wignerモデルのためのシードグラフマッチング【JST機械翻訳】

Araya Ernesto; Braun Guillaume; Tyagi Hemant

プレプリント

J-GLOBAL ID：202202202175690820 整理番号：22P0328521

射影パワー法による相関Gauss Wignerモデルのためのシードグラフマッチング【JST機械翻訳】

Seeded graph matching for the correlated Gaussian Wigner model via the projected power method

出版者サイト {{ this.onShowPLink() }} 複写サービスで全文入手
高度な検索・分析はJDreamⅢで

この文献はプレプリントです。プレプリントについてはこちらをご確認ください。

著者 (3件)： , ,
資料名：
発行年： 2022年04月08日プレプリントサーバーでの情報更新日： 2024年05月05日
JST資料番号： O7000B 資料種別：プレプリント
記事区分：プレプリント発行国：アメリカ合衆国 (USA) 言語：英語 (EN)

グラフマッチング問題では,2つのグラフG,Hを観測し,その目標は,エッジ一致のいくつかの測度が最大化されるように,それらの頂点間の割当(またはマッチング)を見つけることである。本研究では,観測された対G,Hが相関Gauss Wigner(CGW)モデルから導出されたことを仮定した-相関重み付きグラフに対するポピュラーなモデル-ここで,GおよびHの隣接行列のエントリは独立Gaussであり,Gの各エッジはパラメータλ=0,1により記述されるエッジ相関を持つHの1つのエッジ(未知のマッチングにより決定)と相関がある。本論文では,シードグラフマッチングアルゴリズムとして射影電力法(PPM)の性能を解析し,そこでは,側情報として初期部分正しいマッチング(シードと呼ぶ)を与えた。シードがグランドトゥルースマッチングに十分近いならば,高い確率で,PPMはシードを反復的に改善し,O(logn)反復においてグランドトゥルースマッチング(部分的または正確に)を回復することを証明した。その結果,PPMは一定σの領域でも動作し,スパース相関Erdos-Renyi(CER)モデルの(Maoら2023)解析を(高密度)CGWモデルに拡張した。筆者らの解析の副産物として,筆者らはPPMフレームワークがシード付きグラフマッチングに対して幾つかの最先端アルゴリズムを一般化する事を見出した。合成データに関する数値実験により理論的発見を支持し補足した。【JST機械翻訳】

, , , , , , , , ,
, , , , , , 【Automatic Indexing@JST】

グラフ理論基礎 , パターン認識

, , , ,

前のページに戻る