Graph-GRPO: Training Graph Flow Models with Reinforcement Learning

Baoheng Zhu, Deyu Bo, Delvin Ce Zhang, Xiao Wang · 2026

Read Graph-GRPO: Training Graph Flow Models with Reinforcement Learning by Baoheng Zhu, Deyu Bo, Delvin Ce Zhang, Xiao Wang (2026) 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-2603-10395.txt.

Introduction

Baoheng Zhu and co-authors present Graph-GRPO, a way to train graph flow models with online feedback toward rewards that can be checked. Aligning such generators with human preferences or task goals is hard, so two ideas carry the work. First, an analytic form for the transition probability replaces Monte Carlo sampling, making rollouts fully differentiable. Second, a refinement step perturbs chosen nodes and edges, then regenerates them for local exploration. On synthetic and molecular tasks the method sets leading scores, beating rival approaches and classic genetic algorithms.

Catalog record

CREATORBaoheng Zhu, Deyu Bo, Delvin Ce Zhang, Xiao Wang
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE67659
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2603.10395

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Graph-GRPO: Training Graph Flow Models with Reinforcement Learning Baoheng Zhu, Deyu Bo, Delvin Ce Zhang, Xiao Wang Abstract Graph generation is a fundamental task with broad applications, such as drug discovery. Recently, discrete flow matching-based graph generation, a.k.a . , graph flow model (GFM), has emerged due to its superior performance and flexible sampling. However, effectively aligning GFMs with complex human preferences or task-specific objectives remains a significant challenge. In this paper, we propose Graph-GRPO, an online reinforcement learning (RL) framework for training GFMs under verifiable rewards. Our method makes two key contributions: (1) We derive an analytical expression for the transition probability of GFMs, replacing the Monte Carlo sampling and enabling fully differentiable rollouts for RL training; (2) We propose a refinement strategy that randomly perturbs specific nodes and edges in a graph, and regenerates them, allowing for localized exploration and self-improvement of generation quality. Extensive experiments on both synthetic and real datasets demonstrate the effectiveness of Graph-GRPO. With only 50 denoising steps, our method achieves 95.0% and 97.5% Valid-Unique-Novelty scores on the planar and tree datasets, respectively. Moreover, Graph-GRPO achieves state-of-the-art performance on the molecular optimization tasks, outperforming graph-based and fragment-based RL methods as well as classic genetic algorithms. † † affiliationnotice: Equal contribution 1 Introduction (a) Scaffold Hopping (b) Valsartan SMARTS Figure 1 : Reward curves on two molecular optimization tasks. We use DeFoG ( 33 ) as the base model. As the number of oracle calls increases, the score of RL-optimized models gradually rises, while the base model remains almost unchanged. In the tasks with highly selective reward, e.g . , Valsartan SMARTS, refining promising candidates is more effective than de novo generation. Recent advances in discrete generative modeling ( 1 ; 13 ) have given rise to a wide range of graph generation methods ( 39 ; 42 ; 36 ) . Among them, discrete flow matching-based graph generation methods, commonly referred to as graph flow models (GFMs), have recently attracted increasing attention. By decoupling the training objective from sampling, GFMs enable more effective generative modeling and flexible inference ( 33 ) . Despite significant progress, existing GFMs remain limited in satisfying complex human preferences or task-specific objectives. For example, drug discovery requires generating small molecules with high binding affinity and low toxicity ( 41 ) . However, generating such molecules remains computationally expensive due to the vast space of generative models. Recently, online reinforcement learning (RL) ( 34 ) has demonstrated significant promise in aligning generative models with human priors by maximizing specific reward functions. While existing studies have explored the integration of RL with graph generative adversarial networks ( 44 ) and graph diffusion models ( 27 ) , extending RL to GFMs introduces two fundamental challenges: • Modern RL algorithms rely on policy gradients ( 37 ) for optimization, which requires the policy model to be differentiable for the transition probability of each action. However, existing GFMs estimate the action probabilities via Monte Carlo sampling ( 3 ) , breaking the gradient flows. • RL exploration needs sufficient feedback to locate the task-specific region in the generative space. However, GFMs typically perform de novo generation, which can produce sparse reward signals, i.e . , most generated graphs are invalid, leading to ineffective explorations. To address these two challenges, we propose Graph-GRPO, an online RL framework that uses Group Relative Policy Optimization ( 35 ) to align GFMs with task-specific objectives. Specifically, we first derive an analytical expression of GFMs that explicitly connects model predictions to the action probability, which enables fully differentiable sampling and allows GFMs to be trained with modern RL frameworks. Furthermore, we propose a refinement strategy to efficiently explore the potentials of promising samples. For graphs with higher reward scores, we iteratively inject a small amount of noise and let GFMs regenerate clean graphs. By repeating this process, Graph-GRPO progressively concentrates on high-potential regions of the generative space and improves generation quality over multiple refinement rounds. Figure 1 illustrates the effectiveness of the proposed refinement strategy on two molecular optimization tasks. While de novo generation and refinement achieve comparable performance on the basic Scaffold Hopping task, a large performance gap emerges on the more challenging Valsartan SMARTS task, demonstrating the necessity and effectiveness of iterative refinement in complex optimization scenarios. The contributions of this paper are summarized below: • We propose Graph-GRPO, an online RL framework that enables end-to-end RL training of GFMs by replacing the non-differentiable Monte Carlo sampling with an analytical transition probability. • We introduce an iterative refinement strategy that refines high-reward samples through controlled perturbation and regeneration, enabling localized exploration of promising regions in the chemical space. • Extensive experiments on synthetic graph benchmarks and molecular design tasks demonstrate the state-of-the-art performance of Graph-GRPO, outperforming existing RL-based and evolutionary approaches. 2 Preliminary Discrete State Graph. Let G=\{x^{1:N},e^{1:N^{2}}\} denote an undirected graph with N nodes and N^{2} edges, where x^{i}\in\{1,\cdots,\mathcal{X}\} and e^{j}\in\{1,\cdots,\mathcal{E}\} denote the discrete categories of nodes and edges, respectively. Each graph is represented as N+N^{2} dimensional data, and has |\mathcal{X}|^{N}\times|\mathcal{E}|^{N^{2}} possibilities. It is intractable to model the transition probability between graphs, and we address this issue by factorizing a graph into independent nodes and edges ( 6 ) : p(G)=\prod_{i=1}^{N}p(x^{i})\prod_{j=1}^{N^{2}}p(e^{j}). (1) For brevity, we omit the index of nodes and edges and use a uniform notation z to represent x and e , where \mathcal{Z}=\mathcal{X}\cup\mathcal{E} . 2.1 Discrete Flow Matching We consider a time-indexed stochastic process \{z_{t}\}_{t\in[0,1]} defined on \mathcal{Z} , where p_{t}(z=z_{t}) denotes the marginal distribution of z_{t} at time t . Discrete flow matching aims to construct a continuous probability path \{p_{t}\}_{t\in[0,1]} connecting a prior distribution p_{0} to the data distribution p_{1} . Noising Process ( t:1\rightarrow 0 ). In the noising process, given a data state z_{1} , the conditional probability path is defined via linear interpolation: p_{t\mid 1}(z_{t}\mid z_{1})=t\cdot\delta(z_{t},z_{1})+(1-t)\cdot p_{0}(z_{t}), (2) where \delta(i,j) denotes the Kronecker delta function, i.e . , \delta(i,j)=1 if i=j and 0 otherwise. Denoising Process ( t:0\rightarrow 1 ). The denoising process is modeled as a Continuous-Time Markov Chain (CTMC) that evolves the distribution from prior p_{0} to data p_{1} . The transition probability from z_{t} to z_{t+\mathrm{d}t} is defined as: p(z_{t+\mathrm{d}t}|z_{t})=\begin{cases}R_{t}(z_{t},z_{t+\mathrm{d}t})\mathrm{d}t&\text{if }z_{t+\mathrm{d}t}\neq z_{t},\\ 1+R_{t}(z_{t},z_{t})\mathrm{d}t&\text{if }z_{t+\mathrm{d}t}=z_{t},\end{cases} (3) where R_{t} is the rate matrix that determines whether to rest in the current state or jump to another state, and R_{t}(z_{t},z_{t})=-\sum_{z_{t+\mathrm{d}t}\neq z_{t}}R_{t}(z_{t},z_{t+\mathrm{d}t}) . In the following, we denote p(z_{t+\mathrm{d}t}|z_{t}) as the transition probability of the specific state, and use p(\cdot|z_{t})=[p(1|z_{t}),\cdots,p(\mathcal{|Z|}\mid z_{t})] to represent the distribution of all states. 2.2 Training and Sampling Continuous-time Training. GFMs aim to learn a graph denoiser f_{\theta} that takes the graphs with different noise levels as input and predicts the clean graphs, formulated as: \mathcal{L}=\mathbb{E}_{t\sim(0,1),G_{1}\sim p_{1},G_{t}\sim p_{t|1}}\text{CE}\big(G_{1},p_{\theta}(\cdot|G_{t})\big), (4) where CE denotes the cross-entropy loss and p_{\theta}(\cdot|G_{t}) is the probability distribution predicted by the denoiser f_{\theta}(G_{t},t) . Discrete-time Sampling. The sampling process generates data from noise by simulating the trajectory of a CTMC using a finite time interval \Delta t . Given the current discrete state z_{t} , the next state z_{t+\Delta t} is sampled from the categorical distribution defined by the transition probabilities: z_{t+\Delta t}\sim\text{Categorical}\Big(p_{t+\Delta t|t}(\cdot|z_{t})\Big), (5) where the rate matrix is determined by the denoising model prediction p_{\theta} and the initial prior

Read the complete text