Discrete Diffusion Schrödinger Bridge Matching for Graph Transformation

• URL: http://arxiv.org/abs/2410.01500v2
• Date: Fri, 28 Feb 2025 08:55:22 GMT
• Title: Discrete Diffusion Schrödinger Bridge Matching for Graph Transformation
• Authors: Jun Hyeong Kim, Seonghwan Kim, Seokhyun Moon, Hyeongwoo Kim, Jeheon Woo, Woo Youn Kim,
• Abstract summary: Transporting arbitrary distributions between arbitrary distributions is a fundamental goal in generative modeling.<n>We propose a novel framework that utilizes continuous-time Markov chains to solve the SB problem in a high-dimensional discrete state space.<n>We show that our framework can effectively optimize molecules' property-of-interest with minimal graph transformation.
• Score: 1.8257739595540863
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Transporting between arbitrary distributions is a fundamental goal in generative modeling. Recently proposed diffusion bridge models provide a potential solution, but they rely on a joint distribution that is difficult to obtain in practice. Furthermore, formulations based on continuous domains limit their applicability to discrete domains such as graphs. To overcome these limitations, we propose Discrete Diffusion Schr\"odinger Bridge Matching (DDSBM), a novel framework that utilizes continuous-time Markov chains to solve the SB problem in a high-dimensional discrete state space. Our approach extends Iterative Markovian Fitting to discrete domains, and we have proved its convergence to the SB. Furthermore, we adapt our framework for the graph transformation, and show that our design choice of underlying dynamics characterized by independent modifications of nodes and edges can be interpreted as the entropy-regularized version of optimal transport with a cost function described by the graph edit distance. To demonstrate the effectiveness of our framework, we have applied DDSBM to molecular optimization in the field of chemistry. Experimental results demonstrate that DDSBM effectively optimizes molecules' property-of-interest with minimal graph transformation, successfully retaining other features. Source code is available $\href{https://github.com/junhkim1226/DDSBM}{here}$.

Related papers

• Surrogate models for diffusion on graphs via sparse polynomials [0.40964539027092906]
  We provide sparse-based surrogate models for parametric diffusion equations on graphs with community structure. Our theoretical findings are accompanied by a series of numerical experiments conducted on both synthetic and real-world graphs.
  arXiv  Detail & Related papers  (2025-02-10T15:57:33Z)
• Latent Schrodinger Bridge: Prompting Latent Diffusion for Fast Unpaired Image-to-Image Translation [58.19676004192321]
  Diffusion models (DMs), which enable both image generation from noise and inversion from data, have inspired powerful unpaired image-to-image (I2I) translation algorithms. We tackle this problem with Schrodinger Bridges (SBs), which are differential equations (SDEs) between distributions with minimal transport cost. Inspired by this observation, we propose Latent Schrodinger Bridges (LSBs) that approximate the SB ODE via pre-trained Stable Diffusion. We demonstrate that our algorithm successfully conduct competitive I2I translation in unsupervised setting with only a fraction of cost required by previous DM-
  arXiv  Detail & Related papers  (2024-11-22T11:24:14Z)
• Identifying Drift, Diffusion, and Causal Structure from Temporal Snapshots [10.018568337210876]
  We present the first comprehensive approach for jointly estimating the drift and diffusion of an SDE from its temporal marginals. We show that each of these steps areAlterally optimal with respect to the Kullback-Leibler datasets.
  arXiv  Detail & Related papers  (2024-10-30T06:28:21Z)
• DeFoG: Discrete Flow Matching for Graph Generation [45.037260759871124]
  We propose DeFoG, a novel framework using discrete flow matching for graph generation. DeFoG employs a flow-based approach that features an efficient linear noising process and a flexible denoising process. We show that DeFoG achieves state-of-the-art results on synthetic and molecular datasets.
  arXiv  Detail & Related papers  (2024-10-05T18:52:54Z)
