論文の概要: 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空間全体に拡張することができる。 理論的知見を直接的確証するために, 小型数値実験を行った。

関連論文リスト

• FSW-GNN: A Bi-Lipschitz WL-Equivalent Graph Neural Network [2.766564215769441]
  グラフを区別するMPNNの能力は、Weisfeiler-Lemann (WL) グラフ同型テストによって分離できるグラフに限られる。 我々のMPNNは、いくつかのグラフ学習タスクで標準的なMPNNと競合し、過度な長距離タスクでははるかに正確であることを示す。
  論文  参考訳（メタデータ） (2024-10-10T18:11:23Z)
• 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)
• 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)
• 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)
• Permutation-equivariant and Proximity-aware Graph Neural Networks with Stochastic Message Passing [88.30867628592112]
  グラフニューラルネットワーク(GNN)は、グラフ上の新たな機械学習モデルである。 置換等価性と近接認識性は、GNNにとって非常に望ましい2つの重要な特性である。 既存のGNNは、主にメッセージパッシング機構に基づいており、同時に2つの特性を保存できないことを示す。 ノードの近さを保つため,既存のGNNをノード表現で拡張する。
  論文  参考訳（メタデータ） (2020-09-05T16:46:56Z)
• Efficient Probabilistic Logic Reasoning with Graph Neural Networks [63.099999467118245]
  マルコフ論理ネットワーク(MLN)は、多くの知識グラフ問題に対処するために用いられる。 MLNの推論は計算集約的であり、MLNの産業規模での応用は非常に困難である。 本稿では,表現力とモデルの単純さとのバランスのよいグラフニューラルネット(GNN)モデルであるExpressGNNを提案する。
  論文  参考訳（メタデータ） (2020-01-29T23:34:36Z)

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

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