Graph Diffusion Policy Optimization
Authors: Yijing Liu
Chao Du
Tianyu Pang
Chongxuan Li
Min Lin
Wei Chen
Venue: NeurIPS 2024 poster (2024)
Keywords: Graph Generation
Diffusion Models
Reinforcement Learning
Primary area: generative_models
TL;DR: This paper introduces graph diffusion policy optimization (GDPO), a novel approach to optimize graph diffusion models for arbitrary (e.g., non-differentiable) objectives using reinforcement learning.

Abstract: Recent research has made significant progress in optimizing diffusion models for downstream objectives, which is an important pursuit in fields such as graph generation for drug design. However, directly applying these models to graph presents challenges, resulting in suboptimal performance. This paper introduces graph diffusion policy optimization (GDPO), a novel approach to optimize graph diffusion models for arbitrary (e.g., non-differentiable) objectives using reinforcement learning. GDPO is based on an eager policy gradient tailored for graph diffusion models, developed through meticulous analysis and promising improved performance. Experimental results show that GDPO achieves state-of-the-art performance in various graph generation tasks with complex and diverse objectives. Code is available at https://github.com/sail-sg/GDPO.

Graph Diffusion Policy Optimization
Yijing Liu"l, Chao Du*t?, Tianyu Pang", Chongxuan Li Min Lin', Wei Chen
"Stte Key Lab of CAD&CG, Zhejiang University
Sea AI Lab, Singapore Renmin University of China
[1iuy]86, chenvis} edu. en;
(duchao, tianyupang, linmin)@sea. com; chongxuanl1@ruc.edi
Abstract
Recent research has made significant progress in optimizing diffusion models for downstream objectives, which is an important pursuit in fields such as graph generation for drug design. However, directly applying these models to graph presents challenges, resulting suboptimal performance. This paper introduces graph diffusion policy optimization (GDPO), novel approach to optimize graph diffusion models for arbitrary (e.g., non-differentiable) objectives using reinforce- ment learning. GDPO is based diffusion models, developed through meticulous analysis and promising improved performance. Experimental results show that GDPO achieves state-of-the-an art per- formance various graph generation tasks with complex and diverse objectives. Code is available at https://github.. http://iihuubb.oommsslll///DDDe
eager policy gradient tailored for graph
Introduction
Graph generation, key facet of graph learning, has applications in variety of domains, including drug and material design [54], code completion [8], social network analysis [20]. and neural architec- ture search [64]. Numerous studies have shown significant progress in graph generation with deep generative models [34, 62, 69, 21]. one of The most notable advances in the field is the introduction of graph diffusion probabilistic models (DPMs) [61, These methods can learn the underlying distribution from graph data samples and produce high-quality novel graph structures.
In many use cases of graph generation, the primary focus is achieving specific objectives, such as high drug efficacy [60] or creating novel graphs with special discrete properties [22]. These objectives are often expressed as specific reward signals, such as binding affinity [10] and synthetic accessibility [7], rather than a set training graph samples. Therefore, a more pertinent goal such scenarios is to train graph generative models to meet these predefined objectives directly, rather than learning to match a distribution over training data [72].
A major challenge in this context is that most signals are non-differentiable w.r.t. graph representations, making difficult to apply many optimization algorithms. To address this, methods based on property predictors [29, 37] learn parametric models to predict the reward signals, providing gradient guidance for graph generation. However, since reward signals can be highly complex (e.g., results from physical simulations), these predictors often struggle provide accurate guidance [44]. An alternative direction is to learn graph generative models as policies through reinforcement learning (RL) [72], which enables the integration of exact reward signals into the optimization. However, existing work primarily explores earlier graph generative models and has yet to leverage the superior performance of graph DPMs [9, 68]. On the other hand, several pioneer works have significant
"Equal contribution. Work done during Yijing Liu's internship at Sea Al Lab. "Corespoondence Wei Chen and Chao
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

progress in optimizing continuous- vartibbuu--aarialle (e.g. images) DPMs for downstream objectives [6. 16]. The central idea is to formulate the sampling process as policy, with the objective serving as a reward, and then learn the model using policy gradient methods. However, when these approaches are directly extended to Missrree-variiblle graph DPMs, we empirically observe a substantial failure, which we will illustrate and discuss in Sec. 4.
To close this gap, we present graph diffusion policy optimization (GDPO), a policy gradient method designed to optimize graph DPMs for arbitrary reward signals. Using an RL formulation similar to that introduced by Black et al. [6] and Fan al. [16] for continuous-varian the discrete diffusion process of graph DPMs to a Markov decision process (MDP) and formulate the learning problem as policy optimization. Then, to address the observed empirical failure, we introduce a slight modification to the standard policy gradient method REINFORCE [58], dubbed the eager policy gradient and specifically tailored for graph DPMs. Experimental evaluation shows that GDPO proves effective across various scenarios and achieves high sample efficiency. Remarkably, our method achieves a 41.64% to 81.99 81.97% average reduction in generation-test distance and 1. 1.03% to 19.31 % improvement in the rate of generating effective drugs, while only querying a small number of samples (1/25 of the training samples).
DPMs, we first adapt
2 Related Works
Graph Generative Models. Early work in graph generation employs nonparametrie random graph models [15, 26]. To Iearn complex distributions from graph-structured data, recent research has shifted towards leveraging deep generative models. This includes approaches based on auto-regressive generative models [69, 39], variational autoencoders (VAEs) [34, 41, 23], generative adversarial networks (GANs) [62, 9, 43], and normalizing flows [53, 40, 42].
Recently, diffusion probabilistic models (DPMs) [25, 56] have significantly advanced graph generation [70]. Models like EDP-GNN [46] GDSS [31] and DruM [30] construct graph DPMs using continuous diffusion processes [57]. While effective, the use of continuous representations and Gaussian noise can hurt the sparsity of generated graphs DiGress [61] employs categorical distributions as the Markov transitions in discrete diffusion [2]. performing well on complex graph generation tasks. While these works focus on learning graph DPMs from a given dataset, our primary focus in this paper is learning from arbitrary reward signals.
Controllable Generation for Graphs. Recent progress in controllable generation has also enabled graph generation to achieve specific objectives or properties. Previous work leverages mature con- ditional generation techniques from GANs and VAEs [66, 52, 36, 28, 14]. This paradigm has been extended with the introduction of guidance-based conditional generation in DPMs [12]. DiGress [61] and GDSS [31] provide solutions that sample desired graphs with guidance from additional property predictors. MOOD [37] improves these methods by incorporating ever, as predicting the properties (c.g., drug efficacy) can be extremely difficult [33, 44], the predictors often struggle to provide accurate guidance. Our work directly performs property optimization on graph DPMs, thus bypassing this challenge.
control. How-
Graph Generation using RL. RL techniques find wide application in graph generation to meet downstream objectives. REINVENT [47] and GCPN [68] are representative works, which define graph environments and optimize policy networks with policy gradient methods [59]. For data- free generation modelling, MolDQN [71] replaces the data-related environment with a human- defined graph environmentand and utilizes Q-Learning [24] for policy optimi zation. To generate more realistic molccules, DGAPN [63] and FREED [67] investigate the fragment-based chemical environment, which reduce the search space significantly. Despite the great successes, existing methods exhibit high time complexity and limited policy model capabilities. Our work, based on graph DPMs with enhanced policy optimization, achieves new state-of-the-art performance.
Aligning DPMs. Several works focus on optimizing generative models to align with human prefer- ences [45, 3]. DPOK [16] and DDPO [6] are representative works that align text-to- text-to-image DPMs with black-box reward signals. They formulate the denoising process of DPMs as an MDP and optimize the model using policy gradient methods. For differentiable rewards, such as human preference mod- els [35], AlignProp [50] and DRaFT [11] propose effective approaches to optimize DPMs with direct backpropagation, providing a more accurate gradient estimation than DDPO and DPOK. However,

---

these works are conducted on images. To the best of our knowledge, our work is the first effective method for aligning graph DPMs, filling a notable gap the literature.
3 Preliminaries
In this section, we briefly introduce the background of graph DPMs and policy gradient methods.
Following Vignac et al. [61], we consider graphs with categorical node and edge attributes, allowing representation of diverse structured data like molecules. Let X' and & be the space of categories for nodes and edges, respectively, with cardinalities a = | and b [g). For graph with nodes, we denote the attribute of node by a one-hot encoding vector x(()) E R Similarly, the attribute of the edge' from node i node j is represented as elis) E RR. By grouping these one-hot vectors, the graph then be represented
tuple G (X, E), where X E RRax and E Rxxxxb
3.1 Graph Diffusion Probabilistic Models
Graph diffusion probabilistic models (DPMs) [61] involve a forward diffusion process g( (GiT. Go) = Ie (GG//.r1)) which gradually corrupts a data distribution g (G)) into a simple noise distribu- tion a( (Gr) over a specified number of diffusion steps, denoted as T.. The transition distribution q( (G.)) can be factorized into product of categorical distributions for individual nodes and edges, i.e., q(<x²") (xx" ,) and q(e, (e()), For simplicity, superscripts are omitted when no ambi- guity is caused in the following. The transition distribution for each node is defined as q( (ar--)) Cat( - where the transition matrix is chosen as Qr _ azI + (1 a: (1, )a, with a transitioning from 1 to 0 as increases [2]. It then follows that g(2r|z0) = Cat ( xo Q.) and
(<;;-1/;;, 20) = Cat 2.Q, moQ: )), where Q: Q1Q2.. ... Q: and @ denotes element- wise product. The design choice of Q, ensures that q( a0)) = Cat(ær:14) /a).. i.e., uniform dis- tribution over X. The transition distribution for edges is defined similarly, and we omit it for brevity.
Given the forward diffusion process, parametric reverse denoising process Po(Gorr) p(GT) IT'=1 (o then learned recover the data distribution from p(GT) = q (an approximate uniform distribution). The reverse transition po (G.- (G.) is product of categorical distributions over nodes and edges, denoted as pa( | and po(e,-1 |Gt). Notably, in line with the 4o parammterrriztionn used in continuous DPMs [25, 32], po (a [G,) is modeled as:
Po (xx 1 (G.) A
Σ B
q(<,-11 v, To)Po (To G.).
(1)
where po (T. is neural network predicting the posterior probability of æu given noisy graph Gt. For edges, each definition is analogous and thus omitted.
The model is learned with graph dataset 'D by maximizing the following objective [61]:
JGDPM (0) = EE.., B.G. [log po ( Gt)],
(2)
where Go and follow uniform distributions over D and [1, T]. respectively. After learning, graph samples can then be generated by first sampling Gr from p( (Gr) and subsequently sampling G. from po Po (G.-1 GG), resulting in a generation trajectory (Gr, Gr-1,..., Go).
3.2 Markoy Decision Process and Policy Gradient
Markov decision processes (MDPs) are commonly used to model sequential decision-making problems [17]. An MDP formally defined by quintuple (S, P,r, r, Po). where S the state space containing all possible environment states, A is the action space comprising all available potential actions, P is the transition function determining the probabilities of state transitions, r the reward signal, and Po gives the distribution of the initial state.
In the context of an MDP, an agent engages with the environment across multiple steps. At each step f, the agent observes state E S and selects an action a, E A based on its policy distribution
For convenience, "no edge" treated as special type of edge.
3

---

Sampling Trajectories and Receiving Reward Signals
2. Policy Gradient Estimation
Ny. G.G
Prediet Ge
G
Gruph DPM
Sampling
Gr
Gra
Query
V. Volug Volug Go)
Accumulate
0
Σ V Po
r
Grs
Signals
Eager Policy Gradient
Drag Efficecy: 7,081 Novelty: 0.492
Dong Efficaey: 8.840
Doig Frfiesey: 9.337
Drug Edficacy: 10.125 Novelty: 0.547
Daig Erficaey: 10.400
Novelty: 0,545
Novelty: 0,605
Novelt: 0.647
Leaming Step
Figure 1: Overview of GDPO. (1) In each optimization step, GDPO samples multiple generation trajectories from the current Graph DPM and queries the reward function with different Gg. (2) For each trajectory, GDPO accumulates the gradient V, log Pa (G,G) of each (Go. G.) pair and assigns a weight to the aggregated gradient based on the corresponding reward signal. Finally, GDPO estimates the eager policy gradient by averaging the aggregated gradient from all trajectories.
Ts(a:)s)) Subsequently, the agent receives reward r(s a,) and transitions to new state 8++1 following the transition function P( 8t, az). As the agent interacts the MDP (starting from an initial state $0 Po), it generates trajectory (i.c., sequence of states and actions) denoted as (Su; ao, $1, a1,..., ST, ar). The cumulative reward over a trajectory т given by R(T) = E r(s,, a,). In most scenarios, the objective is to maximize the following expectation:
JRL (f) Br=p(r(=s) [R(T).
Policy gradient methods aim to estimate aR (0) and thus solve the problem by gradient descent. An important result the policy gradient theorem [19], which estimates (R. as follows:
V VOJRL = Ex-p(r(aa)
Vo log no (a: ss) R(T))
(4)
L(=0
The REINFORCE algorithm [58] provides simple method for estimating the above policy gradient using Monte-Carle simulation, which will be adopted and discussed in the following section.
Method
In this section, we study the problem of learning graph DPMs from arbitrary reward signals. We first present an MDP formulation of the problem and conduct an analysis on the failure direct application of REINFORCE. Based the analysis, we introduce substitute termed eager policy gradient, which forms the core our method Graph Diffusion Policy Optimization (GDPO).
4.1 A Markov Decision Process Formulation
graph DPM defines a sample distribution pe (Go) through its reverse denoising process po Go:r). Given reward signal r(.) for Go. aim to maximize the expected reward (ER) over Go
JER (0) EGo-ps(Go) (r(G)))
(5)
However, directly optimizing JER (0) challenging since the likelihood (o( unavailable [25] and r(-) is blx, hindering the of typical RL algorithms [6]. Following Fan et al. [16],

---

Nodes:
Nodes:
of Nodes:
Hof
1.0-
1.0
1.0
1.0
Argitovun
0.8-
ArgRRwward
0.5
AvyRowond
ArgRewand
GDPO (ours)
GIPO (ours)
9.66-
80.6
0.6
DDPO
0,:8
DDPO
GDPO (ours)
GIPO DDPO
0.4
0.7
DDPO
0.6
0
5ik
THikk
150k
50k
100k
150k
50k
100k
150%
50k
100k
1.5k
Queries
Queries
Querics
Queries
Figure 2: Toy experiment comparing DDPO and GDPO. We generate connected graphs with in- creasing number of nodes. Node categories are disregarded, and the edge categories are binary, indicating whether two nodes are linked. The graph DPM is initialized randomly as a one-layer graph transformer from DiGress [61]. The diffusion step T set to 50, and the reward signal r(G)) is defined as 1 if Go is connected and 0 otherwise. We use 256 trajectories for gradient estimation in each update. The learning curve illustrates the diminishing performance of DDPO as the number of nodes increases, while GDPO consistently performs well.
formulate the denoising process as T'sttp MDP and obtain an equivalent objective. Using notations in Sec. 3, we define the MDP of graph DPMs as follows:
8t - TT a e GT-t-1- (0(0)(0:) & pe (GT-)-
(6)
P(s (8, az) 0r r(st, az) A r(G)) =f r(s;, a.) & Tf
where the initial state 8n corresponds to the initial noisy graph GT and the policy corresponds to the reverse transition distribution. As result, the graph generation trajectory (GT. GT- Go) can be considered as a state-action trajectory produced by an agent acting in the MDP. It then follows that p(T(mT) pa (. Moreover, we have R(T) Di at) r(Go). Therefore, the expected cumulative reward of the agent (0) = (P(r))))(((TT) Epo(Gor)) (r(Go) is equivalent to JER (0), and thus JER (0) can also be optimized with the policy gradient V (O):
T
DRIRI = E r(Go)
Σ v log loggoo (G.
(7)
[=
where the generation trajectory T follows the parametric reverse process pa ( (Go.T).
4.2 Learning Graph DPMs with Policy Gradient
The policy gradient JO (0) in Eq. (7) is generally intractable and efficient estimation is necessary. In a related setting centered on continuous-variable DPMs for image generation, DDPO [6] estimates the policy gradient V TRIRI. with REINFORCE and achieves great results. This motivates us to also try REINFORCE on graph DPMs. i.c., to approximate Eq. (7) with Monte Carlo estimation:
K
VOJRL ~
T
Σ EE
rG (k) Vo log ( (
(8)
K
T
(k) K where (G O 1=1 are K trajectories sampled from po Gu:r) and I [1, random subsets of timesteps (which avoid summing over all timesteps and accelerate the estimation).
uniformly
However, we empirically observe that it rarely converges on graph DPMs. To investigate this, we design toy experiment, where the reward signal whether Go is connected. The graph DPMs are randomly initialized and optimized using Eq. (8). We refer this setting DDPO. Fig. 2 depicts the learning curves, where the horizontal axis represents the number of queries to the reward signal and the vertical axis represents the average reward. The results demonstrate that DDPO fails to converge to a high reward signal area when generating graphs with more than nodes. Furthermore, as the
With slight abuse of notation we will use 7 = Go.r and T = (So, ao, a1...., Sr, ar) interchange- ably, which should not confuse the MDP relates them with bijection.
5

---

number of nodes increases, the fluctuation of the learning curves grows significantly. This implies that DDPO essentially unable to optimize properly on randomly initialized models. We conjecture that the failure is due to the vast space constituted by discrete graph trajectories and the well-known high variance issue of REINFORCE [58]. A straightforward method to reduce variance is to sample more trajectories. However, this is typically expensive in DPMs, as each trajectory requires multiple rounds of model inference. Moreover, evaluating the reward signals of additional trajectories also incurs high computational costs, such as drug simulation [48].
This prompts us to delve deeper a micro level. Since the policy gradient estimation in Eq. (8) is a weighted summation of gradients, we first inspect each summand term V log (G. Gt). With
the parameterization Eq. (1) described in Sec. 3.1, has the following form:
Vo log pa G.- po (o
1
Σ (G (GGrii//,, Go) Vopo G.) Go
(9)
weight
gradient
where we can view the "weight" term as a weight assigned to the gradient Vopo GGo and thus Va log (G.- (G.) as a weighted sum of such gradients, with Go taken over all possible graphs Intuitively, the gradient Vepe (Gol G.: promotes the probability of predicting Go from G,, Note, however, that the weight q( GG 1 |G.,, Go) is completely independent of rGo)) and could assign large weight for Go that has low reward. Since the weighted sum in Eq. (9) can be dominated by gradient terms with large q( y(,,-1/G. G.,, Go). given a particular sampled trajectory, it is fairly possible that Ve log log Peep&(Gr. (G,- IG,) increases the probabilities of predicting undesired Go with low rewards from G.. This explains why Eq. (8) tends to produce fluctuating and unreliable policy gradient estimates when the number of Monte Carlo samples (i.e., K and [Tx]) is limited. To further analyze why DDPO does not yield satisfactory results, we present additional findings in Appendix A.5. Besides, we discuss the impact of importance sampling techniques in the same section.
4.3 Graph Diffusion Policy Optimization
To address the above issues, we suggest slight modification to Eq. (8) and obtain new policy gradient denoted as g0):
(
4 K
T
Σ r( Vo (
(10)
Tkl
k=1
1ET
which we refer to as the eager policy gradient. Intuitively, although the number of possible graph trajectories is tremendous, if we partition them into different equivalence classes according to Go. where trajectories with the same Go are considered equivalent, then the number of these equivalence classes will be much smaller than the number of graph trajectories. The optimization over these equivalence classes will be much easier than optimizing in the entire trajectory space.
Technically. by replacing the summand gradient term V log pe GG,) with Ve log log Pe in Eq. (8), we skip the weighted sum in Eq. (9) and directly promotes the probability of predicting Go which has higher reward from G, at all timestep t. As result, our estimation does not focus on how G, changes to G within the trajectory; instead, aims to force the model's generated results to be close to the desired Go. which can be seen as optimizing in equivalence classes. While being a biased estimator of the policy gradient VOJRL (0). the eager policy gradient consistently leads to more stable learning and better performance than DDPO, as demonstrated in Fig. 2. We present the resulting method in Fig. and Algorithm I, naming it Graph Diffusion Policy Optimization (GDPO).
5 Reward Functions for Graph Generation
In this work, we study both general graph and molecule reward signals that are crucial in real-world tasks, Below, we elaborate on how we formulate diverse reward signals as numerical functions.
5.1 Reward Functions for General Graph Generation
Validity. For graph generation, a common objective to generate a specific type of graph. For instance, one might be interested in graphs that can be drawn without edges crossing each other [43].

---

Table 1: General graph generation SBM and Planar datasets.
Planor Graphs
SBM Graphs
Methou
Deg
Clas I
Orb
(
Deg
Clar
Orb
(%)1
GraphRNN
24.51 + 3.22
9.03 + 0.78
2508.30 + 30.81
0
6,92 + 1.13
1.72 + 0.05
3.15 + 0.23
4.92 + 0.35
SPECTRE
2.55 + 0.34
2.52 = 0.26
2,42 + 0.37
25.46 + 1.33
1,92 1.21
1.64 = 0.06
1.67 = 0.14
53.76 + 3.62
GDSS
10.81 1 0.86
12.99 1 0.22
38.71 1. 0.83
0.78 0.72
15.53 1. 1,30
3.50 1 0,81
15.98 11988110 2.30
0
MOOD
5.73 +: 0.82
11.87 4: 0.34
30,62 1: 0.67
1,21 0.83
12.874 1.20
3.06 4: 0.37
2.81 4 0.35
0
DiGress
1.43 + 0.90
1.22 + 0,32
1.72 + 0.44
70.02 + 2.17
1.63 + 1.51
1,50 + 0,04
1.70 + 0.16
60.94
+ 4.98
DDPO
109,5911 36.69
31.47
1: 4.96
504.19
+: 17.61
2.34 1.10
250.06
: 7.44
2.93
1: 0.32
6.65
1 0.45
31.25
1: 5.22
GDPO (ours)
0.03 1: 0.04
0.62 1 0.11
0.02 0.01
73.83 1: 2.49
0.15
1 0.13
1,50 1 0.01
1.12 1 0.14
80.08 1. 2.07
For such objectives, the reward function (-vi(-) is then formulated as binary, with "val(G)) - indicating that the generated graph Go conforms the specified type; otherwise, (Gv) _ 0.
Similarity, In certain scenarios, the objective is to generate graphs that resemble a known set of graphs D at the distribution level, based on pre-defined distance metric d(..-) between sets of graphs. As an example, the Deg D) [38] measures the maximum mean discrepancy (MMD) [18] between the degree distributions of a set 9 of generated graphs and the given graphs D. Since method requires a reward for each single generated graph Go. we simply adopt Deg((Go): D) as the signal. As the magnitude of reward is critical for policy gradients [58], we define Tdog (Go) A exp(-Deg( ()))) /)"/ where the controls the reward distribution, ensuring that the reward lies within the range of 0 to 1. The other two similar distance metrics are Clus(g, D) and Orb(g, D). which respectively measure the distances between two sets of graphs in terms of the distribution of clustering coefficients [55] and the distribution of substructures [1]. Based on the two metrics, we define reward signals analogous Fdeg. namely, Telus and Forb.
5.2 Reward Functions for Molecular Graph Generation
Novelty. primary objective of molecular graph generation to discover novel drugs with de- sired therapeutic potentials. Due to drug patent restrictions, the novelty of generated molecules has paramount importance. The Tanimoto similarity [4], denoted as J(.,), measures the chem- ical similarity between two molecules, defined by the Jaccard index of molecule fingerprint bits. Specifically, E [0. 1], and J(G,, G)) tical fingerprints. Following Xie et al. [65], we define the novelty of generated graph Go as NOV(GG) 1 ma (Go, G)), i... the similarity gap between Go and its nearest neighbor in the training dataset D, and further define nxov (Go) NOV(GG).
indicates that two molecules Go and G have iden-
Likg-Likeness. Regarding the efficacy of molecular graph generation in drug design, critical indicator is the binding affinity between the generated drug candidate and a target protein. The docking score [10], denoted as DS(.), estimates the binding energy (in kcal/mol) between the ligand and the target protein through physical simulations in 3D space. Following Lee et al. [37], we clip the docking score in the range 20 0] and define the reward function as Tps(GG, - DD.
Another metric is the quantitative estimate of drug-likeness QED(-), which measures the chemical properties to gauge the likelihood of molecule being successful drug [5]. As takes values in the range [0, 1], we adopt FOED (Go) & T(QED(Go) 0.5).
Synthetic Accessibility. The synthetic accessibility [7] SA(-) evaluates the inherent difficulty in synthesizing a chemical compound, with values in the range from 1 to 10. We follow Lee et al. [37] and use normalized version as the reward function: rsa (Go) (10 SA SA(G)))/9.
6 Experiments
In this section, we first examine the performance of GDPO on both general graph generation tasks and molecular graph generation tasks. Then, we conduct several ablation studies investigate the effectiveness of GDPO's design. Our code can be found in the supplementary material.
7

---

Table 2: Molecule property optimization results ZINC250K.
Target Protein
Method
Metric
parpl
ja7
5hrlb
brof
jak2
Hit Ratio DS (top 5%)
0
1,455 + 1.173
0
GCPN
-8. 3020 0.105
0.188
-8.5441 0.505
-8.713:: 0.155
8.073310.093
Hit Ratio
0.480 + 0.344
0.213 + 0.081
2,453 + 0.561
0.127 + 0.088
0.613 + 0.167
REINVENT
DSS (top 5%)
-8,702 + 0.523
-7.205 0.264
-8.770 + 0.316
-8.392 0.400
8.166 + 0.277
Hit Ratio
4.627 = 0.727
1.332 + 0.113
16.767 = 0.897
2.940 = 0.359
5,800 = 0.295
FREED
DS (top 5%)
-10.579 + 0.104
-8.378 = 0.044
-10.714 + 0.183
-10.561 = 0,080
-9.735 = 0.022
Hit Ratio
7.017 0.428
0.733 + 0.141
18.673 :: 0.423
5.240 +: 0.285
9,200 0.524
MOOD
DS (top 5%)
-10.865 +: 0.113
-8,160 = 0.071
-11.145 +: 0.042
-11.063 +: 0.034
-10.147 +: 0.060
Hit Ratio
0.366 0.146
0.182 0.232
4,236 0.887
0.122 + 0.141
0.861 0.332
DiGress
DS (top 5%)
-9,219 +: 0.078
-7,736 = 0.156
-9,280 + 0.198
-9.052 +: 0,044
-8,706 + 0.222
DiGress-
Hit Ratio
1.172:0.672
0.3211:03700
2.821 1.140
0.152-10.303
0.311:00621
guidance
DS (top 5%)
-9,463+ 0.524
-7.318=0.213
-8.971 0.395
-8.825+ 0.459
-..300
Hit Ratio
0.419
0.280
0.342 0.685
5.488
1.989
0.445 + 0.297
1.717 0.684
DDPO
DS (top 5%.
-9.247 + 0.242
-7.739 = 0.244
-9.488 = 0,287
-9.470 + 0.373
-8,990 = 0.221
GDPO
Hit Ratio
9.814
1.352
3.449
0.188
34.359 = 2.734
9.039 + 1.473
13.405 + 1.515
(ours)
DS (top 5%)
-10.938 0.042
-8,691 = 0.074
-11.304 1: 0.093
-11.197 1 0.132
-10.183 1: 0.124
6.1 General Graph Generation
Following DiGress [61], we evaluate GDPO on two benchmark datasets: SBM (200 nodes) and Planar (64 nodes), each consisting of 200 graphs. We compare GDPO with Nr [69], SPECTRE [43], GDSS [31], MOOD [37] and DiGress. The first two models are based on RNN and GAN, respectively. The remaining methods are graph DPMs, and MOOD employs an additional property predictor. We also test DDPO [6]. i.e., graph DPMs optimized with Eq. (8).
Datasets and Baselines.
Implementation. We set 7 1000, [T| 200, and N 100. The number of trajectory samples K 64 for SBM and 256 for Planar. We use a DiGress model with 10 layers. More implementation details can be found in Appendix A.
Metrics and Reward Functions. Orb(g. Drest), and the V.U.N metrics. V.U.N measures the proportion of generated graphs that are valid, unique, and novel. The reward function is defined as follows:
We consider four metrics: Deg(G, Dtest). Clus(G, Drest).
Tgeneral 0.1 x (Faeg + Telus + Torb) + 0.7 X Tvals
(11)
where we do not explicitly incorporate uniqueness and novelty. All rewards are calculated on the training dataset if reference graph set is required. All evaluation metrics calculated on the test dataset. More details about baselines, reward signals, and metrics are Appendix A.3.
Results. Table summarizes GDPO's superior performance in general graph generation, showing notable improvements Deg and V.U.N across both SBM and Planar datasets. On the Planar dataset, GDPO significantly reduces distribution distance, achieving an 81.97% average decrease in metrics of Deg, Clus, and Orb compared to DiGress (the best baseline method). For the SBM dataset, GDPO has a 41.64% average improvement. The low distributional distances to the test dataset suggests that GDPO accurately captures the data distribution with well-designed rewards. Moreover, we observe that our method outperforms DDPO by a large margin, primarily because the graphs in Planar and SBM contain too many nodes, which aligns with the observation in Fig. 2.
6.2 Molecule Property Optimization
Datasets and Baselines. Molecule property optimization aims to generate molecules with desired properties. We evaluate our method on two large molecule datasets: ZINC250K [27] and MOSES [49]. The ZINC250K dataset comprises 249,456 molecules, each containing 9 types of atoms, with maximum node count of 38; the MOSES dataset consists of 1,584,66, molecules, with types of atoms and maximum node count of 30. We compare GDPO with several leading methods:
8

---

Table 3: Molecule property optimization results MOSES.
Target Protein
Method
Metric
parp!
fa7
Shrlb
bref
jak2
Hit Ratio
0.532 0.614
0
4.255 0.869
0.263 = 0.532
0.798 = 0.532
FREED
DS (top 5%)
-9.313 = 0.357
-7.825 + 0.167
-9,506 = 0.236
-9.306 + 0.327
-8,594 = 0.240
Hit Ratio
5.402 0.042
0.365 = 0.200
26.143 1.647
3.932 = 1.290
11.301 + 1.154
MOOD
DS (wp 5%)
.9.814 1: 1.352
-7.974 1 0.029
10.734 1 0.049
-10.722 1: 0.135
-10.158 1 0.185
Hit Ratio DS (top 5%)
0.231 T. 0.463
0.113 1 0.131
3.852 T. 5.013
0
0.228 1 0.457
DiGress
.9.223 _. 0.083
-6.644 0.533
-8.640 1 0.907
8.522 1 1.017
-7.424 1. 0.994
Hit Ratio DS (top 5%)
3.037 1 2.107
0.504 1 0.667
7.855 T. 1.745
0 0.125
3,943 1. 2.204
DDPO
-9.727 = 0.529
-8.025 0.253
-9.631 + 0.123
-9.407
-9.404 0.319
GDPO
Hit Ratio
24.711 = 1.775
1,393 = 0.982
17.646 + 2.484
19.968 2.309
26.688 + 2,401
(ours)
DS (top 5%)
-11.002 0.056
-8.468 0.058
-10.990 1 0.334
-11.337 - 0.137
-10.290 0.069
GCPN (68), REINVENT [47], FREED [67] and MOOD [37]. GCPN, REINVENT and FREED are RL. methods that search in the chemical environment. MOOD, based on graph DPMs, employs a property predictor for guided sampling. Similar to general graph generation, we also compare our method with DiGress and DDPO. Besides, we show the performance of DiGress with property predictors, termed as DiGress-guidance.
Implementation. We set = 500, [T| = 100, N = 100, and K = 256 for both datasets. We use the same model structure with DiGress. See more details in Appendix A.1.
Metries and Reward Functions. Following MOOD, we consider two metrics essential for real-world novel drug discovery: Novel hit ratio ( (%) and Novel top 5% docking score, denoted as Hit Ratio and DS (top 5%), respectively. Using the notations from Sec. 5.2, the Hit Ratio the proportion of unique generated molecules that satisfy: DS <, median DS of the known effective molecules, NOV > 0.6, QED 0.5, and SA < 5. The DS (top 5%) is the average DS of the top 5% molecules (ranked by DS) that satisfy: NOV > 0.6, QED > 0.5, and SA < 5. Since calculating DS requires specifying target protein, we set five different protein targets to fully test GDPO: parpl. fa7, Sht braf, and jak2. The reward function for molecule property optimization is defined as follows:
Tmolecule = 0.1 X (FaE + +TAA) + 0.3 X NNov + 0.5 X Tps-
(12)
We do not directly use Hit Ratio and DS (top 5%) as rewards in consideration of method generality. The reward weights are determined through several rounds of search, and we find that assigning high weight to Txov leads to training instability, which is discussed Sec. 6.3. More details about the experiment settings are discussed in Appendix A.4.
Results. In Table 2. GDPO shows significant improvement on ZINC250K, especially in the Hit Ratio. A higher Hit Ratio means the model is more likely to generate valuable new drugs, and GDPO averagely improves the Hit Ratio by 5. 5.72% in comparison with other SOTA methods. For DS (top 5%). GDPO also has a 1. 1.48% improvement on average. Discovering new drugs on MOSES much more challenging than on ZINC250k due to its vast training dataset. In Table 3, GDPO also shows promising results on MOSES. Despite less favorable Hit Ratio on Shr/b, GDPO achieves an average improvement of 12.94% on the other four target proteins. For DS (top 5%), GDPO records an average improvement of 5.54% compared to MOOD, showing a big improvement in drug efficacy.
6.3 Generalizability, Sample Efficiency, and A Failure Case
To validate whether GDPO correctly optimizes the model, we test the per- formance of GDPO on metrics not used in the reward signal. In Ta- ble 4, we evaluate the performance on Spectral MMD [43], where the GDPO is optimized by Eq. (11). The results demonstrate that GDPO does
Table 4: Generalizability of GDPO on Spectral MMD,
Methods
Dataset
DiGress
DDPO
GDPO (ours)
PLANAR
1.0353+ 0.4474
20.1431+ 3.5810
0.8047 0.2030
SBM
1.20244 0.2874
13.27734 1.4233
108611 0.2551

---

not show overfitting; instead, it finds more powerful model. The results presented in Appendix A.5 further support that GDPO can attain high sample novelty and diversity.
We then investigate two crucial fac- tors for GDPO: 1) the number of tra- jectories; 2) the selection of the re- ward signals. We test our method on ZINC250K and set the target proteins as Sht/b. In Fig. 3 (a), the results in- dicate that GDPO exhibits good sam- achieves signif-
0.7 (a)
(b)
0.6
AvgReward
Nygrew
0.4
0.5
GDPO-32
pling efficiency, icant improvement in average reward by querying only 10k molecule re- ward signals, which is much less than the number of molecules contained in ZINC250K. Moreover, the sample ef- ficiency can be further improved by reducing the number of trajectories, but this may lead to training instabil- ity. To achieve consistent results, use 256 trajectories. In Fig. (b), we illustrate failure case of GDPO when assigning a high weight to "NOV- Gen- erating novel samples is challenging. MOOD [37] addresses this challenge by controlling noise in the sampling process, whereas we achieve it by novelty optimization. However, assigning a large weight TNOV can lead the model rapidly degenerate. One potential solution is gradually increase the weight and conduct multi-stage optimization.
0.4
GDPO-64
GDPO-128
0.2
NOV (0.3)
GDPO-256
NOV (0.5)
0.3
0.0
0
10k Queries
20k
0
10k
20k
Queries
Figure 3: We investigate two key factors of GDPO ZINC250K, with the target protein being Shr/b. Similarly, the vertical axis represents the total queries, while the hor- izontal axis represents the average reward. We vary the number of trajectories for gradient estimation. (b) We fix the weight of rOED and 'SA. and change the weight of NNOv while ensuring the total weight is
7 Conclusion
We introduce GDPO, a novel policy gradient method for learning graph DPMs that effectively addresses the problem of graph generation under given objectives. Evaluation results on both general and molecular graphs indicate that GDPO is compatible with complex multi-objective optimization and achieves state-of-the-an art performance on a series of representative graph generation tasks. We discuss some limitations of our work in Appendix A.2. Our future work will investigate the theoretical gap between GDPO and DDPO in order to obtain effective unbiased estimators.
Acknowledgment
This work is supported by the Zhejiang Provincial Natural Science Foundation of China (LD24F020011) and "Pioneer and Leading Goose" R&D Program of Zhejiang (2024C01167). Chongxuan Li was supported by Beijing Natural Science Foundation (L247030); Beijing Nova Program (No. 20230484416).
References
[1] Nesreen K Ahmed, Jennifer Neville, Ryan A Rossi, and Nick Duffield. Efficient graphlet counting for large networks. In 2015 IEEE international conference on data mining, pages 1-10. IEEE, 2015.
[2] Jacob Austin, Daniel D. Johnson, Jonathan Ho, Daniel Tarlow, and Rianne van den Berg. Structured denoising diffusion models in discrete statespacces ArXiv, abs/2107.03006 2021.
[3] Yuntao Bai, Andy Jones, Kamal Ndousse, Amanda Askell, Anna Chen, Nova DasSarma, Dawn Drain, Stanislav Fort, Deep Ganguli, T. J. Henighan, Nicholas Joseph, Saurav Kadavath, John Kernion, Tom Conerly, Sheer El-Showk, Nelson Elhage, Zac Haffield-Dodds Danny Hernandez, Tristan Hume, Scott Johnston, Shauna Kravec, Liane Lovitt, Neel Nanda, Catherine Olsson, Dario Amodei, Tom B. Brown, Jack Clark, Sam McCandlish, Christopher Olah, Benjamin
10

---

Mann, and Jared Kaplan. Training a helpful and harmless assistant with reinforcement learning from human feedback. ArXiv, abs/2204.05862. 2022.
[4] Dávid Bajusz, Anita Ráez, and Károly Héberger. Why is tanimoto index an appropriate choice for fingerprint-based similarity calculations? Journal of Cheminformatics, 7, 2015.
[5] G. Richard J. Bickerton, Gaia V. Paolini, Jérémy Besnard, Sorel Muresan, and Andrew I.,
Hopkins. Quantifying the chemical beauty drugs. Nature chemistry, 4 2:90-8, 2012.
[6] Kevin Black, Michael Janner, Yilun Du, llya Kostrikov, and Sergey Levine. Training diffusion models with reinforcement learning. ArXiv, abs/2305.1332 2023.
[7] Krisztina Boda, Thomas Seidel, and Johann Gasteiger. Structure and reaction based evaluation of synthetic accessibility. Journal of Computer-Aided Molecular Design, 21:311-325, 2007.
[8] Mare Brockschmidt, Miltiadis Allamanis, Alexander L. Gaunt, and Oleksandr Polozov. Genera- tive code modeling with graphs. ArXiv, abs// 085900 2018.
[9] Nicola De Cao and Thomas Kipf. Molgan: An implicit generative model for small molecular graphs. ArXiv, abs/ abs/1805.1 11973, 2018
[10] Tobiasz Ciepliński, Tomasz Danel, Sabina Podlewska, and Stanislaw Jastrzebski. Generative models should at least be able to design molecules that dock well: A new benchmark. Journal of Chemical Information and Modeling, 63:3238 3247, 2020.
[11] Kevin Clark, Paul Vicol, Kevin Swersky, and David J. Fleet. Directly fine-tuning diffusion models on differentiable rewards. ArXiv, abs/2309. 17400, 2023.
[12] Prafulla Dhariwal and Alex Nichol. Diffusion models beat gans on image synthesis. ArXiv, 0ls/2105.05233, 2021.
[13] Jerome Eberhardt, Diogo Santos-Martins, Andreas F Tillack, and Stefano Forli. Autodock vina 1.2. 0: New docking methods, expanded force field, and python bindings. Journal of chemical information and modeling, (1()3338913389 2021.
[14] Peter Eekmann, Kunyang Sun, Bo Zhao, Mudong Feng, Michael K. Gilson, and Rose Yu. Limo: Latent inceptionism for targeted molecule generation. Proceedings of machine learning research, 162:5777-5792 2022.
[15] Paul L. Erdos and Alfréd Rényi. On the evolution of random graphs. Transactions of the American Mathematical Society, 286:257-29 257, 1984.
[16] Ying Fan, Olivia Watkins, Yuqing Du, Hao Liu, Moonkyung Ryu, Craig Boutilier, P. Abbeel, Mohammad Ghavamzadeh, Kangwook Lee, and Kimin Lee. Dpok: Reinforcement learning for fine-tuning text-to-image diffusion models. ArXiv, abs/2305. 16381, 2023.
[17] Eugene A Feinberg and Adam Shwartz. Handbook of Markov decision processes: methods and applications, volume 40. Springer Science & Business Media, 2012.
[18) Arthur Gretton, Karsten M. Borgwardt, Malte J. Rasch, Bernhard Scholkopf, and Alex Smola. kernel two-sample test. J. Mach. Learn. Res., 13:723-773, 2012.
[19] Ivo Grondman, Lucian Busoniu, Gabriel AD Lopes, and Robert Babuska. A survey of actor- critic reinforcement learning: Standard and natural policy gradients. IEEE Transactions on Systems, Man, and Cybernetics, Part C (Applications and Reviews), 129)111111 2012.
[20] Aditya Grover, Aaron Zweig, and Stefano Ermon. Graphite: Iterative generative modeling of graphs. In International Conference on Machine Learning, 2018
[21] Xiaojie Guo and Liang Zhao. A systematic survey on deep generative models for graph generation. IEEE Transactions on Pattern Analysis and Machine Intelligence, 45:5370-553 5390, 2020.
[22] Frank Harary and C. St. J. A. Dill-Willaass. eulerian and hamiltonian graphs and line graphs. Canadian Mathematical Bulletin, 8:701 - 709, 1965.

---

[23] Arman Hasanzadeh, Ehsan Hajiramezanali, Nick G. Duffield, Krishna R. Narayanan, Mingyuan Zhou, and Xiaoning Qian. Semi-implicit graph variational auto-encoders. ArXiv, abs/1908.07078, 2019.
[24] Hado Hasselt. Double q-learning. Advances in neural information processing systems, 23, 2010.
[25] Jonathan Ho, Ajay Jain, and P. Abbeel. Denoising diffusion probabilistic models. ArXiv, abs/2006. 1239, 2020.
[26] Paul Holland, Kathryn B. Laskey, and Samuel Leinhardt. Stochastic blockmodels: First steps. Social Nenworks, 5:109-137, 1983.
[27] John J. Irwin, T. Sterling, Michael M. Mysinger, Erin S. Bolstad, and Ryan G. Coleman. Zinc: A free tool to discover chemistry for biology. Journal of Chemical Information and Modeling, 52:1757 - 1768, 2012.
[28] Wengong Jin, Regina Barzilay, and T. Jaakkola. Hierarchical generation of molecular graphs using structural motifs. In International Conference on Machine Learning, 2020.
(29] Wengong Jin, Regina Barzilay, and T. Jaakkola. Multi-objective molecule generation using interpretable substructures. In International Conference on Machine Learning, 2020.
[30] Jachyeong Jo, Dongki Kim, and Sung Ju Hwang. Graph generation with diffusion mixture. arXiv preprint 2tt.:2332.035966 2023.
[31] Jachyeong Jo. Seul Lee, and Sung Ju Hwang. Score-based generative modeling of graphs via the system of stochastic differential equations. In International Conference on Machine Learning. 2022.
[32] Tero Karras, Miia Aittala, Timo Aila, and Samuli Laine. Elucidating the design space of diffusion-basee generative models. ArXiv, abs/2206.00 2022.
[33] Sarah L. Kinnings, Nina Liu, Peter J. Tonge, Richard M. Jackson, Lei Xie, and Philip E. Bourne. machine learning-based method to improve docking scoring functions and its application to drug repurposing. Journal of chemical information and modeling, 51 2:408-19, 2011.
[34] Thomas Kipf and Max Welling. Variational graph auto-encoders. ArXiv, abs/ hts//6116 1.07308, 2016.
[35] Kimin Lee, Hao Liu, Moonkyung Ryu, Olivia Watkins, Yuging Du, Craig Boutilier, P. Abbeel, Mohammad Ghavamzadeh, and Shixiang Shane Gu. Aligning text-to-image models using human feedback. ArXiv, abs/2232..12922 2023.
[36] Myeong- Sung Lee and Kyoungmin Min. Mgevae: Multi-objective inverse design via molecular graph conditional variational autoencoder. Journal of chemical information and modeling, 2022.
[37] Seul Lee, Jaehyeong Jo, and Sung Ju Hwang. Exploring chemical space with score-based out-of-distribution generation. ArXiv, abs/2206.07632, 2022.
[38] Renjie Liao, Yujia Li, Yang Song, Shenlong Wang, Will Hamilton, David K Duvenaud, Raquel Urtasun, and Richard Zemel. Efficient graph generation with graph recurrent attention networks. Advances in neural information processing systems, 32, 2019.
[39] Renjie Liao, Yujia Li, Yang Song, Shenlong Wang, Charlie Nash, William L. Hamilton, David Kristjanson Duvenaud, Raquel Urtasun, and Richard S. Zemel. Efficient graph generation with graph recurrent attention networks. Neural Information Processing Systems, 2019.
[40] Jenny Liu, Aviral Kumar, Jimmy Ba, Jamie Ryan Kiros, and Kevin Swersky, Graph normalizing flows. ArXiv, abs/1905. hbbs/1995.1317,,,.. 13177, 2019.
[41] Qi Liu, Miltiadis Allamanis, Mare Brockschmidt, and Alexander L. Gaunt. Constrained graph variational autoencoders for molecule design. In Neural Information Processing Systems, 2018.
[42] Youzhi Luo, Keqiang Yan, and Shuiwang Graphdf: A discrete flow model for molecular graph generation. In International Conference Machine Learning, 2021.
12

---

[43] Karolis Martinkus, Andreas Loukas, Nathanael Perraudin, and Roger Wattenhofer. Spectre: Spectral conditioning helps to overcome the expressivity limits of one-shot graph generators. In International Conference on Machine Learning, 2022.
[44] Duc Duy Nguyen and Guowei Wei. Agl-score: Algebraic graph learning score for protein- ligand binding scoring, ranking, docking, and screening. Journal of chemical information and modeling, 2019.
[45] Khanh Nguyen, Hal Daumé, and Jordan I.. Boyd-Graber. Reinforcement learning for bandit neural machine translation with simulated human feedback. ArXiv, abs/1707.07402, 2017.
[46] Chenhao NIu, Yang Song, Jiaming Song, Shengjia Zhao, Aditya Grover, and Stefano Ermon. Permutation invariant graph generation via score-based generative modeling. In International Conference Artificial Intelligence and Statistics, 2020.
[47] Marcus Olivecrona, Thomas Blaschke, Ola Engkvist, and Hongming Chen. Molecular de-novo design through deep reinforcement learning, Journal of Cheminformatics, 9, 2017.
[48] Nataraj Sekhar Pagadala, Khajamohiddin Syed, and Jack Adam Tuszynski. Software for molecular docking: a review. Biophysical Reviews, 9:91 102, 2017.
[49] Daniil Polykovskiy, Alexander Zhebrak, Benjamín Sánchez- Lenghliz,eng,,ing, Sergey Golovanov, Oktai Tatanov, Stanislav Belyaev, Rauf Kurbanov, Aleksey Anatolievich Artamonov, Vladimir Aladinskiy, Mark Veselov, Artur Kadurin, Sergey I. Nikolenko, Alán Aspuru-Guzik, and Alex Zhavoronkov. Molecular sets (moses): A benchmarking platform for molecular generation models. Frontiers in Pharmacology, 11, 2018.
[50] Mihir Prabhudesai, Anirudh Goyal, Deepak Pathak, and Katerina Fragkiadaki. Aligning text-to- image diffusion models with reward backpropagation. ArXiv, abs/2310.03739, 2023.
[51] Rafael Rafailov, Archit Sharma, Eric Mitchell, Christopher D Manning, Stefano Ermon, and Chelsea Finn. Direct preference optimization: Your language model is secretly a reward model. Advances in Neural Information Processing Systems, 36, 2024.
[52] Davide Rigoni, Nicoló Navarin, and Alessandro Sperduti. Conditional constrained graph variational autoencoders for molecule design. 2020 IEEE Symposium Series on Computational Intelligence (SSCI), pages 729-736, 2020.
[53] Chence Shi, Minkai Xu, Zhaocheng Zhu, Weinan Zhang, Ming Zhang, and Jian Tang. Graphaf: a flow-based autoregressive model for molecular graph generation. ArXiv, Abs/2001.09338 2020.
[54] Martin Simonovsky and Nikos Komodakis. Graphvae: Towards generation of small graphs using variational autoencoders. In International Conference on Artificial Neural Networks, 2018.
[55] Sara Nadiv Soffer and Alexei Vazquez. Network clustering coefficient without degree- correlation biases. Physical Review E, 71(55)057101,
[56] Jascha Narain Sohl-Diekstein, Eric A. Weiss, Niru Maheswaranathan, and Surya Ganguli. Deep unsupervised learning using nonequilibrium thermodynamics. ArXiv, 00//15033.33883 2015.
[57] Yang Song, Jascha Narain Sohl-Dickstein, Diederik Kingma, Abhishek Kumar, Stefano Er- mon, and Ben Poole. Score-based generative modeling through stochastic differential equations. ArXiv, abs/201 1.1456,,. 2020.
[58] Richard S. Sutton and Andrew G. Barto. Reinforcement learning: An introduction. IEEE Trans. Neural Networks, 9:1054-1054, 1998.
[59] Richard S. Sutton, David A. McAllester, Satinder Singh, and Y. Mansour. Policy gradient methods for reinforcement learning with function approximation. In Neural Information Processing Systems, 1999.
13

---

[60] Oleg Trott and Arthur J. Olson. Autodock vina: Improving the speed and accuracy of docking with new scoring function, efficient optimization, and multithreading. Journal of Computa- lional Chemistry, 31, 2009.
[61] Clément Vignac, Igor Krawezuk, Antoine Siraudin, Bohan Wang, Volkan Cevher, and Pascal Frossard. Digress: Discrete denoising diffusion for graph generation. ArXiv, 0tts/2209.147335 2022.
[62] Hongwei Wang, Jia Wang, Jialin Wang, Miao Zhao, Weinan Zhang, Fuzheng Zhang, Xing Xie, and Minyi Guo. Graphgan: Graph representation learning with generative adversarial nets. ArXiv, abs/1711.08220 2017.
[63] Yulun Wu, Mikaela Cashman, Nicholas Choma, Erica Prates, Verónica G Melesse Vergara, Manesh Shah, Andrew Chen, Austin Clyde, Thomas S Brettin, Wibe A de Jong, et al. Spa- tial graph attention and curiosity-driven policy for antiviral drug discovery. arXiv preprint arXiv:2106.02190, 2021.
[64] Saining Xie, Alexander Kirillov, Ross B. Girshick, and Kaiming He. Exploring randomly wired neural networks for image recognition. 2019 IEEE/CVF International Conference on Computer Vision (ICCV), pages 1284-1293, 2019.
[65] Yutong Xie, Chence Shi, Hao Zhou, Yuwei Yang, Weinan Zhang, Yong Yu, and Lei Li. Mars: Markov molecular sampling for multi-objective drug discovery. ArXiv, abs/2103 10432, 2021.
[66] Carl Yang. Peiye Zhuang, Wenhan Shi, Alan Luu, and Pan Li. Conditional structure generation through graph variational generative adversarial nets. In Neural Information Processing Systems, 2019.
[67] Soojung Yang, Doyeong Hwang, Seul Lee, Seongok Ryu, and Sung Ju Hwang. Hit and lead discovery with explorative rl and fragment-based molecule generation. ArXiv, abs/21 10.01219, 2021.
[68] Jiaxuan You, Bowen Liu, Rex Ying, Vijay S. Pande, and Jure Leskovec. Graph convolutional policy network for goal-directed molecular graph generation. In Neural Information Processing Systems, 2018
[69] Jiaxuan You, Rex Ying, Xiang Ren, William L. Hamilton, and Jure Leskovec. Graphrnn: Generating realistic graphs with deep auto-regressive models. In International Conference on Machine Learning, 2018.
[70] Mengchun Zhang, Maryam Qamar, Taegoo Kang, Yuna Jung, Chenshuang Zhang, Sung- Bae, and Chaoning Zhang. A survey on graph diffusion models: Generative ai in science for molecule, protein and material. ArXív, abs/2304.015665 2023.
[71] Zhenpeng Zhou, Steven Kearnes, Li Li, Richard N Zare, and Patrick Riley. Optimization of molecules via deep reinforcement learning. Scientific reports, 10): 2019.
[72] Zhenpeng Zhou, Steven M. Kearnes, Li Li, Richard N. Zare, and Patrick F. Riley. Optimization of molecules via deep reinforcement learning. Scientific Reports, 9, 2018.
14

---

A Experimental Details and Additional Results
A.1 Implementation Details.
For all experiments, we use the graph transformer proposed in DiGress [61] as the graph DPMs. and the models are pre-trained on the training dataset before applying GDPO or DDPO. During fine-tuning, we keep all layers fixed except for attention, set the learning rate utilize gradient clipping to limit the gradient norm to be less than or equal to 1. In addition, due to significant numerical fluctuations during reward normalization, the normalized reward to the range from |-5, 5). This means that gradients resulting from rewards beyond this range will not contribute model updates. When there is insufficient memory generate enough trajectories, we use gradient accumulation to increase the number of trajectories used for gradient estimation. We conducted all experiments single A 110 GPU with 40GB of VRAM and an AMD EPYC 7352 24-core Processor.
0.00001, and
follow DDPO [6] in constraining
Training time and efficiency. Training DiGress the ZINC250K dataset using single A100 GPU typically takes 48-72 hours, whereas fine-tuning with GDPO takes only 10 hours (excluding the time for reward function computation). This high efficiency is in line with the findings in the practice of DDPO, which is different from traditional RL methods. Additionally, as in Fig. 3 and Sec 6.3, GDPO effectively improves the average reward of the model using only 10,000 queries. This sample size is notably small compared to the 250,000 samples present in the ZINC250K dataset, showing the impressive sample efficiency of GDPO.
A.2 Limitations and Broader Impact.
Below we list some limitations of the current work:
Potential for overoptimization: As an RL--based approach, a recognized limitation is the risk of overoptimization. where the DPM distribution may collapse or diverge excessively from the original distribution. In Section 6.3, we demonstrated failure case where, with high weight on novelty the reward function, GDPO encounters sudden drop in reward after a period of optimization. Future research could explore the application of regularization techniques, similar to those utilized recent works such as DPO [51], to mitigate this risk.
Inherited limitations of DPMs: Our method inherits certain limitations inherent to diffusion models, particularly concerning their training and inference costs. As we do not modify the underlying model architecture, these constraints persist.
Scalability to large graphs: The scalability of GDPO to larger graphs (e.g., with 500 or more nodes) remains unexplored.
For broader impact, this paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
A.3 General Graph Generation
Baselines. There are several baseline methods for general graph generation, we summarize them as follows:
deep autoregressive model designed model and generate complex distribu- tions over graphs. It addresses challenges like non-uniqueness and high dimensionality by decomposing the generation process into node and edge formations.
GraphRNN:
SPECTRE: a novel GAN for graph generation, approaches the problem spectrally by generating dominant parts of the graph Laplacian spectrum and matching them to eigenvalues and eigen- vectors. This method allows for modeling global and local graph structures directly, overcoming issues like expressivity and mode collapse.
GDSS: A novel score-based generative model for graphs is introduced to tackle the task of capturing permutation invariance and intricate node-edge dependencies in graph data generation. This model employs continuous-time framework incorporating novel graph diffusion process,
15

---

Algorithm 1: Graph Diffusion Policy Optimization
Input: graph DPM po
Input: # of diffusion steps T, of timestep samples [T]
Input: reward signal r(-). # of trajectory samples K
Input: learning rate 1) and # of training steps N
Output: Final graph DPM ps
for i I,..., N do
for k lk....., K do
((k) Pa
// Sample trajectory
Tk ~ Uniform [1,
// Sample timesteps
rk + )
// Get rewards
11 Estimate reward mean and variance
f x R Tk std]r] Ee (r
K-1
// Estimate the eager policy gradient
g + k
Σ
K
T
stdlr
No Poggoo(G) ( (K)
LET 1/ Update model parameter
k=1
0 + 17 (0)
characterized by stochastic differential equations (SDEs), to simultaneously model distributions of nodes and edges.
DiGress: DiGress is a discrete denoising diffusion model designed for generating graphs with categorical attributes for nodes and edges. It employs a discrete diffusion process to iteratively modify graphs with noise, guided by a graph transformer network. By preserving the distribution of node and edge types and incorporating graph graph-theoretic features, DiGress achieves state-of- the-art performance on various datasets.
MOOD: MOOD introduces Molecular Out-ff-disribbtionn Diffusion, which employs out-of- distribution control in the generative process without added costs. By incorporating gradients from property predictor, MOOD guides the generation process towards molecules with desired properties, enabling the discovery of novel and valuable compounds surpassing existing methods.
The metrics of general graph generations are all taken from GraphRNN [38]. The reported metrics compare the discrepancy between the distribution of certain metrics on a test set and the distribution of the same metrics on generated graph. The metrics measured include degree distribu- tions, clustering coefficients, and orbit counts (which measure the distribution of all substructures of size 4). Following DiGress [61], we do not report numbers but ratios computed as follows:
Metrics.
MMD (generate, tesr) MMD MMD((raining, test)²
(13)
Besides, we explain some metries that are used in the general graph generation:
the clustering coefficient measures the tendency of nodes to form clusters in a network. Real-world networks, especially social networks, often exhibit tightly knit groups with more ties between nodes than expected by chance. There are two versions of this measure: global, which assesses overall clustering in the network, and local, which evaluates the clustering around individual nodes.
Clus:
Orb: Graphlets are induced subgraph isomorphism classes in graph, where occurrences isomorphic or non-isomorphic. They differ from network motifs, which are over- or under- represented graphlets compared to random graph null model. Orb will count the occurrences of each type of graphlet in a graph. Generally, if two graphs have similar numbers of graphlets, they are considered to be relatively similar.
A.4 Molecule Property Optimization
Implementation Details. Following FREED [67], we selected five proteins, PARP-1 (Poly [ADP- ribose] polymerase-1), FA7 (Coagulation factor VII), 5-HTIB (6-hydroxytryplammne receptor IB),
16

---

BRAF (Serine/trreonine-rroonn proteei kinase B-raf), and JAK2 (Tyrosine-prottss protein kinase JAK2), which have the highest AUROC scores when the pooein-ligannd binding affinities for DUD-E ligands are approximated with AutoDock Vina [13], as the target proteins for which the docking scores are calculated. QED and SA scores are computed using the RDKit library.
Baselines. There are several bascline methods for molecular graph generation under the given objectives, they are diverse in methodology and performance, we summarize them follows:
GCPN: Graph Convolutional Policy Network (GCPN) a general graph convolutional network- based model for goal-directed graph generation using reinforcement learning. The GCPN is trained optimize domain-specific rewards and adversarial loss through policy gradient, operating within an environment that includes domain-specific rules.
REINVENT: This method enhances sequence-based based generative model for molecular design by incorporating augmented episodic likelihood, enabling the generation of structures with specified properties. successfully performs tasks such as generating analogs to a reference molecule and predicting compounds active against specific biological target.
HierVAE: a hierarchical graph encoder-decoder for drug discovery, overcoming limitations of previous approaches by using larger and more flexible graph motif's building blocks. The encoder generates a multi-resolution representation of molccules, while the decoder adds motifs in coarse-to-fine manner, effectively resolving attachments the molecule.
FREED: a novel reinforcement learning (RL) framework for generating effective acceptable molecules with high docking scores, crucial for drug design. FREED addresses challenges in generating realistic molecules and optimizing docking scores through a fragment- based generation method and error-prioritized experience replay (PER).
MOOD: please refer to Appendix A.3.
Metries. There are several metrics for evaluating the molecule properties, we summarize the meaning of these metrics as follows:
Docking simulations aim to find the best binding mode based on scoring functions. Scoring functions in computational chemistry and molecular modeling predict binding affinity between molecules post-docking. They are commonly used for drug-protein interactions, but also for protein-protein protein-DNA interactions. After defining the score function, we can optimize to find the optimal drug-protein matching positions and obtain the docking score.
Docking Score:
QED: Drug-likeness evaluation in drug discovery often lacks nuance, leading to potential issues with compound quality. We introduce QED, a measure based on desirability, which considers the distribution of molecular properties and allows the ranking of compounds by relative merit. QED intuitive, transparent, and applicable to various settings. We extend its use to assess molecular target druggability and suggest it may reflect aesthetic considerations in medicinal chemistry.
SA: scoring method for rapid evaluation of synthetic accessibility, considering structural complexity, similarity to available starting materials, and strategic bond assessments. These components are combined using additive scheme, with weights determined via linear re- gression analysis based on medicinal chemists' accessibility scores. The calculated synthetic accessibility values align well with chemists' assessments.
A.5 Additional Results of the GDPO
Table 5: General graph generation on SBM and Planar datasets with different reward signals.
PLANAR GRAPHS
METROD
Deg
Clus
Orb
YUN.7)
Validity (0.6)
0.03 1 0.03
0.54 + 0.08
0.02
: 0.01
72.34 4: 2.78
Validity (0.7)
0.62
0.02
73.83
Validity (0.8)
0.12 0.00
0.88
+ 0.34
0.24
+ 0.07
78.68 + 3.12
Validiry (0.9)
0.86 +: 0.12
2.17
0.84
1.46 0.78
81.26 - 3.02
Study of the Reward Signals. In Table. 5, we showcase the performance of GDPO on Planar under
different configurations of reward weights. We keep the three weights related to distance the same
17

---

and adjust the weight of validity while ensuring that the sum of weights is 1. The results indicate that GDPO not very sensitive the weights of several reward signals for general graph generation. even though these weight configurations vary significantly, they all achieve good performance. Additionally, we found that GDPO can easily increase VUN. to above 80 while experiencing slight losses in the other three indicators. When applying GDPO in practice, one can make tradeoff between them based on the specific application requirements.
Table 6: Study of the Important Sampling on ZINC250K.
METHOD
METRIC
perpi
TARGET PROTEIN
JoX
DDPO
DS (op 5%)
Hit Ratio
-9.247 0.21
0.419 0.280
-7 -7.739 1 0.244
0.312 = 0.085
-9.488 1: 0,287
5.488 1 1,989
-9.470
0.445 1
-8,990 4: 0.221
1.717 1. 0.684
DDPO-IS
Hit Ratio trop 5%%
0.945 0.385
0.206
0.319 0.257
-7.530 0.225
10.301 1.277
0.174
0.136 0:272
2,097 0.462
-9.120
GDPO-IS
DS top 5%%
Hit Ratio
-9. =: 0.300
0.850 0.602
- -8.254 à: 0.180
0.826 = 0.827
-10,361 4: 0.319
16,283 1,100
-9.771 =: 0.120
1,330
0.392
-9,563 1: 0.202
4,381 +: 0.501
GDPO (OURS)
Hiz Ratio
(rop 57%)
10.938 0.042
3.449
8.691 0.074
34.359 + 2.734
11.304 0.093
9.033
11.197 0.132
1,477
13.405 1,151
10.183
The Impact of Important Sampling. The importance sampling technique in DDPO, aims to facilitate multiple steps of optimization using the same batch of trajectories. This is achieved by weighting each item on the trajectory with an importance weight derived from the density ratio estimated using the model parameters from the previous step Oprev and the current step 0 (referred to as DDPO-IS):
T
pe Po(G(_1|G,) Vo Po (G--1I))
V FoJDDPO is (s = Er r(Go)
Σ t=1 Po... (G.-I(G)
(14)
Our eager policy gradient, independently motivated, aims to address the high variance issue of the policy gradient in each step of optimization, as elaborated in Sec. 4.2. Intuitively, the eager policy gradient can viewed as a biased yet significantly less fluctuating gradient estimation.
We conducted a series of experiments on ZINC250K to compare DDPO, DDPO-IS, and GDPO. The experimental setup remains consistent with the description in Section 6.2. Additionally, consider- ing that the importance sampling technique in DDPO and our eager policy gradient appear to be orthogonal, we also explored combining them simultancously (referred to GDPO-IS):
Go) V log (oggo( Po (GolGr)
VeJuDroAs (0) E, r(Gu) Σ
(15)
In Table. 6, while importance sampling enhances the performance of DDPO, consistent with the results reported in the DDPO paper, it does not yield improvements for GDPO-IS over GDPO. We speculate that this discrepancy may be due to the biasness of the eager policy gradient, rendering it incompatible with the importance sampling technique. We intend to investigate the mechanism and address this in our future work. Nevertheless, it is noteworthy that the performance of DDPO-IS remains inferior to GDPO, indicating the superiority of our proposed GDPO method.
Table 7: Novelty and Diversity on ZINC250K.
TARGET PROTEIN
METRIC
parpl
fa7
Shrlb
braf
jak2
TOU
0.0763%
0.0752% 97.35%
0.0744%
0.113% 99.74%
0.0759% 97.02%
UNIQ
94.86%
99.86%
Novelty and Diversity of GDPO. To provide further insight into the novelty and diversity of our approach, we introduce two additional metrics:
Intersection over Union (loU): We compare two sets of molecules: 1) 500 molecules generated by GDPO (denoted GDPO) and 2) top 500 molecules among 10,000 molecules generated by our base DPM before finetuning (denoted as TopPrior). We then compute IoU=100 x JGDPonTopPriar %. We report average loU of 5 independent runs. GDPOUTopPrior
18

---

Uniqueness in 10k samples (Uniq): We generate 10,000 molecules and compute the ratio of unique molecules Uniq = 100 x unique molecules %.
all molecules
In Table. 7, these results show that GDPO has not converged to a trivial solution, wherein it merely selects subset of molecules generated by the prior diffuusion model. Instead, GDPO has learned an effective and distinct denoising strategy from the prior diffusion model.
The Gap between Image DPMs and Graph DPMs. GDPO is tackling the high variance issue inherent in utilizzig policy gradients on graph DPMs, as stated and discussed in Sec. 4.2. To provide clarity on what GDPO tackles, we would like to elaborate more on the high variance issue of policy gradients on graph DPMs. Consider the generation trajectories in image and graph DPMs:
In image DPMs, the generation process follows a (discretization of) continuous diffusion process (x)) The consecutive steps x and x; are typically close due to the Gaussian reverse denoising distribution p(x;-1|X; ) (typically with a small variance).
In graph DPMs, the generation process follows discrete diffusion process (Gr...., Gg), where each G. is concrete sample (i.e., one-hot vectors) from categorical distributions. Therefore, consecutive steps G5-1 and G. can be very distant. This makes the trajectory of graph DPMs more fluctuating than images and thus leads to high variance of the gradient Ve log p( G,-1GGG, |G,] (and the ineffectiveness of DDPO) when evaluated with same number of trajectories as in DDPO.
Regarding the "distance" between two consecutive steps G2 and G--1, our intuition stems from the fact that graphs generation trajectories are inherently discontinuous. This means that each two consecutive steps can differ significantly, such as in the type/existence of edges. In contrast, the generation trajectories of images, governed by reverse SDEs, are continuous. This continuity implies that for fine- grained discretization (i.e., large T), X, and - can be arbitrarily close to each other (in the limit case of T - X)).
Distance conseculive sleps
0.4
Image Offiuan Graph Defhutoon
Dittance
62-
6.1
0.0
50c
Diftusion Steps
Figure 4: We investigate the I.2 distance between two consecutive steps in two types of DPMs. The diffusion step is 1000 for two models.
To provide quantitative support for this discussion, we conduct an analysis comparing the distances between consecutive steps in both image and graph DPMs. We employ a DDPM [a] pre-trained on CIFAR-10 10 for image diffusion and DiGress [b] pre-trained on the Planar dataset for graph diffusion, both with a total of T 1000 time steps. In these models, graphs are represented with one-hot vectors (as described in Sec. 3) and image pixels are rescaled to the range [0, 1]. ensuring their scales comparable. We then directly compare the per-dimension L2 distances in both spaces, denoted as ||G, - G. //2/ DD and | x,-1 x /De, where Da and D, are the dimensions of graphs and images, respectively. (Dividing by vD is to eliminate the influence of different dimensionalities.) We sample 512 trajectories from each DPM and plot the mean and deviation of distances with respect to the time step t.
In Fig. 4, the results support the explanation of GDPO. While we acknowledge that graphs and images reside in different spaces and typically have different representations, we believe the comparison with 1.2 distance can provide valuable insights into the differences between graph and image DPMs.
GDPO on the Synthetic Tree-like Dataset. We first generate a tree and then connect clique to the nodes of the tree, performing a specified number of rewrite operations suggested. Based on
19

---

(a) Rewrite Step O.
(b) Rewrite Step 1.
(c) Rewrite Step = 2.
(d) Rewrite Step = 3.
(e) Node 16.
(f) Node =
(g) Node
(h) Node = 40.
(i) Shallow Clique Position.
(i) Middle Clique Position.
(k) Deep Clique Position.
Figure 5: Tree with Different Parameters. Node the root node.
Qualti
Quien
(a) Performance of GDPO under different rewrite steps.
(b) Performance GDPO under different graph sizes.
(c) Comparison with DDPO and GDPO.
Figure 6: Ablation Study on the Synthetic Tree-like Dataset.
the number of rewrite steps, graph size, and clique position, generate multiple datasets, each containing 400 samples. Of these, 256 samples are used for training Graph DPMs, with the remaining samples allocated for validation and testing. In Fig. a tree structure with a clique of size 4. When the number of rewrite steps is 3, Fig. 5(d) demonstrates that the overall structure of the samples disrupted. After training the Graph DPMs, we apply GDPO. The model receives a reward of I when it generates a tree with clique; otherwise, the reward is 0. We then ablate the following factors to test the performance GDPO.
present
examples. Fig. 5(a)illustrates
Rewrite Steps: In Fig. 6(a), we demonstrate GDPO's performance across different rewrite steps, with four curves representing steps ranging from 0 to 3. Despite notable decrease in the initial reward as the number of rewrite steps increases, GDPO consistently optimizes the Graph DPMs effectively to generate the desired graph structure.
Graph Size: In Fig. 6(b), we gradually increase the number of nodes from to 40. The results show that graph size affects the initial reward but does not impact GDPO's optimization performance.
20

---

We experiment with inserting the clique at different levels of the tree but find no significant difference. We believe this is because the position of the clique does not affect the initial reward of the Graph DPMs, leading to similar optimization results with GDPO.
Clique Position:
Comparison with Baseline: In Fig. 6(c), compare GDPO with DDPO. The results, consistent with those in Figure 2 of the paper, reveal a clear distinction between GDPO and DDPO in handling challenging data generation tasks.
A.6 Discussions
Comparison with the zo-prediction Formulation. Indeed, our eager policy gradient in Eq. 10, compared the policy gradient of REINFORCE in Eq. 8, resembles the idea of training denois- ing network to predict the original uncorrupted graph rather than performing one-step denoising. However, note that training denoising network to predict the original data is fundamentally matter of parametrization of one-step denoising. Specifically, the one-step denoising pa (Z+=1(G:) parameterized as a weighted sum of zo-prediction, described in Eq. 1. Our method in Eq. is motivated differently, focusing on addressing the variance issue as detailed in Sections 4.2 and 4.3.
Pros and Cons of the RL Approach against Massiffer-based and Classifier-free Guidance for Graph DPMs. Compared to graph diffusion models using Mlassfier-basee and classifier-free guidance, RL approaches such as GDPO have at least two main advantages:
Compatibility with discrete reward signals and discrete graph representations: As guidance for diffusion models is based on gradients, differentiable surrogate (e.g., property predic- tors [65, 37J) is needed for con-differentiable reward signals (e.g., results from physical simulations). RL approaches naturally accommodate arbitrary reward functions without the need for intermediate approximations.
Better sample efficiency: For graph diffusion models with classifier- baased or classifier-fi free guidance, labeled data are required at the beginning and are independently collected with graph diffusion models. In contrast, RL approaches like GDPO collect labeled data during model training, thus allowing data collection from the current model distribution, which can be more beneficial. We also empirically observe significant gap in sample efficiency.
Analysis on the Bias-variance Trade off. The main bias of GDPO arises from modifying the "weight" term in Fq. 9, which shifts the model's focus more towards the generated results rather than the intermediate process, thereby reducing potential noise. Due to the discrete nature of Graph DPMs, the zo- po-prediction and zT- -predicciiiion formulations cannot be related through denoising objectives as in continuous DPMs. This issue also complicates the connection between DDPO and GDPO. We have not yet identified a relevant solution and are still working on do not observe significant performance variance and tradeoff for GDPO given the current scale of experiments. This may be due to the graph sizes we explored not being sufficiently large. future implementations, will incorporate support for sparse graphs to assess GDPO's performance larger graph datasets and investigate the tradeoff more thoroughly.
our empirical study, we
21

---

NeurIPS Paper Checklist
1. Claims
Question:
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
We carefully check the claims, and they align with our evaluation.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors? Answer: [Yes]
Justification: We illustrate the limitations of our work with a failure case. Additionally, we discuss the limitations from various perspectives the appendix.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [NA]
22

---

Justification:
Our paper does not propose any theoretical results.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification: All the implementation details are discussed in the appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm. (b) the contribution is primarily a new model architecture, the paper should describe the architccture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility. the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
23

---

Answer: [Yes]
Justification: the supplementary materials, we provide the code, dataset, and instructions for reproduction.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to to reproduce the results. See the NeurlPS code and data submission guidelines (https:
/eddeS/eeeub ssi wsw.nnoliccgiooeoooo for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: In the experimental setup section, we provide detailed instructions.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: All statistical results are obtained by repeating the experiment five times, and the corresponding standard deviations are provided.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).

---

It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative enror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification:
In the appendix, we provide these contents.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics https / //t//nnurip.../ wttprripp.ccpppppppe httpppppiicttictiiiieieeeeeeeeee
Answer: [Yes]
Justification: This work falls under the general machine learning domain, and during the research process, we adhered to the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: the appendix, we discuss the potential impacts of this work in detail.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
25

---

The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: This work does not involve any relevant datasets or models.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g.. code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: All datasets used in this paper are open-source, and there are no copyright issues involved.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
26

---

If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: This work is based on existing datasets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
This work does not involve any related issues.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: This work does not involve any related issues.
Guidelines:
The answer NA means that the paper does involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
27


Reviews:
[{"review_id": "8RoCvliZjS", "reviewer": "Reviewer_gTVc", "summary": "This paper introduces Graph Diffusion Policy Optimization (GDPO), a novel approach to optimize graph diffusion models for arbitrary objectives using reinforcement learning. The key contributions are:\n\n1. Formulating the denoising process of graph diffusion probabilistic models (DPMs) as a Markov decision process and proposing an \"eager policy gradient\" method tailored for graph DPMs to address high variance issues in standard policy gradient approaches.\n2. Demonstrating state-of-the-art performance on various graph generation tasks, including general graph generation and molecular graph generation with complex objectives.\n\nThe authors show that GDPO significantly outperforms baseline methods, including other graph generation techniques and adaptations of diffusion model optimization approaches from the image domain (e.g., DDPO).", "questions": "1. How sensitive is GDPO to the choice of reward function? Are there certain types of rewards or objectives that are particularly challenging for the method (e.g., very sparse, high dynamic range, noisy...)?\n2. I'd like to suggest an important ablation study on highly ambiguous graphs to better understand the limitations and robustness of GDPO. Specifically, I propose constructing a \"noisy-tree-with-planted-motifs\" dataset with the following process:\n\n---\n\n1. Generate a base tree structure with parameters:\n   - Tree depth\n   - Minimum fan-out factor\n   - Maximum fan-out factor\n   - Binned beta variation across the fan-out for a given node\n\n2. Plant a tree of cliques as an expansion of  nodes at a chosen height in the base tree. This planted structure should have parameters:\n   - Number of rings of cliques\n   - Ring size and clique count\n\n3. Apply a noisy rewiring process towards an Erdős-Rényi random graph with the same number of nodes and edges as the base graph. This process should take as parameters:\n   - Number of rewiring steps\n   - starting layer of the subgraph to be noised (starting at a given layer of the tree)\n  \nThe noisy rewiring process would involve:\na) Randomly selecting an edge\nb) Checking whether to remove it based on the probability of an edge existing in the target Erdős-Rényi graph\nc) Selecting a random node pair to potentially add an edge\nd) Repeating this process for the specified number of steps\n\nI suggest ablating over:\n1. The number of rewiring steps\n2. The size of the subgraph to be noised\n3. The overall graph size\n4. The height at which the tree of cliques is planted\n5. (optional) clique size and ring size\n\nMy hypothesis is that GDPO would struggle to maintain the planted tree of cliques structure and the overall tree structure as the noise level and graph size increase, as it would slowly fill up the capacity of the model with combinatorial structures. This ablation study would provide valuable insights into GDPO's performance on more complex and ambiguous graph structures.\n\nQuestions I'd like answered through this ablation study:\n\n1. How does GDPO's performance change as the noise level (number of rewiring steps) increases?\n2. What is the impact of graph size on GDPO's ability to maintain the planted tree of cliques and the overall tree structure?\n3. Is there a critical point in the noise level or graph size where GDPO's performance significantly degrades?\n4. How does the height at which the tree of cliques is planted affect GDPO's ability to maintain this structure? (i.e., how well does it maintain long-range dependeny)\n5. How does GDPO compare to baseline methods on these more challenging graph structures?\n6. Can you identify specific types of motifs or structures within the planted tree of cliques that GDPO struggles to maintain or generate in these noisy environments?", "limitations": "I think the limitations in the appendix are acceptable", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. Novelty and Originality:  Introduction of the \"eager policy gradient\" method, to address the high variance issues encountered with standard policy gradients in graph diffusion models. Despite the lack of theory supporting it, it's a clever  solution to a significant challenge in optimizing these models for arbitrary objectives.\n\n2. Clarity:\n   - Clear problem formulation: The authors provide a well-structured explanation of the challenges in optimizing graph DPMs and why existing methods fall short.\n   - Effective visualization: Figure 1 offers a clear overview of the GDPO method, aiding understanding of the approach.\n   - Detailed ablation studies: The paper includes thorough analyses of different components and configurations of GDPO, which helps clarify the contribution of each aspect of the method.\n\n3. Significance:\n   - Strong performance improvements: GDPO demonstrates substantial gains over state-of-the-art baselines across various graph generation tasks. For example, in molecular graph generation, it achieves up to a 19.31% improvement in hit ratio for generating effective drugs.\n   - Sample efficiency: The method achieves good results with relatively few queries (e.g., 1/25 of the training samples), which is crucial for applications where reward evaluation may be computationally expensive, such as drug discovery.\n   - Broad applicability: GDPO is flexible and can be applied to a wide range of graph generation tasks with complex, multi-objective reward functions. This versatility enhances its potential impact on the field.\n\n4. Technical Quality:\n   - Thorough experimentation: The authors provide extensive experiments on both general graph generation and molecular graph generation tasks, lending credibility to their claims.\n   - Careful analysis of baseline methods: The paper includes a detailed study of  DDPO (a related method for image diffusion models) failing on graph DPMs, which strengthens the justification for GDPO.\n   - Consideration of practical aspects: The authors address important practical considerations such as the impact of different reward weightings and the number of trajectories used for gradient estimation.", "weaknesses": "- Limited theoretical analysis: While the eager policy gradient is empirically effective, the paper lacks a rigorous theoretical treatment of its properties, particularly regarding the bias-variance trade-off.\n-  The paper would benefit from a comparison to other RL-utilizing graph generation methods, particularly MolGAN https://arxiv.org/pdf/1805.11973 , which also applies RL techniques to molecular graph generation.\n- Scalability concerns: The paper does not explore the method's performance on very large graphs (e.g., 500+ nodes), leaving questions about its scalability unanswered.\n- Limited exploration of failure cases: While the authors provide a failure case related to novelty optimization, a more comprehensive exploration of scenarios where GDPO struggles would provide valuable insights into its limitations.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your insightful comments and valuable suggestions. Below, we respond to the concerns raised in ***Weaknesses (W)*** and ***Questions (Q)***.\n\n---\n\n***W1: Theoretical Analysis, Scalability, and Failure Cases***\n\nThank you for highlighting these points. Despite considerable efforts, theoretical analysis of the eager policy gradient remains challenging due to the discrete nature of Graph DPMs. We will continue to address this in future work. While GDPO shows significant efficiency, its scalability to larger graphs is constrained by the inherent limitations of graph DPMs, particularly concerning GPU memory. In future implementations, we aim to introduce support for sparse graphs to enhance scalability. Regarding failure cases, in addition to the case mentioned in Section 6.3, we believe that potential failure cases likely arise from tasks with very sparse reward signals. We will add further discussion to the final paper.\n\n---\n\n***W2: Comparison with RL-based graph generation methods***\n\nThank you for your suggestion. We discussed MolGAN in the Introduction (line 32). We have also compared GDPO with several representative and leading RL-based Graph Generation Methods, such as GCPN, REINVENT, and FREED. These methods optimize graph neural networks to generate molecules with specific properties by designing molecule encoding schemes and utilizing modern RL techniques.\n\n---\n\n***Q1: Discussion on reward selection***\n\nIn Appendix A.5,  Table 5, we investigated the sensitivity of GDPO to different rewards. The results demonstrate that adjusting the weights of sub-rewards does not significantly impact model performance, indicating that GDPO has a certain degree of robustness to reward variation. However, very sparse rewards generally pose a challenge. As detailed in Algorithm 1 in Appendix, GDPO normalizes the received rewards. For very sparse rewards (e.g., most rewards are zero and a few are one), the normalized values can become very large, leading to instability in optimization. To mitigate this issue, we follow DDPO in clipping gradients and discarding gradients generated by extremely large rewards. However, for extreme cases, these techniques may also fail. We will include further discussion on this topic in the final version.\n\n---\n\n***Q2: Ablation study on noisy tree with planted motifs***\n\nThank you for sharing the idea. Based on your proposed setting, we conduct additional experiments. Due to time constraints, we do not perform extensive parameter exploration. Additionally, we made some simplifications to facilitate implementation and better explore the key factors. We first generate a tree and then connect a clique to the nodes of the tree, performing a specified number of rewrite operations as suggested. Based on the number of rewrite steps, graph size, and clique position, we generate multiple datasets, each containing 400 samples. Of these, 256 samples are used for training Graph DPMs, with the remaining samples allocated for validation and testing.\n\nIn $\\\\textrm{\\\\color{blue}Figure A}$ of the rebuttal PDF, we present some examples. $\\\\textrm{\\\\color{blue} Figure A(a)}$ illustrates a tree structure with a clique of size 4. When the number of rewrite steps is 3, $\\\\textrm{\\\\color{blue} Figure A(d)}$ demonstrates that the overall structure of the samples is disrupted.\n\nAfter training the Graph DPMs, we apply GDPO. The model receives a reward of 1 when it generates a tree with a clique; otherwise, the reward is 0.\n\n**Rewrite Steps** In $\\\\textrm{\\\\color{blue} Figure B(a)}$, we demonstrate GDPO's performance across different rewrite steps, with four curves representing steps ranging from 0 to 3. Despite a notable decrease in the initial reward as the number of rewrite steps increases, GDPO consistently optimizes the Graph DPMs effectively to generate the desired graph structure.\n\n**Graph Size** In $\\\\textrm{\\\\color{blue} Figure B(b)}$, we gradually increase the number of nodes from 16 to 40. The results show that graph size affects the initial reward but does not impact GDPO’s optimization performance.\n\n**Critical Point** In the current Ablation Study, we do not observe any clear change points. This may be due to the limited range of parameters explored. We will include additional experiments in the final version to address this.\n\n**Clique Position** We experiment with inserting the clique at different levels of the tree but find no significant difference. We believe this is because the position of the clique does not affect the initial reward of the Graph DPMs, leading to similar optimization results with GDPO.\n\n**Comparison with Baseline** In $\\\\textrm{\\\\color{blue} Figure B(c)}$, we compare GDPO with DDPO. The results, consistent with those in  Figure 2 of the paper, reveal a clear distinction between GDPO and DDPO in handling challenging data generation tasks.\n\n**Challenging Motifs** Based on the current results, we do not observe related behaviors. However, as indicated by the results in  Table 1 of the paper, generating planar graphs with specific macro-topological features is quite challenging for GDPO. This is due to the model’s need to perform global summarization of the graph structure, and the rewards are typically sparse.\n\nThank you very much for your suggestions. We will include the above discussions in the final version of the paper.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "N9dZOJSzN2", "reviewer": "Reviewer_hRfp", "summary": "This paper introduces graph diffusion policy optimization (GDPO), a policy gradient method for optimizing graph diffusion probabilistic models with respect to non-differentiable reward signals. By establishing the connection between a T-step denoising process and a T-step Markov Decision Process (MDP), policy gradient methods can be applied to graph diffusion models. While a previous work (DDPO) report s competitive generation quality for image diffusion models trained with the classical REINFORCE algorithm, the authors empirically observe a convergence issue when applying REINFORCE to graph diffusion models. This issue is possibly due to the increasingly vast space constituted by discrete graph trajectories as the number of nodes in the graph increases. To address this issue, the authors propose GDPO, a modified policy optimization objective. Empirical studies demonstrate the effectiveness of the proposed modified objective.", "questions": "**Q1.** For the graph diffusion baselines considered, are they trained using classifier-free or classifier-based guidance?\n\n**Q2.** A key question in understanding the pros and cons of the different conditional generation approaches is sample efficiency. If ground truth reward functions are employed for GDPO training, then similarly we can label the samples generated by non-RL conditional graph diffusion models as extra training samples. The key question is then how the performance of the different models changes against the number of reward function evaluations.", "limitations": "The paper considers discrete time graph diffusion models. Whether the proposed approach is effective for continuous time graph diffusion models remains unexplored.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "**S1.** The proposed methodology is neat and well-motivated.\n\n**S2.** The paper is well-written and easy to follow.\n\n**S3.** The empirical studies demonstrate the effectiveness of the proposed approach.", "weaknesses": "**W1.** Some experiment settings are not completely clear from the description. See the questions below.\n\n**W2.** The proposed modification coincides with the idea of training a denoising network to predict the original uncorrupted graph rather than perform one-step denoising. Some discussions are expected.\n\n**W3.** Classifier-based and classifier-free guidance are two popular approaches for training conditional diffusion models and have been previously explored for graph diffusion models. Some discussions on the potential pros and cons of the RL approach against them are expected.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your insightful review and valuable suggestions. Below, we respond to the comments in ***Weaknesses (W)*** and ***Questions (Q)***.\n\n\n---\n\n***W1: Experimental settings***\n\nThanks for your suggestions. We will continue to polish our introduction to experimental settings, moving important details from Appendix to the Sec. 6 and providing additional experimental details for clarify.\n\n---\n\n***W2: Comparison with the $x\\_0$-prediction formulation***\n\nThank you for pointing this out. Indeed, our eager policy gradient in Eq. (10), compared to the policy gradient of REINFORCE in Eq. (8), resembles the idea of training a denoising network to predict the original uncorrupted graph rather than performing one-step denoising. However, we note that training a denoising network to predict the original data is fundamentally a matter of *parametrization* of one-step denoising. Specifically, the one-step denoising $p\\_\\\\theta(x\\_\\{t-1\\}|G\\_t)$ is parameterized as a weighted sum of $x\\_0$-predictions $p\\_\\\\theta(x\\_\\{0\\}|G\\_t)$, as described in Eq. (1). The eager policy gradient in Eq. (10) is motivated differently, focusing on *addressing the variance issue* as detailed in Sections 4.2 and 4.3. We will include this discussion in the final version.\n\n---\n\n***W3: Discussion on the potential pros and cons of the RL approach against classifier-based and classifier-free guidance for graph diffusion models***\n\n\nCompared to graph diffusion models using classifier-based and classifier-free guidance, RL approaches such as GDPO have at least two main advantages:\n- Compatibility with discrete reward signals and discrete graph representations (L24-30): As guidance for diffusion models is based on gradients, a differentiable surrogate (e.g., property predictors [29, 37]) is needed for non-differentiable reward signals (e.g., results from physical simulations). RL approaches naturally accommodate arbitrary reward functions without the need for intermediate approximations.\n- Better sample efficiency: For graph diffusion models with classifier-based or classifier-free guidance, labeled data are required at the beginning and are independently collected with the graph diffusion models. In contrast, RL approaches like GDPO collect labeled data during model training, thus allowing data collection from the current model distribution, which can be more beneficial. We also empirically observe a significant gap in sample efficiency. Please also see our response to ***Q2***.\n\nPotential cons of GDPO are discussed in the Limitations, see Appendix A.2. We will include the above discussion in the final version.\n\n---\n\n***Q1: Are the graph diffusion baselines trained using classifier-free or classifier-based guidance?***\n\nThe graph diffusion baselines in our experiments, i.e., MOOD and DiGress-guidance, are both classifier-based methods. For these methods, additional regressors for guidance (referred to as property predictors) are trained on graph samples with ground truth rewards. Specifically, noise is added to the input molecular graph so that the predictors can provide correct guidance at all timesteps during the denoising process.\n\nFor graph diffusion models using classifier-free guidance, we are currently not aware of comparable work and will be happy to include this in future work.\n\n\n---\n\n***Q2: Sample efficiency and performance comparison***\n\nIn our experiments on ZINC250k, we used 100,000 extra samples with ground truth rewards to train property predictors to provide gradient guidance for the MOOD and DiGress-guidance baselines. Note that for GDPO, the total query of reward is only 20,000, which is much smaller than that used for guidance. Nonetheless, a significant performance gap remains between these methods and GDPO. This demonstrates that GDPO has much better sample efficiency compared to graph diffusion models based on guidance. We will highlight these results in the revision.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "k6Kmntfjzg", "reviewer": "Reviewer_4R3n", "summary": "The paper studies the problem of learning graph diffusion generative models on arbitrary non-differentiable objectives using policy gradients. Authors argue that the recently proposed DDPO technique doesn't work well on the discrete, graph-related learning tasks and consider a modified objective and a corresponding gradient estimate which they refer to as Graph Diffusion Policy Optimization (GDPO). They show that GDPO performs significantly better on a number of reward functions and datasets.", "questions": "My main question is what is the nature of the bias the GDPO introduces? Is there a reasonable objective that is followed go eager gradients? Can we still interpret them as policy gradients in some kind of modified MDP?\n\nFigure 4: what is $D_G$ and $D_I$ concretely? Does it make sense to assess $L_2$ distances on discrete objects with categorical features?\n\nWhat happens if you apply GDPO to image diffusion? Does it still work or work better?", "limitations": "See above, I believe the paper needs a clearer discussion of the bias introduced by policy gradients. At the moment, it is not clear what is the connection of GDPO to the reverse diffusion MDP.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "## GDPO seems to be efficient \n\nDiscrete diffusion models are valuable class of machine learning models and being able to trained them on non-differentiable objectives might might unlock interesting applications, in particular, in optimizing molecular graphs as authors demonstrated.\n\n## The paper is well-written and easy to follow\n\nI can clearly answer most of my own questions about how GDPO works and it should be easy to reproduce main results.", "weaknesses": "## Underexplored potential of modern RL techniques\n\nWhile the proposed GDPO is valueable regardless, it is unclear to me that the biased objective / gradient estimate of eager gradients is necessary. Neither DDPO nor this paper explores even the simplest techniques such as actor-critic, PPO / TRPO or more sophisticated versions of importance sampling. DDPO showed good performance on image tasks without such advances and it could well be that it would still work well on graph tasks.\n\n## Lack of bias-variance analysis\n\nAuthors acknowledge that eager gradients is a biased version of the standard policy gradients but don't provider either theoretical or empirical analysis of the bias-variance tradeoff between the two methods. \n\nIn the appendix (line 660) authors a strange statement that importance sampling is used to reduce variance. It is not obvious to me all. Importance sampling can both reduce or increase variance depending on the proposal or the policy generating the trajectory. What it achieves is that it allows to train on experiences generated by policies other than the current policy being optimized.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your insightful review and valuable questions. Below, we respond to the comments in ***Weaknesses (W)*** and ***Questions (Q)***.\n\n***W1: Other RL techniques***\n\n\nThank you for your suggestions. Due to the multi-step generation process characteristics of DPMs, directly estimating model gradients from rewards is very challenging. While we acknowledge the theoretical limitations of GDPO compared to DDPO, our results suggest that GDPO is an effective method for discrete DPMs and fills a gap in related research. Exploring other RL techniques, such as actor-critic, PPO, TRPO, or more sophisticated versions of importance sampling, to further enhance GDPO should be an interesting extension, which we leave to future work.\n\n---\n\n***W2&Q1: Analysis on bias***\n\nThank you for highlighting these limitations. The main bias of GDPO arises from modifying the \"weight\" term in Eq. (9), which shifts the model's focus more towards the generated results rather than the intermediate process, thereby reducing potential noise. Due to the discrete nature of Graph DPMs, the $x\\_0$-prediction and $x\\_\\{t-1\\}$-prediction formulations cannot be related through denoising objectives as in continuous DPMs. This issue also complicates the connection between DDPO and GDPO. We have not yet identified a relevant solution and are still working on it.\n\nIn our empirical study, we do not observe significant performance variance and tradeoff for GDPO given the current scale of experiments. This may be due to the graph sizes we explored not being sufficiently large. In future implementations, we will incorporate support for sparse graphs to assess GDPO's performance on larger graph datasets and investigate the tradeoff more thoroughly.\n\nRegarding the statement about importance sampling, we apologize for any misunderstanding. In line 660, we did not claim that importance sampling techniques can reduce variance. Instead, we stated that they can be used to update DPMs multiple times with the same batch of trajectories, which aligns with your understanding, i.e., training on experiences generated by policies other than the current policy being optimized.\n\nWe will include the above discussion in the final version.\n\n---\n\n***Q2: Clarification on Figure 4***\n\nWe apologize for the lack of clarity. $D_I$ and $D_G$ represent the feature dimensions of images and graphs, respectively. For example, if an image has a size of $3 \\times 32 \\times 32$, then $D_I = 3072$. For a graph, $D_G$ is the product of the number of nodes and the feature dimension of the nodes. Since the L2 norm sums over the feature dimensions, we average over these dimensions to eliminate the influence of dimensionality. We choose the L2 norm to maintain consistency in the metric for comparisons, we acknowledge that graphs and images reside in different spaces and typically have different representations, we believe the comparison with L2 distance can provide valuable insights into the differences between graph and image DPMs.\n\n---\n\n***Q3: GDPO on images***\n\nThank you for your insightful question. Our research primarily focuses on graph DPMs, so we did not include experiments on Image DPMs. We attempted to adapt GDPO to Image DPMs but observed no significant advantages. We believe that for continuous DPMs, the policy gradient noise of DDPO is already sufficiently small, and there is no need to adjust the weight term. We will include this discussion in the final version.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
Dear Reviewers,

  We thank all reviewers for their constructive feedback, and we have responded to each reviewer individually. We have also uploaded a **Rebuttal PDF** that includes:

  $\\textrm{\\color{blue}Figure A}$: Some visualizations of graph data generated based on Reviewer gTVc's suggestions.

  $\\textrm{\\color{blue}Figure B}$: Results of the ablation study on the synthetic data.

Meta-review: The paper proposes a methodology to optimize graph diffusion probabilistic models for arbitrary reward signals. The methodology has several novel aspects including the Markov Decision Process formulation and the policy gradient considered. Despite the fact that the paper lacks strong theoretical support, the empirical results are quite strong.  The response of the authors to the different questions raised further clarified several aspects of the paper. Therefore, I recommend accepting the paper.
Decision: Accept (poster)