Research map / Graph learning / GNN architectures

Rethinking the Capacity of Graph Neural Networks for Branching Strategy

NeurIPS 2024 · Graph learning › GNN architectures · approach: GNN generalization theory · 2 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Shows theoretically which MILPs' strong branching scores MP-GNNs can represent (MP-tractable class, universal approximation), that MP-GNNs fail beyond it via a counterexample, and that 2-FGNNs universally approximate SB scores.

Problem

Whether GNNs (MP-GNNs and higher-order 2-FGNNs) have the capacity to approximate strong branching (SB) scores for MILPs, which is the basis of learning-to-branch imitation methods.

Approach

Defines "MP-tractable" MILPs via WL color refinement (submatrices constant on color classes) and proves MP-GNNs universally approximate SB on this class; constructs two MP-intractable MILPs with different SB scores that MP-GNNs cannot distinguish; shows 2-FWL-equivalent (2-FGNN) separation suffices for universal approximation over all MILPs.

Key results

• MP-GNN and 2-FGNN both fit SB scores on 100 randomly generated MP-tractable MILPs (6x20), validating the theory.
• On the two MP-intractable MILPs, MP-GNN training error does not decrease regardless of parameter count, while 2-FGNN reaches near-zero error (e.g., 10^-12 with embedding size 1024 in ~1,128 epochs).
• An MP-GNN trained on 100 large set covering instances (1000 vars, 2000 constraints) reached training loss 1.94e-4.

Measured effects reported in the paper

Surprising findings

• Two small MILPs with different SB scores (all-zero vs. 1/4 on six variables) are indistinguishable by every MP-GNN, so no amount of capacity fixes the error.

Limitations

• Existence results only; no quantitative bounds on the number of parameters or complexity needed for a given precision.
• 2-FGNNs are computationally more expensive than MP-GNNs in training and inference.
• Experiments are small-scale and only validate theory; training/generalization performance is deferred to future work.

Experimental setup

Datasets: randomly generated MILP instances (6x20, MP-tractable) two hand-constructed MP-intractable MILPs 100 large set covering instances (1000 vars, 2000 constraints) SB scores computed with SCIP

Metrics: training loss (sum of squared error to SB scores) epochs to reach error threshold

Baselines: MP-GNN

Builds on: Weisfeiler-Lehman test k-FWL / 2-FGNN (higher-order GNN) Gasse et al. bipartite MILP-graph representation Stone-Weierstrass theorem Lusin's theorem

Closest papers by meaning

• Hybrid Models for Learning to Branch (NeurIPS 2020 · similarity 0.92)
• On Representing Mixed-Integer Linear Programs by Graph Neural Networks (ICLR 2023 · similarity 0.91)
• Expressive Power of Graph Neural Networks for (Mixed-Integer) Quadratic Programs (ICML 2025 · similarity 0.90)
• On the Power of Small-size Graph Neural Networks for Linear Programming (NeurIPS 2024 · similarity 0.90)
• A GNN-Guided Predict-and-Search Framework for Mixed-Integer Linear Programming (ICLR 2023 · similarity 0.89)
• Are Graph Neural Networks Optimal Approximation Algorithms? (NeurIPS 2024 · similarity 0.89)