論文の概要: GEDAN: Learning the Edit Costs for Graph Edit Distance

• arxiv url: http://arxiv.org/abs/2508.03111v1
• Date: Tue, 05 Aug 2025 05:44:28 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-08-06 18:18:55.803431
• Title: GEDAN: Learning the Edit Costs for Graph Edit Distance
• Title（参考訳）: GEDAN: グラフ編集距離の編集コストを学習する
• Authors: Francesco Leonardi, Markus Orsi, Jean-Louis Reymond, Kaspar Riesen,
• Abstract要約: 本稿では,教師なしトレーニングと教師なしトレーニングの両方を用いてグラフ編集距離(GED)を近似する新しいグラフニューラルネットワークフレームワークを提案する。 私たちのアーキテクチャの中核となるコンポーネントは、コンテキスト対応編集コストの柔軟かつ解釈可能な学習を可能にする一般化付加モデルの統合です。
• 参考スコア（独自算出の注目度）: 0.4866486451835401
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Graph Edit Distance (GED) is defined as the minimum cost transformation of one graph into another and is a widely adopted metric for measuring the dissimilarity between graphs. The major problem of GED is that its computation is NP-hard, which has in turn led to the development of various approximation methods, including approaches based on neural networks (NN). Most of these NN-based models simplify the problem of GED by assuming unit-cost edit operations, a rather unrealistic constraint in real-world applications. In this work, we present a novel Graph Neural Network framework that approximates GED using both supervised and unsupervised training. In the unsupervised setting, it employs a gradient-only self-organizing mechanism that enables optimization without ground-truth distances. Moreover, a core component of our architecture is the integration of a Generalized Additive Model, which allows the flexible and interpretable learning of context-aware edit costs. Experimental results show that the proposed method achieves similar results as state-of-the-art reference methods, yet significantly improves both adaptability and interpretability. That is, the learned cost function offers insights into complex graph structures, making it particularly valuable in domains such as molecular analysis and structural pattern discovery.
• Abstract（参考訳）: グラフ編集距離 (Graph Edit Distance, GED) は、あるグラフから別のグラフへの最小コスト変換として定義され、グラフ間の相似性を測定するための広く採用されている指標である。 GEDの大きな問題は、その計算がNPハードであることであり、ニューラルネットワーク(NN)に基づくアプローチを含む様々な近似手法の開発につながっている。 これらのNNベースのモデルの多くは、現実のアプリケーションでは非現実的な制約であるユニットコストの編集操作を仮定することで、GEDの問題を単純化している。 本研究では,教師付きトレーニングと教師なしトレーニングの両方を用いてGEDを近似する新しいグラフニューラルネットワークフレームワークを提案する。 教師なしの環境では、グラデーションのみの自己組織化機構を採用し、地絡距離を使わずに最適化できる。 さらに、アーキテクチャの中核となるコンポーネントは、コンテキスト対応編集コストの柔軟かつ解釈可能な学習を可能にする一般化付加モデルの統合です。 実験の結果,提案手法は最先端参照手法と類似した結果が得られるが,適応性と解釈性は著しく向上することがわかった。 すなわち、学習コスト関数は複雑なグラフ構造に関する洞察を与え、特に分子解析や構造パターン発見のような領域で有用である。

関連論文リスト

• 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)
• Flexible Graph Similarity Computation With A Proactive Optimization Strategy [22.212014309562427]
  Graph Edit Distance (GED)は、グラフ類似性の原則的かつ柔軟な尺度を提供する。 GEDは、あるグラフを別のグラフに変換するのに必要な最小コストを、カスタマイズ可能な編集操作コストで定量化する。 既存の方法は、様々な運用コストに対応するのに苦労する。 フレキシブルGED近似のための新しい学習ベースアプローチであるGENを提案する。
  論文  参考訳（メタデータ） (2025-04-09T02:16:46Z)
• Community-Centric Graph Unlearning [10.906555492206959]
  我々は、新しいグラフ構造マッピング・アンラーニング・パラダイム(GSMU)と、それに基づく新しい手法CGE(Community-centric Graph Eraser)を提案する。 CGEは、コミュニティのサブグラフをノードにマッピングすることで、少ないマップ付きグラフ内でノードレベルの未学習操作の再構築を可能にする。
  論文  参考訳（メタデータ） (2024-08-19T05:37:35Z)
