mlsanityData to 7 Oct 2026

Graph Neural Networks for Maximum Constraint Satisfaction

arXiv 1909.08387 ↗First posted 18 Sep 2019cs.AI cs.LGcited by 46

Not on the map. Why?

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.

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 3; 2022: 9; 2023: 9; 2024: 7; 2025: 7; 2026: 11.

46 papers.

Sort:

By area:

  1. 2021The Logic of Graph Neural Networkscited by 84
  2. 2024A Diffusion Model Framework for Unsupervised Neural Combinatorial Optimizationcited by 58
  3. 2023Let the Flows Tell: Solving Graph Combinatorial Optimization Problems with GFlowNetscited by 40
  4. 2021Learning General Optimal Policies with Graph Neural Networks: Expressive Power, Transparency, and Limitscited by 38
  5. 2022Modern graph neural networks do worse than classical greedy algorithms in solving combinatorial optimization problems like maximum independent setcited by 33
  6. 2022One Model, Any CSP: Graph Neural Networks as Fast Global Search Heuristics for Constraint Satisfactioncited by 27
  7. 2021Link Scheduling using Graph Neural Networkscited by 26
  8. 2022Can Hybrid Geometric Scattering Networks Help Solve the Maximum Clique Problem?cited by 25
  9. 2022Augment with Care: Contrastive Learning for Combinatorial Problemscited by 22
  10. 2022Learning Generalized Policies Without Supervision Using GNNscited by 22
  11. 2023Variational Annealing on Graphs for Combinatorial Optimizationcited by 21
  12. 2023Unsupervised Learning for Combinatorial Optimization Needs Meta-Learningcited by 19
34 more
  1. 2022Annealed Training for Combinatorial Optimization on Graphscited by 17
  2. 2022Neural Set Function Extensions: Learning with Discrete Functions in High Dimensionscited by 14
  3. 2022Solving AC Power Flow with Graph Neural Networks under Realistic Constraintscited by 11
  4. 2022DOGE-Train: Discrete Optimization on GPU with End-to-end Trainingcited by 6
  5. 2024Optimization by Parallel Quasi-Quantum Annealing with Gradient-Based Samplingcited by 6
  6. 2025Self-Supervised Transformers as Iterative Solution Improvers for Constraint Satisfactioncited by 6
  7. 2025Reheated Gradient-based Discrete Sampling for Combinatorial Optimizationcited by 6
  8. 2023A Graph Neural Network with Negative Message Passing for Graph Coloringcited by 5
  9. 2023Optimizing Solution-Samplers for Combinatorial Problems: The Landscape of Policy-Gradient Methodscited by 5
  10. 2024A Unified Framework for Combinatorial Optimization Based on Graph Neural Networkscited by 4
  11. 2024Enhancing GNNs Performance on Combinatorial Optimization by Recurrent Feature Updatecited by 4
  12. 2025Towards graph neural networks for provably solving convex optimization problemscited by 4
  13. 2025Geometric Algorithms for Neural Combinatorial Optimization with Constraintscited by 4
  14. 2024A Benchmark for Maximum Cut: Towards Standardization of the Evaluation of Learned Heuristics for Combinatorial Optimizationcited by 3
  15. 2025Learning General Policies with Policy Gradient Methodscited by 3
  16. 2024Graph Pruning for Enumeration of Minimal Unsatisfiable Subsetscited by 2
  17. 2023Lightsolver challenges a leading deep learning solver for Max-2-SAT problemscited by 1
  18. 2023Finding Hamiltonian cycles with graph neural networkscited by 1
  19. 2023Unveiling the Limits of Learned Local Search Heuristics: Are You the Mightiest of the Meek?cited by 1
  20. 2023A Unified Pre-training and Adaptation Framework for Combinatorial Optimization on Graphscited by 1
  21. 2024Learning to Ground Existentially Quantified Goalscited by 1
  22. 2025Learning for Dynamic Combinatorial Optimization without Training Datacited by 1
  23. 2026Large Neighborhood Search meets Iterative Neural Constraint Heuristicscited by 1
  24. 2025Preference-Based Gradient Estimation for ML-Guided Approximate Combinatorial Optimizationcited by 0
  25. 2026GraIP: A Benchmarking Framework For Neural Graph Inverse Problemscited by 0
  26. 2026Test-Time Adaptation for Unsupervised Combinatorial Optimizationcited by 0
  27. 2026Can Computational Reducibility Lead to Transferable Models for Graph Combinatorial Optimization?cited by 0
  28. 2026UniHetCO: A Unified Heterogeneous Representation for Multi-Problem Learning in Unsupervised Neural Combinatorial Optimizationcited by 0
  29. 2026Graph Neural Networks with Triangle-Based Messages for the Multicut Problemcited by 0
  30. 2026Distribution-Aware Algorithm Design with LLM Agentscited by 0
  31. 2026Blocked Gibbs meets Diffusion Transformers: Unsupervised Learning for Constraint Optimizationcited by 0
  32. 2026Anatomy of a Sound Neural Reasoner: One-Shot Amortization, First-Pass Poisoning, and Search Inertness in Clue-Rich Completioncited by 0
  33. 2026Position: Certified Correctness in Neural Constraint Reasoning Requires Symbolic Integrationcited by 0
  34. 2026Self-Supervised Combinatorial Optimization with Constraints via Frank-Wolfecited by 0