# Finding Increasingly Large Extremal Graphs with AlphaZero and Tabu Search

arXiv: https://arxiv.org/abs/2311.03583 · HTML: https://mlsanity.com/paper/2311.03583/

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Builds on 18 of its 43 references that are in the map.
- First posted on arXiv 6 Nov 2023.

## Builds on (most cited first, 18 of 18)

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Layer Normalization](https://mlsanity.com/paper/1607.06450/) (2016)
- [Solving Rubik's Cube with a Robot Hand](https://mlsanity.com/paper/1910.07113/) (2019)
- [Sim-to-Real Transfer of Robotic Control with Dynamics Randomization](https://mlsanity.com/paper/1710.06537/) (2017)
- [Generative Language Modeling for Automated Theorem Proving](https://mlsanity.com/paper/2009.03393/) (2020)
- [Curriculum Learning: A Survey](https://mlsanity.com/paper/2101.10382/) (2021)
- [Reverse Curriculum Generation for Reinforcement Learning](https://mlsanity.com/paper/1707.05300/) (2017)
- [HyperTree Proof Search for Neural Theorem Proving](https://mlsanity.com/paper/2205.11491/) (2022)
- [Monte Carlo Tree Search: A Review of Recent Modifications and Applications](https://mlsanity.com/paper/2103.04931/) (2021)
- [Everything is Connected: Graph Neural Networks](https://mlsanity.com/paper/2301.08210/) (2023)
- [Learning Montezuma's Revenge from a Single Demonstration](https://mlsanity.com/paper/1812.03381/) (2018)
- [Pointer Graph Networks](https://mlsanity.com/paper/2006.06380/) (2020)
- [Constructions in combinatorics via neural networks](https://mlsanity.com/paper/2104.14516/) (2021)
- [Playing Atari Games with Deep Reinforcement Learning and Human Checkpoint Replay](https://mlsanity.com/paper/1607.05077/) (2016)
- [Learning to Guide a Saturation-Based Theorem Prover](https://mlsanity.com/paper/2106.03906/) (2021)
- [Proving Theorems using Incremental Learning and Hindsight Experience Replay](https://mlsanity.com/paper/2112.10664/) (2021)
- [Levin Tree Search with Context Models](https://mlsanity.com/paper/2305.16945/) (2023)

## Built on by (most cited first, 8 of 8)

- [PatternBoost: Constructions in Mathematics with a Little Help from AI](https://mlsanity.com/paper/2411.00566/) (2024)
- [Machine Learning meets Algebraic Combinatorics: A Suite of Datasets Capturing Research-level Conjecturing Ability in Pure Mathematics](https://mlsanity.com/paper/2503.06366/) (2025)
- [Neural Discovery in Mathematics: Do Machines Dream of Colored Planes?](https://mlsanity.com/paper/2501.18527/) (2025)
- [A Systematization of the Wagner Framework: Graph Theory Conjectures and Reinforcement Learning](https://mlsanity.com/paper/2406.12667/) (2024)
- [Improved Upper Bounds for Slicing the Hypercube](https://mlsanity.com/paper/2602.16807/) (2026)
- [RLGT: A reinforcement learning framework for extremal graph theory](https://mlsanity.com/paper/2602.17276/) (2026)
- [The Art of Being Difficult: Combining Human and AI Strengths to Find Adversarial Instances for Heuristics](https://mlsanity.com/paper/2601.16849/) (2026)
- [Learning Minimally Rigid Graphs with High Realization Counts](https://mlsanity.com/paper/2605.12427/) (2026)

## Abstract (arXiv)

This work studies a central extremal graph theory problem inspired by a 1975 conjecture of ErdHos, 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.