LayerDAG: A Layerwise Autoregressive Diffusion Model for Directed Acyclic Graph Generation

## Abstract

Abstract Directed acyclic graphs (DAGs) serve as crucial data representations in domains such as hardware synthesis and compiler/program optimization for computing systems. DAG generative models facilitate the creation of synthetic DAGs, which can be used for benchmarking computing systems while preserving intellectual property. However, generating realistic DAGs is challenging due to their inherent directional and logical dependencies. This paper introduces LayerDAG, an autoregressive diffusion model, to address these challenges. LayerDAG decouples the strong node dependencies into manageable units that can be processed sequentially. By interpreting the partial order of nodes as a sequence of bipartite graphs, LayerDAG leverages autoregressive generation to model directional dependencies and employs diffusion models to capture logical dependencies within each bipartite graph. Comparative analyses demonstrate that LayerDAG outperforms existing DAG generative models in both expressiveness and generalization, particularly for generating large-scale DAGs with up to 400 nodes—a critical scenario for system benchmarking. Extensive experiments on both synthetic and real-world flow graphs from various computing platforms show that LayerDAG generates valid DAGs with superior statistical properties and benchmarking performance. The synthetic DAGs generated by LayerDAG enhance the training of ML-based surrogate models, resulting in improved accuracy in predicting performance metrics of real-world DAGs across diverse computing platforms. Our implementation is available at https://github.com/Graph-COM/LayerDAG .

## 1 Introduction

A Directed Acyclic Graph (DAG) is a data structure that represents the order of elements (Bang-Jensen & Gutin, ). Unlike linear sequences/chains, which follow a single, straight path from the first to the last element, DAGs
incorporate branching and merging, allowing for the modeling of complex dependencies and hierarchies. This flexibility makes DAGs ideal for representing diverse problem domains such as workload behavior during system execution Sridharan et al. (), operator dependence for program analysis (Phothilimthana et al., ; Luo et al., ; Cortez et al., ), dataflows in circuits (Dong et al., ), task dependencies in project management (Skiena, ; Borenstein, ), and cause-effect relationships (Pearl, ; Tennant et al., ). Additionally, DAGs have recently been used to create challenging benchmarks for evaluating the reasoning capabilities of large language models (Zhu et al., ).

Figure: Figure 1: (a) A real-world DAG (the computation flow for a transformer layer (Vaswani et al., )) encompasses complex logical and directional dependencies. Examples of logical dependencies include 1) dimension matching in matrix multiplications and 2) exactly two matrices pointed to a $\times$ operation. One example of directional dependencies here is softmax(qk)v being computed after qk. (b) Each DAG has a unique layerwise partition, an ordered partition of nodes/edges into a sequence of bipartite graphs. In LayerDAG, each bipartite graph $G^{(l+1)}$ is generated by a diffusion model conditioned on $G^{(\leq l)}$. LayerDAG generates in order the number of new nodes, their attributes, and the new edges.
Refer to caption: x1.png

Despite the benefits of DAGs mentioned above, it is non-trivial to get largescale datasets of real DAGs to enable analysis and optimization. Taking workload execution as an example, DAGs capturing execution behavior can help engineers gain valuable insights into performance metrics such as latency and resource consumption exhibited by candidate systems (Luo et al., ; Cortez et al., ) to optimize the software and hardware accordingly.
However, collecting a workload execution DAG (Sridharan et al., ) for even a single Large Language Model training job, potentially involving trillions of operations, is extremely prohibitive given the size of modern AI platforms. For example, Meta’s Llama3 was trained on a 24K GPU platform (Dubey et al., ). Moreover, very few companies in the world even have access to platforms of this scale. Even if such a large workload execution DAG could be collected, practical constraints such as the storage requirements of the DAGs, and potential to leak private information about the AI model architecture or the training platform configuration further limit DAG sharing. Furthermore, a representative and smaller graph is more effective for most performance optimization tasks.

This work focuses on developing generative models for DAGs, which allows various potential applications. First, being able to be data-driven and generate representative small set of DAGs can be much more compute and memory efficient than a real DAG given repetitive patterns. Second, this could enable data sharing without compromising intellectual property (Gao et al., ; Lin et al., ), thereby promoting software and hardware co-design among different companies (Sridharan et al., ). Third, a conditional DAG generative model can efficiently search the space of valid DAGs for optimization purposes in scenarios such as circuit design (Takagi, ; Dong et al., ), compiler optimization (Aho et al., ; Phothilimthana et al., ), and neural architecture search (NAS) (Zhang et al., ; Li et al., ; An et al., ).

Serving as an abstraction for flows and node dependencies, DAGs pose significant challenges in developing powerful and efficient generative models due to their intrinsic strong directional and logical dependencies, such as control flows, logic gates, and dimension requirements of matrix operations (as illustrated in Fig. 1 (a)). These complexities are further magnified in large-scale DAGs, presenting a unique combination of challenges regarding both scale and logical rules. In contrast, although social networks may be large in scale, they do not exhibit strong dependencies between nodes and edges. At the other end of the spectrum, molecular graphs, whose generation also has received much interest recently, must adhere to chemical rules but are generally smaller in size.

This work proposes the use of autoregressive diffusion models to generate DAGs, aiming to decouple the strong node dependencies in DAGs into manageable units and handle them sequentially. Our model, named LayerDAG, is based on a novel perspective of DAGs: as illustrated in Fig. 1 (b), the partial order of nodes dictated by the DAG structure can be decoupled as a sequence of tokens, each corresponding to a bipartite graph. This perspective enables the natural modeling of directional dependencies in DAGs through autoregression, and the rest is to address the logical dependencies within a set of nodes incomparable (i.e. no ordering relations) according to the partial order in each autoregressive step, where we leverage diffusion models known for effectively capturing multidimensional dependencies (Rombach et al., ; Vignac et al., ). Specifically, the diffusion model is conditioned on previously generated bipartite graphs to generate the next bipartite graph consisting of node attributes and edges.

Our model advances existing DAG generative models in multiple aspects (Zhang et al., ; Li et al., ; An et al., ). Methodologically, although autoregressive models have been adopted by D-VAE (Zhang et al., ) and GraphPNAS (Li et al., ) for DAG generation, they treat either a single node or a node set of constant size as a token. This tokenization method imposes an order between nodes that should be incomparable in the partial order, violating the inductive bias inherent in the DAG structure. We argue that the violation may hurt the generalization capability of generative models. Moreover, D-VAE suffers from a potentially slow generation process by generating one node per iteration. Although GraphPNAS generates multiple nodes per iteration, it uses a mixture of Bernoulli distributions to model intra-set edge dependencies, which is less expressive than diffusion models (Wang et al., ; Pearce et al., ). DiffusionNAG (An et al., ) employs diffusion models to generate only node attributes given a DAG structure. Other diffusion models have been developed for undirected graphs (Niu et al., ; Jo et al., ; Vignac et al., ), but they ignore the directional information in DAGs, while our work demonstrates the necessity of the autoregressive component in modeling directional dependencies in DAGs.

