論文の概要: Expressive Power of Graph Neural Networks for (Mixed-Integer) Quadratic Programs

• arxiv url: http://arxiv.org/abs/2406.05938v1
• Date: Sun, 9 Jun 2024 23:57:47 GMT
• ステータス: 処理完了
• システム内更新日: 2024-06-11 15:25:59.264570
• Title: Expressive Power of Graph Neural Networks for (Mixed-Integer) Quadratic Programs
• Title（参考訳）: 混合整数)擬似プログラムのためのグラフニューラルネットワークの表現力
• Authors: Ziang Chen, Xiaohan Chen, Jialin Liu, Xinshang Wang, Wotao Yin,
• Abstract要約: 二次計画法 (QP) は非線形計画法において最も広く適用されている分野である。 QPタスクにグラフニューラルネットワーク(GNN)を適用する最近の研究は、GNNが最適化インスタンスの重要な特徴を捉えることができることを示している。 本稿では,2次プログラムの重要な特性を確実に表現できるメッセージパスGNNの存在を実証する。
• 参考スコア（独自算出の注目度）: 40.99368410911088
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Quadratic programming (QP) is the most widely applied category of problems in nonlinear programming. Many applications require real-time/fast solutions, though not necessarily with high precision. Existing methods either involve matrix decomposition or use the preconditioned conjugate gradient method. For relatively large instances, these methods cannot achieve the real-time requirement unless there is an effective precondition. Recently, graph neural networks (GNNs) opened new possibilities for QP. Some promising empirical studies of applying GNNs for QP tasks show that GNNs can capture key characteristics of an optimization instance and provide adaptive guidance accordingly to crucial configurations during the solving process, or directly provide an approximate solution. Despite notable empirical observations, theoretical foundations are still lacking. In this work, we investigate the expressive or representative power of GNNs, a crucial aspect of neural network theory, specifically in the context of QP tasks, with both continuous and mixed-integer settings. We prove the existence of message-passing GNNs that can reliably represent key properties of quadratic programs, including feasibility, optimal objective value, and optimal solution. Our theory is validated by numerical results.
• Abstract（参考訳）: 二次計画法 (QP) は非線形計画法において最も広く適用されている分野である。 多くのアプリケーションはリアルタイム/高速な解を必要とするが、必ずしも高精度であるとは限らない。 既存の方法は行列分解を含むか、事前条件付き共役勾配法を用いる。 比較的大規模なインスタンスの場合、これらのメソッドは効果的な前提条件がなければリアルタイムの要求を達成できない。 最近、グラフニューラルネットワーク(GNN)がQPの新しい可能性を公開した。 QPタスクにGNNを適用するための有望な実証研究は、GNNが最適化インスタンスの重要な特徴を捉え、問題解決プロセスにおける重要な構成に応じて適応的なガイダンスを提供するか、あるいは近似したソリューションを直接提供できることを示している。 顕著な経験的観察にもかかわらず、理論的な基礎はいまだに欠落している。 本研究では、ニューラルネットワーク理論の重要な側面であるGNNの表現力や代表力について、特にQPタスクの文脈において、連続的および混合的設定の両方で検討する。 本稿では,2次プログラムの重要な特性,実現可能性,最適目的値,最適解を確実に表現できるメッセージパスGNNの存在を実証する。 私たちの理論は数値的な結果によって検証される。

関連論文リスト

• Enhancing GNNs Performance on Combinatorial Optimization by Recurrent Feature Update [0.09986418756990156]
  本稿では,組合せ最適化(CO)問題を効率よく解くために,GNNのパワーを活用して,QRF-GNNと呼ぶ新しいアルゴリズムを提案する。 QUBO緩和による損失関数の最小化による教師なし学習に依存している。 実験の結果、QRF-GNNは既存の学習ベースアプローチを大幅に上回り、最先端の手法に匹敵することがわかった。
  論文  参考訳（メタデータ） (2024-07-23T13:34:35Z)
