Graph-GRPO: Training Graph Flow Models with Reinforcement Learning

Baoheng Zhu; Deyu Bo; Delvin Ce Zhang; Xiao Wang

cs.LGMar 11, 2026

Graph-GRPO: Training Graph Flow Models with Reinforcement Learning

Authors: Baoheng Zhu, Deyu Bo, Delvin Ce Zhang, Xiao Wang

Organizations: Beijing University of Posts and Telecommunications · National University of Singapore · University of Sheffield · Beihang University

Abstract

Graph generation is a fundamental task with broad applications, such as drug discovery. Recently, discrete flow matching-based graph generation, \aka, 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.

Figures & tables

Panel of Figure 1 — Figure 1: Reward curves on two molecular optimization tasks. We use DeFoG ( Qin et al., 2025 ) 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.

Figure 2

Figure 3: Refinement in Graph-GRPO. We first use GFMs to denoise a noise graph from $t=0$ to $t=1$ . Subsequently, we re-noise the generated graph to time step $t_{\epsilon}$ and denoise it again using GFMs. This strategy explicitly increases the denoising steps of GFMs and improves the generation quality of Graph-GRPO.

Model	Step	Planar		Tree
Model	Step	V.U.N. $\uparrow$	Ratio $\downarrow$	V.U.N. $\uparrow$	Ratio $\downarrow$
Train set	-	100	1.0	100	1.0
GraphRNN	-	0.0	490.2	0.0	607.0
BiGG	-	5.0	16.0	75.0	5.2
GraphGen	-	7.5	210.3	95.0	33.2
CatFlow	-	80.0	-	-	-

Table 1: Graph generation performance on two synthetic datasets: Planar and Tree. Results are reported as mean

\pm

standard deviation over five sampling runs, each generating 40 graphs.

Target	Metric	RL-optimized Generative Models						Basic Generative Models
Target	Metric	Graph-GRPO	GDPO	DDPO	FREED	REINVENT	GCPN	DiGress-G	DiGress	MOOD
parp1	DS (top 5%) $\downarrow$	-12.515 $\mathord{\pm}0.024$	-10.938 $\mathord{\pm}0.042$	-9.247 $\mathord{\pm}0.242$	-10.579 $\mathord{\pm}0.104$	-8.702 $\mathord{\pm}0.523$	-8.102 $\mathord{\pm}0.105$	-9.463 $\mathord{\pm}0.524$	-9.219 $\mathord{\pm}0.078$	-10.865 $\mathord{\pm}0.113$
parp1	Hit Ratio $\uparrow$	60.763 $\mathord{\pm}0.471$	9.814 $\mathord{\pm}1.352$	0.419 $\mathord{\pm}0.280$	4.627 $\mathord{\pm}0.727$	0.480 $\mathord{\pm}0.344$	0	1.172 $\mathord{\pm}0.672$	0.366 $\mathord{\pm}0.146$	7.017 $\mathord{\pm}0.428$
fa7	DS (top 5%) $\downarrow$	-9.099 $\mathord{\pm}0.053$	-8.691 $\mathord{\pm}0.074$	-7.739 $\mathord{\pm}0.244$	-8.378 $\mathord{\pm}0.044$	-7.205 $\mathord{\pm}0.264$	-6.688 $\mathord{\pm}0.186$	-7.318 $\mathord{\pm}0.213$	-7.736 $\mathord{\pm}0.156$	-8.160 $\mathord{\pm}0.071$
fa7	Hit Ratio $\uparrow$	9.367 $\mathord{\pm}0.753$	3.449 $\mathord{\pm}0.188$	0.342 $\mathord{\pm}0.685$	1.332 $\mathord{\pm}0.113$	0.213 $\mathord{\pm}0.081$	0	0.321 $\mathord{\pm}0.370$	0.182 $\mathord{\pm}0.232$	0.733 $\mathord{\pm}0.141$
5ht1b	DS (top 5%) $\downarrow$	-11.399 $\mathord{\pm}0.026$	-11.304 $\mathord{\pm}0.093$	-9.488 $\mathord{\pm}0.287$	-10.714 $\mathord{\pm}0.183$	-8.770 $\mathord{\pm}0.316$	-8.544 $\mathord{\pm}0.505$	-8.971 $\mathord{\pm}0.395$	-9.280 $\mathord{\pm}0.198$	-11.145 $\mathord{\pm}0.042$

Table 2: Experimental results on the protein docking task on ZINC250k ( Irwin et al., 2012 ) . Baseline results are taken from GDPO ( Liu et al., 2024 ) . We use the same benchmark evaluation protocol for a fair comparison. The best results are highlighted in bold .

