We thank the reviewer for acknowledging the importance of the topic under consideration and for the insightful comments. We address the reviewer's concerns in the following points:

W1: We agree with the reviewer and do also envision the extension to joint node-edge constraints, e.g. valency constraints in molecular generation, as an exciting future direction. We extend on this topic on item 3 of the global rebuttal.

W2: We remark that, despite the lack of a tractable evidence lower bound for the likelihood, the proposed projector pushes ConStruct to remarkable empirical performance, outperforming unconstrained models.

W3: Even though ConStruct allows for constrained generation in a similar manner to autoregressive models, it is actually a diffusion-based framework. We thoroughly analyse its complexity and efficiency in section 3.5 and appendix C. Based on this, we provide a more explicit comparison in terms of complexity to the underlying discrete diffusion methods in item 1 of the global rebuttal. From such comparison, we are able to conclude that ConStruct is a scalable method.

W4: For EDGE, we do compare for planar and tree datasets (Table 1). We did not test it in the digital pathology setting because we only picked "the methods that, besides DiGress, attain non-zero V.U.N. for the planar dataset in Table 1, which we consider as a proxy for performance in the digital pathology datasets due to the structural similarities between the datasets" (ll. 310-312, pg. 9). In fact, the digital pathology dataset is even more challenging since it contains attributed planar graphs.

For GraphARM, unfortunately the authors do not report results on any of the used datasets, neither provide their code (to the best of our knowledge), which makes meaningful comparisons difficult.

We appreciate the reviewer's suggestion to update citations and have addressed this.

Q1: $\Delta^k$ denotes the $k$-simplex:

We added this clarification to the notation paragraph and we corrected its usage in l.171 accordingly (to $\Delta^{b-1}$).

Q2: If all the newly proposed edges (inserted from $G^t$ to $\hat{G}^{t-1}$) by the diffusion model lead to constraint violation, then the graph remains the same as in the previous step, $G^{t-1}=G^t$ (so the intersection of $\mathcal{C}$ and $\mathcal{G}^{t-1}$ is trivially non-empty). We do not early exit the reverse process in such case because the denoising network takes as input both $G^t$ and the timestep $t$. Therefore, even if for a given timestep $t$ all the proposed edges are rejected, the model predicted probabilities can change in the next reverse step, since the model has now a different input (still the same graph $G^{t-1}$($=G^t$) but the timestep is $t-1$). Note that the case where the diffusion model does not propose any new edge (as we dot not lower nor upper bound the number of edge insertions at each step) falls within that case as well.

Additionally, we remark that the diffusion model outputs a probability distribution over graphs, from which we sample the proposed graph. As a result, the proposed edges at each reverse step are not deterministic, even with the same inputs (thus outputs) to the model.

Q3: In training, as the edge-absorbing noise model only removes edges, the training noisy graphs necessarily remain within the domain of graphs that satisfy the desired edge-deletion invariant property. Therefore, the denoising network is only trained for graphs that satisfy the desired property.

In sampling, even though the posterior term of the edge absorbing noise model ensures the reverse as an edge insertion process (this is a direct implication from using eq. 6 in eq. 5), it does not guarantee that the successive graphs remain within the domain of graphs which satisfy the desired property. In fact, since the denoising neural network is not a perfect edge predictor and the edges are sampled independently, sometimes we obtain intermediate graphs that are outside of such domain, inducing out-of-distribution prediction to the denoising neural network for the next step. To counter this, the projector is used to push back the graph generative trajectory to the domain where the model was actually trained. Note that the projector is only used to correct the trajectory when it gets out of the desired domain and does not interfere whenever the trajectory is within domain. Therefore, the projector is actually reducing the discrepancy between training and sampling processes and promoting in-distribution prediction for the denoising neural network, resulting in improved performance both in terms of sample quality and validity.

These results are aligned with the intuition provided in other constrained diffusion models for continuous state-spaces that also empirically validated the benefit of promoting the match of distributions between training and sampling [1,2,3].

[1] - Lou, Aaron, and Stefano Ermon. "Reflected diffusion models." ICML, 2023.

