Finding Increasingly Large Extremal Graphs with AlphaZero and Tabu
  Search
Abbas Mehrabian Ankit Anand Hyunjik Kim Nicolas Sonnerat Matej Balog Gheorghe Comanici Tudor Berariu Andrew Lee Anian Ruoss Anna Bulanova Daniel Toyama Sam Blackwell Bernardino Romera Paredes Petar Veličković Laurent Orseau Joonkyung Lee Anurag Murty Naredla Doina Precup Adam Zsolt Wagner
This work studies a central extremal graph theory problem inspired by a 1975
conjecture of Erd\H{o}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. We
also propose a flexible graph-generation environment and a
permutation-invariant network architecture for learning to search in the space
of graphs.