論文の概要: CSGO: Constrained-Softassign Gradient Optimization For Large Graph Matching

• arxiv url: http://arxiv.org/abs/2208.08233v4
• Date: Tue, 10 Dec 2024 09:19:24 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-12-11 14:33:08.388465
• Title: CSGO: Constrained-Softassign Gradient Optimization For Large Graph Matching
• Title（参考訳）: CSGO:大規模グラフマッチングのための制約付きソフトデザイン勾配最適化
• Authors: Binrui Shen, Qiang Niu, Shengxin Zhu,
• Abstract要約: 本稿では,よく知られたグラフマッチングアルゴリズムを,制約付き勾配法というフレームワークに統合する。 属性付きグラフマッチングタスクでは、CSGOは現在の制約付き勾配アルゴリズムに比べて10倍以上の速度向上を達成する。
• 参考スコア（独自算出の注目度）: 0.7456521449098222
• License:
• Abstract: Graph matching aims to find correspondences between two graphs. This paper integrates several well-known graph matching algorithms into a framework: the constrained gradient method. The primary difference among these algorithms lies in tuning a step size parameter and constraining operators. By leveraging these insights, we propose an adaptive step size parameter to guarantee the underlying algorithms' convergence, simultaneously enhancing their efficiency and robustness. For the constraining operator, we introduce a scalable softassign for large graph matching problems. Compared to the original softassign, our approach offers increased speed, improved robustness, and reduced risk of overflow. The advanced constraining operator enables a CSGO for large graph matching, which outperforms state-of-the-art methods in experiments. Notably, in attributed graph matching tasks, CSGO achieves an over 10X increase in speed compared to current constrained gradient algorithms.
• Abstract（参考訳）: グラフマッチングは、2つのグラフ間の対応を見つけることを目的としている。 本稿では,よく知られたグラフマッチングアルゴリズムを,制約付き勾配法というフレームワークに統合する。 これらのアルゴリズムの主な違いは、ステップサイズパラメータと制約演算子をチューニングすることである。 これらの知見を利用して,アルゴリズムの収束を保証する適応的なステップサイズパラメータを提案し,その効率性とロバスト性を向上させる。 制約演算子に対しては,大規模グラフマッチング問題に対するスケーラブルなソフトアサインを導入する。 従来のソフトアサインと比較すると,本手法は速度の向上,ロバスト性の向上,オーバーフローのリスク低減を実現している。 高度な制約演算子は、実験における最先端の手法よりも優れた大きなグラフマッチングのためのCSGOを可能にする。 特に、属性付きグラフマッチングタスクでは、CSGOは現在の制約付き勾配アルゴリズムに比べて10倍以上の速度向上を達成する。

関連論文リスト

• 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)

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

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