Permutation Invariant Graph Generation via Score-Based Generative Modeling

By Chenhao Niu, Yang Song, Jiaming Song, Shengjia Zhao, Aditya Grover, Stefano Ermon. 2020

373 citations recorded by the source corpus.

Learning generative models for graph-structured data is challenging because graphs are discrete, combinatorial, and the underlying data distribution is invariant to the ordering of nodes. However, most of the existing generative models for graphs are not invariant to the chosen ordering, which might lead to an undesirable bias in the learned distribution. To address this difficulty, 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 (a.k.a., the score function). This permutation equivariant model of gradients implicitly defines a permutation invariant distribution for graphs. We train this graph neural network with score matching and sample from it with annealed Langevin dynamics. In our experiments, we first demonstrate the capacity of this new architecture in learning discrete graph algorithms. For graph generation, we find that our learning approach achieves better or comparable results to existing models on benchmark datasets.

Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition, Generative Models

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Vision and Pattern Recognition

In Generative Models

Citations in the corpus

D2C: Diffusion-Decoding Models for Few-Shot Conditional Generation (2021, background): “Generative models trained on large amounts of unlabeled data have achieved great success in various domains including images [8, 50, 75, 42], text [56, 2], audio [26, 71, 93, 62], and graphs [36, 67].”
Score-based Generative Modeling in Latent Space (2021, methodology): “Recently, [11] presented a method to generate graphs using score-based models, relaxing the entries of adjacency matrices to continuous values.”
Score-Based Generative Modeling through Stochastic Differential Equations (2020, neutral): “…Goyal et al., 2017; Du & Mordatch, 2019), have proven effective at generation of images (Song & Ermon, 2019; 2020; Ho et al., 2020), audio (Chen et al., 2020; Kong et al., 2020), graphs (Niu et al., 2020), and shapes (Cai ˚ Work partially done during an internship at Google Brain. et al., 2020).”
Grad-TTS: A Diffusion Probabilistic Model for Text-to-Speech (2021, background): “…of generative models called Diffusion Probabilistic Models (DPMs) (Sohl-Dickstein et al., 2015) has started to prove its capability to model complex data distributions such as images (Ho et al., 2020), shapes (Cai et al., 2020), graphs (Niu et al., 2020), handwriting (Luh-man & Luhman, 2020).”
Gotta Go Fast When Generating Data with Score-Based Models (2021, neutral): “…al., 2020, Song et al., 2020a, Piché-Taillefer, 2021] have been very successful at generating data from various modalities, such as images [Ho et al., 2020, Song et al., 2020a], audio [Chen et al., 2020, Kong et al., 2020, Mittal et al., 2021, Kameoka et al., 2020], and graphs [Niu et al., 2020].”
Structured Denoising Diffusion Models in Discrete State-Spaces (2021, background): “Some works [29, 27] have dealt with discrete data by embedding it in continuous space and leveraging Gaussian diffusion, but have not applied this to text.”
Post-Training Quantization on Diffusion Models (2022, background): “nomenal success in various generative tasks, such as images [10, 36, 23], audio [20], video [31], and graphs [24].”
Diffusion Schrödinger Bridge with Applications to Score-Based Generative Modeling (2021, result): “…al. (2020); Chen et al. (2021a); Kong et al. (2021); Gao et al. (2020); Jolicoeur-Martineau et al. (2021b); Ho et al. (2020); Song and Ermon (2020); Song et al. (2020, 2021); Niu et al. (2020); Durkan and Song (2021); Hoogeboom et al. (2021); Saharia et al. (2021); Luhman and Luhman (2021, 2020);…”
SDEdit: Image Synthesis and Editing with Stochastic Differential Equations (2021, background): “Denoising diffusion probabilistic models [23, 50] and score-based generative models [52, 55] are a new class of generative models that have found great success in image generation [52, 23, 53, 51, 55, 28, 13], audio synthesis [33] and graph generation [37].”
ResShift: Efficient Diffusion Model for Image Super-resolution by Residual Shifting (2023, background): “Attributed to its robust theoretical foundation, the diffusion model has achieved impressive success in the generation of images [3, 11], audio [24], graph [25] and shapes [26].”
Score-based diffusion models for accelerated MRI (2021, methodology): “, 2021), and even graph (Niu et al., 2020) synthesis.”
Diffusion Models: A Comprehensive Survey of Methods and Applications (2022, methodology): “There are also generalization examples of data with invariant structures, such as graphs and point clouds [100, 159, 237].”
DiGress: Discrete Denoising diffusion for graph generation (2022, methodology): “Previous diffusion models for graphs proposed to embed the graphs in a continuous space and add Gaussian noise to the node features and graph adjacency matrix (Niu et al., 2020; Jo et al., 2022).”
DiffGAN-TTS: High-Fidelity and Efficient Text-to-Speech with Denoising Diffusion GANs (2022, background): “Diffusion models have obtained state-of-the-art results in several important domains, including image synthesis(Ho et al., 2020), audio synthesis(Kong et al., 2021; Chen et al., 2021; Popov et al., 2021), graphs(Niu et al., 2020), and symbolic music generation (Mittal et al., 2021).”
Q-Diffusion: Quantizing Diffusion Models (2023, background): “strate their power in various applications such as image super-resolution [37, 22], inpainting [44], shape generation [5], graph generation [32], image-to-image translation [40], and molecular conformation generation [47].”
Autoregressive Denoising Diffusion Models for Multivariate Probabilistic Time Series Forecasting (2021, background): “Concurrently, since EBMs are not constrained by the form of their functional approximators, one natural way to improve the model would be to incorporate architectural choices that best encode the inductive bias of the problem being tackled, for example with graph neural networks (Niu et al., 2020) w”
DIFUSCO: Graph-based Diffusion Solvers for Combinatorial Optimization (2023, background): “The most relevant work might be Niu et al. [86], which proposed a continuous score-based generative framework for graphs, but they only evaluated simple non-NP-hard CO tasks such as Shortest Path and Maximum Spanning Tree.”
Score-based Generative Modeling of Graphs via the System of Stochastic Differential Equations (2022, methodology): “Apart from the likelihood-based methods, Niu et al. (2020) introduced a score-based generative model for graphs, namely, edge-wise dense prediction graph neural network (EDP-GNN).”