PaperlayerView exact revision on arXiv

Source-linked AI summary

DiGress: Discrete Denoising diffusion for graph generation

Clement Vignac, Igor Krawczuk, Antoine Siraudin, Bohan Wang, Volkan Cevher, Pascal Frossard

arXiv:2209.14734v4cs.LG

TL;DR

Graph generation is challenging because graphs are unordered, sparse, and structured, while continuous diffusion can destroy those properties. DiGress uses discrete graph edits and a graph transformer, with marginal-preserving noise and auxiliary features, and reports state-of-the-art generation performance at molecular and non-molecular scales.

  • Problem

    Graph generation is challenging because graphs are unordered and sparse, while Gaussian diffusion destroys sparsity and graph-theoretic structure.

  • Method

    DiGress applies discrete diffusion to categorical node and edge attributes and trains a graph transformer to predict clean graphs.

  • Results

    DiGress outperforms existing one-shot methods and scales to larger molecular datasets, reaching the performance of autoregressive models trained using expert knowledge.

  • Takeaways & Limitations

    Discrete graph diffusion supports state-of-the-art generation across molecular and non-molecular tasks while preserving graph structure during noise injection.

  • Takeaways & Limitations

    Conditional generation relies on an additional Gaussian assumption for the noisy graph-level property distribution and a learned mean function.

Abstract

from arXiv · show

This work introduces DiGress, a discrete denoising diffusion model for generating graphs with categorical node and edge attributes. Our model utilizes a discrete diffusion process that progressively edits graphs with noise, through the process of adding or removing edges and changing the categories. A graph transformer network is trained to revert this process, simplifying the problem of distribution learning over graphs into a sequence of node and edge classification tasks. We further improve sample quality by introducing a Markovian noise model that preserves the marginal distribution of node and edge types during diffusion, and by incorporating auxiliary graph-theoretic features. A procedure for conditioning the generation on graph-level features is also proposed. DiGress achieves state-of-the-art performance on molecular and non-molecular datasets, with up to 3x validity improvement on a planar graph dataset. It is also the first model to scale to the large GuacaMol dataset containing 1.3M drug-like molecules without the use of molecule-specific representations.

1 INTRODUCTION

DiGress addresses graph-generation challenges by using discrete diffusion that preserves graph structure while denoising categorical node and edge attributes. It adds marginal-preserving noise, graph features, and conditioning to improve generation across tasks.

  • Graph generation is difficult because graphs are unordered and sparse, complicating direct distribution learning.
  • Continuous graph diffusion destroys sparsity and produces complete noisy graphs where connectivity and cycle counts are undefined.
  • DiGress progressively edits categorical node and edge attributes with discrete noise, then uses a graph transformer to predict the clean graph.
  • Marginal-preserving noise, auxiliary structural and spectral features, and graph-level conditioning are introduced as algorithmic enhancements.
  • DiGress achieves state-of-the-art performance with realistic, diverse, and novel graphs, matching expert-knowledge autoregressive models on MOSES and GuacaMol.

2 DIFFUSION MODELS

Diffusion models corrupt data through a Markovian noise process and learn to reverse it from noisy states. For graphs, the paper motivates discrete diffusion because Gaussian noise destroys sparsity and graph-theoretic structure.

  • Diffusion models generate samples by recursively denoising trajectories that were created by progressively adding noise.
  • The denoising network predicts the clean data point rather than a noisy intermediate state, reducing label noise when the posterior is tractable.
  • Efficient diffusion requires closed-form noisy-state and posterior distributions plus a data-independent limiting distribution for inference.
  • Gaussian noise is poorly suited to graphs because it destroys sparsity and graph-theoretic notions such as connectivity, motivating discrete diffusion.
  • Discrete diffusion represents categorical transitions with Markov transition matrices that specify probabilities of jumping between classes.
  • DiGress uses Markov transition matrices and their cumulative product to define noisy states and reverse-diffusion computations.
  • Graphs additionally require methods handling varying sizes, permutation equivariance, and the absence of a known tractable universal approximator.

