A Dataless Reinforcement Learning Approach to Rounding Hyperplane Optimization for Max-Cut
Gabriel Malikal, Ismail Alkhouri, Alvaro Velasquez, Adam M Alessio, Saiprasad Ravishankar · 2025
Read A Dataless Reinforcement Learning Approach to Rounding Hyperplane Optimization for Max-Cut by Gabriel Malikal, Ismail Alkhouri, Alvaro Velasquez, Adam M Alessio, Saiprasad Ravishankar (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-13405.txt.
Introduction
Gabriel Maliakal, Ismail Alkhouri, Alvaro Velasquez, Adam Alessio, and Saiprasad Ravishankar teach a reinforcement learning agent to round off a famous algorithm's answers better. Max-Cut asks for the split of a graph's nodes maximizing crossing edges, and exact solution is NP-hard. The Goemans-Williamson algorithm relaxes the problem to a semidefinite program, then rounds with a uniformly random hyperplane. That coin-flip rounding leaves value on the table.
Their agent learns, with no training data set, to choose better hyperplanes for the instance at hand. The search is framed as a non-episodic Markov decision process over rounding choices. Across large graphs of varied density and degree patterns, the learned rounding consistently beat the classical one. Data-hungry learning methods often fail to generalize across graph families; optimizing per-instance sidesteps the dataset entirely.
Catalog record
| CREATOR | Gabriel Malikal, Ismail Alkhouri, Alvaro Velasquez, Adam M Alessio, Saiprasad Ravishankar |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 32 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2505-13405
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
A Dataless Reinforcement Learning Approach to Rounding Hyperplane Optimization for Max-Cut Gabriel Malikal, Ismail Alkhouri, Alvaro Velasquez, Adam M Alessio, Saiprasad Ravishankar Abstract The Maximum Cut (MaxCut) problem is NP-Complete, and obtaining its optimal solution is NP-hard in the worst case. As a result, heuristic-based algorithms are commonly used, though their design often requires significant domain expertise. More recently, learning-based methods trained on large (un)labeled datasets have been proposed; however, these approaches often struggle with generalizability and scalability. A well-known approximation algorithm for MaxCut is the Goemans-Williamson (GW) algorithm, which relaxes the Quadratic Unconstrained Binary Optimization (QUBO) formulation into a semidefinite program (SDP). The GW algorithm then applies hyperplane rounding by uniformly sampling a random hyperplane to convert the SDP solution into binary node assignments. In this paper, we propose a training-data-free approach based on a non-episodic reinforcement learning formulation, in which an agent learns to select improved rounding hyperplanes that yield better cuts than those produced by the GW algorithm. By optimizing over a Markov Decision Process (MDP), our method consistently achieves better cuts across large-scale graphs with varying densities and degree distributions. 1 Introduction The Maximum Cut (MaxCut) problem is one of Karp’s classical NP-complete problems [ 1 ] . Given a graph G=(V,E) , where V is the set of vertices and E is the set of edges, the MaxCut problem seeks a subset of nodes S\subset V such that the number of edges between S and its complement is maximized. MaxCut has numerous applications across domains such as image segmentation [ 2 , 3 ] , VLSI design [ 4 ] , and network robustness [ 5 ] . Several approaches have been proposed to tackle MaxCut, including exact solvers based on Integer Linear Programming (ILP)—which employ Branch-and-Bound methods [ 6 ] —and Quadratic Unconstrained Binary Optimization (QUBO). However, due to their reliance on integer variables, ILP and QUBO formulations typically scale poorly, often requiring prohibitively long computation times on large and/or dense graphs. To address these scalability issues, approximate methods have been introduced. For instance, the QUBO formulation of MaxCut can be relaxed into a semidefinite program (SDP). While SDPs are convex and solvable in polynomial time, their solutions require rounding techniques to recover a valid cut from the continuous solution. A notable example is the Goemans-Williamson (GW) algorithm [ 7 ] , which offers a well-known approximation guarantee. Heuristic-based approaches such as Breakout Local Search (BLS) [ 8 ] have also been developed, though they lack theoretical guarantees and often require domain-specific tuning. More recently, learning-based and data-centric methods have been proposed for MaxCut and other combinatorial optimization problems [ 9 , 10 , 11 , 12 ] . These include supervised, unsupervised, and reinforcement learning (RL) approaches. However, such methods often require a large number of (un)labeled training graphs and may suffer from limited generalization and poor scalability to out-of-distribution instances. Motivated by ( i ) the desire to eliminate reliance on training data, and ( ii ) the goal of surpassing the GW bound, we propose an RL-based solver that operates on the SDP solution. Our method uses a fully connected, multi-head neural network and does not depend on heuristics or training datasets. We compare our method to a GPU-accelerated GW implementation that employs parallel hyperplane sampling for rounding, which we refer to as parallelized GW (pGW). Contributions: We introduce a self-supervised, non-episodic reinforcement learning algorithm that operates without any training graphs. Our method learns to generate hyperplanes that maximize the cut value by modeling a Gaussian distribution over hyperplanes, initialized from a uniform distribution and guided by the SDP solution from the Goemans-Williamson (GW) formulation. This Gaussian is parameterized by a fully connected, multi-head neural network with a value head. The learning process is framed as a Markov Decision Process (MDP), where new hyperplanes are sampled based on the current policy and used to round the SDP solution. An Actor-Critic network is trained using Proximal Policy Optimization (PPO) [ 13 ] to improve the policy. We demonstrate that our method consistently outperforms the parallelized Goemans-Williamson baseline (pGW) on large graphs from the Gset dataset as well as on synthetic Erdős-Rényi (ER) graphs across different densities. 2 Background & Motivation Let an unweighted and undirected graph be defined as G(V,E) , where V=\{1,...,n\} is the set of nodes and E\subset V\times V (with |E|=m ) is the set of edges that consists of pairs of vertices that are connected by an edge. The Maximum Cut (MaxCut) problem is formally defined next. Definition 1 (Maximum Cut (MaxCut)) . Given an undirected and unweighted graph G=(V,E) , the MaxCut problem aims to partition V into two disjoint subsets S and S^{c}=V\setminus S such that the total number of edges crossing the cut (i.e., edges with one end in S and the other in S^{c} ) is maximized. Define a vector \mathbf{x}\in\{0,1\}^{n} such that every entry x_{i} corresponds to a node i\in V , and vector \mathbf{y}\in\{0,1\}^{m} is such that every entry y_{i,j} corresponds to an edge (i,j)\in E where we consider each tuple (i,j) to be an index for each element in y . Then, the ILP of the MaxCut problem is given as \displaystyle\max_{\mathbf{x}\in\{0,1\}^{n},\mathbf{y}\in\{0,1\}^{m}}\sum_{(i,j)\in E} \displaystyle y_{i,j}\quad\text{s.t.}\quad y_{i,j}\leq x_{i}+x_{j},\quad y_{i,j}\leq 2-x_{i}-x_{j},\quad\forall(i,j)\in E\>. ( ILP ) In the ( ILP ), there are n+m binary variables. An alternative integer problem, which has only n variables, is the following MaxCut Quadratic Unconstrained Binary Optimization (QUBO). \displaystyle\max_{\mathbf{x}\in\{-1,1\}^{n}}\frac{1}{2}\sum_{(i,j)\in E}(1-x_{i}x_{j})\>. ( QUBO ) We note that the cut value in graph G of some binary vector \mathbf{x}\in\{-1,1\}^{n} is given by the objective function in ( QUBO ). As both of the above optimization problems are binary programs, they do not scale well as n and m increase. Therefore, alternative approaches have been explored such as the MaxCut SDP relaxation we describe next. 2.1 MaxCut SDP & The GW Algorithm The pioneering work in [ 7 ] introduced the MaxCut SDP formulation for which they first define each node i\in V by a multi-dimensional unit norm vector, \mathbf{x}_{i}\in\mathbb{S}^{n-1} , where \mathbb{S}^{n-1} denotes the surface of the n -dimensional unit sphere. Then, the MaxCut SDP optimization problem is \displaystyle\max_{\mathbf{x}_{i}\in\mathbb{S}^{n-1},\forall i\in V}\frac{1}{2}\sum_{(i,j)\in E}(1-\mathbf{x}_{i}\cdot\mathbf{x}_{j})\>, ( SDP ) where \mathbf{x}_{i}\cdot\mathbf{x}_{j} denotes the dot product between the unit-norm vectors \mathbf{x}_{i} and \mathbf{x}_{j} . Although SDPs are convex optimization programs and can be solved in polynomial time, the solution of ( SDP ), which we denote by \mathbf{x}_{i}^{*},\forall i\in V , do not directly correspond to a MaxCut solution on the graph 1 1 1 We note that ( SDP ) is convex, but not strongly convex. This means that while there may exist a unique minimum objective value, there could exist multiple minimizers. . Therefore, rounding techniques (or approximation methods) are used to map \mathbf{x}_{i}^{*} to actual MaxCut solutions. The most notable approximation algorithm is the Goemans-Williamson (GW) Algorithm [ 7 ] (also known as random sampling in Fig 3(a) and Fig 3(b) ). The GW algorithm procedure consists of first obtaining a random hyperplane through the origin whose unit normal vector is sampled from the uniform distribution over the unit sphere. This normal is denoted as \mathbf{r} with \mathbf{r}\sim\mathbb{U}(\mathbb{S}^{n-1}) . The hyperplane is then used to partition the indices of the vectors from