mlsanityData to 7 Oct 2026

Let the Flows Tell: Solving Graph Combinatorial Optimization Problems with GFlowNets

arXiv 2305.17010 ↗First posted 26 May 2023cs.LG cs.AI cs.DMcited by 40

Not on the map. Why?

Abstract (arXiv)

Combinatorial optimization (CO) problems are often NP-hard and thus out of reach for exact algorithms, making them a tempting domain to apply machine learning methods. The highly structured constraints in these problems can hinder either optimization or sampling directly in the solution space. On the other hand, GFlowNets have recently emerged as a powerful machinery to efficiently sample from composite unnormalized densities sequentially and have the potential to amortize such solution-searching processes in CO, as well as generate diverse solution candidates. In this paper, we design Markov decision processes (MDPs) for different combinatorial problems and propose to train conditional GFlowNets to sample from the solution space. Efficient training techniques are also developed to benefit long-range credit assignment. Through extensive experiments on a variety of different CO tasks with synthetic and realistic data, we demonstrate that GFlowNet policies can efficiently find high-quality solutions. Our implementation is open-sourced at https://github.com/zdhNarsil/GFlowNet-CombOpt.

Key facts. Cited by 40 papers in the map (data through 7 Oct 2026). Builds on 51 of its 67 references that are in the map. First posted on arXiv 26 May 2023.

Builds on

51 of 67 references.

References · 51

  1. 2018Soft Actor-Critic: Off-Policy Maximum Entropy Deep Reinforcement Learning with a Stochastic Actorcited by 4,635
  2. 2018How Powerful are Graph Neural Networks?cited by 4,355
  3. 2018Addressing Function Approximation Error in Actor-Critic Methodscited by 2,302
  4. 2017Reinforcement Learning with Deep Energy-Based Policiescited by 659
  5. 2018Attention, Learn to Solve Routing Problems!cited by 646
  6. 2018Machine Learning for Combinatorial Optimization: a Methodological Tour d'Horizoncited by 612
  7. 2016Neural Combinatorial Optimization with Reinforcement Learningcited by 600
  8. 2017Learning Combinatorial Optimization Algorithms over Graphscited by 557
  9. 2021Flow Network based Generative Models for Non-Iterative Diverse Candidate Generationcited by 384
  10. 2020POMO: Policy Optimization with Multiple Optima for Reinforcement Learningcited by 341
  11. 2019Exact Combinatorial Optimization with Graph Convolutional Neural Networkscited by 313
  12. 2021GFlowNet Foundationscited by 286
38 more
  1. 2021Combinatorial optimization and reasoning with graph neural networkscited by 267
  2. 2022Trajectory balance: Improved credit assignment in GFlowNetscited by 244
  3. 2023DIFUSCO: Graph-based Diffusion Solvers for Combinatorial Optimizationcited by 216
  4. 2018Learning a SAT Solver from Single-Bit Supervisioncited by 198
  5. 2018Learning to Perform Local Rewriting for Combinatorial Optimizationcited by 183
  6. 2018Combinatorial Optimization with Graph Convolutional Networks and Guided Tree Searchcited by 182
  7. 2020Solving Mixed Integer Programs Using Neural Networkscited by 178
  8. 2022Biological Sequence Design with GFlowNetscited by 172
  9. 2019Learning Improvement Heuristics for Solving Routing Problemscited by 162
  10. 2022Bayesian Structure Learning with Generative Flow Networkscited by 153
  11. 2022Learning GFlowNets from partial episodes for improved convergence and stabilitycited by 129
  12. 2022DIMES: A Differentiable Meta Solver for Combinatorial Optimization Problemscited by 127
  13. 2020Erdos Goes Neural: an Unsupervised Learning Framework for Combinatorial Optimization on Graphscited by 115
  14. 2022Generative Flow Networks for Discrete Probabilistic Modelingcited by 113
  15. 2022GFlowNets and variational inferencecited by 103
  16. 2022Multi-Objective GFlowNetscited by 100
  17. 2023A theory of continuous generative flow networkscited by 98
  18. 2020Hybrid Models for Learning to Branchcited by 95
  19. 2023Better Training of GFlowNets with Local Credit and Incomplete Trajectoriescited by 83
  20. 2023Towards Understanding and Improving GFlowNet Trainingcited by 74
  21. 2023Robust Scheduling with GFlowNetscited by 67
  22. 2023GFlowNets for AI-Driven Scientific Discoverycited by 63
  23. 2020Reinforcement Learning with Combinatorial Actions: An Application to Vehicle Routingcited by 61
  24. 2020Learning What to Defer for Maximum Independent Setscited by 53
  25. 2022A-NeSI: A Scalable Approximate Method for Probabilistic Neurosymbolic Inferencecited by 50
  26. 2022Generative Augmented Flow Networkscited by 48
  27. 2019Graph Neural Networks for Maximum Constraint Satisfactioncited by 46
  28. 2023GFlowNet-EM for learning compositional latent variable modelscited by 40
  29. 2020Learning to Solve Combinatorial Optimization Problems on Real-World Graphs in Linear Timecited by 39
  30. 2022A Variational Perspective on Generative Flow Networkscited by 39
  31. 2022What's Wrong with Deep Learning in Tree Search for Combinatorial Optimizationcited by 36
  32. 2015Finding Near-Optimal Independent Sets at Scalecited by 32
  33. 2022Unsupervised Learning for Combinatorial Optimization with Principled Objective Relaxationcited by 32
  34. 2023Stochastic Generative Flow Networkscited by 32
  35. 2022Bayesian learning of Causal Structure and Mechanisms with GFlowNets and Variational Bayescited by 30
  36. 2023Distributional GFlowNets with Quantile Flowscited by 28
  37. 2023DAG Matters! GFlowNets Enhanced Explainer For Graph Neural Networkscited by 27
  38. 2022Annealed Training for Combinatorial Optimization on Graphscited by 17

