تقرير
Finding Increasingly Large Extremal Graphs with AlphaZero and Tabu Search
| العنوان: | Finding Increasingly Large Extremal Graphs with AlphaZero and Tabu Search |
|---|---|
| المؤلفون: | Mehrabian, Abbas, Anand, Ankit, Kim, Hyunjik, Sonnerat, Nicolas, Balog, Matej, Comanici, Gheorghe, Berariu, Tudor, Lee, Andrew, Ruoss, Anian, Bulanova, Anna, Toyama, Daniel, Blackwell, Sam, Paredes, Bernardino Romera, Veličković, Petar, Orseau, Laurent, Lee, Joonkyung, Naredla, Anurag Murty, Precup, Doina, Wagner, Adam Zsolt |
| سنة النشر: | 2023 |
| المجموعة: | Computer Science |
| مصطلحات موضوعية: | Computer Science - Artificial Intelligence, Computer Science - Discrete Mathematics, Computer Science - Machine Learning |
| الوصف: | 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. Comment: To appear in the proceedings of IJCAI 2024. First three authors contributed equally, last two authors made equal senior contribution |
| نوع الوثيقة: | Working Paper |
| URL الوصول: | http://arxiv.org/abs/2311.03583 |
| رقم الأكسشن: | edsarx.2311.03583 |
| قاعدة البيانات: | arXiv |
| الوصف غير متاح. |