論文の概要: Are Graph Neural Networks Optimal Approximation Algorithms?

• arxiv url: http://arxiv.org/abs/2310.00526v5
• Date: Tue, 6 Feb 2024 01:45:10 GMT
• ステータス: 処理完了
• システム内更新日: 2024-02-07 20:14:48.054443
• Title: Are Graph Neural Networks Optimal Approximation Algorithms?
• Title（参考訳）: グラフニューラルネットワークは最適な近似アルゴリズムか?
• Authors: Morris Yau, Eric Lu, Nikolaos Karalias, Jessica Xu, Stefanie Jegelka
• Abstract要約: 最適化問題のクラスに対して最適な近似アルゴリズムをキャプチャするグラフニューラルネットワークアーキテクチャを設計する。 我々は、OptGNNの学習した埋め込みから最適解のバウンダリを生成するアルゴリズムを設計するために、凸緩和を捕捉するOptGNNの能力を利用する。
• 参考スコア（独自算出の注目度）: 28.469481437685072
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In this work we design graph neural network architectures that capture optimal approximation algorithms for a large class of combinatorial optimization problems, using powerful algorithmic tools from semidefinite programming (SDP). Concretely, we prove that polynomial-sized message-passing algorithms can represent the most powerful polynomial time algorithms for Max Constraint Satisfaction Problems assuming the Unique Games Conjecture. We leverage this result to construct efficient graph neural network architectures, OptGNN, that obtain high-quality approximate solutions on landmark combinatorial optimization problems such as Max-Cut, Min-Vertex-Cover, and Max-3-SAT. Our approach achieves strong empirical results across a wide range of real-world and synthetic datasets against solvers and neural baselines. Finally, we take advantage of OptGNN's ability to capture convex relaxations to design an algorithm for producing bounds on the optimal solution from the learned embeddings of OptGNN.
• Abstract（参考訳）: 本研究では,半定義型プログラミング(sdp)の強力なアルゴリズムツールを用いて,組合せ最適化問題に対する最適近似アルゴリズムをキャプチャするグラフニューラルネットワークアーキテクチャを設計する。 具体的には, 多項式サイズのメッセージパッシングアルゴリズムは, ユニクゲーム・コンジェクチャを仮定した最大制約満足度問題に対して, 最も強力な多項式時間アルゴリズムを表現できることを示す。 我々はこの結果を利用して、Max-Cut、Min-Vertex-Cover、Max-3-SATといったランドマーク組合せ最適化問題に対する高品質な近似解を得る効率的なグラフニューラルネットワークアーキテクチャOptGNNを構築する。 提案手法は,実世界および合成データセットの幅広い領域において,解法や神経ベースラインに対して強い実験結果が得られる。 最後に, コンベックス緩和を捉えた OptGNN の機能を活用し, 学習した OptGNN の埋め込みから最適解のバウンドを生成するアルゴリズムを設計する。

関連論文リスト

• torchmSAT: A GPU-Accelerated Approximation To The Maximum Satisfiability Problem [1.5850859526672516]
  最大満足度問題(MaxSAT)の解を近似できる単一の微分可能関数を導出する。 我々は,我々の微分可能な関数をモデル化する新しいニューラルネットワークアーキテクチャを提案し,バックプロパゲーションを用いてMaxSATを段階的に解く。
  論文  参考訳（メタデータ） (2024-02-06T02:33:00Z)
• PNN: From proximal algorithms to robust unfolded image denoising networks and Plug-and-Play methods [7.317910352447519]
  本稿では,二元FBと二元Chambolle-Pockアルゴリズムの両方に基づいて,ガウス分母タスクのためのPNNを統一的に構築するフレームワークを提案する。 また、これらのアルゴリズムの高速化により、関連するNN層におけるスキップ接続が可能であることを示す。
  論文  参考訳（メタデータ） (2023-08-06T15:32:16Z)
• Let the Flows Tell: Solving Graph Combinatorial Optimization Problems with GFlowNets [86.43523688236077]
  組合せ最適化(CO)問題はしばしばNPハードであり、正確なアルゴリズムには及ばない。 GFlowNetsは、複合非正規化密度を逐次サンプリングする強力な機械として登場した。 本稿では,異なる問題に対してマルコフ決定プロセス(MDP)を設計し,条件付きGFlowNetを学習して解空間からサンプルを作成することを提案する。
  論文  参考訳（メタデータ） (2023-05-26T15:13:09Z)
• Composite Optimization Algorithms for Sigmoid Networks [3.160070867400839]
  線形化近位アルゴリズムと乗算器の交互方向に基づく合成最適化アルゴリズムを提案する。 フランク関数のフィッティングに関する数値実験により、提案アルゴリズムは十分堅牢に機能することを示した。
  論文  参考訳（メタデータ） (2023-03-01T15:30:29Z)
• Neural Combinatorial Optimization: a New Player in the Field [69.23334811890919]
  本稿では,ニューラルネットワークに基づくアルゴリズムの古典的最適化フレームワークへの導入に関する批判的分析を行う。 性能, 転送可能性, 計算コスト, 大規模インスタンスなど, これらのアルゴリズムの基本的側面を分析するために, 総合的研究を行った。
  論文  参考訳（メタデータ） (2022-05-03T07:54:56Z)
• Optimal Gradient-based Algorithms for Non-concave Bandit Optimization [76.57464214864756]
  この研究は、未知の報酬関数が非可逆であるようなバンドイット問題の大群を考察する。 我々のアルゴリズムは、非常に一般化されたゼロ階最適化のパラダイムに基づいている。 標準的な楽観的アルゴリズムは次元因子によって準最適であることを示す。
  論文  参考訳（メタデータ） (2021-07-09T16:04:24Z)
• Combinatorial Optimization with Physics-Inspired Graph Neural Networks [0.0]
  最適化問題の解法としてグラフニューラルネットワークを用いる方法を示す。 ニューラルネットワークは、既存の解法よりも優れているか、あるいは優れていることが分かりました。
  論文  参考訳（メタデータ） (2021-07-02T16:54:35Z)
• Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
  本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。 問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。 本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-01-07T08:00:02Z)
• 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)
• Channel Assignment in Uplink Wireless Communication using Machine Learning Approach [54.012791474906514]
  本稿では,アップリンク無線通信システムにおけるチャネル割り当て問題について検討する。 我々の目標は、整数チャネル割り当て制約を受ける全ユーザの総和率を最大化することです。 計算複雑性が高いため、機械学習アプローチは計算効率のよい解を得るために用いられる。
  論文  参考訳（メタデータ） (2020-01-12T15:54:20Z)

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

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