• QVIP: An ILP-based Formal Verification Approach for Quantized Neural Networks [14.766917269393865]
  量子化は、浮動小数点数に匹敵する精度でニューラルネットワークのサイズを減らすための有望な技術として登場した。 そこで本研究では,QNNに対する新しい,効率的な形式検証手法を提案する。 特に、QNNの検証問題を整数線形制約の解法に還元する符号化を初めて提案する。
  論文  参考訳（メタデータ） (2022-12-10T03:00:29Z)
• GNN at the Edge: Cost-Efficient Graph Neural Network Processing over Distributed Edge Servers [24.109721494781592]
  グラフニューラルネットワーク(GNN)はまだ探索中であり、その広範な採用に対する大きな違いを示している。 本稿では,多層ヘテロジニアスエッジネットワーク上での分散GNN処理のコスト最適化について検討する。 提案手法は, 高速収束速度で95.8%以上のコスト削減を行い, デファクトベースラインよりも優れた性能が得られることを示す。
  論文  参考訳（メタデータ） (2022-10-31T13:03: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)
• On Representing Linear Programs by Graph Neural Networks [30.998508318941017]
  グラフニューラルネットワーク(GNN)は最適化問題に適した機械学習モデルであると考えられている。 本稿では,線形プログラム(LP)問題にGNNを適用する理論的基礎を確立する。 適切に構築されたGNNは、幅広いクラスにおける各LPに対して、実現可能性、有界性、最適解を確実に予測できることを示す。
  論文  参考訳（メタデータ） (2022-09-25T18:27:33Z)
• Learning to Detect Critical Nodes in Sparse Graphs via Feature Importance Awareness [53.351863569314794]
  クリティカルノード問題(CNP)は、削除が残余ネットワークのペア接続性を最大に低下させるネットワークから臨界ノードの集合を見つけることを目的としている。 本研究は,ノード表現のための特徴重要度対応グラフアテンションネットワークを提案する。 ダブルディープQネットワークと組み合わせて、初めてCNPを解くエンドツーエンドのアルゴリズムを作成する。
  論文  参考訳（メタデータ） (2021-12-03T14:23:05Z)
• dNNsolve: an efficient NN-based PDE solver [62.997667081978825]
  ODE/PDEを解決するためにデュアルニューラルネットワークを利用するdNNsolveを紹介します。 我々は,dNNsolveが1,2,3次元の幅広いODE/PDEを解くことができることを示す。
  論文  参考訳（メタデータ） (2021-03-15T19:14:41Z)
• How Neural Networks Extrapolate: From Feedforward to Graph Neural Networks [80.55378250013496]
  勾配勾配降下法によりトレーニングされたニューラルネットワークが、トレーニング分布の支持の外で学んだことを外挿する方法について検討する。 グラフニューラルネットワーク(GNN)は、より複雑なタスクでいくつかの成功を収めている。
  論文  参考訳（メタデータ） (2020-09-24T17:48:59Z)
• Optimization and Generalization Analysis of Transduction through Gradient Boosting and Application to Multi-scale Graph Neural Networks [60.22494363676747]
  現在のグラフニューラルネットワーク(GNN)は、オーバースムーシング(over-smoothing)と呼ばれる問題のため、自分自身を深くするのは難しいことが知られている。 マルチスケールGNNは、オーバースムーシング問題を緩和するための有望なアプローチである。 マルチスケールGNNを含むトランスダクティブ学習アルゴリズムの最適化と一般化を保証する。
  論文  参考訳（メタデータ） (2020-06-15T17:06:17Z)
• Towards an Efficient and General Framework of Robust Training for Graph Neural Networks [96.93500886136532]
  グラフニューラルネットワーク(GNN)は、いくつかの基本的な推論タスクに大きく進歩している。 GNNの目覚ましい性能にもかかわらず、グラフ構造上の摂動を慎重に作り、誤った予測を下すことが観察されている。 我々は,強靭なGNNを得るために,欲求探索アルゴリズムとゼロ階法を利用する汎用フレームワークを提案する。
  論文  参考訳（メタデータ） (2020-02-25T15:17:58Z)

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

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