論文の概要: Graph Edit Distance with General Costs Using Neural Set Divergence

• arxiv url: http://arxiv.org/abs/2409.17687v1
• Date: Thu, 26 Sep 2024 09:51:29 GMT
• ステータス: 処理完了
• システム内更新日: 2024-09-28 20:46:02.595341
• Title: Graph Edit Distance with General Costs Using Neural Set Divergence
• Title（参考訳）: ニューラル・セット・ディバージェンスを用いた一般費用によるグラフ編集距離
• Authors: Eeshaan Jain, Indradyumna Roy, Saswat Meher, Soumen Chakrabarti, Abir De
• Abstract要約: グラフ編集距離(GED)は、2つのグラフ間の(dis-)類似性を測定する。 本稿では,編集作業に要する一般的なコストで動作可能なニューラルGED推定器である GraphEDX を提案する。 さまざまな編集コスト設定の下で、いくつかのデータセットの実験では、 GraphEDXが最先端の計算とメソッドを一貫して上回っていることが示されている。
• 参考スコア（独自算出の注目度）: 43.77172445814554
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Graph Edit Distance (GED) measures the (dis-)similarity between two given graphs, in terms of the minimum-cost edit sequence that transforms one graph to the other. However, the exact computation of GED is NP-Hard, which has recently motivated the design of neural methods for GED estimation. However, they do not explicitly account for edit operations with different costs. In response, we propose GRAPHEDX, a neural GED estimator that can work with general costs specified for the four edit operations, viz., edge deletion, edge addition, node deletion and node addition. We first present GED as a quadratic assignment problem (QAP) that incorporates these four costs. Then, we represent each graph as a set of node and edge embeddings and use them to design a family of neural set divergence surrogates. We replace the QAP terms corresponding to each operation with their surrogates. Computing such neural set divergence require aligning nodes and edges of the two graphs. We learn these alignments using a Gumbel-Sinkhorn permutation generator, additionally ensuring that the node and edge alignments are consistent with each other. Moreover, these alignments are cognizant of both the presence and absence of edges between node-pairs. Experiments on several datasets, under a variety of edit cost settings, show that GRAPHEDX consistently outperforms state-of-the-art methods and heuristics in terms of prediction error.
• Abstract（参考訳）: グラフ編集距離(GED)は、2つのグラフ間の(dis-)類似性を測定する。 しかし、GEDの正確な計算はNP-Hardであり、近年、GED推定のためのニューラルメソッドの設計を動機付けている。 しかし、彼らは異なるコストで編集操作を明示的に説明していない。 そこで我々は,4つの編集操作(viz., edge deletion, edge addition, node deletion, node addition)で指定された一般的なコストで動作可能な,ニューラルGED推定器である GraphEDXを提案する。 まず、これらの4つのコストを組み込んだ2次代入問題(QAP)としてGEDを提示する。 次に、各グラフをノードとエッジの埋め込みの集合として表現し、それらを用いてニューラルネットワークの発散サロゲートの族を設計する。 各操作に対応するQAP用語をそれぞれのサロゲートに置き換える。 そのようなニューラルネットワークの発散を計算するには、2つのグラフのノードとエッジを整列する必要がある。 我々はGumbel-Sinkhorn置換生成器を用いてこれらのアライメントを学習し、ノードとエッジのアライメントが互いに一致していることを保証する。 さらに、これらのアライメントは、ノードペア間のエッジの存在と欠如の両方を認識している。 さまざまな編集コスト設定の下で、いくつかのデータセットの実験では、 GraphEDXが予測エラーの点において、最先端のメソッドやヒューリスティックを一貫して上回っていることが示されている。

関連論文リスト

• Scalable Graph Compressed Convolutions [68.85227170390864]
  ユークリッド畳み込みのための入力グラフのキャリブレーションに置換を適用する微分可能手法を提案する。 グラフキャリブレーションに基づいて,階層型グラフ表現学習のための圧縮畳み込みネットワーク(CoCN)を提案する。
  論文  参考訳（メタデータ） (2024-07-26T03:14:13Z)
