Diffusion map particle systems for generative modeling

Fengyi Li; Youssef Marzouk

doi:10.3934/fods.2024054

Article Contents

2025, Volume 7, Issue 3: 814-837. Doi: 10.3934/fods.2024054

This issue Previous Article Deep learning with Gaussian continuation Next Article Measure transport via polynomial density surrogates

Diffusion map particle systems for generative modeling

Fengyi Li^, and
Youssef Marzouk

Massachusetts Institute of Technology, Cambridge, MA 02139 USA

^*Corresponding author: Fengyi Li
^*Corresponding author: Fengyi Li

Received: October 2023

Revised: August 2024

Early access: December 24, 2024

Published online: December 24, 2024

Abstract / Introduction Full Text(HTML) Figure(9) / Table(2) Related Papers Cited by

Abstract

We propose a novel diffusion map particle system (DMPS) for generative modeling, based on diffusion maps and Laplacian-adjusted Wasserstein gradient descent (LAWGD). Diffusion maps are used to approximate the generator of the corresponding Langevin diffusion process from samples, and hence to learn the underlying data-generating manifold. On the other hand, LAWGD enables efficient sampling from the target distribution given a suitable choice of kernel, which we construct here via a spectral approximation of the generator, computed with diffusion maps. Our method requires no offline training and minimal tuning, and can outperform other approaches on data sets of moderate dimension.

Keywords:

Mathematics Subject Classification: 65C35, 60J60, 47B34.

Citation:

Full Text(HTML)

Figure 1. Mickey mouse: 2700 generated particles using DPMS and SVGD, with 2000 training samples

Download: Full-size image PowerPoint slide

Figure 2. Mickey mouse: an instance of running the SVGD generative model shows strange non-uniform pattern with 1000 training samples and 2700 generated particles

Download: Full-size image PowerPoint slide

Figure 3. Mickey mouse: error comparison between DMPS, SVGD

Download: Full-size image PowerPoint slide

Figure 4. Two moons: 900 generated particles from DMPS, SVGD, and ULA with 500 training samples

Download: Full-size image PowerPoint slide

Figure 5. Two moons: error comparison between DMPS, SVGD, and ULA. Solid lines use 500 training samples, dashed lines use 1000

Download: Full-size image PowerPoint slide

Figure 6. The arc: 900 generated particles using DMPS, SVGD, ULA, and SGM with 1000 training samples

Download: Full-size image PowerPoint slide

Figure 7. The arc: error comparison between DMPS, SVGD, ULA, and SGM. Solid lines use 100 training samples; dashed lines use 1000

Download: Full-size image PowerPoint slide

Figure 8. Hyper-semisphere: 300 generated samples using DMPS, SVGD, ULA, and SGM in three dimensions with 1000 training samples

Download: Full-size image PowerPoint slide

Figure 9. Gluon jet dataset: marginal distributions of the target samples and 2700 generated particles using DMPS, SVGD, ULA, and SGM with 1000 traning samples. Coordinates are $ \eta^{ \rm{rel}} $, $ \phi^{ \rm{rel}} $, and $ p_T^{ \rm{rel}} $, respectively

Download: Full-size image PowerPoint slide

Table 1. Hyper-semisphere: error comparison ($ \pm $ standard error) between DMPS, SVGD, ULA, and SGM

	DMPS	SVGD	ULA	SGM
$ d $ = 3	0.018 $ \pm $ 0.0003	0.146 $ \pm $ 0.0229	0.033 $ \pm $ 0.0006	0.032 $ \pm $ 0.0024
$ d $ = 6	0.142 $ \pm $ 0.0003	0.267 $ \pm $ 0.0171	0.185 $ \pm $ 0.0012	0.170 $ \pm $ 0.0022
$ d $ = 9	0.303 $ \pm $ 0.0003	0.361 $ \pm $ 0.0077	0.378 $ \pm $ 0.0011	0.348 $ \pm $ 0.0025
$ d $ = 12	0.441 $ \pm $ 0.0002	0.811 $ \pm $ 0.0783	0.555 $ \pm $ 0.0018	0.496 $ \pm $ 0.0041
$ d $ = 15	0.564 $ \pm $ 0.0009	0.986 $ \pm $ 0.0055	0.713 $ \pm $ 0.0025	0.608 $ \pm $ 0.0024

| Show Table

DownLoad: CSV

