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:
1. 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.
2. Demonstrating state-of-the-art performance on various graph generation tasks, including general graph generation and molecular graph generation with complex objectives.
The 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).
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.
2. Clarity:
- Clear problem formulation: The authors provide a well-structured explanation of the challenges in optimizing graph DPMs and why existing methods fall short.
- Effective visualization: Figure 1 offers a clear overview of the GDPO method, aiding understanding of the approach.
- 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.
3. Significance:
- 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.
- 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.
- 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.
4. Technical Quality:
- Thorough experimentation: The authors provide extensive experiments on both general graph generation and molecular graph generation tasks, lending credibility to their claims.
- 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.
- 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.
- 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.
- 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.
- 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.
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...)?
2. 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:
---
1. Generate a base tree structure with parameters:
- Tree depth
- Minimum fan-out factor
- Maximum fan-out factor
- Binned beta variation across the fan-out for a given node
2. Plant a tree of cliques as an expansion of nodes at a chosen height in the base tree. This planted structure should have parameters:
- Number of rings of cliques
- Ring size and clique count
3. 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:
- Number of rewiring steps
- starting layer of the subgraph to be noised (starting at a given layer of the tree)
The noisy rewiring process would involve:
a) Randomly selecting an edge
b) Checking whether to remove it based on the probability of an edge existing in the target Erdős-Rényi graph
c) Selecting a random node pair to potentially add an edge
d) Repeating this process for the specified number of steps
I suggest ablating over:
1. The number of rewiring steps
2. The size of the subgraph to be noised
3. The overall graph size
4. The height at which the tree of cliques is planted
5. (optional) clique size and ring size
My 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.
Questions I'd like answered through this ablation study:
1. How does GDPO's performance change as the noise level (number of rewiring steps) increases?
2. What is the impact of graph size on GDPO's ability to maintain the planted tree of cliques and the overall tree structure?
3. Is there a critical point in the noise level or graph size where GDPO's performance significantly degrades?
4. 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)
5. How does GDPO compare to baseline methods on these more challenging graph structures?
6. 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