Plug-And-Play Controllable Graph Generation With Diffusion Models

We are delighted by the reviewer’s positive recommendation of our work and we hope that any remaining concerns get addressed in the following discussion to further increase their scores. We also thank them for pointing out the typo that we have fixed in the revised version.

Though when the constraints cover all the graphs in the test set, the generated distribution is largely unaffected, in scenarios where the constraints do take effect, the generated distribution obviously deviates from the original distribution. And the deviation is model-sensitive.

We would like to note that our performance difference in different base models is not a weakness but rather a strength of our method as we show plug-and-play improvement over these pre-trained models without being specific to any of them. Thus, as more advanced diffusion models are designed in the future, our method will automatically provide further improvement over them for constrained generation.

For example, in Table 2, with edge count as the constraint, the performance of GDSS downgrades by two folds on Clus. while EDP-GNN is largely unaffected. Also, on the dataset of Enzymes and Grid, both GDSS and EDP-GNN suffer a lot from the constraints.

Please refer to our general comment on higher MMDs (link).

Furthermore, Figure 12 shows a lot of unrealistic molecular graphs (e.g. very large rings, disconnected graphs, very long bridging bonds) with the constraints on atom count.

Unrealistic substructures such as large-cycle rings can arise as the constraint does not control for the size of the cycles and only cares about the counts of atoms. Furthermore, the probability distribution approximated by GDSS is not perfect and the original GDSS also samples such unrealistic graphs. However, the flexibility of our method allows us to control such unrealistic structures if needed by formalizing them as constraints. For example, large cycles can be controlled (just like we control the number of triangles). At this point, since finding the maximum cycle length in a graph is an NP-complete problem, controlling the maximum cycle length becomes a non-scalable problem for larger graphs (since we can’t even calculate it). Future works can explore other efficient methods to incorporate this constraint for larger graphs with certain approximations. Similarly, one can control for connectivity and bridging in the graph since both are formal graph-theoretic functions but we leave them for future works to consider.

The proposed projection paradigm main only applied to constraints with simple calculation process so that the optimization problem has a closed-form solution. When the constraints become complicated (e.g. involves non-linearity), it might be arduous or impossible to find such closed-form solution.

We would like to note that this is the first work on constrained graph generation and to the best of our knowledge, PRODIGY is the only method that can support plug-and-play constrained generation of any graph-level constraint, once it’s formally defined. We consider a wide range of constraints and find that they have efficient projection operators by following the fixed template of Section 4.1. While we make certain assumptions about the form of the constraint, this does not restrict the applicability of this method to any new constraint. Contrary to the reviewer’s comment, we do not require a closed-form solution to exist for the optimization problem. In fact, as noted in Table 1 and Appendix A, the exact value of $\mu$ is never known in closed form and found using inexact linear and bisection search algorithms. Furthermore, we also consider approximations instead of exact projections for efficiency reasons and find superior results (see Triangle count constraint, Appendix A.2). All in all, while the proposed method requires solving an optimization problem, it does not require exact solutions and leave enough room for approximate and intricate solutions to be devised for specific constraints following the proof template (using Lagrangian operators) provided in Section 4.1 and Appendix A. We also discuss extensions to general non-linear constraints (assuming ReLU non-linearity) in Appendix B.3 but find that the optimization problem can get harder to solve and future works can focus on devising more efficient solutions.

Thank you once again for your review! We have tried to carefully address your concerns in our responses and it would be very valuable to us if you could provide your feedback. If any issues still remain that need to be resolved, we would love to address them during the discussion period.

“influences the sampling process in an obscure and uninterpretable manner”: can you elaborate?

An interpretable control on the generation should imply that the generated samples satisfy the given control. But conditional generation techniques instead consider the specified given control as a random variable and approximate the probability distribution $p(x | c(x) = c_0)$ where one can have $p(x=x’ | c(x) = c_0) > 0$ even though $c(x’) \neq c_0$. This is unexpected and each step in the sampling process thus becomes obscure and uninterpretable. Let us know if this doesn’t clarify the concern and we would be happy to elaborate.

Condition-based Control definition: Can you write what y and c are? Or link to the part where you formalize it.

We note that $c(G, y)$ is a boolean function which is $1$ when $y_c(G) = y$ and $0$ otherwise. Here, $y_c(G)$ calculates some property of the graph $G$ and $y$ is a value that this property must take. As such, this is a standard definition in the existing literature and we discuss it in point 1 of controlled generation on page 3. We have also revised the definition in the updated draft.

