Discrete State Diffusion for Graph Generation

42 concepts23 papers1 proposal

Generative diffusion models have revolutionized how we synthesize continuous data like images and audio. By progressively adding Gaussian noise to an image, a model learns to reverse the corruption process, gradually carving a clean image out of a static void.

However, when we try to apply this same machinery to graphs—such as molecules, social networks, or biological structures—we run into a fundamental mismatch. Graphs are inherently discrete and sparse. An edge either exists or it does not; an atom is either Carbon or Nitrogen.

If you apply continuous Gaussian noise to a graph's adjacency matrix, you quickly destroy its structural identity. A sparse graph with a few clean connections becomes a dense matrix of fractional, noisy values. The model is forced to operate on physically impossible intermediate states, leading to "structural blurriness" and an enormous computational bottleneck.

To solve this, a powerful paradigm has emerged: Discrete State Diffusion. Instead of blurring data with continuous noise, these models corrupt graphs via discrete categorical edits, preserving the structural integrity and sparsity of networks from start to finish.


The Core Mechanism: Discrete Transition Kernels

In a standard diffusion model, the forward process adds a small amount of Gaussian noise at each step. In discrete graph diffusion, the forward process is instead governed by a discrete transition kernel—a Markov chain that dictates how categorical variables change over time.

As surveyed by Cheng-Yi Liu et al. and Hongyang Chen et al., rather than adding a continuous value to an adjacency matrix, the forward process uses transition matrices to randomly flip edge states (from existence to non-existence) or change categorical node types (such as atom or bond categories).

For a binary adjacency matrix representing unweighted edges, this can be modeled using Bernoulli distributions, as demonstrated by Jui-Yi Tsai et al. and Wenzhuo Tang et al.. At each forward step, an edge has a certain probability of being deleted, or a non-edge has a probability of appearing. Because the graph remains a valid discrete structure at every single step of the process, the model never has to resolve the ambiguity of fractional edge values.

Continuous Diffusion:  [1, 0, 1] ---> [0.87, 0.12, 0.93] ---> [0.53, 0.48, 0.51] (Blurry/Dense)
Discrete Diffusion:    [1, 0, 1] ---> [1,    0,    0]    ---> [0,    0,    0]    (Always Binary)

Breaking the Quadratic Bottleneck via Sparsity Preservation

While switching to discrete transitions fixes the representation problem, it introduces a scalability challenge. If a forward process uniformly flips edges with a fixed probability, the graph quickly converges toward a random, uniform noise state (an Erdős–Rényi graph). For a graph with $N$ nodes, a random noisy state is highly dense, containing roughly $O(N^2)$ edges.

Processing dense matrices at every diffusion step destroys the inherent computational advantage of real-world graphs, which are typically sparse. To break this "quadratic wall," researchers altered the destination of the forward diffusion process.

Diffusing to the Empty Graph

Instead of diffusing toward random noise, the EDGE framework proposed by Xiaohui Chen et al. targets an empty graph state. In this framework, the forward process acts as a pure edge-deletion mechanism. As time moves forward, edges are progressively erased until nothing remains.

Because the intermediate states are subsets of the original graph, they are guaranteed to remain sparse throughout the entire trajectory. This allows the model to leverage highly optimized sparse graph operations, dropping the computational complexity from $O(N^2)$ down to roughly $O(M)$, where $M$ is the number of active edges.

Marginal and Absorbing Noise Models

A closely related strategy is to bias the transition kernels toward the dataset's marginal distribution rather than a uniform distribution. As implemented in the DiGress framework by Clement Vignac et al. and refined in continuous-time by Antoine Siraudin et al., the noise process transitions variables toward their average real-world frequencies. Since real-world graphs are sparse, the marginal noise process naturally biases intermediate states toward the absence of edges.

As explained by Yiming QIN, this sparsity-preserving property ensures that the model does not waste capacity trying to recover structure from an impossibly dense, chaotic state. Similarly, mask-based or absorbing-state models—such as those used by Chinmay Prabhakar et al. for biological graphs and Chenguo Lin for layout synthesis—treat missing or unassigned attributes as a special "masked" absorbing state, turning the reverse process into an efficient iterative retrieval task.


The Reverse Process: Denoising as Classification

The shift from continuous to discrete state spaces fundamentally changes how the neural network learns. In continuous diffusion, the network performs regression to estimate a score function or a noise gradient. In discrete diffusion, the reverse process is formulated as a discrete classification task.

As detailed by Dongpeng Hou et al., the denoising network (typically a Graph Neural Network or a specialized Transformer) takes a noisy, discrete graph and uses classification layers to predict the exact categorical states or connection probabilities of the original graph.

Continuous Denoising:  Noisy Graph ---> [Score/Gradient Regression] ---> Denoised Graph
Discrete Denoising:    Noisy Graph ---> [Node/Edge Classification]  ---> Categorical Choices

By avoiding continuous regression on adjacency matrices, the model eliminates the structural ambiguity that causes generated graphs to look deformed or disconnected. Instead, the network acts as an intelligent editor, iteratively deciding whether to add an edge, delete an edge, or swap a node label based on the surrounding context.


Why It Works: Preserving Topological and Semantic Rules

The ultimate benefit of discrete graph diffusion is that it respects the mathematical and physical constraints of the target domain.

When a model operates entirely via categorical edits, it preserves critical graph-theoretic properties like connectivity, degree distributions, and cycle counts throughout the generation process. As Clement Vignac et al. demonstrated, maintaining these explicit structures allows researchers to inject auxiliary graph-theoretic descriptors directly into the model as features—something that is impossible when a graph is drowned in continuous Gaussian noise.

This structural fidelity makes discrete diffusion highly effective across diverse domains:

  • Structural Biology: Generating cell-graphs for immune structures while preserving tissue sparsity (Manuel Madeira et al.).
  • Anatomical Modeling: Synthesizing 3D biological networks like blood vessels that must strictly obey semantic edge-deletion and connectivity rules (Chinmay Prabhakar et al.).
  • Network Resilience: Augmenting sparse topology and dynamics for complex system simulations (Chang Liu et al.).

By aligning the mathematical nature of the diffusion process with the discrete, sparse reality of graph structures, discrete state diffusion provides a principled, scalable, and structurally sound framework for generating the complex networks that underpin our world.

Key Foundational Work

DiGress: Discrete Denoising diffusion for graph generation (2023) — contributed 3 concept elements to this direction.
Efficient and Degree-Guided Graph Generation via Discrete Diffusion Modeling (2023) — contributed 3 concept elements to this direction.
CDGraph: Dual Conditional Social Graph Synthesizing via Diffusion Model (2023) — contributed 2 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_discrete_graph_diffusion_c235558c,
  title = {discrete graph diffusion},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/discrete-graph-diffusion/rdr_c235558cca864ef6a253083c3428e875},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_discrete_graph_diffusion_c235558c_v1,
  title = {discrete graph diffusion},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/discrete-graph-diffusion/rdr_c235558cca864ef6a253083c3428e875/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake