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.