Research map / Learning theory and algorithms / Combinatorial and search optimization
Let the Flows Tell: Solving Graph Combinatorial Problems with GFlowNets
Dinghuai Zhang, Hanjun Dai, Nikolay Malkin, Aaron Courville, Yoshua Bengio, Ling Pan
Read the paperCheck your idea against 137,217 papers
AI-extracted. The measured effects below were read by AI from the paper's full text (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use GFlowNet instead of PPO RL baseline | MIS solver · MIS RB-large | independent set size: 32.32 -> 37.48 | Improved |
| use GFlowNet instead of PPO | MIS solver · MIS SATLIB | independent set size: 421.49 -> 423.54 | Improved |
| use GFlowNet instead of best unsupervised baseline (MFA) | MC solver · MC large | clique size: 27.94 -> 31.42 | Improved |
| use GFlowNet instead of ANNEAL | MDS solver · MDS large | dominating set size (lower better): 111.50 -> 110.28 | Improved |
| use GFlowNet instead of ERDOS on large max-cut | MaxCut solver · MaxCut large | cut size: 2870.34 -> 2864.61 | Hurt |
| use GFlowNet sequential generation instead of one-pass probabilistic methods | CO solver · MC small | inference time: 0:42 -> 4:50 (large MC vs ERDOS 2:16) | Hurt |
| transition-based training instead of trajectory-based (ablation) | FL GFlowNet · MIS small | MIS size over epochs | Improved |
| use forward-looking (FL) intermediate signals instead of plain DB (ablation) | transition-based DB GFlowNet · MIS small | MIS size over epochs | Improved |
| vary temperature, exploration, and network architecture (ablation) | GFlowNet · MIS small | MIS size | No clear effect |
Closest papers by meaning
- Learning to Build Solutions in Stochastic Matching Problems Using Flows (Student Abstract) (AAAI 2024 · similarity 0.89)
- COMBHelper: A Neural Approach to Reduce Search Space for Graph Combinatorial Problems (AAAI 2024 · similarity 0.89)
- Learning to Explore and Exploit with GNNs for Unsupervised Combinatorial Optimization (ICLR 2025 · similarity 0.89)
- ROS: A GNN-based Relax-Optimize-and-Sample Framework for Max-$k$-Cut Problems (ICML 2025 · similarity 0.86)
- GOAL: A Generalist Combinatorial Optimization Agent Learner (ICLR 2025 · similarity 0.86)
- Order-Preserving GFlowNets (ICLR 2024 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.
