# A Bi-Level Framework for Learning to Solve Combinatorial Optimization on Graphs

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

## Key facts

- Cited by 26 papers in the map (data through 14 Oct 2026).
- Builds on 31 of its 80 references that are in the map.
- First posted on arXiv 9 Jun 2021.

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

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017)
- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Mask R-CNN](https://mlsanity.com/paper/1703.06870/) (2017)
- [Playing Atari with Deep Reinforcement Learning](https://mlsanity.com/paper/1312.5602/) (2013)
- [Trust Region Policy Optimization](https://mlsanity.com/paper/1502.05477/) (2015)
- [Fast Graph Representation Learning with PyTorch Geometric](https://mlsanity.com/paper/1903.02428/) (2019)
- [Pointer Networks](https://mlsanity.com/paper/1506.03134/) (2015)
- [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)
- [Learning Combinatorial Optimization Algorithms over Graphs](https://mlsanity.com/paper/1704.01665/) (2017)
- [Exact Combinatorial Optimization with Graph Convolutional Neural Networks](https://mlsanity.com/paper/1906.01629/) (2019)
- [An Efficient Graph Convolutional Network Technique for the Travelling Salesman Problem](https://mlsanity.com/paper/1906.01227/) (2019)
- [Graph Matching Networks for Learning the Similarity of Graph Structured Objects](https://mlsanity.com/paper/1904.12787/) (2019)
- [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)
- [Generalize a Small Pre-trained Model to Arbitrarily Large TSP Instances](https://mlsanity.com/paper/2012.10658/) (2020)
- [Investigating Bi-Level Optimization for Learning and Vision from a Unified Perspective: A Survey and Beyond](https://mlsanity.com/paper/2101.11517/) (2021)
- [Learning to Dispatch for Job Shop Scheduling via Deep Reinforcement Learning](https://mlsanity.com/paper/2010.12367/) (2020)
- [Learning Scheduling Algorithms for Data Processing Clusters](https://mlsanity.com/paper/1810.01963/) (2018)
- [Discriminative Embeddings of Latent Variable Models for Structured Data](https://mlsanity.com/paper/1603.05629/) (2016)
- [Erdos Goes Neural: an Unsupervised Learning Framework for Combinatorial Optimization on Graphs](https://mlsanity.com/paper/2006.10643/) (2020)
- [Reinforcement Learning for Integer Programming: Learning to Cut](https://mlsanity.com/paper/1906.04859/) (2019)
- [SimGNN: A Neural Network Approach to Fast Graph Similarity Computation](https://mlsanity.com/paper/1808.05689/) (2018)
- [Neural Graph Matching Network: Learning Lawler's Quadratic Assignment Problem with Extension to Hypergraph and Multiple-graph Matching](https://mlsanity.com/paper/1911.11308/) (2019)
- [Search to aggregate neighborhood for graph neural network](https://mlsanity.com/paper/2104.06608/) (2021)
- [Combinatorial Learning of Graph Edit Distance via Dynamic Embedding](https://mlsanity.com/paper/2011.15039/) (2020)
- [Graph Edit Distance Reward: Learning to Edit Scene Graph](https://mlsanity.com/paper/2008.06651/) (2020)
- [TAP-Net: Transport-and-Pack using Reinforcement Learning](https://mlsanity.com/paper/2009.01469/) (2020)

## Built on by (most cited first, 26 of 26)

- [DIFUSCO: Graph-based Diffusion Solvers for Combinatorial Optimization](https://mlsanity.com/paper/2302.08224/) (2023)
- [DIMES: A Differentiable Meta Solver for Combinatorial Optimization Problems](https://mlsanity.com/paper/2210.04123/) (2022)
- [Towards Omni-generalizable Neural Methods for Vehicle Routing Problems](https://mlsanity.com/paper/2305.19587/) (2023)
- [Generalization of Neural Combinatorial Solvers Through the Lens of Adversarial Robustness](https://mlsanity.com/paper/2110.10942/) (2021)
- [Unsupervised Learning for Combinatorial Optimization with Principled Objective Relaxation](https://mlsanity.com/paper/2207.05984/) (2022)
- [One Model, Any CSP: Graph Neural Networks as Fast Global Search Heuristics for Constraint Satisfaction](https://mlsanity.com/paper/2208.10227/) (2022)
- [Cross-Problem Learning for Solving Vehicle Routing Problems](https://mlsanity.com/paper/2404.11677/) (2024)
- [LinSATNet: The Positive Linear Satisfiability Neural Networks](https://mlsanity.com/paper/2407.13917/) (2024)
- [iSLAM: Imperative SLAM](https://mlsanity.com/paper/2306.07894/) (2023)
- [Neural Topological Ordering for Computation Graphs](https://mlsanity.com/paper/2207.05899/) (2022)
- [LeNSE: Learning To Navigate Subgraph Embeddings for Large-Scale Combinatorial Optimisation](https://mlsanity.com/paper/2205.10106/) (2022)
- [Automatic MILP Solver Configuration By Learning Problem Similarities](https://mlsanity.com/paper/2307.00670/) (2023)
- [EFormer: An Effective Edge-based Transformer for Vehicle Routing Problems](https://mlsanity.com/paper/2506.16428/) (2025)
- [Improving the interpretability of GNN predictions through conformal-based graph sparsification](https://mlsanity.com/paper/2404.12356/) (2024)
- [Learning Reward and Policy Jointly from Demonstration and Preference Improves Alignment](https://mlsanity.com/paper/2406.06874/) (2024)
- [torchmSAT: A GPU-Accelerated Approximation To The Maximum Satisfiability Problem](https://mlsanity.com/paper/2402.03640/) (2024)
- [Adaptive Stabilization Based on Machine Learning for Column Generation](https://mlsanity.com/paper/2405.11198/) (2024)
- [Learning to Solve Combinatorial Optimization under Positive Linear Constraints via Non-Autoregressive Neural Networks](https://mlsanity.com/paper/2409.04495/) (2024)
- [Lifelong Learner: Discovering Versatile Neural Solvers for Vehicle Routing Problems](https://mlsanity.com/paper/2508.11679/) (2025)
- [Detecting Small Query Graphs in A Large Graph via Neural Subgraph Search](https://mlsanity.com/paper/2207.10305/) (2022)
- [A hybrid deep-learning-metaheuristic framework for bi-level network design problems](https://mlsanity.com/paper/2303.06024/) (2023)
- [A Learning Method with Gap-Aware Generation for Heterogeneous DAG Scheduling](https://mlsanity.com/paper/2603.23249/) (2026)
- [A General Framework for Evaluating Robustness of Combinatorial Optimization Solvers on Graphs](https://mlsanity.com/paper/2201.00402/) (2021)
- [Bi-level RL-Heuristic Optimization for Real-world Winter Road Maintenance](https://mlsanity.com/paper/2602.24097/) (2026)
- [Projecting Latent RL Actions: Towards Generalizable and Scalable Graph Combinatorial Optimization](https://mlsanity.com/paper/2605.19721/) (2026)
- [Neural Certificate Pricing for Combinatorial Optimization Problems](https://mlsanity.com/paper/2607.01185/) (2026)

## Abstract (arXiv)

Combinatorial Optimization (CO) has been a long-standing challenging research topic featured by its NP-hard nature. Traditionally such problems are approximately solved with heuristic algorithms which are usually fast but may sacrifice the solution quality. Currently, machine learning for combinatorial optimization (MLCO) has become a trending research topic, but most existing MLCO methods treat CO as a single-level optimization by directly learning the end-to-end solutions, which are hard to scale up and mostly limited by the capacity of ML models given the high complexity of CO. In this paper, we propose a hybrid approach to combine the best of the two worlds, in which a bi-level framework is developed with an upper-level learning method to optimize the graph (e.g. add, delete or modify edges in a graph), fused with a lower-level heuristic algorithm solving on the optimized graph. Such a bi-level approach simplifies the learning on the original hard CO and can effectively mitigate the demand for model capacity. The experiments and results on several popular CO problems like Directed Acyclic Graph scheduling, Graph Edit Distance and Hamiltonian Cycle Problem show its effectiveness over manually designed heuristics and single-level learning methods.