論文の概要: Equivariant Neural Primal-Dual Assignment for Maximum Common Edge Subgraphs

• arxiv url: http://arxiv.org/abs/2609.32661v1
• Date: Sat, 26 Sep 2026 14:19:12 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-06 21:36:17.250915
• Title: Equivariant Neural Primal-Dual Assignment for Maximum Common Edge Subgraphs
• Title（参考訳）: 最大コモンエッジ部分グラフに対する同変ニューラルプリマル双対アサインメント
• Abstract要約: 分子類似性探索には多くのグラフ対をマッチングする必要がある。 Equivariant Neural Primal-Dual Assignment (ENPDA)を紹介する。 ENPDAは共有マッチングポリシーを学び、さらなるトレーニングなしに新しいペアに適用する。
• 参考スコア（独自算出の注目度）: 16.0495191098223
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Maximum common edge subgraph (MCES) matching finds a partial vertex correspondence between two labeled graphs that preserves as many labeled edges as possible. Molecular similarity search requires matching many graph pairs, making the cost of repeated queries important. The strongest baseline attains accurate MCES solutions but trains a separate network for each pair. We introduce Equivariant Neural Primal-Dual Assignment (ENPDA), which learns a shared matching policy and applies it to new pairs without further training, answering queries roughly three orders of magnitude faster and recovering its training cost after a few dozen queries. The policy recomputes exact objective marginals for candidate matches and learns corrections and step sizes that update their scores. Target prices respond to competition when several source vertices favor the same target. Four update rounds and a Hungarian projection produce a partial one-to-one matching. We prove per-pair guarantees that hold for any network parameters. In exact arithmetic, reordering either graph permutes the assignment and price states, the projected matching is one-to-one, and repaired prices give a valid MCES upper bound. Subtracting the preserved-edge count bounds the optimality gap; combined with structural caps, these certificates prove global optimality for 60 of 291 native test pairs. On three molecular benchmarks with disjoint train/validation/test splits, ENPDA improves over an analytic counterpart with the same update and projection budget by 7.4-8.6 accuracy points; after one second of refinement search, 2.5-3 points of the gain remain. Transferred without fine-tuning to edge-deletion tasks from social and protein graphs, the policy gains 9.1-17.6 points over the analytic counterpart. When output matchings must keep aromatic rings intact, ENPDA recovers more reference bonds than the baselines on all three datasets.
• Abstract（参考訳）: 最大共通エッジ部分グラフ (MCES) マッチングは、可能な限り多くのラベル付きエッジを保持する2つのラベル付きグラフの間の部分頂点対応を見つける。 分子類似性探索には多くのグラフペアのマッチングが必要であり、繰り返しクエリのコストが重要になる。 最強のベースラインは正確なMCESソリューションを実現するが、それぞれに別々のネットワークをトレーニングする。 Equivariant Neural Primal-Dual Assignment (ENPDA)を導入し、共有マッチングポリシーを学習し、さらにトレーニングすることなく新しいペアに適用し、クエリを約3桁高速化し、数十のクエリの後にトレーニングコストを回復する。 このポリシーは、候補マッチの正確な客観的限界を計算し、スコアを更新する修正とステップサイズを学ぶ。 複数の情報源が同じ目標を好んだ場合、ターゲット価格は競争に反応する。 4回の更新ラウンドとハンガリーのプロジェクションは、部分的な1対1のマッチングを生成する。 我々は、任意のネットワークパラメータを保持するペアごとの保証を証明します。 正確な算術では、どちらかのグラフの並べ替えは代入状態と価格状態に変化し、投影されたマッチングは1対1であり、修復された価格は有効なMCES上限を与える。 これらの証明は、構造的な上限と組み合わせて、ネイティブテストペア291のうち60のグローバルな最適性を示す。 不安定な列車/検証/テスト分割を持つ3つの分子ベンチマークでは、ENPDAは、同じ更新と予測予算を持つ分析ベンチマークを7.4-8.6の精度ポイントで改善し、改良探索の1秒後に利得の2.5-3ポイントが残る。 ソーシャルグラフやタンパク質グラフからエッジ削除タスクに微調整なしで移行すると、分析対象よりも9.1-17.6ポイント向上する。 出力マッチングが芳香族環をそのまま保たなければならないとき、ENPDAは3つのデータセットのベースラインよりも多くの基準結合を回収する。

