論文の概要: Graph neural networks and the energetic cavity method for combinatorial optimization

• arxiv url: http://arxiv.org/abs/2609.07456v1
• Date: Mon, 07 Sep 2026 13:07:02 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-09-10 19:44:08.428898
• Title: Graph neural networks and the energetic cavity method for combinatorial optimization
• Title（参考訳）: 組合せ最適化のためのグラフニューラルネットワークとエネルギー空洞法
• Abstract要約: 本研究では,Isingモデルの基底状態の近似化にグラフニューラルネットワーク(GNN)を用いることを検討した。 我々は、これらを組み込むため、GNNに小さな変更を加えることで、パフォーマンスが大幅に向上すると考えている。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the use of graph neural networks (GNNs) for finding approximate ground states of Ising models. Efficiently finding these ground states is of broad significance because many combinatorial optimization problems can be formulated as an Ising model with the appropriate choice of couplings and fields. Exactly solving these problems is hard but there are many good heuristic methods. A lineage of these heuristics build from mean-field approximations: one approach uses the leading eigenvector of an appropriately defined matrix, another is the min-sum algorithm, also known as the energetic cavity method. Without modification, GNNs perform worse than both of these methods. We consider small modifications to the GNN to incorporate these heuristics and find that this considerably improves performance. While the modified approach is competitive against other deep-learning approaches, we still find that simulated annealing is reliably at least as good as deep learning methods for the same computational cost.
• Abstract（参考訳）: 本研究では,Isingモデルの基底状態の近似化にグラフニューラルネットワーク(GNN)を用いることを検討した。 これらの基底状態の効率的な発見は、結合と体を適切に選択したイジングモデルとして多くの組合せ最適化問題を定式化できるため、大きな意味を持つ。 これらの問題を正確に解くことは難しいが、多くの優れたヒューリスティックな方法がある。 これらのヒューリスティックスの系統は平均場近似から成り立っている: 1つのアプローチは適切に定義された行列の先頭固有ベクトルを使い、もう1つはmin-sumアルゴリズムであり、エネルギー空洞法(energetic cavity method)とも呼ばれる。 修正がなければ、GNNはどちらの方法よりもパフォーマンスが悪くなります。 我々は、これらのヒューリスティックを組み込むため、GNNに小さな修正を加えることを検討し、これが性能を大幅に改善することを発見した。 修正されたアプローチは、他のディープラーニングアプローチと競合するが、シミュレーションアニーリングは、同じ計算コストのディープラーニング手法と同じくらい、少なくとも確実に優れていることは、まだ明らかである。

関連論文リスト

• Preference-Based Gradient Estimation for ML-Guided Approximate Combinatorial Optimization [15.102119312523696]
  組合せ最適化(CO)の問題は、医学、物流、製造など幅広い領域で発生する。 本研究では,CO の非学習近似アルゴリズムを学習ベースで拡張する手法を提案する。 本手法は,近似アルゴリズムをブラックボックスとして扱う新しい勾配推定法を用いて,自己教師付き方式でエンドツーエンドに学習する。
  論文  参考訳（メタデータ） (2025-02-26T18:23:07Z)
• Tensor Network Estimation of Distribution Algorithms [0.0]
  近年の論文では、テンソルネットワークを進化最適化アルゴリズムに統合する手法が登場している。 これらの手法の最適化性能は, 生成モデルのパワーと直接的に関係しないことがわかった。 これを踏まえると、生成モデルの出力に明示的な突然変異演算子を加えることで、最適化性能が向上することがしばしばある。
  論文  参考訳（メタデータ） (2024-12-27T18:22:47Z)
• GDSG: Graph Diffusion-based Solution Generator for Optimization Problems in MEC Networks [109.17835015018532]
  グラフ拡散型ソリューション生成(GDSG)法を提案する。 このアプローチは、おそらく最適な解に収束しながら、最適以下のデータセットを扱うように設計されている。 グラフニューラルネットワーク(GNN)を用いたマルチタスク拡散モデルとしてGDSGを構築し,高品質な解の分布を求める。
  論文  参考訳（メタデータ） (2024-12-11T11:13:43Z)
