論文の概要: 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 15:57:52.973877
• 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: http://creativecommons.org/licenses/by/4.0/
• 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推定における最先端のパフォーマンスを達成し、多様なデータセットにまたがる優れたスケーラビリティと一般的なコスト設定を示すことを示している。

関連論文リスト

• Flexible Graph Similarity Computation With A Proactive Optimization Strategy [22.212014309562427]
  グラフ編集距離(GED)は、グラフ検索において重要な類似度尺度である。 最近の学習に基づくアプローチは、ベクトル空間における表現間の距離とGEDを近似する。 フレキシブルGED計算のための新しい学習ベースアプローチであるグラフ編集ネットワーク(GEN)を提案する。
  論文  参考訳（メタデータ） (2025-04-09T02:16:46Z)
• G-OSR: A Comprehensive Benchmark for Graph Open-Set Recognition [54.45837774534411]
  ノードレベルとグラフレベルの両方でグラフオープンセット認識(GOSR)手法を評価するベンチマークである textbfG-OSR を導入する。 結果は、現在のGOSR手法の一般化可能性と限界に関する重要な洞察を与える。
  論文  参考訳（メタデータ） (2025-03-01T13:02:47Z)
• 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)
• Erase then Rectify: A Training-Free Parameter Editing Approach for Cost-Effective Graph Unlearning [17.85404473268992]
  グラフアンラーニングは、訓練されたグラフニューラルネットワーク(GNN)からノード、エッジ、属性の影響を排除することを目的としている。 既存のグラフアンラーニング技術は、しばしば残りのデータに対する追加のトレーニングを必要とし、かなりの計算コストをもたらす。 本稿では,2段階の学習自由アプローチであるETR(Erase then Rectify)を提案する。
  論文  参考訳（メタデータ） (2024-09-25T07:20:59Z)
• Efficient Graph Similarity Computation with Alignment Regularization [7.143879014059894]
  グラフ類似性計算(GSC)は、グラフニューラルネットワーク(GNN)を用いた学習に基づく予測タスクである。 適応正規化(AReg)と呼ばれる,シンプルながら強力な正規化技術によって,高品質な学習が達成可能であることを示す。 推論段階では、GNNエンコーダによって学習されたグラフレベル表現は、ARegを再度使用せずに直接類似度スコアを計算するために使用される。
  論文  参考訳（メタデータ） (2024-06-21T07:37:28Z)
• 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)
• Distributed Learning over Networks with Graph-Attention-Based Personalization [49.90052709285814]
  分散ディープラーニングのためのグラフベースパーソナライズアルゴリズム(GATTA)を提案する。 特に、各エージェントのパーソナライズされたモデルは、グローバルな部分とノード固有の部分で構成される。 グラフ内の各エージェントを1つのノードとして扱うことにより、ノード固有のパラメータを特徴として扱うことにより、グラフアテンション機構の利点を継承することができる。
  論文  参考訳（メタデータ） (2023-05-22T13:48:30Z)
• DEGREE: Decomposition Based Explanation For Graph Neural Networks [55.38873296761104]
  我々は,GNN予測に対する忠実な説明を提供するためにDGREEを提案する。 GNNの情報生成と集約機構を分解することにより、DECREEは入力グラフの特定のコンポーネントのコントリビューションを最終的な予測に追跡することができる。 また,従来の手法で見過ごされるグラフノード間の複雑な相互作用を明らかにするために,サブグラフレベルの解釈アルゴリズムを設計する。
  論文  参考訳（メタデータ） (2023-05-22T10:29:52Z)
• Localized Contrastive Learning on Graphs [110.54606263711385]
  局所グラフコントラスト学習(Local-GCL)という,シンプルだが効果的なコントラストモデルを導入する。 その単純さにもかかわらず、Local-GCLは、様々なスケールと特性を持つグラフ上の自己教師付きノード表現学習タスクにおいて、非常に競争力のある性能を達成する。
  論文  参考訳（メタデータ） (2022-12-08T23:36:00Z)
• 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)
• GREED: A Neural Framework for Learning Graph Distance Functions [8.323580169763726]
  我々はGREEDと呼ばれる新しいシアムグラフニューラルネットワークを設計し、GEDとSEDをプロパティ保存方式で学習する。 最大700万のエッジを含む10のグラフデータセットを通じて、GREEDは最先端技術よりも正確であるだけでなく、最大3桁高速であることを示す。
  論文  参考訳（メタデータ） (2021-12-24T21:46:40Z)
• Tackling Oversmoothing of GNNs with Contrastive Learning [35.88575306925201]
  グラフニューラルネットワーク(GNN)は、グラフデータと表現学習能力の包括的な関係を統合する。 オーバースムーシングはノードの最終的な表現を識別不能にし、ノード分類とリンク予測性能を劣化させる。 本稿では,TGCL(Topology-Guided Graph Contrastive Layer)を提案する。
  論文  参考訳（メタデータ） (2021-10-26T15:56:16Z)
• A Robust and Generalized Framework for Adversarial Graph Embedding [73.37228022428663]
  本稿では,AGE という逆グラフ埋め込みのための頑健なフレームワークを提案する。 AGEは、暗黙の分布から強化された負のサンプルとして偽の隣接ノードを生成する。 本フレームワークでは,3種類のグラフデータを扱う3つのモデルを提案する。
  論文  参考訳（メタデータ） (2021-05-22T07:05:48Z)
• Uniting Heterogeneity, Inductiveness, and Efficiency for Graph Representation Learning [68.97378785686723]
  グラフニューラルネットワーク(GNN)は,グラフ上のノード表現学習の性能を大幅に向上させた。 GNNの過半数クラスは均質グラフのためにのみ設計されており、より有益な異種グラフに劣る適応性をもたらす。 本稿では,低次ノードと高次ノードの両方のエッジに付随するヘテロジニアスなノード特徴をパッケージ化する,新しい帰納的メタパスフリーメッセージパッシング方式を提案する。
  論文  参考訳（メタデータ） (2021-04-04T23:31:39Z)
• 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)

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

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