Research map / Graph learning / Graph algorithms and clustering
A Bi-Level Framework for Learning to Solve Combinatorial Optimization on Graphs
Runzhong Wang, Zhigang Hua, Gan Liu, Jiayi Zhang, Junchi Yan, Feng Qi, Shuang Yang, JUN ZHOU, Xiaokang Yang
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 PPO-guided graph modification followed by the Critical Path heuristic instead of the heuristic alone | DAG scheduling · TPC-H-50/100/150 | makespan (objective): 9821±1176 -> 8906±922; 16914±2499 -> 15193±2275; 24429±2484 -> 22371±2538 | Improved |
| Use PPO-guided graph modification and a heuristic rather than single-level PPO | DAG scheduling · TPC-H-50/100/150 | makespan (objective): 10578±2092 -> 8906±922; 17282±3821 -> 15193±2275; 24822±2707 -> 22371±2538 | Improved |
| Use PPO-guided graph modification instead of random graph modification | DAG scheduling · TPC-H-50/100/150 | makespan (objective): 9270±1143 -> 8906±922; 15580±2409 -> 15193±2275; 22930±2408 -> 22371±2538 | Improved |
| Use PPO-guided graph modification followed by IPFP instead of IPFP alone | GED · AIDS-20/30, AIDS-30/50, AIDS-50+ | edit distance (objective): 37.4±8.5 -> 29.1±8.9; 70.4±15.1 -> 61.1±14.2; 101.9±13.1 -> 77.0±19.4 | Improved |
| Use PPO-guided graph modification rather than single-level PPO | GED · AIDS-20/30, AIDS-30/50, AIDS-50+ | edit distance (objective): 56.5±14.4 -> 29.1±8.9; 110.0±19.2 -> 61.1±14.2; 183.9±16.9 -> 77.0±19.4 | Improved |
| Use PPO-guided graph modification instead of random graph modification | GED · AIDS-20/30, AIDS-30/50, AIDS-50+ | edit distance (objective): 33.1±9.0 -> 29.1±8.9; 66.0±15.2 -> 61.1±14.2; 82.4±20.3 -> 77.0±19.4 | Improved |
| Use bi-level graph modification with LKH3-fast instead of LKH3-fast alone | HCP · FHCP-500/600 | tour objective: 13.75 -> 8.45 | Improved |
| Use PPO-BiHyb rather than LKH3-accuracy | HCP · FHCP-500/600 | found Hamilton cycles: 20% -> 25% | Improved |
| Use PPO-BiHyb rather than LKH3-accuracy | HCP · FHCP-500/600 | tour objective: 6.25 -> 8.45 | Hurt |
Closest papers by meaning
- Towards General Algorithm Discovery for Combinatorial Optimization: Learning Symbolic Branching Policy from Bipartite Graph (ICML 2024 · similarity 0.90)
- COMBHelper: A Neural Approach to Reduce Search Space for Graph Combinatorial Problems (AAAI 2024 · similarity 0.90)
- Geometric Algorithms for Neural Combinatorial Optimization with Constraints (NeurIPS 2025 · similarity 0.88)
- Differentiable Quadratic Optimization For the Maximum Independent Set Problem (ICML 2025 · similarity 0.87)
- GOAL: A Generalist Combinatorial Optimization Agent Learner (ICLR 2025 · similarity 0.87)
- Tackling Prevalent Conditions in Unsupervised Combinatorial Optimization: Cardinality, Minimum, Covering, and More (ICML 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.
