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

Thank you for recognizing our contributions and providing insightful feedback!

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

Response: The effectiveness of BiMPNNs for predicting properties of directed graphs in computing systems has been established through empirical studies [1]. In system graphs, information flows exhibit intricate patterns where both forward and backward propagation of features can be valuable. Our experimental results support this architectural choice, showing that BiMPNN either outperforms or matches alternatives for DAG generation tasks.

[1] Wang et al. A Benchmark on Directed Graph Representation Learning in Hardware Designs.

Q2: I think the paper would be improved by a critical analysis of the experimental results, and 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?

Response: Thank you for this insightful observation. You raise a valid point about the Pearson correlation difference of 0.2 in the generalization benchmark. While this represents a substantial improvement over baselines, we acknowledge that the absolute performance still indicates limited generalization capability. We will revise our manuscript to expand the current discussion. We appreciate your guidance in helping us improve the depth and rigor of our analysis.

Q3: If the complexity of generation increases per layer, have you considered using an exponential denoising schedule?

Response: We appreciate your insightful suggestion. We agree that exploring alternative diffusion schedules like the exponential denoising schedule is a promising direction for future investigation, potentially allowing better alignment with the complexity scaling.

Thank you for reviewing our manuscript and recognizing our contributions!

Q1: What is the maximum number of layers for DAGs generated by your model?

Response: LayerDAG can generate an unlimited number of layers through enforcing non-zero nodes in subsequent layers. However, the practical utility may diminish when deviating significantly from real-world graphs. In our experiments with the evaluated datasets, we observed that the real graphs contain approximately 100 layers at maximum (as detailed in Table 2). Our empirical studies demonstrate that our model achieves competitive performance in capturing the layer count distribution when compared to the baselines (Table 3).

Q2: Is LayerDAG able to capture more complex logical constraints other than the number of predecessors?

Response: LayerDAG demonstrates strong capability in capturing complex logical constraints beyond predecessor count through our comprehensive empirical evaluation. Our analysis in Section 5.2 shows how the model effectively handles the intricate interplay between structural dependencies and node attributes like operator types, affecting system performance metrics such as runtime and resource utilization. We provide further evidence in Appendix D, where controlled experiments with synthetic datasets were specifically designed to mimic constraints like tensor dimension matching validate LayerDAG's effectiveness beyond simple predecessor counting. These results from both real-world computational platforms and carefully constructed synthetic scenarios consistently demonstrate that LayerDAG successfully models sophisticated logical relationships in computational graphs.

Q3: Do you have explanations for the better performance of baseline models in Table 3, specifically HLS dataset?

Response: While our method achieves the best overall performance on the HLS dataset, we acknowledge that some baselines show stronger or comparable results on specific metrics. This behavior can be attributed to the highly skewed and imbalanced layer size distribution in HLS, as illustrated in Figure 3. This characteristic likely affects LayerDAG's ability to capture the layer count distribution effectively. However, it's important to note that among all baselines, only D-VAE outperforms our approach on this specific aspect, while our method maintains superior or comparable performance across other metrics.

Thank you for your positive and detailed feedback!

Q1: Computational Overhead: While the layerwise approach is efficient, the combination of autoregressive and diffusion methods can be computationally intensive for very large graphs.

Response: Thank you for this thoughtful observation. We directly tackle this challenge through our non-uniform denoising schedule, detailed in Section 3.4, which strategically allocates more diffusion steps/computation budget to deeper layers where the generation requires dealing with more complex dependencies. Our empirical studies in Section 5.4 demonstrate its effectiveness in balancing computational efficiency and generation quality. We agree that extending these experiments to even larger directed acyclic graphs (DAGs) represents a valuable direction for future research, and our framework provides a foundation for such investigations.

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

Response: We appreciate the reviewer’s observation regarding positional encodings. Our choice of sinusoidal encodings was motivated by their proven expressiveness and generalization capabilities across various scenarios. Nevertheless, we acknowledge that exploring alternative encoding schemes could yield valuable insights in future studies.

We sincerely thank the reviewer for the thorough evaluation and valuable feedback!

Q1: In Pg 6, proof of Proposition 3.1: what does it mean to be “permutation equivariant”? Is this meant to read “...invariant”?