From the application perspective, all the existing works (Zhang et al., ; Li et al., ; An et al., ) focus on generating small DAGs (with $\#$nodes $\leq 24$) for NAS, while our model is capable of generating much larger flow graphs (up to $\sim$ 400 nodes) for system/hardware benchmarking. Overall, our work is the first to use autoregressive diffusion models for DAG generation, aiming to take the advantages of both autoregressive models and diffusion models to model the strong dependencies commonly in DAG data.

We conduct extensive experiments to verify the effectiveness of our model. To assess the model’s ability to learn strong directional and logical rules, we construct a challenging synthetic DAG dataset with injected dependencies for evaluation. Additionally, we employ three real-world datasets— computational graphs on Tensor Processing Units (TPU), flow graphs on Field Programmable Gate Arrays (FPGA), and neural architectures deployed on edge devices — for computing system benchmarking applications. Each dataset contains thousands of DAGs, with individual DAGs comprising up to hundreds of nodes. We compare the validity and statistical properties of the synthetic DAGs generated by our model with baselines. To measure benchmarking performance, we use the synthetic labeled DAGs to train surrogate machine learning (ML) models to predict TPU runtime, FPGA resource usage, and the inference latency of neural architectures for the three application scenarios. These trained surrogate models are then applied to the real-world DAGs for testing. Note that ML-based surrogate models are widely used today to measure the performance of systems and programs without the need for time-consuming simulations (Adams et al., ; Chen et al., ; Mendis et al., ; Sỳkora et al., ; Steiner et al., ; Baghdadi et al., ; Zheng et al., ; Li et al., ; Ahn et al., ; Dubach et al., ; Jia et al., ; Kaufman et al., ; Cao et al., ; Phothilimthana et al., ). We compare the predictions given by the surrogate models with the ground-truth behavior of the DAGs on the corresponding systems. Results show that the surrogate models trained on our generated synthetic DAGs consistently outperform the ones derived with baseline generative models. We also evaluate the extrapolation and interpolation properties of LayerDAG by generating DAGs with labels out of the regime used for training, and LayerDAG demonstrates a superior generalization capability.

## 2 Preliminaries and background

DAG generation A DAG is a directed graph without cycles $G=(\mathcal{V},\mathcal{E},\mathbf{X})$, where $\mathcal{V}=\{1,\cdots,N\}$ is the node set, $\mathcal{E}=\{\cdots,(u,v),\cdots\}$ is the set of directed edges, $\mathbf{X}$ is the node attribute matrix. The edge list $\mathcal{E}$ can also be equivalently represented as the adjacency matrix $\mathbf{A}$. From a collection of DAGs $\{G_{i}\}_{i}\sim\mathbb{P}_{\mathcal{G}}$, we aim to learn $\mathbb{P}_{\mathcal{G}}$ with a generative model $\mathbb{P}_{\mathcal{G}}^{\theta}$, where $\theta$ denotes model parameters. Additionally, many real-world applications, especially computing system benchmarking, involve labeled DAGs $\{(G_{i},y_{i})\}_{i}$ where the labels indicate the performance of the corresponding computing systems. DAG generation conditioning on these labels is also of interest.

Discrete denoising diffusion While our framework is compatible with various diffusion models, we adopt Discrete Denoising Diffusion Probabilistic Model (D3PM) (Austin et al., ) as a proof of concept. We briefly review it here. D3PM (Austin et al., ) generalizes Multinomial Diffusion (Hoogeboom et al., ) in extending DDPM (Ho et al., ) to discrete data. D3PM has two phases, a forward diffusion process and a reverse process. Let each entry of $\mathbf{Z}^{(0)}\in\{0,1\}^{M\times C}$ be an one-hot encoding of a categorical attribute with $C$ possible values. The forward process uses $T$ consecutive steps to progressively corrupt $\mathbf{Z}^{(0)}\rightarrow\mathbf{Z}^{(1)}\rightarrow\cdots$ into purely random variables $\mathbf{Z}^{(T)}$ where $\mathbf{Z}^{(T)}$ can be drawn from a prior categorical distribution. To corrupt $\mathbf{Z}^{(t)}$ into $\mathbf{Z}^{(t+1)}$, it computes and samples from a conditional distribution $q(\mathbf{Z}^{(t+1)}|\mathbf{Z}^{(t)},t)=\mathbf{Z}^{(t)}\mathbf{Q}^{(t+1)}$, where $\mathbf{Q}^{(t+1)}\in\mathbb{R}^{C\times C}$ is a pre-determined transition matrix. A denoising network $\phi_{\theta}$ is trained to predict the uncorrupted data $\mathbf{Z}^{(0)}$ from $(\mathbf{Z}^{(t)},t)$. During the reverse generation process, the trained denoising network is used to convert $\mathbf{Z}^{(T)}$ drawn from the prior distribution into realistic data. DiGress (Vignac et al., ) extends D3PM for undirected molecular graph generation by treating the presence or absence of an edge between a node pair as a binary attribute. The denoising of node attributes and edges takes the form of node classification and link prediction, respectively.

## 3 Methodology

In this section, we present the LayerDAG framework. We first describe our novel view of DAGs, which uniquely transforms a DAG into a sequence of bipartite graphs. This naturally leads to a layerwise tokenization for autoregressive generation, which tackles the directional dependencies in DAGs. In each autoregressive step, we introduce a layerwise diffusion model that is capable of modeling the dependencies between nodes that are incomparable (no by-default order). We also discuss why our way of DAG decomposition is crucial for model generalization. Lastly, as bipartite graphs across different layers hold different levels of complexity, we also propose a flexible quality-efficiency trade-off strategy that adjusts the number of diffusion steps based on layer index.

### 3.1 A unique sequential view of DAGs

The structure of a DAG essentially establishes a partial order among its nodes based on reachability through directed paths. A partially ordered set can be transformed into an ordered sequence while preserving compatibility with the partial order, known as a linear extension or a topological ordering in the context of DAGs (Skiena, ). Previous competitive autoregressive models of DAGs utilize this sequential nature to generate nodes one at a time following a topological ordering (Zhang et al., ). However, topological orderings are not unique. This may compromise the model’s effectiveness and efficiency. We leave a dedicated discussion about the issue to Section 3.3.
On the other hand, non-autoregressive models like diffusion models may be sub-optimal for not explicitly modeling the sequential nature of DAGs.

We map DAGs into a unique sequence by extending topological orderings from a sequence of singleton subsets to general subsets. A DAG is guaranteed to have a set of source nodes, i.e., the nodes are not destinations of any edges, and we denote them by $\mathcal{V}^{(1)}$. Iteratively, we take $\mathcal{V}^{(l+1)}\subset\mathcal{V}\setminus\mathcal{V}^{(\leq l)}$ to be the set of nodes whose predecessors are in $\mathcal{V}^{(\leq l)}$, where $\mathcal{V}^{(\leq l)}=\bigcup_{i=1}^{l}\mathcal{V}^{(i)}$. An implied property is that for each $v\in\mathcal{V}^{(l+1)}$, there exists $u\in\mathcal{V}^{(l)}$ such that $(u,v)\in\mathcal{E}$. In addition, for each $u\in\mathcal{V}^{(l)}$, the longest path from source nodes to it has a length of $l-1$. It follows that $(\mathcal{V}^{(1)},\mathcal{V}^{(2)},\cdots,\mathcal{V}^{(L)})$ forms an ordered partition of $\mathcal{V}$ the moment $\mathcal{V}^{(L+1)}=\emptyset$ (Fig. 1 (b)). We refer to $\mathcal{V}^{(1)},\mathcal{V}^{(2)},\cdots,\mathcal{V}^{(L)}$ as layers and $L$ as the number of layers. For each layer depth $1\leq l\leq L-1$, we also take $\mathcal{E}^{(l+1)}=\{(u,v)\in\mathcal{E}|u\in\mathcal{V}^{(\leq l)},v\in
\mathcal{V}^{(l+1)}\}$, and $(\mathcal{E}^{(2)},\mathcal{E}^{(3)},\cdots,\mathcal{E}^{(L)})$ forms an ordered partition of $\mathcal{E}$. This layerwise partition naturally extends to arbitrary node and edge attributes. Furthermore, this way of construction is unique and allows reconstructing the original DAG from the sequence $\left(\mathcal{V}^{(1)},(\mathcal{V}^{(\leq 1)}\cup\mathcal{V}^{(2)},\mathcal{
E}^{(2)}),\cdots,(\mathcal{V}^{(\leq L-1)}\cup\mathcal{V}^{(L)},\mathcal{E}^{(
L)})\right)$, where $(\mathcal{V}^{(\leq l)}\cup\mathcal{V}^{(l+1)},\mathcal{E}^{(l+1)})$ is a bipartite graph whose edges point from one part to another part. Such an invertible process of converting a raw data sample into a sequence is known as tokenization in the context of generative models, with notable examples being subwords for language models (Sennrich et al., ) and patches for image generation (Peebles & Xie, ). Essentially, layerwise partition leads to a layerwise tokenization for DAGs.

### 3.2 LayerDAG

Autoregressive generation The layerwise tokenization motivates the following factorization for a probability distribution $\mathbb{P}\left(G\right)$ of DAGs. Let $G=(\mathcal{V},\mathbf{X},\mathbf{A})$ be a DAG. In analogy to $\mathcal{V}^{(l)}$ and $\mathcal{V}^{(\leq l)}$, we define $\mathbf{X}^{(l)}$, $\mathbf{X}^{(\leq l)}$, $\mathbf{A}^{(l)}$, and $\mathbf{A}^{(\leq l)}$. In addition, we define $G^{(l)}=\left(\mathcal{V}^{(l)},\mathbf{X}^{(l)},\mathbf{A}^{(l)}\right)$ and $G^{(\leq l)}=\left(\mathcal{V}^{(\leq l)},\mathbf{X}^{(\leq l)},\mathbf{A}^{(
\leq l)}\right)$. Then, we have

$$ $\displaystyle\mathbb{P}\left(G\right)$ $\displaystyle=\prod_{l=0}^{L-1}\mathbb{P}\left(G^{(l+1)}\Bigm{|}G^{(\leq l)}\right)$ $\displaystyle=\prod_{l=0}^{L-1}\mathbb{P}\left(|\mathcal{V}^{(l+1)}|\Bigm{|}G^ {(\leq l)}\right)\mathbb{P}\left(\mathbf{X}^{(l+1)}\Bigm{|}G^{(\leq l)},| \mathcal{V}^{(l+1)}|\right)\mathbb{P}\left(\mathbf{A}^{(l+1)}\Bigm{|}G^{(\leq l )},\mathbf{X}^{(l+1)}\right)$ $$

This factorization naturally leads to a layerwise autoregressive generation framework. Iteratively, to generate the $(l+1)^{\text{th}}$ layer, it first predicts the number of new nodes with $p_{\theta}\left(|\mathcal{V}^{(l+1)}|\mid G^{(\leq l)}\right)$. Then it generates the node attributes with $p_{\theta}\left(\mathbf{X}^{(l+1)}\mid G^{(\leq l)},|\mathcal{V}^{(l+1)}|\right)$. Finally, it generates the edges with $p_{\theta}\left(\mathbf{A}^{(l+1)}\mid G^{(\leq l)},\mathbf{X}^{(l+1)}\right)$. The generation process terminates when $|\mathcal{V}^{(l+1)}|$ is predicted to be 0. With layerwise autoregressive generation, this framework potentially allows better generalization to unseen values of $L$ during generation (layer generalization).

Layerwise diffusion-based generation To preserve the uniqueness of the layerwise tokenization, we need to generate the set of node attributes and edges in the bipartite graph $G^{(l+1)}$ as a whole by modeling $p_{\theta}\left(\mathbf{X}^{(l+1)}\mid G^{(\leq l)},|\mathcal{V}^{(l+1)}|\right)$ and $p_{\theta}\left(\mathbf{A}^{(l+1)}\mid G^{(\leq l)},\mathbf{X}^{(l+1)}\right)$ as set-level generations. This requires capturing complex dependencies between the nodes attributes and edges in the sets, which is crucial for the applications like system and circuit design, where strict logical rules are prevalent, and rule violations can accumulate and propagate over layers of generation. To tackle this issue, we adopt diffusion models for multiple rounds of set refinement in the generation of $G^{(l+1)}$. We employ two separate diffusion processes for node attribute $\mathbf{X}^{(l+1)}$ generation and structure $\mathbf{A}^{(l+1)}$ generation, as suggested by Li et al. (). For simplicity, we focus on categorical node attributes in this work, which find abundant real-world applications like operator types in computational graphs, and thus adopt D3PM (Austin et al., ). Our approach can be extended to handle real-valued attributes by combining discrete diffusion with continuous diffusion, as demonstrated in previous works (Vignac et al., ; Hua et al., ). For more details on layerwise diffusion, see Appendix A.

Implementation LayerDAG consists of three separate modules $p_{\theta}\left(|\mathcal{V}^{(l+1)}|\mid G^{(\leq l)}\right)$, $p_{\theta}\left(\mathbf{X}^{(l+1)}\mid G^{(\leq l)},|\mathcal{V}^{(l+1)}|\right)$, and $p_{\theta}\left(\mathbf{A}^{(l+1)}\mid G^{(\leq l)},\mathbf{X}^{(l+1)}\right)$, whose parameters are shared across layers. All three modules involve a DAG encoder. We use an off-the-shelf bidirectional message passing neural network (BiMPNN) (Wen et al., ), which has been proven effective for encoding directed graphs in hardware systems (Wang et al., ). A single BiMPNN layer updates node representations with synchronous message passing over both the directed edges and their reversed counterparts: $\sigma\left(\mathbf{A}\mathbf{H}\mathbf{W}_{\text{forward}}+\mathbf{A}^{\top}
\mathbf{H}\mathbf{W}_{\text{reverse}}+\mathbf{H}\mathbf{W}_{\text{self}}\right)$, where $\sigma$ is a non-linear layer, $\mathbf{H}$ is the node representation matrix, and $\mathbf{W}$’s are learnable weight matrices. Both layer size generation $p_{\theta}\left(|\mathcal{V}^{(l+1)}|\mid G^{(\leq l)}\right)$ and node attribute generation $p_{\theta}\left(\mathbf{X}^{(l+1)}\mid G^{(\leq l)},|\mathcal{V}^{(l+1)}|\right)$ involve computing graph representations with a set pooling operator over the updated node representations. Let $\mathbf{X}^{(l+1,t)}$ be the node attributes sampled for the $(l+1)^{\text{th}}$ layer at the step $t$ in the reverse node attribute diffusion process. After encoding $(G^{(\leq l)},t)$ into a context vector $\mathbf{h}_{t}^{(\leq l)}$, the denoising network $\phi_{\theta_{X}}$ augments the representations of $\mathbf{X}^{(l+1,t)}$ by $\mathbf{h}_{t}^{(\leq l)}$ and then applies a transformer without positional encodings (Vaswani et al., ) over them for predicting the set of $\mathbf{X}^{(l+1)}$. Similarly, the denoising network $\phi_{\theta_{A}}$ for edge diffusion augments $(G^{(\leq l)},t)$ by $(\mathbf{X}^{(l+1)},\mathbf{A}^{(l+1,t)})$ for computing the node representations of $\mathcal{V}^{(\leq l+1)}$. To predict the probability of edge $(u,v)$ for $u\in\mathcal{V}^{(\leq l)}$ and $v\in\mathcal{V}^{(l+1)}$, it concatenates and transforms the representations of node $u$, node $v$, and $t$ with an MLP.

Training The training process aims to maximize the log-likelihood of observed graphs under our model. We decompose this objective to train the three modules independently. To account for the autoregressive nature of our approach, we train all modules with teacher forcing. In each training iteration, we randomly sample a real partial DAG up to $l$ layers and train the model to predict the $l+1$-th layer. For a given partial DAG, the training of $p_{\theta}\left(|\mathcal{V}^{(l+1)}|\mid G^{(\leq l)}\right)$ is analogous to the standard supervised training of a graph classification model. The training of $p_{\theta}\left(\mathbf{X}^{(l+1)}\mid G^{(\leq l)},|\mathcal{V}^{(l+1)}|\right)$ and $p_{\theta}\left(\mathbf{A}^{(l+1)}\mid G^{(\leq l)},\mathbf{X}^{(l+1)}\right)$ follows the established practices for discrete diffusion models, where the modules are optimized by recovering corrupted discrete data.

Sampling The sampling process follows an autoregressive approach, performing layerwise graph generation. Starting with an empty graph $G^{(\leq 0)}$, we iteratively sample the number of nodes $|\mathcal{V}^{(l+1)}|$ for each subsequent layer using $p_{\theta}\left(|\mathcal{V}^{(l+1)}|\mid G^{(\leq l)}\right)$. If $|\mathcal{V}^{(l+1)}|$ is non-zero, we sequentially generate node attributes $\mathbf{X}^{(l+1)}$ and edges $\mathbf{A}^{(l+1)}$ using their respective reverse diffusion processes. We then update $G^{(\leq l+1)}$ with the new nodes, attributes, and edges. This process continues until we predict $|V^{(l+1)}|$ to be 0 0, at which point generation terminates.

Layerwise positional encoding An important out-of-distribution generalization issue for sequence generation is length generalization, which challenges language models trained on shorter sequences to extrapolate to longer ones during generation (Anil et al., ; Zhou et al., ). A substantial body of research approaches this issue by developing more generalizable positional encodings (PEs) for tokens (Shaw et al., ; Su et al., ; Ruoss et al., ).

As DAGs generalize chains/sequences, we consider the use of PEs based on the layer index $l$ to enhance model expressive power. In our evaluation, we notice that PEs based on one hot encoding of the layer index $l$ may hurt the performance. This observation is different from D-VAE (Zhang et al., ) that uses one-hot encodings of node indices given by a topological order. Relative PEs based on index difference between the latest layer and existing layers, are translation invariant and compatible with layer generalization. However, they are not expressive enough to capture layer-specific patterns. Therefore, we propose to use the sinusoidal encoding of $l$ given by $(\cdots,\cos(w_{i}l),\sin(w_{i}l),\cdots)$ as PEs for nodes in layer $l$, which improves the expressive power while keeping a certain level of generalization. This choice of PE improves the final quality of the generated DAGs in many cases.

Conditional generation LayerDAG is also capable of performing conditional generation. Given a labeled DAG $(G,y)$, we train LayerDAG to learn the conditional distribution $\mathbb{P}(G|Y)$ by integrating the sinusoidal embeddings of $y$ into the representations of $\mathbf{X}^{(\leq l)}$ for any $l$. Once trained, the model can generate DAGs conditioned on specified target properties.

### 3.3 Permutation invariance and model generalization

A critical issue in developing probabilistic generative models of graphs is permutation invariance, whether the probability for a model to generate a graph is invariant to the particular choice of node ordering. Non-permutation invariant models, such as autoregressive models that generate one node at a time, require data augmentations with random node orderings during training (You et al., ; Li et al., ). To sufficiently train the model, one has to enumerate a large number of orderings, which could be exponential in $N$. LayerDAG is permutation invariant with the aforementioned implementation. By aligning with such an inductive bias, LayerDAG has the potential of holding a good generalization capability with limited computational resources for training.

###### Proposition 3.1 (permutation invariance of LayerDAG)

For any depth $l$, $p_{\theta}\left(|\mathcal{V}^{(l+1)}|\mid G^{(\leq l)}\right)$, $p_{\theta}\left(\mathbf{X}^{(l+1)}\mid G^{(\leq l)},|\mathcal{V}^{(l+1)}|\right)$, and $p_{\theta}\left(\mathbf{A}^{(l+1)}\mid G^{(\leq l)},\mathbf{X}^{(l+1)}\right)$ are permutation invariant. Hence, LayerDAG is permutation invariant.

Both bidirectional MPNN layers and positional encodings of layer depth are permutation equivariant, and sum/mean pooling operators are permutation invariant. Then, it follows that for any permutation $\Pi$, we have $\mathbb{P}\left(\Pi^{(l+1)}(G^{(l+1)})\mid\Pi^{(\leq l)}(G^{(\leq l)})\right)=
\mathbb{P}\left(G^{(l+1)}\mid G^{(\leq l)}\right)$, where $\Pi^{(l+1)}$ corresponds to $\mathcal{V}^{(l+1)}$ and $\Pi^{(\leq l)}$ corresponds to $\mathcal{V}^{(\leq l)}$. Finally, $\mathbb{P}\left(G\right)=\prod_{l=0}^{L-1}\mathbb{P}\left(G^{(l+1)}\mid G^{(
\leq l)}\right)$ is also permutation invariant.

###### Proposition 3.1 (permutation invariance of LayerDAG)

### 3.4 Flexible quality-efficiency trade-off with a layer-index-based denoising schedule

Note that as $l$ increases, both $|\mathcal{V}^{(\leq l)}|$ and $|\mathcal{E}^{(l+1)}|$ increase in general, resulting in more complex edge dependencies. To effectively handle this pattern, we introduce a non-uniform denoising schedule for better allocation of the time budget. Specifically, we propose to set the total number of denoising steps to linearly increase in $l$.

$$ $T^{(l)}=T_{\min}+\lfloor\left(T_{\max}-T_{\min}\right)\cdot\min\left\{l/L_{ \max},1\right\}\rfloor$ $$

where $T_{\min}\leq T_{\max}$ are the minimum and maximum number of denoising steps and allow users to make a flexible quality-efficiency trade-off for DAG generation with LayerDAG. $l$ is the current layer index, $L_{\max}$ is the maximum number of layers in the training data, and $\lfloor\cdot\rfloor$ is the floor function.

## 4 Related work

We have already extensively compared LayerDAG with DAG generative models. Here, we review relevant undirected graph generative models.

Autoregressive models. GraphRNN (You et al., ) and DeepGMG (Li et al., ) are nodewise autoregressive models for undirected graphs, generating one node at a time. D-VAE extends this approach for DAGs and adopts topological orderings (Zhang et al., ). For efficiency considerations, GRAN proposes sequentially generating node sets of constant size (Liao et al., ). GraphPNAS extends this approach for attributed DAG generation (Li et al., ). Like their DAG counterparts, GraphRNN and GRAN also violate the inductive bias by imposing an order of the nodes. Consequently, they may suffer from inferior effectiveness or training efficiency.

Diffusion models. Niu et al. applies continuous diffusion models to adjacency matrices of undirected graphs (Niu et al., ). GDSS extends the previous approach to attributed graphs like molecules (Jo et al., ). DiGress proposes a discrete diffusion model for attributed graph generation (Vignac et al., ). GraphMaker extends DiGress for generating large attributed graphs (Li et al., ). All these models use a constant number of denoising steps in the generation of the whole graph, regardless of their size and complexities. Recently, there has been an arising interest in exploring the intersections of autoregressive models and diffusion models. TimeGrad (Rasul et al., ) proposes an autoregressive diffusion model for time series forecasting. ARDMs (Hoogeboom et al., ) generalize order-agnostic autoregressive models and absorbing discrete diffusion. For undirected graph generation, EDGE (Chen et al., ) and GRAPHARM (Kong et al., ) propose diffusion models where each denoising step generates a new set of edges and therefore also corresponds to exactly one step in autoregressive generation. Unlike LayerDAG, they do not perform multiple rounds of refinement, which is critical for capturing logical dependencies among node attributes and edges. In contrast, with autoregressive layerwise diffusion, LayerDAG allows for multiple-step refinement in each layer generation, and with the layer-index-based denoising schedule, LayerDAG also allows for using more denoising steps for more complex layers, which provides the overall freedom to balance quality and efficiency.

## 5 Experiments

The end application scenarios of DAG generative models pose multifaceted requirements that motivate the design of our empirical studies. $\textbf{Q1})$ Given that real-world DAGs encompass complex logical and directional dependencies, where violations can directly invalidate generated samples, how effectively can LayerDAG capture these dependencies by learning from valid DAGs? $\textbf{Q2})$ Beyond ensuring validity, the application of synthetic data for system and hardware benchmarking necessitates the preservation of correlations between DAGs and system metrics such as throughput, latency, and memory footprint. How effectively can LayerDAG perform DAG generation conditioning on these metrics to meet these requirements? $\textbf{Q3})$ With the rapid advancements in computational workloads, including foundation models and edge computing, system vendors need to proactively design next-generation platforms. A model capable of simulating workloads with hypothetical metrics (e.g. low latency / low power consumption) holds significant potential. Additionally, optimizing DAG properties for scenarios like circuit design demands generalization to unseen property values. This raises a crucial question: can LayerDAG generalize to unseen regimes of DAG labels when generating DAGs? $\textbf{Q4})$ Different application scenarios require varying trade-offs between generation efficiency and quality. How effectively does a layer-index-based denoising schedule (in Sec. 3.4) meet this requirement using a single trained LayerDAG model?