Constraint-based Control definition: can you clarify better the difference with soft control. Or refer to where you are defining it.

As we discuss in the Controlled Generation part of Section 2, the main difference is that in a soft control, we need to sample a graph $G$ given the control $c(G)$ as a dependent random variable, while for a hard control or constraint, we require the sampled graph $G$ to satisfy the control $c(G)$. For the soft control, one estimates a conditional probability distribution $p(G | c(G))$ and samples the graph $G$ from this. But this does not imply that the sampled graph would hold $c(G)$. This is because of the cyclic nature of the corresponding Bayesian network since a random variable $c(G)$ affects the distribution of $G$ (i.e., $p(G | c(G))$) and a given $G$ also affects the value of $c(G)$ (i.e., $p(c(G) | G)$). It thus forms an infinite Markov chain to necessitate that the sampled $G$ would imply $c(G)$. Constraint-based control specification, on the other hand, necessitates the control to be satisfied (hence, hard). We have clarified this better in the revised draft.

Does the plug-and-play approach require training of 2 models? Could you point to where you discuss the advantage to training the soft-constrained methods?

We think the reviewer has misunderstood our approach regarding the necessity of training. We wish to clarify that we do not require training of two models. In fact, we do not train any new model but rather solve an optimization problem at every sampling step. The key contribution is to show that such an optimization problem can be solved efficiently, thus, removing the requirement of training a new predictor model or a new generative model, while allowing for the precise controls to be satisfied exactly. As we discuss in the Controlled Generation part of Section 2, the advantage over existing soft-constrained methods is two-fold – (1) Our method can be plugged onto any pre-trained diffusion model’s sampling without training any new model, and (2) We can satisfy precisely defined hard constraints on the generated samples that cannot be done using guidance-based methods.

Figure 2: Sampling process of PRODIGY (red) versus existing methods (Jo et al., 2022). Why are you comparing them, if in the experiments you are not?

We are indeed comparing these two in the experiments. In tables 2,3,5,6, we compare PRODIGY (red) against GDSS (Jo et al., 2022).

We thank the reviewer for providing constructive feedback on our work. Below, we provide detailed responses to their concerns and hope that the following discussion can encourage them to increase their score towards acceptance.

It seems that the constrained generation settings is a completely different task from conditional generation (Hoogeboom 2022, Xu 2020) so, I think that the “constrained” keyword is more suitable?

We are not sure why the reviewer thinks we are focusing on conditional generation as we have never used that term anywhere to describe our approach. We would appreciate it if the reviewer could point out what has confused them. We do call our approach controllable generation as a constraint is a form of control.

Can your approach be applied also into conditional generation, e.g. Hoogeboom 2022 etc?

Yes, as shown in Section 5.3 (dipole moment was also considered in Hoogeboom et al., 2022) and Appendix D.1, the problem of conditional generation can be solved using our approach. One can argue that the problem of conditional generation can be reduced to the more general constrained generation (the focus of this work). The objective of conditional generation can be seen as minimizing the difference (MAE or MSE) in the property of the generated samples and that of the given conditioning samples. More formally, this implies constraining the conditioned property of the generated samples within a certain bound ($\epsilon$) of the median/mean of the given conditioning samples. Theoretically, this will minimize the MAE/MSE of the property between the generated samples and the conditioning samples.

Since the tasks of Hoogeboom 2022, Xu 2020 are different, the comparisons with baselines are not really fair from what I read in the paper. You should compare the proposed “constrained” approach, with other constrained methods, maybe an adaptation of Bar-tal 2023 that you refer to? I am not convinced that measuring VAL_c on GDSS is fair against your model? This is why GDSS and EDP-GNN have the VAL_c metric approximately at zero, see Table 3

“Such controls are not differentiable and no method exists that can control the generation for these properties without relying on curating additional labeled datasets or retaining the entire generative mode”: from what I understand conditional generation is a different setup, so does not seem fair to compare what data is required in constrained generation ?

We argue that comparison against base and conditional-generation models is fair in the absence of any constrained graph generation baseline in the literature.

Comparison with the base models: To the best of our knowledge, there do not exist any baselines for constrained graph generation, that we can compare against. Thus, we decided to highlight the plug-and-play improvement over the base model. We test if our sampling strategy can improve the satisfaction of constraints that are not already satisfied by the original sampling methods. Our comparison with the base models in terms of $\text{Val}_C$ is to show that our method can improve the constraint validity significantly without significantly affecting the distributional metrics. Furthermore, we cannot have Bar-Tal et al. 2023 as a baseline since the proposed method in their work focuses on image generation and is limited to specific image-based constraints (panorama, aspect ratio, and spatial guiding) and any extensions of their method to graph-level constraints are not directly meaningful and hence not the focus of this work.

