GraphRNN: Generating Realistic Graphs with Deep Auto-regressive Models

By Jiaxuan You, Rex Ying, Xiang Ren, William L. Hamilton, Jure Leskovec. 2018

1,019 citations recorded by the source corpus.

Modeling and generating graphs is fundamental for studying networks in biology, engineering, and social sciences. However, modeling complex distributions over graphs and then efficiently sampling from these distributions is challenging due to the non-unique, high-dimensional nature of graphs and the complex, non-local dependencies that exist between edges in a given graph. Here we propose GraphRNN, a deep autoregressive model that addresses the above challenges and approximates any distribution of graphs with minimal assumptions about their structure. GraphRNN learns to generate graphs by training on a representative set of graphs and decomposes the graph generation process into a sequence of node and edge formations, conditioned on the graph structure generated so far. In order to quantitatively evaluate the performance of GraphRNN, we introduce a benchmark suite of datasets, baselines and novel evaluation metrics based on Maximum Mean Discrepancy, which measure distances between sets of graphs. Our experiments show that GraphRNN significantly outperforms all baselines, learning to generate diverse graphs that match the structural characteristics of a target set, while also scaling to graphs 50 times larger than previous deep models.

Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition, Generative Models, 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 Generative Models

In Graph Learning

Citations in the corpus

E(n) Equivariant Graph Neural Networks (2021, methodology): “• Community Small: We used the original code from (You et al., 2018) (https://github.com/JiaxuanYou/graph-generation) to generate a Community Small dataset.”
Graph Convolutional Neural Networks for Web-Scale Recommender Systems (2018, background): “, to exploit user-to-item interaction graphs as well as social graphs) [6, 19, 21, 24, 29, 30].”
Position-aware Graph Neural Networks (2019, background): “…node classiﬁcation (Kipf & Welling, 2017), link prediction (Grover & Leskovec, 2016), graph classiﬁcation (Ying et al., 2018b) and graph generation (You et al., 2018b), with successful applications across domains such as social and information networks (Ying et al., 2018a), chemistry (You et…”
Graph Normalizing Flows (2019, methodology): “The result is a fully permutation-invariant model that achieves competitive results compared to GraphRNN [30], while being more well-suited to parallel computing architectures.”
Recurrent Event Network for Reasoning over Temporal Knowledge Graphs (2019, methodology): “Here we analyze the model capacity of RE-N ET of capturing complex time-invariant local structure like [10], as well as the emerging global community structure as [28].”
Self-Supervised Learning: Generative or Contrastive (2020, background): “[141] propose GraphRNN to generate realistic graphs with deep”
Learning to Fix Build Errors with Graph2Diff Neural Networks (2019, background): “[9, 20, 43], in that these models map from a graph to a sequence of decisions that can include selecting nodes (to determine edges), though it does not appear that either subsumes the other.”
Recurrent Event Network: Autoregressive Structure Inference over Temporal Knowledge Graphs (2019, background): “DeepGMG (Li et al., 2018) and GraphRNN (You et al., 2018) are deep generative models of graphs and focus on generating static homogeneous graphs where there is only a single type of edge.”
Parameterized Explainer for Graph Neural Network (2020, background): “In recent years, deep learning models have shown great potential to generate graphs with complex properties preserved [54, 18, 35].”
Graph Representation Learning (2020, methodology): “The basic idea in the GraphRNN approach is to use a hierarchical RNN to model the edge dependencies in Equation (9.13).”
Deep symbolic regression: Recovering mathematical expressions from data via risk-seeking policy gradients (2019, background): “GraphRNN defines a distribution over graphs that generates an adjacency matrix one column at a time in autoregressive fashion (You et al., 2018).”
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.”
Graph neural networks in particle physics (2020, methodology): “The GraphRNN [78], and Graphite [79] are generative models over edges that use an RNN for sequential prediction, and GraphGAN [80] is an analogous method based on generative adversarial networks.”
Learning Graph Embedding With Adversarial Training Methods (2019, methodology): “We will investigate how to use the ARGA model to generate some realistic graphs [64], which may help discover new drugs in biological domains.”
Secure Deep Graph Generation with Link Differential Privacy (2020, background): “In Table 1, our DP-constrained models constantly yield highly competitive and even better results compared with the non-private baselines of NetGAN and GraphRNN regarding global graph structural similarity between generated and original networks on both datasets.”