Graph Diffusion Policy Optimization

Thank you for your insightful review and valuable questions. Below, we respond to the comments in Weaknesses (W) and Questions (Q).

W1: Other RL techniques

Thank 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.

---

W2&Q1: Analysis on bias

Thank 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.

In 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.

Regarding 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.

We will include the above discussion in the final version.

---

Q2: Clarification on Figure 4

We 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.

---

Q3: GDPO on images

Thank 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.

Thank you for your insightful review and valuable suggestions. Below, we respond to the comments in Weaknesses (W) and Questions (Q).

---

W1: Experimental settings

Thanks 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.

---

W2: Comparison with the $x\_0$-prediction formulation

Thank 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.

---

W3: Discussion on the potential pros and cons of the RL approach against classifier-based and classifier-free guidance for graph diffusion models

Compared to graph diffusion models using classifier-based and classifier-free guidance, RL approaches such as GDPO have at least two main advantages:

• 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.
• 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.

Potential cons of GDPO are discussed in the Limitations, see Appendix A.2. We will include the above discussion in the final version.

---

Q1: Are the graph diffusion baselines trained using classifier-free or classifier-based guidance?

The 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.

For 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.

---

Q2: Sample efficiency and performance comparison

In 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.

Thank you for your insightful comments and valuable suggestions. Below, we respond to the concerns raised in Weaknesses (W) and Questions (Q).

---

W1: Theoretical Analysis, Scalability, and Failure Cases

Thank 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.

---

W2: Comparison with RL-based graph generation methods

Thank 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.

---

Q1: Discussion on reward selection

In 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.

---

Q2: Ablation study on noisy tree with planted motifs

Thank 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.

In $\\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.

After 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.

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.

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.

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.

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.

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.

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.

Thank you very much for your suggestions. We will include the above discussions in the final version of the paper.