論文の概要: Rethinking the Capacity of Graph Neural Networks for Branching Strategy

• arxiv url: http://arxiv.org/abs/2402.07099v2
• Date: Sat, 8 Jun 2024 22:44:02 GMT
• ステータス: 処理完了
• システム内更新日: 2024-06-12 01:43:22.592264
• Title: Rethinking the Capacity of Graph Neural Networks for Branching Strategy
• Title（参考訳）: グラフニューラルネットワークの分岐戦略における能力の再考
• Authors: Ziang Chen, Jialin Liu, Xiaohan Chen, Xinshang Wang, Wotao Yin,
• Abstract要約: グラフニューラルネットワーク(GNN)は、混合整数線形プログラム(MILP)の特性を予測するために広く利用されている。 本稿では,強い分岐(SB)を示すGNNの能力について検討する。 我々はMP-GNNがSBスコアを正確に近似できる「MP-tractable」MILPのクラスを定義する。
• 参考スコア（独自算出の注目度）: 40.99368410911088
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Graph neural networks (GNNs) have been widely used to predict properties and heuristics of mixed-integer linear programs (MILPs) and hence accelerate MILP solvers. This paper investigates the capacity of GNNs to represent strong branching (SB), the most effective yet computationally expensive heuristic employed in the branch-and-bound algorithm. In the literature, message-passing GNN (MP-GNN), as the simplest GNN structure, is frequently used as a fast approximation of SB and we find that not all MILPs's SB can be represented with MP-GNN. We precisely define a class of "MP-tractable" MILPs for which MP-GNNs can accurately approximate SB scores. Particularly, we establish a universal approximation theorem: for any data distribution over the MP-tractable class, there always exists an MP-GNN that can approximate the SB score with arbitrarily high accuracy and arbitrarily high probability, which lays a theoretical foundation of the existing works on imitating SB with MP-GNN. For MILPs without the MP-tractability, unfortunately, a similar result is impossible, which can be illustrated by two MILP instances with different SB scores that cannot be distinguished by any MP-GNN, regardless of the number of parameters. Recognizing this, we explore another GNN structure called the second-order folklore GNN (2-FGNN) that overcomes this limitation, and the aforementioned universal approximation theorem can be extended to the entire MILP space using 2-FGNN, regardless of the MP-tractability. A small-scale numerical experiment is conducted to directly validate our theoretical findings.
• Abstract（参考訳）: グラフニューラルネットワーク(GNN)は、混合整数線形プログラム(MILP)の特性とヒューリスティックを予測し、MILPソルバを加速するために広く用いられている。 本稿では, 分岐とバウンドのアルゴリズムにおいて最も効果的だが計算コストのかかるヒューリスティックである, 強い分岐(SB)を表すGNNの能力について検討する。 文献では、最も単純なGNN構造であるメッセージパッシングGNN(MP-GNN)がSBの高速近似として頻繁に使われており、全てのMILPのSBをMP-GNNで表すことはできない。 我々は、MP-GNNがSBスコアを正確に近似できる「MP-tractable」MILPのクラスを正確に定義する。 特に、我々は普遍近似定理を確立する:MP-tractable class上の任意のデータ分布に対して、常にMP-GNNが存在し、SBスコアを任意に高い精度と任意に高い確率で近似することができる。 MPトラクタビリティのないMILPでは、パラメータの数に関係なく、MP-GNNでは区別できない異なるSBスコアを持つ2つのMILPインスタンスで、同様の結果を示すことは不可能である。 これを認識し、この制限を克服する二階民話GNN (2-FGNN) と呼ばれる別のGNN構造を探索し、上記の普遍近似定理をMPトラクタビリティに関係なく2-FGNNを用いてMILP空間全体に拡張することができる。 理論的知見を直接的確証するために, 小型数値実験を行った。

関連論文リスト

• Sign is Not a Remedy: Multiset-to-Multiset Message Passing for Learning on Heterophilic Graphs [77.42221150848535]
  我々は、Multiset to Multiset GNN(M2M-GNN)と呼ばれる新しいメッセージパッシング機能を提案する。 M2M-GNNは上述のSMPの限界を効果的に緩和し, 比較性能が向上することを示した。
  論文  参考訳（メタデータ） (2024-05-31T07:39:22Z)
