Finding Increasingly Large Extremal Graphs with AlphaZero and Tabu Search
Abstract
This work studies a central extremal graph theory problem inspired by a 1975 conjecture of Erdős, which aims to find graphs with a given size (number of nodes) that maximize the number of edges without having 3- or 4-cycles. We formulate this problem as a sequential decision-making problem and compare AlphaZero, a neural network-guided tree search, with tabu search, a heuristic local search method. Using either method, by introducing a curriculum---jump-starting the search for larger graphs using good graphs found at smaller sizes---we improve the state-of-the-art lower bounds for several sizes. Lastly, we propose a flexible graph-generation environment and a permutation-invariant network architecture for learning to search in the space of graphs.
Cite
Text
Mehrabian et al. "Finding Increasingly Large Extremal Graphs with AlphaZero and Tabu Search." NeurIPS 2023 Workshops: MATH-AI, 2023.Markdown
[Mehrabian et al. "Finding Increasingly Large Extremal Graphs with AlphaZero and Tabu Search." NeurIPS 2023 Workshops: MATH-AI, 2023.](https://mlanthology.org/neuripsw/2023/mehrabian2023neuripsw-finding/)BibTeX
@inproceedings{mehrabian2023neuripsw-finding,
title = {{Finding Increasingly Large Extremal Graphs with AlphaZero and Tabu Search}},
author = {Mehrabian, Abbas and Anand, Ankit and Kim, Hyunjik and Sonnerat, Nicolas and Berariu, Tudor and Balog, Matej and Comanici, Gheorghe and Lee, Andrew and Ruoss, Anian and Bulanova, Anna and Toyama, Daniel and Blackwell, Sam and Paredes, Bernardino Romera and Orseau, Laurent and Veličković, Petar and Naredla, Anurag Murty and Lee, Joonkyung and Wagner, Adam Zsolt and Precup, Doina},
booktitle = {NeurIPS 2023 Workshops: MATH-AI},
year = {2023},
url = {https://mlanthology.org/neuripsw/2023/mehrabian2023neuripsw-finding/}
}