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

Authors: Mufei Li, Viraj Shitole, Eli Chien, Changhai Man, Zhaodong Wang, Srinivas, Ying Zhang, Tushar Krishna, Pan Li
Primary area: learning on graphs and other geometries & topologies
Keywords: directed acyclic graphs, graph generation, discrete diffusion, autoregressive model

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.

Decision: accept (spotlight)
Reviewer scores: 6, 6, 8, 8, 8

Reviews and discussion:
<thread>
creation date:
1729962920782

thread_type:
official_review

<thread_object>
creator: reviewer_qsxe

<content>
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.

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).

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).

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?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730050177251

thread_type:
official_review

<thread_object>
creator: reviewer_vg1z

<content>
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.

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

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)

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?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730153954123

thread_type:
official_review

<thread_object>
creator: reviewer_72ky

<content>
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.

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.

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.

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.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730176740018

thread_type:
official_review

<thread_object>
creator: reviewer_7srq

<content>
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.

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.

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.

questions:
NA
</content>
</thread_object>

</thread>
<thread>
creation date:
1730699024819

thread_type:
official_review

<thread_object>
creator: reviewer_mrjn

<content>
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.

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.

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).

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?
</content>
</thread_object>

</thread>
<thread>
creation date:
1732572170611

thread_type:
official_comment

<thread_object>
creator: authors

<content>
comment:
We sincerely appreciate the insightful and positive feedback from all reviewers and the great coordination efforts of the area chair. Specifically,

- All reviewers recognized the contribution and novelty in decomposing a directed acyclic graph (DAG) into a unique ordered sequence of node and edge subsets, effectively generalizing classical topological orderings and addressing the issues arising from their non-uniqueness in existing autoregressive DAG generative models.
- The novel sequential view above naturally leads to the design of a novel autoregressive diffusion model of DAGs (Reviewers MRjN and 7SrQ). 
- Empirical studies demonstrate the effectiveness of the proposed approach (Reviewer 72KY) for synthetic graph generation (Reviewer MRjN), conditional generation with real-world DAGs for system benchmarking (Reviewers 7SrQ), achieving scalability (Reviewers MRjN and 7SrQ), and generalizability (Reviewers vg1z).
- Reviewer qSxe recognized the contribution of a new synthetic dataset for advancing future research.
- All reviewers find the paper well-written and the presentation easy to follow, “striking a balance between textual/intuitive explanations with easy to follow maths” (Reviewer qSxe). 

We’ve responded to individual reviewers for the specific questions. Three reviewers have already responded and acknowledged that we’ve addressed their questions (MRjN, 72KY, and vg1z).
</content>
</thread_object>

</thread>


Metareview:
metareview:
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.