• AdjointDEIS: Efficient Gradients for Diffusion Models [2.0795007613453445]
  We show that continuous adjoint equations for diffusion SDEs actually simplify to a simple ODE. We also demonstrate the effectiveness of AdjointDEIS for guided generation with an adversarial attack in the form of the face morphing problem.
  arXiv  Detail & Related papers  (2024-05-23T19:51:33Z)
• Gaussian Mixture Solvers for Diffusion Models [84.83349474361204]
  We introduce a novel class of SDE-based solvers called GMS for diffusion models. Our solver outperforms numerous SDE-based solvers in terms of sample quality in image generation and stroke-based synthesis.
  arXiv  Detail & Related papers  (2023-11-02T02:05:38Z)
• Generalized Schrödinger Bridge Matching [54.171931505066]
  Generalized Schr"odinger Bridge (GSB) problem setup is prevalent in many scientific areas both within and without machine learning. We propose Generalized Schr"odinger Bridge Matching (GSBM), a new matching algorithm inspired by recent advances. We show that such a generalization can be cast as solving conditional optimal control, for which variational approximations can be used.
  arXiv  Detail & Related papers  (2023-10-03T17:42:11Z)
• Diffusion Schr\"odinger Bridge Matching [36.95088080680221]
  We introduce Iterative Markovian Fitting (IMF) and Diffusion Schr"odinger Bridge Matching (DSBM) IMF is a new methodology for solving SB problems, and DSBM is a novel numerical algorithm for computing IMF iterates. We demonstrate the performance of DSBM on a variety of problems.
  arXiv  Detail & Related papers  (2023-03-29T16:59:22Z)
• Optimization-Induced Graph Implicit Nonlinear Diffusion [64.39772634635273]
  We propose a new kind of graph convolution variants, called Graph Implicit Diffusion (GIND) GIND implicitly has access to infinite hops of neighbors while adaptively aggregating features with nonlinear diffusion to prevent over-smoothing. We show that the learned representation can be formalized as the minimizer of an explicit convex optimization objective.
  arXiv  Detail & Related papers  (2022-06-29T06:26:42Z)
• The Schr\"odinger Bridge between Gaussian Measures has a Closed Form [101.79851806388699]
  We focus on the dynamic formulation of OT, also known as the Schr"odinger bridge (SB) problem. In this paper, we provide closed-form expressions for SBs between Gaussian measures.
  arXiv  Detail & Related papers  (2022-02-11T15:59:01Z)
• Score-based Generative Modeling of Graphs via the System of Stochastic Differential Equations [57.15855198512551]
  We propose a novel score-based generative model for graphs with a continuous-time framework. We show that our method is able to generate molecules that lie close to the training distribution yet do not violate the chemical valency rule.
  arXiv  Detail & Related papers  (2022-02-05T08:21:04Z)
• Probabilistic Circuits for Variational Inference in Discrete Graphical Models [101.28528515775842]
  Inference in discrete graphical models with variational methods is difficult. Many sampling-based methods have been proposed for estimating Evidence Lower Bound (ELBO) We propose a new approach that leverages the tractability of probabilistic circuit models, such as Sum Product Networks (SPN) We show that selective-SPNs are suitable as an expressive variational distribution, and prove that when the log-density of the target model is aweighted the corresponding ELBO can be computed analytically.
  arXiv  Detail & Related papers  (2020-10-22T05:04:38Z)
• Targeted free energy estimation via learned mappings [66.20146549150475]
  Free energy perturbation (FEP) was proposed by Zwanzig more than six decades ago as a method to estimate free energy differences. FEP suffers from a severe limitation: the requirement of sufficient overlap between distributions. One strategy to mitigate this problem, called Targeted Free Energy Perturbation, uses a high-dimensional mapping in configuration space to increase overlap.
  arXiv  Detail & Related papers  (2020-02-12T11:10:00Z)

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.