• 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)
• A Quasi-Wasserstein Loss for Learning Graph Neural Networks [32.11372485060082]
  グラフ上で定義された最適輸送の助けを借りて、新しい準ワッサーシュタイン(QW)損失を提案する。 提案したQW損失は,様々なグラフニューラルネットワーク(GNN)に適用され,ノードレベルの分類や回帰タスクの性能向上に寄与することを示す。
  論文  参考訳（メタデータ） (2023-10-18T07:39:05Z)
• NodeFormer: A Scalable Graph Structure Learning Transformer for Node Classification [70.51126383984555]
  本稿では,任意のノード間のノード信号を効率的に伝搬する全ペアメッセージパッシング方式を提案する。 効率的な計算は、カーナライズされたGumbel-Softmax演算子によって実現される。 グラフ上のノード分類を含む様々なタスクにおいて,本手法の有望な有効性を示す実験を行った。
  論文  参考訳（メタデータ） (2023-06-14T09:21:15Z)
• Graph Transformer GANs for Graph-Constrained House Generation [223.739067413952]
  本稿では,グラフノード関係を効果的に学習するために,GTGAN(Graph Transformer Generative Adversarial Network)を提案する。 GTGANは、グラフ制約のある住宅生成タスクにおいて、エンドツーエンドで効率的なグラフノード関係を学習する。
  論文  参考訳（メタデータ） (2023-03-14T20:35:45Z)
• Graph Neural Network Bandits [89.31889875864599]
  グラフ構造データ上で定義された報酬関数を用いた帯域最適化問題を考察する。 この設定の主な課題は、大きなドメインへのスケーリングと、多くのノードを持つグラフへのスケーリングである。 グラフニューラルネットワーク(GNN)を用いて報酬関数を推定できることを示す。
  論文  参考訳（メタデータ） (2022-07-13T18:12:36Z)
• SoftEdge: Regularizing Graph Classification with Random Soft Edges [18.165965620873745]
  グラフデータ拡張はグラフニューラルネットワーク(GNN)の正規化において重要な役割を果たす 単純なエッジとノード操作は、同じ構造を持つグラフや、GNNをメッセージパッシングするための区別できない構造を生成することができる。 我々は,任意のグラフのエッジの一部にランダムな重みを割り当てて,そのグラフ上の動的近傍を構築するSoftEdgeを提案する。
  論文  参考訳（メタデータ） (2022-04-21T20:12:36Z)
• Variational Graph Normalized Auto-Encoders [4.416484585765027]
  グラフオートエンコーダ(GAE)と変分グラフオートエンコーダ(VGAE)は,次数0のノードが関与している場合,リンク予測においてうまく機能しないことを示す。 我々は,GAE/VGAEが,コンテンツの特徴に関係なく,孤立ノードの埋め込みをゼロに近いものにすることを発見した。 本稿では、$L$正規化を利用して孤立ノードに対するより良い埋め込みを導出する新しい変分グラフ正規化オートエンコーダ(VGNAE)を提案する。
  論文  参考訳（メタデータ） (2021-08-18T08:56:04Z)
• Line Graph Neural Networks for Link Prediction [71.00689542259052]
  実世界の多くのアプリケーションにおいて古典的なグラフ解析問題であるグラフリンク予測タスクについて検討する。 このフォーマリズムでは、リンク予測問題をグラフ分類タスクに変換する。 本稿では,線グラフをグラフ理論に用いて,根本的に異なる新しい経路を求めることを提案する。 特に、線グラフの各ノードは、元のグラフのユニークなエッジに対応するため、元のグラフのリンク予測問題は、グラフ分類タスクではなく、対応する線グラフのノード分類問題として等価に解決できる。
  論文  参考訳（メタデータ） (2020-10-20T05:54:31Z)

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

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