論文の概要: Optimal Partial Graph Matching

• arxiv url: http://arxiv.org/abs/2410.16718v1
• Date: Tue, 22 Oct 2024 05:56:57 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-10-23 14:28:07.587073
• Title: Optimal Partial Graph Matching
• Title（参考訳）: 最適部分グラフマッチング
• Authors: Gathika Ratnayaka, James Nichols, Qing Wang,
• Abstract要約: 最適部分移動にインスパイアされた部分グラフマッチングのための新しいフレームワークを提案する。 提案手法は, 偏りを取り入れつつ部分的代入を可能にする目的を定式化したものである。 ハンガリーのアルゴリズムを用いて、立方的時間複雑性を伴う効率的で正確な解を求める。
• 参考スコア（独自算出の注目度）: 2.4378101048225735
• License:
• Abstract: Partial graph matching addresses the limitations of traditional graph matching by allowing some nodes to remain unmatched, making it applicable to more complex scenarios. However, this flexibility introduces additional complexity, as both the subset of nodes to match and the optimal mapping must be determined. While recent studies have explored deep learning techniques for partial graph matching, a significant limitation remains: the absence of an optimization objective that fully captures the problem's intrinsic nature while enabling efficient solutions. In this paper, we propose a novel optimization framework for partial graph matching, inspired by optimal partial transport. Our approach formulates an objective that enables partial assignments while incorporating matching biases, using weighted total variation as the divergence function to guarantee optimal partial assignments. We employ the Hungarian algorithm to achieve efficient, exact solutions with cubic time complexity. Our contributions are threefold: (i) we introduce a robust optimization objective that balances matched and unmatched nodes; (ii) we establish a connection between partial graph matching and the linear sum assignment problem, enabling efficient solutions; (iii) we propose a deep graph matching architecture with a novel partial matching loss, providing an end-to-end solution. The empirical evaluations on standard graph matching benchmarks demonstrate the efficacy of the proposed approach.
• Abstract（参考訳）: 部分グラフマッチングは、いくつかのノードが未整合のままでいられることによって、より複雑なシナリオに適用できる、従来のグラフマッチングの制限に対処する。 しかし、この柔軟性は、一致すべきノードのサブセットと最適なマッピングの両方を決定する必要があるため、さらなる複雑さをもたらす。 最近の研究では、部分グラフマッチングのためのディープラーニング技術について検討されているが、重要な制限が残っている。 本稿では,最適部分移動にインスパイアされた部分グラフマッチングのための新しい最適化フレームワークを提案する。 提案手法は, 偏りの重み付き全変動を分散関数として用いて, 最適部分割当を保証しながら部分割当を可能にする目的を定式化する。 ハンガリーのアルゴリズムを用いて、立方的時間複雑性を伴う効率的で正確な解を求める。 私たちの貢献は3倍です。 (i)一致ノードと未一致ノードのバランスをとる頑健な最適化目標を導入する。 (ii)部分グラフマッチングと線形和代入問題との接続を確立し、効率的な解を実現する。 第三に,新たな部分的マッチング損失を伴い,エンドツーエンドのソリューションを提供するディープグラフマッチングアーキテクチャを提案する。 標準グラフマッチングベンチマークにおける実証評価は,提案手法の有効性を示す。

関連論文リスト

• Combining Optimal Transport and Embedding-Based Approaches for More Expressiveness in Unsupervised Graph Alignment [19.145556156889064]
  教師なしグラフアライメントは、グラフ構造とノード特徴のみを利用して、属性グラフのペア間の1対1ノード対応を見つける。 モデル表現性の理論的解析によって動機付けられたそれらの利点を組み合わせるための原理的アプローチを提案する。 我々は,問題を最大重み付けに還元することで,一対一のマッチング制約を最初に保証する。
  論文  参考訳（メタデータ） (2024-06-19T04:57:35Z)
