Abstract
This work studies a central extremal graph theory problem inspired by a 1975 conjecture of Erdos, 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.
Authors
Ankit Anand, Matej Balog, Anna Bulanova, Gheorghe Comanici, Hyunjik Kim, Andrew Lee, Tudor Berariu*, Abbas Mehrabian, Laurent Orseau, Doina Precup, Anian Ruoss, Nicolas Sonnerat, Daniel Toyama, Petar Veličković, Sam Blackwell, Joonkyung Lee*, Anurag Murty Naredla*, Bernardino Romera Paredes, Adam Zsolt Wagner*
Venue
arXiv