Baselines We consider three non-diffusion autoregressive baselines – GraphRNN, D-VAE, and GraphPNAS. GraphRNN originally tackles undirected graph structure generation (You et al., ), and we adopt an extension of it for attributed DAG generation (Zhang et al., ). D-VAE is a variational auto-encoder and employs a nodewise autoregressive decoder. Both GraphRNN and D-VAE employ topological orderings and one-hot encoding of node IDs (Zhang et al., ). GraphPNAS sequentially generates incident edges for a node set of constant size, using a mixture of Bernoulli distributions to model intra-set dependencies. To compare the capability of LayerDAG in set generation against GraphPNAS, we further adapt GraphPNAS by using mixtures of multinoulli distributions for generating a set of node attributes and setting the node set size to be the averaged layer size. For pure diffusion baselines, we implement OneShotDAG, a non-autoregressive variant of LayerDAG. For ablation study of multiple rounds of refinement, we report results with a single denoising step, denoted by LayerDAG ($\mathbf{T=1}$). For details of model extensions, see Appendix B.

### 5.1 Generating synthetic DAGs with strong logical rules ( Q1 )

To evaluate the model’s capability in capturing logical rules by learning from valid DAGs, we propose a synthetic dataset of latent preferential DAGs (LP). LP adheres to various hard logical constraints, including a constraint on the balanced level of binary node attributes among the node’s predecessors. Specifically, we enforce that $\frac{\lfloor|n_{v}^{(0)}-n_{v}^{(1)}|/2\rfloor}{(n_{v}^{(0)}+n_{v}^{(1)})/2}\leq\rho$ for any node $v$, where $\lfloor\cdot\rfloor$ is the floor function, and $n_{v}^{(i)}$ is the number of node $v$’s predecessors with attribute $i$ for $i\in\left\{0,1\right\}$. The parameter $\rho\in\{0,0.5,1\}$ helps assess how model performance varies under different degrees of constraint, where a lower value imposes stricter constraints ($\rho=0$ indicating $|n_{v}^{(0)}-n_{v}^{(1)}|\leq 1$). For a full description of the dataset, see Appendix C.

