Poster
in
Workshop: MATH-AI: The 3rd Workshop on Mathematical Reasoning and AI
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 Wagner · Doina Precup
Keywords: [ graph theory ] [ curriculum ] [ tabu search ] [ alphazero ]
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.