論文の概要: Flexible Graph Similarity Computation With A Proactive Optimization Strategy
- arxiv url: http://arxiv.org/abs/2504.06533v2
- Date: Thu, 15 May 2025 08:42:50 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-05-16 14:06:36.352219
- Title: Flexible Graph Similarity Computation With A Proactive Optimization Strategy
- Title（参考訳）: プロアクティブ最適化戦略を用いたフレキシブルグラフ類似性計算
- Authors: Zhouyang Liu, Ning Liu, Yixin Chen, Jiezhong He, Dongsheng Li,
- Abstract要約: Graph Edit Distance (GED)は、グラフ類似性の原則的かつ柔軟な尺度を提供する。
GEDは、あるグラフを別のグラフに変換するのに必要な最小コストを、カスタマイズ可能な編集操作コストで定量化する。
既存の方法は、様々な運用コストに対応するのに苦労する。
フレキシブルGED近似のための新しい学習ベースアプローチであるGENを提案する。
- 参考スコア（独自算出の注目度）: 22.212014309562427
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Graph Edit Distance (GED) offers a principled and flexible measure of graph similarity, as it quantifies the minimum cost needed to transform one graph into another with customizable edit operation costs. Despite recent learning-based efforts to approximate GED via vector space representations, existing methods struggle with adapting to varying operation costs. Furthermore, they suffer from inefficient, reactive mapping refinements due to reliance on isolated node-level distance as guidance. To address these issues, we propose GEN, a novel learning-based approach for flexible GED approximation. GEN addresses the varying costs adaptation by integrating operation costs prior to match establishment, enabling mappings to dynamically adapt to cost variations. Furthermore, GEN introduces a proactive guidance optimization strategy that captures graph-level dependencies between matches, allowing informed matching decisions in a single step without costly iterative refinements. Extensive evaluations on real-world and synthetic datasets demonstrate that GEN achieves up to 37.8% reduction in GED approximation error and 72.7% reduction in inference time compared with state-of-the-art methods, while consistently maintaining robustness under diverse cost settings and graph sizes.
- Abstract（参考訳）: グラフ編集距離(GED)は、あるグラフを別のグラフに変換するのに必要な最小コストを、カスタマイズ可能な編集操作コストで定量化するため、グラフ類似性の原理的で柔軟な尺度を提供する。
最近の学習に基づくベクトル空間表現によるGED近似の試みにもかかわらず、既存の手法は様々な演算コストに適応するのに苦労している。
さらに、ガイドとして孤立ノードレベル距離に依存するため、非効率でリアクティブなマッピング改善に悩まされる。
これらの問題に対処するために、フレキシブルGED近似のための新しい学習ベースアプローチであるGENを提案する。
GENは、設定が整う前に運用コストを統合することで、様々なコスト適応に対処し、マッピングがコスト変動に動的に適応できるようにする。
さらに、GENは、マッチ間のグラフレベルの依存関係をキャプチャし、コストのかかる反復的な改善を伴わずに、単一のステップで情報的なマッチング決定を可能にする、積極的なガイダンス最適化戦略を導入している。
実世界のデータセットと合成データセットの大規模な評価により、genはGED近似誤差を最大37.8%、推論時間を72.7%削減し、さまざまなコスト設定やグラフサイズで頑健性を維持している。
関連論文リスト
- Learning Partial Graph Matching via Optimal Partial Transport [2.4378101048225735]
最適部分移動にインスパイアされた部分グラフマッチングのための新しいフレームワークを提案する。
提案手法は, 偏りを取り入れつつ部分的代入を可能にする目的を定式化したものである。
我々の手法は,3次最悪のケースタイムの複雑さの中で,効率的かつ正確な解が得られる。
論文 参考訳（メタデータ） (2024-10-22T05:56:57Z) - 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) - EUGENE: Explainable Unsupervised Approximation of Graph Edit Distance with Generalized Edit Costs [20.3519249026886]
グラフ編集距離(GED)は、グラフ間距離を測定するために好ましい。
GED計算はNPハードネスによって妨げられる。
教師なしの手法は、しばしば正確な近似を提供する際の課題に直面する。
論文 参考訳（メタデータ） (2024-02-08T18:23:05Z) - PREM: A Simple Yet Effective Approach for Node-Level Graph Anomaly
Detection [65.24854366973794]
ノードレベルのグラフ異常検出(GAD)は、医学、ソーシャルネットワーク、eコマースなどの分野におけるグラフ構造化データから異常ノードを特定する上で重要な役割を果たす。
本稿では,GADの効率を向上させるために,PREM (preprocessing and Matching) という簡単な手法を提案する。
我々のアプローチは、強力な異常検出機能を維持しながら、GADを合理化し、時間とメモリ消費を削減します。
論文 参考訳（メタデータ） (2023-10-18T02:59:57Z) - GIF: A General Graph Unlearning Strategy via Influence Function [63.52038638220563]
Graph Influence Function (GIF)は、削除されたデータにおける$epsilon$-massの摂動に応答してパラメータの変化を効率的に正確に推定できる、モデルに依存しない未学習の手法である。
我々は,4つの代表的GNNモデルと3つのベンチマークデータセットについて広範な実験を行い,未学習の有効性,モデルの有用性,未学習効率の観点からGIFの優位性を正当化する。
論文 参考訳（メタデータ） (2023-04-06T03:02:54Z) - Localized Contrastive Learning on Graphs [110.54606263711385]
局所グラフコントラスト学習(Local-GCL)という,シンプルだが効果的なコントラストモデルを導入する。
その単純さにもかかわらず、Local-GCLは、様々なスケールと特性を持つグラフ上の自己教師付きノード表現学習タスクにおいて、非常に競争力のある性能を達成する。
論文 参考訳（メタデータ） (2022-12-08T23:36:00Z) - Comprehensive Graph Gradual Pruning for Sparse Training in Graph Neural
Networks [52.566735716983956]
本稿では,CGPと呼ばれるグラフの段階的プルーニングフレームワークを動的にGNNに提案する。
LTHに基づく手法とは異なり、提案手法では再学習を必要とせず、計算コストを大幅に削減する。
提案手法は,既存の手法の精度を一致させたり,あるいは超えたりしながら,トレーニングと推論の効率を大幅に向上させる。
論文 参考訳（メタデータ） (2022-07-18T14:23:31Z) - Optimal Propagation for Graph Neural Networks [51.08426265813481]
最適グラフ構造を学習するための二段階最適化手法を提案する。
また、時間的複雑さをさらに軽減するために、低ランク近似モデルについても検討する。
論文 参考訳（メタデータ） (2022-05-06T03:37:00Z) - Efficient Dynamic Graph Representation Learning at Scale [66.62859857734104]
本稿では,学習損失による時間依存性を選択的に表現し,計算の並列性を改善するための効率的な動的グラフ lEarning (EDGE) を提案する。
EDGEは、数百万のノードと数億の時間的イベントを持つ動的グラフにスケールでき、新しい最先端(SOTA)パフォーマンスを実現することができる。
論文 参考訳（メタデータ） (2021-12-14T22:24:53Z) - A Generative Graph Method to Solve the Travelling Salesman Problem [1.552282932199974]
我々は,旅行セールスマン問題(TSP)を概ね解決するために,生成的アプローチである新しいグラフ学習ネットワーク(GLN)を提案する。
GLNモデルは、トレーニングデータセットとしてTSPインスタンスのパターンを直接学習し、グラフプロパティをエンコードし、異なるノードの埋め込みをマージして、最適なツアーを出力する。
論文 参考訳（メタデータ） (2020-07-09T17:23:55Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。