論文の概要: EUGENE: Explainable Unsupervised Approximation of Graph Edit Distance
- arxiv url: http://arxiv.org/abs/2402.05885v1
- Date: Thu, 8 Feb 2024 18:23:05 GMT
- ステータス: 処理完了
- システム内更新日: 2024-02-09 13:39:01.595658
- Title: EUGENE: Explainable Unsupervised Approximation of Graph Edit Distance
- Title(参考訳): EUGENE: グラフ編集距離の説明不能な近似
- Authors: Aditya Bommakanti, Harshith Reddy Vonteri, Sayan Ranu, Panagiotis
Karras
- Abstract要約: グラフ編集距離(GED)は、その理解性には好まれるが、計算のNP硬度によって妨げられる。
本稿では,GED を近似した効率的な代数的非スーパービジュアライズ手法 EUGENE を提案する。
EUGENEは、すべてのベンチマークデータセットの中で、最も正確な方法の1つだ。
- 参考スコア(独自算出の注目度): 22.23301588387103
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: The need to identify graphs having small structural distance from a query
arises in biology, chemistry, recommender systems, and social network analysis.
Among several methods to measure inter graph distance, Graph Edit Distance
(GED) is preferred for its comprehensibility, yet hindered by the NP-hardness
of its computation. State-of-the-art GED approximations predominantly employ
neural methods, which, however, (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 an efficient algebraic unsuper vised method, EUGENE,
that approximates GED and yields edit paths corresponding to the approx imated
cost, while eliminating the need for ground truth generation and data-specific
training. Extensive experimental evaluation demonstrates that the
aforementioned benefits of EUGENE do not come at the cost of efficacy.
Specifically, EUGENE consistently ranks among the most accurate methods across
all of the benchmark datasets and outperforms majority of the neural
approaches.
- Abstract(参考訳): クエリから小さな構造的距離を持つグラフを識別する必要性は、生物学、化学、推薦システム、およびソーシャルネットワーク分析において生じる。
グラフ間距離を測定するいくつかの方法の中で、グラフ編集距離(GED)はその理解性に好まれるが、計算のNP硬度によって妨げられる。
最先端のGED近似では、主にニューラルな手法が採用されている。
i) 近似されたGEDに対応する説明的編集パスがないこと。
(二)トレーニングには、NP硬化型GEDの育成が必要である。
(iii)データセットごとに個別のトレーニングが必要となる。
本稿では,gedを近似し,近似したコストに対応する編集パスを生成する効率的な代数的非スーパーved手法であるeugeneを提案する。
大規模な実験的評価は、前述のEUGENEの利点が効果の犠牲にならないことを示している。
具体的には、EUGENEは、すべてのベンチマークデータセットの中で最も正確な方法の1つであり、ほとんどのニューラルネットワークアプローチより優れている。
関連論文リスト
- 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。