Discrete Object Generation with Reversible Inductive Construction

• Discrete models face non-unique representations and potentially intractable construction paths, while structured domains also impose hard validity constraints.Source: §1 · pp. 1–2
• The method uses a Markov chain over valid objects, alternating fixed corruption with learned reconstruction through local inductive moves that preserve validity.Source: §1 · p. 2
• With a local corrupter, reconstruction becomes supervised multi-class classification over adjacent objects, yielding a target with fewer modes than the full data distribution.Source: §1 · p. 2
• Deployment requires expensive Gibbs sampling, and the implicit model does not provide predictive probabilities.Source: §1 · p. 3
• Quantitative evaluation indicates the method models highly structured distributions in molecules and Laman graphs while adhering to strict validity constraints.Source: §1 · p. 3

2 Reversible Inductive Construction

• GenRIC models a distribution over valid objects as the equilibrium of a chain that visits only valid objects and uses legal local insertions or deletions.Each transition samples a fixed corruption followed by a learned reconstruction; the chain's marginal approximates the data marginal.Source: §2 · p. 3, §2.1 · p. 3

2.1 Learning the Markov kernel

• With a finite state space enforced by a maximum object size, the equilibrium approaches the target joint distribution as the learned transition matrix approaches the target transition matrix.The result addresses the effect of an imperfect reconstruction model on the chain's equilibrium.Source: §2.1 · p. 4

2.2 Sampling training sequences

• Training samples pair data objects with corruption sequences, then fits the reconstruction distribution to recover originals from corrupted samples by maximum likelihood.The reconstruction objective minimizes expected KL divergence between the true and learned conditional distributions.Source: §2.2 · p. 4

2.3 Fixed corrupter

• The geometric corruption-length distribution gives exponentially decreasing support with edit distance, satisfying the stated ergodicity conditions for the Gibbs-sampled chain.The paper also notes that truncated support can satisfy ergodicity under stronger conditions.Source: §2.3 · p. 4
• The fixed corrupter samples a geometric number of insert or delete moves; the reported default is five expected steps, while shorter corruptions yielded better samples.The authors did not specially optimize corruption length for generation quality.Source: §2.3 · p. 4

2.4 Reconstruction distribution

• Corruption and reconstruction sequences are Markov-factorized, with reconstruction reversing the corruption steps until a stop token; molecule reconstruction also stops on revisiting a molecule.The next corruption depends only on the current object.Source: §2.4 · pp. 4–5
• The reconstruction model assigns probabilities to legal modifications using object-location and vocabulary embeddings, with factorized actions avoiding a fully connected softmax.For graph-structured domains, location embeddings use message passing, and location and vocabulary embeddings interact through a dot product.Source: §2.4 · p. 5

3.1 Legal operations

• Molecular modifications are restricted to inserting or deleting valid substructures, using compatible attachments for insertion and removable leaves for deletion.The vocabulary includes non-ring bonds, simple rings, and bridged compounds found in training data; the described molecular representation does not account for stereochemistry.Source: §3.1 · pp. 5–6
• These minimal operations make the chain ergodic over valid molecular graphs constructible from the extracted vocabulary, although arbitrary molecules may not be reachable.The authors report that the finite vocabulary empirically provides broad coverage over organic molecules.Source: §3.1 · p. 6

3.2 Data

• The molecule experiments use the ZINC dataset, training on 220K molecules from a dataset of about 250K drug-like molecules.Source: §3.2 · p. 6

3.3 Distributional statistics

• The evaluation compares generated-molecule distributions for QED, SA, and logP with ZINC and reports validity; the method enforces valid molecular samples.QED, SA, and logP summarize drug-likeness, synthetic accessibility, and hydrophobicity, respectively.Source: §3.3 · pp. 6–7, Table 1 · p. 7
• Generated novel molecules closely match empirical QED and logP distributions, while SA is more challenging; the SMILES-based LSTM matches SA substantially better than other methods.Only novel molecules are included in the metric computation; the comparison uses 20K samples per method.Source: §3.3 · p. 6
• Reconstructed molecules have 21% higher QED on average than their corrupted inputs, while repeated corruption without reconstruction severely diverges from the data distribution.Corrupted samples are also less druglike and less synthesizable on average than reconstructed samples.Source: §3.3 · p. 7

4 Application: Laman Graphs

• Laman graphs model two-dimensional minimally rigid geometry; removing any single edge makes such a system under-constrained.Validity requires exactly 2n −3 edges and no node-induced subgraph of k nodes to have more than 2k −3 edges; these conditions are not sufficient for well-constrained geometry in 3D.Source: §4 · pp. 7–8

4.3 Distributional statistics

• Table 2 reports bootstrapped DoD-distribution KS distances to training data and validity scores for sampled Laman graphs.The table gives means and standard deviations; it reports results for models trained on the low-decomposability dataset.Source: Table 2 · p. 8, §4.3 · p. 8

4.1 Legal operations

• Henneberg type I and II insertions, and their inverse deletions, provide legal moves for constructing Laman graphs; reverse type II requires checking where the missing edge can be inserted.The legal-neighbor check uses an O(n^2) Laman satisfaction test, running in O(n^1.15) at the rigidity transition.Source: §4.1 · p. 8, Figure 4 · p. 8

4.2 Data

• The synthetic dataset generator approximately controls degree of decomposability (DoD), defined as the number of well-constrained node-induced subgraphs divided by the number of nodes.The study generates 100K graphs each for low- and high-decomposability settings.Source: §4.2 · p. 8

