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

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

## Key facts

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

## Builds on (most cited first, 30 of 51)

- [Soft Actor-Critic: Off-Policy Maximum Entropy Deep Reinforcement Learning with a Stochastic Actor](https://mlsanity.com/paper/1801.01290/) (2018)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Addressing Function Approximation Error in Actor-Critic Methods](https://mlsanity.com/paper/1802.09477/) (2018)
- [Reinforcement Learning with Deep Energy-Based Policies](https://mlsanity.com/paper/1702.08165/) (2017)
- [Attention, Learn to Solve Routing Problems!](https://mlsanity.com/paper/1803.08475/) (2018)
- [Machine Learning for Combinatorial Optimization: a Methodological Tour d'Horizon](https://mlsanity.com/paper/1811.06128/) (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)
- [Flow Network based Generative Models for Non-Iterative Diverse Candidate Generation](https://mlsanity.com/paper/2106.04399/) (2021)
- [POMO: Policy Optimization with Multiple Optima for Reinforcement Learning](https://mlsanity.com/paper/2010.16011/) (2020)
- [Exact Combinatorial Optimization with Graph Convolutional Neural Networks](https://mlsanity.com/paper/1906.01629/) (2019)
- [GFlowNet Foundations](https://mlsanity.com/paper/2111.09266/) (2021)
- [Combinatorial optimization and reasoning with graph neural networks](https://mlsanity.com/paper/2102.09544/) (2021)
- [Trajectory balance: Improved credit assignment in GFlowNets](https://mlsanity.com/paper/2201.13259/) (2022)
- [DIFUSCO: Graph-based Diffusion Solvers for Combinatorial Optimization](https://mlsanity.com/paper/2302.08224/) (2023)
- [Learning a SAT Solver from Single-Bit Supervision](https://mlsanity.com/paper/1802.03685/) (2018)
- [Learning to Perform Local Rewriting for Combinatorial Optimization](https://mlsanity.com/paper/1810.00337/) (2018)
- [Combinatorial Optimization with Graph Convolutional Networks and Guided Tree Search](https://mlsanity.com/paper/1810.10659/) (2018)
- [Solving Mixed Integer Programs Using Neural Networks](https://mlsanity.com/paper/2012.13349/) (2020)
- [Biological Sequence Design with GFlowNets](https://mlsanity.com/paper/2203.04115/) (2022)
- [Learning Improvement Heuristics for Solving Routing Problems](https://mlsanity.com/paper/1912.05784/) (2019)
- [Bayesian Structure Learning with Generative Flow Networks](https://mlsanity.com/paper/2202.13903/) (2022)
- [Learning GFlowNets from partial episodes for improved convergence and stability](https://mlsanity.com/paper/2209.12782/) (2022)
- [DIMES: A Differentiable Meta Solver for Combinatorial Optimization Problems](https://mlsanity.com/paper/2210.04123/) (2022)
- [Erdos Goes Neural: an Unsupervised Learning Framework for Combinatorial Optimization on Graphs](https://mlsanity.com/paper/2006.10643/) (2020)
- [Generative Flow Networks for Discrete Probabilistic Modeling](https://mlsanity.com/paper/2202.01361/) (2022)
- [GFlowNets and variational inference](https://mlsanity.com/paper/2210.00580/) (2022)
- [Multi-Objective GFlowNets](https://mlsanity.com/paper/2210.12765/) (2022)
- [A theory of continuous generative flow networks](https://mlsanity.com/paper/2301.12594/) (2023)
- [Hybrid Models for Learning to Branch](https://mlsanity.com/paper/2006.15212/) (2020)

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

- [Diffusion Generative Flow Samplers: Improving learning signals through partial trajectory optimization](https://mlsanity.com/paper/2310.02679/) (2023)
- [Ant Colony Sampling with GFlowNets for Combinatorial Optimization](https://mlsanity.com/paper/2403.07041/) (2024)
- [Local Search GFlowNets](https://mlsanity.com/paper/2310.02710/) (2023)
- [Fast T2T: Optimization Consistency Speeds Up Diffusion-Based Training-to-Testing Solving for Combinatorial Optimization](https://mlsanity.com/paper/2502.02941/) (2025)
- [Discrete Probabilistic Inference as Control in Multi-path Environments](https://mlsanity.com/paper/2402.10309/) (2024)
- [FlowRL: Matching Reward Distributions for LLM Reasoning](https://mlsanity.com/paper/2509.15207/) (2025)
- [Efficient Diversity-Preserving Diffusion Alignment via Gradient-Informed GFlowNets](https://mlsanity.com/paper/2412.07775/) (2024)
- [Flow of Reasoning: Training LLMs for Divergent Reasoning with Minimal Examples](https://mlsanity.com/paper/2406.05673/) (2024)
- [Learning to Scale Logits for Temperature-Conditional GFlowNets](https://mlsanity.com/paper/2310.02823/) (2023)
- [Improving GFlowNets for Text-to-Image Diffusion Alignment](https://mlsanity.com/paper/2406.00633/) (2024)
- [Learning Energy Decompositions for Partial Inference of GFlowNets](https://mlsanity.com/paper/2310.03301/) (2023)
- [Variational Annealing on Graphs for Combinatorial Optimization](https://mlsanity.com/paper/2311.14156/) (2023)
- [Pre-Training and Fine-Tuning Generative Flow Networks](https://mlsanity.com/paper/2310.03419/) (2023)
- [Learning to Sample Effective and Diverse Prompts for Text-to-Image Generation](https://mlsanity.com/paper/2502.11477/) (2025)
- [AutoSAT: Automatically Optimize SAT Solvers via Large Language Models](https://mlsanity.com/paper/2402.10705/) (2024)
- [Generative Models in Decision Making: A Survey](https://mlsanity.com/paper/2502.17100/) (2025)
- [GFlowVLM: Enhancing Multi-step Reasoning in Vision-Language Models with Generative Flow Networks](https://mlsanity.com/paper/2503.06514/) (2025)
- [Order-Preserving GFlowNets](https://mlsanity.com/paper/2310.00386/) (2023)
- [A Theory of Non-Acyclic Generative Flow Networks](https://mlsanity.com/paper/2312.15246/) (2023)
- [Are Graph Neural Networks Optimal Approximation Algorithms?](https://mlsanity.com/paper/2310.00526/) (2023)
- [Tackling Prevalent Conditions in Unsupervised Combinatorial Optimization: Cardinality, Minimum, Covering, and More](https://mlsanity.com/paper/2405.08424/) (2024)
- [Baking Symmetry into GFlowNets](https://mlsanity.com/paper/2406.05426/) (2024)
- [ARCLE: The Abstraction and Reasoning Corpus Learning Environment for Reinforcement Learning](https://mlsanity.com/paper/2407.20806/) (2024)
- [On Divergence Measures for Training GFlowNets](https://mlsanity.com/paper/2410.09355/) (2024)
- [Relative Trajectory Balance is equivalent to Trust-PCL](https://mlsanity.com/paper/2509.01632/) (2025)
- [Streaming Bayes GFlowNets](https://mlsanity.com/paper/2411.05899/) (2024)
- [Avoid What You Know: Divergent Trajectory Balance for GFlowNets](https://mlsanity.com/paper/2602.17827/) (2026)
- [Embarrassingly Parallel GFlowNets](https://mlsanity.com/paper/2406.03288/) (2024)
- [A Benchmark for Maximum Cut: Towards Standardization of the Evaluation of Learned Heuristics for Combinatorial Optimization](https://mlsanity.com/paper/2406.11897/) (2024)
- [GenAI-Net: A Generative AI Framework for Automated Biomolecular Network Design](https://mlsanity.com/paper/2601.17582/) (2026)

## 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.