We use LP with different $\rho$’s to generate the datasets $D_{\rho}$ and train different generative models based on $D_{\rho}$. After training, we use each model to generate DAGs of the same number as that in $D_{\rho}$. To evaluate the hard logical constraints, we assess the validity of generated DAGs by measuring the proportion of generated DAGs that satisfy the imposed hard constraints. To evaluate the soft constraints, we compare the distributions of graph statistics between generated DAGs and an equal number of real DAGs. We measure the $1$-Wasserstein distance ($W_{1}$) between the distributions of layer numbers ($L$) for the two graph sets. Additionally, we measure Maximum Mean Discrepancy (MMD) (You et al., ) between two sets of graph statistic distributions corresponding to the graph sets. Specifically, we report MMD for the distributions of layer size ($|\mathcal{V}^{(l)}|$).

Table: Table 1: Evaluation results on LP. Best results are in bold.

Table 1 presents the evaluation results. LayerDAG consistently outperforms all the other models in terms of validity, with substantial margins observed under stricter logical rules (lower $\rho$ values), about $20\%$ in absolute value. Nodewise autoregressive models (GraphRNN and D-VAE) that directly encode node IDs struggle to learn strict logical rules. Meanwhile, a mixture of Bernoulli/multinoulli distribution is also not expressive enough, resulting in GraphPNAS achieving low validity scores. The ablation studies against the non-autoregressive variant (OneShotDAG) and the single-denoising-step variant ($T=1$) underscore the importance of combining autoregressive layerwise generation and diffusion in modeling strong directional and logical rules for DAG generation. In terms of graph statistics, the layerwise autoregressive models, LayerDAG ($T=1$) and LayerDAG, yield a better performance in capturing layerwise patterns ($L$ and $|\mathcal{V}^{(l)}|$), demonstrating the benefit of autoregressive layerwise generation. We also experiment with a variant of the LP dataset that allows directly examining the validity of the generated node attributes, where LayerDAG also achieves the best performance consistently. See Appendix D for more details.

