SeaDAG: Semi-autoregressive Diffusion for Conditional Directed Acyclic Graph Generation

## Abstract

Abstract We introduce SeaDAG, a semi-autoregressive diffusion model for conditional generation of Directed Acyclic Graphs (DAGs). Considering their inherent layer-wise structure, we simulate layer-wise autoregressive generation by designing different denoising speed for different layers. Unlike conventional autoregressive generation that lacks a global graph structure view, our method maintains a complete graph structure at each diffusion step, enabling operations such as property control that require the full graph structure.
Leveraging this capability, we evaluate the DAG properties during training by employing a graph property decoder. We explicitly train the model to learn graph conditioning with a condition loss, which enhances the diffusion model’s capacity to generate graphs that are both realistic and aligned with specified properties.
We evaluate our method on two representative conditional DAG generation tasks: (1) circuit generation from truth tables, where precise DAG structures are crucial for realizing circuit functionality, and (2) molecule generation based on quantum properties.
Our approach demonstrates promising results, generating high-quality and realistic DAGs that closely align with given conditions.

## 1 Introduction

The success of diffusion models in various domains (Dhariwal & Nichol, ; Kong et al., )
has led to significant interest in their application to graph generation (Vignac et al., ; Kong et al., ).
In this work, we focus on conditional Directed Acyclic Graph (DAG) generation.
DAGs are essential and widely used data structures in various domains, including logic synthesis (Li et al., ; Liu & Young, ; Wang et al., ; Pei et al., )
and bioinformatics (Zhou & Cai, ).
Compared to general graphs, DAGs possess an inherent layer-wise structure with intricate node inter-dependencies that can significantly influence the overall graph properties.
In logic synthesis, for example, minor structural alterations in lower layers can propagate errors to higher layers, resulting in substantial functional differences.
Modeling these layer-wise structural features of DAGs requires specially designed model architectures and generation mechanisms (An et al., ).
Recognizing these challenges, many established DAG synthesis and optimization tools (Mishchenko et al., ; Flach et al., ; Li et al., ; Wang et al., ) employ a sequential synthesis approach, allowing for effective propagation and modeling of localized changes at each step on the global DAG structure.

Recent studies have explored DAG generation using Autoregressive (AR) diffusion models (Li et al., ), owing to their improved efficiency and enhanced ability to model node-edge dependencies (Kong et al., ). However, existing approaches generally face the following challenges:
(1) Their strict part-by-part generation impedes information flow from later components to earlier ones, whereas in DAG structures with complex inter-layer interactions, subsequent layer structure can often influence the message passing in preceding layers (Wu & Qian, ).
(2) They lack a global graph structure view until the final generation step. This limitation is particularly problematic in conditional generation scenarios, where graph properties or functions generally cannot be evaluated without a complete structure (Fang et al., ).
This incomplete view of conventional AR methods hinders effective property guidance during both training and sampling (Vignac et al., ).
(3) Many existing works do not employ explicit condition learning during training, with conditional guidance applied only during sampling (An et al., ; Vignac et al., ). However, our
experiments suggest that incorporating explicit graph condition learning during training enables the model to more effectively balance condition satisfaction and graph realism.

Figure: Figure 1: The overview of proposed layer-wise semi-autoregressive diffusion of SeaDAG. Layers are denoised at different speeds depending on their levels in DAG. A complete graph structure is maintained at very step.
Refer to caption: x1.png

To address above issues while preserving the benefits of AR models, we propose SeaDAG, a SEmi-Autoregressive diffusion-based DAG generation model that enables graph property control, as illustrated in Figure 1.
Our approach simulates layer-wise autoregressive generation while being able to output a complete graph at every diffusion step. We achieve this by applying different denoising speeds to nodes and edges within different layers, inspired by recent advances in natural language generation (Wu et al., ). Therefore, layers with higher-noise can be generated conditioned on other less-noisy layers.

In summary, SeaDAG offers several key advantages over existing methods:

(1) SeaDAG fully exploits the hierarchical and layer-wise nature of DAGs. We design a denoising process that mimics sequential AR generation, enabling the model to effectively capture inter-layer dependencies.

(2) SeaDAG evolves all layers simultaneously, albeit at different rates, Unlike the strict part-by-part generation, this simultaneous evolution enables
more flexible generation and message passing among layers.

(3) SeaDAG maintains a complete graph structure at each timestep, akin to one-shot methods.
Leveraging this, we incorporate explicit condition learning by employing a property decoder during training to evaluate graph properties. By using a condition loss, we explicitly teach the model to learn the relationship between DAG structures and properties, which helps the model simultaneously satisfy the conditions while producing realistic graph structures.

To demonstrate the broad applicability of our method, we evaluate it on two significant conditional graph generation tasks from distinct domains. First, we address an important challenge in electronic design automation (Liu et al., ): circuit generation from truth tables. This task was selected due to the pervasive use of DAGs in circuit design, representing a classic application of DAGs in real-world engineering. Second, to showcase our model’s versatility, we tackle molecule generation based on quantum properties, a more general graph generation task. For this application, we convert molecular structures into DAGs using the junction tree representation (Jin et al., ). Notably, our model surpasses many specialized molecule generation models. These results collectively show the robustness of our method to produce realistic DAGs that adhere to specified conditions across diverse domains.

## 2 Methods

### 2.1 Preliminary

Figure: Figure 2: (a) Example AIG and its truth table. (b) Example molecule and its junction tree, where each node represents a chemical substructure. The tree will be further transformed into a DAG.
Refer to caption: x2.png

##### Directed acyclic graph

A directed acyclic graph with $n$ nodes $\mathcal{V}=\{n_{1},n_{2}\dots n_{n}\}$ can be represented as $G=(\mathbf{X},\mathbf{E})$. $\mathbf{X}\in\mathbb{R}^{n\times k_{x}}$ is the node type matrix. Each row $x_{i}\in\mathbb{R}^{k_{x}}$ is a one-hot vector encoding the type of node $n_{i}$ among $k_{x}$ possible types. $\mathbf{E}\in\mathbb{R}^{n\times n\times k_{e}}$ is the edge type matrix. Each entry $e_{ij}\in\mathbb{R}^{k_{e}}$ is a one-hot vector encoding the type of the directed edge from $n_{i}$ to $n_{j}$ among $k_{e}$ possible types. In this work, for a directed edge $e_{ij}$, we refer to $n_{i}$ as the child node and $n_{j}$ as the parent node.
The $i$th row of $\mathbf{E}$ encodes all parents of $n_{i}$, denoted as $\mathrm{Pa}(n_{i})$. The $j$th column encodes all children of $n_{j}$, denoted as $\mathrm{Ch}(n_{j})$.
We define leaf nodes as nodes without children, while root nodes are those without parents. The level of node $n_{i}$ is defined as the length of the longest directed path from any leaf node to $n_{i}$ (Bezek, ):

$$ $\displaystyle\mathrm{level}(n_{i})$ $\displaystyle=\max_{n_{j}\in\mathrm{Ch}(n_{i})}\mathrm{level}(n_{j})+1,\text{ if }n_{i}\text{ is not a leaf node,}$ (1) $\displaystyle\mathrm{level}(n_{i})$ $\displaystyle=0,\text{if }n_{i}\text{ is a leaf node.}$ (2) $$

##### DAG representation of circuits

The And-Inverter Graph (AIG) is a powerful representation of logic circuits.
In an AIG, leaf nodes carry input signals to the circuit, while root nodes produce the circuit’s output signals.
Intermediate nodes are computing units that perform logical conjunction (AND operation) on two binary inputs $a,b\in\{0,1\}$, outputting $a\land b$.
Edge $e_{ij}$ from node $n_{i}$ to $n_{j}$ indicates that the output of $n_{i}$ serves as an input to $n_{j}$. Edges can optionally perform logical negation (NOT operation) on the signal they carry.
This representation naturally forms a DAG structure.
The structure of an AIG uniquely defines its functionality, which can be represented as a canonical truth table mapping all possible combinations of input signals to their corresponding output signals. Figure 2(a) illustrates a simple AIG and its truth table.

This representation is particularly useful because any combinational logic circuits can be expressed using only AND and NOT operations, making AIG a universal and efficient model for circuit analysis and synthesis.
In this work, we generate AIGs that can realize a given truth table functionality. For node types, we have three category ($k_{x}=3$): input gates, AND gates and output gates. For edges, we define three types ($k_{e}=3$): non-existing edges representing the absence of a connection, normal edges for direct connections, and negation edges that perform a logical NOT operation.

##### DAG representation of molecules

We adopt the approach of Jin et al. () to convert molecules into junction trees. This method first extracts valid chemical substructures, e.g. rings, bonds and individual atoms, from the training set. The vocabulary size is the number of node types $k_{x}$. Each molecule is then converted into a tree structure representing the scaffold of substructures. We transform this tree into a DAG by designating the tree root as the DAG root and converting tree edges to directed edges from children to parents. Edges have two types ($k_{e}=2$): absent connections and existing connections. In this work, we generate junction trees of molecules from their properties. Junction trees are subsequently assembled into complete molecules for evaluation. Figure 2(b) shows a molecule and its junction tree. For more details on the construction of junction trees and their conversion to molecules, we refer the reader to Jin et al. ().

### 2.2 Semi-Autoregressive Diffusion for DAG

Figure: Figure 3: Training pipeline. SeaDAG predicts the node and edge type distribution in the clean graph. Apart from the cross-entropy loss, we employ a condition loss to incorporate explicit condition learning during training.
Refer to caption: x3.png

In this section, we introduce the proposed semi-autoregressive diffusion generation for DAG. This approach considers the hierarchical nature of DAGs while maintaining a complete graph structure at every step of the sampling process.
The training pipeline of SeaDAG is illustrated in Figure 3.

##### Discrete graph denoising diffusion

The forward diffusion process independently adds noise to each node $x_{i}$ and each edge $e_{ij}$ from timestep 0 to $T$, where $T$ is the maximum diffusion step. The forward process is defined using transition matrices: $[Q^{t}_{X}]_{ij}=q(x^{t}=\mathbf{e}_{j}|x^{t-1}=\mathbf{e}_{i})$ and $[Q^{t}_{E}]_{ij}=q(e^{t}=\mathbf{e}_{j}|e^{t-1}=\mathbf{e}_{i})$. Here, $\mathbf{e}_{i}$ denotes a one-hot vector with 1 in its $i$th position. Consequently, the node and edge types at time $t$ can be sampled from the following distributions:

$$ $\displaystyle q(x_{i}^{t}|x_{i}^{t-1})$ $\displaystyle={Q_{X}^{t}}^{\prime}x_{i}^{t-1},\ q(e_{ij}^{t}|e_{ij}^{t-1})={Q^ {t}_{E}}^{\prime}e_{ij}^{t-1},$ (3) $\displaystyle q(x_{i}^{t}|x_{i})$ $\displaystyle={\bar{Q}_{X}^{t}}^{\prime}x_{i},\ q(e_{ij}^{t}|e_{ij})={\bar{Q}_ {E}^{t}}^{\prime}e_{ij},$ (4) $$

