論文の概要: Branching Strategies Based on Subgraph GNNs: A Study on Theoretical Promise versus Practical Reality

• arxiv url: http://arxiv.org/abs/2512.09355v1
• Date: Wed, 10 Dec 2025 06:29:25 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-12-11 15:14:53.416227
• Title: Branching Strategies Based on Subgraph GNNs: A Study on Theoretical Promise versus Practical Reality
• Title（参考訳）: サブグラフGNNに基づく分岐戦略:理論的約束と実践的現実に関する研究
• Authors: Junru Zhou, Yicheng Wang, Pan Li,
• Abstract要約: グラフニューラルネットワーク(GNN)は、MILP(Mixed-Integer Linear Programming)における'分岐学習のための有望なアプローチとして登場した。 本研究では,GNNを理論的中核として検討する。 以上の結果から,MILP分岐では,表現的GNNの計算コストが決定品質よりも高いことが示唆された。
• 参考スコア（独自算出の注目度）: 16.01902631233758
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Graph Neural Networks (GNNs) have emerged as a promising approach for ``learning to branch'' in Mixed-Integer Linear Programming (MILP). While standard Message-Passing GNNs (MPNNs) are efficient, they theoretically lack the expressive power to fully represent MILP structures. Conversely, higher-order GNNs (like 2-FGNNs) are expressive but computationally prohibitive. In this work, we investigate Subgraph GNNs as a theoretical middle ground. Crucially, while previous work [Chen et al., 2025] demonstrated that GNNs with 3-WL expressive power can approximate Strong Branching, we prove a sharper result: node-anchored Subgraph GNNs whose expressive power is strictly lower than 3-WL [Zhang et al., 2023] are sufficient to approximate Strong Branching scores. However, our extensive empirical evaluation on four benchmark datasets reveals a stark contrast between theory and practice. While node-anchored Subgraph GNNs theoretically offer superior branching decisions, their $O(n)$ complexity overhead results in significant memory bottlenecks and slower solving times than MPNNs and heuristics. Our results indicate that for MILP branching, the computational cost of expressive GNNs currently outweighs their gains in decision quality, suggesting that future research must focus on efficiency-preserving expressivity.
• Abstract（参考訳）: Graph Neural Networks (GNN) は、MILP(Mixed-Integer Linear Programming)における ''learning to branch'' の有望なアプローチとして登場した。 標準的なMPNN(Message-Passing GNN)は効率的だが、理論上はMILP構造を完全に表現する表現力に欠ける。 逆に、2-FGNNのような高階のGNNは表現力があるが、計算は禁じられている。 本研究では,GNNを理論的中核として検討する。 重要なことは、3WL の表現力を持つ GNN がStrong Branching を近似できることを示したのに対して、我々はよりシャープな結果を示した: 3WL (Zhang et al , 2023) よりも厳密な表現力を持つノードアンコールサブグラフ GNN はStrong Branching のスコアを近似するのに十分である。 しかし,4つのベンチマークデータセットに対する広範な実験評価により,理論と実践の対比が著しく高いことがわかった。 ノードアンコールされたサブグラフGNNは理論的には分岐決定に優れているが、O(n)$の複雑さのオーバーヘッドは、MPNNやヒューリスティックよりもメモリのボトルネックが大きくなり、解決時間が短縮される。 以上の結果から,MILP分岐の場合,現在,表現性GNNの計算コストは意思決定品質よりも高く,今後の研究は効率性に重点を置く必要があることが示唆された。

関連論文リスト

• Rethinking GNN Expressive Power from a Distributed Computational Model Perspective [29.47675861430167]
  事前処理と後処理を明確に指定した修正 CONGEST モデルなど,明確に定義された計算モデルを使用することによって,GNN 表現性を分析するためのより健全なフレームワークが提供される,と我々は主張する。 制約のない事前処理を許可したり、外部に計算された機能を組み込んだりすることは、これらの事前計算によって表現性が向上し、時には問題を引き起こす可能性があることを示す。 これらの否定的な結果にもかかわらず、計算モデルの観点から仮想ノードとエッジの効果を特徴付ける肯定的な結果も提示する。
  論文  参考訳（メタデータ） (2024-10-02T08:01:50Z)
