Graph Generation via Spectral Diffusion

• URL: http://arxiv.org/abs/2402.18974v1
• Date: Thu, 29 Feb 2024 09:26:46 GMT
• Title: Graph Generation via Spectral Diffusion
• Authors: Giorgia Minello, Alessandro Bicciato, Luca Rossi, Andrea Torsello, Luca Cosmo
• Abstract summary: We present GRASP, a novel graph generative model based on 1) the spectral decomposition of the graph Laplacian matrix and 2) a diffusion process. Specifically, we propose to use a denoising model to sample eigenvectors and eigenvalues from which we can reconstruct the graph Laplacian and adjacency matrix. Our permutation invariant model can also handle node features by concatenating them to the eigenvectors of each node.
• Score: 51.60814773299899
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this paper, we present GRASP, a novel graph generative model based on 1) the spectral decomposition of the graph Laplacian matrix and 2) a diffusion process. Specifically, we propose to use a denoising model to sample eigenvectors and eigenvalues from which we can reconstruct the graph Laplacian and adjacency matrix. Our permutation invariant model can also handle node features by concatenating them to the eigenvectors of each node. Using the Laplacian spectrum allows us to naturally capture the structural characteristics of the graph and work directly in the node space while avoiding the quadratic complexity bottleneck that limits the applicability of other methods. This is achieved by truncating the spectrum, which as we show in our experiments results in a faster yet accurate generative process. An extensive set of experiments on both synthetic and real world graphs demonstrates the strengths of our model against state-of-the-art alternatives.

Related papers

• Discrete Graph Auto-Encoder [52.50288418639075]
  We introduce a new framework named Discrete Graph Auto-Encoder (DGAE) We first use a permutation-equivariant auto-encoder to convert graphs into sets of discrete latent node representations. In the second step, we sort the sets of discrete latent representations and learn their distribution with a specifically designed auto-regressive model.
  arXiv  Detail & Related papers  (2023-06-13T12:40:39Z)
• Graph Classification Gaussian Processes via Spectral Features [7.474662887810221]
  Graph classification aims to categorise graphs based on their structure and node attributes. In this work, we propose to tackle this task using tools from graph signal processing by deriving spectral features. We show that even such a simple approach, having no learned parameters, can yield competitive performance compared to strong neural network and graph kernel baselines.
  arXiv  Detail & Related papers  (2023-06-06T15:31:05Z)
• 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)
• Conditional Diffusion Based on Discrete Graph Structures for Molecular Graph Generation [32.66694406638287]
  We propose a Conditional Diffusion model based on discrete Graph Structures (CDGS) for molecular graph generation. Specifically, we construct a forward graph diffusion process on both graph structures and inherent features through differential equations (SDE) We present a specialized hybrid graph noise prediction model that extracts the global context and the local node-edge dependency from intermediate graph states.
  arXiv  Detail & Related papers  (2023-01-01T15:24:15Z)
• Graphon Pooling for Reducing Dimensionality of Signals and Convolutional Operators on Graphs [131.53471236405628]
  We present three methods that exploit the induced graphon representation of graphs and graph signals on partitions of [0, 1]2 in the graphon space. We prove that those low dimensional representations constitute a convergent sequence of graphs and graph signals. We observe that graphon pooling performs significantly better than other approaches proposed in the literature when dimensionality reduction ratios between layers are large.
  arXiv  Detail & Related papers  (2022-12-15T22:11:34Z)
• DiGress: Discrete Denoising diffusion for graph generation [79.13904438217592]
  DiGress is a discrete denoising diffusion model for generating graphs with categorical node and edge attributes. It achieves state-of-the-art performance on molecular and non-molecular datasets, with up to 3x validity improvement. It is also the first model to scale to the large GuacaMol dataset containing 1.3M drug-like molecules.
  arXiv  Detail & Related papers  (2022-09-29T12:55:03Z)
• Node Copying: A Random Graph Model for Effective Graph Sampling [35.957719744856696]
  We introduce the node copying model for constructing a distribution over graphs. We show the usefulness of the copying model in three tasks. We employ our proposed model to mitigate the effect of adversarial attacks on the graph topology.
  arXiv  Detail & Related papers  (2022-08-04T04:04:49Z)
• Capturing Graphs with Hypo-Elliptic Diffusions [7.704064306361941]
  We show that the distribution of random walks evolves according to a diffusion equation defined using the graph Laplacian. This results in a novel tensor-valued graph operator, which we call the hypo-elliptic graph Laplacian. We show that this method competes with graph transformers on datasets requiring long-range reasoning but scales only linearly in the number of edges.
  arXiv  Detail & Related papers  (2022-05-27T16:47:34Z)
• A Graph VAE and Graph Transformer Approach to Generating Molecular Graphs [1.6631602844999724]
  We propose a variational autoencoder and a transformer based model which fully utilise graph convolutional and graph pooling layers. The transformer model implements a novel node encoding layer, replacing the position encoding typically used in transformers, to create a transformer with no position information that operates on graphs. In experiments we chose a benchmark task of molecular generation, given the importance of both generated node and edge features.
  arXiv  Detail & Related papers  (2021-04-09T13:13:06Z)
• Permutation Invariant Graph Generation via Score-Based Generative Modeling [114.12935776726606]
  We propose a permutation invariant approach to modeling graphs, using the recent framework of score-based generative modeling. In particular, we design a permutation equivariant, multi-channel graph neural network to model the gradient of the data distribution at the input graph. For graph generation, we find that our learning approach achieves better or comparable results to existing models on benchmark datasets.
  arXiv  Detail & Related papers  (2020-03-02T03:06:14Z)

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.