Table 2. Gluon jet dataset: error comparison ($\pm$ standard error) between DMPS, SVGD, ULA, and SGM, for different numbers of generated particles

# particles	DMPS	SVGD	ULA	SGM
100	$\mathit{\boldsymbol{0.0020}}$ ${\pm 5.03 \times 10^{-5}}$	$0.0062 \pm 4.00 \times 10^{-4}$	$0.0041 \pm 2.64 \times 10^{-4}$	$0.0029 \pm 1.21 \times 10^{-4}$
300	$\mathit{\boldsymbol{0.0014}}$ ${\pm 1.65 \times 10^{-5}}$	$0.0059 \pm 3.75 \times 10^{-4}$	$0.0032 \pm 1.73 \times 10^{-4}$	$0.0021 \pm 0.55 \times 10^{-4}$
900	$\mathit{\boldsymbol{0.0012}}$ ${\pm 1.61 \times 10^{-5}}$	$0.0058 \pm 3.65 \times 10^{-4}$	$0.0029 \pm 1.53 \times 10^{-4}$	$0.0018 \pm 0.46 \times 10^{-4}$
2700	$\mathit{\boldsymbol{0.0012}}$ ${\pm 1.59 \times 10^{-5}}$	$0.0057 \pm 3.61 \times 10^{-4}$	$0.0027 \pm 1.30 \times 10^{-4}$	$0.0018 \pm 0.44 \times 10^{-4}$

| Show Table

DownLoad: CSV

Related Papers

Cited by

References