Response: Thank you for this important clarification question. The term "permutation equivariant" is indeed the correct terminology here, distinct from "permutation invariant." To achieve permutation invariance in the learned distribution of graphs, we require a graph encoder that computes and updates node representations in a permutation equivariant manner [1, 2]. This means that if we permute the ordering of nodes in the input graph structure and their corresponding features, the computed node representations must undergo the exact same permutation. This fundamental property ensures ordering-agnostic behavior, and the permutation equivariance of the encoder serves as a necessary prerequisite for achieving permutation invariance in the overall learned distribution. We can observe this property in many message passing neural networks. Consider the basic matrix operation $AX$, where $A$ denotes the adjacency matrix and $X$ represents the input node features – this operation inherently preserves permutation equivariance.

[1] Srinivasan & Ribeiro. On the Equivalence between Positional Node Embeddings and Structural Graph Representations.

[2] Want et al. Equivariant and Stable Positional Encoding for More Powerful Graph Neural Networks.

Q2: How does the number of denoising steps relate to the number of layers? In particular, for “Implementation” paragraph in page 5, is step $t$ nested under layer $l+1$, i.e., all steps $1, \cdots, T$ occur in each layer, or do steps stretch over all layers?

Response: In our framework, $T$ denotes the number of diffusion steps that occur within each layer, i.e., all steps $1, \cdots, T$ occur in each layer. This notation choice effectively captures the interplay of layerwise autoregressive generation and intra-layer diffusion. We appreciate your suggestion and will refine the presentation for better clarity in the next version of our manuscript.

Thank you for carefully reviewing our manuscript and providing constructive feedback. Below we respond to your questions and concerns.

Q1: Is the proposed sequential view of directed acyclic graphs (DAGs) merely topological ordering? If so, how do you handle the non-uniqueness of topological orderings for autoregressive generation? How is this related to permutation invariance?

Response: Our proposed sequential view of directed acyclic graphs (DAGs) extends beyond classical topological ordering. While a topological ordering arranges vertices linearly such that a vertex u precedes vertex v if there is an edge (u,v), its non-uniqueness poses a challenge for autoregressive DAG generation. Specifically, models like D-VAE [1] rely on randomly selected topological orderings during training, violating permutation invariance: the probability of generating the same DAG varies for different topological orderings. This compromises generalizability and necessitates costly strategies like sampling diverse orderings.

In contrast, our approach guarantees ordering uniqueness by generalizing from vertex ordering to vertex set ordering. Instead of sequentially generating individual vertices in a specific ordering, we construct layers — vertex sets whose members are characterized by the absence of unvisited predecessors. This results in a unique, sequential ordering of vertex sets (or layers), ensuring consistency across representations. The proposed LayerDAG framework leverages this unique layer structure to perform autoregressive generation at the level of vertex or edge sets, rather than individual vertices or edges.

By adopting this unique layer-based construction, our model achieves permutation invariance: the generation probability of a DAG remains unchanged regardless of the topological ordering of vertices. This eliminates the need to sample diverse orderings during training, potentially improving both training efficiency and model quality. Further details on this approach can be found in Sections 3.1 and 3.2 of the manuscript.

Q2: The current generation evaluations are based on statistics and discriminative/surrogate models. Is it possible to directly validate and assess the generated DAGs on the target computational platforms like TPU?

Response: Thank you for your insightful feedback! We choose to establish the testbed based on surrogate models as they are more accessible to the machine learning (ML) community in general and allow the ML community to easily further the research efforts. For example, real-world validation of the generated graphs for TPU Tile requires both access to TPUs and expertise about deep learning compilers. In fact, the system community also heavily employs ML-based surrogate models today, and we list diverse examples in the Section 5.2.

We agree that ultimately this line of research efforts is most useful if the generated synthetic DAGs can effectively replace real DAGs on the end computational platforms. We are currently working with experts in system and compute architecture for performing more domain-specific evaluations. We intend to submit the extension work directly to system/computer architecture venues where the audience can more effectively assess the work for domain purposes.

Q3: Why didn’t you cite the classical papers on topological ordering like Tarjan, R. E. (1972)?

Response: We have revised our manuscript to cite two classical papers on topological ordering including Tarjan, R. E. (1972) at the beginning of Section 3.1. We appreciate your guidance in helping us properly attribute the credit.

[1] Zhang, M et al. D-VAE: A Variational Autoencoder for Directed Acyclic Graphs. NeurIPS 2019.