3 DISCRETE DENOISING DIFFUSION FOR GRAPH GENERATION (DIGRESS)

DiGress applies discrete diffusion independently to categorical node and edge types, while a graph transformer predicts clean graphs and supports permutation-aware generation. Its design also enables structural features, likelihood estimation, and marginal-noise comparisons.

  • DiGress represents node and edge attributes as categorical one-hot tensors, treating absent edges as a distinct edge type.
  • Noise is applied independently to each node and edge feature, avoiding a transition matrix over the much larger space of complete graphs.
  • Adding noise samples every node and edge type from categorical distributions defined by separate transition matrices.
  • For undirected graphs, noise is applied to the upper-triangular edge matrix and then symmetrized.
  • The denoising network predicts clean node and edge distributions from a noisy graph and trains with cross-entropy classification losses.
  • A graph transformer incorporates node, edge, and global features, including auxiliary graph-level information.
  • 3.3 EQUIVARIANCE PROPERTIES: DiGress is permutation equivariant and uses a permutation-invariant loss, avoiding costly matching between predicted and target graphs.
  • 3.3 EQUIVARIANCE PROPERTIES: DiGress produces exchangeable graph distributions, making all node permutations equally likely for likelihood-related modeling.

4 IMPROVING DIGRESS WITH MARGINAL PROBABILITIES AND STRUCTURAL

DiGress improves discrete graph diffusion by choosing noise transitions that preserve node and edge-type marginals and by adding structural features available because noisy graphs remain sparse. These enhancements address limitations of uniform noise and graph neural-network representation power.

  • Marginal probabilities: Uniform transitions produce uniform limiting distributions, although graph edge types are usually far from uniform and sparse graphs take many steps to emerge.
  • Marginal probabilities: The proposed prior factorizes into one node distribution and one edge distribution, with the optimal choices given by the training data’s node and edge marginals.
  • Marginal probabilities: Marginal transitions make jumps toward categories in proportion to their training-set frequencies, and experimentally improve over uniform transitions.
  • Structural features augmentation: DiGress inherits graph neural networks’ limited ability to represent structures such as cycles, while more powerful alternatives are more costly and slower to train.
  • Structural features augmentation: Because discrete noisy graphs remain sparse rather than complete, DiGress can compute structural and spectral descriptors at every diffusion step and provide them to the denoising network.
  • Structural features augmentation: Including auxiliary features experimentally improves performance, although they are not required for a good model and their computational cost matters for larger graphs.

5 CONDITIONAL GENERATION

DiGress supports graph generation conditioned on graph-level properties without retraining the denoising network for each new conditioning property. It uses a learned regressor to guide the unconditional reverse diffusion process toward target properties.

  • Conditional generation is important for applications such as designing molecules that are easy to synthesize and active on specific targets.
  • Training the denoising network with target properties requires retraining when the conditioning properties change.
  • DiGress introduces discrete guidance inspired by classifier guidance to overcome the need for property-specific retraining.
  • A regressor predicts clean-graph properties from noisy graphs and modulates each reverse-step distribution toward graphs with the desired targets.
  • The conditional reverse process combines the unconditional reverse transition with a target-property likelihood term under the stated noising assumption.
  • The method also extends existing subgraphs through molecular scaffold extension, demonstrated on a simple example.

6 RELATED WORK

DiGress is positioned as the first discrete diffusion model for graphs, contrasting with prior Gaussian-based graph diffusion and related molecule-generation models that operate on 3D point clouds.

  • DiGress is presented as the first discrete diffusion model for graphs, while concurrent work was limited to unattributed graphs.
  • Earlier graph diffusion models used Gaussian noise, with adjacency matrices generated by thresholding continuous values and later extensions supporting node and edge attributes.
  • Several discrete diffusion models had already been proposed for text, images, audio, and attributed point clouds.
  • Molecule-generation diffusion models in 3D generate atomic positions as point-cloud tasks and require conformer data, unlike DiGress’s graph-structure generation.
  • Other non-autoregressive graph generators based on VAEs, GANs, normalizing flows, and categorical flows had not matched autoregressive and motif-based models’ performance.

