Branching Strategies Based on Subgraph GNNs: A Study on Theoretical Promise versus Practical Reality

• URL: http://arxiv.org/abs/2512.09355v1
• Date: Wed, 10 Dec 2025 06:29:25 GMT
• Title: Branching Strategies Based on Subgraph GNNs: A Study on Theoretical Promise versus Practical Reality
• Authors: Junru Zhou, Yicheng Wang, Pan Li,
• Abstract summary: Graph Neural Networks (GNNs) have emerged as a promising approach for learning to branch'' in Mixed-Integer Linear Programming (MILP)<n>In this work, we investigate Subgraph GNNs as a theoretical middle ground.<n>Our results indicate that for MILP branching, the computational cost of expressive GNNs currently outweighs their gains in decision quality.
• Score: 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.

Related papers

• Rethinking GNN Expressive Power from a Distributed Computational Model Perspective [29.47675861430167]
  We argue that using well-defined computational models, such as a modified CONGEST model with clearly specified preprocessing and postprocessing, offers a more sound framework for analyzing GNN expressiveness.<n>We show that allowing unrestricted preprocessing or incorporating externally computed features, while claiming that these precomputations enhance the expressiveness, can sometimes lead to problems.<n>Despite these negative results, we also present positive results that characterize the effects of virtual nodes and edges from a computational model perspective.
  arXiv  Detail & Related papers  (2024-10-02T08:01:50Z)
• Rethinking the Capacity of Graph Neural Networks for Branching Strategy [40.99368410911088]
  Graph neural networks (GNNs) have been widely used to predict properties of mixed-integer linear programs (MILPs)<n>This paper investigates the capacity of GNNs to represent strong branching (SB)<n>We define a class of "MP-tractable" MILPs for which MP-GNNs can accurately approximate SB scores.
  arXiv  Detail & Related papers  (2024-02-11T04:09:50Z)
• MAG-GNN: Reinforcement Learning Boosted Graph Neural Network [68.60884768323739]
  A particular line of work proposed subgraph GNNs that use subgraph information to improve GNNs' expressivity and achieved great success. Such effectivity sacrifices the efficiency of GNNs by enumerating all possible subgraphs. We propose Magnetic Graph Neural Network (MAG-GNN), a reinforcement learning (RL) boosted GNN, to solve the problem.
  arXiv  Detail & Related papers  (2023-10-29T20:32:21Z)
• An Efficient Subgraph GNN with Provable Substructure Counting Power [32.44487589958533]
  We investigate the enhancement of graph neural networks' (GNNs) representation power through their ability in substructure counting. Recent advances have seen the adoption of subgraph GNNs, which partition an input graph into numerous subgraphs, subsequently applying GNNs to each to augment the graph's overall representation. Despite their ability to identify various substructures, subgraph GNNs are hindered by significant computational and memory costs.
  arXiv  Detail & Related papers  (2023-03-19T05:35:59Z)
• Rethinking the Expressive Power of GNNs via Graph Biconnectivity [45.4674360883544]
  We introduce a novel class of expressivity metrics via graph biconnectivity and highlight their importance in both theory and practice. We introduce a principled and more efficient approach, called the Generalized Distance Weisfeiler-Lehman (GD-WL) Practically, we show GD-WL can be implemented by a Transformer-like architecture that preserves and enjoys full parallelizability.
  arXiv  Detail & Related papers  (2023-01-23T15:58:59Z)
• Graph Neural Networks are Inherently Good Generalizers: Insights by Bridging GNNs and MLPs [71.93227401463199]
  This paper pinpoints the major source of GNNs' performance gain to their intrinsic capability, by introducing an intermediate model class dubbed as P(ropagational)MLP. We observe that PMLPs consistently perform on par with (or even exceed) their GNN counterparts, while being much more efficient in training.
  arXiv  Detail & Related papers  (2022-12-18T08:17:32Z)
• Boosting the Cycle Counting Power of Graph Neural Networks with I$^2$-GNNs [9.806910643086043]
  We propose I$2$-GNNs to extend Subgraph MPNNs by assigning different identifiers for the root node and its neighbors in each subgraph. I$2$-GNNs' discriminative power is shown to be strictly stronger than Subgraph MPNNs and partially stronger than the 3-WL test. To the best of our knowledge, it is the first linear-time GNN model that can count 6-cycles with theoretical guarantees.
  arXiv  Detail & Related papers  (2022-10-22T09:40:00Z)
• Representation Power of Graph Neural Networks: Improved Expressivity via Algebraic Analysis [124.97061497512804]
  We show that standard Graph Neural Networks (GNNs) produce more discriminative representations than the Weisfeiler-Lehman (WL) algorithm. We also show that simple convolutional architectures with white inputs, produce equivariant features that count the closed paths in the graph.
  arXiv  Detail & Related papers  (2022-05-19T18:40:25Z)
• From Stars to Subgraphs: Uplifting Any GNN with Local Structure Awareness [23.279464786779787]
  We introduce a general framework to uplift any MPNN to be more expressive. Our framework is strictly more powerful than 1&2-WL, and is not less powerful than 3-WL. Our method sets new state-of-the-art performance by large margins for several well-known graph ML tasks.
  arXiv  Detail & Related papers  (2021-10-07T19:08:08Z)
• Optimization of Graph Neural Networks: Implicit Acceleration by Skip Connections and More Depth [57.10183643449905]
  Graph Neural Networks (GNNs) have been studied from the lens of expressive power and generalization. We study the dynamics of GNNs by studying deep skip optimization. Our results provide first theoretical support for the success of GNNs.
  arXiv  Detail & Related papers  (2021-05-10T17:59:01Z)
• The Surprising Power of Graph Neural Networks with Random Node Initialization [54.4101931234922]
  Graph neural networks (GNNs) are effective models for representation learning on relational data. Standard GNNs are limited in their expressive power, as they cannot distinguish beyond the capability of the Weisfeiler-Leman graph isomorphism. In this work, we analyze the expressive power of GNNs with random node (RNI) We prove that these models are universal, a first such result for GNNs not relying on computationally demanding higher-order properties.
  arXiv  Detail & Related papers  (2020-10-02T19:53:05Z)
• Distance Encoding: Design Provably More Powerful Neural Networks for Graph Representation Learning [63.97983530843762]
  Graph Neural Networks (GNNs) have achieved great success in graph representation learning. GNNs generate identical representations for graph substructures that may in fact be very different. More powerful GNNs, proposed recently by mimicking higher-order tests, are inefficient as they cannot sparsity of underlying graph structure. We propose Distance Depiction (DE) as a new class of graph representation learning.
  arXiv  Detail & Related papers  (2020-08-31T23:15:40Z)
• Expressive Power of Invariant and Equivariant Graph Neural Networks [10.419350129060598]
  We show that Folklore Graph Neural Networks (FGNN) are the most expressive architectures proposed so far for a given tensor order. FGNNs are able to learn how to solve the problem, leading to much better average performances than existing algorithms.
  arXiv  Detail & Related papers  (2020-06-28T16:35:45Z)
• Optimization and Generalization Analysis of Transduction through Gradient Boosting and Application to Multi-scale Graph Neural Networks [60.22494363676747]
  It is known that the current graph neural networks (GNNs) are difficult to make themselves deep due to the problem known as over-smoothing. Multi-scale GNNs are a promising approach for mitigating the over-smoothing problem. We derive the optimization and generalization guarantees of transductive learning algorithms that include multi-scale GNNs.
  arXiv  Detail & Related papers  (2020-06-15T17:06:17Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.