Efficient Graph Generation with Graph Recurrent Attention Networks

By Renjie Liao, Yujia Li, Yang Song, Shenlong Wang, Charlie Nash, William L. Hamilton, David Kristjanson Duvenaud, Raquel Urtasun, Richard S. Zemel. 2019

410 citations recorded by the source corpus.

We propose a new family of efficient and expressive deep generative models of graphs, called Graph Recurrent Attention Networks (GRANs). Our model generates graphs one block of nodes and associated edges at a time. The block size and sampling stride allow us to trade off sample quality for efficiency. Compared to previous RNN-based graph generative models, our framework better captures the auto-regressive conditioning between the already-generated and to-be-generated parts of the graph using Graph Neural Networks (GNNs) with attention. This not only reduces the dependency on node ordering but also bypasses the long-term bottleneck caused by the sequential nature of RNNs. Moreover, we parameterize the output distribution per block using a mixture of Bernoulli, which captures the correlations among generated edges within the block. Finally, we propose to handle node orderings in generation by marginalizing over a family of canonical orderings. On standard benchmarks, we achieve state-of-the-art time efficiency and sample quality compared to previous models. Additionally, we show our model is capable of generating large graphs of up to 5K nodes with good quality. Our code is released at: \url{https://github.com/lrjconan/GRAN}.

Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition, Graph Learning

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 Graph Learning

Citations in the corpus

Score-based Generative Modeling in Latent Space (2021, methodology): “LSGM would allow to model graph data more naturally using encoders and decoders tailored to graphs [43, 44, 45, 46].”
On the Binding Problem in Artificial Neural Networks (2020, methodology): “The other approach is to directly infer the connectivity between nodes iteratively based on message passing, e.g. for a fixed number of nodes as in Neural Relational Inference (NRI; Kipf et al., 2018) or adaptively as in Graph Recurrent Attention Networks (GRANs; Liao et al., 2019).”
Iterative Deep Graph Learning for Graph Neural Networks: Better and Robust Node Embeddings (2020, background): “Other related works include structure inference in probabilistic graphical models [9, 60, 57], and graph generation [36, 46], which have a different goal from ours.”
Deep Generative Models in Engineering Design: A Review (2021, background): “Cons: Despite the developments of graph neural networks (GNNs) in the computer science community [47, 48, 49, 50] and their success in molecular graph generation [51, 52], there is less usage of graph-based DGMs in the design community, possibly due to the lack of graph-based design datasets.”
Score-based Generative Modeling of Graphs via the System of Stochastic Differential Equations (2022, methodology): “Among them, autoregressive models (You et al., 2018b; Liao et al., 2019) construct a graph via sequential decisions, while one-shot generative models (De Cao & Kipf, 2018; Liu et al., 2019) generate components of a graph at once.”
Equivariant Diffusion for Molecule Generation in 3D (2022, methodology): “Some examples are autoregressive methods such as (Liu et al., 2018; You et al., 2018; Liao et al., 2019), and one-shot approaches such as (Simonovsky & Komodakis, 2018; De Cao & Kipf, 2018; Bresson & Laurent, 2019; Kosiorek et al., 2020; Krawczuk et al., 2021).”
DiGress: Discrete Denoising diffusion for graph generation (2022, methodology): “…& Frossard, 2021), SPECTRE (Martinkus et al., 2022), GraphNVP (Madhawa et al., 2019), GDSS (Jo et al., 2022), GraphRNN (You et al., 2018), GRAN (Liao et al., 2019), JT-VAE (Jin et al., 2018), NAGVAE (Kwon et al., 2020) and GraphINVENT We first evaluate DiGress on the benchmark proposed in…”
A Unifying Review of Deep and Shallow Anomaly Detection (2020, background): “Likewise, there exist many DGMs for virtually all data types, including time-series data [292], [294], text [295], [296], and graphs [297]–[299], all of which may potentially be used for AD.”
Graph Representation Learning (2020, methodology): “Existing works have used this strategy with graph statistics such as degree distributions, graphlet counts, and spectral features, with distributional distances computed using variants of the total variation score and the first Wasserstein distance [Liao et al., 2019b, You et al., 2018].”
GPT-GNN: Generative Pre-Training of Graph Neural Networks (2020, methodology): “Note that most existing graph generation methods [18, 43] follow the auto-regressive manner to factorize the probability objective, i.e., the nodes in the graph come in an order, and the edges are generated by connecting each new arriving node to existing nodes.”
Hierarchical Generation of Molecular Graphs using Structural Motifs (2020, positive): “When the top motif layer is removed, the translation accuracy drops slightly by 0.8% Our model is closely related to Liao et al. (2019) which generate graphs one block of nodes and edges at a time.”
Meta-Sim2: Unsupervised Learning of Scene Structure for Synthetic Data Generation (2020, background): “Generative models of graphs and trees [42,17,73,43,10,3] generally produce graphs with richer structure with more flexibility over grammar based models, but often fail to produce syntactically correct graphs for cases with a defined syntax such as programs and scene graphs.”