where $\bar{Q}_{X}^{t}=Q_{X}^{1}\dots Q_{X}^{t}$ and $\bar{Q}_{E}^{t}=Q_{E}^{1}\dots Q_{E}^{t}$. Following Vignac et al. (), we use marginal distribution to define transition matrices: $Q_{X}^{t}=\alpha_{t}\mathbf{I}+(1-\alpha_{t})\mathbf{1}\mathbf{m_{X}},Q_{E}^{t
}=\alpha_{t}\mathbf{I}+(1-\alpha_{t})\mathbf{1}\mathbf{m_{E}}$, where $\mathbf{m_{X}},\mathbf{m_{E}}$ are marginal distributions of node and edge types. We use cosine noise schedule following Nichol & Dhariwal ().

##### Semi-Autoregressive diffusion

To leverage the inherent layer-wise structure of DAGs and the dependency-modeling advantages of sequential generation, we introduce different diffusion speed for different layers. We define the timestep $t\in[0,T]$ as the global timestep. We denote the normalized node level as $l_{i}=\mathrm{level}(n_{i})/\max_{n_{j}\in\mathcal{V}}\mathrm{level}(n_{j})$. We then design a function $\mathcal{T}:[0,T]\times[0,1]\rightarrow[0,T]$ that maps the global timestep $t$ and normalized level $l_{i}$ to a node-specific local timestep $\tau_{i}^{t}=\mathcal{T}(t,l_{i})$ for node $n_{i}$, or an edge-specific local timestep $\tau_{ij}^{t}=\mathcal{T}(t,l_{j})$ for edge $e_{ij}$. By designing $\mathcal{T}$ such that $\mathcal{T}(t,l_{i})>=\mathcal{T}(t,l_{j})$ when $l_{i}>l_{j}$, we assign larger timesteps to nodes at higher levels and edges pointing to higher levels. This configuration results in a bottom-up generation process, where layers at the bottom of the DAG are denoised at a higher speed. Conversely, we can achieve top-down generation by reversing this relationship. In our experiments, we implement $\mathcal{T}$ as:

$$ $\displaystyle\text{Bottom up generation: }\mathcal{T}(t,l)$ $\displaystyle=\text{clip}(\frac{T}{T-\beta(1-l)}(t-\beta(1-l)),0,T)$ (5) $\displaystyle\text{Top down generation: }\mathcal{T}(t,l)$ $\displaystyle=\text{clip}(\frac{T}{T-\beta l}(t-\beta l),0,T),$ (6) $$

where $\beta$ is a hyperparameter and function $\text{clip}(x,a,b)$ clips input $x$ to $[a,b]$. Empirically, we adopt a bottom-up generation approach for AIGs and a top-down generation approach for molecules.

During training, we sample a random global timestep $t$ from $[0,T]$ and sample $G^{t}=(\mathbf{X}^{t},\mathbf{E}^{t})$ from the distribution:

$$ $\displaystyle q(G^{t}|G)$ $\displaystyle=\prod_{1\leq i\leq n}q(x_{i}^{\tau_{i}^{t}}|G)\prod_{1\leq i,j \leq n}q(e_{ij}^{\tau_{ij}^{t}}|G)$ (7) $\displaystyle q(x_{i}^{\tau_{i}^{t}}|G)$ $\displaystyle={\bar{Q}_{X}^{\tau_{i}^{t}}}^{\prime}x_{i},\ q(e_{ij}^{\tau_{ij} ^{t}}|G)={\bar{Q}_{E}^{\tau_{ij}^{t}}}^{\prime}e_{ij}.$ (8) $$

We train a network $f_{\theta}$ to predict the distribution of real graph $G$ from the noisy graph $G^{t}$: $f_{\theta}(G^{t})=(p_{\theta}(\mathbf{X}),p_{\theta}(\mathbf{E}))$. Specifically, we extend the graph transformer architecture from Dwivedi & Bresson (). We employ cross-entropy loss between the predicted distribution and ground truth $G$ to compute the graph reconstruction loss $\mathcal{L}_{graph}$:

$$ $\displaystyle\mathcal{L}_{graph}(\theta)=\sum_{1\leq i\leq n}\text{Cross- Entropy}(x_{i},p_{\theta}(x_{i}))+\sum_{1\leq i,j\leq n}\text{Cross-Entropy}(e _{ij},p_{\theta}(e_{ij})).$ (9) $$

During inference, we can use the predicted distribution to sample $G^{t-1}$ from $G^{t}$:

$$ $\displaystyle p_{\theta}(G^{t-1}|G^{t})$ $\displaystyle=\prod_{1\leq i\leq n}p_{\theta}(x_{i}^{\tau_{i}^{t-1}}|G^{t}) \prod_{1\leq i,j\leq n}p_{\theta}(e_{ij}^{\tau_{ij}^{t-1}}|G^{t}),$ (10) $$

where

$$ $\displaystyle p_{\theta}(x_{i}^{\tau_{i}^{t-1}}|G^{t})$ $\displaystyle=\sum_{k\in\{1\dots k_{x}\}}p_{\theta}(x_{i}^{\tau_{i}^{t-1}}|x_{ i}=\mathbf{e}_{k},G^{t})p_{\theta}(x_{i}=\mathbf{e}_{k}|G^{t})$ (11) $\displaystyle p_{\theta}(x_{i}^{\tau_{i}^{t-1}}|x_{i},G^{t})$ $\displaystyle=p_{\theta}(x_{i}^{\tau_{i}^{t-1}}|x_{i},x_{i}^{\tau_{i}^{t}})= \frac{p(x_{i}^{\tau_{i}^{t}}|x_{i}^{\tau_{i}^{t-1}},x_{i})q(x_{i}^{\tau_{i}^{t -1}}|x_{i})}{q(x_{i}^{\tau_{i}^{t}}|x_{i})}$ (12) $\displaystyle p(x_{i}^{\tau_{i}^{t}}|x_{i}^{\tau_{i}^{t-1}},x_{i})$ $\displaystyle=\sum_{x_{i}^{\tau_{i}^{t-1}+1}}\dots\sum_{x_{i}^{\tau_{i}^{t}-2} }\sum_{x_{i}^{\tau_{i}^{t}-1}}\prod_{\tau=\tau_{i}^{t-1}+1}^{\tau_{i}^{t}}q(x_ {i}^{\tau}|x_{i}^{\tau-1}),$ (13) $$

and $p_{\theta}(e_{ij}^{\tau_{ij}^{t-1}}|G^{t})$ can be similarly computed. Detailed computation is provided in Appendix C.

##### Sampling from SeaDAG

Computing node and edge-specific timesteps requires the node levels in the clean DAG. During training, we have access to the ground truth clean graph $G$ and could directly compute node levels. During sampling, where we start from a random graph, we determine its hierarchical structure by sampling the number of levels and their sizes from distributions observed in the training data. We can then apply Equation 10 to perform backward denoising and generate the final DAG. Detailed sampling algorithm is provided in Appendix D.1.

##### Model equivariance

We can prove that our method is permutation equivariant since the utilized graph generation model is equivariant and the loss is invariant to node permutations. Detailed proofs are provided in Appendix C.

### 2.3 Conditional Generation

Our approach incorporates explicit condition learning by employing a property decoder to compute a condition loss during training. This section details the implementation of these key components.

#### 2.3.1 Condition loss

To incorporate graph properties as generation conditions, we extend our network to accept an additional condition input $cond$: $f_{\theta}(G^{t},cond)=(p_{\theta}(\mathbf{X}),p_{\theta}(\mathbf{E}))$. For AIG generation from truth tables, we concatenate truth table vectors with other node features. Each column of binary values in the truth table serves as an additional feature for the corresponding node. Since the condition truth table only provides signals for the input and output gates, we use all zero signals for the AND gates. In molecule generation from quantum property, we concatenate the desired molecule property with the graph level features.

To enhance the network’s ability to generate graphs that meet given conditions, we introduce a differentiable graph property decoding module $\phi$. This module decodes the graph property from a clean graph.
The implementation of $\phi$ varies based on the application: (1) For AIG generation, we simulate continuous circuit output using softmax-choice wiring, where each gate’s input is a soft distribution over candidate inputs rather than a hard selection. (2) For applications where the graph property is not directly computable, such as molecule generation, we employ a pre-trained prediction model as the decoding module.
Detailed implementations of $\phi$ can be found in Appendix B.3.
During training, we sample a predicted clean graph $\hat{G}$ from the predicted distribution $(p_{\theta}(\mathbf{X}),p_{\theta}(\mathbf{E}))$ using Gumbel-Softmax and decode its property using $\phi$. Then we compute the condition loss $\mathcal{L}_{cond}$ between ground truth property condition $cond$ and the decoded property:

$$ $\displaystyle\mathcal{L}_{cond}(\theta)$ $\displaystyle=\text{LossFunction}(cond,\phi(\hat{G})),$ (14) $$

where LossFunction is Binary Cross Entropy for comparing two binary truth tables and Mean Squared Error for molecule property.
The final loss is the combination of $\mathcal{L}_{graph}$ and $\mathcal{L}_{cond}$:

$$ $\displaystyle\mathcal{L}(\theta)$ $\displaystyle=\mathcal{L}_{graph}(\theta)+\lambda\mathcal{L}_{cond}(\theta),$ (15) $$

where $\lambda$ is a hyperparameter.
Since the $\mathcal{L}_{cond}$ is also invariant, the total loss is still invariant to permutation.
The training algorithm of SeaDAG is presented in Algorithm 1.

Figure: Algorithm 1 SeaDAG training algorithm

#### 2.3.2 Integrating conditon learning into training

Many AR or one-shot approaches to conditional graph generation train an unconditional model and incorporate conditional guidance only during sampling (Vignac et al., ; Kong et al., ). However, we argue that this separation of condition learning from training hinders the model’s ability to balance condition satisfaction with graph realism. Our experiment results suggest that while these methods can generate realistic graphs in unconditional mode, they struggle to maintain graph quality after applying conditional guidance during sampling.
In contrast,
by integrating conditional learning into the training process, our method SeaDAG achieves a more effective balance between adhering to conditions and producing plausible graph structures.

## 3 Related Works

Different diffusion mechanisms have been proposed for graph generation. One-shot generation models apply noise addition and denoising processes across the entire graph structure simultaneously, predicting all nodes and edges at each timestep (Yan et al., ; Vignac et al., ).
In contrast, AR diffusion models generate the graph sequentially, either producing one part of the graph at each diffusion step (Kong et al., ) or having a separate denoising process for each part (Zhao et al., ). These AR approaches offer advantages in generation efficiency and are better at modeling dependencies between nodes and edges by allowing each step to condition on previously generated parts. (Kong et al., ). However, they face challenges such as sensitivity to node ordering (You et al., ) and the production of only partial, incomplete graph structures during the sampling process. This limitation precludes operations that require the entire graph structure, such as validity checks and property guidance (Vignac et al., ; Yu et al., ).
Latent diffusion models have also been explored for graph generation (Zhou et al., ), with studies indicating their potential to enhance performance in 3D graph generation tasks (You et al., ).

