論文の概要: 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が輝いている。
また, 実験中の観測特性について, 対応する数学的定式化と詳細な考察を行った。
関連論文リスト
- Mixed-Integer Optimisation of Graph Neural Networks for Computer-Aided
Molecular Design [4.593587844188084]
ReLUニューラルネットワークは、混合整数線形プログラミング(MILP)の制約としてモデル化されている。
本稿では、ReLUグラフ畳み込みニューラルネットワークの定式化と、ReLUグラフSAGEモデルのMILP定式化を提案する。
これらの定式化により、グローバルな最適性に埋め込まれた訓練されたGNNで最適化問題を解くことができる。
論文 参考訳(メタデータ) (2023-12-02T21:10:18Z) - 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) - How Graph Neural Networks Learn: Lessons from Training Dynamics [86.27589054492427]
グラフニューラルネットワーク(GNN)の関数空間におけるトレーニングダイナミクスについて検討する。
勾配降下によるGNNの最適化は暗黙的にグラフ構造を利用して学習した関数を更新する。
グラフ構造を用いて学習した関数を明示的に更新することで得られる単純で効率的な非パラメトリックアルゴリズムは、非線形GNNと一貫して競合することを示す。
論文 参考訳(メタデータ) (2023-10-08T10:19:56Z) - Neural Improvement Heuristics for Graph Combinatorial Optimization
Problems [49.85111302670361]
本稿では,ノード,エッジ,あるいはその両方に情報をエンコードするグラフベースの問題を扱う新しいニューラル改善(NI)モデルを提案する。
提案モデルは,各地区の操作の選択を誘導する丘登頂に基づくアルゴリズムの基本的な構成要素として機能する。
論文 参考訳(メタデータ) (2022-06-01T10:35:29Z) - GPN: A Joint Structural Learning Framework for Graph Neural Networks [36.38529113603987]
グラフ構造と下流タスクを同時に学習するGNNベースの共同学習フレームワークを提案する。
本手法は,この課題を解決するためのGNNベースの二段階最適化フレームワークである。
論文 参考訳(メタデータ) (2022-05-12T09:06:04Z) - A Differentiable Approach to Combinatorial Optimization using Dataless
Neural Networks [20.170140039052455]
我々は、ソリューションを生成するニューラルネットワークのトレーニングにデータを必要としないという、根本的に異なるアプローチを提案する。
特に、最適化問題をニューラルネットワークに還元し、データレストレーニングスキームを用いて、それらのパラメータが関心の構造をもたらすように、ネットワークのパラメータを洗練する。
論文 参考訳(メタデータ) (2022-03-15T19:21:31Z) - Combinatorial Optimization with Physics-Inspired Graph Neural Networks [0.0]
最適化問題の解法としてグラフニューラルネットワークを用いる方法を示す。
ニューラルネットワークは、既存の解法よりも優れているか、あるいは優れていることが分かりました。
論文 参考訳(メタデータ) (2021-07-02T16:54:35Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。