論文の概要: Graph Matching Relaxations and Amortization for Supervised Graph Prediction

• arxiv url: http://arxiv.org/abs/2609.15437v1
• Date: Mon, 14 Sep 2026 12:00:52 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-09-16 07:15:06.316524
• Title: Graph Matching Relaxations and Amortization for Supervised Graph Prediction
• Title（参考訳）: 教師付きグラフ予測のためのグラフマッチング緩和と補正
• Abstract要約: SGP(End-to-end Supervised Graph Prediction)は、予測グラフとターゲットグラフを任意のノード順序と比較するために、置換不変の損失を必要とする。 まず、この問題の最適輸送緩和について3つの研究を行い、理論上かつ実証的に、Gromov-Wasserstein(GW)の目的がSGPに最も適していることを示す。 トレーニング例毎に得られる内部最適化の解決を避けるため,グラフマッチング(ノードアライメント)問題を補正する手法を提案する。
• 参考スコア（独自算出の注目度）: 11.692215143424976
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: End-to-end Supervised Graph Prediction (SGP) requires a permutation-invariant loss to compare predicted and target graphs with arbitrary node orderings. Such losses typically involve a costly graph-matching problem. We first study three Optimal Transport relaxations of this problem and show, theoretically and empirically, that the Gromov-Wasserstein (GW) objective is the most suitable for SGP. Then, to avoid solving the resulting inner optimization for every training example, we propose to amortize the graph matching (node alignment) problem. For each training sample, the loss function leverages a transport plan provided by a parametric matcher based on the differentiable Sinkhorn algorithm applied on empirical node distributions. The graph prediction module and the matcher are jointly learned. We showcase the efficiency of this approach on toy and real world SGP problems of increasing complexity including a novel Mass-spectra to Scaffold task that we introduce.
• Abstract（参考訳）: SGP(End-to-end Supervised Graph Prediction)は、予測グラフとターゲットグラフを任意のノード順序と比較するために、置換不変の損失を必要とする。 このような損失は通常、コストのかかるグラフマッチングの問題を伴う。 まず、この問題の最適輸送緩和について3つの研究を行い、理論上かつ実証的に、Gromov-Wasserstein(GW)の目的がSGPに最も適していることを示す。 そこで本研究では,学習例ごとに得られる内部最適化の解決を避けるために,グラフマッチング(ノードアライメント)問題を復号化することを提案する。 各トレーニングサンプルに対して、損失関数は、経験ノード分布に適用された微分可能シンクホーンアルゴリズムに基づいて、パラメトリックマーカによって提供される輸送計画を利用する。 グラフ予測モジュールとマーカは共同で学習される。 本稿では,Scaffold タスクに新たに導入したMass-spectra to Scaffold タスクを含む複雑性を増大させる,玩具および実世界の SGP 問題に対するこのアプローチの効率性について紹介する。

関連論文リスト

• AGDN: Learning to Solve Traveling Salesman Problem with Anisotropic Graph Diffusion Network [50.69521065962045]
  Anisotropic Graph Diffusion Network (AGDN) はトラベリングセールスマン問題(TSP)を解決するために設計された新しいグラフニューラルネットワークフレームワークである。 提案手法は,1) 完全連結TSPグラフにおける情報的トポロジ的事前の欠如,2) グラフスペーシフィケーション手法により最適解における接続ノードの喪失,の2つの問題に対処する。 AGDNは、競争力を維持しながら、既存の手法を一貫して上回る。
  論文  参考訳（メタデータ） (2026-06-17T15:24:37Z)
• Differentiable Proximal Graph Matching [40.41380102260085]
  微分可能近位グラフマッチング(DPGM)と呼ばれる近位演算子に基づくグラフマッチングアルゴリズムを提案する。 アルゴリズム全体をグラフ親和性行列からノード対応の予測への微分可能な写像とみなすことができる。 数値実験により、PGMは様々なデータセット上で既存のグラフマッチングアルゴリズムより優れていることが示された。
  論文  参考訳（メタデータ） (2024-05-26T08:17:13Z)
