First Hitting Diffusion Models for Generating Manifold, Graph and Categorical Data
Authors: Mao Ye
Lemeng Wu
qiang liu
Venue: NeurIPS 2022 Accept (2022)
Keywords: diffusion model

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. Moreover, FHDM  enables instance-dependent terminate time and accelerates the diffusion process to sample higher quality data with fewer diffusion steps. Technically, we train FHDM by maximum likelihood estimation on diffusion trajectories augmented from observed data with conditional first hitting processes (i.e., bridge) derived based on Doob's $h$-transform, deviating from the commonly used time-reversal mechanism. 
We apply FHDM to generate data in various domains such as point cloud (general continuous distribution),  climate and geographical events on earth (continuous distribution on the sphere),  unweighted graphs (distribution of binary matrices), and segmentation maps of 2D images (high-dimensional categorical distribution). We observe considerable improvement compared with the state-of-the-art approaches in both quality and speed. 

First Hitting Diffusion Models for Generating Manifold, Graph and Categorical Data
Mao Ye," Lemeng Wu, Qiang Liu
Department of Computer Science The University of Texas Austin
Abstract
We propose a family of First Hitting Diffusion Models (FHDM), deep generative models that generate data with 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 natu- rally designed to learn distributions on continuous as well as range of discrete and structure domains. Moreover, FHDM enables instance-dependen terminate time and accelerates the diffusion process to sample higher quality data with fewer diffusion steps. Technically, we train FHDM by maximum likelihood estimation on diffusion trajectories augmented from observed data with conditional first hitting processes (i.e., bridge) derived based on Doob's ' h-transform, deviating from the commonly used time-reversal mechanism. We apply FHDM to generate data in various domains such as point cloud (general continuous distribution), climate and geographical events on earth (continuous distribution the sphere). unweighted graphs (distribution of binary matrices), and segmentation maps of 2D images (high-dimensional categorical distribution). We observe considerable improvement compared with the state-of offth---rttttttttt approaches in both quality and speed.
Introduction
Diffusion processes have become powerful tool in various areas of machine learning (ML. and statistics. Traditionally, Langevin dynamics and Hamiltonian Monte Carlo have been foundations for learning and sampling from graphical models and energy-based models. Recently, denoising diffusion probabilistic models (DDPM) [18] and score matching with Langevin dynamics (SMLD) with its variants [41 [41-43] have achieved the state-of-the- -ftr--arttttt results on data generation [13, 9, 30, 19].
Standard diffusion processes used in ML can be classified into two categories: 1) infinite (or mixing) time diffusion processes such as Langevin dynamics, which requires the process to run sufficiently long to converge to the invariant distribution, whose property is leveraged for the purpose of learning and inference; and 2) fixed time diffusion processes such as DDPM, SMLD, and Schrodinger bridges [11], which are designed to output the desirable results at a pre-fixed time. Although fixed-time diffusion has been show to surpass infinite time diffusion on both speed and quality, it still yield slow speed for modern applications due to the need of a pre-specified time and the incapability to adapt the time based the difficulty instances and problems. Moreover, standard diffusion models naturally designed on Rdd and can not work for discrete and structured data without special cares.
In this work, we study and explore different first hitting time diffusion model that terminates at the first time as it hits a given domain, and leverages the distribution of the exit location (known as exit distribution, harmonic measure [31]) as tool for learning and inference. We provide the
"onresponding author. Email: maoye21 @ (dutexas.edu
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

Time
Pre-fix time hit
Sphere hit
C: B.ooooaa hit
D: Categorical hit
Figure I: The four hitting schemes introduced in this paper. A: fixed-time hit, the process terminates fixed time; B: Sphere hit, hitting the boundary of a sphere from inside; C: Boolean hit, each coordinate terminates when it hits 0 or and the whole process terminates when all of its coordinates terminate; D: Categorical hit, hitting the one-hot codes based on conditioned process.
basic framework and tools for first hitting diffusion models. We leverage our framework to develop a general approach for learning deep generative models based first hitting diffusion. This approach generalizes SMLD and its SDE extensions but can be attractively applied to a range of discrete and structured domains. This contrasts with the standard diffusion models, which are restricted to continuous I data. In particular, we instantiate our framework to three cases, yielding new diffuusio models for learning 1) spherical, binary and 3) categorical data. In addition, the proposed diffusion model gives different instances adaptive arrival times and can generate high-quality samples using fewer diffusion steps. We discuss theoretical properties and fast implementation of our methods and demonstrate their practical efficiency in a suite of practical learning problems.
2 Main Framework
2.1 First Hitting Diffusion Processes
Let II" be distribution of interest domain Ω C Rd, The goal is to construct a first hitting stochastic process, which starts from a point outside of Ql and returns a sample drawn from II" when it first hits set Ω. We start with introducing the new first hitting model.
Let Z [Ze: t [0, }o0}} be a continuous-time Markov process with probability law Q taking value in a set V that contains Ω as subset. Here Q is a probability measure defined on the space of all continuous trajectories C(10, +oo), (R.). We use Q denote the marginal distribution of Z, at time t. We assume that the process is initialized from point Zu outside of Ω. Denote by r the first hitting time of Z, on S2, that is, r inf, (t 2 Z, 2). We call that Z, is absorbing to set
i) The process enters Ω in finite time almost surely when initialized from anywhere in V, that is, Q(T < +oo Zo 2)
Vz V.
ii) The process stops to move once it arrives at Ω that is, Q(Z++ = Z, 2, E 2) = 1,,
denoted by Qn | 2, 2) (Z, dx Z. 2). The marginal distribution of Z,, which we write (d(rr) = QZ- = dz), is called the exit distribution, or harmonic measure. Note that (dx) Jv Qn (dz Zo= (dz). The crux of our framework is to leverage the exit distribution Qa as tool for statistical learning and inference, which is different from traditional frameworks that exploit the properties of the distributions
We define the Poisson kernel of Q as the conditional distribution of Z, given Z:
fixed time or at convergence.
Example 2.1 (Sphere Hitting). As shown in Figure 1-B, let V {x E Rd: || S 1} be the unit ball and Ω = Sa == @V the unit sphere. Let Z be a Brownian motion starting from E V and stopped once it hits the boundary Q. It is writlen as
Q
dZ, 1(] < 1)dW, Zo
(1)
where W, is Wiener process; the indicator function I(I 2 < 1) sets the velocity to zero and hence stops the process once Z, hits Q. The Poisson kernel in this case is a textbook result:
1 - |
Sa (da Zi =)
ms(ld)) where μr is the surface measure on Ω = Sa-
(2)
||00 =|1

---

