# Generative Modelling of Structurally Constrained Graphs

arXiv: https://arxiv.org/abs/2406.17341 · HTML: https://mlsanity.com/paper/2406.17341/

## Key facts

- Cited by 19 papers in the map (data through 14 Oct 2026).
- Placed in Flow matching, time series and science, one of 14 directions in Diffusion models.
- Builds on 58 of its 89 references that are in the map.
- First posted on arXiv 25 Jun 2024.

## Placed in

- Diffusion models / [Flow matching, time series and science](https://mlsanity.com/diffusion/flow-matching-time-series-and-science/)

## Builds on (most cited first, 30 of 58)

- [Denoising Diffusion Probabilistic Models](https://mlsanity.com/paper/2006.11239/) (2020)
- [Deep Unsupervised Learning using Nonequilibrium Thermodynamics](https://mlsanity.com/paper/1503.03585/) (2015)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Improved Denoising Diffusion Probabilistic Models](https://mlsanity.com/paper/2102.09672/) (2021)
- [Structured Denoising Diffusion Models in Discrete State-Spaces](https://mlsanity.com/paper/2107.03006/) (2021)
- [Variational Graph Auto-Encoders](https://mlsanity.com/paper/1611.07308/) (2016)
- [MoleculeNet: A Benchmark for Molecular Machine Learning](https://mlsanity.com/paper/1703.00564/) (2017)
- [Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networks](https://mlsanity.com/paper/1810.02244/) (2018)
- [On the Convergence of Adam and Beyond](https://mlsanity.com/paper/1904.09237/) (2019)
- [A Generalization of Transformer Networks to Graphs](https://mlsanity.com/paper/2012.09699/) (2020)
- [Junction Tree Variational Autoencoder for Molecular Graph Generation](https://mlsanity.com/paper/1802.04364/) (2018)
- [DiGress: Discrete Denoising diffusion for graph generation](https://mlsanity.com/paper/2209.14734/) (2022)
- [GraphRNN: Generating Realistic Graphs with Deep Auto-regressive Models](https://mlsanity.com/paper/1802.08773/) (2018)
- [MolGAN: An implicit generative model for small molecular graphs](https://mlsanity.com/paper/1805.11973/) (2018)
- [GraphVAE: Towards Generation of Small Graphs Using Variational Autoencoders](https://mlsanity.com/paper/1802.03480/) (2018)
- [GuacaMol: Benchmarking Models for De Novo Molecular Design](https://mlsanity.com/paper/1811.09621/) (2018)
- [Score-based Generative Modeling of Graphs via the System of Stochastic Differential Equations](https://mlsanity.com/paper/2202.02514/) (2022)
- [Molecular Sets (MOSES): A Benchmarking Platform for Molecular Generation Models](https://mlsanity.com/paper/1811.12823/) (2018)
- [Permutation Invariant Graph Generation via Score-Based Generative Modeling](https://mlsanity.com/paper/2003.00638/) (2020)
- [Efficient Graph Generation with Graph Recurrent Attention Networks](https://mlsanity.com/paper/1910.00760/) (2019)
- [DIFUSCO: Graph-based Diffusion Solvers for Combinatorial Optimization](https://mlsanity.com/paper/2302.08224/) (2023)
- [Fr'echet ChemNet Distance: A metric for generative models for molecules in drug discovery](https://mlsanity.com/paper/1803.09518/) (2018)
- [GraphDF: A Discrete Flow Model for Molecular Graph Generation](https://mlsanity.com/paper/2102.01189/) (2021)
- [GraphNVP: An Invertible Flow Model for Generating Molecular Graphs](https://mlsanity.com/paper/1905.11600/) (2019)
- [Graph Normalizing Flows](https://mlsanity.com/paper/1905.13177/) (2019)
- [SPECTRE: Spectral Conditioning Helps to Overcome the Expressivity Limits of One-shot Graph Generators](https://mlsanity.com/paper/2204.01613/) (2022)
- [D-VAE: A Variational Autoencoder for Directed Acyclic Graphs](https://mlsanity.com/paper/1904.11088/) (2019)
- [MiDi: Mixed Graph and 3D Denoising Diffusion for Molecule Generation](https://mlsanity.com/paper/2302.09048/) (2023)
- [Constrained Synthesis with Projected Diffusion Models](https://mlsanity.com/paper/2402.03559/) (2024)
- [Reflected Diffusion Models](https://mlsanity.com/paper/2304.04740/) (2023)

## Built on by (most cited first, 19 of 19)

- [Dynamic Generation of Multi-LLM Agents Communication Topologies with Graph Diffusion Models](https://mlsanity.com/paper/2510.07799/) (2025)
- [Improving Molecular Graph Generation with Flow Matching and Optimal Transport](https://mlsanity.com/paper/2411.05676/) (2024)
- [Projected Coupled Diffusion for Test-Time Constrained Joint Generation](https://mlsanity.com/paper/2508.10531/) (2025)
- [Graph Guided Diffusion: Unified Guidance for Conditional Graph Generation](https://mlsanity.com/paper/2505.19685/) (2025)
- [Generating Directed Graphs with Dual Attention and Asymmetric Encoding](https://mlsanity.com/paper/2506.16404/) (2025)
- [Semantically Consistent Discrete Diffusion for 3D Biological Graph Modeling](https://mlsanity.com/paper/2507.04856/) (2025)
- [Inference-Time Attribute Distribution Alignment for Unconditional Diffusion](https://mlsanity.com/paper/2605.07456/) (2026)
- [Designing ReLU Generative Networks to Enumerate Trees with a Given Tree Edit Distance](https://mlsanity.com/paper/2510.10706/) (2025)
- [Unveiling and Steering Connectome Organization with Interpretable Latent Variables](https://mlsanity.com/paper/2505.13011/) (2025)
- [A collaborative constrained graph diffusion model for the generation of realistic synthetic molecules](https://mlsanity.com/paper/2505.16365/) (2025)
- [NGTM: Substructure-based Neural Graph Topic Model for Interpretable Graph Generation](https://mlsanity.com/paper/2507.13133/) (2025)
- [Local Message-Passing for Discrete Graph Generation](https://mlsanity.com/paper/2603.08825/) (2026)
- [Bi-CamoDiffusion: A Boundary-informed Diffusion Approach for Camouflaged Object Detection](https://mlsanity.com/paper/2603.13357/) (2026)
- [ReLU Networks for Exact Generation of Similar Graphs](https://mlsanity.com/paper/2604.05929/) (2026)
- [Oracle-Budgeted Molecular Optimization with Short-Term Graph Memory](https://mlsanity.com/paper/2607.28437/) (2026)
- [From topology learning to graph generation: A unifying perspective](https://mlsanity.com/paper/2609.02286/) (2026)
- [Partially Observed Sparse Graphs: The Unknown Sampling Rate is a Tail Index](https://mlsanity.com/paper/2609.26199/) (2026)
- [Constrained Goal-directed Planar Graph Generation with Grammar-based Reinforcement Learning](https://mlsanity.com/paper/2610.06244/) (2026)
- [Exact Topological Compliance: Generating Persistence-Equivalent Graphs](https://mlsanity.com/paper/2610.18856/) (2026)

## Abstract (arXiv)

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.