• EUGENE: Explainable Unsupervised Approximation of Graph Edit Distance with Generalized Edit Costs [20.3519249026886]
  グラフ編集距離(GED)は、グラフ間距離を測定するために好ましい。 GED計算はNPハードネスによって妨げられる。 教師なしの手法は、しばしば正確な近似を提供する際の課題に直面する。
  論文  参考訳（メタデータ） (2024-02-08T18:23:05Z)
• GraphGLOW: Universal and Generalizable Structure Learning for Graph Neural Networks [72.01829954658889]
  本稿では,この新たな問題設定の数学的定義を紹介する。 一つのグラフ共有構造学習者と複数のグラフ固有GNNを協調する一般的なフレームワークを考案する。 十分に訓練された構造学習者は、微調整なしで、目に見えない対象グラフの適応的な構造を直接生成することができる。
  論文  参考訳（メタデータ） (2023-06-20T03:33:22Z)
• EPIC: Graph Augmentation with Edit Path Interpolation via Learnable Cost [12.191001329584502]
  本稿では,グラフデータセットを新たに拡張するEPIC (Edit Path Interpolation via learnable Cost)を提案する。 不規則な領域にある2つのグラフの間を補間するために、EPICは2つのグラフ間の変換プロセスを表す編集パスを構築する。 我々のアプローチは多くのタスクにおいて既存の拡張テクニックよりも優れています。
  論文  参考訳（メタデータ） (2023-06-02T07:19:07Z)
• DEGREE: Decomposition Based Explanation For Graph Neural Networks [55.38873296761104]
  我々は,GNN予測に対する忠実な説明を提供するためにDGREEを提案する。 GNNの情報生成と集約機構を分解することにより、DECREEは入力グラフの特定のコンポーネントのコントリビューションを最終的な予測に追跡することができる。 また,従来の手法で見過ごされるグラフノード間の複雑な相互作用を明らかにするために,サブグラフレベルの解釈アルゴリズムを設計する。
  論文  参考訳（メタデータ） (2023-05-22T10:29:52Z)
• Comprehensive Graph Gradual Pruning for Sparse Training in Graph Neural Networks [52.566735716983956]
  本稿では,CGPと呼ばれるグラフの段階的プルーニングフレームワークを動的にGNNに提案する。 LTHに基づく手法とは異なり、提案手法では再学習を必要とせず、計算コストを大幅に削減する。 提案手法は,既存の手法の精度を一致させたり,あるいは超えたりしながら,トレーニングと推論の効率を大幅に向上させる。
  論文  参考訳（メタデータ） (2022-07-18T14:23:31Z)
• Combinatorial Learning of Graph Edit Distance via Dynamic Embedding [108.49014907941891]
  本稿では,従来の検索手法による編集経路の解釈可能性を組み合わせたハイブリッド手法を提案する。 動的プログラミングにインスパイアされたノードレベルの埋め込みは、動的再利用方式で指定され、サブ最適分岐がプルーニングされることが推奨される。 異なるグラフデータセットを用いた実験結果から,A* の探索処理は精度を犠牲にすることなく極めて容易であることが示唆された。
  論文  参考訳（メタデータ） (2020-11-30T17:41:02Z)
• Tensor Graph Convolutional Networks for Multi-relational and Robust Learning [74.05478502080658]
  本稿では,テンソルで表されるグラフの集合に関連するデータから,スケーラブルな半教師付き学習(SSL)を実現するためのテンソルグラフ畳み込みネットワーク(TGCN)を提案する。 提案アーキテクチャは、標準的なGCNと比較して大幅に性能が向上し、最先端の敵攻撃に対処し、タンパク質間相互作用ネットワーク上でのSSL性能が著しく向上する。
  論文  参考訳（メタデータ） (2020-03-15T02:33:21Z)
• Graph Representation Learning via Graphical Mutual Information Maximization [86.32278001019854]
  本稿では,入力グラフとハイレベルな隠蔽表現との相関を測る新しい概念であるGMIを提案する。 我々は,グラフニューラルエンコーダの入力と出力の間でGMIを最大化することで訓練された教師なし学習モデルを開発する。
  論文  参考訳（メタデータ） (2020-02-04T08:33:49Z)

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

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