[1]	S. Adams, N. Dirr, M. Peletier and J. Zimmer, Large deviations and gradient flows, Philosophical Transactions. Series A, Mathematical, Physical, and Engineering Sciences, 371 (2013), 20120341, 17 pp. doi: 10.1098/rsta.2012.0341.
[2]	L. Ambrosio, N. Gigli and G. Savare, Gradient Flows in Metric Spaces and in The Space Of Probability Measures, Birkhäuser Verlag, Basel, 2008.
[3]	N. Anand and P.-S. Huang, Generative modeling for protein structures, in Advances in Neural Information Processing Systems (eds. S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi and R. Garnett), vol. 31, Curran Associates, Inc., 2018, https://proceedings.neurips.cc/paper/2018/file/afa299a4d1d8c52e75dd8a24c3ce534f-Paper.pdf
[4]	M. Belkin and P. Niyogi, Laplacian eigenmaps for dimensionality reduction and data representation, Neural Computation, 15 (2003), 1373-1396. doi: 10.1162/089976603321780317.
[5]	V. D. Bortoli, E. Mathieu, M. Hutchinson, J. Thornton, Y. W. Teh and A. Doucet, Riemannian score-based generative modeling, ArXiv, arXiv: 2202.02763.
[6]	J. Brehmer and K. Cranmer, Flows for simultaneous manifold learning and density estimation, ArXiv, arXiv: 2003.13913.
[7]	R. Cai, G. Yang, H. Averbuch-Elor, Z. Hao, S. Belongie, N. Snavely and B. Hariharan, Learning gradient fields for shape generation, in Computer Vision - ECCV 2020 - 16th European Conference, Glasgow, UK, August 23-28, 2020, Proceedings, Part III (eds. A. Vedaldi, H. Bischof, T. Brox and J. Frahm), vol. 12348 of Lecture Notes in Computer Science, Springer, 2020,364-381. doi: 10.1007/978-3-030-58580-8_22.
[8]	A. L. Caterini, G. Loaiza-Ganem, G. Pleiss and J. P. Cunningham, Rectangular flows for manifold learning, in Neural Information Processing Systems, 2021.
[9]	S. Chewi, T. L. Gouic, C. Lu, T. Maunu and P. Rigollet, Svgd as a kernelized wasserstein gradient flow of the chi-squared divergence, ArXiv, arXiv: 2006.02509.
[10]	R. R. Coifman and S. Lafon, Diffusion maps, Applied and Computational Harmonic Analysis, 21 (2006), 5-30, Special Issue: Diffusion Maps and Wavelets. doi: 10.1016/j.acha.2006.04.006.
[11]	R. R. Coifman, S. Lafon, A. B. Lee, M. Maggioni, B. Nadler, F. Warner and S. W. Zucker, Geometric diffusions as a tool for harmonic analysis and structure definition of data: Diffusion maps, Proceedings of the National Academy of Sciences, 102 (2005), 7426-7431. doi: 10.1073/pnas.0500334102.
[12]	M. Cuturi, Sinkhorn distances: Lightspeed computation of optimal transport, in Advances in Neural Information Processing Systems (eds. C. Burges, L. Bottou, M. Welling, Z. Ghahramani and K. Weinberger), vol. 26, Curran Associates, Inc., 2013, https://proceedings.neurips.cc/paper/2013/file/af21d0c97db2e27e13572cbf59eb343d-Paper.pdf.
[13]	S. Daneri and G. Savaré, Lecture notes on gradient flows and optimal transport, 2010, https://arXiv.org/abs/1009.3737.
[14]	G. Franzese, S. Rossi, L. Yang, A. Finamore, D. Rossi, M. Filippone and P. Michiardi, How much is enough? a study on diffusion times in score-based generative models, Entropy, 25 (2023), Paper No. 633, 30 pp. https://arXiv.org/abs/2206.05173. doi: 10.3390/e25040633.
[15]	A. Garbuno-Iñigo, N. Nüsken and S. Reich, Affine invariant interacting langevin dynamics for bayesian inference, SIAM J. Appl. Dyn. Syst., 19 (2019), 1633-1658. doi: 10.1137/19M1304891.
[16]	I. J. Goodfellow, J. Pouget-Abadie, M. Mirza, B. Xu, D. Warde-Farley, S. Ozair, A. Courville and Y. Bengio, Generative adversarial nets, in Advances in Neural Information Processing Systems (eds. Z. Ghahramani, M. Welling, C. Cortes, N. Lawrence and K. Weinberger), vol. 27, Curran Associates, Inc., 2014, https://proceedings.neurips.cc/paper/2014/file/5ca3e9b122f61f8f06494c97b1afccf3-Paper.pdf.
[17]	G. A. Gottwald, F. Li, Y. Marzouk and S. Reich, Stable generative modeling using diffusion maps, 2024, https://arXiv.org/abs/2401.04372.
[18]	M. Hein, J.-Y. Audibert and U. von Luxburg, From graphs to manifolds - weak and strong pointwise consistency of graph laplacians, in Annual Conference Computational Learning Theory, 2005. doi: 10.1007/11503415_32.
[19]	J. Ho, X. Chen, A. Srinivas, Y. Duan and P. Abbeel, Flow++: Improving flow-based generative models with variational dequantization and architecture design, ArXiv, arXiv: 1902.00275.
[20]	J. Ho, A. Jain and P. Abbeel, Denoising diffusion probabilistic models, in Advances in Neural Information Processing Systems (eds. H. Larochelle, M. Ranzato, R. Hadsell, M. Balcan and H. Lin), vol. 33, Curran Associates, Inc., 2020, 6840-6851, https://proceedings.neurips.cc/paper/2020/file/4c5bcfec8584af0d967f1ab10179ca4b-Paper.pdf.
[21]	J. Ho, C. Saharia, W. Chan, D. J. Fleet, M. Norouzi and T. Salimans, Cascaded diffusion models for high fidelity image generation, J. Mach. Learn. Res., 23 (2021), Paper No. [47], 33 pp.
[22]	R. Jordan, D. Kinderlehrer and F. Otto, The variational formulation of the fokker–planck equation, SIAM Journal on Mathematical Analysis, 29 (1998), 1-17. doi: 10.1137/S0036141096303359.
[23]	R. Kansal, J. Duarte, H. Su, B. Orzari, T. Tomei, M. Pierini, M. Touranakou, D. Gunopulos et al., Particle cloud generation with message passing generative adversarial networks, Advances in Neural Information Processing Systems, 34 (2021), 23858-23871.
[24]	S. Kazeminia, C. Baur, A. Kuijper, B. van Ginneken, N. Navab, S. Albarqouni and A. Mukhopadhyay, Gans for medical image analysis, Artificial Intelligence in Medicine, 109 (2020), 101938. doi: 10.1016/j.artmed.2020.101938.
[25]	A. Khandelwal and R. G. Krishnan, Fine-tuning generative models, 2019.
[26]	D. P. Kingma and M. Welling, Auto-encoding variational bayes, CoRR, arXiv: 1312.6114.
[27]	P. A. Knight, The sinkhorn-knopp algorithm: Convergence and applications, SIAM J. Matrix Anal. Appl., 30 (2008), 261-275. doi: 10.1137/060659624.
[28]	C.-L. Li, W.-C. Chang, Y. Cheng, Y. Yang and B. Póczos, MMDGAN: Towards deeper understanding of moment matching network, in NIPS, 2017.
[29]	X. L. Li, J. Thickstun, I. Gulrajani, P. Liang and T. B. Hashimoto, Diffusion-lm improves controllable text generation, 2022, https://arXiv.org/abs/2205.14217.
[30]	Y. Li, Q. Pan, S. Wang, T. Yang and E. Cambria, A generative model for category text generation, Information Sciences, 450 (2018), 301-315. doi: 10.1016/j.ins.2018.03.050.
[31]	Q. Liu, Stein variational gradient descent as gradient flow, in Advances in Neural Information Processing Systems (eds. I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan and R. Garnett), vol. 30, Curran Associates, Inc., 2017, https://proceedings.neurips.cc/paper/2017/file/17ed8abedc255908be746d245e50263a-Paper.pdf.
[32]	Q. Liu and D. Wang, Stein variational gradient descent: A general purpose bayesian inference algorithm, in NIPS, 2016.
[33]	D. Mahapatra, B. Bozorgtabar and R. Garnavi, Image super-resolution using progressive generative adversarial networks for medical image analysis, Computerized Medical Imaging and Graphics, 71 (2019), 30-39. doi: 10.1016/j.compmedimag.2018.10.005.
[34]	Y. Miao and P. Blunsom, Language as a latent variable: Discrete generative models for sentence compression, In Proceedings of the 2016 Conference on Empirical Methods in Natural Language Processing, (2016), 319-328. doi: 10.18653/v1/D16-1031.
[35]	B. Nadler, S. Lafon, R. R. Coifman and I. G. Kevrekidis, Diffusion maps, spectral clustering and reaction coordinates of dynamical systems, Applied and Computational Harmonic Analysis, 21 (2006), 113-127, Special Issue: Diffusion Maps and Wavelets. doi: 10.1016/j.acha.2005.07.004.
[36]	B. Nadler, S. Lafon, R. R. Coifman and I. G. Kevrekidis, Diffusion maps, spectral clustering and eigenfunctions of fokker-planck operators, in Advances in Neural Information Processing Systems (eds. Y. Weiss, B. Schölkopf and J. Platt), vol. 18, MIT Press, 2005, https://proceedings.neurips.cc/paper/2005/file/2a0f97f81755e2878b264adf39cba68e-Paper.pdf.
[37]	D. Nie, R. Trullo, J. Lian, C. Petitjean, S. Ruan, Q. Wang and D. Shen, Medical image synthesis with context-aware generative adversarial networks, in Medical Image Computing and Computer Assisted Intervention (MICCAI 2017) (eds. M. Descoteaux, L. Maier-Hein, A. Franz, P. Jannin, D. L. Collins and S. Duchesne), Springer International Publishing, Cham, 2017,417-425. doi: 10.1007/978-3-319-66179-7_48.
[38]	Y. Peres, Conditions for convergence of a derivative, given the function itself is convergent, Mathematics Stack Exchange, https://math.stackexchange.com/q/4517640, (version: 2022-08-24).
[39]	J. Pidstrigach, Score-based generative models detect manifolds, ArXiv, arXiv: 2206.01018.
[40]	J. Pidstrigach, Score-based generative models introduction, https://jakiw.com/sgm_intro, 2022, Accessed: 2024-01-24.
[41]	M. Ranzato, J. Susskind, V. Mnih and G. Hinton, On deep generative models with applications to recognition, in CVPR 2011, 2011, 2857-2864. doi: 10.1109/CVPR.2011.5995710.
[42]	D. J. Rezende, S. Mohamed and D. Wierstra, Stochastic backpropagation and approximate inference in deep generative models, in Proceedings of the 31st International Conference on Machine Learning (eds. E. P. Xing and T. Jebara), vol. 32 of Proceedings of Machine Learning Research, PMLR, Bejing, China, 2014, 1278-1286, https://proceedings.mlr.press/v32/rezende14.html.
[43]	R. Rombach, A. Blattmann, D. Lorenz, P. Esser and B. Ommer, High-resolution image synthesis with latent diffusion models, 2021, https://arXiv.org/abs/2112.10752.
[44]	S. T. Roweis and L. K. Saul, Nonlinear dimensionality reduction by locally linear embedding, Science, 290 (2000), 2323-2326. doi: 10.1126/science.290.5500.2323.
[45]	L. Ruthotto and E. Haber, An introduction to deep generative modeling, GAMM-Mitteilungen, 44 (2021), e202100008, 24 pp. doi: 10.1002/gamm.202100008.
[46]	T. Salimans, I. Goodfellow, W. Zaremba, V. Cheung, A. Radford and X. Chen, Improved techniques for training gans, in Advances in Neural Information Processing Systems (eds. D. Lee, M. Sugiyama, U. Luxburg, I. Guyon and R. Garnett), vol. 29, Curran Associates, Inc., 2016, https://proceedings.neurips.cc/paper/2016/file/8a3363abe792db2d8761d6403605aeb7-Paper.pdf.
[47]	F. Santambrogio, {Euclidean, Metric, and Wasserstein} gradient flows: An overview, Bulletin of Mathematical Sciences, 7 (2017), 87-154. doi: 10.1007/s13373-017-0101-1.
[48]	T. R. Shaham, T. Dekel and T. Michaeli, Singan: Learning a generative model from a single natural image, IEEE/CVF International Conference on Computer Vision (ICCV), (2019) 4569-4579. doi: 10.1109/ICCV.2019.00467.
[49]	A. Singer, From graph to manifold laplacian: The convergence rate, Applied and Computational Harmonic Analysis, 21 (2006), 128-134. doi: 10.1016/j.acha.2006.03.004.
[50]	Y. Song and S. Ermon, Generative modeling by estimating gradients of the data distribution, in Advances in Neural Information Processing Systems, vol. 32, Curran Associates, Inc., 2019, https://proceedings.neurips.cc/paper/2019/file/3001ef257407d5a371a96dcd947c7d93-Paper.pdf.
[51]	Y. Song and S. Ermon, Improved techniques for training score-based generative models, in Advances in Neural Information Processing Systems (eds. H. Larochelle, M. Ranzato, R. Hadsell, M. Balcan and H. Lin), vol. 33, Curran Associates, Inc., 2020, 12438-12448, https://proceedings.neurips.cc/paper/2020/file/92c3b916311a5517d9290576e3ea37ad-Paper.pdf.
[52]	Y. Song, J. Sohl-Dickstein, D. P. Kingma, A. Kumar, S. Ermon and B. Poole, Score-based generative modeling through stochastic differential equations, ArXiv, arXiv: 2011.13456.
[53]	J. B. Tenenbaum, V. de Silva and J. C. Langford, Reduction a global geometric framework for nonlinear dimensionality, 2011.
[54]	C. Villani, Topics in Optimal Transportation, Grad. Stud. Math., 58, American Mathematical Society, Providence, RI, 2003. doi: 10.1090/gsm/058.
[55]	C. Villani, Optimal Transport: Old and New, Grundlehren Math. Wiss., 338, Springer-Verlag, Berlin, 2009. doi: 10.1007/978-3-540-71050-9.
[56]	A. Wibisono, Sampling as optimization in the space of measures: The langevin dynamics as a composite optimization problem, in Annual Conference Computational Learning Theory, 2018.
[57]	Z. Wu, K. E. Johnston, F. H. Arnold and K. K. Yang, Protein sequence design with deep generative models, Current Opinion in Chemical Biology, 65 (2021), 18-27. doi: 10.1016/j.cbpa.2021.04.004.
[58]	L. Yang, Z. Zhang, Y. Song, S. Hong, R. Xu, Y. Zhao, W. Zhang, B. Cui and M.-H. Yang, Diffusion models: A comprehensive survey of methods and applications, 2022, https://arXiv.org/abs/2209.00796.
[59]	R. A. Yeh, C. Chen, T. Y. Lim, A. G. Schwing, M. Hasegawa-Johnson and M. N. Do, Semantic image inpainting with deep generative models, in 2017 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), IEEE Computer Society, Los Alamitos, CA, USA, 2017, 6882-6890. doi: 10.1109/CVPR.2017.728.
[60]	X. Yi, E. Walia and P. Babyn, Generative adversarial network in medical imaging: A review, Medical Image Analysis, 58 (2019), 101552. doi: 10.1016/j.media.2019.101552.
[61]	D. Yogatama, C. Dyer, W. Ling and P. Blunsom, Generative and discriminative text classification with recurrent neural networks, ArXiv, arXiv: 1703.01898.