DeFoG: Discrete Flow Matching for Graph Generation

• URL: http://arxiv.org/abs/2410.04263v1
• Date: Sat, 5 Oct 2024 18:52:54 GMT
• Title: DeFoG: Discrete Flow Matching for Graph Generation
• Authors: Yiming Qin, Manuel Madeira, Dorina Thanou, Pascal Frossard,
• Abstract summary: 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.
• Score: 45.037260759871124
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Graph generation is fundamental in diverse scientific applications, due to its ability to reveal the underlying distribution of complex data, and eventually generate new, realistic data points. Despite the success of diffusion models in this domain, those face limitations in sampling efficiency and flexibility, stemming from the tight coupling between the training and sampling stages. To address this, we propose DeFoG, a novel framework using discrete flow matching for graph generation. DeFoG employs a flow-based approach that features an efficient linear interpolation noising process and a flexible denoising process based on a continuous-time Markov chain formulation. We leverage an expressive graph transformer and ensure desirable node permutation properties to respect graph symmetry. Crucially, our framework enables a disentangled design of the training and sampling stages, enabling more effective and efficient optimization of model performance. We navigate this design space by introducing several algorithmic improvements that boost the model performance, consistently surpassing existing diffusion models. We also theoretically demonstrate that, for general discrete data, discrete flow models can faithfully replicate the ground truth distribution - a result that naturally extends to graph data and reinforces DeFoG's foundations. Extensive experiments show that DeFoG achieves state-of-the-art results on synthetic and molecular datasets, improving both training and sampling efficiency over diffusion models, and excels in conditional generation on a digital pathology dataset.

Related papers

• Cometh: A continuous-time discrete-state graph diffusion model [8.444907767842228]
  We propose Cometh, a continuous-time discrete-state graph diffusion model, tailored to the specificities of graph data. In terms of VUN samples, Cometh obtains a near-perfect performance of 99.5% on the planar graph dataset and outperforms DiGress by 12.6% on the large GuacaMol dataset.
  arXiv  Detail & Related papers  (2024-06-10T16:39:39Z)
• Fisher Flow Matching for Generative Modeling over Discrete Data [12.69975914345141]
  We introduce Fisher-Flow, a novel flow-matching model for discrete data. Fisher-Flow takes a manifestly geometric perspective by considering categorical distributions over discrete data. We prove that the gradient flow induced by Fisher-Flow is optimal in reducing the forward KL divergence.
  arXiv  Detail & Related papers  (2024-05-23T15:02:11Z)
• Discrete-state Continuous-time Diffusion for Graph Generation [46.626952802292074]
  Diffusion generative models have been applied to graph generation tasks. We formulate the graph diffusion generation in a discrete-state continuous-time setting. Our proposed model shows competitive empirical performance against state-of-the-art graph generation solutions.
  arXiv  Detail & Related papers  (2024-05-19T00:09:42Z)
• Distribution-Aware Data Expansion with Diffusion Models [55.979857976023695]
  We propose DistDiff, a training-free data expansion framework based on the distribution-aware diffusion model. DistDiff consistently enhances accuracy across a diverse range of datasets compared to models trained solely on original data.
  arXiv  Detail & Related papers  (2024-03-11T14:07:53Z)
• Fast Graph Generative Model via Spectral Diffusion [38.31052833073743]
  We argue that running full-rank diffusion SDEs on the whole space hinders diffusion models from learning graph topology generation. We propose an efficient yet effective Graph Spectral Diffusion Model (GSDM), which is driven by low-rank diffusion SDEs on the graph spectrum space.
  arXiv  Detail & Related papers  (2022-11-16T12:56:32Z)
• Data-heterogeneity-aware Mixing for Decentralized Learning [63.83913592085953]
  We characterize the dependence of convergence on the relationship between the mixing weights of the graph and the data heterogeneity across nodes. We propose a metric that quantifies the ability of a graph to mix the current gradients. Motivated by our analysis, we propose an approach that periodically and efficiently optimize the metric.
  arXiv  Detail & Related papers  (2022-04-13T15:54:35Z)
• Score-based Generative Modeling of Graphs via the System of Stochastic Differential Equations [57.15855198512551]
  We propose a novel score-based generative model for graphs with a continuous-time framework. We show that our method is able to generate molecules that lie close to the training distribution yet do not violate the chemical valency rule.
  arXiv  Detail & Related papers  (2022-02-05T08:21:04Z)
• 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.