Plug-and-Play Controllable Graph Generation with Diffusion Models

Diffusion models for graph generation present transformative capabilities in generating high-quality graphs. However, controlling the properties of the generated graphs remains a challenging task for the existing methods as they mainly focus on uncontrolled graph generation from the data. To address this limitation, we propose PRODIGY (PROjected DIffusion for generating constrained Graphs), a novel approach for controllable graph generation that works with any pre-trained diffusion model. This formalizes the problem of controlled graph generation and identifies a class of constraints (e.g., edge count, valency, etc.) applicable to practical graph generation tasks. At the center of our approach is a plug-and-play sampling process, based on projection-based optimization to ensure that each generated graph satisfies the specified constraints. Experiments demonstrate the effectiveness of PRODIGY in generating high-quality and diverse graphs that satisfy the specified constraints while staying close to the training distribution.