論文の概要: Understanding the Usage of QUBO-based Hamiltonian Function in Combinatorial Optimization over Graphs: A Discussion Using Max Cut (MC) Problem

• arxiv url: http://arxiv.org/abs/2308.13978v1
• Date: Sun, 27 Aug 2023 00:57:01 GMT
• ステータス: 処理完了
• システム内更新日: 2023-08-29 17:43:49.853106
• Title: Understanding the Usage of QUBO-based Hamiltonian Function in Combinatorial Optimization over Graphs: A Discussion Using Max Cut (MC) Problem
• Title（参考訳）: グラフ上の組合せ最適化におけるquboに基づくハミルトニアン関数の利用の理解:max cut(mc)問題による考察
• Authors: Redwan Ahmed Rizvee, Md. Mosaddek Khan
• Abstract要約: ノード間で情報を伝達するために、グラフニューラルネットワーク(GNN)をメッセージパッシングアーキテクチャとして使用しています。 GNNベースのRL(MCTS-GNN)を用いたMonty-Carlo Tree Search、GNNベースのRL(GRL)を用いたDQN、アテンションベースのRL(GRL)を用いた汎用GNN(GRL)の3つの定式化について検討する。 我々の研究は、RLに基づくパラダイムにおいて、QUBOの定式化におけるハミルトン関数に基づく最適化はモデル収束をもたらし、一般的な報酬関数として使用できることを述べている。
• 参考スコア（独自算出の注目度）: 1.566437882635872
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Quadratic Unconstrained Binary Optimization (QUBO) is a generic technique to model various NP-hard combinatorial optimization problems in the form of binary variables. The Hamiltonian function is often used to formulate QUBO problems where it is used as the objective function in the context of optimization. In this study, we investigate how reinforcement learning-based (RL) paradigms with the presence of the Hamiltonian function can address combinatorial optimization problems over graphs in QUBO formulations. We use Graph Neural Network (GNN) as the message-passing architecture to convey the information among the nodes. We have centered our discussion on QUBO formulated Max-Cut problem but the intuitions can be extended to any QUBO supported canonical NP-Hard combinatorial optimization problems. We mainly investigate three formulations, Monty-Carlo Tree Search with GNN-based RL (MCTS-GNN), DQN with GNN-based RL, and a generic GNN with attention-based RL (GRL). Our findings state that in the RL-based paradigm, the Hamiltonian function-based optimization in QUBO formulation brings model convergence and can be used as a generic reward function. We also analyze and present the performance of our RL-based setups through experimenting over graphs of different densities and compare them with a simple GNN-based setup in the light of constraint violation, learning stability and computation cost. As per one of our findings, all the architectures provide a very comparable performance in sparse graphs as per the number of constraint violation whreas MCTS-GNN gives the best performance. In the similar criteria, the performance significantly starts to drop both for GRL and simple GNN-based setups whereas MCTS-GNN and DQN shines. We also present the corresponding mathematical formulations and in-depth discussion of the observed characteristics during experimentations.
• Abstract（参考訳）: Quadratic Unconstrained Binary Optimization (QUBO) は、NP-hard組合せ最適化問題をバイナリ変数の形でモデル化する一般的な手法である。 ハミルトニアン函数は、最適化の文脈において目的関数として使用されるQUBO問題を定式化するためにしばしば用いられる。 本研究では,ハミルトニアン関数の存在下での強化学習ベース(rl)パラダイムが,qubo定式化におけるグラフ上の組合せ最適化問題にどのように対処できるかを検討する。 ノード間の情報伝達には,graph neural network(gnn)をメッセージパッシングアーキテクチャとして使用する。 我々はQUBOの定式化Max-Cut問題を中心に議論を行ったが、直観はQUBOがサポートしている標準NP-Hard組合せ最適化問題にまで拡張することができる。 GNNベースのRL(MCTS-GNN)を用いたMonty-Carlo Tree Search,GNNベースのRLを用いたDQN,注意に基づくRL(GRL)を用いた汎用GNNの3つの定式化について検討する。 本研究は, rlに基づくパラダイムにおいて, qubo定式化におけるハミルトニアン関数に基づく最適化はモデル収束をもたらし, 汎用報酬関数として使用できることを示す。 また, 制約違反, 学習安定性, 計算コストを考慮して, 異なる密度のグラフ上で実験し, 単純なGNNベースの設定と比較することにより, RLベースのセットアップの性能を解析・提示する。 私たちの調査結果の1つによると、すべてのアーキテクチャは、MCTS-GNNの制約違反の回数に応じて、スパースグラフで非常に同等のパフォーマンスを提供する。 同様の基準では、GRLと単純なGNNベースのセットアップの両方でパフォーマンスが大幅に低下し始め、MCTS-GNNとDQNが輝いている。 また, 実験中の観測特性について, 対応する数学的定式化と詳細な考察を行った。

関連論文リスト

• Scalable Graph Compressed Convolutions [68.85227170390864]
  ユークリッド畳み込みのための入力グラフのキャリブレーションに置換を適用する微分可能手法を提案する。 グラフキャリブレーションに基づいて,階層型グラフ表現学習のための圧縮畳み込みネットワーク(CoCN)を提案する。
  論文  参考訳（メタデータ） (2024-07-26T03:14:13Z)