## 4 Experiments

In our experiments, we focus on evaluating two key aspects of the methods:
(1) Conditional generation: We assess whether the methods can generate graphs that satisfy the given condition.
(2) Graph quality: We evaluate whether the generated graphs are realistic and resemble real graphs in their distribution.

Figure: Figure 4: Sampled AIG and molecules by SeaDAG and the one-shot diffusion baseline DiGress.
Refer to caption: x4.png

### 4.1 Data and Baselines

##### AIG dataset

We generate a dataset of random AIGs with 8 inputs, 2 outputs and a maximum of 32 gates. For each AIG, we compute its corresponding truth table. The dataset comprises 12950 AIGs in the training set, 1850 in the validation set, and 256 in the test set. The generalization experiments on AIGs with more than 8 input and 2 outputs are available in Appendix A.2.

##### Molecule dataset

For molecule generation, we evaluate SeaDAG on the standard QM9 benchmark (Wu et al., ), which contains molecules with up to 9 heavy atoms. We adopt the standard dataset split, utilizing 100k graphs for training and 20k for validation. We generate 10k molecules for evaluation. We further conduct a molecule optimization experiment using the ZINC dataset (Irwin et al., ), which has 219k molecules in training set and 24k molecules for validation. More dataset statistics are provided in Appendix E.1.

##### Baselines

We evaluate SeaDAG against several recent graph generation diffusion models as well as state-of-the-art molecule generation models.
For one-shot graph diffusion baselines, we compare SeaDAG with SwinGNN (Yan et al., ), EDP-GNN (Niu et al., ), GDSS (Jo et al., ) and DiGress (Vignac et al., ).
For AR graph diffusion baselines, we compare SeaDAG with Pard (Zhao et al., ) and GRAPHARM (Kong et al., ).
For graph diffusion baselines that operate in latent space, we compare SeaDAG with LDM-3DG (You et al., ) and EDM (Hoogeboom et al., ).
For molecule generation baselines, we compare SeaDAG with GraphAF (Shi et al., ), GraphDF (Luo et al., ), MoFlow (Zang & Wang, ), GraphEBM (Liu et al., ) and SPECTRE (Martinkus et al., ).
Detailed implementations for baselines are provided in Appendix E.3.

### 4.2 Conditional generation

**Table 1: AIG generation. The best results are highlighted in bold and the second-best results are underlined.**
| Model | Class | Validity$\uparrow$ | Accuracy$\uparrow$ |
| --- | --- | --- | --- |
| SwinGNN | One-shot | \ul88.29 | 57.40 |
| Pard | Autoreg. | 78.86 | 75.78 |
| DiGress | One-shot | 43.21 | \ul82.07 |
| SeaDAG | Semi-Autoreg. | 92.38 | 89.25 |

##### Conditional AIG generation

Table 1 presents the evaluation results for AIG generation. To achieve conditional generation, we extend baseline models to accept truth tables as additional input. We report two metrics: Validity, which means the percentage of generated AIGs that are structurally valid, and function Accuracy, which means the bit-wise accuracy between the condition truth table and the truth table of the generated AIGs. SeaDAG significantly outperforms baseline models on both metrics.

**Table 2: Conditional generation evaluation on QM9. We report the absolute error between the target and oracle-predicted properties (You et al., ). The best results are highlighted in bold and the second-best results are underlined.**
| Model | $\alpha$ | HOMO | LUMO | Gap | $\mu$ |
| --- | --- | --- | --- | --- | --- |
| Random | 41.00 | 103.30 | 121.83 | 193.36 | 8.40 |
| EDM | 20.15 | 158.70 | 166.20 | 287.00 | 7.01 |
| LDM-3DG | 15.56 | 54.62 | 63.08 | 107.14 | 6.33 |
| LDM-3DG-GSSL | 16.43 | 55.03 | \ul66.53 | 113.15 | 9.22 |
| DiGress | \ul9.23 | \ul31.98 | 105.06 | \ul90.57 | \ul1.49 |
| SeaDAG | 8.85 | 30.91 | 103.03 | 89.70 | 1.33 |

##### Conditional molecule generation

We evaluate conditional molecule generation across five molecule properties: polarizability $\alpha$ ($\text{Bohr}^{3}$), Highest Occupied Molecular Orbital (HOMO) energy (meV), Lowest Unoccupied Molecular Orbital (LUMO) energy (meV), Gap between HOMO and LUMO (meV), and dipole moment $\mu$ (D). Table 2 presents the Mean Absolute Error (MAE) between the target molecular properties and properties of the generated molecules. The random baseline represents the MAE of randomly sampled molecules. SeaDAG achieves the lowest MAE in four out of five property conditions, which underscores SeaDAG’s ability in generating molecules with desired properties.

### 4.3 Graph Quality Evaluation

In addition to evaluating the methods’ ability to meet the conditions, we also assess the realism of the generated graphs and how closely they resemble the real graph distribution.

Figure: Figure 5: Distribution of maximum levels in generated AIGs. SeaDAG with semi-autoregressive diffusion generates AIGs with maximum levels similar to ground truth AIGs, while other two one-shot methods produce significantly shallower AIGs.
Refer to caption: x5.png

Figure: Figure 6: Comparison of a sampled AIG and the function accuracy during the sampling process by DiGress and SeaDAG from the same truth table. SeaDAG is capable of generating AIGs with greater level and complexity, achieving higher function accuracy.
Refer to caption: x6.png

##### Semi-autoregressive diffusion enhances AIG realism.

We analyze the quality of generated AIGs from two aspects: (1) the AIG Validity, which is reported in Table 1, and (2) the distribution of maximum levels in the generated AIGs.
Figure 5 illustrates a comparison between our proposed SeaDAG model, its one-shot variant (trained without layer-wise semi-autoregressive generation), and the one-shot diffusion model DiGress. While DiGress and the one-shot SeaDAG tend to produce shallow AIGs with significantly fewer levels than the ground truth, SeaDAG with semi-autoregressive diffusion achieves a maximum level distribution closely resembling that of the ground truth AIGs.
Figure 6 presents a case study where DiGress and SeaDAG generate an AIG conditioned on the same truth table. SeaDAG is able to generate more complex AIGs with a greater number of levels and obtains higher function accuracy.
These observations indicate that semi-autoregressive generation can help the model to construct more complex AIGs that are more similar to ground truth ones and therefore more capable of realizing the given truth tables.

**Table 3: Molecule quality evaluation on QM9. Other conditional models, such as LDM-3DG and DiGress, exhibit a decline in quality compared to their unconditional counterparts. In contrast, SeaDAG maintains quality comparable to the best models in the unconditional group. Note that higher novelty on QM9 datasets indicates deviation from the training distribution rather than better performance (Vignac & Frossard, ).**
| Generation<br>Mode | Model | Validity$\uparrow$ | NSPDK$\downarrow$ | FCD$\downarrow$ | Unique$\uparrow$ | Novelty |
| --- | --- | --- | --- | --- | --- | --- |
| Unconditional | GraphAF | 74.43 | 0.020 | 5.27 | 88.64 | 86.59 |
| GraphDF | 93.88 | 0.064 | 10.93 | 98.58 | 98.54 |  |
| MoFlow | 91.36 | 0.017 | 4.47 | \ul98.65 | 94.72 |  |
| EDP-GNN | 47.52 | 0.005 | 2.68 | 99.25 | 86.58 |  |
| GraphEBM | 8.22 | 0.030 | 6.14 | 97.90 | 97.01 |  |
| SPECTRE | 87.3 | 0.163 | 47.96 | 35.70 | 97.28 |  |
| GDSS | 95.72 | 0.003 | 2.90 | 98.46 | 86.27 |  |
| GRAPHARM | 90.25 | \ul0.002 | \ul1.22 | 95.62 | 70.39 |  |
| LDM-3DG | 100.0 | 0.009 | 2.44 | 97.57 | 89.89 |  |
| DiGress | \ul99.00 | 0.0005 | 0.36 | 96.66 | 33.40 |  |
| Conditional | LDM-3DG | 100.0 | 0.018 | 4.72 | 81.09 | 92.03 |
| DiGress | \ul99.28 | 0.0004 | \ul0.72 | 96.34 | 47.21 |  |
| SeaDAG | 100.0 | \ul0.002 | 0.36 | \ul93.01 | 55.15 |  |

##### SeaDAG can balance molecule quality and condition satisfaction.

Table 3 presents the evaluation of the quality of generated molecules.
We employ several metrics to assess the plausibility of molecules: Validity is the fraction of valid molecules. Neighborhood subgraph pairwise distance kernel (NSPDK) MMD (Costa & Grave, ) computes the MMD between the generated molecules and the test set, which takes into account both the node and edge features for evaluation. Fréchet ChemNet Distance (FCD) is the difference between training set and generated molecules in distributions of last layer activations of ChemNet.

Additionally, we also report Uniqueness, which is the fraction of the unique and valid molecules, and Novelty, which is the fraction of unique and valid molecules not present in the training set. Note that for QM9 dataset, a higher Novelty score does not indicate better performance, but rather suggests a deviation from the dataset’s distribution, as QM9 comprehensively enumerates molecules within specific constraints (Vignac & Frossard, ).
We evaluate models in two categories: Unconditional group, where molecules are generated without constraints, and Conditional group, where generation is guided by one of the five aforementioned properties and the results represent the average of five separate evaluations.

For the baselines in the Conditional group, LDM-3DG (You et al., ) achieves conditional generation by giving models additional property inputs and DiGress (Vignac et al., ) applys conditional guidance only during sampling stage.
Notably, the conditional variants of LDM-3DG and DiGress exhibit up to 100% deterioration in NSPDK and FCD metrics compared to their unconditional counterparts.
In contrast, SeaDAG achieves the best FCD scores across both conditional and unconditional groups, while its NSPDK performance is comparable to the best results in both groups.

### 4.4 Molecule Optimization via Conditional Generation

**Table 4: Molecule Optimization on ZINC. We report the best property scores achieved by each method. While other methods use optimization algorithms, SeaDAG is solely trained for conditional generation, yet it produces molecules with properties comparable to those of other methods.**
| Model | Optimization Algo. | Penalized logP |  | QED |  |  |  |  |
| --- | --- | --- | --- | --- | --- | --- | --- | --- |
| 1st | 2nd | 3rd |  | 1st | 2nd | 3rd |  |  |
| Train set | N.A. | 4.52 | 4.30 | 4.23 |  | 0.948 | 0.948 | 0.948 |
| ORGAN | Reinforcement Learning | 3.63 | 3.49 | 3.44 |  | 0.896 | 0.824 | 0.820 |
| JT-VAE | Bayesian Optimization | 5.30 | 4.93 | 4.49 |  | 0.925 | 0.911 | 0.910 |
| GCPN | Policy Gradient | 7.98 | 7.85 | 7.80 |  | 0.948 | 0.947 | 0.946 |
| MolecularRNN | Policy Gradient | 10.34 | 10.19 | 10.14 |  | \ul0.948 | 0.948 | 0.947 |
| SeaDAG | N.A. | \ul8.52 | \ul8.35 | \ul8.33 |  | 0.948 | \ul0.947 | \ul0.946 |

