Graph diffusion models have emerged as state-of-the-art techniques in graph generation; yet, integrating domain knowledge into these models remains challenging. Domain knowledge is particularly important in real-world scenarios, where invalid generated graphs hinder deployment in practical applications. Unconstrained and conditioned graph diffusion models fail to guarantee such domain-specific structural properties. We present ConStruct, a novel framework that enables graph diffusion models to incorporate hard constraints on specific properties, such as planarity or acyclicity. Our approach ensures that the sampled graphs remain within the domain of graphs that satisfy the specified property throughout the entire trajectory in both the forward and reverse processes. This is achieved by introducing an edge-absorbing noise model and a new projector operator. ConStruct demonstrates versatility across several structural and edge-deletion invariant constraints and achieves state-of-the-art performance for both synthetic benchmarks and attributed real-world datasets. For example, by incorporating planarity constraints in digital pathology graph datasets, the proposed method outperforms existing baselines, improving data validity by up to 71.1 percentage points.
Paper
Similar papers
Peer review
Summary
The authors proposed ConStruct, a graph generative framework that enables hard-constraining graph topological properties that hold upon edge deletion throughout the entire sampling trajectory. Specifically, the authors model the forward (data-to-prior) process using an edge absorbing noise model, and they predict the reversed edge insertion process using a GNN projector.
Strengths
**S1.** The proposed method is the first graph constrained discrete generative framework. The hard-constraining graph generation task is challenging and meaningful. **S2.** The authors provided theoretical guarantee for the generation quality of ConStruct. **S3.** The authors improve the sampling efficiency using the incremental constraint satisfaction algorithm in the spirit of curriculum learning.
Weaknesses
**W1.** The ConStruct is only applicable to edge-deletion invariant properties (Definition 3.1). Thus, it cannot be applied to hard-constrain more complicated and general graph properties, e.g. chemical properties for molecules. However, this limitation does NOT weaken the contribution of this paper and should be considered a future research direction of hard-conditioned graph generation. **W2.** The projector module (Figure 2 and Algorithm 3) introduces intractability in likelihood estimation of the graph, making it hard to estimate the likelihood of the graph instances generated by ConStruct. **W3.** ConStruct seems to be a autoregressive method, which means that the sampling complexity is in proportional to the graph size. In contrast, the diffusion-based method generates the whole graph and keeps refining it along the generative trajectory. Thus, it seems that ConStruct takes more generative steps for large graphs (w.r.t the amount of nodes and edges) when compared to diffusion-based models. I recommend the authors to assess the time complexity and efficiency of this model compared to diffusion-based methods. **W4.** It seems that the authors did not compare their method against the two mentioned (Page 3, line 88-89) discrete-diffusion graph generative models EDGE [1] and Graph-ARM [2]. By the way, I recommend the authors to cite the latest or published version rather than the ArXiv versions. [1]. Xiaohui Chen, Jiaxing He, Xu Han, and Li-Ping Liu. 2023. Efficient and degree-guided graph generation via discrete diffusion modeling. In Proceedings of the 40th International Conference on Machine Learning (ICML'23), Vol. 202. JMLR.org, Article 181, 4585–4610. [2]. Kong, L., Cui, J., Sun, H., Zhuang, Y., Prakash, B.A., & Zhang, C. (2023). Autoregressive Diffusion Model for Graph Generation. *International Conference on Machine Learning*.
Questions
**Q1.** Please clarify the definition of $\Delta^b$ in Page 5, line 171. **Q2.** During the reverse sampling process, how to guarantee the existence of a feasible $G^{t-1}$ among the candidates induced by discarding some newly added edges from $G^t$ to $\widehat{G}^{t-1}$ (or equivalently, the intersection of $\mathcal{C}$ and $\mathcal{G}^{t-1}$ in Theorem 1 is not empty)? If there is no feasible candidate, will the generative procedure be prematurely existed? **Q3.** Following **W2**, I notice that there is a seemingly discrepancy between the training and sampling process. The effect of the projector is absent during the training process. I hope the authors can add some analysis and clarifications on why the edge predictor trained without projector can still provide satisfactory samples.
Rating
7
Confidence
4
Soundness
3
Presentation
4
Contribution
4
Limitations
The authors adequately discussed the limitations of the proposed method. They discuss in detail the performance limitations of their approach in Appendix H.1. They also point out potential further improvements and extensions to their approach in Section 5. Finally, they discuss computational efficiency and scalability of the proposed method in Section 3.5 and Appendices D.2 and D.3.
Summary
The paper presents a novel diffusion model, ConStruct, to generate graphs that follow certain pre-specified properties. ConStruct involves an edge-absorbing forward process and a projected edge-addition reverse process to sample graphs that satisfy pre-specified constraints. The novelty of their method comes from a simple random-sampling-based projection algorithm that samples constrained graphs at each diffusion step. Experimental results show that ConStruct can generate more realistic synthetic graphs that have a pre-defined constraint for the whole domain. They also show its applicability to real-world pathology graphs, by leveraging the fact that they tend to be planar.
Strengths
- The paper is well-written and easy to read. - Experimental results are comprehensive for the synthetic graph datasets and use all representative metrics. - The paper also provides results of a real-world pathology dataset to highlight how structurally constraining the diffusion model is useful once we can establish some structure on the real-world graphs. In particular, they consider the planarity of the breast cancer pathology cell graphs. - ConStruct provides efficient ways to solve an otherwise NP-hard problem of projecting to hard constraints of acyclicity and planarity. The sampling time of ConStruct is at par with its unconstrained counterparts, which is quite impressive.
Weaknesses
- It is not clear how applicable such domain-level constraints will be for real-world graphs that do not have a well-defined constraint. While the motivating example of pathology cell graphs is appreciated, it is difficult to see how it generalizes. - The idea is similar to PRODIGY which can be applied to any diffusion model and constraint including discrete models in the latest version [1] (which can be ignored but worthwhile to mention). Upon ignoring the minor requirement of an edge-absorbing forward process, ConStruct can be seen as an approximation of the projection operator where the distance is calculated as a GED instead of the Euclidean distance between the adjacency matrices. Thus, the novelty of the proposed method is limited. - Furthermore, the authors claim that PRODIGY distorts the underlying diffusion process even though PRODIGY takes a fractional step to the closest noisy graph that satisfies the given constraint. On the other hand, ConStruct finds a random graph that satisfies the constraint and takes a full step in that direction. Thus, it seems intuitively that ConStruct distorts the process more than PRODIGY, as opposed to the authors' claims. - The major novelty of the method comes from the proposed projection algorithm that tries to circumvent the NP-hardness by iteratively adding a random edge if it satisfies the constraint, which can be seen as a simple randomized greedy algorithm, which is quite well-studied in the discrete optimization literature. Theorem 1 in this vein is a bit trivial since it is expected that the optimal graph will belong to a randomly-edited set but it is not clear how easily it will be sampled for an arbitrary constraint. In the absence of this analysis, the proposed projection algorithm is not suitable for application. - While the authors compare against SPECTRE, they do not provide an elaborate discussion with this important related work that proposed this problem of including structurally-constrained generative models. - The proposed framework is limited to edge-deletion invariant (or more formally, downward-closed) constraints while the PRODIGY framework can theoretically handle a larger range of constraints including box constraints. - ConStruct is limited to non-attributed structural constraints due to the edit distance formulation and thus, cannot be applied to important molecular constraints. [1] Sharma, Kartik, Srijan Kumar, and Rakshit Trivedi. "Diffuse, Sample, Project: Plug-And-Play Controllable Graph Generation." Forty-first International Conference on Machine Learning. 2024
Questions
See above weaknesses.
Rating
6
Confidence
4
Soundness
3
Presentation
3
Contribution
3
Limitations
The authors do not adequately discuss the limitations of their work and the potential negative impacts of their work. It will be really useful to elaborate on the limitations of their work, e.g., limited to structural constraints of a certain kind. Furthermore, since they are using a pathology dataset of breast cancer studies, the authors must discuss the potential negative societal impacts of their analysis, particularly when the "planar" generated graphs are used as a data augmentation tool for the downstream application for cancer detection or such.
Summary
This paper presents ConStruct, a framework incorporating structural constraints into graph generation models using a discrete graph diffusion process. By introducing an edge-absorbing noise model and a projector operator, ConStruct ensures generated graphs meet specific properties like planarity or acyclicity, crucial for real-world applications. The framework significantly improves the validity of generated graphs, demonstrated through experiments on synthetic benchmarks and real-world datasets such as digital pathology, achieving up to a 71.1 percentage point increase in graph validity. It mainly focuses on addressing the challenge of integrating domain knowledge into graph generative models, enhancing their practical deployment.
Strengths
1. Maintaining the structural constraint of the generated graph is an important but challenging problem for diffusion-based graph generative models. 2. The design of the edge-absorbing noise model and projector operator is reasonable and technically sound. Especially the efficiency consideration of incremental validity checks. 3. The experimental results are good compared with recent SOTA baselines, including diffusion-based methods. The extensive results provided in appendix also well support the advantage of proposed method. 4. The presented evaluation on Digital Pathology Graph dataset is interesting, and the released dataset seems useful for future research.
Weaknesses
1. As explained by the authors, the proposed method can only deal with a specific type of structural constraint, i.e., edge-deletion invariance, but the discussion on the possible impact of this limitation is not well clarified. For example, what other normally-seen constraint 2. Lack of complexity analysis. Instead, only the runtime measurement is provided. 3. This method might not be able to deal with large graphs.
Questions
Please answer my listed weakness above.
Rating
7
Confidence
4
Soundness
3
Presentation
3
Contribution
3
Limitations
None.
Thanks for the detailed responses. I hope the authors to thoroughly scrutinize the manuscript to ensure the notation system is correct and self-contain. I raise my score to 7 because my Q2 is fully addressed. The setting is new and important, the proposed method is sounded. The logic flow of the paper is smooth. The theoretical analysis is adequate. I cannot give a higher rate because this paper is restricted to 'edge-deletion-invariant constraints', which is not general enough.
We thank the reviewer for their time and the score update. We remain open to any further clarifications.
Thanks for the rebuttal! However, I don't agree with the authors' views on certain topics and hope we can discuss and reach a conclusion. **Motivation:** The major problem I have with this is that the structural constraint of the underlying graphs must be known beforehand. As noted, this helps in the case of synthetic graphs which are specifically formed of such a constraint and maybe some generalizations can happen for specific use-cases as identified by authors for pathology graphs and planarity. However, the major benefit of graph generation is that it can approximate a distribution just from data. What this paper proposes is to include an additional constraint that identifies the underlying distribution. This is good if the proposed method is motivated as a way to simulate synthetic NP-hard structural distributions, which takes time to generate otherwise. However, in the absence of such a clear motivation and an expectation to generalize to real-world graphs, it is not clear how the users would be able to identify structural constraints of arbitrary graph distributions before training. **Comparison with SPECTRE:** SPECTRE trains generative model by explicitly conditioning the eigenspectrum of the training data. This explicit conditioning on the underlying distribution is similar to the idea of explicitly constraining on the structural constraint of planarity and acyclicity that the current paper looks at. For example, if we have graphs with 2 connected components, it can be inferred from the number of non-zero eigenvalues in the training graphs. However, this discussion is absent in the current work but is extremely important. **Comparison with PRODIGY:** This paper also requires further discussion that the authors have not acknowledged. The difference is not in continuous vs discrete or combinatorial vs not. PRODIGY constraints are also inherently combinatorial as opposed to what the authors are claiming. They have particularly considered P-space matroid constraints while ConStruct focuses on NP-hard constraints. However, more importantly, the difference is that ConStruct is a discrete diffusion model trained to generate graphs given a structural constraint on the distribution while PRODIGY aims to do plug-and-play controllable graph generation to satisfy arbitrary constraints. The authors have been inconsistent in claiming (with the guidance comment) that they may be doing the same problem as PRODIGY, then such an experimental validation would be essential to show. **Contribution of the method:** The theorems that assist the proposed method are not quite generalizable. Theorem 1 barely shows that a satisfiable constrained graph can be sampled, which is also possible through a simple random sampling. Theorem 2, on the other hand, is specific to a single constraint. I agree that any such theoretical proof will be extremely hard to prove for a general graph constraint. However, in that case, the authors should not overclaim their contributions in terms of constraint satisfaction with discrete graphs. The experiments are strong enough to validate the method's usefulness. **Attributed settings:** I am not diminishing the contributions but I would like to keep my opinion that this is a major weakness in using the method in real-world settings.
We thank the reviewer for the detailed reply to our rebuttal. We address the raised concerns below: **Motivation**: We agree with the reviewer that the flexibility provided by the unsconstrained graph generation of mimicking any data distribution is extremely convenient. However, in many real-world scenarios, this flexibility alone is not sufficient to yield satisfactory performance without incorporating additional priors into the generative model. This approach is particularly relevant in data scarce settings — such as due to high costs, ethical/privacy concerns, or a lack of high-quality annotated data — or where instances that do not adhere to specified constraints are either infeasible or lack physical meaning. Constrained generation is a valuable method for incorporating such priors by hard-constraining the hypothesis space to valid instances (in our cases, graphs), thereby reducing the search space and potentially enhancing the efficacy of the learning process. We note, nevertheless, that just enforcing such constraint does not identify the underlying distribution; instead, there is still the need to learn the underlying distribution within the constrained domain. As outlined in our rebuttal (W1), constrained generation indeed requires an explicit and unambiguous definition of the constraints. We understand the reviewer’s concerns about identifying structural constraints *a priori*, but we do not view this as a limitation. Instead, constrained generation is a practical choice for settings where practitioners have established explicit constraints through expertise or problem exposure and wish to leverage them for a more effective learning process. Typical sources of such constraints include the physics of the problem, application domain constraints, or detailed knowledge about the data acquisition process. We highlight several real-world examples (some mentioned in the paper) where such prior knowledge is available and can be effectively applied using ConStruct, showcasing its versatility. - *Planarity*: design of road networks [1], chip design [2], biochemistry [3] or digital pathology [4]. - *Acyclicity*: evolutionary biology [5] or epidemiology [6]. Additionally, if we consider the extension of discrete diffusion for directed graphs, e.g. [7], for which ConStruct is still applicable, there are several domains where the generation of directed acyclic graphs is critical: neural architecture search or bayesian network structure learning [8], causal discovery [9], etc. - *Maximum Degree*: design of contact networks [10, 11]. **Comparison to SPECTRE**: Even though we still see some relevant differences between ConStruct and SPECTRE - such as, 1) ConStruct enforces constraints by default, while SPECTRE requires learning such dependencies even with explicit structural information; or 2) SPECTRE uses spectral properties to inform the model about global graph structure, whereas ConStruct can still be used to constrain generation for local level properties (e.g., maximum degree) -, we agree with the reviewer that the latter is the first method, to the best of our knowledge, that recognizes the importance of explicitly incorporating structural information (other than locality biases from common GNNs) as powerful priors for the expressiveness of one-shot graph generative models. Therefore, we will add this discussion into our final version of the manuscript. We thank the reviewer for the constructive feedback.
**Comparison with PRODIGY**: We agree with the reviewer that the two methods can be used to address different sets of constraints and, more importantly, that the main difference between PRODIGY and ConStruct consists of the different tasks addressed by both, as accurately described by the reviewer. The fact that both tasks are different lead to fundamental differences in the two approaches. For example, PRODIGY does not have to necessarily guarantee constraint satisfaction, whilst ConStruct does. The comment regarding guidance points towards our section G.2. There, we use the projector to control the generation of an unconstrained model (i.e., trained with a noise model that does not preserve the structural constraint across the forward process). This approach is similar to PRODIGY's procedure but uses our projector instead. Even though this approach accomplishes satisfactory performance, it is significantly outperformed by a ConStruct model (where the noise model preserves the constraint) in terms of validity: 81.3\% vs 99.8\%. As discussed in that section, this experiment is meaningful to reinforce the foundation upon which ConStruct is designed: matching the forward and reverse domains allows for in distribution prediction of the denoising neural network, improving constrained generation performance. We apologize if this reference was misleading. To address the reviewer's concerns, we propose to extend our paragraph dedicated to PRODIGY of our related work section (ll. 80-87, page 3) to make a more explicit distinction between both methods on the different nature of constraints addressed and, specially, on the different tasks tackled by each of them. **Contribution of the method**: We thank the reviewer for acknowledging the suitability of our method for application. Our intention with the provided theoretical analysis is to provide insights to the reader that underscore the complexity of the problem and substantiate the design of our projector. For instance, Theorem 1 implies that a deterministic projector based on edge sampling likelihoods from the diffusion model is not guaranteed to have the optimal graph in its output set, as elaborated in Appendix H.3. Also, Theorems 1 and 2 and the counter-examples in Figure 3 show that the problem that the projector is addressing is not so trivial such that it can always output the optimal graph in the GED sense for all the edge-deletion invariant properties. Nevertheless, our projector is *guaranteed* to produce graphs that meet the specified structural constraints. Considering this, we remain open to discussing and refining any specific claims in our manuscript that might be seen as overstated by the reviewer. **Attributed settings**: We appreciate the reviewer’s opinion but do not fully understand why the absence of node feature-dependent constraints is seen as a *major* weakness. As argued in W7 of rebuttal, ConStruct targets applications where node ordering is not feasible. In contrast, node-edge joint constraints are primarily useful for constrained molecular generation, a domain where node ordering is possible and thus perfectly suited for autoregressive models. Due to their ability to perform very efficient validity checks at each step, these models already successfully solve such task. While integrating node-edge constraints is an interesting potential extension to ConStruct, we believe that our focus on structural constraints adresses our intended applications and does not constitute a fundamental weakness. ____ We believe that the constructive feedback provided by the reviewer has guided us toward addressing their concerns more effectively. In light of these improvements, we hope the reviewer might consider revising their score.
[1] - Xie et al. "Topological evolution of surface transportation networks." Computers, Environment and Urban Systems, 2009. [2] - Bhatt et al. "A framework for solving VLSI graph layout problems." Journal of Computer and System Sciences, 1984. [3] - Simmons III et al. "Synthesis of the first topologically non-planar molecule." Tetrahedron Letters, 1981. [4] - Jaume et al. "Histocartography: A toolkit for graph analytics in digital pathology." MICCAI Workshop on Computational Pathology. PMLR, 2021. [5] - Gregory. "Understanding evolutionary trees." Evolution: Education and Outreach, 2008. [6] - Seibold et al. "Modeling epidemics on a regular tree graph." Letters in Biomathematics, 2016. [7] - Asthana, Rohan, et al. "Multi-conditioned Graph Diffusion for Neural Architecture Search." arXiv, 2024. [8] - Zhang, Muhan, et al. "D-vae: A variational autoencoder for directed acyclic graphs." NeurIPS, 2019. [9] - Sanchez et al. "Diffusion models for causal discovery via topological ordering." arXiv, 2022. [10] - Jang et al. "Evaluating architectural changes to alter pathogen dynamics in a dialysis unit: for the CDC MInD-healthcare group." International Conference on Advances in Social Networks Analysis and Mining, 2019. [11] - Kong et al. "Autoregressive diffusion model for graph generation." ICML, 2023.
I thank the authors for providing additional discussion and clarifications regarding their work that positions their paper better in my opinion. I believe they should thus include all these points in their revised version. I don't think non-attributed settings is a major weakness but worth mentioning as a limitation and potential for future research. I will raise my scores now that I think we are on the same page.
We thank the reviewer for their time, constructive feedback, and the updated score. We will incorporate the additional discussions and clarifications into the revised version of the paper.
Appreciation for Your Efforts and Feedback
Dear Reviewers and Area Chairs, Thank you for managing our submission. We are pleased to see that our rebuttal successfully addressed the reviewers' concerns. We greatly value the feedback provided, which has clearly enhanced the quality of our paper. If there are any remaining issues or additional points that need further attention, please let us know. We really appreciate your time and consideration. Best regards, The Authors
Decision
Accept (poster)