# One Model, Any CSP: Graph Neural Networks as Fast Global Search Heuristics for Constraint Satisfaction

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

## Key facts

- Cited by 27 papers in the map (data through 14 Oct 2026).
- Builds on 18 of its 63 references that are in the map.
- First posted on arXiv 22 Aug 2022.

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

- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Neural Message Passing for Quantum Chemistry](https://mlsanity.com/paper/1704.01212/) (2017)
- [Pointer Networks](https://mlsanity.com/paper/1506.03134/) (2015)
- [Attention, Learn to Solve Routing Problems!](https://mlsanity.com/paper/1803.08475/) (2018)
- [Neural Combinatorial Optimization with Reinforcement Learning](https://mlsanity.com/paper/1611.09940/) (2016)
- [Learning Combinatorial Optimization Algorithms over Graphs](https://mlsanity.com/paper/1704.01665/) (2017)
- [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)
- [Learning a SAT Solver from Single-Bit Supervision](https://mlsanity.com/paper/1802.03685/) (2018)
- [The Surprising Power of Graph Neural Networks with Random Node Initialization](https://mlsanity.com/paper/2010.01179/) (2020)
- [Random Features Strengthen Graph Neural Networks](https://mlsanity.com/paper/2002.03155/) (2020)
- [Exploratory Combinatorial Optimization with Reinforcement Learning](https://mlsanity.com/paper/1909.04063/) (2019)
- [Graph Neural Networks for Maximum Constraint Satisfaction](https://mlsanity.com/paper/1909.08387/) (2019)
- [A Bi-Level Framework for Learning to Solve Combinatorial Optimization on Graphs](https://mlsanity.com/paper/2106.04927/) (2021)
- [NLocalSAT: Boosting Local Search with Solution Prediction](https://mlsanity.com/paper/2001.09398/) (2020)
- [PDP: A General Neural Framework for Learning Constraint Satisfaction Solvers](https://mlsanity.com/paper/1903.01969/) (2019)
- [Learning to Solve Combinatorial Graph Partitioning Problems via Efficient Exploration](https://mlsanity.com/paper/2205.14105/) (2022)
- [Reversible Action Design for Combinatorial Optimization with Reinforcement Learning](https://mlsanity.com/paper/2102.07210/) (2021)

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

- [A Diffusion Model Framework for Unsupervised Neural Combinatorial Optimization](https://mlsanity.com/paper/2406.01661/) (2024)
- [Some Might Say All You Need Is Sum](https://mlsanity.com/paper/2302.11603/) (2023)
- [Graphically Structured Diffusion Models](https://mlsanity.com/paper/2210.11633/) (2022)
- [Are Graph Neural Networks Optimal Approximation Algorithms?](https://mlsanity.com/paper/2310.00526/) (2023)
- [Self-Supervised Transformers as Iterative Solution Improvers for Constraint Satisfaction](https://mlsanity.com/paper/2502.15794/) (2025)
- [Towards a Generic Representation of Combinatorial Problems for Learning-Based Approaches](https://mlsanity.com/paper/2403.06026/) (2024)
- [A Unified Framework for Combinatorial Optimization Based on Graph Neural Networks](https://mlsanity.com/paper/2406.13125/) (2024)
- [Repetition Makes Perfect: Recurrent Graph Neural Networks Match Message-Passing Limit](https://mlsanity.com/paper/2505.00291/) (2025)
- [Learning from Algorithm Feedback: One-Shot SAT Solver Guidance with GNNs](https://mlsanity.com/paper/2505.16053/) (2025)
- [UNSAT Solver Synthesis via Monte Carlo Forest Search](https://mlsanity.com/paper/2211.12581/) (2022)
- [A Benchmark for Maximum Cut: Towards Standardization of the Evaluation of Learned Heuristics for Combinatorial Optimization](https://mlsanity.com/paper/2406.11897/) (2024)
- [Quadratic Binary Optimization with Graph Neural Networks](https://mlsanity.com/paper/2404.04874/) (2024)
- [FORGE: Foundational Optimization Representations from Graph Embeddings](https://mlsanity.com/paper/2508.20330/) (2025)
- [Finding Hamiltonian cycles with graph neural networks](https://mlsanity.com/paper/2306.06523/) (2023)
- [Beyond Interpolation: Extrapolative Reasoning with Reinforcement Learning and Graph Neural Networks](https://mlsanity.com/paper/2502.04402/) (2025)
- [Learning for Dynamic Combinatorial Optimization without Training Data](https://mlsanity.com/paper/2505.19497/) (2025)
- [Nonlocal Monte Carlo via Reinforcement Learning](https://mlsanity.com/paper/2508.10520/) (2025)
- [Large Neighborhood Search meets Iterative Neural Constraint Heuristics](https://mlsanity.com/paper/2603.20801/) (2026)
- [One Model, Any Conjunctive Query: Graph Neural Networks for Answering Queries over Incomplete Knowledge Graphs](https://mlsanity.com/paper/2409.13959/) (2024)
- [Enabling Population-Based Architectures for Neural Combinatorial Optimization](https://mlsanity.com/paper/2601.08696/) (2026)
- [Test-Time Adaptation for Unsupervised Combinatorial Optimization](https://mlsanity.com/paper/2601.21048/) (2026)
- [Exploiting Low-Rank Objective Structure in Discrete Quadratic Optimization](https://mlsanity.com/paper/2602.20376/) (2026)
- [Can Computational Reducibility Lead to Transferable Models for Graph Combinatorial Optimization?](https://mlsanity.com/paper/2603.02462/) (2026)
- [Lost in Aggregation: On a Fundamental Expressivity Limit of Message-Passing Graph Neural Networks](https://mlsanity.com/paper/2603.14846/) (2026)
- [Hypergraph Neural Networks Accelerate MUS Enumeration](https://mlsanity.com/paper/2604.09001/) (2026)
- [Distribution-Aware Algorithm Design with LLM Agents](https://mlsanity.com/paper/2605.14141/) (2026)
- [Blocked Gibbs meets Diffusion Transformers: Unsupervised Learning for Constraint Optimization](https://mlsanity.com/paper/2605.25129/) (2026)

## Abstract (arXiv)

We propose a universal Graph Neural Network architecture which can be trained as an end-2-end search heuristic for any Constraint Satisfaction Problem (CSP). Our architecture can be trained unsupervised with policy gradient descent to generate problem specific heuristics for any CSP in a purely data driven manner. The approach is based on a novel graph representation for CSPs that is both generic and compact and enables us to process every possible CSP instance with one GNN, regardless of constraint arity, relations or domain size. Unlike previous RL-based methods, we operate on a global search action space and allow our GNN to modify any number of variables in every step of the stochastic search. This enables our method to properly leverage the inherent parallelism of GNNs. We perform a thorough empirical evaluation where we learn heuristics for well known and important CSPs from random data, including graph coloring, MaxCut, 3-SAT and MAX-k-SAT. Our approach outperforms prior approaches for neural combinatorial optimization by a substantial margin. It can compete with, and even improve upon, conventional search heuristics on test instances that are several orders of magnitude larger and structurally more complex than those seen during training.