mlsanityData to 7 Oct 2026

Erdos Goes Neural: an Unsupervised Learning Framework for Combinatorial Optimization on Graphs

arXiv 2006.10643 ↗First posted 18 Jun 2020cs.LG stat.MLcited by 115

Not on the map. Why?

Abstract (arXiv)

Combinatorial optimization problems are notoriously challenging for neural networks, especially in the absence of labeled instances. This work proposes an unsupervised learning framework for CO problems on graphs that can provide integral solutions of certified quality. Inspired by Erdos' probabilistic method, we use a neural network to parametrize a probability distribution over sets. Crucially, we show that when the network is optimized w.r.t. a suitably chosen loss, the learned distribution contains, with controlled probability, a low-cost integral solution that obeys the constraints of the combinatorial problem. The probabilistic proof of existence is then derandomized to decode the desired solutions. We demonstrate the efficacy of this approach to obtain valid solutions to the maximum clique problem and to perform local graph clustering. Our method achieves competitive results on both real datasets and synthetic hard instances.

Key facts. Cited by 115 papers in the map (data through 7 Oct 2026). First posted on arXiv 18 Jun 2020.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 11; 2022: 18; 2023: 14; 2024: 21; 2025: 31; 2026: 20.

115 papers.

Sort:

By area:

  1. 2021Combinatorial optimization and reasoning with graph neural networkscited by 267
  2. 2023DIFUSCO: Graph-based Diffusion Solvers for Combinatorial Optimizationcited by 216
  3. 2021Scalars are universal: Equivariant machine learning, structured like classical physicscited by 127
  4. 2022DIMES: A Differentiable Meta Solver for Combinatorial Optimization Problemscited by 127
  5. 2021Combinatorial Optimization with Physics-Inspired Graph Neural Networkscited by 107
  6. 2021Matrix Encoding Networks for Neural Combinatorial Optimizationcited by 89
  7. 2024A Diffusion Model Framework for Unsupervised Neural Combinatorial Optimizationcited by 58
  8. 2022Pareto Set Learning for Neural Multi-objective Combinatorial Optimizationcited by 56
  9. 2025PyG 2.0: Scalable Learning on Real World Graphscited by 49
  10. 2022MIP-GNN: A Data-Driven Framework for Guiding Combinatorial Solverscited by 48
  11. 2022Differentiable DAG Samplingcited by 46
  12. 2025Fast T2T: Optimization Consistency Speeds Up Diffusion-Based Training-to-Testing Solving for Combinatorial Optimizationcited by 43
38 more
  1. 2023Let the Flows Tell: Solving Graph Combinatorial Optimization Problems with GFlowNetscited by 40
  2. 2024Diffusion Models as Constrained Samplers for Optimization with Unknown Constraintscited by 33
  3. 2022Unsupervised Learning for Combinatorial Optimization with Principled Objective Relaxationcited by 32
  4. 2022Graph Coloring with Physics-Inspired Graph Neural Networkscited by 29
  5. 2022Towards Better Out-of-Distribution Generalization of Neural Algorithmic Reasoning Taskscited by 29
  6. 2025Scalable Discrete Diffusion Samplers: Combinatorial Optimization and Statistical Physicscited by 28
  7. 2021A Bi-Level Framework for Learning to Solve Combinatorial Optimization on Graphscited 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. 2023Variational Annealing on Graphs for Combinatorial Optimizationcited by 21
  11. 2023Unsupervised Learning for Combinatorial Optimization Needs Meta-Learningcited by 19
  12. 2022Learning to Control Local Search for Combinatorial Optimizationcited by 18
  13. 2025Pareto Set Learning for Multi-Objective Reinforcement Learningcited by 18
  14. 2022Annealed Training for Combinatorial Optimization on Graphscited by 17
  15. 2023Controlling Continuous Relaxation for Combinatorial Optimizationcited by 16
  16. 2024LinSATNet: The Positive Linear Satisfiability Neural Networkscited by 16
  17. 2022Neural Set Function Extensions: Learning with Discrete Functions in High Dimensionscited by 14
  18. 2021Maximum Entropy Weighted Independent Set Pooling for Graph Neural Networkscited by 12
  19. 2021Partition and Code: learning how to compress graphscited by 10
  20. 2023Are Graph Neural Networks Optimal Approximation Algorithms?cited by 10
  21. 2025Regularized Langevin Dynamics for Combinatorial Optimizationcited by 10
  22. 2024Efficient Rectification of Neuro-Symbolic Reasoning Inconsistencies by Abductive Reflectioncited by 9
  23. 2025Graph neural networks extrapolate out-of-distribution for shortest pathscited by 9
  24. 2021Graph Partitioning and Sparse Matrix Ordering using Reinforcement Learning and Graph Neural Networkscited by 8
  25. 2021Maximizing Influence with Graph Neural Networkscited by 8
  26. 2022Maximum Common Subgraph Guided Graph Retrieval: Late and Early Interaction Networkscited by 8
  27. 2024Generative AI and Process Systems Engineering: The Next Frontiercited by 8
  28. 2025Primal-Dual Neural Algorithmic Reasoningcited by 8
  29. 2021Adversarial Deep Learning for Online Resource Allocationcited by 7
  30. 2022Learning Graph Search Heuristicscited by 7
  31. 2024GLinSAT: The General Linear Satisfiability Neural Network Layer By Accelerated Gradient Descentcited by 7
  32. 2024Tackling Prevalent Conditions in Unsupervised Combinatorial Optimization: Cardinality, Minimum, Covering, and Morecited by 6
  33. 2024Optimization by Parallel Quasi-Quantum Annealing with Gradient-Based Samplingcited by 6
  34. 2025Self-Supervised Transformers as Iterative Solution Improvers for Constraint Satisfactioncited by 6
  35. 2025Reheated Gradient-based Discrete Sampling for Combinatorial Optimizationcited by 6
  36. 2022Learning to Optimize with Stochastic Dominance Constraintscited by 5
  37. 2023Monte Carlo Policy Gradient Method for Binary Optimizationcited by 5
  38. 2023Optimizing Solution-Samplers for Combinatorial Problems: The Landscape of Policy-Gradient Methodscited by 5

50 most cited of 115 All 115 (JSON)