論文の概要: A Unified Pre-training and Adaptation Framework for Combinatorial Optimization on Graphs

• arxiv url: http://arxiv.org/abs/2312.11547v1
• Date: Sat, 16 Dec 2023 12:36:04 GMT
• ステータス: 処理完了
• システム内更新日: 2023-12-20 18:48:24.737637
• Title: A Unified Pre-training and Adaptation Framework for Combinatorial Optimization on Graphs
• Title（参考訳）: グラフの組合せ最適化のための統一事前学習適応フレームワーク
• Authors: Ruibin Zeng, Minglong Lei, Lingfeng Niu, Lan Cheng
• Abstract要約: グラフ上での組合せ最適化(CO)のための事前学習と適応の統一フレームワークを提案する。 最初にMax-SATを用いてグラフ上の異なるCOをブリッジする。これは、標準的な公式や論理情報を持つ節で表されるMax-SAT問題に変換できるからである。 事前トレーニングの段階では、モデルのパラメータを初期化するためにMax-SATインスタンスが生成される。 微調整段階では、COおよびMax-SAT問題からのインスタンスを適応するために使用することにより、転送能力をさらに向上することができる。
• 参考スコア（独自算出の注目度）: 4.659033572014701
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Combinatorial optimization (CO) on graphs is a classic topic that has been extensively studied across many scientific and industrial fields. Recently, solving CO problems on graphs through learning methods has attracted great attention. Advanced deep learning methods, e.g., graph neural networks (GNNs), have been used to effectively assist the process of solving COs. However, current frameworks based on GNNs are mainly designed for certain CO problems, thereby failing to consider their transferable and generalizable abilities among different COs on graphs. Moreover, simply using original graphs to model COs only captures the direct correlations among objects, which does not consider the mathematical logicality and properties of COs. In this paper, we propose a unified pre-training and adaptation framework for COs on graphs with the help of the maximum satisfiability (Max-SAT) problem. We first use Max-SAT to bridge different COs on graphs since they can be converted to Max-SAT problems represented by standard formulas and clauses with logical information. Then, we further design a pre-training and domain adaptation framework to extract the transferable and generalizable features so that different COs can benefit from them. In the pre-training stage, Max-SAT instances are generated to initialize the parameters of the model. In the fine-tuning stage, instances from CO and Max-SAT problems are used for adaptation so that the transferable ability can be further improved. Numerical experiments on several datasets show that features extracted by our framework exhibit superior transferability and Max-SAT can boost the ability to solve COs on graphs.
• Abstract（参考訳）: グラフ上の組合せ最適化(CO)は古典的なトピックであり、多くの科学や産業分野で広く研究されている。 近年,学習手法によるグラフ上のCO問題の解法が注目されている。 グラフニューラルネットワーク(GNN)のような先進的なディープラーニング手法は、COの解決プロセスを効果的に支援するために使われてきた。 しかしながら、GNNに基づく現在のフレームワークは、主に特定のCO問題のために設計されており、グラフ上の異なるCO間の転送可能で一般化可能な能力を考慮できない。 さらに、COsをモデル化するためにオリジナルのグラフを使うだけでは、COsの数学的論理性と性質を考慮しないオブジェクト間の直接的な相関を捉えるだけである。 本稿では,最大満足度問題(Max-SAT)の助けを借りて,グラフ上のCOの統一事前学習・適応フレームワークを提案する。 最初にMax-SATを用いてグラフ上の異なるCOをブリッジする。これは、標準的な公式や論理情報を持つ節で表されるMax-SAT問題に変換できるからである。 さらに,事前学習とドメイン適応のためのフレームワークを設計し,異なるCOがそれらの利点を享受できるように,転送可能で一般化可能な特徴を抽出する。 事前トレーニングの段階では、モデルのパラメータを初期化するためにMax-SATインスタンスが生成される。 微調整段階では、COおよびMax-SAT問題のインスタンスを適応するために使用することにより、転送能力をさらに向上することができる。 いくつかのデータセットの数値実験により,我々のフレームワークが抽出した特徴は優れた転送性を示し,Max-SATはグラフ上のCOを解く能力を向上できることが示された。

関連論文リスト

