Research map / Graph learning / GNN architectures
Expressive Power of Graph Neural Networks for (Mixed-Integer) Quadratic Programs
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 message-passing GNNs universally represent feasibility, optimal objective and optimal solution of convex LCQPs via a WL-test separation argument, shows they fail for general MI-LCQPs, and identifies GNN-solvable/analyzable MI-LCQP subclasses where they succeed.
Problem
Whether GNNs can represent feasibility, optimal objective value, and optimal solutions of linearly constrained (mixed-integer) quadratic programs.
Approach
Uses a linear-form WL color-refinement test over a bipartite constraint-variable graph with a quadratic-term edge set to show that WL-indistinguishable convex LCQPs share optimal objective and minimum-norm optimal solution, giving universal approximation via Stone-Weierstrass; for MI-LCQP, defines GNN-solvable and GNN-analyzable subclasses where the approximation still holds.
Key results
- On 1,000 synthetic LCQPs, a trained GNN averaged relative error 6.31e-4 versus OSQP at relative error 1e-3, with GNN batch-1000 time 0.089 ms per instance versus OSQP 4.48 ms.
- GNNs fit optimal objective and solutions on randomly generated LCQP and MI-LCQP instances with relative error approaching zero for large embedding sizes.
- Two MI-LCQP instances with identical WL colors have disjoint optimal solution sets, so no GNN can represent them, showing GNNs are not universal for MI-LCQP.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Increase GNN batch size from 1 to 1,000 | GNN · Synthetic LCQP | average solving time (ms): 53.62±16.72 -> 0.089±0.002 | Helped |
| Increase embedding size | GNN · Synthetic LCQP and MI-LCQP | relative error | Helped |
| Increase the number of training samples to 500 or 2,500 | GNN · Synthetic LCQP and MI-LCQP | relative error | Helped |
| Increase embedding size | GNN · Maros and Meszaros Problem Set | training error | Helped |
| Increase embedding size | GNN · QPLib, 73 GNN-solvable MI-LCQP instances | training error | Helped |
Surprising findings
- GNNs cannot distinguish a pair of MI-LCQPs that differ in optimal solution, showing failure even with infinite capacity.
- Theorems fail without convexity: a convex and a nonconvex LCQP are indistinguishable by any GNN.
Limitations
- Only message-passing GNNs with continuous mappings analyzed; no training dynamics or generalization theory.
- GNN-solvable and GNN-analyzable conditions depend on symmetry; challenging QPLIB instances may be GNN-insolvable or inanalyzable.
- Numerical validation is limited to fitting training data; feasibility experiments omitted.
Experimental setup
Datasets: Maros-Meszaros problem set QPLIB
Benchmarks: Maros-Meszaros QPLIB
Metrics: relative error solving time (ms)
Baselines: OSQP
Builds on: Weisfeiler-Lehman test GNN expressive power theory (Xu et al.) MILP unfoldability
Closest papers by meaning
- On the Power of Small-size Graph Neural Networks for Linear Programming (NeurIPS 2024 · similarity 0.91)
- Principled Data Augmentation for Learning to Solve Quadratic Programming Problems (NeurIPS 2025 · similarity 0.90)
- 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)
- Learning Initial Basis Selection for Linear Programming via Duality-Inspired Tripartite Graph Representation and Comprehensive Supervision (ICML 2025 · similarity 0.88)
- Deep Distributed Optimization for Large-Scale Quadratic Programming (ICLR 2025 · similarity 0.88)
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.