DDPS: Discrete Diffusion Posterior Sampling for Paths in Layered Graphs

Published as a workshop paper at ICLR 2025DDPS: D iscrete D iffusion P osterior S ampling for Pathsin L ayered G raphs Hao Luan 1, See-Kiong Ng 1,2, and Chun Kai Ling 1 1 School of Computing, National University of Singapore 2 Institute of Data Science, National University of Singapore haoluan@comp.nus.edu.sg, A bstract Di ff usion 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 di ffusion models, while guaranteeing that our generated samples are indeed paths. Our approach utilizes a simple yet e ffective representation for paths which we call the padded adjacency-list matrix (P ALM). In addition, we show how to e ff ectively perform classifier guidance, which helps steer the sampled paths to specific preferred edges without any retraining of the di ff usion model. Our preliminary results show that empirically, our method outperforms alternatives which do not explicitly account for path constraints. 1 I ntroduction Di ffusion models have emerged as one of the most popular methods of generative AI particularly with hyper-realistic image and video generation, often outperforming older methods like generative adversarial networks. The recent years have seen much interest in replicating this success in other domains. These domains include protein design (Frey et al., 2024), molecular conformations (Xu et al., 2022), text generation (Li et al., 2022), robotics (Chi et al., 2023; Wang et al., 2024; Feng et al., 2024; 2025), etc. Unlike image and video generation, These recent applications often require the restriction that the generated samples belong to some discrete domain .