関連論文リスト

• QAM: Quadratic-Accurate Checkpoint Merging via Sequential Consistency [44.9106079497003]
  保存されたチェックポイントはトレーニングの軌道に沿って状態を記録しますが、通常、異なるスケジュールで訪問される状態の更新を判断しません。 これらのチェックポイントが、所定の更新強度でシーケンシャル参照のエンドポイントをいかに正確に再構築できるかを検討する。
  論文  参考訳（メタデータ） (2026-09-28T13:39:41Z)
• Online Supervised Dimension Reduction with Random Features: Diagnostics and Computational Trade-offs [3.7044133020722954]
  Online Kernel Supervised principal Component Analysis (OKSPCA)は、有限乱数係数座標における中心となるクロスモーメントと、確立された目的に対するAdamスタイルの正則基底更新を組み合わせたものである。 有限乱数係数座標における中心的クロスモーメントと、確立された目的に対するAdamスタイルの正規直交基底更新を組み合わせたOKSPCAについて、これらの区別について検討する。
  論文  参考訳（メタデータ） (2026-09-17T14:19:29Z)
• Learning Where Outcomes Change:Credit-Addressable Reasoning for Multimodal Geometry [105.89493240787861]
  推論中に露出したセマンティックユニットは、学習が代替品と比較し、クレジットを割り当てる場所を定義する。 我々は,この原理を,ライン順応可能な実行可能コードとして視覚的関係を表すCode-CoTでインスタンス化し,推論を型付きイベントに整理する。 9つの幾何ベンチマークで、CE-GRPOは平均76.04の精度を達成し、Qwen3-VL-8Bと軌跡レベルGRPOをそれぞれ8.09$と3.43ポイント上回る。
  論文  参考訳（メタデータ） (2026-08-31T08:44:36Z)
• PAIR: Pairwise-Aware Inclusion Reweighting for Adaptive Rollout Allocation in RLVR [0.0]
  検証可能な報酬を伴う強化学習は、長い推論軌道の計算生成グループの大部分に費やしている。 最近のアロケータは、難易度やユーティリティのポイントワイズな概念に従って、プロンプト、ロールアウト、トークンに予算を割り当てることで、このコストを削減している。 グループ相対スコア勾配は、独立点寄与の総和ではなく、ロールアウト対に対する2次統計値である。
  論文  参考訳（メタデータ） (2026-08-11T19:24:59Z)
• MinPrompt: Graph-based Minimal Prompt Data Augmentation for Few-shot Question Answering [64.6741991162092]
  オープンドメイン質問応答のための最小限のデータ拡張フレームワークMinPromptを提案する。 我々は、生テキストをグラフ構造に変換し、異なる事実文間の接続を構築する。 次に、グラフアルゴリズムを適用して、原文のほとんどの情報をカバーするのに必要な最小限の文の集合を識別する。 同定された文サブセットに基づいてQAペアを生成し、選択した文に基づいてモデルをトレーニングし、最終モデルを得る。
  論文  参考訳（メタデータ） (2023-10-08T04:44:36Z)
• Q-REG: End-to-End Trainable Point Cloud Registration with Surface Curvature [81.25511385257344]
  本稿では、リッチな幾何学的情報を用いて、単一の対応から剛性ポーズを推定する新しい解Q-REGを提案する。 Q-REGは、堅牢な推定を徹底的な探索として形式化し、エンドツーエンドのトレーニングを可能にする。 実験では、Q-REGは対応マッチング法に非依存であり、推論とエンドツーエンドトレーニングの両方で使用した場合に一貫した改善を提供する。
  論文  参考訳（メタデータ） (2023-09-27T20:58:53Z)
• Deep Probabilistic Graph Matching [72.6690550634166]
  本稿では,マッチング制約を伴わずに,元のQAPに適合する深層学習ベースのグラフマッチングフレームワークを提案する。 提案手法は,一般的な3つのベンチマーク(Pascal VOC,Wilow Object,SPair-71k)で評価され,すべてのベンチマークにおいて過去の最先端よりも優れていた。
  論文  参考訳（メタデータ） (2022-01-05T13:37:27Z)

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

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