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
Abstract
This work proposes a new learning-to-search benchmark and uses AI to discover new mathematical knowledge related to an open conjecture of Erdos (1975) in extremal graph theory. The problem is 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 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.
BibTeX
@inproceedings{ijcai2024p772,
title = {Finding Increasingly Large Extremal Graphs with AlphaZero and Tabu Search},
author = {Mehrabian, Abbas and Anand, Ankit and Kim, Hyunjik and Sonnerat, Nicolas and Balog, Matej and Comanici, Gheorghe and Berariu, Tudor and Lee, Andrew and Ruoss, Anian and Bulanova, Anna and Toyama, Daniel and Blackwell, Sam and Romera Paredes, Bernardino and Veličković, Petar and Orseau, Laurent and Lee, Joonkyung and Naredla, Anurag Murty and Precup, Doina and Wagner, Adam Zsolt},
booktitle = {Proceedings of the Thirty-Third International Joint Conference on
Artificial Intelligence, {IJCAI-24}},
publisher = {International Joint Conferences on Artificial Intelligence Organization},
editor = {Kate Larson},
pages = {6985--6993},
year = {2024},
month = {8},
note = {Main Track},
doi = {10.24963/ijcai.2024/772},
url = {https://doi.org/10.24963/ijcai.2024/772},
}