• How does over-squashing affect the power of GNNs? [39.52168593457813]
  グラフニューラルネットワーク(GNN)は、グラフ構造化データ上での機械学習のための最先端モデルである。 与えられた容量のMPNNがどのノード特徴の関数クラスを学習できるかを決定するための厳密な分析を提供する。 一対のノード間の十分な通信を保証するために、MPNNの容量は十分大きすぎることを証明する。
  論文  参考訳（メタデータ） (2023-06-06T11:15:53Z)
• On Neural Networks as Infinite Tree-Structured Probabilistic Graphical Models [47.91322568623835]
  本稿では,ニューラルネットワークに対応する無限木構造PGMを構築することにより,革新的な解を提案する。 我々の研究は、DNNが前方伝播中に、この代替のPGM構造において正確であるPGMの近似を実行することを明らかにした。
  論文  参考訳（メタデータ） (2023-05-27T21:32:28Z)
• Graph Neural Networks are Inherently Good Generalizers: Insights by Bridging GNNs and MLPs [71.93227401463199]
  本稿では、P(ropagational)MLPと呼ばれる中間モデルクラスを導入することにより、GNNの性能向上を本質的な能力に向ける。 PMLPは、トレーニングにおいてはるかに効率的でありながら、GNNと同等(あるいはそれ以上)に動作することを観察する。
  論文  参考訳（メタデータ） (2022-12-18T08:17:32Z)
• Boosting the Cycle Counting Power of Graph Neural Networks with I$^2$-GNNs [9.806910643086043]
  本稿では,各サブグラフ内のルートノードとその隣人に異なる識別子を割り当てることで,サブグラフMPNNを拡張するための2$-GNNを提案する。 2$-GNNsの識別力は、サブグラフMPNNよりも強く、3WLテストより部分的に強いことが示されている。 我々の知る限りでは、理論的な保証とともに6サイクルを数えられる最初の線形時間GNNモデルである。
  論文  参考訳（メタデータ） (2022-10-22T09:40:00Z)
• On Representing Mixed-Integer Linear Programs by Graph Neural Networks [30.998508318941017]
  混合整数線形プログラミング(MILP)は一般にNPハードであるが, 実用的MILPは過去20年間で約100倍の高速化を実現している。 しかし、全てのGNNが平等に扱うような、実現不可能で実現不可能なMILPが存在する。 我々は、MILPを展開可能なものに制限したり、ランダムな特徴を加えることで、MILPの実現可能性、最適目標値、最適解を所定の精度で確実に予測できるGNNが存在することを示す。
  論文  参考訳（メタデータ） (2022-10-19T17:56:07Z)
• Universal Deep GNNs: Rethinking Residual Connection in GNNs from a Path Decomposition Perspective for Preventing the Over-smoothing [50.242926616772515]
  近年の研究では、残りの結合を持つGNNが変性をわずかに遅らせていることが示されている。 本稿では,新しい経路分解の観点からの残差接続を有するGNNの前方・後方挙動について検討する。 コールドスタート適応残差接続(DRIVE)とフィードフォワードモジュールを備えたUniversal Deep GNNsフレームワークを提案する。
  論文  参考訳（メタデータ） (2022-05-30T14:19:45Z)
• From Stars to Subgraphs: Uplifting Any GNN with Local Structure Awareness [23.279464786779787]
  私たちはMPNNをより表現力のあるものにするための一般的なフレームワークを導入します。 私たちのフレームワークは1&2-WLよりも強力で、3WLよりも強力です。 本手法は,いくつかのよく知られたグラフMLタスクに対して,新たな最先端性能を大きなマージンで設定する。
  論文  参考訳（メタデータ） (2021-10-07T19:08:08Z)
• Efficient Probabilistic Logic Reasoning with Graph Neural Networks [63.099999467118245]
  マルコフ論理ネットワーク(MLN)は、多くの知識グラフ問題に対処するために用いられる。 MLNの推論は計算集約的であり、MLNの産業規模での応用は非常に困難である。 本稿では,表現力とモデルの単純さとのバランスのよいグラフニューラルネット(GNN)モデルであるExpressGNNを提案する。
  論文  参考訳（メタデータ） (2020-01-29T23:34:36Z)

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

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