Oracle	w/ Prescreening				Cold-Start (w/o Prescreening)
Oracle	Graph-GRPO	InVirtuoGen	GenMol	f-RAG	Graph-GRPO	InVirtuoGen	Gen. GFN	Mol GA	REINVENT
Albuterol Similarity	0.994 $\mathord{\pm}0.000$	0.975 $\mathord{\pm}0.016$	0.937 $\mathord{\pm}0.010$	0.977 $\mathord{\pm}0.002$	0.994 $\mathord{\pm}0.000$	0.950 $\mathord{\pm}0.017$	0.949 $\mathord{\pm}0.010$	0.896 $\mathord{\pm}0.035$	0.882 $\mathord{\pm}0.006$
Amlodipine MPO	0.823 $\mathord{\pm}0.008$	0.836 $\mathord{\pm}0.031$	0.810 $\mathord{\pm}0.012$	0.749 $\mathord{\pm}0.019$	0.823 $\mathord{\pm}0.008$	0.733 $\mathord{\pm}0.043$	0.761 $\mathord{\pm}0.019$	0.688 $\mathord{\pm}0.039$	0.635 $\mathord{\pm}0.035$
Celecoxib Rediscovery	0.890 $\mathord{\pm}0.000$	0.839 $\mathord{\pm}0.013$	0.826 $\mathord{\pm}0.018$	0.778 $\mathord{\pm}0.007$	0.890 $\mathord{\pm}0.000$	0.798 $\mathord{\pm}0.028$	0.802 $\mathord{\pm}0.029$	0.567 $\mathord{\pm}0.083$	0.713 $\mathord{\pm}0.067$
Deco Hop	0.942 $\mathord{\pm}0.005$	0.968 $\mathord{\pm}0.012$	0.960 $\mathord{\pm}0.010$	0.936 $\mathord{\pm}0.011$	0.762 $\mathord{\pm}0.127$	0.748 $\mathord{\pm}0.109$	0.733 $\mathord{\pm}0.109$	0.649 $\mathord{\pm}0.025$	0.666 $\mathord{\pm}0.044$
DRD2	0.995 $\mathord{\pm}0.000$	0.995 $\mathord{\pm}0.000$	0.995 $\mathord{\pm}0.000$	0.992 $\mathord{\pm}0.000$	0.995 $\mathord{\pm}0.000$	0.985 $\mathord{\pm}0.002$	0.974 $\mathord{\pm}0.006$	0.936 $\mathord{\pm}0.016$	0.945 $\mathord{\pm}0.007$

Table 3: Target property optimization results on the PMO benchmark ( Gao et al., 2022 ) (AUC-top10). Baseline results are taken from InVirtuoGen ( Kaech et al., 2025 ) and GenMol ( Lee et al., 2025 ) . Results are shown for both prescreening and cold-start settings, with best scores highlighted in bold .

Method	RL	Refine- ment	Pre- screening	Dynamic Prior	AUC-top10
DeFoG	-	-	-	-	11.079
DeFoG	-	✓	-	-	15.251
DeFoG	-	✓	✓	-	15.887
Graph-GRPO	✓	-	-	-	16.901
Graph-GRPO	✓	-	-	✓	17.450
Graph-GRPO	✓	✓	-	-	17.950

Table 4: Ablation studies on the PMO benchmark. We report the averaged AUC-top10 over all 23 tasks. All oracle calls used by refinement are counted under the same 10k budget.

Figure 4: Visualization of the sampling trajectory. From left to right, the graphs $G_{t}$ move from a prior distribution ( $t=0$ ) to the data distribution ( $t=1$ ). Visualizations of the predicted clean state $\hat{z}_{1}$ at the corresponding time steps are provided in Figure 8 .

Panel of Figure 5 — Figure 5: Visualization of training and evaluation curves in Graph-GRPO. We select five representative tasks from the PMO benchmark. (a) Training reward curves plotted against training steps. (b) Average top-10 scores plotted against the number of oracle calls. For brevity, we only visualize the first 5,000 oracle calls.

Appendix figures & tables9 assets

Supplementary material from the paper’s appendix.

Appendix

Figure 6: Comparison of learned prior distributions between the pre-trained DeFoG backbone and Graph-GRPO on the DRD2 task. The histograms illustrate the (Left) Node Type, (Middle) Edge Type, and (Right) Node Count distributions. Graph-GRPO dynamically aligns these priors with the characteristics of high-reward candidates, resulting in significant distributional shifts and sharper concentrations compared to the static baseline.

Figure 7: Randomly sampled molecules generated by Graph-GRPO. The generated molecules exhibit diverse scaffolds, ring systems, and functional groups, suggesting that the model does not collapse to repeated molecular structures.

Figure 8: Visualization of predicted clean states $\hat{z}_{1}$ . We display the clean graphs predicted by the denoiser at different time steps. The model infers the global topology of the target molecule early in the denoising process.

