# Discrete Object Generation with Reversible Inductive Construction

arXiv: https://arxiv.org/abs/1907.08268 · HTML: https://mlsanity.com/paper/1907.08268/

## Key facts

- Cited by 16 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 18 Jul 2019.

## Built on by (most cited first, 16 of 16)

- [Structured Denoising Diffusion Models in Discrete State-Spaces](https://mlsanity.com/paper/2107.03006/) (2021)
- [Flow Network based Generative Models for Non-Iterative Diverse Candidate Generation](https://mlsanity.com/paper/2106.04399/) (2021)
- [GFlowNet Foundations](https://mlsanity.com/paper/2111.09266/) (2021)
- [A Reparameterized Discrete Diffusion Model for Text Generation](https://mlsanity.com/paper/2302.05737/) (2023)
- [MARS: Markov Molecular Sampling for Multi-objective Drug Discovery](https://mlsanity.com/paper/2103.10432/) (2021)
- [Multi-Objective GFlowNets](https://mlsanity.com/paper/2210.12765/) (2022)
- [Improved Masked Image Generation with Token-Critic](https://mlsanity.com/paper/2209.04439/) (2022)
- [How Discrete and Continuous Diffusion Meet: Comprehensive Analysis of Discrete Diffusion Models via a Stochastic Integral Framework](https://mlsanity.com/paper/2410.03601/) (2024)
- [Fast Solvers for Discrete Diffusion Models: Theory and Applications of High-Order Algorithms](https://mlsanity.com/paper/2502.00234/) (2025)
- [Convergence Analysis of Discrete Diffusion Model: Exact Implementation through Uniformization](https://mlsanity.com/paper/2402.08095/) (2024)
- [Beyond In-Place Corruption: Insertion and Deletion In Denoising Probabilistic Models](https://mlsanity.com/paper/2107.07675/) (2021)
- [Molecule Generation for Drug Design: a Graph Learning Perspective](https://mlsanity.com/paper/2202.09212/) (2022)
- [Scalable Fragment-Based 3D Molecular Design with Reinforcement Learning](https://mlsanity.com/paper/2202.00658/) (2022)
- [Amortized Synthesis of Constrained Configurations Using a Differentiable Surrogate](https://mlsanity.com/paper/2106.09019/) (2021)
- [ChatMol: A Versatile Molecule Designer Based on the Numerically Enhanced Large Language Model](https://mlsanity.com/paper/2502.19794/) (2025)
- [Bayesian Sequential Stacking Algorithm for Concurrently Designing Molecules and Synthetic Reaction Networks](https://mlsanity.com/paper/2204.01847/) (2022)

## Abstract (arXiv)

The success of generative modeling in continuous domains has led to a surge of interest in generating discrete data such as molecules, source code, and graphs. However, construction histories for these discrete objects are typically not unique and so generative models must reason about intractably large spaces in order to learn. Additionally, structured discrete domains are often characterized by strict constraints on what constitutes a valid object and generative models must respect these requirements in order to produce useful novel samples. Here, we present a generative model for discrete objects employing a Markov chain where transitions are restricted to a set of local operations that preserve validity. Building off of generative interpretations of denoising autoencoders, the Markov chain alternates between producing 1) a sequence of corrupted objects that are valid but not from the data distribution, and 2) a learned reconstruction distribution that attempts to fix the corruptions while also preserving validity. This approach constrains the generative model to only produce valid objects, requires the learner to only discover local modifications to the objects, and avoids marginalization over an unknown and potentially large space of construction histories. We evaluate the proposed approach on two highly structured discrete domains, molecules and Laman graphs, and find that it compares favorably to alternative methods at capturing distributional statistics for a host of semantically relevant metrics.