Reinforcement learning for graph theory, Parallelizing Wagner's approach

2025/09/01 by Bouffard, Alix, Breen, Jane
#Combinatorics (math.CO) #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG)

paper · doi:10.48550/arxiv.2509.01607

Abstract

Our work applies reinforcement learning to construct counterexamples concerning conjectured bounds on the spectral radius of the Laplacian matrix of a graph. We expand upon the re-implementation of Wagner's approach by Stevanovic et al. with the ability to train numerous unique models simultaneously and a novel redefining of the action space to adjust the influence of the current local optimum on the learning process.

Citations

• PatternBoost: Constructions in Mathematics with a Little Help from AI
• Reinforcement learning for graph theory, II. Small Ramsey numbers
• Reinforcement learning for graph theory, I. Reimplementation of Wagner's approach
• Tempestas ex machina: A review of machine learning methods for wavefront control
• A Nordhaus-Gaddum type problem for the normalized Laplacian spectrum and graph Cheeger constant
• A Simple Decentralized Cross-Entropy Method
• Constructions in combinatorics via neural networks
• Action Space Shaping in Deep Reinforcement Learning
• Population Based Training of Neural Networks
• Gaussian Error Linear Units (GELUs)
• Adam: A Method for Stochastic Optimization

Related

• Reinforcement learning for graph theory, I. Reimplementation of Wagner's approach
• A Systematization of the Wagner Framework: Graph Theory Conjectures and Reinforcement Learning
• The Laplacian in RL: Learning Representations with Efficient Approximations
• Towards Better Laplacian Representation in Reinforcement Learning with Generalized Graph Drawing
• Proper Laplacian Representation Learning