RLGT: A reinforcement learning framework for extremal graph theory

Ivan Damnjanović; Uroš Milivojević; Irena Đorđević; Dragan Stevanović

cs.LGFeb 19, 2026

RLGT: A reinforcement learning framework for extremal graph theory

Authors: Ivan Damnjanović, Uroš Milivojević, Irena Đorđević, Dragan Stevanović

Organizations: Faculty of Electronic Engineering, University of Niš, Aleksandra Medvedeva 4, Niš, 18104, Serbia · Faculty of Mathematics, Natural Sciences and Information Technologies, University of Primorska, Glagoljaška 8, Koper, 6000, Slovenia · College of Integrative Studies, Abdullah Al Salem University, Firdous Street, Block 3, Khaldiya, 72303, Kuwait

Abstract

Reinforcement learning (RL) is a subfield of machine learning that focuses on developing models that can autonomously learn optimal decision-making strategies over time. In a recent pioneering paper, Wagner demonstrated how the Deep Cross-Entropy RL method can be applied to tackle various problems from extremal graph theory by reformulating them as combinatorial optimization problems. Subsequently, many researchers became interested in refining and extending the framework introduced by Wagner, thereby creating various RL environments specialized for graph theory. Moreover, a number of problems from extremal graph theory were solved through the use of RL. In particular, several inequalities concerning the Laplacian spectral radius of graphs were refuted, new lower bounds were obtained for certain Ramsey numbers, and contributions were made to the Turán-type extremal problem in which the forbidden structures are cycles of length three and four. Here, we present Reinforcement Learning for Graph Theory (RLGT), a novel RL framework that systematizes the previous work and provides support for both undirected and directed graphs, with or without loops, and with an arbitrary number of edge colors. The framework efficiently represents graphs and aims to facilitate future RL-based research in extremal graph theory through optimized computational performance and a clean and modular design.

Figures & tables

	Graph $G_{1}$	Graph $G_{2}$
edge_colors	3	3
is_directed	True	True
allow_loops	True	False
Bitmask format for the out-neighborhoods	$\begin{bmatrix}\begin{smallmatrix}8&8&0&0\\ 0&0&4&9\\ 7&0&10&2\end{smallmatrix}\end{bmatrix}$	$\begin{bmatrix}\begin{smallmatrix}8&12&0&0\\ 6&0&9&2\end{smallmatrix}\end{bmatrix}$
Bitmask format for the in-neighborhoods	$\begin{bmatrix}\begin{smallmatrix}0&0&0&3\\ 8&0&4&8\\ 1&13&1&4\end{smallmatrix}\end{bmatrix}$	$\begin{bmatrix}\begin{smallmatrix}0&0&2&3\\ 4&9&1&4\end{smallmatrix}\end{bmatrix}$
Adjacency matrix format with color numbers	$\rule{0.0pt}{17.22217pt}\begin{bmatrix}\begin{smallmatrix}2&2&2&0\\ 3&3&3&0\\ 3&2&1&2\\ 1&2&3&1\end{smallmatrix}\end{bmatrix}\rule[-12.05553pt]{0.0pt}{0.0pt}$	$\rule{0.0pt}{17.22217pt}\begin{bmatrix}\begin{smallmatrix}0&2&2&1\\ 0&0&1&1\\ 2&0&0&2\\ 0&2&0&0\end{smallmatrix}\end{bmatrix}\rule[-12.05553pt]{0.0pt}{0.0pt}$

Table 1: A directed graph

G_{1}

with allowed loops and a directed graph

G_{2}

without allowed loops, both represented in all eight supported graph formats. A reduced format is always used when possible.

	Graph $G_{3}$	Graph $G_{4}$
edge_colors	4	2
is_directed	False	False
allow_loops	True	False
Bitmask format for the out-neighborhoods	$\rule{0.0pt}{17.22217pt}\begin{bmatrix}\begin{smallmatrix}2&1&0\\ 1&4&2\\ 4&0&1\\ 0&2&0\end{smallmatrix}\end{bmatrix}\rule[-12.05553pt]{0.0pt}{0.0pt}$	$\begin{bmatrix}\begin{smallmatrix}12&24&25&23&14\end{smallmatrix}\end{bmatrix}$
Bitmask format for the in-neighborhoods	$\rule{0.0pt}{17.22217pt}\begin{bmatrix}\begin{smallmatrix}2&1&0\\ 1&4&2\\ 4&0&1\\ 0&2&0\end{smallmatrix}\end{bmatrix}\rule[-12.05553pt]{0.0pt}{0.0pt}$	$\begin{bmatrix}\begin{smallmatrix}12&24&25&23&14\end{smallmatrix}\end{bmatrix}$
Adjacency matrix format with color numbers	$\begin{bmatrix}\begin{smallmatrix}1&0&2\\ 0&3&1\\ 2&1&4\end{smallmatrix}\end{bmatrix}$	$\rule{0.0pt}{19.80551pt}\begin{bmatrix}\begin{smallmatrix}0&0&1&1&0\\ 0&0&0&1&1\\ 1&0&0&1&1\\ 1&1&1&0&1\\ 0&1&1&1&0\end{smallmatrix}\end{bmatrix}\rule[-14.63881pt]{0.0pt}{0.0pt}$