Example 2.2 (Boolean Hitting). As shown in Figure 1-C. let V = [0. be the unit cube and = Bg == (0. 10 the Boolean cube. Let Z be a Brownian motion starting from Zo E V and confined inside the cube V in the following way:
Ba,
1 = I E (0, 1) Vi 21,2. .d],
where Zt, is the i-th element of Z. Here, each coordinate Z stops to move once hits one of the end points (0 1). It can be viewed as a particle flying in room that sticks wall once it hits it.
Proposition 2.3. The Poisson kernel of Q Ba is a simple product of Bernoulli distributions:
Ba (x Zi 2) Ber(x]2) II Ber(2, where Ber(x.)2s) I424 + (1 2;) -2);:
Ber (z: (2)) is the likelihood function of observing 2, {0,1) under Bernoulli(z;) with 2, [0. 1]. Example 2.4 (Fixed Time Hitting). Our first hitting framework includes the more standard models with fixed terminal time. To see this, let Z. = (1, Zz) be a stochastic process Ze with law Q augmented with time as one of its coordinates. Let V [0, t] IR and S2 {t} x RR, where St is a vertical plane on the augmented space. Then the hitring time equals t deterministically, and the exit distribution equals the marginal distribution of Zy at time See Figure 1-A, for illustration.
2.2 Diffusion Process Tools: Conditioning and h-transform
We introduce some basic tools for diffusion processes, including how to conduct conditioning, and exponential tilting (via h-transform) diffusion processes. We apply these tools to the first hitting models we have. The readers can find related background in Oksendal [31], Särkkä and Solin [37].
Assume Z is general Ito diffusion process in V that is absorbed to Ω denoted as Iton (b,
Q (b)
dz, by Zz dt + or (Z.)dW, AI E [0, +oo),
Zo Co
(3)
where (z(z) E Rd the drift term and or (x) Rddd is a positive definite diffusion matrix. We always assume that b and are sufficiently regular yield unique weak solution of (3).
Conditioning step in our work is to find the distribution of the trajectories of a process Q conditioned on a future event, e.g., the event of hitting particular value at exit, that is, ( x). notable result that the conditioned diffusion processes are also diffusion processes. Given point E Ω on the exit surface, the process of Q(- Zr z) can be shown to be the law of the following diffusion process [14, 37]:
Q(-1, = x): d2: = (b. + (Z,) log (2 2.)) dt + (Z))ddWe Zo ~ Pojes (4) where (x 2) is the density function of the Poisson kernel Qn Z; = 2) w.r.t. reference measure μ on Ω2 and o² is the matrix square of a, and the conditional initial distribution Polz = Qo(: Z, = z) is the posterior probability of Zo given Z, = x.
Intuitively, the additional drift term Vz, log (2 Z.) plays the role of steering the process towards the target x, with increasing magnitude as Z, approaches Ω (because Pa Z, 2) converges to a delta measure centered at x when = approaches 22). This process is known as a diffusion bridge, because it is guaranteed to achieve Z, at the first hitting time with probability one.
Proposition 2.5. For SAA the process conditioned on 7 = x E Sa at exit is
- |Z,11 dt + dW,
S Z. =r :):
dz: = -<[1 <
2. log
(5)
|| [
Here the additional drift term (colored in blue) grows to infinity if ||//|| and hence enforces that Z, = x when we exit the unit ball. Proposition 2.6. For Ba, the process conditioned Z, {0, 1)dd at exit is
1 but 11, x|| is large,
Q B (-11, x) aZ,, I(Zi, E (0.
2444 + (1 2.)(1 24) dt + +Wiss Vi. (6)
2x; -
The additional drift term (colored in blue) enforces that Zr, = Di at the exit time as the drift would be infinite if 24 is still far from D; when is close to {0, 1).
3

---

Proposition 2.7. For the fixed time diffiusion in Example 2.4, let Q² be the standard Brownian motion
dz, dW, stopped at fixed time t T, then Q conditioned on Q3" (Z) z) is
Z T - dt + +dW,) dz = T(L T))
Q' =x):
(7)
The additional drift (colored in blue) forces Zr as it grows to infinity if Z + z while + T.
h- h-Transform Assume we want to modify the Markov process Z such that its exit distribution Qn
matches the desirable target distribution II". Doob's h-transform [14] provides simple general procedure to do so. Note that by disintegration theorem, we have Q(dZ) ) = (o(d)) 2r
r). which factorizes Q into the product of the exit distribution and the conditional process given
fixed exit location Zr = x. To modify the exit distribution of Q to II", we can simply replace Qo with II in the disintegration theorem, yielding
QTh (dz) (T((d)== = II (d=))(((Z / Z, xx n' (Z.))(Z)) with (Z,)
d1I dQn
(Zr),
(8)
where π- an is the Radon-Nikodym derivative (or density ratio) between II" and Co. and Q called an h-transform of Q. Intuitively, QJ' the distribution trajectories when the exit location is randomly drawn from II.. We can also view x² (Z,) an importance score of each trajectory Z based on its terminal state Z., and Q"" is obtained by reweighing (or tilting) the probability of each trajectory based on its score.
dQu
Q x)
If is diffusion process, then Q is also a diffusion process. In addition, Q" is the law of the following diffusion process:
QJI
dZ: (bi(Z,) + of of Log h!t (Z.) dt (Z()d,, Zo Qf
(9)
where the initial distribution Of"" and h TI" in the drift term are defined as
Q!' (dz) (dz(d)== = 111 (z(x)((Zr = dx, Zo -d)
(10)
h (z) = EalT" (Z+) Z, = 2] = / (x)Q(Zz = dr Ze = 2).
(11)
It is clear that / coincides with n" on the boundary, that is, 11 (x, () = ग (x) for all x E 22 / 0. The name of h-transform comes from the fact that lT is (prace-time) harmonic function w.r.t. Q (Ze+.) in the light of a mean value property: N. (z) (o Z = 2], Vs, > O. Q yields
simple variational representation in terms of Kullback-Leibi (KL) divergence.
Proposition 2.8 (Variational Principle). The Q" (8) yields
QT arg min PEP(V.))
KC((P [1Q) = E, 1E> log dP (Z) dQ
s.l. Pa P1=I1' {
(12)
II KCP( (1 Ez x (2+)1]
arg min PEP(V.)
(13)
where P(V, 2. denotes the set path measures on that absorbed to Q
Eq. (12) shows that TT is the distribution with II as the exit distribution that has the minimum KL divergence with Q. It can be viewed as Schrodinger half bridge problem [e.g., 32], which enforces the constraint of PP = IT* at a fixed time T. rather than the first hitting time 7. Eq. (13) shows that the constraint can be turned into penalty.
First Hitting Diffusion for Sampling The h-transform above readily provides first hitting diffusion approach to approximate sampling from II", assuming we can approximate the drift term n,"", The Schrodinger-Folli sampler [20] can be viewed special case of this approach with fixed exit time. We leave further exploration to future works. See more discussion in Appendix A.3.

---

NN(Z) di Approximate
Training set
b b dt
dW,
Z
Zo
Terminate when hits the domain
Simulate Conditioned SDE by h-transform
Figure 2: The training pipeline of FHDM. Start from initial distribution, conditioned SDE such that the process terminates at the desired destination data from training set its hitting time. The network is trained approximate the drift term (6(Z.)). resulting score- more-matching loss that equivalent to the KL divergence.
h-transform to simulate
Algorithm Learning Generative Models by First Hitting Diffusion
Inputs & Goal: A data It := {xx() drawn from II f2 A baseline process Q and model p that are absorbing to Ω. Want to find 0 such that Pe II", Training: Approximate 0 arg ming [()) by stochastic gradient descent with batches of data (approximately) drawn Z ( Zr = x) and fl. Inference: Simulate ToO.
2.3 Learning First Hitting Diffusion Models
We illustrate the learning pipeline of our First Hitting Diffusion Models (FHDM) in Figure 2. Assume II is unknown and we observe through i..d sample (z(0) Ji=1 drawn from II" We want to fit the data with parametric diffusion process Itog(se, o)) in V that is absorbing to ? po:
dz, = i (Z.)dt + or (Z))dW,,
Zo ~ P
(14)
such that the exit distribution Pa matches the unknown II", Here (e) is a deep neural network with input (z, t) and parameters 9. We should design s" and a properly ensure the absorbing property. The standard approach to estimate II is maximum likelihood estimation, which can be viewed as approximately solving ming KC((II* (.). However, calculating the likelihood of the exit distribution 1od of general diffusion process computationally intractable. To address this problem, we fix Q as "prior" process, and augment the data distribution II" to the h-transformm Q whose exit distribution Q matches II by definition. Note that we can draw i..d. sample from Q"" in "backward" way: first drawing exit location x ~ IT from the data, and then draw the trajectory Z from Q Z, = 2) with the fixed exit point. To train generative model, we train p to fit with the data drawn from Q by maximum likelihood estimation:
min (((0))=K00)
|| IP") = -EEzan [logr' (Z)] + const, }
d where p" -Q is Radon-Nikodym density function of pd relative to TT" By the chain rule of
KL divergence in (20) in Appendix A.9, we have XCC(1I* || IPh) s KCCQ" || P(). Therefore, if minimizing the KL divergence allows us to achieve Fd ~ Q"" we should also have I = Q = II".
Using Girsanov theorem [24], we can calculate the density function pd and hence the loss function. Proposition 2.9. Assume in (3), and Ipo in (14) are absorbing Ω. We have
(()) = - Egg 1/ (1
by Ze 2 dt log p (2)) + const,
(15)
where be(2|z)= b() + (z)V (4), and phe the probability density function of the initial distribution T. addition, H" achieves the global minimum of L(0) if
log (2)) the drift of the conditioned process Q(-1Z, = x)
6r St (z) (Zz-gn((6((2ZZn)) Ze 2).
P
=Q0 -E-HI- (.)(.)
5

---

Therefore, the optimal drift term sf should match the conditional expectation of (z(2(a) with Q2 =), which coincides with the drift of Q" in (9). The initial distribution of TP should obviously match the initial distribution of QT In practice, we recommend eliminating the need of estimating pe by starting Q from a deterministic point Zo = 20, in which case pd should initialize from the same deterministic point. See Algorithm I.
Learning Spherical Hitting Models Take Q = Q in Example 2.1, we get a method for learning generative models for data on the unit sphere. We set the model to be dZ, T(|) Z ll < (Z.)) dW,) to ensure that is absorbing to Sa. The loss function
1
6 [e((z)) - Vz, , log B. 2-111
1 - |
[())
dt log (Zo)
+ const.
Z-22"
| 1
Learning Boolean Hitting Models Taking Q QBa as in Example 2.2 provides an approach to learning diffusion generative models for binary variables. We set the model Ip to be dZ,- = II E (0, 1)) ( (f)dt + dW,) to ensure that Too is absorbing to Ba like Q²,, where denotes element-wise multiplication. The loss function
/ (() = 2 2-
1
B B
|[ (0) (J2 Zz log Ber [[1))]| dt log pi((z) const.
Learning Fixed Time Diffusion Models Following the fixed time setting Example 2.4, we can recover the standard fixed time diffusion models for continuous data, such as SMLD and DDPM. In particular, a natural choice is to set Q to an O-U process dZ, a, a,Zd + a,dW, initialized from Zo (0, vo) where o, 2 0, vo > O. We show in Appendix A.4 that SMLD (a: 0) and DDPM (at > 0) is recovered as the limit case when Up + +00.
2.3.1 Learning Categorical Generative Models
In addition to the boolean hitting model, we provide here first hitting framework for learning cate- gorical data. In this case, the data domain is Ca. = {ei,...,, ea]"", where e; = [O...... I, ............ .]]
the i-th one-hot (or basis) vector in I&d so the data a m-dimensional and d'categorical.
It is less straightforward to construct a first hitting diffusion process that is absorbing to Ca.m- We leverage the conditioning technique to achieve this. We explain the idea with m = 1. of which the general case is a direct product. The key observation is that the one-hot vectors Ca,1 is subset of the boolean cube B₁ = {0, 1)d. Hence, by definition, the conditioned process QCa.. = Q Bu (- E Ca,1) exits at Ca,1 from the inside of Ba. Using the method of h-transforms [14, 371, @ = Q Ba (. 12) for any Q c Bg is the law of
dz. 11 E (0, 1)) o (V log Ber(S) 2, dt + dW,),
Ber(S) (er(s)2) 2) = Eere | 2).
Another challenge is to construct parametric family of PP that is absorbing to Ca,m. regardless of the value of f The result below shows that this can be done by simply adding on top of Q any bounded neural network drift term.
Proposition 2.10. Let V 1]d and Q is any subset of Ba {0, 1.. Assume (2) is any bounded measurable function. Then the following process is guaranteed to hit Q when exits V:
dz,- T(Z, E (0, o (J (Z+) V. log Ber(S) Z,)dt + aw.), Zo E 1)..
See Appendix A. for the summary of the algorithm for learning categorical data.
2.3.2 Fast Sampling of Bridges
One main step in calculating the loss L(0) is draw trajectory Z from the bridge Q= Q(- Z, x). This can be achieved by simulating the bridge processes using Mulrr-Maruyama method. This not computationally costly because it the simulation of elementary SDEs and does not involve deep neural networks. However, it does cause a slow down in the training algorithm if the data x is very high dimensional and the data size is very large.

---

To speed up the training, we propose a fast algorithm for sim- ulating bridges by exploiting the symmetry when we initialize from a point 2g (e.g., the center of sphere) around which Q and Q are rotational symmetric. The idea is simple: we simulate the unconditioned process Q to get trajectory Z that exits at any point. Then, to obtain the conditional process Q(-IZ, = x), we simply rotate the trajectory Z such that the exit point Z, is transformed from the original one to x. An advantage is that we can pre-simulate large number of trajectories before training and only need to apply the rotation operator to get specific conditioned processes during training. Figure 3 gives an illustration using the example of sphere hit. The idea can he applied similarly for other types of hitting.
Rotate
Desired Exit
Point To sample conditioned process, we can pick up a trajectory of unconditioned process and rotate it so that it exits at given point.
Figure 3:
Proposition 2.11. Assume Z with law Q initialized from 20 E Rd is absorbing to Ω. For x' E Ω2 let rotz'=a be the rotation operator around 20 that transforms x' (hence rotz'=a (x') = x). Assume that Q and QQ are rotation invariant around zo in that rota', i (S)) 52 and rotz', (Z) ~ Q when Z ~ Q for any x' x E Q. Then if Z ~ Q we get Z' = rotz, - Z), a sample from Q2, = z).
Such fast sampling approach applicable for all the categorical, sphere and binary distributions.
2.4 Discretization Error
In practice, the Guler-Maruyane method is applied to discretize the process. Analyzing the dis- cretization error of a random hitting process is more difficult than that of a fixed-time process. In a fixed-time process, both discretized and continuous processes terminate at the same time, making the coupling tricks applicable for analyzing the discretization error based on the Eg Wasserstein distance. Standard analysis under Lipschitz continuity assumption of the drifts gives ((A) error rate where A is the discretization step size [37]. In comparison, the key challenge of analyzing the FHDM is that the discretized and continuous processes may not terminate the same time, and thus we need to bound the probability of the difference of the hitting time distribution in the analysis. Besides, in practice, we might also apply some time truncation tricks in order to have a bounded waiting time for generating. In Appendix A.8, we provide a full analysis and show that FHDM also yields O(A) discretization error asymptotically.
Related Work
Diffusion Generative Model on Different Domains Diffusion generative model has been demon- strated to be powerful in generation of general continuous data such as image [40, 41, 18, 42, 43, 13], point cloud shape [7, 26, 49] and audio [9, 22]. Recently, diffusion generative model has also been extended learn to generate data on special domains such graph [30], segmentation map [19], text [19] and manifold data [12]. Such a generalization of diffusion model is usually case-by-case and is based on applying constraints to ensure the data remains in the desired domain during the diffusion process [19, 12] or use heuristic approximation to round the data into the discrete space [30]. Our FHDM gives a unified framework for generating data on special domain via a completely new mechanism of first hitting.
Theoretical Framework on Diffusion Process Most existing diffusion models are based on the framework of time-reversing [43] in which the generation (i.c. denoising) process is learned based on its time-reversed stochastic differential equation trajectory that can be simulated easily, ignoring the mismatch of the initial distribution. In comparison, our framework is conceptually simpler and is only based on forward process, in which the learning based on conditioned stochastic differential equations (i.e.. bridge) that can be simulated via h-trranffrmm. A similar framework is independently explored in [34] but our method more general and exploits the idea of first hitting. Schrodinger bridges is an another well studied framework of diffusion model [46, 34, 10]. However, using Schrodinger bridges usually require expensive forward-backwand algorithms. It is also unknown whether or how Schrodinger bridges can be applied for generating data in special domains.
7

---

Airplane
Chair
Model
MMD
COVT
I-NNA!
JSD[
MMD
COV1
I-NNA,
JSD.
PC-GAN [1]
3.819
42.17
77.59
6.188
13.436
46.23
69.67
6.649
GCN-GAN [45]
4.713
39.04
89.13
6,669
15.354
39.84
77.86
21.71
Tree-GAN [38]
4.323
39.37
83.86
15.646
14.936
38.02
74.92
13.28
PointFLow [47]
3,688
44.98
66.39
1.536
13.631
41.86
66.13
12,47
ShapeGF [7]
3.306
50.41
61.94
1.059
13.175
48.53
56.17
5.996
DPM[26]
3,276
48.71
64.83
1.067
12.276
48.94
60.11
7.797
Ours
3.350
50.41
67.21
0.986
6.644
49.50
56.87
5.913
Table 1: Result of point cloud generation experiment. Bolded value indicates the best performance method.
We adopt the base line from Luo and Hu [26].
4 Experiments
We applied FHDM to distributions various domains such point cloud (general continuous distribution), distribution of climate and geography events on earth (continuous distribution on the sphere), unweighted graphs (distribution of binary matrices), and segmentation map of 2D image (high dimension categorical distribution). We demonstrate that
1. As generalization of the fixed-time processes such as DDPM, the fixed-time scheme of FHDM a generative model of higher quality for general continuous distribution (section 4.
2. As versatile model, FHDM is able to learn the distribution in many different domains and it outperforms existing specifically designed generative models (see section 4.1).
3. The hitting time of FHDM is bell-bounded and in several tasks, FHDM even requires much fewer diffusion steps than existing methods while generating higher quality samples (see section 4.2).
Besides, we also conduct experiments to understand the intuition of the first time hitting mechanism (section 4.2) and demonstrate the acceleration of the fast sampling approach introduced in Section 2.3.2 (see in Appendix A.6). We include the visualization of the generated samples in Appendix A.7. Please find the code at https://// //g thub com
www..oommmmllll..ee weaf ffrsttrrt.ttt///ee wataaafffrssstttteeteeeeeeaaeeee wiwtingttiiii...i........ diffusion.
4.1 Generation Experiment
Point Cloud Generation Following Luo and Hu [26]. we employ the ShapeNet dataset [8] to evaluate the generated point cloud. We compare our approach against several the state-of-the-
art generative models including PC-GAN [1], GCN-GAN [45], Tree-GAN [38], PointFlow [47], ShapeGF [7] and DPM [26]. See Appendix A.5 for training details. Following Cai et al. [7], Luo and Hu [26]. use minimum matching distance (MMD) and the coverage score (COV) paired with Chamfer distance as well as I-NN classifier accuracy and the
divergence (JSD) to evaluate the quality of the generated point cloud. We refer readers to Appendix A.5 for more details on the metrics. Same to Cai et al. [7]. Luo and Hu [26]. we evaluate the quality on two categories, Airplane and Chair and the generated and reference point clouds are normalized into bounding box of [-1, 1]3 at evaluation. Table summarizes the results showing that FHDM achieves the best performance most criterion.
Generating Distribution on Sphere We apply FHDM to generate distribution of occurrences of earth and climate science events on the surface of earth (which is approximated perfect sphere). Following De Bortoli et al. [12], we consider 4 datasets: volcanic cruption [29], earthquakes [28], floods [5] and wild fires [15]. We compared FHDM against the current the state-of-the-ar baselines including Riemannian Continuous Normalizing Flows [27], Moser Flows [36], mixture of Kent distributions [33] and standard Score-Based Generative model on 2D plane followed by the inverse stereographic projection (Stereographic Score- -aared [16] and Riemannian Generative Model [12]. Same De Bortoli et [12], we evaluate the method via the negative log-likelihood on the test set. We run our method for 5 independent trials and report the averaged metric with its standard deviation. We directly adopt the baseline result from De Bortoli al. [12]. Table summarizes the result. See Appendix A.5 for additional details.
8

---

Volcano
Earthquake
Flood
Fire
Mixture of Kent [33]
0.80 + 0.47
0.33 + 0.05
0.73 + 0.07
-1.18 0.06
Riemannian CNF [27]
0.977 0.15
0.90
0.05
Moser Flow [36]
-2.0 + 0.42
-0.09
0.00
-1.03
Stereographic Score-based [16]
-4.18 + 0.30
-0.04
1.16
0.28 0.20
Riemannian Score-based [ [12]
5.56 + 0.26
-
0.52 0.02
-1.24 + 0.07
Ours
1.25 + 0.18
-0.27 0.02
0.29 0.03
-1.24 = 0.08
Table 2: Result on generating distribution of occurrences of earth and climate science events on the
surface of earth. Bolded value indicates the best method.
Community
Ego-small
Method
Avg.
Deg.
Clus.
Orbit.
Avg.
Deg.
Clus.
Orbit.
Avg.
GraphVAE [39]
0.350
0.980
0.540
0.623
0.130
0.170
0.050
0.117
0.370
DeepGMG [23]
0.220
0.950
0.400
0.523
0.040
0.100
0.020
0.053
0.288
GraphRNN [48]
0.080
0.120
0.040
0.080
0.090
0.220
0.003
0.104
0.092
GNF [25]
0.200
0,200
0.110
0.170
0.030
0.100
0.001
0.044
0.107
EDP- 33
0.053
0.144
0.026
0.074
0.052
0.093
0.007
0.050
0.062
Ours
0.009
0.105
0.009
0.041
0.019
0.040
0.005
0.021
0.031
Table 3: Result graph generation experiment. We report the averaged performance of our approach
based on 5 independent runs, giving 0.0013 standard deviation of the averaged metric. The results of the other baselines are directly adopted from Niu et al. [30]. Bolded value indicates the best method.
Graph Generation We apply FHDM to generate (unweighted) graph that can be represented using binary adjacency matrix. Following the experiment setup in You et al. [48], Liu al. [25], Niu et al. [30], we compare methods on two widely used benchmark datasets, Community-sin -mall and Ego-small, We apply the EDP-GNN [30] that preserves the node permutation invariance approximate the drift. We compare FHDM against GraphRNN [48], GNF [25], Graph VAE [39] and DeepGMG [23]. The maximum mean discrepancy (MMD) over three graph statistics (1. degree distribution; 2. cluster coefficient distribution; 3. the number of orbits with 4 nodes) proposed by You et al. [48] is used to evaluate the quality of the generative graphs. For our approach, we run independent trails and report the averaged performance. See Appendix A.5 for additional training details. Table 3 summarizes the result, suggesting considerable improvement over the baselines.
VAE
Method
ELBO
IWBO
Segmentation Map Generation FHDM
Round / Unif [44]
1,010
0.930
can also be applied to generate high dimen- sional categorical distribution such as the seg- mentation map of 2D image. Following Hoogeboom et al. [19], we aim to learn a model to generate the segmentation map of cityscapes dataset, in which the value of each pixel represents the category of the object that pixel belongs to. Following the setup in Hoogeboom al. [19], there are in total 8 categories and the value at each pixel is coded using one-hot vector. We compare our
Round / Var [17]
0.334
0.315
Argmax / Softplus thres. [19]
0.303
0.290
Argmax / Gumbel dist. [19]
0.365
0.341
Argmax / Gumbel thres. [19]
0.307
0.287
Multinomial Diffusion [19]
0.305
Ours
0.066
0.065
Table 4: Result for segmentation map generation. We our method for independent runs and report the averaged performance. FHDM gives 0,003/0.006 standard deviation of ELBO/WBB.
approach with uniform dequantization [44], variational dequantization [17], three variants of argmax flow [19] and multinomial diffusion [19]. Following Hoogeboom et [19], we evaluate the quality of generative model by evidence lower bound (ELBO) and importance weighted bound (IWBO) [6] (when it is available) with 1000 samples measured bits per pixel. For our method, we run independent trials and report the averaged metric and its standard deviation. The other baselines are directly adopted from Hoogeboom et [19]. The result summarized in Table See Appendix
A.5 for additional details.

---

Rounded Pixel
Hit Pixel
Only
10
20
50
60
80
100 Diffusion Steps
Figure 4: The trajectory of generating a segmentation map image. The upper row shows the image where the category of all pixels decided based on the argmax (i.c., rounding) of all the 8 scores. The lower row only plots the hit pixels of the snapshots.
4.2 Analysis
Hitting time distribution We study the hitting time distribution given by the optimized network, which is summarized in Figure 5. Our first hitting diffusion model is able to hit the domain in well-bounded time. It is worth remarking that for Boolean and categorical distribution, FHDM generates higher quality samples with much fewer diffusion steps. For example, in graph generation, FHDM on average takes about 100 steps while the previous approach such as Niu et [30] requires 6K steps. Similarly, in segmentation map generation, FHDM takes about 90 steps on average while the multinomial diffusion [19] needs 4K steps. Decreasing the number of diffusion steps those approaches will degenerate the performance. For example, if we only use 120 diffusion steps in Niu al. [30] the averaged performance becomes 0.306 which much worse. See Appendix A.6 for detailed result.
Community
Feeo
Why we can stop at hitting time The key feature of FHDM that stop the diffusion when hits the domain rather than keep it running for a pre-fixed time. We explore more the intuition behind such a process. In figure we visualize the trajectory of generating segmentation map. By looking at the image snapshot in the upper row where the value of each pixel decided by the argmax (i.e. rounding) of the 8 scores, we observe that the global contour of the image is already determined at a very early time (i.e., step 20) while the refinement of local details is almost finished at step 50. Our first hitting model exploits such property to stop the diffusion the hit pixels that the model has enough confidence about its value making generating process the rest pixels easier.
Crysscope
Earthquzek
Figure 5: Hitting time distri- butions for different data dis- tributions.
Conclusion
We propose the first hitting diffusion model (FHDM), which generalizes the fixed-time diffusion pro- cess and allows instance- deeendeed adaptive diffusion steps. Leveraging the idea of exit distribution, FHDM provides an unified framework for learning distribution in various special domains. Despite the good functionality, FHDM takes slightly larger training overhead, which is partially solved by the our fast sampling tricks.
6 Acknowledge
The research was conducted in both the statistical learning and AI group (SLAD) led by Qiang Liu at UT Austin. SLAI research supported part by CAREER- 1846421, SenSE-2037267, EAGER- 2041327, and Office of Navy Research, and NSF Al Institute for Foundations of Machine Learning (IFML).
Societal Impacts
The proposed first hitting diffusion model able to generate data in various of domains and thus might be maliciously used to generate fake data such images videos, which might cause negative
10

---

socictal impact or even crime. Unfortunately, this paper is not able to provide technique to prevent such abuse as it the main focus of the paper. The theoretical foundation itself does not cause negative societal impacts, to the best of our knowledge.
References
[1] Panos Achlioptas. Olga Diamanti, Ioannis Mitliagkas, and Leonidas Guibas. Learning repre- sentations and generative models for 3d point clouds. In International conference on machine learning, pages 40-49, PMLR, 2018.
[2] Brian DO Anderson. Reverse-time diffusion equation models. Stochastic Processes and their Applications, 12(3):313-2 1982.
[3] Andrei N Borodin and Paavo Salminen. Handbook of Brownian motion-facts and formulae. Springer Science Business Media, 2015.
[4] Bruno Bouchard, Stefan Geiss, and Emmanuel Gobet. First time exit of continuous itô process: General moment estimates and (--convergence rate for discrete time approximations. Bernoulli, 23(3):1631-1662, 2017.
[5] G. Brakenridge. Global active archive of large flood events. 2017. URL http:// floodosservaoory.ollloooo wow.avaaaaoooooooooooooooooooooe edu/ htt///rccvvvveeereeeeeeeeeeeeeee html.
[6] Yuri Burda, Roger Grosse, and Ruslan Salakhutdinov. Importance weighted autoencoders. arXiv preprint arXiv: 1509.00599 2015.
[7] Ruojin Cai, Guandao Yang, Hadar Averbuch-Elor Zekun Hao, Serge Belongie, Noah Snavely, and Bharath Hariharam. Learning gradient fields for shape generation. European Conference on Computer Vision, pages 364-381. Springer, 2020.
[8] Angel X Chang, Thomas Funkhouser, Leonidas Guibas, Pat Hanrahan, Qixing Huang, Zimo Li, Silvio Savarese, Manolis Savva, Shuran Song, Hao Su, et al. Shapenet: An information-rice 3d model repository. arXiv preprint 1013:v:512.03000 2015.
[9] Nanxin Chen, Yu Zhang, Heiga Zen, Ron Weiss, Mohammad Norouzi, and William Chan. Wavegrad: Estimating gradients for waveform generation. arXiv preprint 0rXiv:2009.00713 2020.
[10] Tianrong Chen, Guan-Horng Liu, and Evangelos A Theodorou. Likelihood training of schr\"" odinger bridge using forward-basd backwrd sdes theory. arXiv preprint 10 2021.
[11] Valentin De Bortoli, James Thorton,, Jeremy Heng, and Arnaud Doucet. Diffusion schrödinger bridge with applications to score-based generative modeling. Advances in Neural Information Processing Systems, 34, 2021.
[12] Valentin De Bortoli, Emile Mathieu, Michael Hutchinson, James Thorton,, Yee Whye Teh, and Arnaud Doucet. Riemannian cosee generative modeling, arXiv preprint arXiv:2202.02763. 2022.
[13] Prafulla Dhariwal and Alexander Nichol. Diffusion models beat gans on image synthesis. Advances in Neural Information Processing Systems, 34, 2021.
[14] Joseph L Doob and JI Doob. Classical potential theory and its probabilistic counterpart, volume 549. Springer, 1984.
[15] EOSDIS. Land, atmosphere near real-time capability for eos (lance) system operated by nasa's earth science data and information system (esdis). 2020. URL attps://////a nasa. nov/earth- observation data/near wataa//narreeeeeeee telettime//feeeee salmm//firmm//ativeeee fire-data.
[16] Mevlana Gemici, Danilo Rezende, and Shakir Mohamed. Normalizing flows on riemannian manifolds, arXiv preprint 1.11v:1611.02344, 2016.

---

[17] Jonathan Ho. Xi Chen, Aravind Srinivas, Yan Duan, and Pieter Abbeel. Flow++: Improving flow-based generative models with variational dequantization and architecture design. In International Conference on Machine Learning, pages 2722-2730. PMLR, 2019.
[18] Jonathan Ho, Ajay Jain, and Pieter Abbeel. Denoising diffusion probabilistic models. Advances in Neural Information Processing Systems, 33:6840 6851, 2020.
[19] Emiel Hoogeboom, Didrik Nielsen, Priyank Jaini, Patrick Forré, and Max Welling, Argmax flows and multinomial diffusion: Learning categorical distributions. Advances in Neural Information Processing Systems, 34, 2021.
[20] Jian Huang, Yuling Jiao, Lican Kang, Xu Liao, Jin Liu, and Yanyan Liu. Schrödinggr-föllmer sampler: Sampling without ergodicity. arXiv preprint arXiv:2106. 10880, 2021.
[21] Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6980, 2014.
[22] Zhifeng Kong, Wei Ping, Jiaji Huang, Kexin Zhao, and Bryan Catanzaro. Diffwave: A versatile diffusion model for audio synthesis. In International Conference on Learning Representations, 2020.
[23] Yujia Li, Oriol Vinyals, Chris Dyer, Razvan Pascanu, and Peter Battaglia. Learning deep generative models of graphs. arXiv preprint arXiv:1803.0333 2018.
[24] Robert Shevilevich Liptser and Al'bert Nikolaevich Shiriaev. Statistics of random processes: General theory, volume 394. Springer, 1977.
[25] Jenny Liu, Aviral Kumar, Jimmy Ba, Jamie Kiros, and Kevin Swersky. Graph normalizing flows. Advances in Neural Information Processing Systems, 32, 2019.
[26] Shitong Luo and Wei Hu. Diffusion probabilistic models for 3d point cloud generation. In Proceedings of the IEEE/CVF Conference Computer Vision and Pattern Recognition, pages 2021.
[27] Emile Mathicu and Maximilian Nickel. Riemannian continuous normalizing flows. Advances Neural Information Processing Systems, 33:2503-2515, 2020.
[28] NGDC/WDS.
Ncei/wds global significant carthquake database.
URL https:
//www. ncei noaa. http://////aaaaaa/////////////// ngdc.mgg mgg. saazards:001215:
page/bin//so7id-gon .ow........a.................... noaa.
[29] NGDC/WDS. Neei/wds global significant volcanic eruptions database.
URL
www.::nneeii..aag..o.oomm. gov noaa. ngdc. mgg.cc..g...o. hazards
https://ww http://www.nei...ooomee/ noaa. htt.:////ccccss/eaaaataaaaaa///a http://aaaaaaaaanaaa////////aaaa
[30] Chenhao Niu, Yang Song, Jiaming Song, Shengjia Zhao, Aditya Grover, and Stefano Ermon.
Permutation invariant graph generation via score-based generative modeling. In International Conference Artificial Intelligence and Statistics, pages 4474-4484 PMLR, 2020.
[31] Bernt Oksendal. Stochastic differential equations: an introduction with applications. Springer Science & Business Media, 2013.
[32] Michele Pavon, Giulio Trigila, and Esteban G Tabak. The data-driven schrödinger bridge. Communications Pure and Applied Mathematics, 74(7):1545 1573, 2021.
[33] David Peel, William Whiten, and Geoffrey McLachlan. Fitting mixtures kent distributions to aid in joint set identification. Journal of the American Statistical Association, 96(453):56-66 2001.
[34] Stefano Peluchetti. Non-denoising forward-time diffusions. 2021.
[35] Olaf Ronneberger, Philipp Fischer, and Thomas Brox. U-net: Convolutional networks for biomedical image segmentation. In International Conference on Medical image computing and computer-assisted intervention, pages 234-241. Springer, 2015.
12

---

[36] Noam Rozen, Aditya Grover, Maximilian Nickel, and Yaron Lipman. Moser flow: Divergence- based generative modeling on manifolds. Advances in Neural Information Processing Systems, 34, 2021.
[37] Simo Särkkä and Arno Solin. Applied stochastic differential equations, volume 10. Cambridge University Press, 2019.
[38] Dong Wook Shu, Sung Woo Park, and Junseok Kwon. 3d point cloud generative adversar- ial network based tree structured graph convolutions. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 3859-3868, 2019.
[39] Martin Simonovsky and Nikos Komodakis. Graphvae: Towards generation of small graphs using variational autoencoders. In International conference on artificial neural networks, pages 412 422. Springer, 2018.
[40] Jascha Sohl-Dickstein, Eric Weiss, Niru Maheswaranathan, and Surya Ganguli. Deep unsuper- vised learning using nonequilibrium thermodynamics. International Conference on Machine Learning, pages 2256-2265. PMLR, 2015.
[41] Yang Song and Stefano Ermon. Generative modeling by estimating gradients of the data distribution. Advances in Neural Information Processing Systems, 32, 2019.
[42] Yang Song and Stefano Ermon. Improved techniques for training score-based based generative models. Advances neural information processing systems, 33: 13:11238-12443 2020.
[43] Yang Song, Jascha Sohl-Dickstein, Diederik P Kingma, Abhishek Kumar, Stefano Ermon, and Ben Poole. Score- score-based generative modeling through stochastic differential equations. In International Conference on Learning Representations, 2020.
[44] Benigno Uria, lain Murray, and Hugo Larochelle. Rnade: density-estimator. Advances in Neural Information Processing Systems, 26, 2013.
The real-valued neural autoregressive
[45] Diego Valsesia, Giulia Fracastoro, and Enrico Magli. Learning localized generative models for 3d point clouds via graph convolution. In International conference on learning representations, 2018.
[46] Gefei Wang, Yuling Jiao, Qian Xu, Yang Wang, and Can Yang. Deep generative learning via schrödinger bridge. In International Conference on Machine Learning, pages 10794-10804. PMLR, 2021.
[47] Guandao Yang, Xun Huang, Zekun Hao, Ming- Yu Liu, Serge Belongie, and Bharath Hariharan. Pointflow: 3d point cloud generation with continuous normalizing flows. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 4541-4550, 2019.
[48] Jiaxuan You, Rex Ying, Xiang Ren, William Hamilton, and Jure Leskovec. Graphrun: Generat- ing realistic graphs with deep auto-regressive models. In International conference machine learning, pages
PMLR, 2018.
[49] Linqi Zhou, Yilun Du, and Jiajun Wu. 3d shape generation and completion through point-voxel diffusion. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 5826-5835, 2021.
13


Reviews:
[{"review_id": "mExiR9uKMZc", "reviewer": "Reviewer_FUwB", "summary": "The authors propose a generative model based on the simulation of SDEs that terminate at random hitting times.\n\nSection 2 introduces the relevant background for first hitting diffusion processes, providing some simple examples like hitting of the sphere or the hyperbox. Then it exposes the conditioning principle and the h-transform, that can be used to derive the law of diffusions conditioned on hitting events/times. Section 2.3 explains how to fit a parametric SDE to learn a first hitting diffusion process with the desider exit distribution (eq 12). The authors also include interesting comments on the generation of categorical data and cheap pre-simulation of certain trajectories.\nSection 3 is composed by two paragraphs that position the proposed method w.r.t the literature.\nSection 4 presents compelling numerical results on various domains, like sphere, graphs and segmentation generation. To the best of my knowledge the comparisons are fair and the list of competitors is accurate. \n", "questions": "* The variational principle (Prop 2.8) and the loss L(\\theta) are KL minimization in different directions (direct, reverse). Can you clarify the implications? This would help!\n* The conditioning principle: how is it used exactly? Is it only for categorical data?\n* Gains from early stopping of certain coordinates: isn’t the computational complexity still the same? For example, when performing segmentation, even if certain pixel are “frozen” the score network still needs to process the full image, right?\n* Fast presampling of trajectories and rotation. Is this really trivially applicable to other hitting domains? The authors should sketch a discussion (also in Appendix) or modify the claim\n* Diffusion models for sampling: lines 28-30: It is a bit confusing in my opinion to claim that finite time diffusion models outperform infinite time (or mixing), as the former are used typically for data generation, while the latter for Bayesian Sampling and/or optimization. In line 35 it is claimed that the method can be used for inference as well. The authors should either clarify or remove the claim.\n\nTypos:\n* Line 153: P\\theta_0\n* Line 309: “Why can stop at hitting time”\n* Algorithm 2.3: where is it?\n\n\n== Post rebuttal comments==\nI have read the rebuttal and decided to increase my score slightly. I still think the notation, and the background knowledge required to digest the methodological part of this work to be worth improving. But this is a valid submission.\n", "limitations": "I think the limitations are exposed clearly and fairly.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 1, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The strength of the paper is the introduction of a new (to the best of my knowledge) data generation methodologies, suitable for arbitrary domains. Interestingly, classical diffusion models can be seen as a particular case of first hitting diffusion processes. To the best of my understanding the technical derivations are correct and the claims are mathematically valid. The experiments show the practical usefulness of the method.\n\nIn my opinion, one of the biggest drawback of the work is linked to the clarity of the exposition. The authors should clarify/simplify the notation. I think for a reader it is be quite hard to follow the paper, because it uses different notation/symbols to identify similar quantities. In particular:\n\n* Q is used for the paths/Ito process absorbed to \\Omega.\n* Q is used for times \\tau \n* Q^{... }_{\\Omega} for the harmonic measure/ exit distribution (why the notation with both pedix and superscript?) \n* Q^{\\Pi^*} is the Markov process with the desired exit distribution. Again, comparing with previous notation: Q^{ something}, “something” is sometimes a set, sometimes a measure\n* Q^{x}: paths taken conditionally on starting input x (is this explicitly defined?)\n* Q_0: some initial measure\n* P^{\\theta}, \\theta is the set of NN parameters!\n\nSecond, the authors should not take for granted certain results, and try to have a paper that is as self contained as possible. I understand many results could be taken for granted in other communities, but this is not the case for the Neurips audience, at least in my opinion. In particular:\n\n* the exit distribution on the sphere when the Brownian motion starts from a point z_0 that is not the center. Reference/ proof sketch?\n* Eq (7): be explicit about the math of disintegration and measure products\n* Eq (8): this is the central element of the paper, and is left uncommented/unjustified. Consider adding in the appendix a full expansion using h- transform (or any other tool)\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "l7Eqy0gI_T7", "reviewer": "Reviewer_wpmu", "summary": "This paper proposes FHDM (first hitting diffusion model), which differs from diffusion models based on infinite time (e.g., Langevin dynamics) or fixed time diffusion processes (e.g., DDPM); hence it can be used for data from discrete and structured domain by utilizing the exit distribution for learning and inference. The authors also propose a fast sampling algorithm for the rotational symmetric domain.", "questions": "- (L84) Equation 2 seems not general since it has time-independent coefficients in drift and diffusion terms. The solvability of SDEs with time-dependent coefficients is a well-known fact and the original fixed-time diffusion models also assume such conditions. Why do you restrict the condition of the coefficients? See [De Bortoli et al., (2021)](https://arxiv.org/abs/2111.07243) for a reference.\n- (L86) Why do we need a unique solvability of Equation 2 in the *weak* sense? For the readers who are not familiar with analytic probability theory, the authors need to specify why we can relax the regularity of the coefficients.\n- (L143) Where is Equation 15? Many equations have wrong equation numbers hence it is difficult to understand the statement of the manuscript.\n- Typos.\n    - (L141-L142): To address this problem, $P_{\\Omega}^{\\theta}$ of general **general** diffusion process\n    - (L141-L142): “**backwar**” way\n    - (L660, L662, 665 in Appendix A.9): It is a straightforward application of formula (4) → These are results of Equation 3.", "limitations": "The authors mentioned the technical limitations of their work. ", "rating": 3, "confidence": 4, "soundness": 3, "presentation": 1, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "(Strength)\n\n- (Significance) The proposed method shows good performance compared to the different genetive models on various domains such as sphere and graph.\n\n(Weakness)\n\n- (Originality) The proposed method shares a similar idea, *diffusion bridge*, with [S. Peluchetti (Non-denoising forward-time diffusion, 2021)](https://openreview.net/pdf?id=oVfIKuhqfC). The authors mention that the FHDM can learn the distribution in various domains by leveraging the Doob $h$-transform; however, the background theory of the two approaches seems equivalent although Peluchetti’s paper focuses on the diffusion mixtures.\n- (Quality) The concept of *Diffusion Bridge* is classical in the theory of diffusion processes. However, the authors only cover the diffusion processes with the *time-homogeneous* coefficients (see Equation 2). This setting cannot recover the original setting of fixed-time diffusion models which utilize the SDE classes with time-dependent coefficients.\n- (Clarity) The paper seems quite technical for general ML audiences while less informative for the experts in the diffusion theory. Furthermore, the reviewer finds out a few typos and has difficulties reading the proof since the statements of the manuscript are disorganized. The author recommends proofreading before the submission.\n\n***Updated Review***\n\nThe reviewer has read the authors' responses. The authors addressed my concerns regarding quality. However, the originality and clarity problems remain; hence I will keep my score.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "QuvTLE0Pg3Y", "reviewer": "Reviewer_Qdu1", "summary": "This paper introduces diffusion processes to generate discrete data by using hitting times as the end of the diffusion process rather than a fixed stopping time. The resulting first hitting diffusion models can be optimized by maximum likelihood, and the learning process is equivalent to matching the drift of the conditioned process. The simulation is done by a forward sampling process using the learned drift.", "questions": "1. Can you show the novelty of generated samples? Since the generative process lands on isolated points, the cost of learning to generalize to unseen data points can be bigger than operating in continuous spaces. \n2. Can this method works well with structured data, such as molecules?\n3. What is the approximate number of diffusion steps when the data dimension grows?", "limitations": "The authors properly addressed the limitations in their work.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: \n1. This paper proposes a rigorous approach to generating discrete data by introducing the hitting time on the target range as the stopping time. With the help of the h-transform, one can approximate the desired distribution by modeling the drift term.\n2. On symmetric spaces, one can pre-sample paths for faster computation with the rotation trick. \n3. Empirical results demonstrate better performance on point cloud generation and graph generation.\n\nWeaknesses: \n1. The method seems hard to scale to large and complex images.\n2. The sampling mechanism sequentially samples pixels in an image. The sequential selection process places a challenging condition (existing pixels) on the succeeding sampling process. The cost to learn all conditional distributions can be huge.\n3. There seems to be no mechanism to restrict the hitting time upper bound.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "4uh7D3tlidn", "reviewer": "Reviewer_hXZa", "summary": "This paper introduces First Hitting Diffusion Models (FHDM), a class of generative models that generalize the fixed time diffusion probabilistic models by enabling instance-dependent adaptive diffusion steps (i.e. terminates at a random first hitting time). Leveraging the framework of first hitting diffusion, FHDM can be applied to a wide range of distributions beyond $\\mathbb{R}^d$ by specifying the domain $\\Omega$, which could be a sphere or a simplex. Learning and inference are achieved by approximating the drift term in the corresponding Ito diffusion process with a neural network, in analogy to the score models in standard DDPMs. Experiments show that FHDM is able to generate high-quality samples for general data distributions.", "questions": "1. Is FHDM applicable for image generation tasks or others whose $\\Omega$ are not easily specified?\n2. Can you provide the example training time of the experiments? It seems that training FHDM could be time-consuming. For example, How long does it take to train the model for the \"Segmentation Map Generation\" task?", "limitations": "The authors mentioned that training overhead is one of the limitations.", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "- Originality:\nThe idea is very interesting and looks novel to me. To produce the data distribution, a different framework is adopted to construct the stochastic process, where only the forward process is considered. This could be an interesting topic for future research.\n----\n- Quality:\nThe proposed method looks technically sound. However, I am not familiar with the mathematical background of this paper and can not check the details.\n----\n- Clarity:\nThe paper is well-written and the figures are illustrative. Notations are clean and rigorous.\n----\n- Significance:\nThe proposed method is verified on several different domains (e.g. point cloud, sphere data, and graphs).", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept