論文の概要: EUGENE: Explainable Unsupervised Approximation of Graph Edit Distance with Generalized Edit Costs

• arxiv url: http://arxiv.org/abs/2402.05885v2
• Date: Sun, 02 Feb 2025 05:10:11 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-02-04 16:04:32.520437
• Title: EUGENE: Explainable Unsupervised Approximation of Graph Edit Distance with Generalized Edit Costs
• Title（参考訳）: EUGENE: 一般的な編集コストによるグラフ編集距離の説明不能な近似
• Authors: Aditya Bommakanti, Harshith Reddy Vonteri, Sayan Ranu, Panagiotis Karras,
• Abstract要約: グラフ編集距離(GED)は、グラフ間距離を測定するために好ましい。 GED計算はNPハードネスによって妨げられる。 教師なしの手法は、しばしば正確な近似を提供する際の課題に直面する。
• 参考スコア（独自算出の注目度）: 20.3519249026886
• License:
• Abstract: The need to identify graphs with small structural distances from a query arises in various domains such as biology, chemistry, recommender systems, and social network analysis. Among several methods for measuring inter-graph distance, Graph Edit Distance (GED) is preferred for its comprehensibility, though its computation is hindered by NP-hardness. Unsupervised methods often face challenges in providing accurate approximations. State-of-the-art GED approximations predominantly utilize neural methods, which, however, have several limitations: (i) lack an explanatory edit path corresponding to the approximated GED; (ii) require the NP-hard generation of ground-truth GEDs for training; and (iii) necessitate separate training on each dataset. In this paper, we propose EUGENE, an efficient algebraic unsupervised method that approximates GED while providing edit paths corresponding to the approximated cost. Extensive experimental evaluation demonstrates that EUGENE achieves state-of-the-art performance in GED estimation and exhibits superior scalability across diverse datasets and generalized cost settings.
• Abstract（参考訳）: クエリから小さな構造的な距離を持つグラフを識別する必要性は、生物学、化学、レコメンダシステム、ソーシャルネットワーク分析など、さまざまな領域で生じる。 グラフ間距離を測定するいくつかの方法の中で、グラフ編集距離(GED)はNP硬さによって計算が妨げられるが、その理解性には好まれる。 教師なしの手法は、しばしば正確な近似を提供する際の課題に直面する。 最先端のGED近似は、主にニューラルメソッドを利用するが、いくつかの制限がある。 i) 近似されたGEDに対応する説明的編集パスがないこと。 (二)トレーニングには、NP硬化型GEDの育成が必要である。 (iii)データセットごとに個別のトレーニングが必要である。 本稿では,GEDを近似した効率的な代数的教師なし手法であるEUGENEを提案する。 大規模な実験的評価は、EUGENEがGED推定における最先端のパフォーマンスを達成し、多様なデータセットにまたがる優れたスケーラビリティと一般的なコスト設定を示すことを示している。

関連論文リスト

• Generative Risk Minimization for Out-of-Distribution Generalization on Graphs [71.48583448654522]
  本稿では,抽出ではなく,各入力グラフの不変部分グラフを生成するために,GRM (Generative Risk Minimization) という革新的なフレームワークを提案する。 我々は,ノードレベルのOOD一般化とグラフレベルのOOD一般化のために,さまざまな実世界のグラフデータセットに対して広範な実験を行う。
  論文  参考訳（メタデータ） (2025-02-11T21:24:13Z)
• 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)
• Graph Edit Distance with General Costs Using Neural Set Divergence [40.79963604310166]
  グラフ編集距離(GED)は、2つのグラフ間の(dis-)類似性を測定する。 本稿では,編集作業に要する一般的なコストで動作可能なニューラルGED推定器である GraphEDX を提案する。 さまざまな編集コスト設定の下で、いくつかのデータセットの実験では、 GraphEDXが最先端の計算とメソッドを一貫して上回っていることが示されている。
  論文  参考訳（メタデータ） (2024-09-26T09:51:29Z)
• Exploring Task Unification in Graph Representation Learning via Generative Approach [12.983429541410617]
  グラフは現実世界のシナリオにおいてユビキタスであり、ノードレベル、エッジレベル、グラフレベルのタスクから移行学習まで、さまざまなタスクを含んでいる。 最近の取り組みは、複数のグラフタスクをまたいで一般化できる統一されたフレームワークを設計することを目的としている。 これらのうち、グラフオートエンコーダ(GAE)は、様々なグラフタスクに効果的に対処する可能性を示している。 本稿では,これらの課題にシームレスに対処可能な,対向マスク型オートエンコーダであるGA2Eを提案する。
  論文  参考訳（メタデータ） (2024-03-21T12:14:02Z)
• 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)
• DEGREE: Decomposition Based Explanation For Graph Neural Networks [55.38873296761104]
  我々は,GNN予測に対する忠実な説明を提供するためにDGREEを提案する。 GNNの情報生成と集約機構を分解することにより、DECREEは入力グラフの特定のコンポーネントのコントリビューションを最終的な予測に追跡することができる。 また,従来の手法で見過ごされるグラフノード間の複雑な相互作用を明らかにするために,サブグラフレベルの解釈アルゴリズムを設計する。
  論文  参考訳（メタデータ） (2023-05-22T10:29:52Z)
• From Unsupervised to Few-shot Graph Anomaly Detection: A Multi-scale Contrastive Learning Approach [26.973056364587766]
  グラフデータからの異常検出は、ソーシャルネットワーク、金融、eコマースなど、多くのアプリケーションにおいて重要なデータマイニングタスクである。 マルチスケールcONtrastive lEarning(略してANEMONE)を用いた新しいフレームワーク, graph Anomaly dEtection フレームワークを提案する。 グラフニューラルネットワークをバックボーンとして、複数のグラフスケール(ビュー)から情報をエンコードすることで、グラフ内のノードのより良い表現を学習する。
  論文  参考訳（メタデータ） (2022-02-11T09:45:11Z)
• 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)
• Graph Representation Learning via Graphical Mutual Information Maximization [86.32278001019854]
  本稿では,入力グラフとハイレベルな隠蔽表現との相関を測る新しい概念であるGMIを提案する。 我々は,グラフニューラルエンコーダの入力と出力の間でGMIを最大化することで訓練された教師なし学習モデルを開発する。
  論文  参考訳（メタデータ） (2020-02-04T08:33:49Z)
• Unsupervised Domain Adaptation in Person re-ID via k-Reciprocal Clustering and Large-Scale Heterogeneous Environment Synthesis [76.46004354572956]
  個人再識別のための教師なし領域適応手法を提案する。 実験結果から,ktCUDA法とSHRED法は,再同定性能において,+5.7 mAPの平均的改善を実現することがわかった。
  論文  参考訳（メタデータ） (2020-01-14T17:43:52Z)

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

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