50 most cited of 51 All 51 (JSON)

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2023: 9; 2024: 13; 2025: 8; 2026: 10.

40 papers.

Sort:

By area:

  1. 2023Diffusion Generative Flow Samplers: Improving learning signals through partial trajectory optimizationcited by 57
  2. 2024Ant Colony Sampling with GFlowNets for Combinatorial Optimizationcited by 53
  3. 2023Local Search GFlowNetscited by 45
  4. 2025Fast T2T: Optimization Consistency Speeds Up Diffusion-Based Training-to-Testing Solving for Combinatorial Optimizationcited by 43
  5. 2024Discrete Probabilistic Inference as Control in Multi-path Environmentscited by 40
  6. 2025FlowRL: Matching Reward Distributions for LLM Reasoningcited by 38
  7. 2024Efficient Diversity-Preserving Diffusion Alignment via Gradient-Informed GFlowNetscited by 30
  8. 2024Flow of Reasoning: Training LLMs for Divergent Reasoning with Minimal Examplescited by 29
  9. 2024Improving GFlowNets for Text-to-Image Diffusion Alignmentcited by 27
  10. 2023Learning to Scale Logits for Temperature-Conditional GFlowNetscited by 26
  11. 2023Learning Energy Decompositions for Partial Inference of GFlowNetscited by 24
  12. 2023Variational Annealing on Graphs for Combinatorial Optimizationcited by 21
28 more
  1. 2023Pre-Training and Fine-Tuning Generative Flow Networkscited by 16
  2. 2025Learning to Sample Effective and Diverse Prompts for Text-to-Image Generationcited by 16
  3. 2025GFlowVLM: Enhancing Multi-step Reasoning in Vision-Language Models with Generative Flow Networkscited by 15
  4. 2024AutoSAT: Automatically Optimize SAT Solvers via Large Language Modelscited by 14
  5. 2025Generative Models in Decision Making: A Surveycited by 14
  6. 2023Order-Preserving GFlowNetscited by 13
  7. 2023A Theory of Non-Acyclic Generative Flow Networkscited by 12
  8. 2023Are Graph Neural Networks Optimal Approximation Algorithms?cited by 10
  9. 2024Baking Symmetry into GFlowNetscited by 7
  10. 2024ARCLE: The Abstraction and Reasoning Corpus Learning Environment for Reinforcement Learningcited by 7
  11. 2024Tackling Prevalent Conditions in Unsupervised Combinatorial Optimization: Cardinality, Minimum, Covering, and Morecited by 6
  12. 2024On Divergence Measures for Training GFlowNetscited by 6
  13. 2024Streaming Bayes GFlowNetscited by 4
  14. 2024Embarrassingly Parallel GFlowNetscited by 3
  15. 2024A Benchmark for Maximum Cut: Towards Standardization of the Evaluation of Learned Heuristics for Combinatorial Optimizationcited by 3
  16. 2025Relative Trajectory Balance is equivalent to Trust-PCLcited by 3
  17. 2026Avoid What You Know: Divergent Trajectory Balance for GFlowNetscited by 3
  18. 2026GenAI-Net: A Generative AI Framework for Automated Biomolecular Network Designcited by 2
  19. 2025A Denoising Diffusion-Based Evolutionary Algorithm Framework: Application to the Maximum Independent Set Problemcited by 1
  20. 2026CADO: From Imitation to Cost Minimization for Heatmap-based Solvers in Combinatorial Optimizationcited by 1
  21. 2026QFlowNet: Fast, Diverse, and Efficient Unitary Synthesis with Generative Flow Networkscited by 1
  22. 2025Neural Tractability via Structure: Learning-Augmented Algorithms for Graph Combinatorial Optimizationcited by 0
  23. 2026Neural Ising Machines via Unrolling and Zeroth-Order Trainingcited by 0
  24. 2026Can Computational Reducibility Lead to Transferable Models for Graph Combinatorial Optimization?cited by 0
  25. 2026Learning to Solve Orienteering Problem with Time Windows and Variable Profitscited by 0
  26. 2026Crystal structure prediction using graph neural combinatorial optimizationcited by 0
  27. 2026Path-dependent Discrete Amortized Inferencecited by 0
  28. 2026Particle GFlowNets: Rethinking Generative Marginalization Modelscited by 0