DDPS: Discrete Diffusion Posterior Sampling for Paths in Layered Graphs
This work addresses the issue of generating constrained samples in graph-based problems, which is incremental as it extends diffusion models to a specific domain.
The paper tackles the problem of generating paths in layered graphs with explicit constraints using discrete diffusion models, and the result shows that their method empirically outperforms alternatives that do not account for path constraints.
Diffusion models form an important class of generative models today, accounting for much of the state of the art in cutting edge AI research. While numerous extensions beyond image and video generation exist, few of such approaches address the issue of explicit constraints in the samples generated. In this paper, we study the problem of generating paths in a layered graph (a variant of a directed acyclic graph) using discrete diffusion models, while guaranteeing that our generated samples are indeed paths. Our approach utilizes a simple yet effective representation for paths which we call the padded adjacency-list matrix (PALM). In addition, we show how to effectively perform classifier guidance, which helps steer the sampled paths to specific preferred edges without any retraining of the diffusion model. Our preliminary results show that empirically, our method outperforms alternatives which do not explicitly account for path constraints.