### 5.2 Conditional generation for real-world datasets from diverse computational platforms ( Q2 )

Datasets. We repurpose and adapt three representative real-world datasets, originally developed for DAG property prediction, to serve as testbeds for conditional DAG generation. The datasets are associated with computation workloads executed on diverse hardware platforms, and they well fit the end scenario of synthetic data sharing for system/hardware benchmarking. Originally released as part of the TpuGraphs dataset, TPU Tile is a collection of kernel graphs for machine learning workload on Tensor Processing Units (TPUs), with graph labels $y$ indicating the runtime averaged over a set of compilation configurations (Phothilimthana et al., ). High-level synthesis (HLS) is a collection of data flow intermediate representation graphs for compiled C programs, with each DAG labeled according to the resource usage of look up table measured on Field Programmable Gate Arrays (FPGAs) (Wu et al., ). NA-Edge is a collection of DAGs representing neural architectures, with labels indicating their inference latency on mobile CPU (Dong & Yang, ; Zhang et al., ). We follow Wang et al. () for data pre-processing. Table 2 presents the dataset statistics. We perform a random train/val/test split for all datasets. For more details on dataset adaptation and data statistic distributions, see Appendix E.

Evaluation. Performing ground truth evaluations for conditional generation of DAGs in system and hardware design requires direct measurements on specific computational platforms. For example, the HLS dataset requires program implementation and measurement on FPGAs (Wu et al., ). Such evaluations are computationally costly or infeasible due to limited access. Additionally, they demand specialized domain knowledge that often exceeds the expertise of general machine learning practitioners. Recently, employing ML-based surrogate cost models has emerged as a popular and effective alternative to direct measurement in various system and hardware optimizations (Chen et al., ; Jia et al., ; Phothilimthana et al., ; Kaufman et al., ; Mendis et al., ; Sỳkora et al., ; Steiner et al., ; Baghdadi et al., ; Zheng et al., ; Dubach et al., ). In light of these achievements, we propose to evaluate the quality of generated DAGs with ML-based surrogate models. Specifically, we partition the real labeled DAG datasets into training/validation/test subsets. Then, we use the real training and validation labels as conditions for DAG generation. The generated labeled DAGs essentially form synthetic training and validation subsets. Inspired by previous practices (Yoon et al., ; Li et al., ), we train two ML models with BiMPNN using the same automated pipeline respectively on the real and synthetic training/validation subsets. We then compare the performance of the two models on the real test set. A generative model is considered better if its corresponding model achieves a performance closer to that of the model trained on the real subsets.

Table: Table 2: Dataset statistics. $|\mathcal{V}|$, $|\mathcal{E}|$, and $L$ are averaged over graphs. $|\mathcal{V}^{(l)}|$ is averaged over layers.

Table: Table 3: Evaluation results for conditional generation. Best results are in bold.

Table: Table 4: Evaluation results for label generalization. Best results are in bold.

Table 3 presents the evaluation results. For a comprehensive analysis, we report two metrics for ML-based evaluation – Pearson correlation coefficient that compares the relative label differences of DAGs in the test set based on the predicted labels and the ground-truth labels, and mean absolute error (MAE) that compares the absolute difference between the predicted labels and the ground-truth labels. LayerDAG consistently achieves the best performance in ML-based evaluation. Furthermore, we assess discrepancies in graph statistics between the real validation subset and a synthetic validation subset via the same metrics used in Sec.5.1, where LayerDAG also achieves the best performance in general. Overall, these evaluation results are aligned with previous observations made for the LP dataset.

### 5.3 Label generalization in conditional generation ( Q3 )

To assess the model capabilities in generalizing to unseen regimes of label values, we establish a challenging out-of-distribution testbed using the TPU Tile dataset. We sort the real-world DAGs based on their labels and then partition them into five quantiles. For an experiment, we exclude one quantile of data during the development of the generative models. After training the generative models, we conduct a random train/val/test split on the previously excluded quantile. We evaluate conditional generation exclusively on this quantile, i.e., generating DAGs conditioning on labels from this quantile. Essentially, this setup requires the models to perform interpolation for intermediate quantiles and extrapolation for the end quantiles. An analysis of the TPU tile dataset reveals a long-tailed label distribution, with larger value ranges in latter quantiles, detailed in Appendix E. Therefore, we choose the 5th quantile for an extrapolation study and the 4th quantile for an interpolation study, which presents significant challenges. Besides the previously employed BiMPNN model, we leverage another surrogate model that stood out as a top-5 solution from more than 600 submissions in a Kaggle competition for the TpuGraphs dataset (Phothilimthana et al., ; Kag, ).

