# Decision-focused Graph Neural Networks for Combinatorial Optimization

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 13 of its 43 references that are in the map.
- First posted on arXiv 5 Jun 2024.

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

- [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)
- [Measuring and Relieving the Over-smoothing Problem for Graph Neural Networks from the Topological View](https://mlsanity.com/paper/1909.03211/) (2019)
- [Melding the Data-Decisions Pipeline: Decision-Focused Learning for Combinatorial Optimization](https://mlsanity.com/paper/1809.05504/) (2018)
- [Combinatorial Optimization with Graph Convolutional Networks and Guided Tree Search](https://mlsanity.com/paper/1810.10659/) (2018)
- [Combinatorial Optimization with Physics-Inspired Graph Neural Networks](https://mlsanity.com/paper/2107.01188/) (2021)
- [Automatically Learning Compact Quality-aware Surrogates for Optimization Problems](https://mlsanity.com/paper/2006.10815/) (2020)
- [Graph Transformer Networks: Learning Meta-path Graphs to Improve GNNs](https://mlsanity.com/paper/2106.06218/) (2021)
- [Inability of a graph neural network heuristic to outperform greedy algorithms in solving combinatorial optimization problems like Max-Cut](https://mlsanity.com/paper/2210.00623/) (2022)
- [Wireless Network Design for Control Systems: A Survey](https://mlsanity.com/paper/1708.07353/) (2017)
- [Decision-Focused Learning without Differentiable Optimization: Learning Locally Optimized Decision Losses](https://mlsanity.com/paper/2203.16067/) (2022)
- [NuMVC: An Efficient Local Search Algorithm for Minimum Vertex Cover](https://mlsanity.com/paper/1402.0584/) (2014)

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

- [Hard Constraints Meet Soft Generation: Guaranteed Feasibility for LLM-based Combinatorial Optimization](https://mlsanity.com/paper/2602.01090/) (2026)
- [CL4KGE: A Curriculum Learning Method for Knowledge Graph Embedding](https://mlsanity.com/paper/2408.14840/) (2024)

## Abstract (arXiv)

In recent years, there has been notable interest in investigating combinatorial optimization (CO) problems by neural-based framework. An emerging strategy to tackle these challenging problems involves the adoption of graph neural networks (GNNs) as an alternative to traditional algorithms, a subject that has attracted considerable attention. Despite the growing popularity of GNNs and traditional algorithm solvers in the realm of CO, there is limited research on their integrated use and the correlation between them within an end-to-end framework. The primary focus of our work is to formulate a more efficient and precise framework for CO by employing decision-focused learning on graphs. Additionally, we introduce a decision-focused framework that utilizes GNNs to address CO problems with auxiliary support. To realize an end-to-end approach, we have designed two cascaded modules: (a) an unsupervised trained graph predictive model, and (b) a solver for quadratic binary unconstrained optimization. Empirical evaluations are conducted on various classical tasks, including maximum cut, maximum independent set, and minimum vertex cover. The experimental results on classical CO problems (i.e. MaxCut, MIS, and MVC) demonstrate the superiority of our method over both the standalone GNN approach and classical methods.