GraphRNN: Generating Realistic Graphs with Deep Auto-regressive Models

Abstract

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.

ICML 2018

Cited by in corpus (129)

• Graph Neural Networks: A Review of Methods and Applications
• Learning Graph Embedding with Adversarial Training Methods
• A Gentle Introduction to Deep Learning for Graphs
• Graph-Based Deep Learning for Medical Diagnosis and Analysis: Past, Present and Future
• Graph Convolutional Policy Network for Goal-Directed Molecular Graph Generation
• Iterative Deep Graph Learning for Graph Neural Networks: Better and Robust Node Embeddings
• Metrics for Graph Comparison: A Practitioner's Guide
• Molecular graph generation with Graph Neural Networks
• Deep Learning on Graphs: A Survey
• Graph Neural Networks: Taxonomy, Advances and Trends
• Learning on Attribute-Missing Graphs
• Hierarchical Generation of Molecular Graphs using Structural Motifs
• E(n) Equivariant Graph Neural Networks
• Generative Models for Automatic Chemical Design
• Machine Learning on Graphs: A Model and Comprehensive Taxonomy
• D-VAE: A Variational Autoencoder for Directed Acyclic Graphs
• Multilevel Graph Matching Networks for Deep Graph Similarity Learning
• Deeply learning molecular structure-property relationships using attention- and gate-augmented graph convolutional network
• A Graph to Graphs Framework for Retrosynthesis Prediction
• Earthquake Phase Association with Graph Neural Networks
• Interaction networks for the identification of boosted $H\to b\overline{b}$ decays
• A Deep Generative Model for Graph Layout
• Heterogeneous Deep Graph Infomax
• Graph Neural Ordinary Differential Equations
• Deep Set Prediction Networks
• StructureNet: Hierarchical Graph Networks for 3D Shape Generation
• FSPool: Learning Set Representations with Featurewise Sort Pooling
• SE-GSL: A General and Effective Graph Structure Learning Framework through Structural Entropy Optimization
• Deep symbolic regression: Recovering mathematical expressions from data via risk-seeking policy gradients
• Motif-based Graph Self-Supervised Learning for Molecular Property Prediction
• A Deep Generative Model for Fragment-Based Molecule Generation
• Bringing Your Own View: Graph Contrastive Learning without Prefabricated Data Augmentations
• A Simple Baseline Algorithm for Graph Classification
• AEGCN: An Autoencoder-Constrained Graph Convolutional Network
• Graph Normalizing Flows
• Hypergraph Convolution and Hypergraph Attention
• Graph Representation Learning for Road Type Classification
• SketchGraphs: A Large-Scale Dataset for Modeling Relational Geometry in Computer-Aided Design
• Recurrent Event Network: Autoregressive Structure Inference over Temporal Knowledge Graphs
• Graphite: Iterative Generative Modeling of Graphs
• Directed Acyclic Graph Neural Networks
• M-Evolve: Structural-Mapping-Based Data Augmentation for Graph Classification
• Edge-based sequential graph generation with recurrent neural networks
• GraphDF: A Discrete Flow Model for Molecular Graph Generation
• Interpretable Deep Graph Generation with Node-Edge Co-Disentanglement
• FeederGAN: Synthetic Feeder Generation via Deep Graph Adversarial Nets
• Hierarchical Graph-to-Graph Translation for Molecules
• Deep Generative Models for Detector Signature Simulation: A Taxonomic Review
• Transfer Learning of Graph Neural Networks with Ego-graph Information Maximization
• SLAPS: Self-Supervision Improves Structure Learning for Graph Neural Networks
• Hierarchical Temporal Convolutional Networks for Dynamic Recommender Systems
• Learning Sparse Interaction Graphs of Partially Detected Pedestrians for Trajectory Prediction
• House-GAN++: Generative Adversarial Layout Refinement Networks
• TG-GAN: Continuous-time Temporal Graph Generation with Deep Generative Models
• A Network Science perspective of Graph Convolutional Networks: A survey
• Labeled Graph Generative Adversarial Networks
• TIGGER: Scalable Generative Modelling for Temporal Interaction Graphs
• Goal-directed graph construction using reinforcement learning
• Supplementing Recurrent Neural Networks with Annealing to Solve Combinatorial Optimization Problems
• Generating Tertiary Protein Structures via an Interpretative Variational Autoencoder
• Categorical Normalizing Flows via Continuous Transformations
• Multitask Learning on Graph Neural Networks: Learning Multiple Graph Centrality Measures with a Unified Network
• Deep Generation of Heterogeneous Networks
• Towards Interpretable Sparse Graph Representation Learning with Laplacian Pooling
• Brick-by-Brick: Combinatorial Construction with Deep Reinforcement Learning
• A Variational-Sequential Graph Autoencoder for Neural Architecture Performance Prediction
• Learning Universal Graph Neural Network Embeddings With Aid Of Transfer Learning
• Fast and Robust Comparison of Probability Measures in Heterogeneous Spaces
• Superpixels and Graph Convolutional Neural Networks for Efficient Detection of Nutrient Deficiency Stress from Aerial Imagery
• Barking up the right tree: an approach to search over molecule synthesis DAGs
• Neural Architecture Optimization with Graph VAE
• Practical Massively Parallel Monte-Carlo Tree Search Applied to Molecular Design
• Secure Deep Graph Generation with Link Differential Privacy
• Graph Generators: State of the Art and Open Challenges
• Artificial Intelligence in Drug Discovery: Applications and Techniques
• Spatial Graph Attention and Curiosity-driven Policy for Antiviral Drug Discovery
• CARL-G: Clustering-Accelerated Representation Learning on Graphs
• Revisiting 2D Convolutional Neural Networks for Graph-based Applications
• Constant Time Graph Neural Networks
• Deep Generative Models to Extend Active Directory Graphs with Honeypot Users
• Neural Markov Logic Networks
• GraphTune: A Learning-based Graph Generative Model with Tunable Structural Features
• Non-Parametric Graph Learning for Bayesian Graph Neural Networks
• SCGG: A Deep Structure-Conditioned Graph Generative Model
• E(n) Equivariant Normalizing Flows
• SceneGen: Learning to Generate Realistic Traffic Scenes
• Modeling Graphs with Vertex Replacement Grammars
• Node Feature Extraction by Self-Supervised Multi-scale Neighborhood Prediction
• Towards Interpretable Graph Modeling with Vertex Replacement Grammars
• DeepGG: a Deep Graph Generator
• CCGG: A Deep Autoregressive Model for Class-Conditional Graph Generation
• Deterministic Decoding for Discrete Data in Variational Autoencoders
• Highly Accurate Disease Diagnosis and Highly Reproducible Biomarker Identification with PathFormer
• Random clique covers for graphs with local density and global sparsity
• Weakly Supervised Concept Map Generation through Task-Guided Graph Translation
• HIN-RNN: A Graph Representation Learning Neural Network for Fraudster Group Detection With No Handcrafted Features
• Evaluation Metrics for Graph Generative Models: Problems, Pitfalls, and Practical Solutions
• The Atlas for the Aspiring Network Scientist
• The Infinity Mirror Test for Graph Models
• Embeddings and Representation Learning for Structured Data
• DeepNC: Deep Generative Network Completion
• Discrete Object Generation with Reversible Inductive Construction
• Continuous Graph Flow
• Neural Language Modeling for Contextualized Temporal Graph Generation
• SHADOWCAST: Controllable Graph Generation
• Permutation-Invariant Variational Autoencoder for Graph-Level Representation Learning
• Deep Generative Modeling in Network Science with Applications to Public Policy Research
• Generating a Doppelganger Graph: Resembling but Distinct
• Evolution of Real-world Hypergraphs: Patterns and Models without Oracles
• Neural Subgraph Isomorphism Counting
• Graph Embedding VAE: A Permutation Invariant Model of Graph Structure
• Partition and Code: learning how to compress graphs
• Relational dynamic memory networks
• Graph Context Encoder: Graph Feature Inpainting for Graph Generation and Self-supervised Pretraining
• Learning to Sample Hard Instances for Graph Algorithms
• Social Graph Restoration via Random Walk Sampling
• Uncovering Political Promotion in China: A Network Analysis of Patronage Relationship in Autocracy
• TD-GEN: Graph Generation With Tree Decomposition
• GraphGen-Redux: a Fast and Lightweight Recurrent Model for labeled Graph Generation
• Using Laplacian Spectrum as Graph Feature Representation
• Attributed Graph Modeling with Vertex Replacement Grammars
• X-GGM: Graph Generative Modeling for Out-of-Distribution Generalization in Visual Question Answering
• Towards quantitative methods to assess network generative models
• Learning-based Efficient Graph Similarity Computation via Multi-Scale Convolutional Set Matching
• ExplaGraphs: An Explanation Graph Generation Task for Structured Commonsense Reasoning
• Generating the Graph Gestalt: Kernel-Regularized Graph Representation Learning
• Node Attribute Generation on Graphs
• Learning to Represent and Predict Sets with Deep Neural Networks
• One Node at a Time: Node-Level Network Classification