• Rethinking the Capacity of Graph Neural Networks for Branching Strategy [40.99368410911088]
  グラフニューラルネットワーク(GNN)は、混合整数線形プログラム(MILP)の特性を予測するために広く利用されている。 本稿では,強い分岐(SB)を示すGNNの能力について検討する。 我々はMP-GNNがSBスコアを正確に近似できる「MP-tractable」MILPのクラスを定義する。
  論文  参考訳（メタデータ） (2024-02-11T04:09:50Z)
• MAG-GNN: Reinforcement Learning Boosted Graph Neural Network [68.60884768323739]
  特定の研究の行は、GNNの表現性を向上させるためにサブグラフ情報を使用するサブグラフGNNを提案し、大きな成功を収めた。 このような効果は、すべての可能な部分グラフを列挙することによって、GNNの効率を犠牲にする。 本稿では,強化学習(RL)により強化されたGNNである磁気グラフニューラルネットワーク(MAG-GNN)を提案する。
  論文  参考訳（メタデータ） (2023-10-29T20:32:21Z)
• An Efficient Subgraph GNN with Provable Substructure Counting Power [32.44487589958533]
  本稿では,グラフニューラルネットワーク(GNN)のサブストラクチャカウント能力による表現能力の向上について検討する。 近年の進歩では、入力グラフを多数のサブグラフに分割するサブグラフGNNが採用され、グラフ全体の表現を拡大するためにそれぞれにGNNが適用されるようになった。 様々なサブ構造を識別できるにもかかわらず、サブグラフGNNは計算とメモリの大幅なコストによって妨げられる。
  論文  参考訳（メタデータ） (2023-03-19T05:35:59Z)
• Rethinking the Expressive Power of GNNs via Graph Biconnectivity [45.4674360883544]
  本稿では,グラフ双連結性による表現度指標の新たなクラスを導入し,理論と実践の両面での重要性を強調した。 我々は、GD-WL(Generalized Distance Weisfeiler-Lehman)と呼ばれる原理的で効率的なアプローチを導入する。 実際に,GD-WLをTransformerのようなアーキテクチャで実装し,完全な並列化性を保ち,実現可能であることを示す。
  論文  参考訳（メタデータ） (2023-01-23T15:58:59Z)
• Representation Power of Graph Neural Networks: Improved Expressivity via Algebraic Analysis [124.97061497512804]
  標準グラフニューラルネットワーク (GNN) はWeisfeiler-Lehman (WL) アルゴリズムよりも差別的な表現を生成する。 また、白い入力を持つ単純な畳み込みアーキテクチャは、グラフの閉経路をカウントする同変の特徴を生じさせることを示した。
  論文  参考訳（メタデータ） (2022-05-19T18:40:25Z)
• Optimization of Graph Neural Networks: Implicit Acceleration by Skip Connections and More Depth [57.10183643449905]
  グラフニューラルネットワーク(GNN)は表現力と一般化のレンズから研究されている。 GNNのダイナミクスを深部スキップ最適化により研究する。 本研究は,GNNの成功に対する最初の理論的支援を提供する。
  論文  参考訳（メタデータ） (2021-05-10T17:59:01Z)
• 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)
• Expressive Power of Invariant and Equivariant Graph Neural Networks [10.419350129060598]
  Folklore Graph Neural Networks (FGNN) は、与えられたテンソル次数に対してこれまで提案されてきた最も表現力のあるアーキテクチャである。 FGNNはこの問題の解決方法を学ぶことができ、既存のアルゴリズムよりも平均的なパフォーマンスが向上する。
  論文  参考訳（メタデータ） (2020-06-28T16:35:45Z)
• 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)

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

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