Comparison with conditional-generation models: Our comparisons against the conditional-generation approaches are geared towards demonstrating that our approach is general enough that it can handle condition-based control as well. These experiments are not meant to assess the basic efficacy of our approach. We formulate the objective of their paper as a constraint and apply our method to achieve similar performance. In particular, we consider a constraint such that the value of the conditioned property is close (within $\epsilon$) to the mean/median of the given data. This would imply that the generated samples have property values closer to the conditioned value. In Section 5.3 and Appendix D.1, we thus compare the conditional generation methods with the constrained generation approach of PRODIGY. We use simple linear models to estimate these properties and find that even with these models, we can achieve lower MAE of the predicted properties between the generated and conditioning data samples. This implies that even with highly biased predictors, we can lower the error rate by effectively satisfying the constraint satisfaction and thus, keeping the property within $\epsilon$ bounds of the predicted median.

Thank you once again for your review! We have tried to carefully address your concerns in our responses and it would be very valuable to us if you could provide your feedback. If any issues still remain that need to be resolved, we would love to address them during the discussion period.

We appreciate the reviewer’s recognition of the strengths of our work and we hope the following discussion will be able to address their remaining concerns.

The main concern is that using the proposed approach seems to have inferior generation quality compared to the original diffusion model. For example, in Table 2, GDSS+PRODIGY results in a significantly higher clustering coefficient MMD for the Community-small dataset and Enzymes dataset. This is problematic as the generated graphs should primarily follow the data distribution, not only satisfying the constraint.

Please refer to our general comment on higher MMDs (link).

For some constraints, e.g., Degree and Molecular weight, the proposed method does not seem to achieve high validity (lower than 70%) even though the denoised samples are projected to the constrained set. In particular, GDSS+PRODIGY shows similar validity to GDSS for molecular weight constraint. Through analysis clarifying the reason for failing to satisfy the constraint is required.

What is the reason for GDSS+PRODIGY showing similar validity to GDSS for molecular weight constraint?

Lower satisfaction of given constraints in the experiments cited by the reviewer is primarily because we have to round our constraint-satisfying continuous solution to a corresponding discrete solution. As mentioned in Section 4, we consider a continuous relaxation of the constrained set, and the projection step projects the adjacency and atom-type matrices to the closest continuous solution that satisfies the constraint. At this point, we can guarantee the constraint is fully satisfied. However, since the graph structure is discrete, we round this continuous solution at the end to the closest discrete value and find the constraint validity on the rounded solution. This means that the constraint may not always be satisfied by the discrete solution. While specific rounding strategies to satisfy the constraints can be devised, this is a challenging task and must be carefully designed based on the application. For simplicity, we stick to the existing threshold-based rounding strategy as in the literature (Niu et al., 2020; Jo et al., 2022). In the experiments, we find that this is often very effective while being considerably efficient.

Reflecting on the reviewer’s suggestion, we discuss and analyze possible reasons why low satisfaction may be achieved in specific cases including the ones cited by the reviewer:

1. Molecular weight constraint: This tends to be the case because the closest point found by the projection operator tends to make the $X$ matrix uniform across different atom types. When a low satisfaction is achieved on this constraint, we see in the failure cases that it tends to converge to $X_{ij} \rightarrow W / (n \sum_j m_j)$. This is not ideal during rounding as even though $\sum_{i, j} m_j X_{ij} \le W$, we can have $\sum_{i} m_{\arg\max_j X_{ij}} > W$ since $X_{ij} \approx X_{ik}$ ($j \ne k$). This can be alleviated with additional constraints on $X$ (such as $|X_{ij} - X_{ik}| > \epsilon$ for some $\epsilon$) but we leave such engineering tweaks for specific constraints for future works to examine.
2. Ego-small (Edge Count and Degree): We believe this comes due to the limited number of discrete graphs that are possible around the constraint-feasible set. Ego-small consists of typically sparse graphs with few (~5) nodes. Our constraints of at most $3$ edges and at most $5$ maximum degree allow for very few graphs that tend to be harder to reach through simple rounding techniques.
3. EDP-GNN, Community-small (Edge Count and Degree): We believe the low satisfaction, when it happens in this case, comes because we consider an aggressive $\gamma_t = 1$ projection for EDP-GNN. This may not be ideal as it can drift the sampling procedure too much leading into a specific continuous region that may not be close to the learned distributions of (discrete) graphs. EDP-GNN only consists of Langevin sampling and thus, one cannot schedule a $\gamma(t)$ as a function of $t$ as in GDSS. But we believe a scalar value of $\gamma_t < 1$ might give better results and we will update the results in the paper to include this (will share here as soon as they are available).

