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

• arxiv url: http://arxiv.org/abs/2402.07099v1
• Date: Sun, 11 Feb 2024 04:09:50 GMT
• ステータス: 処理完了
• システム内更新日: 2024-02-13 17:30:05.383975
• 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)の特性や性質を予測するために広く用いられている。 本稿では,GNNの高次分岐(SB)スコアの表現能力について検討し,分岐とバウンドのアルゴリズムにおける効率的な戦略を提案する。
• 参考スコア（独自算出の注目度）: 43.97990814066709
• 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) scores that provide an efficient strategy in the branch-and-bound algorithm. Although message-passing GNN (MP-GNN), as the simplest GNN structure, is frequently employed in the existing literature to learn SB scores, we prove a fundamental limitation in its expressive power -- there exist two MILP instances with different SB scores that cannot be distinguished by any MP-GNN, regardless of the number of parameters. In addition, we establish a universal approximation theorem for another GNN structure called the second-order folklore GNN (2-FGNN). We show that for any data distribution over MILPs, there always exists a 2-FGNN that can approximate the SB score with arbitrarily high accuracy and arbitrarily high probability. A small-scale numerical experiment is conducted to directly validate our theoretical findings.
• Abstract（参考訳）: グラフニューラルネットワーク(GNN)は、混合整数線形プログラム(MILP)の特性とヒューリスティックを予測し、MILPソルバを加速するために広く用いられている。 本稿では,GNNの高次分岐(SB)スコアの表現能力について検討し,分岐とバウンドのアルゴリズムにおける効率的な戦略を提案する。 最も単純なGNN構造であるメッセージパスGNN(MP-GNN)は、既存の文献においてSBスコアを学習するために頻繁に使用されるが、表現力の根本的な制限を証明している。 さらに,2階民話GNN (2-FGNN) と呼ばれる別のGNN構造に対する普遍近似定理を確立する。 我々は、MILP上の任意のデータ分布に対して、SBスコアを任意に高精度かつ任意に高い確率で近似できる2-FGNNが存在することを示す。 理論的な結果を直接検証するために,小規模数値実験を行った。

関連論文リスト

• 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)

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

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