We demonstrate a practical application of our conditional DAG generation in the domain of molecule optimization. On the ZINC dataset, we train SeaDAG to conditionally generate molecules based on two properties: penalized logP and Quantitative Estimate of Druglikeness (QED), which are two common target properties for molecule optimization (Popova et al., ). We then sample from SeaDAG with target property scores. Detailed implementations could be found in Appendix E.6.
Without using explicit optimization techniques, SeaDAG achieves top property scores comparable to several optimization-based baselines (Guimaraes et al., ; Jin et al., ; You et al., ) as shown in Table 4.
Notably, for the penalized logP property, SeaDAG attains scores surpassing the highest values observed in the training set. This suggests SeaDAG’s capacity to extrapolate beyond the training distribution by effectively learning the intrinsic relationships between molecular structure and associated properties.

## 5 Conclusion

In this paper, we introduced SeaDAG, a semi-autoregressive diffusion model for conditional DAG generation. Our approach demonstrates significant improvements in generating graphs that are realistic and realize given conditions. Future research could focus on enhancing the method’s efficiency to match that of fully autoregressive models.

## Appendix A More Experiment Results

### A.1 MCTS-Based Refinement for Condition Alignment

We implement an MCTS-based post-processing step to enhance the condition properties of the DAGs generated by the diffusion model.

**Table 5: Conditional generation results of our proposed MCTS-based DAG structure refinement.**
| Model | AIG -<br>Accuracy$\uparrow$ |  | Molecule - MAE$\downarrow$ |  |  |  |  |
| --- | --- | --- | --- | --- | --- | --- | --- |
|  | $\alpha$ | HOMO | LUMO | Gap | $\mu$ |  |  |
| SeaDAG | 89.25 |  | 8.47 | 32.47 | 105.16 | 89.83 | 1.39 |
| SeaDAG + MCTS | 94.76 |  | 7.11 | 21.32 | 89.25 | 77.79 | 0.99 |

##### State representation

Each state is a DAG structure $G=(\mathbf{X},\mathbf{E})$.

##### Action space and transition model

The action space is defined as a set of random graph edits. An action, i.e. a graph edit, for an AIG or a molecule junction tree is defined as follows:

- •
To sample an action for an AIG, we first randomly sample a gate from the AND gates and output gates. We then change the input gates (i.e. the children) of the chosen gate to nodes randomly sampled from possible candidate input gates. Specifically, an AND gate has two inputs and a output gate only requires one input. The candidate gates are the set of gate nodes with lower levels. Finally, for the new edges from the new inputs to the chosen gate, we determine their types by sampling from normal type and negation type.
- •
To sample an action for a molecule junction tree, we first randomly select a node from the junction tree. Then, with a probability of 0.5, we either modify the node’s type or alter its parent node. In the case of type modification, we randomly assign a new type to the selected node. In the case of changing parent, we randomly select a new parent from the nodes at higher levels in the tree.

Applying an action to a state is to modify the DAG structure using the edit defined by the action and result in a new DAG structure. Our design of the action space ensures that the resulting DAG is always valid.

##### Reward function

We employ the property decoder $\phi$ to compute the reward function for a state.

- •
For AIGs, we aim to maximize the function accuracy. Therefore, we use the truth table decoder $\phi$ to decode the output signals of the AIG and compute the accuracy as reward.
- •
For molecules, we aim to minimize the MAE between the molecule property and the target property. Therefore, we employ $\phi$ to predict the molecule property from the junction tree and compute the negative of MAE loss as reward.

##### MCTS Algorithm Structure

Since the action space, namely the set of possible edits to a DAG, is finite but is still very large, we employ the progressive widening strategy (Coulom, ; Chaslot et al., ) to balance adding new children and selecting among existing children. We employ UCB selection strategy (Auer et al., ) to select the best child. In the simulation phase, we employ a random action sampling strategy until reaching the predefined maximum depth limit. Upon reaching this limit, we evaluate the reward of the terminal state and back-propagated it through the tree. We conduct 500 such simulations for each decision point. After these simulations, we select the best child node as the next state. This process is repeated for 50 steps for each DAG.

After the MCTS refinement, we evaluate the resulting DAG structure. If it performs worse than the original DAG, we reject the refinement and retain the original structure.

We evaluate the performance of our MCTS-based DAG structure refinement in Table 5. MCTS is applied to 256 generated AIGs and 600 generated molecule junction trees for each of the five properties, with the aim to improve the function accuracy and property MAE respectively. The MCTS refinement significantly improves performance across all metrics on both tasks.

### A.2 Model Generalization

Figure: Figure 7: Generalization capacity of SeaDAG across diverse AIG configurations. SeaDAG demonstrates robust generalization to AIGs with input and output gate numbers unseen during training, while maintaining stable performance across a diverse range of AIG sizes.
Refer to caption: x7.png

We evaluate SeaDAG’s generalization capacity by testing its ability to generate AIGs with varying numbers of input and output gates, as well as diverse total gate counts. Our model uses truth table columns as node-level features, with a fixed length parameter of 256 ($2^{8}$) rows corresponding to the 8 input gates in the training AIGs. To accommodate AIGs with $N_{\text{input}}>8$, we randomly sample 256 rows from the $2^{N_{\text{input}}}$ rows of the full truth table. For AIGs with $N_{\text{input}}<8$, we pad the truth table to 256 rows by randomly duplicating $256-2^{N_{\text{input}}}$ rows. Then the truth table can be concatenated to node features and the AIG can be generated in the same way.
Figure 7 plots the function accuracy of SeaDAG on AIGs with different number of input gates, output gates and total gates. Although it is only trained on AIGs with 8 input gates and 2 output gates, SeaDAG demonstrates robust performance on AIGs with very different configurations from the training set. Meanwhile, it maintains stable performance across a diverse range of AIG sizes.

### A.3 Ablation study

We conduct ablation study on the two key elements in our method: the condition loss and the semi-autoregressive diffusion scheme.

**Table 6: Ablation study results for AIG generation. Note that Accuracy is calculated after correcting the invalid AIG structures.**
| Condition<br>Loss | Semi-<br>Autoreg. | Validity$\uparrow$ | Accuracy$\uparrow$ |
| --- | --- | --- | --- |
|  | ✔ | 97.34 | 78.06 |
| ✔ |  | 45.25 | 89.84 |
| ✔ | ✔ | \ul92.38 | \ul89.25 |

As shown in Table 6, incorporating condition loss during training significantly improves the function accuracy for AIG generation. This suggests that merely providing the condition as an additional input to the model may be insufficient. The condition loss appears to enhance the model’s ability to learn the relationship between DAG structure and its property conditions.
Conversely, the model without semi-autoregressive generation performs poorly in terms of graph validity (note that we correct invalid AIG graphs when calculating Accuracy). This finding further supports our argument in Section 4.3 that semi-autoregressive diffusion helps the model learn structural features and dependencies within DAGs, leading to the generation of higher quality and more realistic DAG structures.

Table 7 presents the ablation study results for molecule generation. Consistent with our previous findings, the model trained without semi-autoregressive generation shows significant performance degradation across molecule quality metrics. Interestingly, the impact of condition loss on condition satisfaction metrics appears less pronounced in molecule generation compared to AIG generation. We hypothesize that this discrepancy stems from the nature of the property decoders: for junction trees, we employ trained models that may introduce prediction errors, whereas for AIGs, we use precise logic operations. Consequently, the guidance provided by the molecule property decoder may not be as effective as its AIG counterpart. Nonetheless, we can still observe improvements in the MAE metric compared to the ablated models and baselines.

**Table 7: Ablation study results for molecule generation on QM9.**
| Condition<br>Loss | Semi-<br>Autoreg. | Molecule Quality |  | Condition MAE$\downarrow$ |  |  |  |  |  |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| Validity$\uparrow$ | NSPDK$\downarrow$ | FCD$\downarrow$ | Unique | Novelty |  | $\alpha$ | HOMO |  |  |
|  | ✔ | 100.0 | 0.002 | 0.32 | 93.60 | 54.85 |  | 9.42 | 31.30 |
| ✔ |  | 100.0 | 0.018 | 1.98 | 68.75 | 61.47 |  | 21.06 | 33.33 |
| ✔ | ✔ | 100.0 | 0.002 | 0.36 | 93.01 | 55.15 |  | 8.85 | 30.91 |

## Appendix B SeaDAG Parameterization and Training

### B.1 Denoising network implementation

We extend the model employ in Dwivedi & Bresson () and Vignac et al. () to implement our denoising network $f_{\theta}$. First, we extract the graph features of $G^{t}=(\mathbf{X}^{t},\mathbf{E}^{t})$ following Vignac et al. (), resulting in node level feature $\mathbf{F_{x}}\in\mathbb{R}^{n\times d_{x}}$, edge level feature $\mathbf{F_{e}}\in\mathbb{R}^{n\times n\times d_{e}}$ and graph level feature $y\in\mathbb{R}^{d_{y}}$. For clarity of presentation, we omit the timestep superscript $t$ for $\mathbf{F_{x}},\mathbf{F_{e}},y$. These features encode (1) the node and edge types and (2) the graph structure features of $G^{t}$. We refer the reader to Vignac et al. () for details on the structure features. Global timestep $t$ is encoded in graph level feature $y$. Node level $l_{i}$ and node-specific local timestep $\tau_{i}^{t}$ is encoded in node level feature $\mathbf{F_{x}}$.

We then incorporate the condition information into graph features.

##### Truth table condition as node features

Each column in truth tables are a series of {0, 1} values of one input gate or output gate. The signal values for AND gates are unknown in the condition and therefore we first pad 0 for the values for AND gate. For AIGs with 8 input gates, the padded truth table could be represented as $\mathbf{T}\in\{0,1\}^{n\times 2^{8}}$. To compress this representation, we convert each 8-bit sequence in the last dimension of $\mathbf{T}$ to its corresponding integer value. These integer values are then normalized by dividing by 256, resulting in a compressed representation with values in the range [0, 1]. We concatenate the compressed truth table $\mathbf{T}$ with node level features $\mathbf{F_{x}}$. With a slight abuse of notation, we continue to denote these augmented node features as $\mathbf{F_{x}}$.

##### Property condition as graph level features

We concatenate the molecule property condition with the graph level feature $y$. With a slight abuse of notation, we continue to denote the resulting graph level feature as $y$.

##### Model architecture

After the condition information is incorporated into graph features $(\mathbf{F_{x}},\mathbf{F_{e}},y)$, we process the them through several graph transformer layers to update the features. The graph transformer layer is implemented as:

