Research map / Graph learning / Graph self-supervised learning
LayerDAG: A Layerwise Autoregressive Diffusion Model for Directed Acyclic Graph Generation
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes LayerDAG, a layerwise autoregressive diffusion model that represents a DAG as a unique sequence of bipartite graphs (layers), generating each layer with discrete diffusion for node attributes and edges.
Problem
Generating realistic, large-scale DAGs that respect strong directional (topological) and logical dependencies, e.g., for synthetic benchmarking of computing systems and NAS, where prior models were limited to small DAGs and violate partial-order inductive biases.
Approach
Decompose a DAG's partial order into a unique ordered partition of layers (bipartite graphs); autoregress over layers and use D3PM-based discrete diffusion within each layer to model incomparable-node dependencies, with a layer-index-based denoising schedule for quality-efficiency trade-off.
Key results
- On LP with rho=0, LayerDAG reaches 0.56 validity versus 0.37 for the best baseline (OneShotDAG) and 0.23-0.25 for GraphPNAS/D-VAE.
- On TPU Tile conditional generation, LayerDAG achieves Pearson 0.65 and MAE 1.2 for the surrogate model, closest to real-graph performance (0.75 / 0.9) among generative models.
- In TPU Tile 5th-quantile extrapolation, LayerDAG improves BiMPNN Pearson correlation to 0.22 while most baselines obtain negative values.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use autoregressive layerwise generation with diffusion rather than OneShotDAG's non-autoregressive generation (ablation) | LayerDAG · LP (ρ=0) | validity: 0.37 ± 0.02 -> 0.56 ± 0.02 | Helped |
| use autoregressive layerwise generation with diffusion rather than OneShotDAG's non-autoregressive generation (ablation) | LayerDAG · LP (ρ=0.5) | validity: 0.31 ± 0.07 -> 0.63 ± 0.00 | Helped |
| use autoregressive layerwise generation with diffusion rather than OneShotDAG's non-autoregressive generation (ablation) | LayerDAG · LP (ρ=1) | validity: 0.50 ± 0.08 -> 0.96 ± 0.02 | Helped |
| use multiple denoising steps rather than a single denoising step (ablation) | LayerDAG · LP (ρ=0) | validity: 0.26 ± 0.06 -> 0.56 ± 0.02 | Helped |
| use multiple denoising steps rather than a single denoising step (ablation) | LayerDAG · TPU Tile | Pearson: 0.37 ± 0.11 -> 0.65 ± 0.01 | Helped |
| use multiple denoising steps rather than a single denoising step (ablation) | LayerDAG · HLS | Pearson: 0.27 ± 0.26 -> 0.85 ± 0.02 | Helped |
| use multiple denoising steps rather than a single denoising step (ablation) | LayerDAG · NA-Edge | Pearson: 0.956 ± 0.011 -> 0.990 ± 0.005 | Helped |
| vary denoising steps by layer index instead of using a constant schedule (ablation) | LayerDAG · LP (ρ=0), TPU Tile, HLS | generation quality at equal time budget | Helped |
| use a constant number of denoising steps across layers (ablation) | LayerDAG · LP (ρ=0), TPU Tile, HLS | generation quality-efficiency trade-off | No clear effect |
| generate node attributes and structure jointly through the layerwise diffusion model | LayerDAG · extended LP (ρ=0) | full validity: 0.094 -> 0.195 | Helped |
| use LayerDAG for conditional generation instead of GraphRNN | conditional DAG generation · TPU Tile | Pearson: 0.62 ± 0.02 -> 0.65 ± 0.01 | Helped |
| use LayerDAG for conditional generation instead of D-VAE | conditional DAG generation · HLS | Pearson: 0.82 ± 0.04 -> 0.85 ± 0.02 | Helped |
Surprising findings
- Non-autoregressive OneShotDAG and single-step LayerDAG (T=1) both lag the full model, showing multi-step diffusion refinement matters.
- Most baselines fail to attain a positive Pearson correlation in the extrapolation setting.
Limitations
- Only categorical node attributes are handled; real-valued attributes are left to extensions.
- Layer-index-based schedule assumes complexity grows with depth and may not help for trees with stationary layer distributions.
- Real-world ML-based extrapolation gains remain modest (Pearson about 0.2).
Experimental setup
Datasets: LP (synthetic latent preferential DAGs) TPU Tile HLS NA-Edge TpuGraphs
Benchmarks: LP TPU Tile HLS NA-Edge
Metrics: validity 1-Wasserstein distance MMD Pearson correlation MAE
Baselines: GraphRNN D-VAE GraphPNAS OneShotDAG LayerDAG (T=1)
Builds on: D3PM DiGress D-VAE GraphPNAS GRAN
Closest papers by meaning
- SBGD: Improving Graph Diffusion Generative Model via Stochastic Block Diffusion (ICML 2025 · similarity 0.86)
- Pard: Permutation-Invariant Autoregressive Diffusion for Graph Generation (NeurIPS 2024 · similarity 0.85)
- Discrete-state Continuous-time Diffusion for Graph Generation (NeurIPS 2024 · similarity 0.85)
- DeFoG: Discrete Flow Matching for Graph Generation (ICML 2025 · similarity 0.85)
- ProDAG: Projected Variational Inference for Directed Acyclic Graphs (NeurIPS 2025 · similarity 0.85)
- When Edge Independence Fails: Joint Graph Diffusion with Latent Sociability Priors (NeurIPS 2026 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.