Table 4 presents the evaluation results. As expected, the extrapolation setting is extremely challenging, where most models even failed to achieve a single positive Pearson correlation coefficient. In contrast, LayerDAG consistently achieves the best metrics for ML-based evaluation in this setting, with a gain of at most about $0.2$ in Pearson correlation coefficient for BiMPNN. Overall, LayerDAG significantly outperforms the rest models for both the extrapolation and interpolation settings, suggesting a superior generalization capability arising from the combination of autoregressive layerwise generation and diffusion.

### 5.4 Evaluation for the layer-index-based denoising schedule ( Q4 )

Figure 2 presents the evaluation of layer-index-based denoising schedule in quality-efficiency trade-off on LP $(\rho=0)$, TPU Tile, and HLS. The curves start from the time budget that leads to the best performance.
For an ablation study, we also experiment with a constant denoising schedule that simply utilizes a constant number of denoising steps $T$ for all layers. Both schedules allow an effective quality-efficiency trade-off, while the layer-index-based schedule often yields a better generation quality with the same time budget. For comparison, we also evaluate the generation time of the baselines using the same batch size. Using layer-index-based linear denoising schedule, LayerDAG exhibits a better or comparable trade-off than most baselines except GraphRNN.

Figure: Figure 2: Generation quality with respect to time budget for LP $(\rho=0)$, TPU Tile, and HLS.
Refer to caption: x2.png

## 6 Conclusion

We propose LayerDAG, a layerwise autoregressive diffusion model for DAGs, conceptualized by viewing a DAG as a sequence of bipartite graphs. Extensive experiments on synthetic and real-world datasets demonstrate a superior capability of LayerDAG in modeling the strong dependencies common in DAG data and in generating DAGs even with out-of-distribution labels.

#### Acknowledgement

We are deeply grateful to Haoyu Wang and Yinan Huang for their insights on dataset adoption and adaptation. M. Li, V. Shitole, E. Chien and P. Li are partially supported by NSF awards PHY-2117997, IIS-2239565, IIS-2428777, and CCF-2402816; DOE award DE-FOA-0002785; JPMC faculty awards; Microsoft Azure Research Credits for Generative AI; and Meta research award.

## Appendix A Details on layerwise diffusion

Composing the transition matrices across multiple time steps yields the closed-form expression $q(\mathbf{Z}^{(t+1)}|\mathbf{Z}^{(0)},t)=\mathbf{Z}^{(0)}\overline{\mathbf{Q}}
^{(t+1)}$, where $\overline{\mathbf{Q}}^{(t+1)}=\mathbf{Q}^{(1)}\mathbf{Q}^{(2)}\cdots\mathbf{Q}
^{(t+1)}$, which allows parallel training across samples and time steps.
An instantiation of $\{\overline{\mathbf{Q}}^{(t)}\}_{t}$ is valid as long as $\lim_{t\rightarrow T}\overline{\mathbf{Q}}^{(t)}$ is a known prior distribution.
During the reverse generation process, the trained denoising network is used to convert $\mathbf{Z}^{(T)}$ drawn from the prior distribution into realistic data. Iteratively, we compute and sample from $p_{\theta}(\mathbf{Z}^{(t-1)}|\mathbf{Z}^{(t)},t)\propto\mathbf{Z}^{(t)}(
\mathbf{Q}^{(t)})^{\top}\odot\hat{\mathbf{Z}}^{(0)}\overline{\mathbf{Q}}^{(t-1)}$, where ^⊤ denotes transpose, and $\odot$ denotes element-wise product.

Following the practice of DiGress, we use the empirical marginal distribution of a categorical attribute $\textbf{m}\in\mathbb{R}^{C}$ as its corresponding prior distribution, which was observed to yield more efficient generation compared with a uniform prior in practice. The composed transition matrix is chosen to be $\overline{\mathbf{Q}}^{(t)}=\overline{\alpha}^{(t)}\mathbf{I}+\left(1-
\overline{\alpha}^{(t)}\right)\textbf{1}\textbf{m}^{\top}$, where $\overline{\alpha}^{(t)}=\cos^{2}\left(\frac{\pi}{2}\frac{t/T+s}{1+s}\right)$ is the cosine noise schedule (Nichol & Dhariwal, ), $\mathbf{I}\in\mathbb{R}^{C\times C}$ is the identity matrix, and $\textbf{1}\in\mathbb{R}^{C}$ is the one-valued vector. As $t\rightarrow T$, the probability for real categorical attributes to be corrupted into random samples from the prior distribution approaches $1$.

In addition, we propose two modifications to the diffusion process that better preserve the layerwise patterns of DAGs. To handle the potential uneven graph sparsity with respect to layer depth $l$, we set the prior probability of a directed edge $(u,v)$ for $u\in\mathcal{V}^{(\leq l)}$ and $v\in\mathcal{V}^{(l+1)}$ to be $\frac{\min(|\mathcal{V}^{(\leq l)}|,d_{\text{in}})}{|\mathcal{V}^{(\leq l)}|}$, where $d_{\text{in}}$ is the average node in-degree of the training data. As all nodes in $\mathcal{V}\setminus\mathcal{V}^{(1)}$ have at least one predecessor, we enforce this property in the sampling for graph structure corruption and generation.

To generate $\mathbf{X}^{(l+1)}$, the node attribute prediction module first samples $\mathbf{X}^{(l+1,T_{X})}\in\mathbb{R}^{|\mathcal{V}^{(l+1)}|\times C}$ from its prior distribution, where $T_{X}$ is the maximum number of denoising steps. Then iteratively, it samples $\mathbf{X}^{(l+1,t)}$ with a denoising network $\phi_{\theta_{X}}\left(G^{(\leq l)},\mathbf{X}^{(l+1,t+1)},t+1\right)$ for $t=T_{X}-1,T_{X}-2,\cdots,0$. Similarly, the edge prediction module iteratively samples $\mathbf{A}^{(l+1,t)}$ with a denoising network $\phi_{\theta_{E}}\left(G^{(\leq l)},\mathbf{X}^{(l+1)},\mathbf{A}^{(l+1,t+1)},
t+1\right)$.

## Appendix B Baseline extensions

General extension for DAG generation. To extend generative models of undirected graphs for DAG generation, we constrain the structure generation to the lower-triangular part of adjacency matrices with a topological ordering.

GraphRNN. GraphRNN originally employs rows of an adjacency matrix for both the encoder input and decoder output. Following the practice of (Zhang et al., ), we augment them with one-hot encodings of categorical attributes for encoding and predicting the node attributes.

GraphPNAS.
We use two separate encoders for node attribute prediction and structure prediction as in LayerDAG. Repeatedly, the model first predicts the categorical attributes of a new set of nodes given the partially generated DAG, and then it predicts the incident edges of the new nodes given the partial DAG and the new node attributes. We model the termination of DAG generation as an extra node attribute, which enables the model to generate DAGs with an arbitrary number of nodes different from multiples of the pre-specified size.

We extend the official implementation for D-VAE and GRAN, both use MIT license.

Figure: Figure 3: Layer size distribution in the real-world datasets.
Refer to caption: x3.png

Figure: Figure 4: Scatter plot of the sorted labels. The label distributions in the real-world datasets are long-tailed.
Refer to caption: x4.png

## Appendix C A synthetic dataset of latent preferential DAGs (LP)

A latent preferential DAG is constructed as follows.

