論文の概要: Combinatorial Optimization with Physics-Inspired Graph Neural Networks
- arxiv url: http://arxiv.org/abs/2107.01188v1
- Date: Fri, 2 Jul 2021 16:54:35 GMT
- ステータス: 処理完了
- システム内更新日: 2021-07-05 12:56:07.667172
- Title: Combinatorial Optimization with Physics-Inspired Graph Neural Networks
- Title（参考訳）: 物理インスパイアされたグラフニューラルネットワークによる組合せ最適化
- Authors: Martin J. A. Schuetz, J. Kyle Brubaker, Helmut G. Katzgraber
- Abstract要約: 最適化問題の解法としてグラフニューラルネットワークを用いる方法を示す。
ニューラルネットワークは、既存の解法よりも優れているか、あるいは優れていることが分かりました。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We demonstrate how graph neural networks can be used to solve combinatorial
optimization problems. Our approach is broadly applicable to canonical NP-hard
problems in the form of quadratic unconstrained binary optimization problems,
such as maximum cut, minimum vertex cover, maximum independent set, as well as
Ising spin glasses and higher-order generalizations thereof in the form of
polynomial unconstrained binary optimization problems. We apply a relaxation
strategy to the problem Hamiltonian to generate a differentiable loss function
with which we train the graph neural network and apply a simple projection to
integer variables once the unsupervised training process has completed. We
showcase our approach with numerical results for the canonical maximum cut and
maximum independent set problems. We find that the graph neural network
optimizer performs on par or outperforms existing solvers, with the ability to
scale beyond the state of the art to problems with millions of variables.
- Abstract（参考訳）: 組合せ最適化問題の解法としてグラフニューラルネットワークを用いる方法を示す。
本手法は,最大カット,最小頂点被覆,最大独立集合,イジングスピングラスおよび多項式非拘束二元最適化問題の形式での高次一般化といった二次非拘束二元最適化問題の形式において,正準np-ハード問題に対して広く適用できる。
グラフニューラルネットワークをトレーニングし、教師なし学習プロセスが完了すると、単純なプロジェクションを整数変数に適用する、微分可能な損失関数を生成するために、ハミルトン問題に緩和戦略を適用する。
正準最大カットと最大独立集合問題に対する数値計算結果を用いて本手法を実証する。
グラフニューラルネットワークオプティマイザが既存のソルバと同等かそれ以上の性能を発揮し、数百万の変数を持つ問題に対して最先端を超えてスケールすることができることが分かりました。
関連論文リスト
- 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) - Optimizing Solution-Samplers for Combinatorial Problems: The Landscape
of Policy-Gradient Methods [52.0617030129699]
本稿では,DeepMatching NetworksとReinforcement Learningメソッドの有効性を解析するための新しい理論フレームワークを提案する。
我々の主な貢献は、Max- and Min-Cut、Max-$k$-Bipartite-Bi、Maximum-Weight-Bipartite-Bi、Traveing Salesman Problemを含む幅広い問題である。
本分析の副産物として,バニラ降下による新たな正則化プロセスを導入し,失効する段階的な問題に対処し,悪い静止点から逃れる上で有効であることを示す理論的および実験的証拠を提供する。
論文 参考訳（メタデータ） (2023-10-08T23:39:38Z) - Are Graph Neural Networks Optimal Approximation Algorithms? [28.469481437685072]
最適化問題のクラスに対して最適な近似アルゴリズムをキャプチャするグラフニューラルネットワークアーキテクチャを設計する。
我々は、OptGNNの学習した埋め込みから最適解のバウンダリを生成するアルゴリズムを設計するために、凸緩和を捕捉するOptGNNの能力を利用する。
論文 参考訳（メタデータ） (2023-10-01T00:12:31Z) - Learning to solve Minimum Cost Multicuts efficiently using Edge-Weighted
Graph Convolutional Neural Networks [13.985534521589257]
グラフ畳み込みニューラルネットワーク(GNN)は、最適化の文脈で有望であることが証明されている。
我々は、グラフ畳み込みネットワーク、符号付きグラフ畳み込みネットワーク、グラフ等化ネットワークなど、さまざまなGNNに適応する。
エンドツーエンドのトレーニング可能なマルチカットへの最初のアプローチを提供する。
論文 参考訳（メタデータ） (2022-04-04T10:21:02Z) - Meta-Solver for Neural Ordinary Differential Equations [77.8918415523446]
本研究では,ソルバ空間の変動がニューラルODEの性能を向上する方法について検討する。
解法パラメータ化の正しい選択は, 敵の攻撃に対するロバスト性の観点から, 神経odesモデルに大きな影響を与える可能性がある。
論文 参考訳（メタデータ） (2021-03-15T17:26:34Z) - A Flexible Framework for Designing Trainable Priors with Adaptive
Smoothing and Game Encoding [57.1077544780653]
我々は、前方通過を非滑らかな凸最適化問題として解釈できるニューラルネットワーク層の設計とトレーニングのための一般的なフレームワークを紹介する。
グラフのノードに代表されるローカルエージェントによって解決され、正規化関数を介して相互作用する凸ゲームに焦点を当てる。
このアプローチは、訓練可能なエンドツーエンドのディープモデル内で、古典的な画像の事前使用を可能にするため、画像の問題を解決するために魅力的である。
論文 参考訳（メタデータ） (2020-06-26T08:34:54Z) - Erdos Goes Neural: an Unsupervised Learning Framework for Combinatorial
Optimization on Graphs [35.14404918074861]
本研究では,グラフ上での組合せ最適化問題に対する教師なし学習フレームワークを提案する。
エルドスの確率論的手法に触発され、ニューラルネットワークを用いて集合上の確率分布をパラメータ化する。
ネットワークが適切に選択された損失に最適化された場合、学習された分布は、制御された確率、低コストな積分解を含むことを示す。
論文 参考訳（メタデータ） (2020-06-18T16:13:36Z) - The Hidden Convex Optimization Landscape of Two-Layer ReLU Neural
Networks: an Exact Characterization of the Optimal Solutions [51.60996023961886]
コーン制約のある凸最適化プログラムを解くことにより,グローバルな2層ReLUニューラルネットワークの探索が可能であることを示す。
我々の分析は新しく、全ての最適解を特徴づけ、最近、ニューラルネットワークのトレーニングを凸空間に持ち上げるために使われた双対性に基づく分析を活用できない。
論文 参考訳（メタデータ） (2020-06-10T15:38:30Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。