7 EXPERIMENTS

Experiments evaluate DiGress across general graph, QM9, MOSES, GuacaMol, and conditional-generation settings, comparing it with one-shot and continuous diffusion baselines. The results show strong graph-distribution modeling, scalability to large molecular datasets, and faster training than the continuous model on QM9.

  • Molecule generation: On QM9, DiGress achieves similar results to the continuous model while reaching 99% validity faster on small graphs.Training time is measured as the time needed to reach 99% validity.
  • General graph generation: DiGress captures SBM and planar-graph distributions effectively, with significant improvements over baselines on planar graphs.The evaluation considers validity, uniqueness, novelty, planarity, connectivity, and related graph properties.
  • Large molecular datasets: DiGress is the first one-shot graph model reported to scale to the MOSES dataset.The comparison reports that it outperforms GraphInvent on most metrics without hard-coded validity rules used by other graph-based methods.
  • Large molecular datasets: On GuacaMol, DiGress is the first general graph-generation method reported to achieve correct performance, including on the FCD score.The table reports scores where higher values are better for all metrics.
  • Conditional generation: Conditional generation on QM9 evaluates whether generated molecules match target dipole moments and HOMO values using discrete regression guidance.The procedure samples conditioning pairs from test molecules and estimates generated properties with RDKit conformers and Psi4.

8 CONCLUSION

The paper concludes that DiGress uses discrete graph diffusion to outperform existing one-shot methods and scale to large molecular datasets. Its Gaussian counterpart, ConGress, provides an ablation showing that the discrete process itself contributes to performance, while auxiliary features improve expressivity but add computational considerations.

  • Conclusion: DiGress operates in a discrete space for graph generation and reaches the performance of autoregressive models trained using expert knowledge.The conclusion also states that DiGress outperforms existing one-shot generation methods and scales to larger molecular datasets.
  • Continuous graph denoising diffusion model (ConGress): ConGress uses Gaussian diffusion with the same denoising network as DiGress to isolate the contribution of the diffusion process.Its purpose is to test whether DiGress’s better performance arises from the discrete process rather than only the neural-network design.
  • Continuous graph denoising diffusion model (ConGress): Gaussian diffusion adds noise to continuous node and edge representations, then maps predicted outputs back to categorical graph values with argmax.ConGress is trained by predicting Gaussian noise and sampled through reverse iterations.
  • Continuous graph denoising diffusion model (ConGress): ConGress differs from GDSS by using noise that factorizes independently across nodes and edges, while empirically outperforming GDSS on QM9.The comparison attributes the distinction to the noise model rather than the denoising network.
  • Denoising network and auxiliary features: The graph transformer processes node, edge, and graph-level features, augmented with graph-theoretic, spectral, and molecular descriptors.Cycle counts, Laplacian-derived spectral features, atom valency, and molecular weight are among the auxiliary features used.
  • Denoising network and auxiliary features: Discrete noisy graphs preserve sparsity, enabling structural descriptors during diffusion; these features improve performance but require computational choices for larger graphs.Spectral features require O(n3) eigendecomposition, while cycle features are computed with formulas up to size six.
  • Graphical model and likelihood: The diffusion framework samples graph size from the training distribution, keeps it fixed during diffusion, and admits an evidence lower bound for likelihood estimation.The ELBO decomposes into prior, diffusion, and reconstruction-related terms estimated from categorical distributions and predicted probabilities.

D PROOFS