- 1.
Randomly sample the number of layers $L\sim\mathcal{U}\left\{2,5\right\}$.
- 2.
Create the first layer of $|\mathcal{V}^{(1)}|\sim\mathcal{U}\left\{1,5\right\}$ nodes. Each node is associated with a random binary attribute 0 0 or $1$.
- 3.
For $l=2,\cdots,L$:
(a)
Create a new layer of $|\mathcal{V}^{(l)}|\sim\mathcal{U}\left\{1,5\right\}$ nodes. Each node is associated with a random binary attribute 0 0 or $1$.
(b)
For each new node $v$:
i.
An edge $(u,v)$ is created with a probability $\propto\frac{1}{d_{v}-d_{u}}$, where $d_{v}=l$ is the depth of node $v$ and $d_{v}>d_{u}$.
ii.
Let $n_{v}^{(i)}$ be the number of predecessors of node $v$ with attribute $i$ for $i\in\left\{0,1\right\}$. We enforce that $\frac{\lfloor|n_{v}^{(0)}-n_{v}^{(1)}|/2\rfloor}{(n_{v}^{(0)}+n_{v}^{(1)})/2}\leq\rho$, where $\lfloor\cdot\rfloor$ is the floor function.
iii.
$n_{v}=n_{v}^{(0)}+n_{v}^{(1)}\sim\mathcal{U}\left\{1,4\right\}$.

The logical rules for predecessors get increasingly relaxed as $\rho$ goes from 0 0 to $1$.

## Appendix D Variant of the LP Dataset for Assessing the Validity of Generated Node Attributes

We extend the original synthetic dataset with $\rho=0$ (full balance requirement). Specifically,

- •
Each node now has three binary attributes (previously one).
- •
For nodes in the first layer, all three binary attributes are randomly sampled from prior Bernoulli distributions.
- •
The first attribute is still used for determining edge connections based on balance.
- •
The second and third attributes of an intermediary node are assigned the most and least common corresponding attribute values among its predecessors, respectively. This design is inspired by real-world scenarios, such as tensor dimension matching in computational graphs. In cases of ties, attribute values are assigned randomly.

Table: Table 5: Evaluation results on the extended synthetic dataset for $\rho=0$ (full balance requirement). Best results are in bold.

In addition to the previously adopted metrics, we also report balance-only validity and feature-only validity as key components of the full validity metric, as well as MMD for feature distributions. Table 5 compares LayerDAG with the two most competitive baselines concluded from the other experiments, with results averaged over three random seeds. Overall, LayerDAG achieves the best performance across all metrics. This demonstrates LayerDAG’s superior capability in generating valid attributes and learning the attribute distribution.

## Appendix E Additional details on real-world datasets and adaptation of them

TPU Tile. In the original dataset, each data sample includes a computational graph, a compilation configuration, and the execution time of the graph on TPU when compiled with that configuration. A single graph may appear in multiple data samples and have multiple associated compilation configurations. We simplify the dataset by averaging the runtime across all compilation configurations for each graph. As the labels of the test set were not released, we re-perform a split of the labeled samples.

HLS. We randomly choose 20% of the original graphs.

For all three real-world datasets, we perform a 80/10/10 random split of the dataset. All three datasets exhibit long-tailed layer size distributions (Fig. 3) and label distributions (Fig. 4).

TPU Tile was originally part of the TpuGraphs dataset, which uses Apache-2.0 license. The HLS dataset is not released with a license. NA-Edge is released with an MIT license as part of the nn-Meter project.

## Appendix F Experiment details

### F.1 Model development

For the synthetic LP dataset, we tune the hyperparameters based on validity. For conditional generation, we tune the hyperparameters based on Pearson correlation coefficient. For each experiment, an early stop is performed based on validation accuracies (for layer size prediction) or negative log likelihoods (for diffusion).

### F.2 ML-based evaluation

We perform ML-based evaluation by implementing a standardized AutoML pipeline. Based on empirical studies, the best BiMPNN model is selected based on validation Pearson correlation coefficient, and the best Kaggle model is selected based on validation mean absolute error.

### F.3 Experiments Compute Resources

We have access to an Azure virtual machine equipped with 2 NVIDIA A100 PCIe GPUs, each with 80 GB of memory, 48 non-multithreaded AMD EPYC Milan processor cores, and 440 GiB of system memory.

### F.4 Implementation

Our implementation is based on PyTorch 1.12.0 (Paszke et al., ) and DGL 1.1.0 (Wang et al., ).

## Peer Reviews

confidence: 3
contribution: 2
initial_rating: 6
presentation: 3
questions: 1.	Given that the topological ordering of a DAG is not unique, how does the layered representation remain consistent for a given DAG? Was any consideration given to the ordering of nodes within each layer?
2.	What is the rationale for seeking permutation invariance when generating DAGs?
3.	Is it possible to validate the generated DAGs for the TPU Tile datasets experimentally, without relying on a surrogate model?
soundness: 3
strengths: 1.	Generating DAGs is more challenging than generating general graphs due to their inherent dependencies and constraints. The layered structure simplifies the generation process by breaking down the DAG into a sequence of directed bipartite graphs, making dependencies easier to handle.
2.	LayerDAG's combination of autoregressive and diffusion models makes it a more robust approach to handling these complexities.
3.	LayerDAG offers a scalable solution for generating large, structured DAGs.
4.	The paper demonstrates the improved performance of LayerDAG over other methods through experiments with various synthetic DAGs.
summary: This paper presents an autoregressive model, LayerDAG, for generating directed acyclic graphs (DAGs). A key contribution of the paper is framing the problem as a layered graph, leveraging the fact that a topological ordering of a DAG naturally induces a layered structure, where each pair of consecutive layers forms a directed bipartite graph. Building on this layered representation, LayerDAG employs autoregressive generation to model directional dependencies between layers, while diffusion models capture logical dependencies within each bipartite graph. Experimental results demonstrate that LayerDAG outperforms several existing graph generative models.
weaknesses: 1.	The authors state that "LayerDAG is based on a novel perspective of DAGs: as illustrated in Fig. 1(b), the partial order of nodes dictated by the DAG structure can be decoupled as a sequence of tokens, each corresponding to a bipartite graph." However, this approach has been widely known for decades. For example, Tarjan’s topological ordering algorithm for a DAG uses a Depth-First Search (DFS) traversal to produce a linear ordering of vertices, ensuring that for every edge, the source vertex appears before the target vertex in the ordering. Surprisingly, the paper does not reference Tarjan’s method or other relevant work in this area.
Citation: Tarjan, R. E. (1972). Depth-first search and linear graph algorithms. SIAM Journal on Computing, 1(2), 146–160. doi:10.1137/0201010
2.	The directional and ordered dependencies within a DAG structure are essential, meaning that order should be preserved. Thus, the motivation for seeking permutation invariance in this context is unclear. Furthermore, Proposition 3.1 lacks clarity, and a formal proof would help understand the proposition.
3.	In Section 5.2, the experiments explore several real-world DAGs. However, the presented results indicate whether the generated DAGs can substitute training DAGs, which seems insufficient. For instance, the generated graphs have different layer counts than the actual DAGs. A more pertinent question would be whether the generated DAGs are suitable for downstream tasks. Although validating hardware DAGs might be challenging, it should be feasible to assess the relevance of other types of DAGs for specific applications (e.g., with the TPU Tile dataset).

---

confidence: 3
contribution: 3
initial_rating: 6
presentation: 3
questions: NA
soundness: 3
strengths: Innovative Approach: The combination of autoregressive and diffusion models provides a novel framework for generating complex DAGs with strong dependencies.

Layerwise Decomposition: The use of bipartite graphs for sequential layer generation improves scalability and reduces computational complexity.

Conditional Generation Capability: LayerDAG supports generating DAGs based on specific performance metrics, making it valuable for system benchmarking applications.
summary: The paper makes a compelling contribution by proposing a novel framework for DAG generation that addresses key challenges in modeling both logical and directional dependencies. The combination of autoregressive generation and diffusion models offers strong expressiveness, and the extensive experiments validate its practical utility. However, addressing the computational complexity and providing more interpretability would strengthen the work. Expanding the comparison with simpler models and exploring alternative encoding methods would also improve the empirical analysis. Nonetheless, the novelty and relevance of LayerDAG justify its acceptance.
weaknesses: Computational Overhead: While the layerwise approach is efficient, the combination of autoregressive and diffusion methods can be computationally intensive for very large graphs.

Limited Exploration of Alternative Encodings: The paper mainly focuses on sinusoidal encodings, without exploring other potential positional encodings.

---

confidence: 4
contribution: 3
initial_rating: 8
presentation: 4
questions: Pg 6, proof of Proposition 3.1: what is does it mean to be "permutation equivariant"? Is this meant to read "...invariant"?

