Research map / Graph learning / GNN architectures
On the Power of Small-size Graph Neural Networks for Linear Programming
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.
Proves that polylogarithmic-depth, constant-width GNNs can solve packing and covering LPs by unrolling a variant of Awerbuch-Khandekar gradient descent, and proposes GD-Net, which outperforms a GCN with far fewer parameters on synthetic LP benchmarks.
Problem
Theory predicts GNNs need large sizes to approximate LP solution mappings, yet small GNNs work well in practice; the paper asks when and why small GNNs can solve LPs.
Approach
A variant of the Awerbuch-Khandekar gradient descent for packing/covering LPs is simulated layer by layer by a GNN with learnable sigmoid-based step-function replacements, giving GD-Net with constant width and polylogarithmic depth.
Key results
- GD-Net with 1,656 parameters achieves relative gaps such as 4.41% on IS-S versus 15.46% for a 34,306-parameter GCN.
- On Set Covering and Packing, GD-Net beats Gurobi and PDLP in time to reach the same objective quality, by up to about 300x versus Gurobi simplex on SC-10,000.
- GD-Nets trained on smaller instances generalize to 10% larger instances with only minimal degradation.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use GD-Net instead of GCN | IS · IS S/M/L | relative gap: 15.46% -> 4.41%; 16.18% -> 3.55%; 15.35% -> 6.84% | Helped |
| use GD-Net instead of GCN | Packing · Packing S/M/L | relative gap: 19.50% -> 16.53%; 10.69% -> 10.68%; 7.37% -> 7.35% | Helped |
| use GD-Net instead of GCN | ECP · ECP S/M/L | relative gap: 36.83% -> 7.84%; 38.73% -> 21.51%; 39.22% -> 18.28% | Helped |
| use GD-Net instead of GCN | SC · SC S/M/L | relative gap: 21.91% -> 26.68%; 10.91% -> 13.09%; 8.90% -> 8.42% | Mixed |
| use GD-Net instead of Gurobi | SC · SC 1,000 variables | inference time: 0.244s -> 0.105s | Helped |
| use GD-Net instead of PDLP | SC · SC 1,000 variables | inference time: 0.919s -> 0.105s | Helped |
| use GD-Net instead of Gurobi | Packing · Packing 5,000 variables | inference time: 3.980s -> 0.216s | Helped |
Surprising findings
- On some Packing and SC instances GD-Net has higher relative gaps than GCN (e.g., SC-S 26.68% vs 21.91%), and on Packing-L it has higher test error yet a better gap.
Limitations
- Theory covers only packing and covering LPs in normal form, not general LPs.
- No error bars reported because experiments were expensive to repeat.
- Theoretical depth is polylogarithmic with large constants, and the gap between theory and empirical small size remains open.
Experimental setup
Datasets: Maximum Independent Set instances generated with Ecole Packing LP instances (random, 60% density) Edge Covering instances derived from IS Set Covering instances (random, 60% density) Bipartite Maxflow instances
Benchmarks: IS Packing ECP SC Bipartite Maxflow
Metrics: relative gap absolute gap validation MSE test MSE inference time
Baselines: GCN (Qian et al. 2023) Gurobi primal simplex PDLP Ford-Fulkerson
Builds on: Awerbuch and Khandekar packing/covering algorithm GCN Gasse et al. bipartite GNN formulation (Ecole)
Closest papers by meaning
- Expressive Power of Graph Neural Networks for (Mixed-Integer) Quadratic Programs (ICML 2025 · similarity 0.91)
- Learning Initial Basis Selection for Linear Programming via Duality-Inspired Tripartite Graph Representation and Comprehensive Supervision (ICML 2025 · similarity 0.91)
- Rethinking the Capacity of Graph Neural Networks for Branching Strategy (NeurIPS 2024 · similarity 0.90)
- Are Graph Neural Networks Optimal Approximation Algorithms? (NeurIPS 2024 · similarity 0.88)
- PDHG-Unrolled Learning-to-Optimize Method for Large-Scale Linear Programming (ICML 2024 · similarity 0.88)
- DOGE-Train: Discrete Optimization on GPU with End-to-End Training (AAAI 2024 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.