論文の概要: Flexible Graph Similarity Computation With A Proactive Optimization Strategy

• arxiv url: http://arxiv.org/abs/2504.06533v1
• Date: Wed, 09 Apr 2025 02:16:46 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-04-10 13:06:56.662809
• Title: Flexible Graph Similarity Computation With A Proactive Optimization Strategy
• Title（参考訳）: プロアクティブ最適化戦略を用いたフレキシブルグラフ類似性計算
• Authors: Zhouyang Liu, Ning Liu, Yixin Chen, Jiezhong He, Dongsheng Li,
• Abstract要約: グラフ編集距離(GED)は、グラフ検索において重要な類似度尺度である。 最近の学習に基づくアプローチは、ベクトル空間における表現間の距離とGEDを近似する。 フレキシブルGED計算のための新しい学習ベースアプローチであるグラフ編集ネットワーク(GEN)を提案する。
• 参考スコア（独自算出の注目度）: 22.212014309562427
• License:
• Abstract: Graph Edit Distance (GED) is an important similarity measure in graph retrieval, which quantifies the minimum cost of transforming one graph into another through edit operations, and offers flexibility by allowing customizable operation costs. Recent learning-based approaches approximate GEDs with the distances between representations in vector spaces. However, these methods often struggle with varying operation costs due to neglecting the impact of these costs on determining optimal graph mappings. Furthermore, they rely on isolated node distances as guidance, necessitating inefficient reactive refinements of mappings. To address these issues, we propose Graph Edit Network (GEN), a novel learning-based approach for flexible GED computation. By identifying the limitations of existing methods in capturing flexibility of GED, we introduce a principled yet simple solution that incorporates the operation costs before establishing mappings. To improve matching efficiency, we propose a strategy that proactively optimizes guidance from a graph perspective. This strategy initializes guidance as each node's alignment difficulty and captures the interdependencies between matches within and across graphs through a difficulty propagation mechanism, enabling more informed decisions. As a result, GEN selects optimal matches in a single step, minimizing the need for costly refinements. Results on real-world and synthetic datasets demonstrate the effectiveness, time efficiency, and adaptability of GEN, achieving up to 37.8\% error reduction and 72.7\% inference time reduction compared with state-of-the-art models, while performing robustly under varying cost settings and graph sizes.
• Abstract（参考訳）: グラフ編集距離 (Graph Edit Distance, GED) は、グラフ検索において重要な類似度尺度であり、編集操作によってグラフを別のグラフに変換する最小コストを定量化し、カスタマイズ可能な操作コストを許容することによって柔軟性を提供する。 最近の学習に基づくアプローチは、ベクトル空間における表現間の距離とGEDを近似する。 しかし、これらの手法は、最適なグラフマッピングを決定する上でのこれらのコストの影響を無視するため、様々な作業コストに悩まされることが多い。 さらに、ガイドとして孤立ノード距離を頼りにしており、マッピングの非効率な反応性改善を必要としている。 これらの問題に対処するため,我々は,フレキシブルGED計算のための新しい学習ベースアプローチであるGraph Edit Network (GEN)を提案する。 GEDの柔軟性を捉えるための既存の手法の限界を識別することにより、マッピングの確立前に運用コストを組み込んだ、原則的かつシンプルなソリューションを導入する。 マッチング効率を向上させるため,グラフの観点からガイダンスを積極的に最適化する手法を提案する。 この戦略は、各ノードのアライメントの困難さとしてガイダンスを初期化し、困難伝播機構を通じてグラフ内およびグラフ間のマッチ間の相互依存性をキャプチャし、より情報的な決定を可能にする。 その結果、GENは1ステップで最適なマッチングを選択し、コストのかかる改善の必要性を最小限に抑える。 実世界のデータセットと合成データセットの結果は、Genの有効性、時間効率、適応性を示し、最新のモデルと比較して最大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)

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

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