Hard-Constrained Graph Generation with Discrete-Projection Diffusion

Diffusion models have achieved remarkable success in graph generation, but enforcing hard constraints on generated graphs remains challenging, limiting their deployment in constraint-critical applications. Existing approaches either fail to guarantee strict constraint satisfaction or are limited to narrow constraint types, lacking the flexibility to handle diverse constraint specifications. To address this challenge, we exploit the discrete structure of graphs, which allows hard constraints to be formulated as symbolic reasoning problems. Building on this insight, we propose NSPSG, a framework that integrates unconstrained diffusion models with discrete projection operators. NSPSG employ an SMT (Satisfiability Modulo Theories)-based projector to ensure that the generated graphs strictly satisfy constraints while remaining within the training data distribution. To further accelerate generation, we employ a supervised auto-regressive neural projector to approximate the symbolic reasoning process. Across heterogeneous constraints and various graph generation datasets, NSPSG achieves 99%-100% validity rates, demonstrating state-of-the-art performance. Notably, for a complex non-linear constraint, it improves data validity by up to 43% and reaches 99% validity while maintaining comparable generation efficiency.

Graph diffusion models can generate realistic graphs, but they often struggle to obey hard rules such as “must be connected,“must not contain certain patterns,” or other domain-specific constraints. This makes them unreliable in settings where invalid outputs are costly or unusable. We propose NSPSG, a framework that combines an unconstrained diffusion model with discrete projection. The key idea is to treat constraint satisfaction as a symbolic reasoning problem on graphs, then use an SMT-based projector to project generated graphs so they strictly satisfy the required constraints while staying close to the training distribution. To make generation faster, we also train a supervised auto-regressive neural projector that approximates this symbolic project process. NSPSG achieves 99%–100% validity across diverse constraints and graph datasets, showing that strict constraint satisfaction is possible without sacrificing generation quality. It is effective for complex non-linear constraints, where it improves validity by up to 43%. This makes graph generation more practical for constraint-critical applications such as molecular design and other structured generation tasks.