$$ $\displaystyle\mathbf{Q},\mathbf{K},\mathbf{V}$ $\displaystyle=\text{Linear}(\mathbf{F_{x}}),\text{Linear}(\mathbf{F_{x}}), \text{Linear}(\mathbf{F_{x}})$ (16) $\displaystyle s_{E},b_{E}$ $\displaystyle=\text{Linear}(\mathbf{F_{e}}),\text{Linear}(\mathbf{F_{e}})$ (17) $\displaystyle s_{y}^{\mathbf{X}},b_{y}^{\mathbf{X}}$ $\displaystyle=\text{Linear}(\mathbf{y}),\text{Linear}(\mathbf{y})$ (18) $\displaystyle s_{y}^{\mathbf{E}},b_{y}^{\mathbf{E}}$ $\displaystyle=\text{Linear}(\mathbf{y}),\text{Linear}(\mathbf{y})$ (19) $\displaystyle\mathbf{atten}$ $\displaystyle=(s_{E}+1)\frac{\mathbf{Q}\mathbf{K}^{T}}{\sqrt{d}}+b_{E}$ (20) $\displaystyle\mathbf{F_{x}}^{\prime}$ $\displaystyle=\text{Linear}((s_{y}^{\mathbf{X}}+1)\cdot\text{Softmax}(\mathbf{ atten})\mathbf{V}+b_{y}^{\mathbf{X}})$ (21) $\displaystyle\mathbf{F_{e}}^{\prime}$ $\displaystyle=\text{Linear}((s_{y}^{\mathbf{E}}+1)\cdot\mathbf{atten})+b_{y}^{ \mathbf{E}})$ (22) $\displaystyle y^{\prime}$ $\displaystyle=\text{Linear}(\text{Linear}(\text{flatten}(\mathbf{F_{x}}))+ \text{Linear}(\text{flatten}(\mathbf{F_{e}}))+\text{Linear}(y))$ (23) $$

where $d$ is the size of the last dimension of $\mathbf{Q},\mathbf{K},\mathbf{V}$ and $\mathbf{F_{x}}^{\prime},\mathbf{F_{e}}^{\prime},y^{\prime}$ are updated node, edge and graph level features. Layers are connected by layer normalization and residue operation. The output node and edge features at the last layer are passed through linear layers to predict the probability distribution of node and edge types in the clean graph $G$.

### B.2 Training SeaDAG

The training algorithm for SeaDAG is detailed in Algorithm 1. Note that for AIG generation, the truth table implicitly specifies the numbers of input and output gates, thereby partially determining the node types. For example, we can designate the first $N_{\text{input}}$ nodes as input gates and the last $N_{\text{output}}$ nodes as output gates, with the remaining nodes naturally serving as AND gates. $N_{\text{input}}$ and $N_{\text{output}}$ are the numbers of input and output gates that can be inferred from the truth table.
Given this predetermined information, the diffusion of node types becomes unnecessary for AIG graphs. Instead, the model only needs to generate the edge connections. To implement this, we omit the addition of noise to node types during the forward process and maintain fixed node types in the backward process. Consequently, we exclude the node cross-entropy loss from the model’s loss function.

### B.3 Property decoder for condition loss

In this section, we introduce the implementation of property decoder $\phi$.
We denote the probability distribution of node types and edge types predicted by the network $f_{\theta}$ as $p_{\theta}(\mathbf{X})\in\mathbb{R}^{n\times k_{x}},p_{\theta}(\mathbf{E)}\in
\mathbb{R}^{n\times k_{e}}$.

##### AIG function decoder

As discussed in the previous section, the node types are fixed in AIG generation and we only need $\mathbf{E}$ to decode the AIG structure. Given the graph structure of an AIG, the logic function represented by an AIG can be directly determined and the output signals are readily computable. However, to ensure that this operation is differentiable and can be incorporated into the training process, several aspects require special consideration:

- •
Input selection. To determine the inputs (children) for each gate, we employ a softmax operation across all candidate input gates. Candidate gates are those with levels lower than the current gate. For AND gates, we select two inputs, while for output gates, we select one input.
- •
Edge type selection. The type of each edge (normal or NOT) is determined by computing an edge type score. This score is calculated as $\text{Tanh}(p_{\theta}(\mathbf{E)}_{ij1}-p_{\theta}(\mathbf{E)}_{ij2})$, where $p_{\theta}(\mathbf{E)}$ represents the predicted edge type distribution from nodes $i$ to $j$. A positive score indicates a higher likelihood of a normal edge, while a negative score suggests a higher probability of a NOT edge.

Utilizing the aforementioned differentiable operations, we can compute the output signals as continuous values. The decoded output signals are then compared against the ground truth output signals specified in the condition truth table to compute the condition loss using BCE. Note that the loss computation only involves the output signal portion, as the input signals, which are all possible combinations of input values, are the same for every AIG.

##### Molecule property decoder

Since molecular properties cannot be directly decoded from the molecular structure, we train a separate property prediction model $\phi$ for each of the five condition properties. The architecture of these models is identical to that of the denoising network $f_{\theta}$, with two difference:(1) $\phi$ takes clean graphs as input rather than the noisy graphs used by $f_{\theta}$. (2) $\phi$ outputs the predicted molecular property.
During the training process, we sample a discrete graph from the predicted distributions $p_{\theta}(\mathbf{X})$ and $p_{\theta}(\mathbf{E})$ using the Gumbel-Softmax technique, which allows us to maintain differentiability while working with discrete graph structures. The sampled graph serves as the input to $\phi$ and the predicted value is compared against the property condition using MSE loss.

## Appendix C Proofs

##### Proof of Equation 10

During inference, we use the predicted distribution to sample $G^{t-1}$ from $G^{t}$:

$$ $\displaystyle p_{\theta}(G^{t-1}|G^{t})$ $\displaystyle=\prod_{1\leq i\leq n}p_{\theta}(x_{i}^{\tau_{i}^{t-1}}|G^{t}) \prod_{1\leq i,j\leq n}p_{\theta}(e_{ij}^{\tau_{ij}^{t-1}}|G^{t}).$ (24) $$

To compute $p_{\theta}(x_{i}^{\tau_{i}^{t-1}}|G^{t})$, we marginalize over the network predictions:

$$ $\displaystyle p_{\theta}(x_{i}^{\tau_{i}^{t-1}}|G^{t})$ $\displaystyle=\sum_{k\in\{1\dots k_{x}\}}p_{\theta}(x_{i}^{\tau_{i}^{t-1}}|x_{ i}=\mathbf{e}_{k},G^{t})p_{\theta}(x_{i}=\mathbf{e}_{k}|G^{t}),$ (25) $$

where $p_{\theta}(x_{i}=e_{k}|G^{t})$ is the network prediction and $p_{\theta}(x_{i}^{\tau_{i}^{t-1}}|x_{i}=e_{k},G^{t})$ is computed as follows:

$$ $\displaystyle p_{\theta}(x_{i}^{\tau_{i}^{t-1}}|x_{i},G^{t})$ $\displaystyle=p_{\theta}(x_{i}^{\tau_{i}^{t-1}}|x_{i},x_{i}^{\tau_{i}^{t}})= \frac{p(x_{i}^{\tau_{i}^{t}}|x_{i}^{\tau_{i}^{t-1}},x_{i})q(x_{i}^{\tau_{i}^{t -1}}|x_{i})}{q(x_{i}^{\tau_{i}^{t}}|x_{i})}.$ (26) $$

$q(x_{i}^{\tau_{i}^{t}}|x_{i})$ and $q(x_{i}^{\tau_{i}^{t-1}}|x_{i})$ could be computed from Equation 4. $p(x_{i}^{\tau_{i}^{t}}|x_{i}^{\tau_{i}^{t-1}},x_{i})$ is computed as follows:

$$ $\displaystyle p(x_{i}^{\tau_{i}^{t}}|x_{i}^{\tau_{i}^{t-1}},x_{i})$ $\displaystyle=p(x_{i}^{\tau_{i}^{t}}|x_{i}^{\tau_{i}^{t-1}})$ (27) $\displaystyle=\sum_{x_{i}^{\tau_{i}^{t-1}+1}}p(x_{i}^{\tau_{i}^{t}}|x_{i}^{ \tau_{i}^{t-1}+1},x_{i}^{\tau_{i}^{t-1}})q(x_{i}^{\tau_{i}^{t-1}+1}|x_{i}^{ \tau_{i}^{t-1}})$ (28) $\displaystyle=\sum_{x_{i}^{\tau_{i}^{t-1}+1}}p(x_{i}^{\tau_{i}^{t}}|x_{i}^{ \tau_{i}^{t-1}+1})q(x_{i}^{\tau_{i}^{t-1}+1}|x_{i}^{\tau_{i}^{t-1}})$ (29) $\displaystyle=\sum_{x_{i}^{\tau_{i}^{t-1}+1}}\sum_{x_{i}^{\tau_{i}^{t-1}+2}}p( x_{i}^{\tau_{i}^{t}}|x_{i}^{\tau_{i}^{t-1}+2})q(x_{i}^{\tau_{i}^{t-1}+2}|x_{i} ^{\tau_{i}^{t-1}+1})q(x_{i}^{\tau_{i}^{t-1}+1}|x_{i}^{\tau_{i}^{t-1}})$ (30) $\displaystyle=\sum_{x_{i}^{\tau_{i}^{t-1}+1}}\dots\sum_{x_{i}^{\tau_{i}^{t}-2} }\sum_{x_{i}^{\tau_{i}^{t}-1}}\prod_{\tau=\tau_{i}^{t-1}+1}^{\tau_{i}^{t}}q(x_ {i}^{\tau}|x_{i}^{\tau-1}).$ (31) $$

$q(x_{i}^{\tau}|x_{i}^{\tau-1})$ could be computed from Equation 3. $p_{\theta}(e_{ij}^{\tau_{ij}^{t-1}}|G^{t})$ could be calculated likewise.

##### Proof of model equivariance

In this section, we prove that the network we use is equivariant to node permutations. For any node permutation $\sigma:[n]\rightarrow[n]$, $(\sigma\star\mathbf{X})_{\sigma(i),\dots\sigma(n)}=\mathbf{X}_{i,\dots,n}$ and $(\sigma\star\mathbf{E})_{\sigma(i)\sigma(j)k}=\mathbf{E}_{ijk}$.
Then for graph $G^{t}=(\mathbf{X}^{t},\mathbf{E}^{t})$, we can prove the following:

- •
Equivariant feature extraction: the graph features are either permutation equivariant (node level and edge level features) or permutation invariant (graph level features). If the features of $G^{t}$ are ($\mathbf{F_{x}},\mathbf{F_{e}},y$), the features for $\sigma\star G^{t}$ would be ($\sigma\star\mathbf{F_{x}},\sigma\star\mathbf{F_{e}},y$).
- •
Equivariant condition feature: we can easily prove that the truth table condition for AIG is permutation equivariant, i.e. the truth table for $\sigma\star G^{t}$ being $\sigma\star\mathbf{T}$, and the molecule property condition is permutation invariant.
- •
Equivariant model architecture: the operations used in the network, i.e. Linear function, self-attention, layer normalization and residue operation, are all permutation equivariant.