• Decision-focused Graph Neural Networks for Combinatorial Optimization [62.34623670845006]
  最適化問題に取り組むための新たな戦略は、従来のアルゴリズムに代わるグラフニューラルネットワーク(GNN)の採用である。 GNNや従来のアルゴリズムソルバがCOの領域で人気が高まっているにもかかわらず、それらの統合利用とエンドツーエンドフレームワークにおけるそれらの相関について限定的な研究がなされている。 我々は、GNNを利用してCO問題に補助的なサポートで対処する決定に焦点を当てたフレームワークを導入する。
  論文  参考訳（メタデータ） (2024-06-05T22:52:27Z)
• Graph Q-Learning for Combinatorial Optimization [44.8086492019594]
  グラフニューラルネットワーク(GNN)は,グラフデータの予測と推論の問題を解くのに有効であることが示されている。 本稿では,GNNを組合せ最適化問題に適用できることを示す。
  論文  参考訳（メタデータ） (2024-01-11T01:15:28Z)
• Learnable Graph Matching: A Practical Paradigm for Data Association [74.28753343714858]
  これらの問題に対処するための一般的な学習可能なグラフマッチング法を提案する。 提案手法は,複数のMOTデータセット上での最先端性能を実現する。 画像マッチングでは,一般的な屋内データセットであるScanNetで最先端の手法より優れている。
  論文  参考訳（メタデータ） (2023-03-27T17:39:00Z)
• Transformer-based Machine Learning for Fast SAT Solvers and Logic Synthesis [63.53283025435107]
  CNFベースのSATとMaxSATは論理合成と検証システムの中心である。 そこで本研究では,Transformerアーキテクチャから派生したワンショットモデルを用いて,MaxSAT問題の解法を提案する。
  論文  参考訳（メタデータ） (2021-07-15T04:47:35Z)
• Combinatorial Optimization with Physics-Inspired Graph Neural Networks [0.0]
  最適化問題の解法としてグラフニューラルネットワークを用いる方法を示す。 ニューラルネットワークは、既存の解法よりも優れているか、あるいは優れていることが分かりました。
  論文  参考訳（メタデータ） (2021-07-02T16:54:35Z)
• A Bi-Level Framework for Learning to Solve Combinatorial Optimization on Graphs [91.07247251502564]
  本稿では,2つの世界の長所を結合するハイブリッドな手法を提案する。この手法では,グラフを最適化する上層学習手法とバイレベルフレームワークを開発する。 このような二段階のアプローチは、元のハードCOでの学習を単純化し、モデルキャパシティの需要を効果的に軽減することができる。
  論文  参考訳（メタデータ） (2021-06-09T09:18:18Z)
• A Flexible Framework for Designing Trainable Priors with Adaptive Smoothing and Game Encoding [57.1077544780653]
  我々は、前方通過を非滑らかな凸最適化問題として解釈できるニューラルネットワーク層の設計とトレーニングのための一般的なフレームワークを紹介する。 グラフのノードに代表されるローカルエージェントによって解決され、正規化関数を介して相互作用する凸ゲームに焦点を当てる。 このアプローチは、訓練可能なエンドツーエンドのディープモデル内で、古典的な画像の事前使用を可能にするため、画像の問題を解決するために魅力的である。
  論文  参考訳（メタデータ） (2020-06-26T08:34:54Z)
• Gumbel-softmax-based Optimization: A Simple General Framework for Optimization Problems on Graphs [5.486093983007419]
  本稿では,ディープラーニングフレームワークによって強化された高度な自動微分技術に基づく,シンプルで高速で汎用的なアルゴリズムフレームワークを提案する。 高品質なソリューションは、従来のアプローチに比べてはるかに少ない時間で得られる。
  論文  参考訳（メタデータ） (2020-04-14T14:11:00Z)
• Graph Ordering: Towards the Optimal by Learning [69.72656588714155]
  グラフ表現学習は、ノード分類、予測、コミュニティ検出など、多くのグラフベースのアプリケーションで顕著な成功を収めている。 しかし,グラフ圧縮やエッジ分割などのグラフアプリケーションでは,グラフ表現学習タスクに還元することは極めて困難である。 本稿では,このようなアプリケーションの背後にあるグラフ順序付け問題に対して,新しい学習手法を用いて対処することを提案する。
  論文  参考訳（メタデータ） (2020-01-18T09:14:16Z)

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

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