論文の概要: Graph Matching via convex relaxation to the simplex

• arxiv url: http://arxiv.org/abs/2310.20609v3
• Date: Fri, 9 Aug 2024 07:53:34 GMT
• ステータス: 処理完了
• システム内更新日: 2024-08-12 20:51:27.923006
• Title: Graph Matching via convex relaxation to the simplex
• Title（参考訳）: 凸緩和によるグラフマッチング
• Authors: Ernesto Araya Valdivia, Hemant Tyagi,
• Abstract要約: 本稿では,2つの入力グラフの最適アライメントを求めるグラフマッチング問題に対処する。 この問題に対処するための一般的なアプローチは、NP-hard emphQuadratic Assignment Problem (QAP) の凸緩和である。 単位単純度に新しい凸緩和を導入し、この問題を解決するための閉形式反復を用いた効率的なミラー降下スキームを開発する。
• 参考スコア（独自算出の注目度）: 5.355990925686151
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: This paper addresses the Graph Matching problem, which consists of finding the best possible alignment between two input graphs, and has many applications in computer vision, network deanonymization and protein alignment. A common approach to tackle this problem is through convex relaxations of the NP-hard \emph{Quadratic Assignment Problem} (QAP). Here, we introduce a new convex relaxation onto the unit simplex and develop an efficient mirror descent scheme with closed-form iterations for solving this problem. Under the correlated Gaussian Wigner model, we show that the simplex relaxation admits a unique solution with high probability. In the noiseless case, this is shown to imply exact recovery of the ground truth permutation. Additionally, we establish a novel sufficiency condition for the input matrix in standard greedy rounding methods, which is less restrictive than the commonly used `diagonal dominance' condition. We use this condition to show exact one-step recovery of the ground truth (holding almost surely) via the mirror descent scheme, in the noiseless setting. We also use this condition to obtain significantly improved conditions for the GRAMPA algorithm [Fan et al. 2019] in the noiseless setting.
• Abstract（参考訳）: 本稿では、2つの入力グラフ間の最適なアライメントを見つけることによるグラフマッチング問題に対処し、コンピュータビジョン、ネットワークのデ匿名化、タンパク質アライメントに多くの応用がある。 この問題に対処するための一般的なアプローチは、NP-hard \emph{Quadratic Assignment Problem} (QAP) の凸緩和である。 本稿では,単位単純度に新しい凸緩和を導入し,この問題を解決するために閉形式反復を用いた効率的なミラー降下法を開発した。 相関したガウス・ウィグナーモデルの下では、単純緩和は高い確率で一意的な解を持つことを示す。 ノイズレスの場合、これは基底真理置換の正確な回復を示す。 さらに, 標準グリーディラウンドリング法では, 入力行列に対して, 通常の「対角線支配」条件よりも制約が小さい, 新たな充足条件を確立する。 我々は、この条件を用いて、ノイズのない環境で、ミラー降下スキームを介して、(ほぼ確実に保持する)基底真実の正確な1段階の回復を示す。 また, この条件を用いて, GRAMPA アルゴリズム [Fan et al 2019] のノイズレス環境での条件を大幅に改善した。

関連論文リスト

• CLAP: Concave Linear APproximation for Quadratic Graph Matching [5.417323487240968]
  線形モデルを導入し、グラフマッチングのための新しい近似行列を設計する。 次に、元のQAPを構造制約の凹凸となる線形モデルに変換する。 このモデルはシンクホーン最適輸送アルゴリズムを用いて解くことができる。
  論文  参考訳（メタデータ） (2024-10-22T15:28:18Z)
• Distributed Extra-gradient with Optimal Complexity and Communication Guarantees [60.571030754252824]
  複数のプロセッサ/ワーカー/クライアントがローカルなデュアルベクトルにアクセス可能なマルチGPU設定において、モノトン変分不等式(VI)問題を考察する。 モノトーンVI問題に対するデファクトアルゴリズムであるExtra-gradientは、通信効率が良くないように設計されている。 そこで本稿では,VI の解法に適した非バイアスで適応的な圧縮手法である量子化一般化外部勾配 (Q-GenX) を提案する。
  論文  参考訳（メタデータ） (2023-08-17T21:15:04Z)
• Graph Signal Sampling for Inductive One-Bit Matrix Completion: a Closed-form Solution [112.3443939502313]
  グラフ信号解析と処理の利点を享受する統合グラフ信号サンプリングフレームワークを提案する。 キーとなる考え方は、各ユーザのアイテムのレーティングをアイテムイットグラフの頂点上の関数(信号)に変換することである。 オンライン設定では、グラフフーリエ領域における連続ランダムガウス雑音を考慮したベイズ拡張(BGS-IMC)を開発する。
  論文  参考訳（メタデータ） (2023-02-08T08:17:43Z)
• WARPd: A linearly convergent first-order method for inverse problems with approximate sharpness conditions [0.0]
  シャープネス条件は1次法のリスタートスキームのリカバリ性能を直接制御する。 重み付き, 加速度付き, 再起動されたプリマルデュアル(WARPd)の1次手法を提案する。 一般的な近似的シャープネス条件の下では、WARPd は所望のベクトルに対して安定な線形収束を達成する。 本稿では、WARPdが専門的な最先端手法と比較し、大規模問題の解決に最適であることを示す。
  論文  参考訳（メタデータ） (2021-10-24T13:19:41Z)
• Learning Sparse Graph with Minimax Concave Penalty under Gaussian Markov Random Fields [51.07460861448716]
  本稿では,データから学ぶための凸解析フレームワークを提案する。 三角凸分解はその上部に対応する変換によって保証されることを示す。
  論文  参考訳（メタデータ） (2021-09-17T17:46:12Z)
• Lifting the Convex Conjugate in Lagrangian Relaxations: A Tractable Approach for Continuous Markov Random Fields [53.31927549039624]
  断片的な離散化は既存の離散化問題と矛盾しないことを示す。 この理論を2つの画像のマッチング問題に適用する。
  論文  参考訳（メタデータ） (2021-07-13T12:31:06Z)
• Bayesian Inference of Random Dot Product Graphs via Conic Programming [1.7188280334580195]
  本稿では,ランダムドット積グラフ(RDPG)の潜在確率行列を推定する凸コーンプログラムを提案する。 また、この手法がケイトクラブグラフと米国上院の投票グラフの潜在構造を復元することを示した。
  論文  参考訳（メタデータ） (2021-01-06T18:29:37Z)
• Gaussian MRF Covariance Modeling for Efficient Black-Box Adversarial Attacks [86.88061841975482]
  我々は,ゼロオーダーのオラクルにのみアクセス可能なブラックボックス設定において,逆例を生成する問題について検討する。 我々はこの設定を用いて、FGSM(Fast Gradient Sign Method)のブラックボックス版と同様に、高速な1ステップの敵攻撃を見つける。 提案手法はクエリを少なくし,現在の技術よりも攻撃成功率が高いことを示す。
  論文  参考訳（メタデータ） (2020-10-08T18:36:51Z)
• Online and Distribution-Free Robustness: Regression and Contextual Bandits with Huber Contamination [29.85468294601847]
  線形回帰と文脈的帯域幅という2つの古典的高次元オンライン学習問題を再考する。 従来の手法が失敗した場合にアルゴリズムが成功することを示す。
  論文  参考訳（メタデータ） (2020-10-08T17:59:05Z)
• Approximation Schemes for ReLU Regression [80.33702497406632]
  我々はReLU回帰の根本的な問題を考察する。 目的は、未知の分布から引き出された2乗損失に対して、最も適したReLUを出力することである。
  論文  参考訳（メタデータ） (2020-05-26T16:26:17Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。