• Enhancing GNNs Performance on Combinatorial Optimization by Recurrent Feature Update [0.09986418756990156]
  本稿では,組合せ最適化(CO)問題を効率よく解くために,GNNのパワーを活用して,QRF-GNNと呼ぶ新しいアルゴリズムを提案する。 QUBO緩和による損失関数の最小化による教師なし学習に依存している。 実験の結果、QRF-GNNは既存の学習ベースアプローチを大幅に上回り、最先端の手法に匹敵することがわかった。
  論文  参考訳（メタデータ） (2024-07-23T13:34:35Z)
• Decision-focused Graph Neural Networks for Combinatorial Optimization [62.34623670845006]
  最適化問題に取り組むための新たな戦略は、従来のアルゴリズムに代わるグラフニューラルネットワーク(GNN)の採用である。 GNNや従来のアルゴリズムソルバがCOの領域で人気が高まっているにもかかわらず、それらの統合利用とエンドツーエンドフレームワークにおけるそれらの相関について限定的な研究がなされている。 我々は、GNNを利用してCO問題に補助的なサポートで対処する決定に焦点を当てたフレームワークを導入する。
  論文  参考訳（メタデータ） (2024-06-05T22:52:27Z)
• Combinatorial Optimization with Automated Graph Neural Networks [28.19349828026972]
  NP-hard CO 問題,すなわち textbfAutoGNP を解決するために,textbfAUTOmated textbfGNN のクラスを新たに提案する。 AutoGNPの考え方は、グラフニューラルアーキテクチャ検索アルゴリズムを使用して、与えられたNPハード最適化問題に対して最適なGNNを自動的に見つけることである。
  論文  参考訳（メタデータ） (2024-06-05T02:43:41Z)
• Hamiltonian-based Quantum Reinforcement Learning for Neural Combinatorial Optimization [2.536162003546062]
  量子コンピューティング(QC)とニューラル最適化(NCO)の交差点におけるアプローチとして,ハミルトニアンの量子強化学習(QRL)を導入する。 我々のアンサーゼは、ハードウェア効率のよいアンサーゼと比較して、良好なトレーサビリティ特性を示す一方で、以前の研究とは異なり、グラフベースの問題に制限されない。 本研究では,ハミルトニアンのQRLの性能を多種多様な最適化問題で評価し,本手法の適用可能性を実証し,QAOAと比較する。
  論文  参考訳（メタデータ） (2024-05-13T14:36:22Z)
• A Graph Neural Network-Based QUBO-Formulated Hamiltonian-Inspired Loss Function for Combinatorial Optimization using Reinforcement Learning [1.325953054381901]
  グラフニューラルネットワーク(GNN)を用いた新しいモンティカルロ木探索手法を提案する。 PI-GNNに関連する行動パターンを特定し,その性能向上のための戦略を考案する。 また、RL法とQUBO法で定式化されたハミルトニアンとの橋渡しにも着目する。
  論文  参考訳（メタデータ） (2023-11-27T19:33:14Z)
• GPN: A Joint Structural Learning Framework for Graph Neural Networks [36.38529113603987]
  グラフ構造と下流タスクを同時に学習するGNNベースの共同学習フレームワークを提案する。 本手法は,この課題を解決するためのGNNベースの二段階最適化フレームワークである。
  論文  参考訳（メタデータ） (2022-05-12T09:06:04Z)
• A Unified View on Graph Neural Networks as Graph Signal Denoising [49.980783124401555]
  グラフニューラルネットワーク(GNN)は,グラフ構造化データの学習表現において顕著に普及している。 本研究では,代表的GNNモデル群における集約過程を,グラフ記述問題の解法とみなすことができることを数学的に確立する。 UGNNから派生した新しいGNNモデルADA-UGNNをインスタンス化し、ノード間の適応的滑らかさでグラフを処理する。
  論文  参考訳（メタデータ） (2020-10-05T04:57:18Z)
• Multipole Graph Neural Operator for Parametric Partial Differential Equations [57.90284928158383]
  物理系をシミュレーションするためのディープラーニングベースの手法を使用する際の大きな課題の1つは、物理ベースのデータの定式化である。 線形複雑度のみを用いて、あらゆる範囲の相互作用をキャプチャする、新しいマルチレベルグラフニューラルネットワークフレームワークを提案する。 実験により, 離散化不変解演算子をPDEに学習し, 線形時間で評価できることを確認した。
  論文  参考訳（メタデータ） (2020-06-16T21:56:22Z)
• Binarized Graph Neural Network [65.20589262811677]
  我々は二項化グラフニューラルネットワークを開発し、二項化ネットワークパラメータを用いてノードのバイナリ表現を学習する。 提案手法は既存のGNNベースの埋め込み手法にシームレスに統合できる。 実験により、提案された二項化グラフニューラルネットワーク、すなわちBGNは、時間と空間の両方の観点から、桁違いに効率的であることが示されている。
  論文  参考訳（メタデータ） (2020-04-19T09:43:14Z)
• Graph Ordering: Towards the Optimal by Learning [69.72656588714155]
  グラフ表現学習は、ノード分類、予測、コミュニティ検出など、多くのグラフベースのアプリケーションで顕著な成功を収めている。 しかし,グラフ圧縮やエッジ分割などのグラフアプリケーションでは,グラフ表現学習タスクに還元することは極めて困難である。 本稿では,このようなアプリケーションの背後にあるグラフ順序付け問題に対して,新しい学習手法を用いて対処することを提案する。
  論文  参考訳（メタデータ） (2020-01-18T09:14:16Z)

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

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