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

• arxiv url: http://arxiv.org/abs/2406.05938v2
• Date: Sun, 21 Sep 2025 19:20:40 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-09-23 18:58:15.59021
• 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) は非線形計画法において最も広く適用されている分野である。 最近、グラフニューラルネットワーク(GNN)がQPの新しい可能性を公開した。 理論上、GNNがQPタスクに対して何を達成でき、達成できないのかは不明だ。
• 参考スコア（独自算出の注目度）: 35.70023437238074
• 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 preconditioner. 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. However, the theoretical understanding of GNNs in this context remains limited. Specifically, it is unclear what GNNs can and cannot achieve for QP tasks in theory. This work addresses this gap in the context of linearly constrained QP tasks. In the continuous setting, we prove that message-passing GNNs can universally represent fundamental properties of convex quadratic programs, including feasibility, optimal objective values, and optimal solutions. In the more challenging mixed-integer setting, while GNNs are not universal approximators, we identify a subclass of QP problems that GNNs can reliably represent.
• Abstract（参考訳）: 二次計画法 (QP) は非線形計画法において最も広く適用されている分野である。 多くのアプリケーションはリアルタイム/高速な解を必要とするが、必ずしも高精度であるとは限らない。 既存の方法は行列分解を含むか、事前条件付き共役勾配法を用いる。 比較的大規模なインスタンスの場合、これらのメソッドは実効的なプレコンディショナーがなければリアルタイムの要求を達成できない。 最近、グラフニューラルネットワーク(GNN)がQPの新しい可能性を公開した。 QPタスクにGNNを適用するための有望な実証研究は、GNNが最適化インスタンスの重要な特徴を捉え、問題解決プロセスにおける重要な構成に応じて適応的なガイダンスを提供するか、あるいは近似したソリューションを直接提供できることを示している。 しかし、この文脈におけるGNNの理論的理解は依然として限られている。 具体的には、理論上、GNNがQPタスクに対して何が可能であり、達成できないのかは不明確である。 この研究は、線形に制約されたQPタスクの文脈におけるこのギャップに対処する。 連続的な設定では、メッセージパスGNNは、実現可能性、最適目的値、最適解を含む凸二次プログラムの基本特性を普遍的に表現できることを示す。 より困難な混合整数設定では、GNNは普遍的な近似子ではないが、GNNが確実に表現できるQP問題のサブクラスを特定する。

関連論文リスト

• Partially-Supervised Neural Network Model For Quadratic Multiparametric Programming [2.765106384328772]
  本研究では,大域的解関数の数学的構造を直接表現する部分教師付きNNアーキテクチャを提案する。 汎用的なNNトレーニング手法とは対照的に,PSNN法は最適化問題の数学的性質から直接モデル重みを導出する。
  論文  参考訳（メタデータ） (2025-06-05T20:26:18Z)
• Rethinking GNN Expressive Power from a Distributed Computational Model Perspective [21.723600297533835]
  事前処理と後処理を明確に指定した修正 CONGEST モデルなど,明確に定義された計算モデルを使用することによって,GNN 表現性を分析するためのより健全なフレームワークが提供される,と我々は主張する。 制約のない事前処理を許可したり、外部に計算された機能を組み込んだりすることは、これらの事前計算によって表現性が向上し、時には問題を引き起こす可能性があることを示す。 これらの否定的な結果にもかかわらず、計算モデルの観点から仮想ノードとエッジの効果を特徴付ける肯定的な結果も提示する。
  論文  参考訳（メタデータ） (2024-10-02T08:01:50Z)
• 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)

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

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