@inproceedings{
mehrabian2023finding,
title={Finding Increasingly Large Extremal Graphs with AlphaZero and Tabu Search},
author={Abbas Mehrabian and Ankit Anand and Hyunjik Kim and Nicolas Sonnerat and Tudor Berariu and Matej Balog and Gheorghe Comanici and Andrew Lee and Anian Ruoss and Anna Bulanova and Daniel Toyama and Sam Blackwell and Bernardino Romera Paredes and Laurent Orseau and Petar Veli{\v{c}}kovi{\'c} and Anurag Murty Naredla and Joonkyung Lee and Adam Zsolt Wagner and Doina Precup},
booktitle={The 3rd Workshop on Mathematical Reasoning and AI at NeurIPS'23},
year={2023},
url={https://openreview.net/forum?id=woQ9G0bzBM}
}
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.
Finding Increasingly Large Extremal Graphs with AlphaZero and Tabu Search
Abbas Mehrabian Ankit Anand Hyunjik Kim Nicolas Sonnerat Tudor Berariu Matej Balog Gheorghe Comanici Andrew Lee Anian Ruoss Anna Bulanova Daniel Toyama Sam Blackwell Bernardino Romera Paredes Laurent Orseau Petar Veličković Anurag Murty Naredla Joonkyung Lee Adam Zsolt Wagner Doina Precup