mlsanityData to 14 Oct 2026

Combinatorial Optimization with Graph Convolutional Networks and Guided Tree Search

arXiv 1810.10659 ↗First posted 25 Oct 2018cs.LG cs.AI stat.MLcited by 183

Not on the map. Why?

Abstract (arXiv)

We present a learning-based approach to computing solutions for certain NP-hard problems. Our approach combines deep learning techniques with useful algorithmic elements from classic heuristics. The central component is a graph convolutional network that is trained to estimate the likelihood, for each vertex in a graph, of whether this vertex is part of the optimal solution. The network is designed and trained to synthesize a diverse set of solutions, which enables rapid exploration of the solution space via tree search. The presented approach is evaluated on four canonical NP-hard problems and five datasets, which include benchmark satisfiability problems and real social network graphs with up to a hundred thousand nodes. Experimental results demonstrate that the presented approach substantially outperforms recent deep learning work, and performs on par with highly optimized state-of-the-art heuristic solvers for some NP-hard problems. Experiments indicate that our approach generalizes across datasets, and scales to graphs that are orders of magnitude larger than those used during training.

Key facts. Cited by 183 papers in the map (data through 14 Oct 2026). First posted on arXiv 25 Oct 2018.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 42; 2022: 38; 2023: 34; 2024: 34; 2025: 18; 2026: 17.

183 papers.

Sort:

By area:

  1. 2021Combinatorial optimization and reasoning with graph neural networkscited by 268
  2. 2023DIFUSCO: Graph-based Diffusion Solvers for Combinatorial Optimizationcited by 221
  3. 2021Learning to Optimize: A Primer and A Benchmarkcited by 208
  4. 2023Neural Combinatorial Optimization with Heavy Decoder: Toward Large Scale Generalizationcited by 142
  5. 2022DIMES: A Differentiable Meta Solver for Combinatorial Optimization Problemscited by 129
  6. 2022Sym-NCO: Leveraging Symmetricity for Neural Combinatorial Optimizationcited by 119
  7. 2021Combinatorial Optimization with Physics-Inspired Graph Neural Networkscited by 108
  8. 2021Efficient Active Search for Combinatorial Optimization Problemscited by 100
  9. 2021Deep Policy Dynamic Programming for Vehicle Routing Problemscited by 94
  10. 2021Matrix Encoding Networks for Neural Combinatorial Optimizationcited by 91
  11. 2023GLOP: Learning Global Partition and Local Construction for Solving Large-scale Routing Problems in Real-timecited by 85
  12. 2022Simulation-guided Beam Search for Neural Combinatorial Optimizationcited by 84
38 more
  1. 2023RL4CO: an Extensive Reinforcement Learning for Combinatorial Optimization Benchmarkcited by 71
  2. 2024A Diffusion Model Framework for Unsupervised Neural Combinatorial Optimizationcited by 59
  3. 2023Unsupervised Learning for Solving the Travelling Salesman Problemcited by 58
  4. 2022Pareto Set Learning for Neural Multi-objective Combinatorial Optimizationcited by 56
  5. 2021Graph Coarsening with Neural Networkscited by 55
  6. 2021Learning to schedule job-shop problems: Representation and policy learning using graph neural network and reinforcement learningcited by 52
  7. 2025Fast T2T: Optimization Consistency Speeds Up Diffusion-Based Training-to-Testing Solving for Combinatorial Optimizationcited by 45
  8. 2021Learning a Large Neighborhood Search Algorithm for Mixed Integer Programscited by 43
  9. 2024Can Graph Learning Improve Planning in LLM-based Agents?cited by 43
  10. 2021Device Sampling for Heterogeneous Federated Learning: Theory, Algorithms, and Implementationcited by 40
  11. 2023Let the Flows Tell: Solving Graph Combinatorial Optimization Problems with GFlowNetscited by 40
  12. 2022The Machine Learning for Combinatorial Optimization Competition (ML4CO): Results and Insightscited by 39
  13. 2022What's Wrong with Deep Learning in Tree Search for Combinatorial Optimizationcited by 37
  14. 2023Searching Large Neighborhoods for Integer Linear Programs with Contrastive Learningcited by 37
  15. 2021Generalization of Neural Combinatorial Solvers Through the Lens of Adversarial Robustnesscited by 35
  16. 2024Diffusion Models as Constrained Samplers for Optimization with Unknown Constraintscited by 35
  17. 2022Unsupervised Learning for Combinatorial Optimization with Principled Objective Relaxationcited by 32
  18. 2025Scalable Discrete Diffusion Samplers: Combinatorial Optimization and Statistical Physicscited by 29
  19. 2021A Bi-Level Framework for Learning to Solve Combinatorial Optimization on Graphscited by 26
  20. 2021Link Scheduling using Graph Neural Networkscited by 26
  21. 2022Can Hybrid Geometric Scattering Networks Help Solve the Maximum Clique Problem?cited by 25
  22. 2022On the Generalization of Neural Combinatorial Optimization Heuristicscited by 24
  23. 2023Meta-SAGE: Scale Meta-Learning Scheduled Adaptation with Guided Exploration for Mitigating Scale Shift on Combinatorial Optimizationcited by 23
  24. 2021Analytics and Machine Learning in Vehicle Routing Researchcited by 22
  25. 2022SurCo: Learning Linear Surrogates For Combinatorial Nonlinear Optimization Problemscited by 21
  26. 2025Pareto Set Learning for Multi-Objective Reinforcement Learningcited by 20
  27. 2021The Power of the Weisfeiler-Leman Algorithm for Machine Learning with Graphscited by 19
  28. 2022Annealed Training for Combinatorial Optimization on Graphscited by 18
  29. 2022A Survey on Influence Maximization: From an ML-Based Combinatorial Optimizationcited by 15
  30. 2022Learning to Solve Combinatorial Graph Partitioning Problems via Efficient Explorationcited by 14
  31. 2021Deep Reinforcement Learning for Combinatorial Optimization: Covering Salesman Problemscited by 13
  32. 2021Solve routing problems with a residual edge-graph attention neural networkcited by 13
  33. 2021Contingency-Aware Influence Maximization: A Reinforcement Learning Approachcited by 13
  34. 2022TransPath: Learning Heuristics For Grid-Based Pathfinding via Transformerscited by 13
  35. 2024CLDG: Contrastive Learning on Dynamic Graphscited by 13
  36. 2021Maximum Entropy Weighted Independent Set Pooling for Graph Neural Networkscited by 12
  37. 2021Enhancing Column Generation by a Machine-Learning-Based Pricing Heuristic for Graph Coloringcited by 12
  38. 2025Improving Generalization of Neural Combinatorial Optimization for Vehicle Routing Problems via Test-Time Projection Learningcited by 12

50 most cited of 183 All 183 (JSON)