Graphically Structured Diffusion Models
This work addresses the problem of efficiently generating solutions for structured computational tasks, which is incremental as it adapts existing diffusion models to specific problem domains.
The authors tackled the challenge of learning deep generative models for algorithmically structured problems like sorting and Sudoku by introducing a framework that tailors diffusion model architectures to problem-specific graphical structures, resulting in improved scaling relationships between problem dimension and model performance in terms of training time and accuracy.
We introduce a framework for automatically defining and learning deep generative models with problem-specific structure. We tackle problem domains that are more traditionally solved by algorithms such as sorting, constraint satisfaction for Sudoku, and matrix factorization. Concretely, we train diffusion models with an architecture tailored to the problem specification. This problem specification should contain a graphical model describing relationships between variables, and often benefits from explicit representation of subcomputations. Permutation invariances can also be exploited. Across a diverse set of experiments we improve the scaling relationship between problem dimension and our model's performance, in terms of both training time and final accuracy. Our code can be found at https://github.com/plai-group/gsdm.