Are the MMD results of Table 2 measured between the generated graphs and the constraint-filtered test set? I presume the MMD is not measured between generated graphs and the original test set as the MMD results are different among the constraints for the same dataset.

Yes, as mentioned in Section 5.2, MMD results in Table 2 are found using the generated and constraint-filtered test graphs. Since in this experiment, we are only interested in generating graphs that satisfy specific constraints, unsatisfiable graphs do not form meaningful ground-truth samples for comparison. Hence, we filtered these out to compute the MMD.

I do not understand the t-test results in the general comments. Which MMD (Deg., Clus., Orb.) was the target for the t-test? I find the Clus. results on Enzymes and Deg. results on Community-small to be significantly different on GDSS.

In the general comment, we consider the hypothesis that given a constraint, the MMD of GDSS/EDP-GNN for any property is different from the MMD of GDSS+PRODIGY/EDP-GNN+PRODIGY for that property and dataset. Thus, we combine different properties in the same statistical analysis because each property is as important as the other and find no statistically significant result for the same.

To specifically address what the reviewer has suggested, one must instead test the hypothesis that x-MMD(GDSS/EDP-GNN | dataset) is different than x-MMD(GDSS/EDP-GNN+PRODIGY | dataset), where x is Deg., Clus., Orb.. We give the results for these tests below. We highlight the rows which are found to be statistically different ($p <0.05$) and note that a positive t-statistic mean x-MMD(GDSS | dataset) > x-MMD(GDSS+PRODIGY | dataset) while a negative t-statistic mean x-MMD(GDSS/EDP-GNN | dataset) < x-MMD(GDSS/EDP-GNN+PRODIGY | dataset). This shows that PRODIGY statistically worsens the MMD in only the deg. and orb. MMDs for Grid (that we already discussed above). This is given the fact that PRODIGY significantly lowered the MMDs in 7 cases and improved the constraint validity in all cases. This establishes that the strengths of PRODIGY in satisfying constraints overshadow increasing the MMD in one dataset (Grid).

I also have some concerns regarding the practicality of the proposed method. From the projection operations summarized in the paper, the proposed method seems more suitable for controllable generation for atomic features X or structural information A related properties, such as valency, atom count, and molecular weight. However, in real-world applications, such as constrained molecular generation, we mostly expect the generated molecules to exhibit certain graph-level properties.

We would like to clarify that our method is suitable for and indeed applies to graph-level properties. Any (global) property $h$ of an attributed 2-D graph $G = (X, A)$ can be written as a function of its parts $h(G) = h(X, A)$. We consider general constraints of the form $(h_1(X, A) \le 0) \land (h_2(X, A) \le 0) \land \cdots (h_k(X, A) \le 0)$. For instance, the number of triangles and edges are all global properties of the graph, while total molecular weight and number of certain atoms are global properties of a 2D molecule. We also consider the dipole moment, which is a global property of the 3D molecular structure. Finally, we also show extensions to general linear (Appendix B.2, D.1) and non-linear properties (with ReLU non-linear activations in Appendix B.3) of a graph using parameterized models. In this work, we show, for the first time, that one can control generation from pre-trained models under precisely defined constraints efficiently on a wide array of graph-level properties. Future works can extend our approach to satisfy specific constraints more efficiently.

One can further argue that the exact form of complex molecular properties as a function of its constituents may not be known when these are only experimentally observed (for example, boiling points, chemical reactivity, etc.). However, this is not a limitation of our method but rather a dependence on chemistry research that aims to find such closed-form functions of all molecular properties in terms of their structure. One way that is increasingly adopted by computational chemists is to learn neural networks from data for these properties (Hoogeboom et al., 2022). This gives us an exact predictive function of these properties and one can then constrain the predicted value from this parameterized model. This would imply constraining the value of the underlying property that we also validate through experiments (Appendix D.1 and Section 5.3 with simple parameterized linear models).

We hope this helps clarify the concern but if the reviewer still believes some graph-level properties would not be allowed in our proposed framework, then it would be great if they could give specific examples of the same.