4.3 Distributional statistics

• Erdős–Rényi produces < 0.1% valid graphs, while GraphRNN does little better; the proposed method instead learns DoD statistics within valid graphs.The reported statistics compare 20K samples per method on the low-decomposability dataset; similar results were observed in the high-decomposability setting.Source: §4.3 · pp. 8–9

5 Conclusion and Future Work

• The approach captures relevant distributional statistics over molecules and Laman graphs while always producing valid structures.The method trains a model to undo local corrupting operations using reversible inductive moves that preserve validity constraints.Source: §5 · p. 9
• A limitation is that inductive moves must be identified and specified for each new domain; learning these moves from data is proposed as future work.For molecules, restricting transitions to learned chemical reactions could improve synthesizability.Source: §5 · p. 9
• Masking chain transitions to preserve a desired molecular scaffold is proposed as a route to conditional generation, potentially paired with virtual screening for candidate-drug search.The example scaffold is benzodiazepines.Source: §5 · p. 9

A Geometric Distribution for Corrupter

• A one-step average corruption sequence seems to better match the SA distribution, but observed Markov-chain mixing is slower.Figure 5 presents QED, SA, and logP distributions for ZINC and models trained with varying expected corruption-sequence lengths.Source: A Geometric Distribution for Corrupter · p. 12, Figure 5 · p. 12

B Molecular Reconstruction Model Operations

• Molecular operations are represented by a location and an operation type; the stop action uses the whole molecule, while atom- and ring-leaf deletions target an atom or ring.Atom-fusion insertion attaches at an existing atom, and bond-fusion insertion attaches at an existing bond in a ring.Source: B Molecular Reconstruction Model… · p. 12
• Message passing produces atom and bond messages that are pooled or transformed into embeddings for stopping, leaf deletions, and atom- or bond-fusion insertions.The molecule embedding is used for stop prediction; leaf-ring messages are pooled for delete-ring actions.Source: B Molecular Reconstruction Model… · p. 12

C.1 Molecule model

• Molecule models use five message-passing steps, pooled atom messages, and 384-dimensional messages and hidden layers; training runs for 50 epochs with Adamax.Training uses a base learning rate of 2 × 10−3, batch size 1024, and learning-rate reductions after epochs 12, 24, and 36.Source: §C.1 · p. 13

C.2 Laman model

• Laman models encode node degree with Fourier features and use five message-passing steps, average and max pooling, 30 training epochs, and batch size 256.The models use the molecule-model optimizer settings and were trained on a Titan X Pascal GPU.Source: §C.2 · p. 13

D Sampling Details

• Sampling starts from a random training-set object and alternates corrupter and reconstructor sequences; reported results use a geometric corruption length averaging five moves.Every Markov-chain sample is retained without thinning, including adjacent repeats caused by perfect reconstruction.Source: D Sampling Details · p. 13
• The action space slightly exceeds valid moves; invalid reconstructor actions are ignored and resampled, and object-size bounds prevent deletion of the entire object.Molecules are capped at 25 atoms; the authors report little result impact for maximum sizes between 25 and 35 atoms.Source: D Sampling Details · p. 13

D.1 Revisit Stop Criterion

• For molecules, reconstruction stops when its output revisits a molecule already seen in that reconstruction history.The rule addresses a model with high precision and no recurrent state to increase its probability of stopping as the sequence grows; revisiting is interpreted as an implicit indication that the molecule is realistic enough on average.Source: §D.1 · pp. 13–14

E.1 Laman

• Laman graph sizes are sampled from a normal distribution with mean 30 and standard deviation 5, while p sets low or high decomposability.The low-decomposability setting uses p ∼U(0, 0.1), and the high-decomposability setting uses p ∼U(0.9, 1); graphs start from K3.Source: §E.1 · p. 14

F.1 Molecule Corrupter

• Molecule corruption uses a fixed corrupter, sampling a geometric number of steps and iteratively applying the single-step procedure.The authors did not optimize the corrupter to improve samples or ease learning.Source: §F.1 · p. 14

F.2 Laman Corrupter

• Laman corruption uniformly chooses among four Henneberg move types and then among valid actions of that type, with sub-step counts sampled geometrically.The four types are Henneberg I and II and their inverses.Source: §F.2 · p. 15

G GuacaMol Benchmarks

• Validity: 1.0, uniqueness: 0.933, novelty: 0.942, KL divergence: 0.771, and FCD: 0.058 on GuacaMol after training on ChEMBL.The model uses the same hyperparameters and sampling framework as for the ZINC model.Source: G GuacaMol Benchmarks · p. 15
• Autocorrelation in generated chains makes FCD not directly applicable and limits sample diversity, though thinning may address the diversity limitation.The reported results use the same sampling framework as for the ZINC model.Source: G GuacaMol Benchmarks · p. 15

H Reconstructed vs. Corrupted Samples

• Corruption-only samples severely diverge from the data distribution, as the QED and SA distributions compare reconstructed, corrupted, and corruption-only molecules.Figure 6 presents QED on the left and SA on the right.Source: Figure 6 · p. 15, H Reconstructed vs. Corrupted Samples · p. 15

I Example Chains

• Example molecular chains are shown after every transition, every five transitions, and every ten transitions.The section introduces three example chains for the molecular model.Source: I Example Chains · p. 15, Figure 7 · p. 16, Figure 8 · p. 17