論文の概要: DiffGED: Computing Graph Edit Distance via Diffusion-based Graph Matching
- arxiv url: http://arxiv.org/abs/2503.18245v1
- Date: Mon, 24 Mar 2025 00:03:16 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-03-25 14:34:45.978362
- Title: DiffGED: Computing Graph Edit Distance via Diffusion-based Graph Matching
- Title（参考訳）: DiffGED:拡散グラフマッチングによるグラフ編集距離の計算
- Authors: Wei Huang, Hanchen Wang, Dong Wen, Wenjie Zhang, Ying Zhang, Xuemin Lin,
- Abstract要約: グラフ編集距離(GED)問題は、あるグラフを別のグラフに変換するのに必要な編集操作の最小数を計算することを目的としている。
本稿では、生成拡散モデルを利用してGEDを解き、対応する編集経路を復元する新しい手法DiffGEDを提案する。
- 参考スコア（独自算出の注目度）: 32.853086706407986
- License:
- Abstract: The Graph Edit Distance (GED) problem, which aims to compute the minimum number of edit operations required to transform one graph into another, is a fundamental challenge in graph analysis with wide-ranging applications. However, due to its NP-hard nature, traditional A* approaches often suffer from scalability issue, making them computationally intractable for large graphs. Many recent deep learning frameworks address GED by formulating it as a regression task, which, while efficient, fails to recover the edit path -- a central interest in GED. Furthermore, recent hybrid approaches that combine deep learning with traditional methods to recover the edit path often yield poor solution quality. These methods also struggle to generate candidate solutions in parallel, resulting in increased running times.In this paper, we present a novel approach, DiffGED, that leverages generative diffusion model to solve GED and recover the corresponding edit path. Specifically, we first generate multiple diverse node matching matrices in parallel through a diffusion-based graph matching model. Next, node mappings are extracted from each generated matching matrices in parallel, and each extracted node mapping can be simply transformed into an edit path. Benefiting from the generative diversity provided by the diffusion model, DiffGED is less likely to fall into local sub-optimal solutions, thereby achieving superior overall solution quality close to the exact solution. Experimental results on real-world datasets demonstrate that DiffGED can generate multiple diverse edit paths with exceptionally high accuracy comparable to exact solutions while maintaining a running time shorter than most of hybrid approaches.
- Abstract（参考訳）: グラフ編集距離(GED)問題は、あるグラフを別のグラフに変換するのに必要な最小の編集操作数を計算することを目的としており、広範囲のアプリケーションによるグラフ解析において根本的な課題である。
しかし、NPハードな性質のため、従来のA*アプローチはスケーラビリティの問題に悩まされることが多く、大きなグラフに対して計算的に難解である。
最近のディープラーニングフレームワークの多くは、回帰タスクとしてGEDを定式化することによって、GEDに対処している。
さらに、最近のハイブリッドアプローチでは、ディープラーニングと編集パスを復元する従来の方法を組み合わせることで、ソリューションの品質が低下することが多い。
本稿では,生成拡散モデルを利用してGEDを解き,対応する編集経路を復元する新しい手法DiffGEDを提案する。
具体的には,拡散型グラフマッチングモデルを用いて,複数のノードマッチング行列を並列に生成する。
次に、生成されたマッチング行列から並列にノードマッピングを抽出し、抽出したノードマッピングを編集パスに変換する。
DiffGEDは拡散モデルによって提供される生成的多様性から得られる利点により、局所最適解に分解されることが少なくなり、より正確な解に近い総合的な解品質を達成することができる。
実世界のデータセットに対する実験結果から、DiffGEDは、多くのハイブリッドアプローチよりも短い実行時間を維持しながら、正確なソリューションに匹敵する極めて高い精度で、複数の多様な編集パスを生成できることが示されている。
関連論文リスト
- Ensemble Quadratic Assignment Network for Graph Matching [52.20001802006391]
グラフマッチングはコンピュータビジョンやパターン認識において一般的に用いられる技法である。
最近のデータ駆動型アプローチは、グラフマッチングの精度を著しく改善した。
データ駆動手法と従来の手法の利点を組み合わせたグラフニューラルネットワーク(GNN)に基づくアプローチを提案する。
論文 参考訳（メタデータ） (2024-03-11T06:34:05Z) - Deep Manifold Graph Auto-Encoder for Attributed Graph Embedding [51.75091298017941]
本稿では,属性付きグラフデータに対する新しいDeep Manifold (Variational) Graph Auto-Encoder (DMVGAE/DMGAE)を提案する。
提案手法は,最先端のベースラインアルゴリズムを,一般的なデータセット間でのダウンストリームタスクの差を大きく越える。
論文 参考訳（メタデータ） (2024-01-12T17:57:07Z) - 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) - Symmetry-preserving graph attention network to solve routing problems at
multiple resolutions [1.9304772860080408]
問題解決のために,最初の完全同変モデルとトレーニングを導入する。
入力グラフのマルチスケール構造を捉えることが不可欠である。
本稿では,Equi Graph Attention Network (mEGAT) アーキテクチャと組み合わせたマルチレゾリューション方式を提案する。
論文 参考訳（メタデータ） (2023-10-24T06:22:20Z) - NodeFormer: A Scalable Graph Structure Learning Transformer for Node
Classification [70.51126383984555]
本稿では,任意のノード間のノード信号を効率的に伝搬する全ペアメッセージパッシング方式を提案する。
効率的な計算は、カーナライズされたGumbel-Softmax演算子によって実現される。
グラフ上のノード分類を含む様々なタスクにおいて,本手法の有望な有効性を示す実験を行った。
論文 参考訳（メタデータ） (2023-06-14T09:21:15Z) - Addressing Heterophily in Node Classification with Graph Echo State
Networks [11.52174067809364]
ノード分類のためのグラフエコー状態ネットワーク(GESN)を用いた異種グラフの課題に対処する。
GESNはグラフのための貯水池計算モデルであり、ノードの埋め込みは訓練されていないメッセージパッシング関数によって計算される。
実験の結果, 貯水池モデルでは, ほぼ完全に訓練された深層モデルに対して, より優れた精度あるいは同等の精度が得られることがわかった。
論文 参考訳（メタデータ） (2023-05-14T19:42:31Z) - Score-based Generative Modeling of Graphs via the System of Stochastic
Differential Equations [57.15855198512551]
本稿では,連続時間フレームワークを用いたグラフのスコアベース生成モデルを提案する。
本手法は, トレーニング分布に近い分子を生成できるが, 化学価数則に違反しないことを示す。
論文 参考訳（メタデータ） (2022-02-05T08:21:04Z) - A Robust and Generalized Framework for Adversarial Graph Embedding [73.37228022428663]
本稿では,AGE という逆グラフ埋め込みのための頑健なフレームワークを提案する。
AGEは、暗黙の分布から強化された負のサンプルとして偽の隣接ノードを生成する。
本フレームワークでは,3種類のグラフデータを扱う3つのモデルを提案する。
論文 参考訳（メタデータ） (2021-05-22T07:05:48Z) - Combinatorial Learning of Graph Edit Distance via Dynamic Embedding [108.49014907941891]
本稿では,従来の検索手法による編集経路の解釈可能性を組み合わせたハイブリッド手法を提案する。
動的プログラミングにインスパイアされたノードレベルの埋め込みは、動的再利用方式で指定され、サブ最適分岐がプルーニングされることが推奨される。
異なるグラフデータセットを用いた実験結果から,A* の探索処理は精度を犠牲にすることなく極めて容易であることが示唆された。
論文 参考訳（メタデータ） (2020-11-30T17:41:02Z) - A Generative Graph Method to Solve the Travelling Salesman Problem [1.552282932199974]
我々は,旅行セールスマン問題(TSP)を概ね解決するために,生成的アプローチである新しいグラフ学習ネットワーク(GLN)を提案する。
GLNモデルは、トレーニングデータセットとしてTSPインスタンスのパターンを直接学習し、グラフプロパティをエンコードし、異なるノードの埋め込みをマージして、最適なツアーを出力する。
論文 参考訳（メタデータ） (2020-07-09T17:23:55Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。