論文の概要: 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は,グラフの濃度(サイズ)に敏感であることがわかった。
我々は,グラフの濃度にロバストな動的ソフトアサインアルゴリズムを提案する。
適応的なステップサイズと動的ソフトアサインを組み合わせることで,動的ソフトアサイン付き適応投影固定点法という新しいグラフマッチングアルゴリズムを提案する。
様々な実験により、提案アルゴリズムは精度を損なうことなく、他の最先端アルゴリズムよりも大幅に高速であることが示された。
関連論文リスト
- Ensemble Quadratic Assignment Network for Graph Matching [52.20001802006391]
グラフマッチングはコンピュータビジョンやパターン認識において一般的に用いられる技法である。
最近のデータ駆動型アプローチは、グラフマッチングの精度を著しく改善した。
データ駆動手法と従来の手法の利点を組み合わせたグラフニューラルネットワーク(GNN)に基づくアプローチを提案する。
論文 参考訳(メタデータ) (2024-03-11T06:34:05Z) - Stochastic Ratios Tracking Algorithm for Large Scale Machine Learning
Problems [0.7614628596146599]
古典的なSGDフレームワークにおける適応的なステップ長選択のための新しいアルゴリズムを提案する。
妥当な条件下では、アルゴリズムは十分に確立された理論的な要件に従ってステップ長を生成する。
このアルゴリズムは,手動チューニングから得られる最良ステップ長に匹敵するステップ長を生成することができることを示す。
論文 参考訳(メタデータ) (2023-05-17T06:22:11Z) - Fast and Provably Convergent Algorithms for Gromov-Wasserstein in Graph
Learning [37.89640056739607]
2つのアルゴリズム、Bregman Alternating Projected Gradient (BAPG) とハイブリッドBregman Proximal Gradient (hBPG) は(ほぼ)収束することが証明されている。
グラフアライメント,グラフ分割,形状マッチングなど,タスクのホスト上での手法の有効性を検証するための総合的な実験を行った。
論文 参考訳(メタデータ) (2022-05-17T06:26:54Z) - Effective and efficient structure learning with pruning and model
averaging strategies [9.023722579074734]
本稿では,2つの新しい手法と丘登り探索を組み合わせたBN構造学習アルゴリズムについて述べる。
アルゴリズムは探索空間グラフをプルーニングすることから始まり、プルーニング戦略をプルーニング戦略のアグレッシブバージョンと見なすことができる。
そして、ヒルクライミング探索プロセスで平均化を行い、目的関数を最大化する近隣グラフに移動する。
論文 参考訳(メタデータ) (2021-12-01T10:35:34Z) - Graph Matching via Optimal Transport [11.93151370164898]
グラフマッチング問題の解決は、運用研究、コンピュータビジョン、神経科学などへの応用により、ますます重要になっている。
現在の最先端のアルゴリズムは、非常に大きなグラフのマッチングには非効率であるが、精度は高い。
我々は,最新のグラフマッチングアルゴリズム "FAQ" (Vogelstein, 2015) を改良した GOAT を,その線形和割り当てステップを Cuturi (2013) の "Lightspeed Optimal Transport" メソッドに置き換える。
論文 参考訳(メタデータ) (2021-11-09T19:18:18Z) - Efficient proximal gradient algorithms for joint graphical lasso [9.752101654013053]
スパースデータから非方向のグラフィカルモデルを学ぶことを検討する。
JGL(ジョイント・グラフィカル・ラッソ)のバックトラックオプションを伴わない近位勾配法を提案する。
提案アルゴリズムは高い精度と精度を達成でき、その効率は最先端のアルゴリズムと競合する。
論文 参考訳(メタデータ) (2021-07-16T09:59:13Z) - Graph Signal Restoration Using Nested Deep Algorithm Unrolling [85.53158261016331]
グラフ信号処理は、センサー、社会交通脳ネットワーク、ポイントクラウド処理、グラフネットワークなど、多くのアプリケーションにおいてユビキタスなタスクである。
凸非依存型深部ADMM(ADMM)に基づく2つの復元手法を提案する。
提案手法のパラメータはエンドツーエンドでトレーニング可能である。
論文 参考訳(メタデータ) (2021-06-30T08:57:01Z) - Accelerated Message Passing for Entropy-Regularized MAP Inference [89.15658822319928]
離散値のランダムフィールドにおけるMAP推論の最大化は、機械学習の基本的な問題である。
この問題の難しさから、特殊メッセージパッシングアルゴリズムの導出には線形プログラミング(LP)緩和が一般的である。
古典的加速勾配の根底にある手法を活用することにより,これらのアルゴリズムを高速化するランダム化手法を提案する。
論文 参考訳(メタデータ) (2020-07-01T18:43:32Z) - Online Dense Subgraph Discovery via Blurred-Graph Feedback [87.9850024070244]
我々は高密度サブグラフ発見のための新しい学習問題を導入する。
まず,確率の高いほぼ最適解を求めるエッジ時間アルゴリズムを提案する。
そして、理論的保証のあるよりスケーラブルなアルゴリズムを設計する。
論文 参考訳(メタデータ) (2020-06-24T11:37:33Z) - Wasserstein-based Graph Alignment [56.84964475441094]
我々は,より小さいグラフのノードと大きなグラフのノードをマッチングすることを目的とした,1対多のグラフアライメント問題に対する新しい定式化を行った。
提案手法は,各タスクに対する最先端のアルゴリズムに対して,大幅な改善をもたらすことを示す。
論文 参考訳(メタデータ) (2020-03-12T22:31:59Z) - Adaptivity of Stochastic Gradient Methods for Nonconvex Optimization [71.03797261151605]
適応性は現代最適化理論において重要であるが、研究されていない性質である。
提案アルゴリズムは,PL目標に対して既存のアルゴリズムよりも優れた性能を保ちながら,PL目標に対して最適な収束性を実現することを実証した。
論文 参考訳(メタデータ) (2020-02-13T05:42:27Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。