論文の概要: 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が存在することを示す。
理論的な結果を直接検証するために,小規模数値実験を行った。
関連論文リスト
- 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) - Neural Network Branch-and-Bound for Neural Network Verification [26.609606492971967]
本稿では,効率的な分岐戦略を設計するための新しい機械学習フレームワークを提案する。
グラフ入力として検証したいネットワークを直接扱う2つのグラフニューラルネットワーク(GNN)を学習する。
我々のGNNモデルは、より大きな未確認ネットワーク上での厳しい特性に対してよく一般化されていることを示す。
論文 参考訳(メタデータ) (2021-07-27T14:42:57Z) - Learning Graph Neural Networks with Approximate Gradient Descent [24.49427608361397]
ラベルがノードまたはグラフに添付されているかどうかに応じて、2種類のグラフニューラルネットワーク(GNN)が調査されます。
gnnトレーニングアルゴリズムの設計と解析のための包括的なフレームワークを開発した。
提案アルゴリズムは,GNNの根底にある真のパラメータに対する線形収束率を保証する。
論文 参考訳(メタデータ) (2020-12-07T02:54:48Z) - The Surprising Power of Graph Neural Networks with Random Node
Initialization [54.4101931234922]
グラフニューラルネットワーク(GNN)は、関係データ上での表現学習に有効なモデルである。
標準 GNN はその表現力に制限があり、Weisfeiler-Leman グラフ同型(英語版)の能力以外の区別はできない。
本研究では,ランダムノード(RNI)を用いたGNNの表現力の解析を行う。
我々はこれらのモデルが普遍的であることを証明し、GNNが高次特性の計算に頼らない最初の結果である。
論文 参考訳(メタデータ) (2020-10-02T19:53:05Z) - Distance Encoding: Design Provably More Powerful Neural Networks for
Graph Representation Learning [63.97983530843762]
グラフニューラルネットワーク(GNN)はグラフ表現学習において大きな成功を収めている。
GNNは、実際には非常に異なるグラフ部分構造に対して同一の表現を生成する。
より強力なGNNは、最近高階試験を模倣して提案され、基礎となるグラフ構造を疎結合にできないため、非効率である。
本稿では,グラフ表現学習の新たなクラスとして距離分解(DE)を提案する。
論文 参考訳(メタデータ) (2020-08-31T23:15:40Z) - Global Attention Improves Graph Networks Generalization [30.134738629447927]
本稿では,低ランクグローバルアテンション(LRGA)モジュールをグラフニューラルネットワーク(GNN)に導入することを提唱する。
表現型GNNの特定のファミリーに着目し、LRGAで拡張することで、強力なグラフ同型テストへのアルゴリズム的アライメントが得られることを示す。
現実的な観点からは、既存のGNNレイヤをLRGAで拡張することで、現在のGNNベンチマークにおける技術結果の状態を生成できる。
論文 参考訳(メタデータ) (2020-06-14T09:01:57Z) - Binarized Graph Neural Network [65.20589262811677]
我々は二項化グラフニューラルネットワークを開発し、二項化ネットワークパラメータを用いてノードのバイナリ表現を学習する。
提案手法は既存のGNNベースの埋め込み手法にシームレスに統合できる。
実験により、提案された二項化グラフニューラルネットワーク、すなわちBGNは、時間と空間の両方の観点から、桁違いに効率的であることが示されている。
論文 参考訳(メタデータ) (2020-04-19T09:43:14Z) - Generalization and Representational Limits of Graph Neural Networks [46.20253808402385]
ローカル情報に完全に依存するグラフニューラルネットワーク(GNN)では,いくつかの重要なグラフ特性を計算できないことを示す。
メッセージパッシングGNNに対する最初のデータ依存一般化境界を提供する。
私たちのバウンダリは、既存のVC次元ベースのGNN保証よりもはるかに厳格で、リカレントニューラルネットワークのRademacherバウンダリと同等です。
論文 参考訳(メタデータ) (2020-02-14T18:10:14Z) - Efficient Probabilistic Logic Reasoning with Graph Neural Networks [63.099999467118245]
マルコフ論理ネットワーク(MLN)は、多くの知識グラフ問題に対処するために用いられる。
MLNの推論は計算集約的であり、MLNの産業規模での応用は非常に困難である。
本稿では,表現力とモデルの単純さとのバランスのよいグラフニューラルネット(GNN)モデルであるExpressGNNを提案する。
論文 参考訳(メタデータ) (2020-01-29T23:34:36Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。