論文の概要: Computing Approximate Graph Edit Distance via Optimal Transport
- arxiv url: http://arxiv.org/abs/2412.18857v1
- Date: Wed, 25 Dec 2024 09:55:14 GMT
- ステータス: 翻訳完了
- システム内更新日: 2024-12-30 17:28:40.520003
- Title: Computing Approximate Graph Edit Distance via Optimal Transport
- Title（参考訳）: 最適移動によるグラフ編集距離の計算
- Authors: Qihao Cheng, Da Yan, Tianhao Wu, Zhongyi Huang, Qin Zhang,
- Abstract要約: グラフペア$(G1, G2)$が与えられたとき、グラフ編集距離(GED)は、G1$から$G2$に変換する編集操作の最小数として定義される。
GEDIOTは、学習可能なシンクホーンアルゴリズムを利用して結合行列を生成する逆最適輸送に基づいている。
GEDGWは最適輸送と変種であるGromov-Wassersteinの不一致の線形結合としてGED計算をモデル化した。
- 参考スコア（独自算出の注目度）: 16.327678462502668
- License:
- Abstract: Given a graph pair $(G^1, G^2)$, graph edit distance (GED) is defined as the minimum number of edit operations converting $G^1$ to $G^2$. GED is a fundamental operation widely used in many applications, but its exact computation is NP-hard, so the approximation of GED has gained a lot of attention. Data-driven learning-based methods have been found to provide superior results compared to classical approximate algorithms, but they directly fit the coupling relationship between a pair of vertices from their vertex features. We argue that while pairwise vertex features can capture the coupling cost (discrepancy) of a pair of vertices, the vertex coupling matrix should be derived from the vertex-pair cost matrix through a more well-established method that is aware of the global context of the graph pair, such as optimal transport. In this paper, we propose an ensemble approach that integrates a supervised learning-based method and an unsupervised method, both based on optimal transport. Our learning method, GEDIOT, is based on inverse optimal transport that leverages a learnable Sinkhorn algorithm to generate the coupling matrix. Our unsupervised method, GEDGW, models GED computation as a linear combination of optimal transport and its variant, Gromov-Wasserstein discrepancy, for node and edge operations, respectively, which can be solved efficiently without needing the ground truth. Our ensemble method, GEDHOT, combines GEDIOT and GEDGW to further boost the performance. Extensive experiments demonstrate that our methods significantly outperform the existing methods in terms of the performance of GED computation, edit path generation, and model generalizability.
- Abstract（参考訳）: グラフペア$(G^1, G^2)$が与えられたとき、グラフ編集距離(GED)は、$G^1$から$G^2$に変換する編集操作の最小数として定義される。
GEDは多くのアプリケーションで広く使われている基本演算であるが、その正確な計算はNPハードであるため、GEDの近似は注目されている。
データ駆動学習に基づく手法は、古典的近似アルゴリズムよりも優れた結果が得られたが、頂点の特徴から頂点の対の結合関係に直接適合する。
頂点結合行列は頂点対の結合コスト(離散性)を捉えることができるが、最適輸送のようなグラフ対のグローバルな文脈を意識したより確立された手法により、頂点対のコスト行列から導出すべきである。
本稿では,教師あり学習法と教師なし学習法を統合したアンサンブル手法を提案する。
我々の学習手法であるGEDIOTは、学習可能なシンクホーンアルゴリズムを利用して結合行列を生成する逆最適輸送に基づいている。
我々の教師なし手法であるGEDGWは、最適輸送と変種であるGromov-Wassersteinの不一致の線形結合としてGED計算をモデル化する。
我々のアンサンブル手法であるGEDHOTはGEDIOTとGEDGWを組み合わせて性能をさらに向上させる。
本手法は,GED計算の性能,経路生成の編集,モデル一般化性の観点から,既存の手法よりも優れていることを示す。
関連論文リスト
- Near-Optimal Online Learning for Multi-Agent Submodular Coordination: Tight Approximation and Communication Efficiency [52.60557300927007]
離散部分モジュラー問題を連続的に最適化するために,$textbfMA-OSMA$アルゴリズムを提案する。
また、一様分布を混合することによりKLの発散を効果的に活用する、プロジェクションフリーな$textbfMA-OSEA$アルゴリズムも導入する。
我々のアルゴリズムは最先端OSGアルゴリズムによって提供される$(frac11+c)$-approximationを大幅に改善する。
論文 参考訳（メタデータ） (2025-02-07T15:57:56Z) - Graph Similarity Computation via Interpretable Neural Node Alignment [19.34487413883093]
GED(Graph Edit Distance)とMCS(Maximum Common Subgraphs)は、グラフの類似性を評価するために一般的に使用されるメトリクスである。
ディープラーニングモデルはよく知られたブラックボックス'であるため、典型的な1対1のノード/サブグラフアライメントプロセスは見ることができない。
我々は,ノードアライメント基底真理情報に頼ることなく,新しい解釈可能なニューラルノードアライメントモデルを提案する。
論文 参考訳（メタデータ） (2024-12-13T10:23:27Z) - Adaptive Principal Components Allocation with the $\ell_{2,g}$-regularized Gaussian Graphical Model for Efficient Fine-Tuning Large Models [7.6656660956453635]
ガウス図形モデル(GGM)に基づく高速ファインニング(PEFT)手法を提案する。
提案手法の有効性を実証し、トレーニング可能なパラメータを著しく少なくして競合性能を実現する。
論文 参考訳（メタデータ） (2024-12-11T18:11:21Z) - GDSG: Graph Diffusion-based Solution Generator for Optimization Problems in MEC Networks [109.17835015018532]
グラフ拡散型ソリューション生成(GDSG)法を提案する。
このアプローチは、おそらく最適な解に収束しながら、最適以下のデータセットを扱うように設計されている。
グラフニューラルネットワーク(GNN)を用いたマルチタスク拡散モデルとしてGDSGを構築し,高品質な解の分布を求める。
論文 参考訳（メタデータ） (2024-12-11T11:13:43Z) - Efficient Graph Similarity Computation with Alignment Regularization [7.143879014059894]
グラフ類似性計算(GSC)は、グラフニューラルネットワーク(GNN)を用いた学習に基づく予測タスクである。
適応正規化(AReg)と呼ばれる,シンプルながら強力な正規化技術によって,高品質な学習が達成可能であることを示す。
推論段階では、GNNエンコーダによって学習されたグラフレベル表現は、ARegを再度使用せずに直接類似度スコアを計算するために使用される。
論文 参考訳（メタデータ） (2024-06-21T07:37:28Z) - Combining Optimal Transport and Embedding-Based Approaches for More Expressiveness in Unsupervised Graph Alignment [19.145556156889064]
教師なしグラフアライメントは、グラフ構造とノード特徴のみを利用して、属性グラフのペア間の1対1ノード対応を見つける。
モデル表現性の理論的解析によって動機付けられたそれらの利点を組み合わせるための原理的アプローチを提案する。
我々は,問題を最大重み付けに還元することで,一対一のマッチング制約を最初に保証する。
論文 参考訳（メタデータ） (2024-06-19T04:57:35Z) - Ensemble Quadratic Assignment Network for Graph Matching [52.20001802006391]
グラフマッチングはコンピュータビジョンやパターン認識において一般的に用いられる技法である。
最近のデータ駆動型アプローチは、グラフマッチングの精度を著しく改善した。
データ駆動手法と従来の手法の利点を組み合わせたグラフニューラルネットワーク(GNN)に基づくアプローチを提案する。
論文 参考訳（メタデータ） (2024-03-11T06:34:05Z) - MATA*: Combining Learnable Node Matching with A* Algorithm for
Approximate Graph Edit Distance Computation [12.437507185260577]
正確なグラフ編集距離(GED)計算はNP完全であることが知られている。
グラフニューラルネットワーク(GNN)とA*アルゴリズムに基づく近似GED計算のためのデータ駆動型ハイブリッドアプローチMATA*を提案する。
論文 参考訳（メタデータ） (2023-11-04T09:33:08Z) - Leveraging Non-uniformity in First-order Non-convex Optimization [93.6817946818977]
目的関数の非一様洗練は、emphNon-uniform Smoothness(NS)とemphNon-uniform Lojasiewicz inequality(NL)につながる
新しい定義は、古典的な$Omega (1/t2)$下界よりも早く大域的最適性に収束する新しい幾何学的一階法を刺激する。
論文 参考訳（メタデータ） (2021-05-13T04:23:07Z) - Deep Reinforcement Learning of Graph Matching [63.469961545293756]
ノードとペアの制約下でのグラフマッチング(GM)は、最適化からコンピュータビジョンまでの領域におけるビルディングブロックである。
GMのための強化学習ソルバを提案する。
rgmはペアワイズグラフ間のノード対応を求める。
本手法は,フロントエンドの特徴抽出と親和性関数学習に焦点をあてるという意味において,従来のディープグラフマッチングモデルと異なる。
論文 参考訳（メタデータ） (2020-12-16T13:48:48Z) - Stochastic Flows and Geometric Optimization on the Orthogonal Group [52.50121190744979]
直交群 $O(d)$ 上の幾何駆動最適化アルゴリズムの新しいクラスを示す。
提案手法は,深層,畳み込み,反復的なニューラルネットワーク,強化学習,フロー,メトリック学習など,機械学習のさまざまな分野に適用可能であることを示す。
論文 参考訳（メタデータ） (2020-03-30T15:37:50Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。