First Hitting Diffusion Models for Generating Manifold, Graph and Categorical Data

Mao Ye, Lemeng Wu, qiang liu

Abstract

We propose a family of First Hitting Diffusion Models (FHDM), deep generative models that generate data with a diffusion process that terminates at a random first hitting time. This yields an extension of the standard fixed-time diffusion models that terminate at a pre-specified deterministic time. Although standard diffusion models are designed for continuous unconstrained data, FHDM is naturally designed to learn distributions on continuous as well as a range of discrete and structure domains.

Introduction

Standard diffusion models, such as Denoising Diffusion Probabilistic Models (DDPMs), have set benchmarks in generating continuous, unconstrained data like high-resolution images. However, these models face significant hurdles when applied to structured data. Specifically, they struggle with discrete domains (e.g., graphs, categorical text) and manifold-constrained data (e.g., coordinates on a sphere) without resorting to ad-hoc rounding or complex projection layers. Furthermore, standard models utilize a fixed computation budget for every sample, regardless of its complexity, leading to inefficiencies during inference.

Methodology: From Fixed-Time to First-Hitting

The core innovation of First Hitting Diffusion Models (FHDM) is the transition from a deterministic stopping time $T$ to a random "first hitting time."

First Hitting Processes

In FHDM, the diffusion process terminates the moment a particle reaches a predefined target domain $\Omega$. This geometric approach allows for a unified treatment of various data types:

  • Binary Data: The process stops upon hitting the boundaries of a Boolean hypercube (0 or 1).
  • Spherical Data: Termination occurs when the particle hits the surface of a unit sphere.
  • Categorical Data: The process hits the faces of a probability simplex.
Visualizing the transition from fixed-time diffusion (A) to first-hitting diffusion across different domains: spherical (B), Boolean (C), and categorical (D).

Training via Doob's h-transform

To train FHDM, the model must learn to simulate trajectories that exit the domain at specific training data points. The authors utilize Doob's h-transform to condition a base diffusion process to steer toward a target point $x$. A neural network is then trained to approximate the drift term of these conditioned processes, effectively learning the "score" required to guide noise toward the data distribution.

Fast Bridge Sampling

To overcome the computational cost of simulating conditioned SDEs during training, the authors exploit rotational symmetry. By pre-simulating unconditioned trajectories and rotating them to match the exit points of training data, they achieve a significant reduction in training overhead.

Experimental Results

FHDM was evaluated across diverse domains, demonstrating superior efficiency and quality.

Efficiency and Adaptive Computation

FHDM introduces adaptive computation, where "easier" components of a sample (like global contours in a segmentation map) reach their boundaries faster, allowing the model to focus remaining steps on complex details.

  • Graph Generation: FHDM requires ~100 steps on average, a 60x speedup over previous methods like EDP-GNN (6,000 steps).
  • Segmentation Maps: FHDM achieves generation in ~90 steps, compared to 4,000 steps for Multinomial Diffusion.

Performance Metrics

  • Graphs: Achieved a Maximum Mean Discrepancy (MMD) of 0.031, significantly outperforming the next best baseline (0.062).
  • Categorical Data: On the Cityscapes dataset, FHDM reached an Evidence Lower Bound (ELBO) of 0.066, a substantial improvement over Multinomial Diffusion (0.305).
  • Manifolds: FHDM yielded the best negative log-likelihood across multiple climate science datasets (earthquakes, floods, etc.) compared to Riemannian score-based models.

Conclusion

First Hitting Diffusion Models provide a mathematically elegant and unified framework for generative modeling across continuous and structured domains. By replacing fixed-time horizons with geometric boundaries, FHDM achieves state-of-the-art performance with drastically reduced inference times, paving the way for more efficient and versatile diffusion-based generation.

Summary updated

Abstract

We propose a family of First Hitting Diffusion Models (FHDM), deep generative models that generate data with a diffusion process that terminates at a random first hitting time. This yields an extension of the standard fixed-time diffusion models that terminate at a pre-specified deterministic time. Although standard diffusion models are designed for continuous unconstrained data, FHDM is naturally designed to learn distributions on continuous as well as a range of discrete and structure domains.
BibTeX
@inproceedings{ye2022first,
  author = {Mao Ye and Lemeng Wu and qiang liu},
  title = {{First Hitting Diffusion Models for Generating Manifold, Graph and Categorical Data}},
  booktitle = {SBM @ NeurIPS},
  year = {2022},
  url = {https://openreview.net/forum?id=uhAoWceUb5},
}
Figure