There is not enough discussion about how exactly the denoising steps interact with the successive layer-wise generation. It is not clear to me how the number of denoising steps relates to the number of layers. It is also jarring to read in S2 that in general diffusion generation is conditioned on previous steps, whereas in LayerDAG it is conditioned on previous layers. For example, the "__Implementation__" paragraph in page 5 reads "Let $\textbf{X}^{l+1,t}$ be the node attributes sampled for the $(l+1)^{\text{th}}$ layer at the step $t$ in the reverse node attribute diffusion process." Is step $t$ nested under layer $l+1$, i.e. all steps $1,\ldots,T$ occur in each layer, or do steps stretch over all layers? Similarly, S3.4 should be better-explained.
soundness: 3
strengths: The paper's contributions stem from a novel formulation of a DAG as a sequence of layers. This formulation is original, non-trivial, and concise, and directly motivates the LayerDAG algorithm. The paper itself is quite clear and well-written. The experiments are comprehensive and clearly demonstrate the superior performance of LayerDAG over other autoregressive DAG models.
summary: The paper presents a diffusion model LayerDAG for directed acyclic graphs (DAGs) based on a novel representation of DAGs as a sequence of bipartite graphs, each bipartite graph divided across nodes in the next layer of the DAG versus nodes in all previous layers of the DAG. This representation allows for layer-wise conditional generation of the DAG, which allows the model to better-learn logical rules. The experiments show that LayerDAG exceeds in learning hard logical rules, learning soft rules, and in generalization.
weaknesses: A minor weakness in the paper is that there is not enough discussion about the definition of LayerDAG across layers versus the usual definition of diffusion models across denoising steps. I elaborate more in the "Questions" section.

---

confidence: 2
contribution: 3
initial_rating: 8
presentation: 3
questions: Questions
* What is the maximum number of layers of DAG your model could generate?
* Is LayerDAG able to capture more complex logical constraints other than the number of predecessors? 
* Do you have explanations for the better performance of baseline models in Table 3, specifically HLS dataset?
soundness: 3
strengths: * Make a novel observation that DAG can be viewed as a sequence of bipartite graphs, which preserve the partial ordering and are autoregressive-friendly.
* Explore and discuss different design choices for DAG generative models, including separating three modules, positional encoding, etc.
* LayerDAG is permutation invariant, achieving good generalization.
* Different experiments to evaluate the proposed model quality on different tasks
summary: This paper proposes an autoregressive diffusion model to generate directed acyclic graph (DAG). This work observes that the DAG structure can be decoupled by a sequence of tokens, where each token corresponds to a bipartite graph. It is capable of generating larger DAGs (up to ~400 nodes). To validate the model, the paper compares the validity and statistical properties of the synthetic DAGs generated by the model with the baselines: computational graphs on TPU, flow graphs in FPGA, and Neural architectures on edge devices. They use the synthetic DAGs to train a ML-based surrogate model to measure the performance of systems (inference time, resource usage, etc.). And results show that the trained surrogate model outperformed ones that are trained on the baseline generative model.
weaknesses: * In the beginning of the introduction (line 51), the author mentioned that the one of the challenge in DAG is the training LLM workload execution DAG involves trillions of operations. But this work is capable of generating nodes up to 400 nodes, which seems not to be able to solve the challenge mentioned above.
* In the beginning of the introduction (line 51), the author mentioned that one of the challenges in DAG is the training LLM workload execution DAG involves trillions of operations. But this work is capable of generating nodes up to 400 nodes, which seems not to be able to solve the challenge mentioned above. Or do the authors suggest that using DAG with 400 nodes could capture the characteristics of a trillion of nodes? How do you get the logical constraints from the real-world large DAG for the synthetic DAG generation?
* In D-VAE, they have additional experiments to evaluate the model quality, like reconstruction accuracy. Would like to see the comparison on those experiments.

Minor issue
* The symbol for DAG are not consistent (line 143 vs. line 207)

---

confidence: 3
contribution: 3
initial_rating: 8
presentation: 4
questions: Overall I do not have many questions as I believe this is a high quality submission, however:

- As mentioned in the weaknesses section, I think the paper would be improved by a critical analysis of the experimental results. I understand that space limitations can prevent this, but a high quality discussion of results is more valuable than quantity of benchmarks. For example, how significant is a difference in Pearson correlation of **at most** 0.2 in the generalization benchmark? Is the model able to generalize at all, even if the coefficient is slightly higher than the baselines?

- What is the impact of a BiMPNN instead of considering message passing solely along the direction of the edges?

- If the complexity of generation increases per layer, have you considered using an exponential denoising schedule?
soundness: 4
strengths: - The method is simple, easy to understand and solidly rooted on a wealth of methodology on autoregressive diffusion models.
- The simplicity of the method does not detract the ingenuity of transforming the topological partial ordering into a sequence of bipartite graphs, leveraging that for generation.
- The authors are not over-reliant on mathematical formulation to describe their method (often a problem with diffusion based contributions), striking a balance between textual/intuitive explanations with easy to follow maths.
- Contribution of a synthetic dataset is extremely positive, as it helps testing for a wide range of possibilities that are often not considered with benchmarking datasets (that, in turn, are often not predictive of performance in real-world problems).
summary: This submission proposes a generative model, based on autoregression and dffusion, for Direct Acyclic Graph generation (DAG). The problem under study is relevant for the general scientific community with broad applicability in many crucial systems. 

The main idea behind the method presented is to transform the topological order induced by the DAG into a series of bipartite graphs that capture sequential dependencies of the tasks represented within the DAG. This idea enables the authors to sequentially generate sets of nodes as if they were a layer of the DAG, overcoming issues with partial ordering of nodes within the topological order of the graph. This is where the autoregressive component of the algorithm comes in, as the generation of a new set of nodes is dependent on the previous layers generated by the model.

The authors propose evaluation on a new synthetic dataset capable of capturing logical dependencies between nodes of different layers with multiple levels of hard logical constraints. This evaluation method attempts to capture the generative model's ability to impose logical dependencies between nodes. The proposed model is further evaluated on the ability to generate DAGs that mimick the properties of DAG property prediction benchmark (supported by an ML-surrogate approach, following related work in the area) and generalization of generated label values. The proposed model shows better performance than related work using the chosen evaluation metrics.
weaknesses: - Although the authors claim a significant increase in the number of nodes generated per DAG (from 24 to 400), this is still far from truly complex DAGs that can number in the thousands.

- There is a lack of critical analysis on the experimental results and the variations in performance of the proposed method. For example, the difference in LayerDAG with a single denoising step to the full algorithm for some benchmarks are negligible, it would be good to have some insight on why and in which conditions is it worth performing multiple denoising steps (and the impact in training time).

Meta-review: This paper introduces LayerDAG, a novel approach for generating directed acyclic graphs (DAGs) that combines autoregressive generation with diffusion models. LayerDAG leverages the layered structure of DAGs, induced by their topological ordering, to model both directional and logical dependencies effectively. The authors demonstrate the superior performance of LayerDAG compared to existing graph generative models, particularly in capturing complex dependencies and generating large DAGs.

Reviewers praise the innovative combination of autoregressive and diffusion models in LayerDAG, recognizing its potential to improve the expressiveness and scalability of DAG generation. The empirical results convincingly demonstrate the advantages of LayerDAG over existing methods, particularly in capturing complex dependencies and generating large, structured DAGs. The layered representation is seen as a key enabler for achieving these improvements.

However, one weakness is also identified:

- Computational Overhead: While the layerwise approach offers efficiency gains, the combination of autoregressive and diffusion models can lead to increased computational costs, particularly for very large graphs.

Recommendation:

Despite the computational considerations, the reviewers agree that LayerDAG presents a significant advancement in DAG generation. So I would suggest to accept it as poster.

Program Chair Modification: The area chair initially accepted, then rejected the paper later. However, this rejection was not confirmed by the Senior AC. ICLR requires that rejecting a paper with otherwise unanimous reviews requires Senior AC confirmation. The paper is thus accepted.

Decision: Accept (Spotlight)