Therefore, the entire model is equivariant to node permutations: $f_{\theta}(\sigma\star G^{t},\sigma\star cond)=\sigma\star f_{\theta}(G^{t},cond)$.

##### Proof of loss invariance

We employ graph CrossEntropy loss $\mathcal{L}_{graph}$ and condition loss $\mathcal{L}_{cond}$ during training. Based on the equivariance of $f_{\theta}$ proved above, we can prove $\mathcal{L}_{graph}$ is invariant to permutation.

$$ $\displaystyle\mathcal{L}_{graph}(\sigma\star G,f_{\theta}(\sigma\star G^{t}, \sigma\star cond))=$ $\displaystyle\sum_{1\leq i\leq n}\text{Cross-Entropy}((\sigma\star\mathbf{X})_ {i},(\sigma\star p_{\theta}(\mathbf{X}))_{i})$ $\displaystyle+\sum_{1\leq i,j\leq n}\text{Cross-Entropy}((\sigma\star\mathbf{E })_{ij},(\sigma\star p_{\theta}(\mathbf{E}))_{ij})$ (32) $\displaystyle=$ $\displaystyle\sum_{1\leq i\leq n}\text{Cross-Entropy}(\mathbf{X}_{i},p_{\theta }(\mathbf{X})_{i})$ $\displaystyle+\sum_{1\leq i,j\leq n}\text{Cross-Entropy}(\mathbf{E}_{ij},p_{ \theta}(\mathbf{E})_{ij})$ (33) $\displaystyle=$ $\displaystyle\mathcal{L}_{graph}(G,f_{\theta}(G^{t},cond))$ (34) $$

For the truth table decoder for AIG: $\phi(G)=\mathbf{T}$, the operation is equivariant: $\phi(\sigma\star G)=\sigma\star\mathbf{T}=\sigma\star\phi(G)$. Therefore, we can prove $\mathcal{L}_{cond}$ for AIG generation is permutation invariant:

$$ $\displaystyle\mathcal{L}_{cond}(\sigma\star cond,\sigma\star\hat{G})$ $\displaystyle=\text{BCE}(\sigma\star cond,\phi(\sigma\star\hat{G}))$ (35) $\displaystyle=\text{BCE}(\sigma\star cond,\sigma\star\phi(\hat{G}))$ (36) $\displaystyle=\text{BCE}(cond,\phi(\hat{G}))$ $\displaystyle\leftarrow\text{ Invariant BCE loss}$ (37) $\displaystyle=\mathcal{L}_{cond}(cond,\hat{G})$ (38) $$

For the molecule property decoder, $\phi$ has the same equivariant model structure as $f_{\theta}$ and is permutation invariant: $\phi(\sigma\star G)=\phi(G)$. Similarly, we can prove its invariance:

$$ $\displaystyle\mathcal{L}_{cond}(cond,\sigma\star\hat{G})$ $\displaystyle=\text{MSE}(cond,\phi(\sigma\star\hat{G}))$ (39) $\displaystyle=\text{MSE}(cond,\phi(\hat{G}))$ $\displaystyle\leftarrow\text{ Invariant MSE loss}$ (40) $\displaystyle=\mathcal{L}_{cond}(cond,\hat{G})$ (41) $$

In conclusion, the total training loss is invariant to node permutation.

## Appendix D Sampling from SeaDAG

### D.1 Sampling algorithm

To sample a DAG from SeaDAG, we first sample the number of levels in the DAG: $N\sim p(N)$, where $p(N)$ is the distribution of number of levels observed in the training set. Then we sample the size, i.e. the number of nodes, for each level: $M_{i}\sim p(M_{i}|i),\text{for }i=0,1,...,N-1$, where $i$ is the level index, $M_{i}$ is the level size and $p(M_{i}|i)$ is the level size distribution of level $i$ in the training set.
However, for AIG generation, the sizes of the first and last levels are predetermined by the truth table condition. The size of the first level is set to $N_{\text{input}}$ which is the number of input gates and the size of the last level is set to $N_{\text{output}}$ which is the number of output gates. In the case of molecule generation, the size of the last level is set to one because of the tree structure of junction trees. Consequently, the sizes of these particular levels are not sampled but are instead predefined.

Once the number of levels and their respective sizes are determined, we can determine the level assignment $l_{i}$ for each node $i$. Subsequently, we sample an initial random graph based on the marginal distributions of node types $\mathbf{m_{X}}$ and edge types $\mathbf{m_{E}}$ and use the denoising model $f_{\theta}$ to gradually remove noise from the random graph. Algorithm 2 illustrates the above process.

Figure: Algorithm 2 SeaDAG sampling algorithm

### D.2 AIG generation specification

We now detail the procedure for parsing an AIG from the generated DAG $G=(\mathbf{X},\mathbf{E})$ obtained from Algorithm 2. As previously discussed, the node types are predetermined during AIG generation, so we only need to parse the gate connections.
For each AND gate $i$, we sample its two inputs from its children set $\mathrm{Ch}(n_{i})$, which is defined by the $i$-th column of $\mathbf{E}$. The edge from a child gate $j$ to gate $i$ is a normal edge if $\text{argmax}(\mathbf{E}_{ji})=1$ or a negation edge if $\text{argmax}(\mathbf{E}_{ji})=2$. If $|\mathrm{Ch}(n_{i})|<2$, we introduce a new input gate to the AIG that constantly outputs a signal of 0, and connect this new gate to gate $i$. For output gates, we sample one input for each in a similar manner.
Once the inputs have been determined for each AND gate and output gate, we remove floating gates from the AIG, which are defined as the AND gates and input gates that are not in the cone of any output gates. Finally, we simulate the resulting AIG to obtain its output for evaluation. For all baselines and our model, we generate 10 AIGs for a truth table and take the one with highest function accuracy.

### D.3 Molecule generation specification

To parse a molecule junction tree from the generated DAG $G=(\mathbf{X},\mathbf{E})$, we first determine the node type for every node by computing $\text{argmax}(\mathbf{X}_{i})$. Next, starting from the nodes at lower levels, we sequentially determine the children of each node $i$ by selecting the nodes in $\mathrm{Ch}(n_{i})$ that have not yet been assigned a parent. We then designate the node without a parent as the root of the junction tree. In cases where multiple nodes lack a parent, we randomly assign a parent from nodes at higher levels for all such nodes except the one at the highest level, which becomes the root of the tree. Once we obtain the junction trees, we follow the methodology outlined by Jin et al. () to assemble these trees into complete molecules for subsequent evaluation.

## Appendix E Experiment Settings

### E.1 Dataset statistics

**Table 8: Dataset information.**
| Dataset | #Training graphs | #Valid. graphs | #Test graphs | Average #nodes | Node types | Edge types |
| --- | --- | --- | --- | --- | --- | --- |
| AIG | 12950 | 1850 | 3700 | 21.00 | 3 | 3 |
| QM9 | 96663 | 19659 | 10000 | 5.36 | 1839 | 2 |
| ZINC | 218969 | 24333 | 4973 | 14.38 | 780 | 2 |

We list the statistics of the datasets in Table 8.

### E.2 Training parameters for SeaDAG

For AIG generation, we choose $T=500,\lambda=1.,\beta=32$ and use $8$ graph transformer layers in the network $f_{\theta}$. We train the model for 1000 epochs with learning rate 0.0002 and batch size 256. We use AdamW optimization (Loshchilov & Hutter, ) with weight decay coefficient $1.0e-12$.
For molecule generation on QM9 (ZINC), we choose $T=500,\lambda=1.,\beta=32$ and use $8$ graph transformer layers in the network $f_{\theta}$. We train the model for 1000 epochs with learning rate 0.0002 and batch size 300 (320). We use AdamW optimization with weight decay coefficient $1.0e-12$. We trained 7 molecule property prediction models in total (5 for QM9 and 2 for ZINC). We use $3$ graph transformer layers in their networks. The remaining training configurations are largely consistent with those used for the denoising network.

### E.3 Baselines

##### AIG generation

We extend our baselines to achieve conditional AIG generation in the following way:

- •
SwinGNN: we incorporate truth table condition into graph features by mapping a truth table to a vector embedding using Linear layers and concatenating the embedding with graph level features. We choose this strategy based on empirical results. We train the model with the following parameters: num_steps = 256, model_depths = [1, 3, 1], patch_size = 4, window_size = 4, batch_size = 512, learning_rate = 0.0001, epoch = 1000, weight_decay = 0. Since SwinGNN is a continuous diffusion model, the generated continuous values need to be discretized. We choose a threshold that leads to the highest function accuracy.
- •
Pard: to incorporate the condition, we treat the truth table as node-level features as in our model. Since Pard is a block-wise autoregressive diffusion model, the output gates are not generated until the last steps and their signals can not be seen by nodes generated before. To make the output signals available during the entire generation process, we flatten the output signals and concatenate it with every node feature.
Different from the original work where the graphs are generated block-by-block and the blocks are divided based on node degrees, we modify Pard to generate DAGs level-by-level like our model. Following their proposed procedure, we train two models: a model to predict the size of the next level to generate and a model that performs diffusion generation for the next level with predicted size.
The level size prediction model is trained with the following parameters: hidden_size = 256, num_layers = 8, batch_size = 256, dropout = 0., epochs = 500, learning_rate = 0.0002 with decay = 0.5 and weight decay coefficient = 0.01.
The local diffusion model is trained with the following parameters: cross-entropy loss coefficient = 0.1, diffusion steps = 100, hidden_size = 256, num_layers = 8, batch_size = 256, dropout = 0., epochs = 500, learning_rate = 0.0002 with decay = 0.5 and weight decay coefficient = 0.01.
We use cosine learning rate scheduler and AdamW optimization for both models.
- •
DiGress: we incorporate the truth table condition in the same manner as in our SeaDAG model, namely by compressing the truth table and concatenating it with node level features. Then we train the model using the following parameters: transition = marginal, diffusion_steps = 500, num_layers = 8, $\lambda=1$, epochs = 1000, batch_size = 640, learning_rate = 0.0002 and weight decay coefficient = 1.0e-12. We use AdamW optimization.

##### Molecule generation

For baselines employed in molecule generation, we follow the methods outlined in the original papers to perform both conditional and unconditional generation. Specifically, for conditional generation using DiGress, we employed the discrete regressor guidance strategy introduced in their work. We first train an unconditional generation model and then train five property regressors for the five property conditions in our settings. These regressors were then utilized to guide conditional generation. For more details on the baselines, we direct the reader to the original works.

### E.4 Conditional generation metrics

We report two metrics when evaluating the conditional AIG generation performance: (1) Validity: Since an AIG is valid as long as the gates receive the correct number of inputs (two for AND gates and one for output gates), we compute the percentage of AND and output gates that have correct number of inputs as the validity of generated AIGs. (2) Accuracy: As discussed in Section B.3, only output signals participate in the computation of loss function and accuracy evaluation since the input signals are always fixed. Therefore, we take the output signals from condition truth tables and those of the generated AIGs and compute the element-wise accuracy.

We report the mean absolute error between the condition properties and the oracle-predicted properties of molecules. To calculate the predicted properties of generated molecules, we closely follow the procedure used in You et al. ().

