Discamus continentiam augere, luxuriam coercere
Home -> Publications
Home
  Publications
    
edited volumes
  Awards
  Research
  Teaching
  Miscellaneous
  Full CV [pdf]
  BLOG






  Events








  Past Events





Publications of Torsten Hoefler
Lukas Gianinazzi, Maximilian Fries, Nikoli Dryden, Tal Ben-Nun, Maciej Besta, Torsten Hoefler:

 Learning Combinatorial Node Labeling Algorithms

(arXiv:2106.03594. Jun. 2021)

Abstract

We present a novel neural architecture to solve graph optimization problems where the solution consists of arbitrary node labels, allowing us to solve hard problems like graph coloring. We train our model using reinforcement learning, specifically policy gradients, which gives us both a greedy and a probabilistic policy. Our architecture builds on a graph attention network and uses several inductive biases to improve solution quality. Our learned deterministic heuristics for graph coloring give better solutions than classical degree-based greedy heuristics and only take seconds to apply to graphs with tens of thousands of vertices. Moreover, our probabilistic policies outperform all greedy state-of-the-art coloring baselines and a machine learning baseline. Finally, we show that our approach also generalizes to other problems by evaluating it on minimum vertex cover and outperforming two greedy heuristics.

Documents

download article:     
 

BibTeX

@article{gianinazzi2021learning,
  author={Lukas Gianinazzi and Maximilian Fries and Nikoli Dryden and Tal Ben-Nun and Maciej Besta and Torsten Hoefler},
  title={{Learning Combinatorial Node Labeling Algorithms}},
  journal={arXiv:2106.03594},
  year={2021},
  month={Jun.},
  source={http://www.unixer.de/~htor/publications/},
}


serving: 44.220.184.63:56272© Torsten Hoefler