論文の概要: Dynamical softassign and adaptive parameter tuning for graph matching
- arxiv url: http://arxiv.org/abs/2208.08233v3
- Date: Sun, 24 Mar 2024 12:11:18 GMT
- ステータス: 処理完了
- システム内更新日: 2024-03-27 06:02:58.823537
- Title: Dynamical softassign and adaptive parameter tuning for graph matching
- Title(参考訳): グラフマッチングのための動的ソフトアサインと適応パラメータチューニング
- Authors: Binrui Shen, Qiang Niu, Shengxin Zhu,
- Abstract要約: 制約勾配アルゴリズムと呼ばれるグラフマッチング問題に対する統一的なフレームワークについて検討する。
我々の寄与する適応的なステップサイズパラメータは、基礎となるアルゴリズムの収束を保証することができる。
本稿では,ソフトアサイン制約勾配法という新しいグラフマッチングアルゴリズムを提案する。
- 参考スコア(独自算出の注目度): 0.7456521449098222
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: This paper studies a unified framework for graph matching problems called the constrained gradient method. Popular algorithms within this framework include graduated assignment (GA), integer projected fixed-point method (IPFP), and doubly stochastic projected fixed-point method (DSPFP). These algorithms differ from the step size parameter and constrained operator. Our contributed adaptive step size parameter can guarantee the underlying algorithms' convergence and enhance their efficiency and accuracy. A preliminary analysis suggests that the optimal step size parameter has a high probability of being 1 in fully connected graph matching. Secondly, we propose a dynamic strategy for softassign, a popular constrained operator, to address its sensitivity concerning nodes' cardinality and risk of overflow. Combining the adaptive step size parameter and the dynamical softassign, we propose a novel graph matching algorithm: the softassign constrained gradient method. Various experiments demonstrate that it is significantly faster than other state-of-the-art algorithms based on the constrained gradient method with improved accuracy.
- Abstract(参考訳): 本稿では,制約勾配法と呼ばれるグラフマッチング問題の統一的枠組みについて検討する。
このフレームワークの一般的なアルゴリズムには、卒業代入(GA)、整数射影固定点法(IPFP)、二重確率射影固定点法(DSPFP)がある。
これらのアルゴリズムは、ステップサイズパラメータと制約演算子とは異なる。
提案する適応的なステップサイズパラメータは,アルゴリズムの収束を保証し,その効率と精度を向上させる。
予備的な分析は、最適ステップサイズパラメータが完全連結グラフマッチングにおいて 1 になる確率が高いことを示唆している。
次に,制約演算子であるソフトアサインの動的戦略を提案し,ノードの濃度とオーバーフローのリスクに対する感度に対処する。
適応的なステップサイズパラメータと動的ソフトアサインを組み合わせることで,ソフトアサイン制約勾配法という新しいグラフマッチングアルゴリズムを提案する。
様々な実験により、精度が向上した制約勾配法に基づく他の最先端アルゴリズムよりもはるかに高速であることが示されている。
関連論文リスト
- Efficient Graph Similarity Computation with Alignment Regularization [7.143879014059894]
グラフ類似性計算(GSC)は、グラフニューラルネットワーク(GNN)を用いた学習に基づく予測タスクである。
適応正規化(AReg)と呼ばれる,シンプルながら強力な正規化技術によって,高品質な学習が達成可能であることを示す。
推論段階では、GNNエンコーダによって学習されたグラフレベル表現は、ARegを再度使用せずに直接類似度スコアを計算するために使用される。
論文 参考訳(メタデータ) (2024-06-21T07:37:28Z) - Differentiable Proximal Graph Matching [40.41380102260085]
微分可能近位グラフマッチング(DPGM)と呼ばれる近位演算子に基づくグラフマッチングアルゴリズムを提案する。
アルゴリズム全体をグラフ親和性行列からノード対応の予測への微分可能な写像とみなすことができる。
数値実験により、PGMは様々なデータセット上で既存のグラフマッチングアルゴリズムより優れていることが示された。
論文 参考訳(メタデータ) (2024-05-26T08:17:13Z) - Ensemble Quadratic Assignment Network for Graph Matching [52.20001802006391]
グラフマッチングはコンピュータビジョンやパターン認識において一般的に用いられる技法である。
最近のデータ駆動型アプローチは、グラフマッチングの精度を著しく改善した。
データ駆動手法と従来の手法の利点を組み合わせたグラフニューラルネットワーク(GNN)に基づくアプローチを提案する。
論文 参考訳(メタデータ) (2024-03-11T06:34:05Z) - T-GAE: Transferable Graph Autoencoder for Network Alignment [79.89704126746204]
T-GAEはグラフオートエンコーダフレームワークで、GNNの転送性と安定性を活用して、再トレーニングなしに効率的なネットワークアライメントを実現する。
実験の結果、T-GAEは最先端の最適化手法と最高のGNN手法を最大38.7%、50.8%で上回っていることがわかった。
論文 参考訳(メタデータ) (2023-10-05T02:58:29Z) - CBAG: An Efficient Genetic Algorithm for the Graph Burning Problem [0.0]
グラフ燃焼問題の解法として,Centrality BAsed Genetic-algorithm (CBAG) という効率的な遺伝的アルゴリズムを提案する。
グラフバーニング問題の特徴を考慮し,新しい染色体表現法と評価法を提案する。
この結果から,提案アルゴリズムは従来の最先端の中央値と比較して性能が向上していることが明らかとなった。
論文 参考訳(メタデータ) (2022-08-01T17:34:07Z) - Graph Matching via Optimal Transport [11.93151370164898]
グラフマッチング問題の解決は、運用研究、コンピュータビジョン、神経科学などへの応用により、ますます重要になっている。
現在の最先端のアルゴリズムは、非常に大きなグラフのマッチングには非効率であるが、精度は高い。
我々は,最新のグラフマッチングアルゴリズム "FAQ" (Vogelstein, 2015) を改良した GOAT を,その線形和割り当てステップを Cuturi (2013) の "Lightspeed Optimal Transport" メソッドに置き換える。
論文 参考訳(メタデータ) (2021-11-09T19:18:18Z) - FGOT: Graph Distances based on Filters and Optimal Transport [62.779521543654134]
グラフ比較は、グラフ間の類似点と相違点の識別を扱う。
大きな障害は、グラフの未知のアライメントと、正確で安価な比較指標の欠如である。
本研究では,フィルタグラフ距離近似を導入する。
論文 参考訳(メタデータ) (2021-09-09T17:43:07Z) - Online Matching in Sparse Random Graphs: Non-Asymptotic Performances of
Greedy Algorithm [20.582965700659788]
我々は、最も単純なアルゴリズムであるGREEDYの競合比を、関連する離散過程を連続的に近似することによって推定する。
驚くべきことに、GREEDYは、オンラインマッチングのためのもう1つの有名なアルゴリズムであるRANKINGよりも優れたパフォーマンスを保証することができる。
論文 参考訳(メタデータ) (2021-07-02T12:18:19Z) - Learnable Graph Matching: Incorporating Graph Partitioning with Deep
Feature Learning for Multiple Object Tracking [58.30147362745852]
フレーム間のデータアソシエーションは、Multiple Object Tracking(MOT)タスクの中核にある。
既存の手法は、主にトラックレットとフレーム内検出の間のコンテキスト情報を無視する。
そこで本研究では,学習可能なグラフマッチング手法を提案する。
論文 参考訳(メタデータ) (2021-03-30T08:58:45Z) - Wasserstein-based Graph Alignment [56.84964475441094]
我々は,より小さいグラフのノードと大きなグラフのノードをマッチングすることを目的とした,1対多のグラフアライメント問題に対する新しい定式化を行った。
提案手法は,各タスクに対する最先端のアルゴリズムに対して,大幅な改善をもたらすことを示す。
論文 参考訳(メタデータ) (2020-03-12T22:31:59Z) - Variance Reduction with Sparse Gradients [82.41780420431205]
SVRGやSpiderBoostのような分散還元法では、大きなバッチ勾配と小さなバッチ勾配が混在している。
我々は、新しい空間演算子:ランダムトップk演算子を導入する。
我々のアルゴリズムは、画像分類、自然言語処理、スパース行列分解など様々なタスクにおいて、一貫してSpiderBoostより優れています。
論文 参考訳(メタデータ) (2020-01-27T08:23:58Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。