• Enhancing CNN Classification with Lamarckian Memetic Algorithms and Local Search [0.0]
  そこで本研究では,局所探索機能を組み込んだ2段階学習手法と集団最適化アルゴリズムを併用した新しい手法を提案する。 実験の結果,提案手法は最先端の勾配に基づく手法よりも優れていた。
  論文  参考訳（メタデータ） (2024-10-26T17:31:15Z)
• Sample-efficient Bayesian Optimisation Using Known Invariances [56.34916328814857]
  バニラと制約付きBOアルゴリズムは、不変目的を最適化する際の非効率性を示す。 我々はこれらの不変カーネルの最大情報ゲインを導出する。 核融合炉用電流駆動システムの設計に本手法を用い, 高性能溶液の探索を行った。
  論文  参考訳（メタデータ） (2024-10-22T12:51:46Z)
• Ensemble Quadratic Assignment Network for Graph Matching [52.20001802006391]
  グラフマッチングはコンピュータビジョンやパターン認識において一般的に用いられる技法である。 最近のデータ駆動型アプローチは、グラフマッチングの精度を著しく改善した。 データ駆動手法と従来の手法の利点を組み合わせたグラフニューラルネットワーク(GNN)に基づくアプローチを提案する。
  論文  参考訳（メタデータ） (2024-03-11T06:34:05Z)
• 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)
• Unfolded proximal neural networks for robust image Gaussian denoising [7.018591019975253]
  本稿では,二元FBと二元Chambolle-Pockアルゴリズムの両方に基づいて,ガウス分母タスクのためのPNNを統一的に構築するフレームワークを提案する。 また、これらのアルゴリズムの高速化により、関連するNN層におけるスキップ接続が可能であることを示す。
  論文  参考訳（メタデータ） (2023-08-06T15:32:16Z)
• Inability of a graph neural network heuristic to outperform greedy algorithms in solving combinatorial optimization problems like Max-Cut [0.0]
  Nature Machine Intelligence 4, 367 (2022) において、Schuetzらは、様々な古典的なNPハード最適化問題を解決するためにニューラルネットワーク(GNN)を使用するスキームを提供している。 ネットワークがサンプルインスタンス上でどのようにトレーニングされているかを説明し、その結果のGNNは、広く使われているテクニックを適用して、その成功の可能性を判断する。 しかし, より綿密な検査により, このGNNの報告結果は勾配降下率よりもわずかに優れており, グリーディアルゴリズムにより性能が向上していることがわかった。
  論文  参考訳（メタデータ） (2022-10-02T20:50:33Z)
• Neural Improvement Heuristics for Graph Combinatorial Optimization Problems [49.85111302670361]
  本稿では,ノード,エッジ,あるいはその両方に情報をエンコードするグラフベースの問題を扱う新しいニューラル改善(NI)モデルを提案する。 提案モデルは,各地区の操作の選択を誘導する丘登頂に基づくアルゴリズムの基本的な構成要素として機能する。
  論文  参考訳（メタデータ） (2022-06-01T10:35:29Z)
• Meta-Solver for Neural Ordinary Differential Equations [77.8918415523446]
  本研究では,ソルバ空間の変動がニューラルODEの性能を向上する方法について検討する。 解法パラメータ化の正しい選択は, 敵の攻撃に対するロバスト性の観点から, 神経odesモデルに大きな影響を与える可能性がある。
  論文  参考訳（メタデータ） (2021-03-15T17:26:34Z)
• Self-Directed Online Machine Learning for Topology Optimization [58.920693413667216]
  自己指向型オンライン学習最適化は、ディープニューラルネットワーク(DNN)と有限要素法(FEM)計算を統合している。 本アルゴリズムは, コンプライアンスの最小化, 流体構造最適化, 伝熱促進, トラス最適化の4種類の問題によって検証された。 その結果, 直接使用法と比較して計算時間を2～5桁削減し, 実験で検証した全ての最先端アルゴリズムより優れていた。
  論文  参考訳（メタデータ） (2020-02-04T20:00:28Z)

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

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