• Bayesian Optimization of Functions over Node Subsets in Graphs [14.670181702535825]
  グラフ上での最適化のための新しいフレームワークを提案する。 元のグラフの各$k$-nodeを、新しいグラフのノードにマップします。 人工環境と実環境環境の両方における実験により,提案したBOフレームワークの有効性が示された。
  論文  参考訳（メタデータ） (2024-05-24T00:24:55Z)
• Linearization Algorithms for Fully Composite Optimization [61.20539085730636]
  本稿では,完全合成最適化問題を凸コンパクト集合で解くための一階アルゴリズムについて検討する。 微分可能および非微分可能を別々に扱い、滑らかな部分のみを線形化することで目的の構造を利用する。
  論文  参考訳（メタデータ） (2023-02-24T18:41:48Z)
• Backpropagation of Unrolled Solvers with Folded Optimization [55.04219793298687]
  ディープネットワークにおけるコンポーネントとしての制約付き最適化モデルの統合は、多くの専門的な学習タスクに有望な進歩をもたらした。 1つの典型的な戦略はアルゴリズムのアンローリングであり、これは反復解法の操作による自動微分に依存している。 本稿では,非ロール最適化の後方通過に関する理論的知見を提供し,効率よく解けるバックプロパゲーション解析モデルを生成するシステムに繋がる。
  論文  参考訳（メタデータ） (2023-01-28T01:50:42Z)
• End-to-End Pareto Set Prediction with Graph Neural Networks for Multi-objective Facility Location [10.130342722193204]
  施設配置問題(FLP)は、サプライチェーンやロジスティクスで広く見られるNPハード最適化問題の典型的なクラスである。 本稿では,システム全体のコストを同時に最小化し,システム信頼性を最大化する多目的施設配置問題(MO-FLP)について考察する。 ノードとエッジの暗黙グラフ表現を学習するために、2つのグラフニューラルネットワークを構築した。
  論文  参考訳（メタデータ） (2022-10-27T07:15:55Z)
• Deep Probabilistic Graph Matching [72.6690550634166]
  本稿では,マッチング制約を伴わずに,元のQAPに適合する深層学習ベースのグラフマッチングフレームワークを提案する。 提案手法は,一般的な3つのベンチマーク(Pascal VOC,Wilow Object,SPair-71k)で評価され,すべてのベンチマークにおいて過去の最先端よりも優れていた。
  論文  参考訳（メタデータ） (2022-01-05T13:37:27Z)
• Sparse Quadratic Optimisation over the Stiefel Manifold with Application to Permutation Synchronisation [71.27989298860481]
  二次目的関数を最大化するスティーフェル多様体上の行列を求める非最適化問題に対処する。 そこで本研究では,支配的固有空間行列を求めるための,単純かつ効果的なスパーシティプロモーティングアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-09-30T19:17:35Z)
• A Bi-Level Framework for Learning to Solve Combinatorial Optimization on Graphs [91.07247251502564]
  本稿では,2つの世界の長所を結合するハイブリッドな手法を提案する。この手法では,グラフを最適化する上層学習手法とバイレベルフレームワークを開発する。 このような二段階のアプローチは、元のハードCOでの学習を単純化し、モデルキャパシティの需要を効果的に軽減することができる。
  論文  参考訳（メタデータ） (2021-06-09T09:18:18Z)
• Enhancing Balanced Graph Edge Partition with Effective Local Search [41.4257628524592]
  グラフパーティションは、ワークロードバランスを達成し、並列グラフ処理システムにおけるジョブ完了時間を短縮するための重要なコンポーネントです。 本稿では,本問題の局所探索アルゴリズムについて検討し,既存の手法による分割結果をさらに改善する。
  論文  参考訳（メタデータ） (2020-12-17T08:58:06Z)
• Divide and Learn: A Divide and Conquer Approach for Predict+Optimize [50.03608569227359]
  予測+最適化問題は、予測係数を使用する最適化プロブレムと、確率係数の機械学習を組み合わせる。 本稿では, 予測係数を1次線形関数として, 最適化問題の損失を直接表現する方法を示す。 本稿では,この制約を伴わずに最適化問題に対処し,最適化損失を用いてその係数を予測する新しい分割アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-12-04T00:26:56Z)

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

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