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
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 G1
Graph G2
edge_colors
3
3
is_directed
True
True
allow_loops
True
False
Bitmask format for the out-neighborhoods
[8078000410092]
[861200902]
Bitmask format for the in-neighborhoods
[0810013041384]
[04092134]
Adjacency matrix format with color numbers
[2331232223130021]
[0020200221001120]
Table 1: A directed graph G1 with allowed loops and a directed graph G2 without allowed loops, both represented in all eight supported graph formats. A reduced format is always used when possible.
Graph G3
Graph G4
edge_colors
4
2
is_directed
False
False
allow_loops
True
False
Bitmask format for the out-neighborhoods
[214014020210]
[1224252314]
Bitmask format for the in-neighborhoods
[214014020210]
[1224252314]
Adjacency matrix format with color numbers
[102031214]
[0011000011100111110101110]
Table 2: An undirected graph G3 with allowed loops and an undirected graph G4 without allowed loops, both represented in all eight supported graph formats. A reduced format is always used when possible.
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 .
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 studies how agents learn sequential decisions from rewards and interaction, balancing exploration, performance, safety, and adaptation.
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× 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.
Franco Terranova, Guillermo Bernardez, Albert Cabellos-Aparicio +2
UL, LORIA, RESIST · UC Santa Barbara - UCSB · UPC +1
This paper explores the problem of finding the minimum zero-forcing set on undirected graphs and proposes an adapted machine-learning framework to solve the problem. The minimum zero-forcing set problem is a graph coloring problem where the color of an initial set of nodes propagates throughout a network. The set of nodes is zero-forcing if it forces all uncolored nodes to change color under the constraint of the color-change rule. There are several applications to this problem across different domains such as network science, network control, and designing logical circuits. Finding the minimum zero-forcing set is shown to be NP-hard. We propose a reinforcement learning framework, SD-ZFS, that adapts the S2V-DQN architecture to the ZFS problem. We train several models on this adapted framework and analyze the performance across graph datasets that have varying structures. We evaluate how the models trained on the framework generalize, scale, and transfer to different network types. The results demonstrate the effectiveness of the framework when compared against the optimal solution and greedy heuristic. We provide further insight into how the ZFS problem can be solved through machine-learning and the influence of network structure on the problem.
Steve Halley, Maurício Gruppi
Department of Computing Sciences, Villanova University Villanova, Pennsylvania, USA
Neural algorithmic reasoning (NAR) is a paradigm that trains neural networks to execute classic algorithms by supervised learning. Despite its successes, important limitations remain: inability to construct valid solutions without post-processing and to reason about multiple correct ones, poor performance on combinatorial NP-hard problems, and inapplicability to problems for which strong algorithms are not yet known. To address these limitations, we reframe the problem of learning algorithm trajectories as a Markov decision process, which imposes structure on the solution construction procedure and unlocks the powerful tools of imitation and reinforcement learning (RL). We propose the GNARL framework, encompassing the methodology to translate problem formulations from NAR to RL and a learning architecture suitable for a wide range of graph-based problems. We achieve high rates of reaching correct states on several CLRS-30 problems and performance matching or exceeding much narrower NAR approaches for NP-hard problems. Remarkably, GNARL remains applicable when no expert algorithm is available, though reward-driven learning can exhibit greater variability than direct supervision.
Alex Schutz, Victor-Alexandru Darvariu, Efimia Panagiotaki +2
Oxford Robotics Institute, University of Oxford · Stateful Robotics