SeaDAG: Semi-autoregressive Diffusion for Conditional Directed Acyclic Graph Generation

• URL: http://arxiv.org/abs/2410.16119v1
• Date: Mon, 21 Oct 2024 15:47:03 GMT
• Title: SeaDAG: Semi-autoregressive Diffusion for Conditional Directed Acyclic Graph Generation
• Authors: Xinyi Zhou, Xing Li, Yingzhao Lian, Yiwen Wang, Lei Chen, Mingxuan Yuan, Jianye Hao, Guangyong Chen, Pheng Ann Heng,
• Abstract summary: We introduce SeaDAG, a semi-autoregressive diffusion model for conditional generation of Directed Acyclic Graphs (DAGs) Unlike conventional autoregressive generation that lacks a global graph structure view, our method maintains a complete graph structure at each diffusion step. We explicitly train the model to learn graph conditioning with a condition loss, which enhances the diffusion model's capacity to generate realistic DAGs.
• Score: 83.52157311471693
• License:
• Abstract: We introduce SeaDAG, a semi-autoregressive diffusion model for conditional generation of Directed Acyclic Graphs (DAGs). Considering their inherent layer-wise structure, we simulate layer-wise autoregressive generation by designing different denoising speed for different layers. Unlike conventional autoregressive generation that lacks a global graph structure view, our method maintains a complete graph structure at each diffusion step, enabling operations such as property control that require the full graph structure. Leveraging this capability, we evaluate the DAG properties during training by employing a graph property decoder. We explicitly train the model to learn graph conditioning with a condition loss, which enhances the diffusion model's capacity to generate graphs that are both realistic and aligned with specified properties. We evaluate our method on two representative conditional DAG generation tasks: (1) circuit generation from truth tables, where precise DAG structures are crucial for realizing circuit functionality, and (2) molecule generation based on quantum properties. Our approach demonstrates promising results, generating high-quality and realistic DAGs that closely align with given conditions.

Related papers

• LayerDAG: A Layerwise Autoregressive Diffusion Model for Directed Acyclic Graph Generation [17.94316378710172]
  This paper introduces LayerDAG, an autoregressive diffusion model, to generate realistic directed acyclic graphs (DAGs) By interpreting the partial order of nodes as a sequence of bipartite graphs, LayerDAG decouples the strong node dependencies into manageable units that can be processed sequentially. 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.
  arXiv  Detail & Related papers  (2024-11-04T17:47:15Z)
• Dynamic and Textual Graph Generation Via Large-Scale LLM-based Agent Simulation [70.60461609393779]
  GraphAgent-Generator (GAG) is a novel simulation-based framework for dynamic graph generation. Our framework effectively replicates seven macro-level structural characteristics in established network science theories. It supports generating graphs with up to nearly 100,000 nodes or 10 million edges, with a minimum speed-up of 90.4%.
  arXiv  Detail & Related papers  (2024-10-13T12:57:08Z)
• DeFoG: Discrete Flow Matching for Graph Generation [45.037260759871124]
  We propose DeFoG, a novel framework using discrete flow matching for graph generation. DeFoG employs a flow-based approach that features an efficient linear noising process and a flexible denoising process. We show that DeFoG achieves state-of-the-art results on synthetic and molecular datasets.
  arXiv  Detail & Related papers  (2024-10-05T18:52:54Z)
• IFH: a Diffusion Framework for Flexible Design of Graph Generative Models [53.219279193440734]
  Graph generative models can be classified into two prominent families: one-shot models, which generate a graph in one go, and sequential models, which generate a graph by successive additions of nodes and edges. This paper proposes a graph generative model, called Insert-Fill-Halt (IFH), that supports the specification of a sequentiality degree.
  arXiv  Detail & Related papers  (2024-08-23T16:24:40Z)
• Generative Modelling of Structurally Constrained Graphs [44.28728853270471]
  We present ConStruct, a novel framework that allows for hard-constraining graph diffusion models to incorporate specific properties, such as planarity or acyclicity. Our approach ensures that the sampled graphs remain within the domain of graphs that verify the specified property throughout the entire trajectory in both the forward and reverse processes.
  arXiv  Detail & Related papers  (2024-06-25T07:54:32Z)
• Hyperbolic Graph Diffusion Model [24.049660417511074]
  We propose a novel graph generation method called, Hyperbolic Graph Diffusion Model (HGDM) HGDM consists of an auto-encoder to encode nodes into successive hyperbolic embeddings, and a DM that operates in the hyperbolic latent space. Experiments show that HGDM achieves better performance in generic graph and molecule generation benchmarks, with a $48%$ improvement in the quality of graph generation with highly hierarchical structures.
  arXiv  Detail & Related papers  (2023-06-13T08:22:18Z)
• Graph Generation with Diffusion Mixture [57.78958552860948]
  Generation of graphs is a major challenge for real-world tasks that require understanding the complex nature of their non-Euclidean structures. We propose a generative framework that models the topology of graphs by explicitly learning the final graph structures of the diffusion process.
  arXiv  Detail & Related papers  (2023-02-07T17:07:46Z)
• SCGG: A Deep Structure-Conditioned Graph Generative Model [9.046174529859524]
  A conditional deep graph generation method called SCGG considers a particular type of structural conditions. The architecture of SCGG consists of a graph representation learning network and an autoregressive generative model, which is trained end-to-end. Experimental results on both synthetic and real-world datasets demonstrate the superiority of our method compared with state-of-the-art baselines.
  arXiv  Detail & Related papers  (2022-09-20T12:33:50Z)
• Heterogeneous Graph Transformer [49.675064816860505]
  Heterogeneous Graph Transformer (HGT) architecture for modeling Web-scale heterogeneous graphs. To handle dynamic heterogeneous graphs, we introduce the relative temporal encoding technique into HGT. To handle Web-scale graph data, we design the heterogeneous mini-batch graph sampling algorithm---HGSampling---for efficient and scalable training.
  arXiv  Detail & Related papers  (2020-03-03T04:49:21Z)
• Block-Approximated Exponential Random Graphs [77.4792558024487]
  An important challenge in the field of exponential random graphs (ERGs) is the fitting of non-trivial ERGs on large graphs. We propose an approximative framework to such non-trivial ERGs that result in dyadic independence (i.e., edge independent) distributions. Our methods are scalable to sparse graphs consisting of millions of nodes.
  arXiv  Detail & Related papers  (2020-02-14T11:42:16Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.