[2] - Fishman, Nic, et al. "Metropolis Sampling for Constrained Diffusion Models." NeurIPS, 2024.

[3] - Liu, Guan-Horng, et al. "Mirror diffusion models for constrained and watermarked generation." NeurIPS, 2024.

We appreciate the detailed comments and pertinent questions. We address the raised concerns below:

W1: We acknowledge that our model is tailored for the task of constrained generation, which requires the explicit and unambiguous definition of the constraint, as reflected in the paper's title. Despite not universal, we believe our framework is quite general. It proves effective for various properties in structurally constrained synthetic graphs and digital pathology, outperforming unconstrained models, and can also be used to guide unconstrained models (e.g., generating acyclic molecules, App. G.2). Additionally, we (non-exhaustively) enumerate several real-world applications beyond digital pathology where essential constraints are well-defined and edge-deletion invariant (l. 144-147, pg 4).

W2: Both works indeed address similar tasks. However, they differ fundamentally: PRODIGY offers efficient guidance of pre-trained models by relaxing adjacency matrices to continuous spaces (implicitly imposing an order between states) and finding low overhead projections there. Yet, it does not guarantee constraint satisfaction and faces a trade-off between performance and constraint satisfaction due to mismatched train/sample distributions. In contrast, ConStruct, while also suitable for guided generation (App. G.2), is designed for constrained generation. It treats adjacency matrices as discrete, where there are no efficient solutions for projections into arbitrary subclasses of graphs (e.g. maximum planar subgraph is NP-hard). This results from the lack of inherent ordering between states and the combinatorial nature of the domains of valid graphs. Nonetheless, ConStruct ensures constraint satisfaction with matched distributions, thereby improving performance over unconstrained models, and maintains efficiency through incremental algorithms and blocking edge hash tables. Thus, ConStruct is not an approximation of continuous-space projections and we believe it to be a full contribution in itself.

W3: Our mention to the potentially compromised smoothness of the diffusion process refers to the thresholding step required by PRODIGY to convert the continuous adjacency matrix back to a discrete one, either at the end of the diffusion process (continuous diff.) or at each reverse step (discrete diff., a variant not available at submission). This step can disrupt smoothness as it is sensitive to the implicit ordering between states, may not yield the most appropriate discrete matrix for the original continuous relaxation, and does not guarantee constraint satisfaction. Despite notably reducing the distortion of the diffusion process, PRODIGY's fractional constraint enforcement does not address this drawback.

In contrast, ConStruct operates directly on discrete state-spaces and avoids this limitation. ConStruct adjusts a graph from the previous reverse step by inserting the property preserving newly proposed edges, which are typically very few, promoting the process smoothness. Although edges are chosen in random order in the default implementation, Section H.3 empirically shows that this approach is not inferior to methods that order edge insertion based on predicted likelihoods by the diffusion model.

W4: Theorem 1 provides useful guarantees about the proposed projector and helps understand the problem complexity. We agree that analyzing how often the projector retrieves the optimal graph is valuable; indeed, Theorem 2 shows that for the acyclicity constraint, the proposed projector always retrieves the optimal graph. Table 3 provides counter-examples demonstrating that this is not true for planarity, maximum degree, and lobster components. Since ConStruct generates new edges based on the diffusion model and not randomly, characterizing this subset to obtain more refined results (e.g., probabilistic bounds) for arbitrary properties is far from trivial. Finally, we believe that ConStruct is indeed well-suited for application as it shows significant performance improvements, high efficiency, and guaranteed property satisfaction.

W5: We did not initially consider SPECTRE as closely related because it is GAN-based and it addresses unconstrained generation by producing eigenvectors and eigenvalues of the Laplacian and generating graphs conditioned on these. We did not find steps handling constraints, apart from the auxiliary eigenvector refinement matrices construction (must belong to the special orthogonal group). We would be happy to discuss SPECTRE’s relevance if the reviewer clarifies why it is particularly pertinent.

