LayerDAG: A Layerwise Autoregressive Diffusion Model for Directed Acyclic Graph Generation
directed acyclic graphs;graph generation;discrete diffusion;autoregressive model
Yes
No ethics review needed.
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?
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.
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.
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).
Yes
No ethics review needed.
NA
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.
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.
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.
Yes
No ethics review needed.
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.
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.
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.
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.
Yes
No ethics review needed.
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?
* 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
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.
* 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)
Yes
No ethics review needed.
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?
- 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).
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.
- 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).
@inproceedings{
anonymous2024layerdag,
title={Layer{DAG}: A Layerwise Autoregressive Diffusion Model for Directed Acyclic Graph Generation},
author={Anonymous},
booktitle={Submitted to The Thirteenth International Conference on Learning Representations},
year={2024},
url={https://openreview.net/forum?id=kam84eEmub},
note={under review}
}
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.
I certify that there is no URL (e.g., github page) that could be used to find authors’ identity.
I acknowledge that I and all co-authors of this work have read and commit to adhering to the ICLR Code of Ethics.
directed acyclic graphs graph generation discrete diffusion autoregressive model
I certify that there is no acknowledgement section in this submission for double blind review.
/pdf/d7c3ca7ed93e446965111ee1573d08b90b021075.pdf
learning on graphs and other geometries & topologies
I understand the reciprocal reviewing requirement as described on https://iclr.cc/Conferences/2025/CallForPapers. If none of the authors are registered as a reviewer, it may result in a desk rejection at the discretion of the program chairs. To request an exception, please complete this form at https://forms.gle/Huojr6VjkFxiQsUp6.
I certify that this submission complies with the submission instructions as described on https://iclr.cc/Conferences/2025/AuthorGuide.
/attachment/102078de05e443135ba4c59ae0531adccf160ee5.zip
LayerDAG: A Layerwise Autoregressive Diffusion Model for Directed Acyclic Graph Generation
ICLR 2025 Conference Submission
ICLR.cc/2025/Conference/Submission