### E.5 Graph quality evaluation metrics

To evaluate the quality of generated molecules, we employ the metrics in the benchmark proposed by Polykovskiy et al. (). Metrics including Validity, FCD, Unique and Novelty are computed using the provided evaluation codebase. The metric NSPDK are computed using the code provided by Gao et al. ().

### E.6 Molecule optimization via conditional generation

Figure: Figure 8: The top 3 molecules for penalized logP and QED found by SeaDAG.
Refer to caption: x8.png

We demonstrate that we could leverage the conditional generation provided by SeaDAG to generate molecules with optimized properties. We first train SeaDAG on ZINC dataset to generate molecules conditioned on the penalized logP and QED. Then we sample 2000 molecules for each property and take the top 3 for evaluation. For penalized logP, we sample molecules with condition values ranging from 7 to 10. For QED, we sample molecules with condition values ranging from 0.94 to 0.99. Figure 8 presents the top 3 molecules we found for the two properties.

## Appendix F More Sampled Graphs

We provide more DAGs sampled from our SeaDAG in Figure 9 and Figure 10.

Figure: Figure 9: AIGs sampled from SeaDAG.
Refer to caption: x9.png

Figure: Figure 10: Molecules sampled from SeaDAG.
Refer to caption: x10.png

## Peer Reviews

confidence: 3
contribution: 2
initial_rating: 6
presentation: 3
questions: (1) The discrete diffusion loss could contain more variational lower bound terms than cross-entropy. Why do the authors not include the additional terms in the loss calculation?

(2) Why do the authors not report the conditional generation evaluation results of PARD and SwinGNN on QM9 and Zinc molecule dataset?

(3) In the ablation study, where the authors present the results without semi-autoregressive generation, what is the noise scheduling method and how to convert the semi-autoregressive into generate the whole DAG at once? 

(4) For molecule generation, if the authors have already converted the molecular structures into DAGs using the junction tree representation, do this conversion losses information of molecules and lead to potentially downgraded performances?
soundness: 2
strengths: (1) The paper is written with a logical flow and clear exposition, and the authors provide an algorithm pseudocodes that makes the algorithm easy to understand.

(2) The empirical performance of SeaDAG is promising, demonstrating improvements across a range of benchmark tests and scenarios like  AIG and molecules.

(3) The authors have provided additional theoretical analysis to show that SeaDAG is permutation equivariant with the utilized
graph generation and that the proposed loss is invariant to node permutations. 

(4) The authors provide a detailed experiment setting for training SeaDAG in AIG and molecule dataset. The training details with SeaDAG and comparison methods make it easier to replicate the experiments.
summary: The paper proposes SeaDAG which is a semi-autoregressive diffusion-based DAG generation model. SeaDAG utilizes discrete graph denoising diffusion, which operates on the transition metrices of marginal node and edge types. To leverage the layerwise structure of DAGs, SeaDAG will have different diffusion speed for different layers, and the reconstruction loss of the graph is a combined cross entropy of node and edge losses. To incorporate the conditional graph properties and conditional generation, SeaDAG introduces the graph property decoding module, where the training loss will be combined conditional loss and graph loss. The authors evaluate SeaDAG on various experiments including AIG and molecules.
weaknesses: (1) For autoregressive between the layers, the authors introduce the different diffusion speed for noise schedules. However, it is unclear just diffusing between different time steps and layers can capture the interdependencies between the layers. It can hardly be called "autoregressive" since the whole graphs are generated instead of components of graphs generating. 

(2) There is lack of ablation study about how different choices of hyper-paramter $\beta$ or how different diffusion speed could impact the performances. 

(3) While the SeaDAG algorithm is trained on conditional loss terms, the comparison methods in the experiments—such as Pard, DiGress, and SwinGNN—do not explicitly incorporate conditional loss information. These existing baseline methods are graph generative models that do not constrain themselves to generate only DAG data. In fact, many of them tackle a more challenging problem: determining an ordering to generate graphs, which is inherently more complex than generating a DAG where node hierarchy and structure are predefined. Consequently, direct comparisons between SeaDAG and these methods may not be entirely fair.

(4) In addition to the experiment results, the authors should also report the training time and memory sizes of different methods for a fair comparison, for example, training time per epoch, total training time, peak memory usage during training, and model size in terms of parameters.

(5)  During sampling and inference time, the authors mention that the hierarchical structure, as the number of levels and their sizes from distributions, are sampled from the training data. However, there is no adjustment of the number of levels or sizes during the sampling process, which could lead to mode collapsing and losing of diversity of graphs generated.

---

confidence: 4
contribution: 1
initial_rating: 3
presentation: 2
questions: Please provide more details on the similarities between the proposed model and the one in [3].

Line 215: ``*Specifically, we extend the graph transformer architecture from Dwivedi \& Brensson (2020).*'' How do the extensions compare to those described in [1]?