Why does the method in the paper only demonstrate its effectiveness on continuous diffusion methods and not on recently proposed discrete diffusion methods, such as DiGress+PRODIGY?

The focus of our work on supporting plug-and-play sampling-based constrained graph generation for continuous-time diffusion models is a design choice borne out of both the recently reported generation results of state-of-the-art methods in this field and a carefully conducted feasibility analysis on our end.

First, it is not clear that discrete models are necessarily the best choice and provide state-of-the-art performance on unconditional graph generation. As a case in point, in Section 2 (start of page 3), we note that more recent advancements in continuous-time models (DruM, Jo et al., 2023) have been shown to outperform discrete models such as DiGress (however, note that the codes and models for DruM are not publicly available yet but we are in communication with their authors and our method can directly apply on their trained models without any modifications). As for the DiGress model cited by the reviewer, we recognize that their ability to do conditional generation (separate focus from ours but their definition of conditional generation is generalizable to our constraint-based formulation) is useful and provides a meaningful comparison point for us. Considering this, in Appendix D.1, we compared the guidance-based approach of DiGress against our constrained generation result with GDSS to generate molecules with given HOMO and dipole moment values. We found PRODIGY to provide comparable performance even with weaker underlying continuous time models. This is because we can generate molecules close to the median property value which reduces the error even with a highly biased model.

In terms of feasibility, the discrete models pose significant efficiency challenges for constrained generation. These challenges primarily stem from the combinatorial explosion of the space of constraint-feasible graphs. The constraint set for discrete graphs is formed by a set of discrete points with no definite structure, unlike the continuity and convexity in the continuous case. Due to these reasons, the solution to the optimization problem becomes an instance of integer programming, and thus, results in an NP-hard problem. The projection step would then involve iterating over all the graphs in the constrained set to find the closest one. This explodes as the size of the constrained set increases, which can be exponential even for a simple edge-count constraint since $|E| \le B$ has $\binom{n^2}{B}$ different graphs that satisfy the constraint (where n is the number of nodes). Thus, constraint satisfaction for discrete diffusion models can be NP-hard and we leave it for future works to explore innovative workaround solutions.

Finally, we would like to note that this is the first work on constrained graph generation, and to the best of our knowledge, PRODIGY is the only method that can support plug-and-play constrained generation of any graph-level constraint, once it’s formally defined. We believe that it is an unfair expectation for a single work to solve a highly novel and challenging problem in all available settings. In light of this, we would highly appreciate it if you would be kind to reassess our work and score it based on the above clarifications. We are happy to engage in further discussions and would love to provide any clarifications that can help alleviate any of your outstanding concerns.

Jo, Jaehyeong, Dongki Kim, and Sung Ju Hwang. "Graph Generation with Destination-Driven Diffusion Mixture." arXiv preprint arXiv:2302.03596 (2023).

We thank the reviewer for recognizing the strengths of our work and providing constructive feedback to improve it further. Below, we respond to specific concerns raised by the reviewer:

My biggest concern is whether such an operation, which pulls the embedding towards the designated constrained space through projection during the reverse process, is effective in more practical scenarios. The paper proposes some compromises to determine whether to pull towards the original data distribution or the constrained space during the reverse process. However, from the experimental results, I find that the performance of this approach is not entirely satisfactory. For example, in the Community-small and Ego-small datasets, the MMD metric worsens in many cases after applying the PRODIGY method. Additionally, in the QM9 molecular generation experiment, adding PRODIGY poses a significant risk of decreasing validity and novelty.

Please refer to our general comment on higher MMDs (link) in some dataset/model settings on general graphs. In addition, the reviewer raised concerns regarding a decrease in validity in QM9, which happens for EDP-GNN under molecular weight and atom count constraints. We would like to note that (1) This is attributed to the underlying model of EDP-GNN as it only denoises the adjacency matrix while these constraints are dependent on only the node attribute matrix (thus, the reverse sampling of $A$ is not affected by the projection of $X$ and can decrease the validity), and (2) Our framework gives the ability to further increase the validity directly by using the valency constraint on top of any other constraint. Further, decreased novelty under atom count constraint in QM9 primarily arises from the fact that we study a highly constrained setting, where we need to generate molecules with only C and O atoms as compared to the unconstrained setting where we can generate over C, N, O, and F. This naturally limits the total number of possible molecules and thus, limits the novel molecules we can generate over the C and O molecules that already exist in the dataset. Thanks to the reviewer’s comments, we have realized that comparing raw novelty metrics is unfair to our method since we are exploring a limited set of molecules compared to GDSS. We believe a better metric to study would be the proportion of molecules that are both novel and constraint-valid. For this example, we can see it would be roughly $0.33 \times 81.04 = 26.74\%$ for GDSS while it would be $1.00 \times 67.67 = 67.67\%$ for GDSS+PRODIGY. We will add the constraint-valid and novelty (VN%) metric in the revised version.

