# Graph Neural Networks for Maximum Constraint Satisfaction

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

## Key facts

- Cited by 46 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 18 Sep 2019.

## Built on by (most cited first, 30 of 46)

- [The Logic of Graph Neural Networks](https://mlsanity.com/paper/2104.14624/) (2021)
- [A Diffusion Model Framework for Unsupervised Neural Combinatorial Optimization](https://mlsanity.com/paper/2406.01661/) (2024)
- [Let the Flows Tell: Solving Graph Combinatorial Optimization Problems with GFlowNets](https://mlsanity.com/paper/2305.17010/) (2023)
- [Learning General Optimal Policies with Graph Neural Networks: Expressive Power, Transparency, and Limits](https://mlsanity.com/paper/2109.10129/) (2021)
- [Modern graph neural networks do worse than classical greedy algorithms in solving combinatorial optimization problems like maximum independent set](https://mlsanity.com/paper/2206.13211/) (2022)
- [One Model, Any CSP: Graph Neural Networks as Fast Global Search Heuristics for Constraint Satisfaction](https://mlsanity.com/paper/2208.10227/) (2022)
- [Link Scheduling using Graph Neural Networks](https://mlsanity.com/paper/2109.05536/) (2021)
- [Can Hybrid Geometric Scattering Networks Help Solve the Maximum Clique Problem?](https://mlsanity.com/paper/2206.01506/) (2022)
- [Augment with Care: Contrastive Learning for Combinatorial Problems](https://mlsanity.com/paper/2202.08396/) (2022)
- [Learning Generalized Policies Without Supervision Using GNNs](https://mlsanity.com/paper/2205.06002/) (2022)
- [Variational Annealing on Graphs for Combinatorial Optimization](https://mlsanity.com/paper/2311.14156/) (2023)
- [Unsupervised Learning for Combinatorial Optimization Needs Meta-Learning](https://mlsanity.com/paper/2301.03116/) (2023)
- [Annealed Training for Combinatorial Optimization on Graphs](https://mlsanity.com/paper/2207.11542/) (2022)
- [Neural Set Function Extensions: Learning with Discrete Functions in High Dimensions](https://mlsanity.com/paper/2208.04055/) (2022)
- [Solving AC Power Flow with Graph Neural Networks under Realistic Constraints](https://mlsanity.com/paper/2204.07000/) (2022)
- [Optimization by Parallel Quasi-Quantum Annealing with Gradient-Based Sampling](https://mlsanity.com/paper/2409.02135/) (2024)
- [DOGE-Train: Discrete Optimization on GPU with End-to-end Training](https://mlsanity.com/paper/2205.11638/) (2022)
- [Self-Supervised Transformers as Iterative Solution Improvers for Constraint Satisfaction](https://mlsanity.com/paper/2502.15794/) (2025)
- [Reheated Gradient-based Discrete Sampling for Combinatorial Optimization](https://mlsanity.com/paper/2503.04047/) (2025)
- [A Graph Neural Network with Negative Message Passing for Graph Coloring](https://mlsanity.com/paper/2301.11164/) (2023)
- [Optimizing Solution-Samplers for Combinatorial Problems: The Landscape of Policy-Gradient Methods](https://mlsanity.com/paper/2310.05309/) (2023)
- [A Unified Framework for Combinatorial Optimization Based on Graph Neural Networks](https://mlsanity.com/paper/2406.13125/) (2024)
- [Enhancing GNNs Performance on Combinatorial Optimization by Recurrent Feature Update](https://mlsanity.com/paper/2407.16468/) (2024)
- [Towards graph neural networks for provably solving convex optimization problems](https://mlsanity.com/paper/2502.02446/) (2025)
- [Geometric Algorithms for Neural Combinatorial Optimization with Constraints](https://mlsanity.com/paper/2510.24039/) (2025)
- [A Benchmark for Maximum Cut: Towards Standardization of the Evaluation of Learned Heuristics for Combinatorial Optimization](https://mlsanity.com/paper/2406.11897/) (2024)
- [Learning General Policies with Policy Gradient Methods](https://mlsanity.com/paper/2512.19366/) (2025)
- [Graph Pruning for Enumeration of Minimal Unsatisfiable Subsets](https://mlsanity.com/paper/2402.15524/) (2024)
- [Lightsolver challenges a leading deep learning solver for Max-2-SAT problems](https://mlsanity.com/paper/2302.06926/) (2023)
- [Finding Hamiltonian cycles with graph neural networks](https://mlsanity.com/paper/2306.06523/) (2023)

## Abstract (arXiv)

Many combinatorial optimization problems can be phrased in the language of constraint satisfaction problems. We introduce a graph neural network architecture for solving such optimization problems. The architecture is generic; it works for all binary constraint satisfaction problems. Training is unsupervised, and it is sufficient to train on relatively small instances; the resulting networks perform well on much larger instances (at least 10-times larger). We experimentally evaluate our approach for a variety of problems, including Maximum Cut and Maximum Independent Set. Despite being generic, we show that our approach matches or surpasses most greedy and semi-definite programming based algorithms and sometimes even outperforms state-of-the-art heuristics for the specific problems.