• NodeFormer: A Scalable Graph Structure Learning Transformer for Node Classification [70.51126383984555]
  本稿では,任意のノード間のノード信号を効率的に伝搬する全ペアメッセージパッシング方式を提案する。 効率的な計算は、カーナライズされたGumbel-Softmax演算子によって実現される。 グラフ上のノード分類を含む様々なタスクにおいて,本手法の有望な有効性を示す実験を行った。
  論文  参考訳（メタデータ） (2023-06-14T09:21:15Z)
• Gradient scarcity with Bilevel Optimization for Graph Learning [0.0]
  勾配不足は、ノードのサブセットの損失を最小限にすることでグラフを学習する際に発生する。 我々は、この現象の正確な数学的特徴を与え、双レベル最適化にも現れることを証明した。 この問題を緩和するために,グラフ・ツー・グラフモデル(G2G)を用いた潜時グラフ学習,グラフに先行構造を課すグラフ正規化,あるいは直径を縮小した元のグラフよりも大きなグラフを最適化することを提案する。
  論文  参考訳（メタデータ） (2023-03-24T12:37:43Z)
• Rethinking Explaining Graph Neural Networks via Non-parametric Subgraph Matching [68.35685422301613]
  そこで我々はMatchExplainerと呼ばれる新しい非パラメトリックな部分グラフマッチングフレームワークを提案し、説明的部分グラフを探索する。 ターゲットグラフと他のインスタンスを結合し、ノードに対応する距離を最小化することで最も重要な結合部分構造を識別する。 合成および実世界のデータセットの実験は、最先端のパラメトリックベースラインをかなりのマージンで上回り、MatchExplainerの有効性を示す。
  論文  参考訳（メタデータ） (2023-01-07T05:14:45Z)
• Deep graph matching meets mixed-integer linear programming: Relax at your own risk ? [8.05409526074409]
  グラフマッチング問題のMILP定式化を統合する手法を提案する。 同様のアプローチは、グラフマッチング解決器の最適保証と品質レベルの導入によって導かれる。 実験により,いくつかの理論的知見が得られ,深部グラフマッチング手法の方向性を導出する。
  論文  参考訳（メタデータ） (2021-08-01T08:29:55Z)
• Line Graph Neural Networks for Link Prediction [71.00689542259052]
  実世界の多くのアプリケーションにおいて古典的なグラフ解析問題であるグラフリンク予測タスクについて検討する。 このフォーマリズムでは、リンク予測問題をグラフ分類タスクに変換する。 本稿では,線グラフをグラフ理論に用いて,根本的に異なる新しい経路を求めることを提案する。 特に、線グラフの各ノードは、元のグラフのユニークなエッジに対応するため、元のグラフのリンク予測問題は、グラフ分類タスクではなく、対応する線グラフのノード分類問題として等価に解決できる。
  論文  参考訳（メタデータ） (2020-10-20T05:54:31Z)
• A Generative Graph Method to Solve the Travelling Salesman Problem [1.552282932199974]
  我々は,旅行セールスマン問題(TSP)を概ね解決するために,生成的アプローチである新しいグラフ学習ネットワーク(GLN)を提案する。 GLNモデルは、トレーニングデータセットとしてTSPインスタンスのパターンを直接学習し、グラフプロパティをエンコードし、異なるノードの埋め込みをマージして、最適なツアーを出力する。
  論文  参考訳（メタデータ） (2020-07-09T17:23:55Z)
• Wasserstein-based Graph Alignment [56.84964475441094]
  我々は,より小さいグラフのノードと大きなグラフのノードをマッチングすることを目的とした,1対多のグラフアライメント問題に対する新しい定式化を行った。 提案手法は,各タスクに対する最先端のアルゴリズムに対して,大幅な改善をもたらすことを示す。
  論文  参考訳（メタデータ） (2020-03-12T22:31:59Z)
• Graph Ordering: Towards the Optimal by Learning [69.72656588714155]
  グラフ表現学習は、ノード分類、予測、コミュニティ検出など、多くのグラフベースのアプリケーションで顕著な成功を収めている。 しかし,グラフ圧縮やエッジ分割などのグラフアプリケーションでは,グラフ表現学習タスクに還元することは極めて困難である。 本稿では,このようなアプリケーションの背後にあるグラフ順序付け問題に対して,新しい学習手法を用いて対処することを提案する。
  論文  参考訳（メタデータ） (2020-01-18T09:14:16Z)

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

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