Another concern I have pertains to the potential impact of such operations on the convergence of the Langevin Dynamics process. It would be prudent to provide a proof for the convergence of the Projected Inexact Langevin Dynamic/Algorithm follows some ideas from PSLA [1].

We appreciate this suggestion but note that such a proof of convergence is extremely non-trivial and out of the scope of this work.

Having said that, as we note in Section 2 (Projected Sampling), modern diffusion models (Song et al., 2021; Jo et al., 2022) differ from theoretical Langevin dynamics considered in Lamperski, 2021, and others. This implies that the proofs in PSLA cannot be directly transferred to our current work due to various reasons –

1. We do not know of a corresponding convergence proof even for the unconditional generation of diffusion-based models. Since our method is based on these models, any proof of convergence of the overall sampling becomes highly non-trivial. In the theoretical works, the (unnormalized) probability distribution is known exactly and assumed to have a certain form (uniformly sub-Gaussian), while such assumptions do not hold for diffusion models where the probability density function (or equivalently, the score function) is approximated through arbitrary (graph) data. For real-world graph data, such sub-Gaussian assumptions are not well-motivated.
2. We consider a non-zero drift coefficient (which is assumed to be $0$ in PSLA) for more expressivity, which complicates the theoretical analysis further.
3. Our proposed method is a generalization of PSLA in the sense that we do not project the noisy sample completely but instead move the sample only slightly in the direction of the projection (see the last paragraph of Section 4). In particular, we consider $G_{t-1} = (1 - \gamma_t)\tilde{G_{t-1}} + \gamma_t \prod_{C} \tilde{G_{t-1}}$, where $\tilde{G_{t-1}}$ is obtained from $G_t$ following the reverse process. In the experiments, we find that $\gamma_t = (t/T)^p$ for some $p$ gives the best results, which is in contrast with PSLA which is an instantiation of our method with $\gamma_t = 1$.

Further, reflecting upon the reviewer’s comments, we analyzed the drift caused by the PRODIGY method on the original sampling by bounding $\lVert G_T - \tilde{G_T} \rVert$ assuming the same initial random graph $G_0$ and Reverse$(G_t) \sim$ Reverse$(\tilde{G_t})$. In particular, we show that $\lVert G_T - \tilde{G_T} \rVert\le 2 \sum_{t} \gamma_t \lVert \prod_{C}(G_t) - \tilde{G_t} \rVert$. Since the term inside the summation is what we optimize in every iteration under a given constraint, our method optimizes the upper bound to be minimal. Furthermore, $\gamma_t$ gives the flexibility to be close to the original graphs if needed. To prove the statement, we first note that $\lVert G_T - \tilde{G_T} \rVert = \lVert (G_T - G_{T-1}) + (G_{T-1} - G_{T-2}) + \cdots + (G_1 - G_0) - (\tilde{G_T} - \tilde{G_{T-1}}) - (\tilde{G_{T-1}} - \tilde{G_{T-2}}) - \cdots - (\tilde{G_1} - G_0) \rVert$ $\le \lVert (G_T - G_{T-1}) - (\tilde{G_T} - \tilde{G_{T-1}}) \rVert + \cdots + \lVert (G_1 - G_0) - (\tilde{G_1} - G_0) \rVert$. By definition, $G_t - \tilde{G_T} = \gamma_t (\prod_{C}(G_t) - \tilde{G_t})$. Thus, we get $\lVert G_T - \tilde{G_T} \rVert\le 2 \sum_{t} \gamma_t \lVert \prod_{C}(G_t) - \tilde{G_t} \rVert$. Finally, we note that a lack of proof does not undermine the effectiveness of our work since we show empirically that PRODIGY can (1) converge to the underlying model’s learned distribution when the test set is a subset of the constraint feasible set (see Section 5.4), and (2) generate graphs that satisfy hard constraints (see Section 5.2).

Thank you once again for your review! We have tried to carefully address your concerns in our responses and it would be very valuable to us if you could provide your feedback. If any issues still remain that need to be resolved, we would love to address them during the discussion period.

Thank you for your response. Could you please revise your current version and mark the revisions as blue?