DDPS: Discrete Diffusion Posterior Sampling for Paths in Layered Graphs

• URL: http://arxiv.org/abs/2504.20754v1
• Date: Tue, 29 Apr 2025 13:34:17 GMT
• Title: DDPS: Discrete Diffusion Posterior Sampling for Paths in Layered Graphs
• Abstract summary: We study the problem of generating paths in a layered graph using discrete diffusion models.<n>Our approach utilizes a simple yet effective representation for paths which we call the padded adjacency-list matrix.<n>Our preliminary results show that our method outperforms alternatives which do not explicitly account for path constraints.
• Score: 27.60869539689859
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.

Related papers

• Diffusion Integrated Gradients: Controllable Path Generation for Flexible Feature Attribution [29.066960285647962]
  Integrated Diffusion Gradients (DiffIG) is a novel method that reformulates path generation as a conditional generative modeling problem.<n>We demonstrate that DiffIG quantitatively matches or outperforms existing path-based methods, achieving perceptually aligned explanations.<n>This work introduces a new generative perspective for flexible, inference-time controllable Explainable Artificial Intelligence (XAI) methods.
  arXiv  Detail & Related papers  (2026-06-21T03:04:35Z)
• Feynman-Kac Correctors in Diffusion: Annealing, Guidance, and Product of Experts [64.34482582690927]
  We provide an efficient and principled method for sampling from a sequence of annealed, geometric-averaged, or product distributions derived from pretrained score-based models. We propose Sequential Monte Carlo (SMC) resampling algorithms that leverage inference-time scaling to improve sampling quality.
  arXiv  Detail & Related papers  (2025-03-04T17:46:51Z)
• Diffusing Differentiable Representations [60.72992910766525]
  We introduce a novel, training-free method for sampling differentiable representations (diffreps) using pretrained diffusion models. We identify an implicit constraint on the samples induced by the diffrep and demonstrate that addressing this constraint significantly improves the consistency and detail of the generated objects.
  arXiv  Detail & Related papers  (2024-12-09T20:42:58Z)
• Random Walks with Tweedie: A Unified View of Score-Based Diffusion Models [11.161487364062667]
  Diffusion models have emerged as powerful tools for generating realistic, synthetic signals.<n>We present a concise derivation for several influential score-based diffusion models that relies on only a few textbook results.
  arXiv  Detail & Related papers  (2024-11-27T19:13:20Z)
• Derivative-Free Guidance in Continuous and Discrete Diffusion Models with Soft Value-Based Decoding [84.3224556294803]
  Diffusion models excel at capturing the natural design spaces of images, molecules, DNA, RNA, and protein sequences. We aim to optimize downstream reward functions while preserving the naturalness of these design spaces. Our algorithm integrates soft value functions, which looks ahead to how intermediate noisy states lead to high rewards in the future.
  arXiv  Detail & Related papers  (2024-08-15T16:47:59Z)
• A Practical Diffusion Path for Sampling [8.174664278172367]
  Diffusion models are used in generative modeling to estimate score vectors guiding a Langevin process. Previous approaches rely on Monte Carlo estimators that are either computationally heavy to implement or sample-inefficient. We propose a computationally attractive alternative, relying on the so-called dilation path, that yields score vectors that are available in closed-form.
  arXiv  Detail & Related papers  (2024-06-20T07:00:56Z)
• A Diffusion Model Framework for Unsupervised Neural Combinatorial Optimization [7.378582040635655]
  Current deep learning approaches rely on generative models that yield exact sample likelihoods. This work introduces a method that lifts this restriction and opens the possibility to employ highly expressive latent variable models. We experimentally validate our approach in data-free Combinatorial Optimization and demonstrate that our method achieves a new state-of-the-art on a wide range of benchmark problems.
  arXiv  Detail & Related papers  (2024-06-03T17:55:02Z)
• Denoising Diffusion Bridge Models [54.87947768074036]
  Diffusion models are powerful generative models that map noise to data using processes. For many applications such as image editing, the model input comes from a distribution that is not random noise. In our work, we propose Denoising Diffusion Bridge Models (DDBMs)
  arXiv  Detail & Related papers  (2023-09-29T03:24:24Z)
• Towards Controllable Diffusion Models via Reward-Guided Exploration [15.857464051475294]
  We propose a novel framework that guides the training-phase of diffusion models via reinforcement learning (RL) RL enables calculating policy gradients via samples from a pay-off distribution proportional to exponential scaled rewards, rather than from policies themselves. Experiments on 3D shape and molecule generation tasks show significant improvements over existing conditional diffusion models.
  arXiv  Detail & Related papers  (2023-04-14T13:51:26Z)
• Example-Based Sampling with Diffusion Models [7.943023838493658]
  diffusion models for image generation could be appropriate for learning how to generate point sets from examples. We propose a generic way to produce 2-d point sets imitating existing samplers from observed point sets using a diffusion model. We demonstrate how the differentiability of our approach can be used to optimize point sets to enforce properties.
  arXiv  Detail & Related papers  (2023-02-10T08:35:17Z)
• Interpretations Steered Network Pruning via Amortized Inferred Saliency Maps [85.49020931411825]
  Convolutional Neural Networks (CNNs) compression is crucial to deploying these models in edge devices with limited resources. We propose to address the channel pruning problem from a novel perspective by leveraging the interpretations of a model to steer the pruning process. We tackle this challenge by introducing a selector model that predicts real-time smooth saliency masks for pruned models.
  arXiv  Detail & Related papers  (2022-09-07T01:12:11Z)
• Improving Diffusion Models for Inverse Problems using Manifold Constraints [55.91148172752894]
  We show that current solvers throw the sample path off the data manifold, and hence the error accumulates. To address this, we propose an additional correction term inspired by the manifold constraint. We show that our method is superior to the previous methods both theoretically and empirically.
  arXiv  Detail & Related papers  (2022-06-02T09:06:10Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.