# Quadratic Binary Optimization with Graph Neural Networks

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 23 of its 57 references that are in the map.
- First posted on arXiv 7 Apr 2024.

## Builds on (most cited first, 23 of 23)

- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Neural Ordinary Differential Equations](https://mlsanity.com/paper/1806.07366/) (2018)
- [Fast Graph Representation Learning with PyTorch Geometric](https://mlsanity.com/paper/1903.02428/) (2019)
- [Implicit Neural Representations with Periodic Activation Functions](https://mlsanity.com/paper/2006.09661/) (2020)
- [Dynamic Graph CNN for Learning on Point Clouds](https://mlsanity.com/paper/1801.07829/) (2018)
- [Simple and Deep Graph Convolutional Networks](https://mlsanity.com/paper/2007.02133/) (2020)
- [Geom-GCN: Geometric Graph Convolutional Networks](https://mlsanity.com/paper/2002.05287/) (2020)
- [Geometric deep learning on graphs and manifolds using mixture model CNNs](https://mlsanity.com/paper/1611.08402/) (2016)
- [GRAND: Graph Neural Diffusion](https://mlsanity.com/paper/2106.10934/) (2021)
- [Optimal approximation of piecewise smooth functions using deep ReLU neural networks](https://mlsanity.com/paper/1709.05289/) (2017)
- [DIMES: A Differentiable Meta Solver for Combinatorial Optimization Problems](https://mlsanity.com/paper/2210.04123/) (2022)
- [Erdos Goes Neural: an Unsupervised Learning Framework for Combinatorial Optimization on Graphs](https://mlsanity.com/paper/2006.10643/) (2020)
- [Combinatorial Optimization with Physics-Inspired Graph Neural Networks](https://mlsanity.com/paper/2107.01188/) (2021)
- [PDE-GCN: Novel Architectures for Graph Neural Networks Motivated by Partial Differential Equations](https://mlsanity.com/paper/2108.01938/) (2021)
- [Neural Algorithmic Reasoning](https://mlsanity.com/paper/2105.02761/) (2021)
- [GREAD: Graph Neural Reaction-Diffusion Networks](https://mlsanity.com/paper/2211.14208/) (2022)
- [One Model, Any CSP: Graph Neural Networks as Fast Global Search Heuristics for Constraint Satisfaction](https://mlsanity.com/paper/2208.10227/) (2022)
- [Graph Neural Convection-Diffusion with Heterophily](https://mlsanity.com/paper/2305.16780/) (2023)
- [Improving Graph Neural Networks with Learnable Propagation Operators](https://mlsanity.com/paper/2210.17224/) (2022)
- [Benchmark of quantum-inspired heuristic solvers for quadratic unconstrained binary optimization](https://mlsanity.com/paper/2104.14096/) (2021)

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

- [The Heterophilic Graph Learning Handbook: Benchmarks, Models, Theoretical Analysis, Applications and Challenges](https://mlsanity.com/paper/2407.09618/) (2024)
- [Target-Aware Data Augmentation for SAT Prediction](https://mlsanity.com/paper/2605.06931/) (2026)

## Abstract (arXiv)

We investigate a link between Graph Neural Networks (GNNs) and Quadratic Unconstrained Binary Optimization (QUBO) problems, laying the groundwork for GNNs to approximate solutions for these computationally challenging tasks. By analyzing the sensitivity of QUBO formulations, we frame the solution of QUBO problems as a heterophilic node classification task. We then propose QUBO-GNN, an architecture that integrates graph representation learning techniques with QUBO-aware features to approximate solutions efficiently. Additionally, we introduce a self-supervised data generation mechanism to enable efficient and scalable training data acquisition even for large-scale QUBO instances. Experimental evaluations of QUBO-GNN across diverse QUBO problem sizes demonstrate its superior performance compared to exhaustive search and heuristic methods. Finally, we discuss open challenges in the emerging intersection between QUBO optimization and GNN-based learning.