Panel of Figure 9 — Figure 9: Evolution of generated molecules across training epochs on the JNK3 task. We showcase samples obtained at different stages of training.

Task	0.9	0.7	0.5	0.3	0.0
Deco Hop	0.682	0.709	0.641	0.646	0.638
Osimertinib MPO	0.918	0.899	0.865	0.862	0.878
Valsartan SMARTS	0.949	0.827	0.584	0.211	0.174

Appendix

Table 5: Effect of renoising time

t_{\epsilon}

on the PMO benchmark.

Method	Reward @Step 0	Reward @Step 500	Grad Norm	Clip Rate
REINFORCE w/o analytic	1.03	0.312	130.6	100%
Graph-GRPO w/ analytic	1.03	1.537	0.97	0.7%

Appendix

Table 6: Comparison with REINFORCE variant on Tree (

N=64

Table 7: Scalability analysis of Graph-GRPO computational cost.

Target	Valid.	Uniq.	Nov.	Avg. QED	Avg. SA	Avg. Reward
parp1	97.803	100.000	0.945	0.667	0.655	0.459
fa7	98.617	100.000	0.992	0.726	0.650	0.358
braf	98.405	100.000	0.976	0.723	0.679	0.447
jak2	98.763	100.000	0.987	0.750	0.674	0.466
5ht1b	98.145	100.000	0.977	0.720	0.675	0.421

Appendix

Table 8: Detailed performance metrics of Graph-GRPO on five distinct targets.

	Planar Dataset
Model	Deg. $\downarrow$	Clus. $\downarrow$	Orbit $\downarrow$	Spec. $\downarrow$	Wavelet $\downarrow$	Ratio $\downarrow$	Valid $\uparrow$	Unique $\uparrow$	Novel $\uparrow$	V.U.N. $\uparrow$
Train set	0.0002	0.0310	0.0005	0.0038	0.0012	1.0	100	100	0.0	0.0
GraphRNN	0.0049	0.2779	1.2543	0.0459	0.1034	490.2	0.0	100	100	0.0
GRAN	0.0007	0.0426	0.0009	0.0075	0.0019	2.0	97.5	85.0	2.5	0.0
SPECTRE	0.0005	0.0785	0.0012	0.0112	0.0059	3.0	25.0	100	100	25.0
DiGress	0.0007	0.0780	0.0079	0.0098	0.0031	5.1	77.5	100	100	77.5

Appendix

Table 9: Extended Graph Generation Performance on Synthetic Graphs. We report the detailed MMD metrics and validity statistics. We only report the performance of Graph-GRPO (Ours) based on our own experiments, averaged over 5 runs.

Graph Generation

Graph generation builds models and algorithms that create graphs with desired structures, properties, or distributions.

See all 66 papers

Hierarchical Discrete Flow Matching for Graph Generation
Mar 31, 2026Yoann Boget, Pablo Strasser, Alexandros KalousisGraph Generation Flow-Based Generative Modeling
Department of Computer Science, University of Geneva, Switzerland · DMML Group, Geneva School for Business administration HES-SO, Switzerland
Latent Flow Matching for Molecular Graph Generation
Oct 5, 2026Mathis Goupillon, Roman Bresson, Konstantinos Divriotis +1Flow Matching Molecular Graph Generation
Mohamed bin Zayed University of Artificial Intelligence
Scaling Novel Graph Generation via Lightweight Structure-Guided Autoregressive Models
Jun 2, 2026Alessio Barboni, Massimiliano Lupo Pasini, Bishal Lakha +1Graph Generation Generative Modeling
Boise State University Boise, Idaho, USA · Oak Ridge National Laboratory Oak Ridge, Tennessee, USA

Mar 31, 2026J/K move · Enter open · S save

Hierarchical Discrete Flow Matching for Graph Generation

Yoann Boget, Pablo Strasser, Alexandros Kalousis

Department of Computer Science, University of Geneva, Switzerland · DMML Group, Geneva School for Business administration HES-SO, Switzerland

Graph Generation Flow-Based Generative Modeling Discrete Flow Matching

Open paper AskPDF arXiv

Denoising-based models, including diffusion and flow matching, have led to substantial advances in graph generation. Despite this progress, such models remain constrained by two fundamental limitations: a computational cost that scales quadratically with the number of nodes and a large number of function evaluations required during generation. In this work, we introduce a novel hierarchical generative framework that reduces the number of node pairs that must be evaluated and adopts discrete flow matching to significantly decrease the number of denoising iterations. We empirically demonstrate that our approach more effectively captures graph distributions while substantially reducing generation time.

Abstract

Graph Generation

Explore similar work

Hierarchical Discrete Flow Matching for Graph Generation

Latent Flow Matching for Molecular Graph Generation

Scaling Novel Graph Generation via Lightweight Structure-Guided Autoregressive Models