Line 338: ``*We adopt the standard dataset split, utilizing 100k graphs for training and 20k for validation.*'' Does it mean the experiments use the predefined set of training and validation indices as, e.g., in [4] (https://github.com/calvin-zcx/moflow/blob/master/data/valid\_idx\_qm9.json)?

Line 458: "*Note that for QM9 dataset, a higher Novelty score does not
indicate better performance, but rather suggests a deviation from the dataset's distribution, as QM9
comprehensively enumerates molecules within specific constraints (Vignac \& Frossard, 2022).*" Can this statement be verified? Many methods do achieve all metrics close to 100\%.

Why is there no SeaDAG in the `unconditional' part of Table 3?

Are the molecules in Figure 10 only from a model trained on the QM9 dataset?

Please also show a separate set of samples for the Zinc250k dataset.

Why is there no table with molecular metrics also for the Zinc250k dataset? At least in the supplementary material.

DiGress [2] uses the empirical distribution of the number of nodes in the training graphs to sample the number of nodes in the newly generated graphs. For QM9, the model can sample at most nine atoms. However, some molecules in Figure 10 have 12 atoms. How does the model extrapolate the empirical distribution to more than nine atoms?

We have to pick the root node to convert a molecular graph to a tree graph. Did the authors try different choices for the root node? If yes, did they observe any performance deviations?

Regarding the experiments in Figure 6. Can the authors please show a histogram of the number of input gates computed from the ground truth, DiGress, and SeaDAG samples?

[1] Vignac, C., Krawczuk, I., Siraudin, A., Wang, B., Cevher, V. and Frossard, P., DiGress: Discrete Denoising diffusion for graph generation. In The Eleventh International Conference on Learning Representations.

[2] Wu, T., Fan, Z., Liu, X., Zheng, H.T., Gong, Y., Jiao, J., Li, J., Guo, J., Duan, N. and Chen, W., 2023. Ar-diffusion: Auto-regressive diffusion model for text generation. Advances in Neural Information Processing Systems, 36, pp.39957-39974.

[3] Li, M., Shitole, V., Chien, E., Man, C., Wang, Z., Zhang, Y., Krishna, T. and Li, P., LayerDAG: A Layerwise Autoregressive Diffusion Model of Directed Acyclic Graphs for System. In Machine Learning for Computer Architecture and Systems 2024.

[4] Zang, C. and Wang, F., 2020, August. Moflow: an invertible flow model for generating molecular graphs. In Proceedings of the 26th ACM SIGKDD international conference on knowledge discovery \& data mining (pp. 617-626).
soundness: 3
strengths: The paper is experimentally thorough.

The examples of generating logic circuits are nice and interesting.

The design choices are nicely illustrated throughout the text.
summary: The paper proposes a semi-autoregressive discrete denoising diffusion model for the conditional generation of directed acyclic graphs (DAGs). The core part of this model is a combination of the discrete denoising diffusion model for general graphs [1] and the multilevel diffusion model for text [2]. The fundamental motivation behind this design choice is to ensure that each layer in a DAG is denoised at a different speed, which may benefit the performance due to a different degree of interactions between the layers. The secondary (optional) part of the model involves a property decoder to improve the model's ability to generate graphs conditionally on desired properties. The experiments demonstrate the conditional generation of (i) logic circuits based on truth tables and (ii) molecules based on chemical properties, comparing the proposed model with several existing benchmarks.
weaknesses: Major:

The proposed model is a direct combination of [1] and [2]. The authors use [1] as the template for their diffusion model. The main difference to [1] is in the way $p\_\theta(x^{\tau^{t-1}\_i}\_i|x\_i=e\_k,G^t)$ in equation 11 is computed. The authors borrow equation 10 from [2] and the accompanying time step schedules to compute this distribution. Then, they only need to instantiate this equation in the context of Markov transition matrices.

Section 2.1 is nicely written. However, its focus should be somewhere else. The paper is about a semi-autoregressive discrete diffusion model. Therefore, the structure of this section can be, e.g., as follows: (i) discrete diffusion models, (ii) autoregressive diffusion models, and (iii) answering where the semi-autoregressive diffusion model lies between these two cases. The description of domain-specific instances of DAGs should be left in the appendix. In the current form, it is not easy to separate the paper's true methodological contributions and originality in Section 2.2.

Section 3 does not discuss any relation to diffusion models for DAGs. Previous work on multilevel diffusion or semi-(non-)autoregressive models needs to be covered. The authors can look at the related work section in [2] to initiate their search for references.

Minor:

Section I should do a better job articulating the paper's original contributions. For example, it would be better if the authors connect the points (1-3) in the second paragraph with (1-3) in the second last paragraph (though one of these will have to use different points, say, (a-c)).

Please define $p_\theta$ in $f_\theta$ in line 215. If the reader is unfamiliar with [1], it will be hard to understand the redefinition of $f_\theta$ in line 257.

---

confidence: 4
contribution: 2
initial_rating: 5
presentation: 4
questions: ### How is the noise schedule chosen?

In particular, how is $\beta$ selected? Additionally, why was a bottom-up noise schedule used for AIGs and a top-down schedule used for molecules? Is there any intuition as to why one is better than the other for different datasets?

### Is the network $\phi$ (for the conditioning loss) pre-trained or trained end-to-end with the diffusion model?

### Does the conditioning loss and/or semi-autoregressive noise schedule lead to more or less efficient training?

Compared to a uniform noise schedule, does SeaDAG take less time to train or sample from? Compared to classifier-free guidance (and DiGress’ conditional diffusion), does SeaDAG’s conditioning loss take more time to train?
soundness: 2
strengths: ### Clear writing and description of what was done

The manuscript is clearly written. The methodological novelties are clearly described and the procedure is largely made clear by the main text and the thorough supplement. The connection with previous works is also well explained. The experimental section presents the empirical results in a cleanly, and the contents of each experiment are well described.

### Compelling results on utility of non-uniform noise schedule on AIGs (Figure 5)

The results on the AIG graphs showing the utility of non-uniform noise (i.e. semi-autoregressive generation) is fairly convincing. Assuming that the same sampling procedure (as described in the supplement) is used in both SeaDAG panels of Figure 5, this is a rather compelling result which shows a specific benefit of the unique noise schedule.

### Good comparisons to other neural networks to many relevant works

In many of the analyses, there are many other works being compared to, which show that SeaDAG achieves comparable generative performance in the tested datasets. Additionally, the performance metrics used are reasonable diverse and thorough.
summary: This paper proposes SeaDAG, a method for generating directed acyclic graphs (DAGs) using diffusion. At its core, SeaDAG performs diffusion based on the discrete graph-diffusion method DiGress (Vignac, et. al, 2022). In contrast with DiGress, however, SeaDAG performs diffusion differently in two ways.

Firstly, because DAGs have an implicit topological ordering (i.e. every node can be assigned a “level” or “depth”), SeaDAG sets the noise schedule differently for nodes and edges at different levels. For example, nodes with a low level can be given a slow noise schedule, so that in reverse diffusion, it is defined/fixed more quickly than nodes at a high level. Secondly, SeaDAG performs conditional diffusion by training the diffusion model with a conditioning signal in the loss. In particular, during training, a noisy graph is sampled and the diffusion model is trained to reconstruct the clean (denoised) graph. In order to provide a conditioning signal for a property of interest, another model (e.g. a classifier) predicts the property of interest from the denoised graph (for each example during training), and penalizes the model if the property does not match the desired conditioning signal.

The authors demonstrate SeaDAG on a synthetic dataset of circuits, and two molecular datasets (where the molecules are represented in junction-tree format to turn them into DAGs): QM9 and ZINC. The authors show that SeaDAG can produce DAGs (unconditioned or conditioned) which are comparable in quality to some other general graph-diffusion methods.
weaknesses: ### Missing comparison to classifier-free diffusion

One of the two technical contributions of this work is the condition loss, where generating DAGs conditioned on some label is performed using an auxiliary classifier/regressor for that label, during training. One of the major claims that motivates this development is the argument that it is better to build conditioning signals into the training process rather than separating it during inference time (Section 2.3.2).

The most informative and meaningful comparison to demonstrate this claim would be to train SeaDAG on the same datasets (with and without the semi-autoregressive noise schedule), but apply classifier-free diffusion (Ho & Salimans, 2021), where the conditioning signal is fed into the neural network as an input itself (modifying the architecture to feed in the conditioning label embedding in a way that is similar to other classifier-free conditional graph-diffusion works). This method of classifier-free guidance is arguably by far the most commonly used form of conditional diffusion in the literature currently, and it is also a way to build conditional diffusion models by incorporating the conditioning signal at training time.

There doesn’t seem to be any comparison to this classifier-free guidance anywhere, even in Tables 2 – 4, which show results on conditional diffusion. This comparison is crucial to understand the performance of SeaDAG’s condition loss.

### Missing comparison to DiGress or LDM-3DG in Table 4

In addition to missing the comparison with classifier-free guidance, Table 4 (conditional molecular generation) does not compare to DiGress of LDM-3DG. In particular, DiGress is a close analog of SeaDAG because it uses the same diffusion process (minus the semi-autoregressive noise schedule). It would be more meaningful to also show a comparison with these two works on the ZINC dataset.

### Robustness of noise schedule

There aren’t currently results on the robustness of SeaDAG to the noise schedule. Since the noise schedule (which defines the semi-autoregressive diffusion process) is the main contribution of this work, it is important to show the robustness of SeaDAG to the selected noise schedule, as well as some reasoning for why the noise schedule is designed as it is (i.e. equations 5 and 6).

### Somewhat limited ablation studies

The ablation studies in Section A.3 are very appreciated, but it would also be great to include a row in Tables 6 and 7 which shows SeaDAG (same dataset and architecture as the other rows), but trained without the semi-autoregressive noise schedule and without the conditioning loss (and instead use the method employed by DiGress; if this is just equivalent to DiGress, then it would be good to mention that and reproduce that row).

It also seems that from these tables, the conditioning loss seems to actually hurt the quality of the generated objects on average.

### Sampling using SeaDAG starts with more given information

When sampling graphs using SeaDAG, the number of levels in the DAG, as well as the number of nodes in each level, are effectively pre-determined by sampling from the empirical distribution. In comparison, other methods don’t seem to have that information given at inference time. As such, the experiments which compare the quality of DAGs generated by SeaDAG versus other methods are skewed fairly heavily toward SeaDAG’s favor. This makes these experiments quite a bit weaker when trying to show that SeaDAG has comparable or better performance than these other methods.

If there is a way to also inject this same information into other methods, this would be a more fair comparison. As of now, SeaDAG seems to have an unfair advantage because it is given a lot more information about the graph structure at the outset.

### Limited datasets

This is a more minor point, but the datasets are a bit limited in this work. The AIG dataset is interesting, but ultimately fairly simplistic and synthetic. QM9 and ZINC are great real-world datasets, but they are both molecular and each molecule is limited in size. Perhaps there are additional meaningful DAG datasets (with more complexity and interesting conditioning signals) which can be shown, as well.

---

confidence: 3
contribution: 2
initial_rating: 3
presentation: 2
questions: 1. How does unconditional SeaDAG perform on QM9, Guacamol, and MOSES?
2. How does SeaDAG perform in comparison to JT-VAE (with or without conditioning)?
3. How do general-purpose graph generators (e.g. DiGress) perform on QM9 when trained to generate junction trees instead of full graphs?
4. Does SeaDAG encode the layer index into node attributes that are supplied to the model?
5. Is SeaDAG constrained to only produce acyclic graphs? I.e. do you constrain the model to only produce arcs between neighboring levels?
soundness: 2
strengths: - The idea of denoising different levels of a DAG at different speeds is reasonable and intuitive. It appears that this substantially improves the validity of generated graphs.
- Molecule generation is currently one of the few graph-generation tasks that are close to real-world applications. Therefore, I greatly appreciate the results for this task and I believe that they could be emphasized even further.
summary: The paper proposes SeaDAG, a generative model for directed acyclic graphs (DAGs). SeaDAG specializes in graph diffusion to DAGs by varying the noise schedule across layers of the DAG, thereby denoising top (or bottom) layers faster than bottom (or top) layers. In addition, the authors present a scheme for training SeaDAG conditionally: SeaDAG is explicitly conditioned on some properties during training and the authors introduce a novel loss term, called "condition loss". Here, a differentiable decoder attempts to infer the property of the predicted clean graph, and deviations from the provided conditioning are penalized. The method is evaluated in the tasks of generating And-Inverter Graphs and small molecules (via junction trees).
weaknesses: - The scope of this paper is limited to the generation of DAGs. While DAGs are important in many domains and may warrant special treatment, the impact may be somewhat limited in comparison to general-purpose graph generative models.
- Given that this work focuses exclusively on generating DAGs, I would expect an evaluation of baselines that also specifically address this task, e.g. LayerDAG (Li et al., 2024a). This seems especially important since line 45ff appears to frame SeaDAG as an improvement over LayerDAG. This point applies both to experiments and related work.
- For a conditional generation with DiGress, the authors use the guidance approach. This is a post-hoc approach to injecting conditions into a trained unconditional model. For SeaDAG, however, the authors perform conditional training. To ensure a more fair comparison, I would suggest a comparison to a DiGress model that is trained conditionally using the most commonly used approach [1]. If such a comparison is not feasible, it's important to explain why this approach was not used and discuss any limitations of the current comparison. It is worth noting that this approach was also mentioned as a possible extension in the DiGress paper (even though computationally more expensive). Therefore, the point (3) raised in line 53 is debatable.
- JT-VAE is closely related to SeaDAG's approach to molecule generation. I was surprised that it was not included as a comparison partner in Tables 2 and 3. A conditional JT-VAE would also be a highly relevant baseline. If conditioning JT-VAE was not possible, a comparison of JT-VAE and an unconditional SeaDAG model would be crucial for understanding SeaDAG's advantages.
- On the molecule generation task (e.g. Table 3), the compared graph generative models (e.g. DiGress) generate the whole molecular graphs, while SeaDAG generates junction trees. An important baseline would be to use DiGress to generate junction trees directly. It is not clear to me whether the improvements stem from the proposed model or simply from the reformulation of the problem as junction tree generation.
- The AIG-generation task is not convincing. From the paper, It is not clear how challenging this task is and I believe more background should be provided for readers unfamiliar with the area of logic synthesis. In addition, I think benchmarking the proposed method on some existing datasets, e.g. those used by LayerDAG (Li et al., 2024a), would be more convincing.
- The condition loss seems to be a highly heuristic modification. As noted in A3, the empirical evidence for its usefulness remains mostly in the AIG task. It would be useful if the authors provided some theoretical justification for this choice, such as analyzing how the condition loss affects the optimization landscape or relating it to existing theoretical frameworks for conditional generation.
- The paper would benefit from a comprehensive ablation study in the main text. While the authors propose two distinct techniques, namely semi-autoregressive generation and condition loss, they only present empirical results for these methods in combination. Separating and analyzing the individual contributions of each technique would provide clearer insights into their respective impacts on performance. A possible ablation study design could be evaluating models with 1) only semi-autoregressive generation, 2) only condition loss, 3) both techniques, and 4) neither technique (baseline), on a key benchmark task.
- The absence of unconditional generation results represents a missed opportunity. Testing on unconditional tasks, particularly for molecule generation, would have allowed for two key improvements. First, it would have enabled evaluating the semi-autoregressive approach independently from the condition loss. Second, and more significantly, it would have facilitated a more comprehensive evaluation by: 1. Enabling fairer comparisons with existing QM9 literature; 2. Allowing testing on more sophisticated datasets like MOSES and Guacamol, which contain more complex molecular structures than QM9's limit of 9 heavy atoms. This expanded evaluation scope would have provided more compelling evidence for the method's practical applicability.

#### Minor points:
- Line 44-70: This paragraph appears to be an important motivation but is not yet clear to me. In (1), it is unclear what "information flow" refers to, and the statement that this is an issue appears to lack evidence (LayerDAG is not evaluated in experiments).
- The notation on Line 106 suffers from symbol overloading: the variable $n$ is used both to represent the cardinality of vocabulary set $\mathcal{V}$ and as an index variable. This creates confusion, particularly evident in the expression $n_n$ which is mathematically ambiguous. The notation should be revised to use distinct symbols for these different purposes.
- Lines 107 and 108: I suggest avoiding starting a sentence with a mathematical symbol.
- Line 179: I would consider simplifying notation, as there are both $e_i$ (referring to an edge type) and bold $\boldsymbol{e}_i$ (referring to a standard basis vector).
- Eq (3) and (4): I think that one would want to do a right multiplication by $Q^t$, instead of a left multiplication.
- Line 303: GraphARM is cited in the context of conditional guidance. Could the authors elaborate on how GraphARM uses a guidance approach?
- Line 374: It is unclear what the definition of "structural validity" exactly refers to.

[1] Emiel Hoogeboom, Vicctor Garcia Satorras, Clement Vignac, and Max Welling. Equivariant diffusion for molecule generation in 3D. In International Conference on Machine Learning, pp. 8867–8887. PMLR, 2022. 6, 7, 20.