Generative Modelling of Structurally Constrained Graphs

• URL: http://arxiv.org/abs/2406.17341v2
• Date: Fri, 06 Dec 2024 08:07:23 GMT
• Title: Generative Modelling of Structurally Constrained Graphs
• Authors: Manuel Madeira, Clement Vignac, Dorina Thanou, Pascal Frossard,
• Abstract summary: We present ConStruct, a novel framework that enables graph diffusion models to incorporate hard constraints on specific properties, such as planarity or acyclicity. Our approach ensures that the sampled graphs remain within the domain of graphs that satisfy the specified property throughout the entire trajectory in both the forward and reverse processes.
• Score: 44.28728853270471
• License:
• Abstract: Graph diffusion models have emerged as state-of-the-art techniques in graph generation; yet, integrating domain knowledge into these models remains challenging. Domain knowledge is particularly important in real-world scenarios, where invalid generated graphs hinder deployment in practical applications. Unconstrained and conditioned graph diffusion models fail to guarantee such domain-specific structural properties. We present ConStruct, a novel framework that enables graph diffusion models to incorporate hard constraints on specific properties, such as planarity or acyclicity. Our approach ensures that the sampled graphs remain within the domain of graphs that satisfy the specified property throughout the entire trajectory in both the forward and reverse processes. This is achieved by introducing an edge-absorbing noise model and a new projector operator. ConStruct demonstrates versatility across several structural and edge-deletion invariant constraints and achieves state-of-the-art performance for both synthetic benchmarks and attributed real-world datasets. For example, by incorporating planarity constraints in digital pathology graph datasets, the proposed method outperforms existing baselines, improving data validity by up to 71.1 percentage points.

Related papers

• DiffGraph: Heterogeneous Graph Diffusion Model [16.65576765238224]
  Graph Neural Networks (GNNs) have revolutionized graph-structured data modeling, yet traditional GNNs struggle with complex heterogeneous structures prevalent in real-world scenarios. We present the Heterogeneous Graph Diffusion Model (DiffGraph), a pioneering framework that introduces an innovative cross-view denoising strategy. At its core, DiffGraph features a sophisticated latent heterogeneous graph diffusion mechanism, implementing a novel forward and backward diffusion process for superior noise management.
  arXiv  Detail & Related papers  (2025-01-04T15:30:48Z)
• SeaDAG: Semi-autoregressive Diffusion for Conditional Directed Acyclic Graph Generation [83.52157311471693]
  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.
  arXiv  Detail & Related papers  (2024-10-21T15:47:03Z)
• AnyGraph: Graph Foundation Model in the Wild [16.313146933922752]
  Graph foundation models offer the potential to learn robust, generalizable representations from graph data. In this work, we investigate a unified graph model, AnyGraph, designed to handle key challenges. Our experiments on diverse 38 graph datasets have demonstrated the strong zero-shot learning performance of AnyGraph.
  arXiv  Detail & Related papers  (2024-08-20T09:57:13Z)
• Improving embedding of graphs with missing data by soft manifolds [51.425411400683565]
  The reliability of graph embeddings depends on how much the geometry of the continuous space matches the graph structure. We introduce a new class of manifold, named soft manifold, that can solve this situation. Using soft manifold for graph embedding, we can provide continuous spaces to pursue any task in data analysis over complex datasets.
  arXiv  Detail & Related papers  (2023-11-29T12:48:33Z)
• 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)
• Iterative Scene Graph Generation [55.893695946885174]
  Scene graph generation involves identifying object entities and their corresponding interaction predicates in a given image (or video) Existing approaches to scene graph generation assume certain factorization of the joint distribution to make the estimation iteration feasible. We propose a novel framework that addresses this limitation, as well as introduces dynamic conditioning on the image.
  arXiv  Detail & Related papers  (2022-07-27T10:37:29Z)
• Energy-Based Learning for Scene Graph Generation [26.500496033477127]
  We introduce a novel energy-based learning framework for generating scene graphs. The proposed formulation allows for efficiently incorporating the structure of scene graphs in the output space. We use the proposed framework to train existing state-of-the-art models and obtain a significant performance improvement.
  arXiv  Detail & Related papers  (2021-03-03T07:11:23Z)
• GraphOpt: Learning Optimization Models of Graph Formation [72.75384705298303]
  We propose an end-to-end framework that learns an implicit model of graph structure formation and discovers an underlying optimization mechanism. The learned objective can serve as an explanation for the observed graph properties, thereby lending itself to transfer across different graphs within a domain. GraphOpt poses link formation in graphs as a sequential decision-making process and solves it using maximum entropy inverse reinforcement learning algorithm.
  arXiv  Detail & Related papers  (2020-07-07T16:51:39Z)
• Quantifying Challenges in the Application of Graph Representation Learning [0.0]
  We provide an application oriented perspective to a set of popular embedding approaches. We evaluate their representational power with respect to real-world graph properties. Our results suggest that "one-to-fit-all" GRL approaches are hard to define in real-world scenarios.
  arXiv  Detail & Related papers  (2020-06-18T03:19:43Z)
• Interpretable Deep Graph Generation with Node-Edge Co-Disentanglement [55.2456981313287]
  We propose a new disentanglement enhancement framework for deep generative models for attributed graphs. A novel variational objective is proposed to disentangle the above three types of latent factors, with novel architecture for node and edge deconvolutions. Within each type, individual-factor-wise disentanglement is further enhanced, which is shown to be a generalization of the existing framework for images.
  arXiv  Detail & Related papers  (2020-06-09T16:33:49Z)

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.