論文の概要: Dynamical softassign and adaptive parameter tuning for graph matching
- arxiv url: http://arxiv.org/abs/2208.08233v1
- Date: Wed, 17 Aug 2022 11:25:03 GMT
- ステータス: 処理完了
- システム内更新日: 2022-08-18 13:34:09.015940
- Title: Dynamical softassign and adaptive parameter tuning for graph matching
- Title(参考訳): グラフマッチングのための動的ソフトアサインと適応パラメータチューニング
- Authors: Binrui Shen, Qiang Niu, Shengxin Zhu
- Abstract要約: 本稿では,グラフマッチングのためのフレームワーク,射影固定点法について検討する。
本稿では,このフレームワークのステップサイズパラメータを調整するための適応戦略を提案する。
本稿では,動的ソフトアサイン付き適応投影固定点法という新しいグラフマッチングアルゴリズムを提案する。
- 参考スコア(独自算出の注目度): 0.36832029288386137
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: This paper studies a framework, projected fixed-point method, for graph
matching. The framework contains a class of popular graph matching algorithms,
including graduated assignment (GA), integer projected fixed-point method
(IPFP) and doubly stochastic projected fixed-point method (DSPFP). We propose
an adaptive strategy to tune the step size parameter in this framework. Such a
strategy improves these algorithms in efficiency and accuracy. Further, it
guarantees the convergence of the underlying algorithms. Some preliminary
analysis based on distance geometry seems to support that the optimal step size
parameter has a high probability of 1 when graphs are fully connected.
Secondly, it is observed that a popular projection method, softassign, is
sensitive to graphs' cardinality(size). We proposed a dynamical softassign
algorithm that is robust to graphs' cardinality. Combining the adaptive step
size and the dynamical softassign, we propose a novel graph matching algorithm:
the adaptive projected fixed-point method with dynamical softassign. Various
experiments demonstrate that the proposed algorithm is significantly faster
than several other state-of-art algorithms with no loss of accuracy.
- Abstract(参考訳): 本稿では,グラフマッチングのためのフレームワーク,射影固定点法について検討する。
このフレームワークは、逐次代入(GA)、整数射影固定点法(IPFP)、二重確率射影固定点法(DSPFP)を含む人気のあるグラフマッチングアルゴリズムのクラスを含む。
本フレームワークでは,ステップサイズパラメータをチューニングするための適応戦略を提案する。
このような戦略はこれらのアルゴリズムを効率と精度で改善する。
さらに、基礎となるアルゴリズムの収束を保証する。
距離幾何学に基づく予備解析では、グラフが完全連結であるときに最適なステップサイズパラメータが 1 の確率が高いことを支持しているようである。
次に,人気のある投影法であるsoftassignは,グラフの濃度(サイズ)に敏感であることがわかった。
我々は,グラフの濃度にロバストな動的ソフトアサインアルゴリズムを提案する。
適応的なステップサイズと動的ソフトアサインを組み合わせることで,動的ソフトアサイン付き適応投影固定点法という新しいグラフマッチングアルゴリズムを提案する。
様々な実験により、提案アルゴリズムは精度を損なうことなく、他の最先端アルゴリズムよりも大幅に高速であることが示された。
関連論文リスト
- 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。