# Expressive Power of Graph Neural Networks for (Mixed-Integer) Quadratic Programs

arXiv: https://arxiv.org/abs/2406.05938 · HTML: https://mlsanity.com/paper/2406.05938/

## Key facts

- Cited by 16 papers in the map (data through 14 Oct 2026).
- Builds on 38 of its 69 references that are in the map.
- First posted on arXiv 9 Jun 2024.

## Builds on (most cited first, 30 of 38)

- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networks](https://mlsanity.com/paper/1810.02244/) (2018)
- [Exact Combinatorial Optimization with Graph Convolutional Neural Networks](https://mlsanity.com/paper/1906.01629/) (2019)
- [Random Features Strengthen Graph Neural Networks](https://mlsanity.com/paper/2002.03155/) (2020)
- [Solving Mixed Integer Programs Using Neural Networks](https://mlsanity.com/paper/2012.13349/) (2020)
- [OSQP: An Operator Splitting Solver for Quadratic Programs](https://mlsanity.com/paper/1711.08013/) (2017)
- [A Survey on The Expressive Power of Graph Neural Networks](https://mlsanity.com/paper/2003.04078/) (2020)
- [Expressive Power of Invariant and Equivariant Graph Neural Networks](https://mlsanity.com/paper/2006.15646/) (2020)
- [Learning Combinatorial Embedding Networks for Deep Graph Matching](https://mlsanity.com/paper/1904.00597/) (2019)
- [Hybrid Models for Learning to Branch](https://mlsanity.com/paper/2006.15212/) (2020)
- [How Powerful are K-hop Message Passing Graph Neural Networks](https://mlsanity.com/paper/2205.13328/) (2022)
- [Neural Graph Matching Network: Learning Lawler's Quadratic Assignment Problem with Extension to Hypergraph and Multiple-graph Matching](https://mlsanity.com/paper/1911.11308/) (2019)
- [Expressiveness and Approximation Properties of Graph Neural Networks](https://mlsanity.com/paper/2204.04661/) (2022)
- [Learning To Cut By Looking Ahead: Cutting Plane Selection via Imitation Learning](https://mlsanity.com/paper/2206.13414/) (2022)
- [Efficient representation and approximation of model predictive control laws via deep learning](https://mlsanity.com/paper/1806.10644/) (2018)
- [MIP-GNN: A Data-Driven Framework for Guiding Combinatorial Solvers](https://mlsanity.com/paper/2205.14210/) (2022)
- [Learning to branch with Tree MDPs](https://mlsanity.com/paper/2205.11107/) (2022)
- [On Representing Linear Programs by Graph Neural Networks](https://mlsanity.com/paper/2209.12288/) (2022)
- [Online Mixed-Integer Optimization in Milliseconds](https://mlsanity.com/paper/1907.02206/) (2019)
- [Searching Large Neighborhoods for Integer Linear Programs with Contrastive Learning](https://mlsanity.com/paper/2302.01578/) (2023)
- [Accelerating Quadratic Optimization with Reinforcement Learning](https://mlsanity.com/paper/2107.10847/) (2021)
- [Revised Note on Learning Algorithms for Quadratic Assignment with Graph Neural Networks](https://mlsanity.com/paper/1706.07450/) (2017)
- [Lookback for Learning to Branch](https://mlsanity.com/paper/2206.14987/) (2022)
- [End-to-End Learning to Warm-Start for Real-Time Quadratic Optimization](https://mlsanity.com/paper/2212.08260/) (2022)
- [Exploring the Power of Graph Neural Networks in Solving Linear Optimization Problems](https://mlsanity.com/paper/2310.10603/) (2023)
- [On Representing Mixed-Integer Linear Programs by Graph Neural Networks](https://mlsanity.com/paper/2210.10759/) (2022)
- [Deep Graph Matching under Quadratic Constraint](https://mlsanity.com/paper/2103.06643/) (2021)
- [Tight Lower and Upper Bounds for the Complexity of Canonical Colour Refinement](https://mlsanity.com/paper/1509.08251/) (2015)
- [Learning Primal Heuristics for Mixed Integer Programs](https://mlsanity.com/paper/2107.00866/) (2021)

## Built on by (most cited first, 16 of 16)

- [Learning to Optimize for Mixed-Integer Non-linear Programming with Feasibility Guarantees](https://mlsanity.com/paper/2410.11061/) (2024)
- [Towards graph neural networks for provably solving convex optimization problems](https://mlsanity.com/paper/2502.02446/) (2025)
- [CoCo-MILP: Inter-Variable Contrastive and Intra-Constraint Competitive MILP Solution Prediction](https://mlsanity.com/paper/2511.09209/) (2025)
- [An Efficient Unsupervised Framework for Convex Quadratic Programs via Deep Unrolling](https://mlsanity.com/paper/2412.01051/) (2024)
- [Learning to accelerate distributed ADMM using graph neural networks](https://mlsanity.com/paper/2509.05288/) (2025)
- [Principled Data Augmentation for Learning to Solve Quadratic Programming Problems](https://mlsanity.com/paper/2506.01728/) (2025)
- [Warm-starting active-set solvers using graph neural networks](https://mlsanity.com/paper/2511.13174/) (2025)
- [Unrolled Graph Neural Networks for Constrained Optimization](https://mlsanity.com/paper/2509.17156/) (2025)
- [A General Neural Backbone for Mixed-Integer Linear Optimization via Dual Attention](https://mlsanity.com/paper/2601.04509/) (2026)
- [On the Expressive Power of GNNs to Solve Linear SDPs](https://mlsanity.com/paper/2604.27786/) (2026)
- [Solving Max-Cut to Global Optimality via Feasibility-Preserving Graph Neural Networks](https://mlsanity.com/paper/2605.07113/) (2026)
- [Data-driven Projection Generation for Efficiently Solving Heterogeneous Quadratic Programming Problems](https://mlsanity.com/paper/2510.26061/) (2025)
- [Unrolled Neural Networks for Constrained Optimization](https://mlsanity.com/paper/2601.17274/) (2026)
- [Exact Instance Compression for Convex Empirical Risk Minimization via Color Refinement](https://mlsanity.com/paper/2602.00437/) (2026)
- [Towards Solving Polynomial-Objective Integer Programming with Hypergraph Neural Networks](https://mlsanity.com/paper/2603.19318/) (2026)
- [Learned Preconditioning for a Primal-Dual Interior-Point Method](https://mlsanity.com/paper/2609.35665/) (2026)

## Abstract (arXiv)

Quadratic programming (QP) is the most widely applied category of problems in nonlinear programming. Many applications require real-time/fast solutions, though not necessarily with high precision. Existing methods either involve matrix decomposition or use the preconditioned conjugate gradient method. For relatively large instances, these methods cannot achieve the real-time requirement unless there is an effective preconditioner. Recently, graph neural networks (GNNs) opened new possibilities for QP. Some promising empirical studies of applying GNNs for QP tasks show that GNNs can capture key characteristics of an optimization instance and provide adaptive guidance accordingly to crucial configurations during the solving process, or directly provide an approximate solution. However, the theoretical understanding of GNNs in this context remains limited. Specifically, it is unclear what GNNs can and cannot achieve for QP tasks in theory. This work addresses this gap in the context of linearly constrained QP tasks. In the continuous setting, we prove that message-passing GNNs can universally represent fundamental properties of convex quadratic programs, including feasibility, optimal objective values, and optimal solutions. In the more challenging mixed-integer setting, while GNNs are not universal approximators, we identify a subclass of QP problems that GNNs can reliably represent.