Table 2: An undirected graph

G_{3}

with allowed loops and an undirected graph

G_{4}

without allowed loops, both represented in all eight supported graph formats. A reduced format is always used when possible.

Panel of Figure 1 — Figure 1: The best score versus step count plot for the Deep Cross-Entropy agent based disproof of Conjecture 3.6 , and two counterexamples of order $16$ .

Panel of Figure 2 — Figure 2: The best score versus step count plot for the disproof of Conjecture 4.2 , and two counterexamples of order $14$ .

Figure 3: The best score versus step count plot for the unsuccessful attempt to disprove Conjecture 4.3 for the case

n=21

Reinforcement Learning

Reinforcement learning studies how agents learn sequential decisions from rewards and interaction, balancing exploration, performance, safety, and adaptation.

See all 1,717 papers

Projecting Latent RL Actions: Towards Generalizable and Scalable Graph Combinatorial Optimization
May 19, 2026Franco Terranova, Guillermo Bernardez, Albert Cabellos-Aparicio +2Latent Action Learning Combinatorial Optimization
UL, LORIA, RESIST · UC Santa Barbara - UCSB · UPC +1
Deep Reinforcement Learning for Minimum Zero-Forcing Sets
Jun 16, 2026Steve Halley, Maurício GruppiReinforcement Learning Combinatorial Optimization
Department of Computing Sciences, Villanova University Villanova, Pennsylvania, USA
Tackling GNARLy Problems: Graph Neural Algorithmic Reasoning Reimagined through Reinforcement Learning
Sep 23, 2025Alex Schutz, Victor-Alexandru Darvariu, Efimia Panagiotaki +2Graph Neural Networks Reinforcement Learning
Oxford Robotics Institute, University of Oxford · Stateful Robotics

May 19, 2026J/K move · Enter open · S save

Projecting Latent RL Actions: Towards Generalizable and Scalable Graph Combinatorial Optimization

Franco Terranova, Guillermo Bernardez, Albert Cabellos-Aparicio, Nina Miolane+1

UL, LORIA, RESIST · UC Santa Barbara - UCSB · UPC+1

Latent Action Learning Combinatorial Optimization RL for Combinatorial Optimization Neural Combinatorial Optimization

Open paper AskPDF arXiv

Graph combinatorial optimization (GCO) has attracted growing interest, as many NP-hard problems naturally admit graph formulations, yet their combinatorial explosion renders exact methods computationally intractable. Recent advances in Reinforcement Learning (RL) combined with Graph Neural Networks (GNNs) have significantly improved learning-based GCO solvers. However, existing approaches face limitations in both generalization across diverse graph instances and computational scalability as action spaces grow. To address both challenges, we introduce projection agents, a GCO methodology built on the Wolpertinger framework and adapted to a shared GNN-based latent space for observations and actions. These agents are trained to solve GCO problems by predicting a desired latent action in a single forward pass, which is subsequently decoded into a valid discrete action in the graph using the latent space. Across diverse benchmarks, our approach achieves up to 6.41

\times

faster inference and up to 75% better generalization than existing solutions using a simple nearest-neighbor decoding, while opening the door to strong RL performance in super-linear decision spaces with multiple interdependent variables. Finally, we release LaGCO-RL, a Python library that automates latent action-space construction and supports existing RL-GCO solutions, promoting reproducibility and adaptation to new GCO benchmarks.

Abstract

Reinforcement Learning

Explore similar work

Projecting Latent RL Actions: Towards Generalizable and Scalable Graph Combinatorial Optimization

Deep Reinforcement Learning for Minimum Zero-Forcing Sets

Tackling GNARLy Problems: Graph Neural Algorithmic Reasoning Reimagined through Reinforcement Learning