mlsanityData to 7 Oct 2026

Finding Increasingly Large Extremal Graphs with AlphaZero and Tabu Search

arXiv 2311.03583 ↗First posted 6 Nov 2023cs.AI cs.DM cs.LGcited by 8

Not on the map. Why?

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.

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

Builds on

18 of 43 references.

References · 18

  1. 2015Deep Residual Learning for Image Recognitioncited by 51,809
  2. 2017Graph Attention Networkscited by 8,854
  3. 2016Layer Normalizationcited by 5,579
  4. 2019Solving Rubik's Cube with a Robot Handcited by 699
  5. 2017Sim-to-Real Transfer of Robotic Control with Dynamics Randomizationcited by 616
  6. 2020Generative Language Modeling for Automated Theorem Provingcited by 379
  7. 2021Curriculum Learning: A Surveycited by 257
  8. 2022HyperTree Proof Search for Neural Theorem Provingcited by 192
  9. 2017Reverse Curriculum Generation for Reinforcement Learningcited by 185
  10. 2021Monte Carlo Tree Search: A Review of Recent Modifications and Applicationscited by 158
  11. 2023Everything is Connected: Graph Neural Networkscited by 85
  12. 2018Learning Montezuma's Revenge from a Single Demonstrationcited by 76
6 more
  1. 2020Pointer Graph Networkscited by 52
  2. 2021Constructions in combinatorics via neural networkscited by 46
  3. 2016Playing Atari Games with Deep Reinforcement Learning and Human Checkpoint Replaycited by 22
  4. 2021Learning to Guide a Saturation-Based Theorem Provercited by 15
  5. 2021Proving Theorems using Incremental Learning and Hindsight Experience Replaycited by 13
  6. 2023Levin Tree Search with Context Modelscited by 7

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2024: 2; 2025: 2; 2026: 4.

8 papers.

  1. 2024PatternBoost: Constructions in Mathematics with a Little Help from AIcited by 32
  2. 2025Machine Learning meets Algebraic Combinatorics: A Suite of Datasets Capturing Research-level Conjecturing Ability in Pure Mathematicscited by 5
  3. 2025Neural Discovery in Mathematics: Do Machines Dream of Colored Planes?cited by 4
  4. 2024A Systematization of the Wagner Framework: Graph Theory Conjectures and Reinforcement Learningcited by 1
  5. 2026Improved Upper Bounds for Slicing the Hypercubecited by 1
  6. 2026RLGT: A reinforcement learning framework for extremal graph theorycited by 1
  7. 2026The Art of Being Difficult: Combining Human and AI Strengths to Find Adversarial Instances for Heuristicscited by 0
  8. 2026Learning Minimally Rigid Graphs with High Realization Countscited by 0