W6: While ConStruct does not cover all PRODIGY constraints (e.g., molecular properties, see W7), it does handle a meaningful subset, including all of those tested on non-attributed datasets (edge count, triangle count, maximum degree). Crucially, ConStruct also handles combinatorial constraints (e.g., planarity, acyclicity), which PRODIGY cannot.

W7: ConStruct does not handle node feature-dependent constraints found in molecular generation. However, molecular generation is dominated by autoregressive models due to their ability to perform validity checks at each step with minimal overhead [1]. The possibility of node ordering in molecules (via canonical smiles) explains this success. In contrast, ConStruct is designed for settings where node ordering is not suitable, such as digital pathology, focusing on purely structural constraints. While integrating node-dependent constraints into ConStruct is an exciting prospect, we believe that our focus on structural constraints does not diminish our contribution in a fundamentally distinct setting, as highlighted by Reviewer FDH7 in W1.

Limitations: We appreciate the reviewer's suggestion and have elaborated on the specified points in the final manuscript (items 3 and 4 of global rebuttal). Overall, we believe we have addressed the limitations of our work adequately, a view also supported by Reviewer FDH7

[1] - Mercado, Rocío, et al. "Graph networks for molecular design." Machine Learning: Science and Technology 2021

We sincerely appreciate the reviewer’s constructive feedback and requests for clarification. We have addressed the raised questions below:

W1: An example of other purely structural constraints that ConStruct does not cover by default are edge-insertion invariant properties, i.e., properties that hold upon edge insertion. This type of constraint can be useful, for instance, in the molecular generation domain, where we could impose constraints like "the generated graph should at least have a cycle" (we explore the inverse setting — acyclic molecular generation — in Appendix G.2). We note, nevertheless, that edge-insertion invariant properties could be easily captured by our framework through two simple modifications: design the transition matrices with the absorbing state in the existing edge state (instead of in the no-edge state) and a projector that progressively removes edges (instead of inserting them) while preserving the desired property. This simple inversion of ConStruct would allow it to cover edge-insertion invariant properties. In item 3 of the global rebuttal, we discuss other meaningful constraints that ConStruct does not cover but that could be extended to as future work, even if not purely structural. We propose to explicitly add this discussion to the paper.

Additionally, an example of a structural constraint that is completely outside the scope of ConStruct can be seen in graph stochastic models. Since the validity of these types of graphs is determined via statistical tests (thus, not deterministically), it is difficult to constrain the generation in that setting. An example of this occurs in the graph generation benchmark SBM dataset (from Stochastic Block Model), where validity is checked using a Wald test [1]. To the best of our knowledge, constrained diffusion towards such graph structural properties remains an open problem.

W2: Since the projector is the only component incurring overhead, ConStruct only interferes with the complexity of the sampling algorithm, leaving the efficiency of the training algorithm intact. As described in Section 3.5, through the use of a blocking edge hash table and incremental property satisfaction algorithms, we are able to minimize the increase in complexity imposed by the projector. The complexity analysis for the blocking edge hash table is provided directly in Section 3.5. The complexity analysis for all the different edge-deletion invariant properties explored in the paper (planarity, acyclicity, lobster components, and maximum degree) can be found in Section 3.5 (planarity) and in Appendix C (all of them). We also provide a more explicit comparison between the underlying discrete diffusion algorithm and the incurred overhead by the projector in item 1 of the global rebuttal. We remark that due to the combinatorial nature of edge-deletion invariant properties, each property satisfaction algorithm is specific to the property at hand. Therefore, there is no general efficient property satisfaction algorithm for all edge-deletion invariant properties, and we have to address each property on a case-by-case basis.

W3: Item 1 of the global rebuttal details the minor overhead imposed by the projector within the diffusion framework. It also addresses the method’s (high) scalability relative to the underlying discrete diffusion framework. In particular, we demonstrate that as the generated graph size increases, the overhead of ConStruct becomes increasingly negligible compared to the underlying discrete diffusion framework. Therefore, as far as that discrete diffusion framework is able to scale, ConStruct remains a viable option.

[1] - Martinkus, Karolis, et al. "Spectre: Spectral conditioning helps to overcome the expressivity limits of one-shot graph generators." ICML, 2022.