Breaking conjectures in combinatorics with graph neural networks and reinforcement learning

Department's Seminar
25 May 2023
Start time 
2:00 pm
Polo Ferrari 2 - Via Sommarive 9, Povo (Trento)
Room B112 – Povo2 and via Zoom (please contact for credentials)
Target audience: 
University community
UniTrento students
Registration email: 
Contact person: 
Prof. Luigi Amedeo Bianchi
Contact details: 
Università degli Studi Trento 38123 Povo (TN) - Staff Dipartimento di Matematica
+39 04 61/281508-1625-1701-1980-3898-1511
Francesco Morandin (University of Parma)


I will present some recent results on using reinforcement learning to find explicit constructions and counterexamples to several open conjectures in graph theory. Reinforcement learning is a branch of machine learning that deals with learning optimal actions in an environment based on feedback and rewards. I will explain how a reinforcement learning algorithm can be used to generate graphs that satisfy or violate certain properties. I will also discuss how using graph neural networks instead of fully connected networks can significantly improve the performance and scalability of this approach. Graph neural networks are neural networks that operate on graph structures and can capture their features and relations. This talk is based on the paper Constructions in combinatorics via neural networks by Adam Zsolt Wagner and is a joint work with Renato Faraone.