The proofs establish that DiGress uses permutation-equivariant components to produce exchangeable graph distributions, and derive properties of its posterior, priors, conditioning, and evaluation metrics.

  • Posterior derivation: The true posterior over a previous noisy state is proportional to zt (Qt)′ ⊙ x ¯Qt−1, obtained by combining the Markov transition and Bayes rule.This posterior provides the target distribution used in the discrete diffusion derivation.
  • Permutation equivariance: DiGress’s graph transformer combines permutation-equivariant self-attention, FiLM, pooling, and normalization blocks, so the denoising network is permutation equivariant.The resulting relation is ϕθ(π.Gt, f(π.Gt, t)) = π.ϕθ(Gt, f(Gt, t)).
  • Exchangeability: Permutation equivariance of the noise distribution, denoising network, and reverse transition implies that generated graph distributions are exchangeable.Thus P(X, E) = P(π.X, π.E) for any permutation π.
  • Optimal prior distribution: For product priors over node and edge types, the closest distribution under l2 distance uses the empirical marginal distributions of node and edge types.The proof applies orthogonal projections from graph distributions to node and edge marginals and then to product distributions.
  • Conditional generation: Conditioning on a subgraph is implemented by masking its node and edge features at every reverse step, then restoring the masked entries after each sample update.Permutation equivariance permits choosing the first ns nodes without changing the procedure’s meaning.
  • Evaluation: The reported graph metrics compare generated and test distributions for degree distributions, clustering coefficients, and orbit counts using normalized MMD ratios.The denominator is taken from SPECTRE’s results table, whose reported MMD is actually MMD squared.

F.2 QM9

The QM9 evaluation reports metric caveats, ablations, and novelty considerations. Marginal transitions and auxiliary features improve performance, while novelty is omitted from the main table because QM9 is exhaustively enumerated.

  • Metrics: QM9 validity is measured by converting generated molecules to valid SMILES with RdKit, but charged molecules can be counted as invalid under this procedure.A relaxed definition allowing partial charges gives Jo et al. a small advantage.
  • Ablation study: Marginal transitions improve over uniform transitions, and spectral and structural features further boost performance on QM9 with explicit hydrogens.These effects are reported in the ablation study summarized in Table 6.
  • Novelty: Novelty is not reported for QM9 in the main table because QM9 exhaustively enumerates small molecules satisfying specified constraints.DiGress reaches 33.4% novelty with implicit hydrogens, compared with 40.0% for ConGress.

F.3 MOSES AND GUACAMOL

On MOSES and GuacaMol, the evaluation addresses graph-to-SMILES processing, benchmark metrics, likelihood reporting, and size extrapolation. DiGress extrapolates well on GuacaMol but fails on MOSES.

  • Datasets: Around 20% of GuacaMol training molecules cannot be mapped from SMILES to graphs and back because formal charges and fused rings complicate processing.The authors therefore call for more efficient graph-processing tools to evaluate complex molecules reliably.
  • Metrics: MOSES and GuacaMol evaluation uses validity, uniqueness, novelty, filter score, and additional benchmark metrics derived from generated SMILES.Validity measures basic valency checks, while uniqueness measures distinct, non-isomorphic SMILES strings.
  • Likelihood: DiGress reports test NLL values of 129.7 on QM9 with explicit hydrogens, 205.2 on MOSES, and 308.1 on GuacaMol.Likelihood results are omitted from the MOSES and GuacaMol comparison table because other methods did not report them.
  • Size extrapolation: Size extrapolation is tested by generating molecules with nmax + k atoms for k ∈ [5, 10, 20] and measuring validity and uniqueness across 6144 molecules per setting.All extrapolated molecules are novel because they exceed the training-set size range.
  • Size extrapolation: DiGress performs very well on GuacaMol size extrapolation but completely fails on MOSES, which the authors associate with GuacaMol’s greater size diversity.The network was not designed to be size invariant, and SizeShiftReg is suggested as a possible improvement.

G SAMPLES FROM OUR MODEL

The figures show non-curated DiGress samples across molecular and graph-generation settings, including QM9, GuacaMol, MOSES, planar graphs, and stochastic block-model graphs.

  • Molecular samples: Figure 10 shows non-curated QM9 samples generated with implicit hydrogens and explicit hydrogens.The implicit-hydrogen examples are on top and the explicit-hydrogen examples are on the bottom.
  • Molecular samples: Figure 11 shows non-curated samples from GuacaMol and MOSES, including some disconnected or invalid molecules.The figure passage identifies DiGress as the first non-autoregressive method scaling to these more complex datasets than QM9.
Loading 2209.14734v4…