論文の概要: Towards Unsupervised Training of Matching-based Graph Edit Distance Solver via Preference-aware GAN

• arxiv url: http://arxiv.org/abs/2506.01977v1
• Date: Fri, 16 May 2025 03:45:31 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-06-08 12:40:08.651188
• Title: Towards Unsupervised Training of Matching-based Graph Edit Distance Solver via Preference-aware GAN
• Title（参考訳）: 優先認識型GANによるマッチング型グラフ編集距離解法の教師なし学習に向けて
• Authors: Wei Huang, Hanchen Wang, Dong Wen, Shaozhen Ma, Wenjie Zhang, Xuemin Lin,
• Abstract要約: グラフ編集距離 (Graph Edit Distance, GED) は、様々なアプリケーションで広く使われている基本的なグラフ類似度尺度である。 最近の最先端ハイブリッドGEDソルバは有望な性能を示した。 GED計算のための新しい教師なしGANベースのフレームワークであるGEDRankerを提案する。
• 参考スコア（独自算出の注目度）: 29.471035994169323
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Graph Edit Distance (GED) is a fundamental graph similarity metric widely used in various applications. However, computing GED is an NP-hard problem. Recent state-of-the-art hybrid GED solver has shown promising performance by formulating GED as a bipartite graph matching problem, then leveraging a generative diffusion model to predict node matching between two graphs, from which both the GED and its corresponding edit path can be extracted using a traditional algorithm. However, such methods typically rely heavily on ground-truth supervision, where the ground-truth labels are often costly to obtain in real-world scenarios. In this paper, we propose GEDRanker, a novel unsupervised GAN-based framework for GED computation. Specifically, GEDRanker consists of a matching-based GED solver and introduces an interpretable preference-aware discriminator with an effective training strategy to guide the matching-based GED solver toward generating high-quality node matching without the need for ground-truth labels. Extensive experiments on benchmark datasets demonstrate that our GEDRanker enables the matching-based GED solver to achieve near-optimal solution quality without any ground-truth supervision.
• Abstract（参考訳）: グラフ編集距離 (Graph Edit Distance, GED) は、様々なアプリケーションで広く使われている基本的なグラフ類似度尺度である。 しかし、GEDの計算はNPハード問題である。 最近の最先端ハイブリッドGEDソルバは、GEDを二部グラフマッチング問題として定式化し、生成拡散モデルを用いて2つのグラフ間のノードマッチングを予測し、GEDとそれに対応する編集経路を従来のアルゴリズムで抽出することで、有望な性能を示した。 しかし、そのような手法は一般に地上の交通管理に大きく依存しており、そこでは地上の交通ラベルが現実のシナリオで入手するのにしばしばコストがかかる。 本稿では,GEDRankerを提案する。GEDRankerは,GED計算のための新しい教師なしGANベースのフレームワークである。 具体的には、GEDRankerは、マッチングベースのGEDソルバと、マッチングベースのGEDソルバをグランドトラストラベルを必要とせずに高品質なノードマッチングを生成するための効果的なトレーニング戦略を備えた解釈可能な選好認識判別器を導入している。 ベンチマークデータセットに関する大規模な実験により、我々のGEDRankerは、マッチングベースのGEDソルバが、基盤的トラストの監督なしに、ほぼ最適のソリューション品質を達成できることを示した。

関連論文リスト

• Pave Your Own Path: Graph Gradual Domain Adaptation on Fused Gromov-Wasserstein Geodesics [59.07903030446756]
  グラフニューラルネットワークは、グラフ上の分散シフトに対して非常に脆弱である。 非IIDグラフデータのための最初のフレームワークであるGadgetを提示する。 ガジェットは既存のグラフDAメソッドとシームレスに統合して、グラフ上の大きなシフトを処理することができる。
  論文  参考訳（メタデータ） (2025-05-19T05:03:58Z)
• GRAIL: Graph Edit Distance and Node Alignment Using LLM-Generated Code [11.73546901244934]
  グラフ編集距離 (Graph Edit Distance, GED) は、2つのグラフ間の類似度を測定するために広く用いられている尺度である。 ニューラルメソッドは、非ニューラルアプローチと比較して近似品質の改善を実現している。 GRAILは、大規模言語モデル(LLM)と自動プロンプトチューニングを組み合わせて、GEDの計算に使用されるプログラムを生成する。
  論文  参考訳（メタデータ） (2025-05-04T14:14:24Z)
• DiffGED: Computing Graph Edit Distance via Diffusion-based Graph Matching [32.853086706407986]
  グラフ編集距離(GED)問題は、あるグラフを別のグラフに変換するのに必要な編集操作の最小数を計算することを目的としている。 本稿では、生成拡散モデルを利用してGEDを解き、対応する編集経路を復元する新しい手法DiffGEDを提案する。
  論文  参考訳（メタデータ） (2025-03-24T00:03:16Z)
• Computing Approximate Graph Edit Distance via Optimal Transport [16.327678462502668]
  グラフペア$(G1, G2)$が与えられたとき、グラフ編集距離(GED)は、G1$から$G2$に変換する編集操作の最小数として定義される。 GEDIOTは、学習可能なシンクホーンアルゴリズムを利用して結合行列を生成する逆最適輸送に基づいている。 GEDGWは最適輸送と変種であるGromov-Wassersteinの不一致の線形結合としてGED計算をモデル化した。
  論文  参考訳（メタデータ） (2024-12-25T09:55:14Z)
• GeoMix: Towards Geometry-Aware Data Augmentation [76.09914619612812]
  Mixupは画像分類におけるラベル付き限られたデータによる課題の緩和にかなりの成功を収めている。 In-place graph editing を利用した簡易かつ解釈可能な混合手法 Geometric Mixup (GeoMix) を提案する。
  論文  参考訳（メタデータ） (2024-07-15T12:58:04Z)
• EUGENE: Explainable Unsupervised Approximation of Graph Edit Distance with Generalized Edit Costs [20.3519249026886]
  グラフ編集距離(GED)は、グラフ間距離を測定するために好ましい。 GED計算はNPハードネスによって妨げられる。 教師なしの手法は、しばしば正確な近似を提供する際の課題に直面する。
  論文  参考訳（メタデータ） (2024-02-08T18:23: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)
• 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)
• 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)
• Inverse Graph Identification: Can We Identify Node Labels Given Graph Labels? [89.13567439679709]
  グラフ識別(GI)は、グラフ学習において長い間研究されており、特定の応用において不可欠である。 本稿では,逆グラフ識別(Inverse Graph Identification, IGI)と呼ばれる新しい問題を定義する。 本稿では,グラフアテンションネットワーク(GAT)を用いたノードレベルのメッセージパッシング処理を,GIのプロトコルの下でシンプルかつ効果的に行う方法を提案する。
  論文  参考訳（メタデータ） (2020-07-12T12:06:17Z)

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

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