# Combinatorial Optimization with Automated Graph Neural Networks

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

## Key facts

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

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

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Pointer Networks](https://mlsanity.com/paper/1506.03134/) (2015)
- [Reinforcement Learning for Solving the Vehicle Routing Problem](https://mlsanity.com/paper/1802.04240/) (2018)
- [Exact Combinatorial Optimization with Graph Convolutional Neural Networks](https://mlsanity.com/paper/1906.01629/) (2019)
- [Combinatorial optimization and reasoning with graph neural networks](https://mlsanity.com/paper/2102.09544/) (2021)
- [Design Space for Graph Neural Networks](https://mlsanity.com/paper/2011.08843/) (2020)
- [Combinatorial Optimization with Physics-Inspired Graph Neural Networks](https://mlsanity.com/paper/2107.01188/) (2021)
- [Policy-GNN: Aggregation Optimization for Graph Neural Networks](https://mlsanity.com/paper/2006.15097/) (2020)
- [Search to aggregate neighborhood for graph neural network](https://mlsanity.com/paper/2104.06608/) (2021)
- [GraphNAS: Graph Neural Architecture Search with Reinforcement Learning](https://mlsanity.com/paper/1904.09981/) (2019)
- [Automated Machine Learning on Graphs: A Survey](https://mlsanity.com/paper/2103.00742/) (2021)
- [DiffMG: Differentiable Meta Graph Search for Heterogeneous Graph Neural Networks](https://mlsanity.com/paper/2010.03250/) (2020)
- [DADAM: A Consensus-based Distributed Adaptive Gradient Method for Online Optimization](https://mlsanity.com/paper/1901.09109/) (2019)
- [Simplifying Architecture Search for Graph Neural Network](https://mlsanity.com/paper/2008.11652/) (2020)
- [Zeroth-Order Algorithms for Nonconvex Minimax Problems with Improved Complexities](https://mlsanity.com/paper/2001.07819/) (2020)
- [Graph Neural Network Architecture Search for Molecular Property Prediction](https://mlsanity.com/paper/2008.12187/) (2020)
- [AutoGEL: An Automated Graph Neural Network with Explicit Link Information](https://mlsanity.com/paper/2112.01064/) (2021)
- [Cuts, Primal Heuristics, and Learning to Branch for the Time-Dependent Traveling Salesman Problem](https://mlsanity.com/paper/1805.01415/) (2018)

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

- [CL4KGE: A Curriculum Learning Method for Knowledge Graph Embedding](https://mlsanity.com/paper/2408.14840/) (2024)
- [Binarizing Physics-Inspired GNNs for Combinatorial Optimization](https://mlsanity.com/paper/2507.13703/) (2025)
- [A Modality-Aware Cooperative Co-Evolutionary Framework for Multimodal Graph Neural Architecture Search](https://mlsanity.com/paper/2510.07325/) (2025)
- [Designing faster mixed integer linear programming algorithm via learning the optimal path](https://mlsanity.com/paper/2601.16056/) (2026)
- [Enhancing Genetic Algorithms with Graph Neural Networks: A Timetabling Case Study](https://mlsanity.com/paper/2602.08619/) (2026)

## Abstract (arXiv)

In recent years, graph neural networks (GNNs) have become increasingly popular for solving NP-hard combinatorial optimization (CO) problems, such as maximum cut and maximum independent set. The core idea behind these methods is to represent a CO problem as a graph and then use GNNs to learn the node/graph embedding with combinatorial information. Although these methods have achieved promising results, given a specific CO problem, the design of GNN architectures still requires heavy manual work with domain knowledge. Existing automated GNNs are mostly focused on traditional graph learning problems, which is inapplicable to solving NP-hard CO problems. To this end, we present a new class of AUTOmated GNNs for solving NP-hard problems, namely AutoGNP. We represent CO problems by GNNs and focus on two specific problems, i.e., mixed integer linear programming and quadratic unconstrained binary optimization. The idea of AutoGNP is to use graph neural architecture search algorithms to automatically find the best GNNs for a given NP-hard combinatorial optimization problem. Compared with existing graph neural architecture search algorithms, AutoGNP utilizes two-hop operators in the architecture search space. Moreover, AutoGNP utilizes simulated annealing and a strict early stopping policy to avoid local optimal solutions. Empirical results on benchmark combinatorial problems demonstrate the superiority of our proposed model.