mlsanityData to 7 Oct 2026

Maximum Independent Set: Self-Training through Dynamic Programming

arXiv 2310.18672 ↗First posted 28 Oct 2023cs.LG cs.DMcited by 5

Not on the map. Why?

Abstract (arXiv)

This work presents a graph neural network (GNN) framework for solving the maximum independent set (MIS) problem, inspired by dynamic programming (DP). Specifically, given a graph, we propose a DP-like recursive algorithm based on GNNs that firstly constructs two smaller sub-graphs, predicts the one with the larger MIS, and then uses it in the next recursive call. To train our algorithm, we require annotated comparisons of different graphs concerning their MIS size. Annotating the comparisons with the output of our algorithm leads to a self-training process that results in more accurate self-annotation of the comparisons and vice versa. We provide numerical evidence showing the superiority of our method vs prior methods in multiple synthetic and real-world datasets.

Key facts. Cited by 5 papers in the map (data through 7 Oct 2026). Builds on 32 of its 59 references that are in the map. First posted on arXiv 28 Oct 2023.

Builds on

32 of 59 references.

References · 32

  1. 2017Attention Is All You Needcited by 59,932
  2. 2015Deep Residual Learning for Image Recognitioncited by 51,809
  3. 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,282
  4. 2017Graph Attention Networkscited by 8,854
  5. 2016Layer Normalizationcited by 5,579
  6. 2018How Powerful are Graph Neural Networks?cited by 4,355
  7. 2016Gaussian Error Linear Units (GELUs)cited by 3,431
  8. 2019A Comprehensive Survey on Graph Neural Networkscited by 2,906
  9. 2015Pointer Networkscited by 882
  10. 2018Link Prediction Based on Graph Neural Networkscited by 829
  11. 2020TUDataset: A collection of benchmark datasets for learning with graphscited by 718
  12. 2018Reinforcement Learning for Solving the Vehicle Routing Problemcited by 327
20 more
  1. 2019Exact Combinatorial Optimization with Graph Convolutional Neural Networkscited by 313
  2. 2021Neural Bellman-Ford Networks: A General Graph Neural Network Framework for Link Predictioncited by 273
  3. 2019A Fair Comparison of Graph Neural Networks for Graph Classificationcited by 244
  4. 2020Reinforcement Learning for Combinatorial Optimization: A Surveycited by 235
  5. 2018Combinatorial Optimization with Graph Convolutional Networks and Guided Tree Searchcited by 182
  6. 2020Learning to Dispatch for Job Shop Scheduling via Deep Reinforcement Learningcited by 139
  7. 2020Erdos Goes Neural: an Unsupervised Learning Framework for Combinatorial Optimization on Graphscited by 115
  8. 2021Combinatorial Optimization with Physics-Inspired Graph Neural Networkscited by 107
  9. 2018Learning to Solve NP-Complete Problems - A Graph Neural Network for Decision TSPcited by 58
  10. 2020Learning What to Defer for Maximum Independent Setscited by 53
  11. 2019Graph Colouring Meets Deep Learning: Effective Graph Neural Network Models for Combinatorial Problemscited by 40
  12. 2022Unsupervised Learning for Combinatorial Optimization with Principled Objective Relaxationcited by 32
  13. 2021ScheduleNet: Learn to solve multi-agent scheduling problems with reinforcement learningcited by 31
  14. 2020It's Not What Machines Can Learn, It's What We Cannot Teachcited by 29
  15. 2022Graph Coloring with Physics-Inspired Graph Neural Networkscited by 29
  16. 2017Revised Note on Learning Algorithms for Quadratic Assignment with Graph Neural Networkscited by 28
  17. 2023Unsupervised Learning for Combinatorial Optimization Needs Meta-Learningcited by 19
  18. 2021Deep Reinforcement Learning for Combinatorial Optimization: Covering Salesman Problemscited by 13
  19. 2022Learning to Solve Multiple-TSP with Time Window and Rejections via Deep Reinforcement Learningcited by 8
  20. 2020Solve Traveling Salesman Problem by Monte Carlo Tree Search and Deep Neural Networkcited by 7

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2024: 3; 2025: 1; 2026: 1.

5 papers.

  1. 2024Learning-augmented Maximum Independent Setcited by 11
  2. 2024DISCO: Efficient Diffusion Solver for Large-Scale Combinatorial Optimization Problemscited by 10
  3. 2024Harmonizing Human Insights and AI Precision: Hand in Hand for Advancing Knowledge Graph Taskcited by 0
  4. 2025Unsupervised Learning of Local Updates for Maximum Independent Set in Dynamic Graphscited by 0
  5. 2026Dual-GNN Multilevel Coarsening for Maximum Independent Setcited by 0