Finding Increasingly Large Extremal Graphs with AlphaZero and Tabu Search
Authors: 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
IJCAI 2024 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | This work proposes a new learning-to-search benchmark and uses AI to discover new mathematical knowledge related to an open conjecture of Erd os (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 3or 4-cycles. We formulate this as a sequential decision-making problem and compare Alpha Zero, a neural network-guided tree search, with tabu search, a heuristic local search method. Using either method, by introducing a curriculum jumpstarting the search for larger graphs using good graphs found at smaller sizes we improve the stateof-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. |
| Researcher Affiliation | Collaboration | 1Google Deep Mind 2Imperial College London 3Yonsei University 4University of Bonn 5Worcester Polytechnic Institute |
| Pseudocode | Yes | Algorithm 1 Our version of tabu search Algorithm 2 Incremental tabu search (worker for size n) |
| Open Source Code | No | The paper states: "we release these graphs to the research community to aid further research: https://storage.googleapis. com/gdm_girth5_graphs/girth5_graphs.zip." This link refers to the generated graphs, not the source code for the Alpha Zero or Tabu Search implementations. |
| Open Datasets | Yes | As all the optimal graphs up to size 52 are known [Mc Kay, 2023], we use high-scoring graphs of smaller sizes (garnished with a suitable number of isolated nodes) as the initial graph and iterate. ... For incremental tabu search, we initialized Best Graphs[n] (see Algorithm 2) to contain the set of graphs published by [Mc Kay, 2023] (for n = 1, 2, . . . , 64), set the history size to 5, and the K in incremental tabu search to 4 it is important this is greater than 1. |
| Dataset Splits | No | The paper does not explicitly mention traditional train/validation/test dataset splits. The problem involves generating graphs and evaluating their properties, rather than splitting a fixed dataset. While training and evaluation of neural networks are discussed, the concept of a 'validation split' as commonly understood in supervised learning on fixed datasets is not applicable or stated. |
| Hardware Specification | No | The paper mentions a "distributed implementation of Alpha Zero with multiple processing units" and "32 parallel copies of tabu search", but does not provide specific details on the hardware used, such as CPU/GPU models or memory specifications. |
| Software Dependencies | No | The paper discusses the use of Alpha Zero and various network architectures (Pairformer, Res Net, GNNs) but does not provide specific version numbers for any software dependencies, libraries, or frameworks used in their implementation. |
| Experiment Setup | Yes | For each size n, we started the episodes in incremental Alpha Zero with one of the high-scoring graphs found by incremental tabu search at size n k, where k is chosen randomly between 1 and 4. ... A key hyperparameter is the episode length (the horizon). ... we set horizons to 80, 160, 240, 320, and 434, respectively. With incremental search, ... we experimented with horizon lengths of 30, 50 and 100 but found the results don t change much beyond 30. For tabu search, we tried various history sizes but size 5 worked best. For each size, we ran 32 parallel copies of tabu search for seven days, restarting every 1000 iterations and merging the results. For incremental tabu search, ... set the history size to 5, and the K in incremental tabu search to 4. |