NetGAN: Generating Graphs via Random Walks

By Aleksandar Bojchevski, Oleksandr Shchur, Daniel Zügner, Stephan Günnemann. 2018

410 citations recorded by the source corpus.

We propose NetGAN - the first implicit generative model for graphs able to mimic real-world networks. We pose the problem of graph generation as learning the distribution of biased random walks over the input graph. The proposed model is based on a stochastic neural network that generates discrete output samples and is trained using the Wasserstein GAN objective. NetGAN is able to produce graphs that exhibit the well-known network patterns without explicitly specifying them in the model definition. At the same time, our model exhibits strong generalization properties, as highlighted by its competitive link prediction performance, despite not being trained specifically for this task. Being the first approach to combine both of these desirable properties, NetGAN opens exciting further avenues for research.

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

Relational inductive biases, deep learning, and graph networks (2018, background): “Recent work has also focused on building generative models of graphs (Li et al., 2018; De Cao and Kipf, 2018; You et al., 2018; Bojchevski et al., 2018), and unsupervised learning of graph embeddings (Perozzi et al.”
Graphite: Iterative Generative Modeling of Graphs (2018, background): “Amongst adversarial generation approaches, [50] and [3] model local graph neighborhoods and random walks on graphs respectively.”
Predict then Propagate: Graph Neural Networks meet Personalized PageRank (2018, background): “Deep learning approaches have achieved great success on many important graph problems such as link prediction (Grover & Leskovec, 2016; Bojchevski et al., 2018), graph classiﬁcation (Duvenaud et al., 2015; Niepert et al., 2016; Gilmer et al., 2017) and semi-supervised node classiﬁcation (Yang et…”
A Comprehensive Survey on Graph Neural Networks (2019, methodology): “…[51], [53] [56], [61], [62] Pubmed [117] 1 19717 44338 500 3 [18], [22], [25], [41], [43], [44], [45] [49], [51], [53], [55], [56], [61], [62] [70], [95] DBLP (v11) [118] 1 4107340 36624464 - - [64], [70], [99] Bio-chemicalGraphs PPI [119] 24 56944 818716 50 121 [18], [42], [43], [48], [45],…”
Graph Representation Learning (2020, methodology): “In the context of graph generation, a GAN-based approach was first employed in concurrent work by Bojchevski et al. [2018] and De Cao and Kipf [2018]. The basic approach proposed by De Cao and Kipf [2018]—which we focus on here—is similar to the graph-level VAE discussed in the previous section.”
Secure Deep Graph Generation with Link Differential Privacy (2020, background): “…GGen models have been developed recently, which leverage different powerful neural networks in a learn-to-generate manner [Kipf and Welling, 2016; Bojchevski et al. , 2018; You et al. , 2018; Simonovsky and Komodakis, 2018] For example, NetGAN [Bojchevski et al. , 2018] converts graphs into…”
MolGAN: An implicit generative model for small molecular graphs (2018, methodology): “For link prediction within graphs, a range of adversarial methods have been introduced in the literature (Minervini et al., 2017; Wang et al., 2018; Bojchevski et al., 2018).”
Adversarial Attack and Defense on Graph Data: A Survey (2018, background): “Please refer to [10] for more details about those metrics.”
Designing Random Graph Models Using Variational Autoencoders With Applications to Chemical Design (2018, background): “In this context, there have been a surge of interest in developing deep generative models for graphs [5, 10, 16, 22, 26, 33, 36], partly fueled by the success of generative adversarial networks (GANs) [3, 9] and variational autoencoders (VAEs) [20, 31] in image, audio and text generation [6, 14, 35,”
Conditional Structure Generation through Graph Variational Generative Adversarial Nets (2019, methodology): “As we can clearly observe, state-of-the-art graph generation algorithms like GraphRNN and NetGAN are rather slow, due to the heavy model of RNN and large number of sampled walks, respectively, while C OND G EN and its base model GVAE are much faster.”
Efficient Graph Generation with Graph Recurrent Attention Networks (2019, background): “NetGAN [4] builds a generative adversarial network on top of random walks over the graph.”
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.”
Hypergraph Convolution and Hypergraph Attention (2019, background): “, 2018b), generative models (You et al., 2018b; Bojchevski et al., 2018), adversarial attack (Dai et al.”
Semantic Bottleneck Scene Generation (2019, background): “GANs on discrete domains GANs for discrete domains have been investigated in several works [22, 43, 24, 6, 26].”
Deep Learning on Graphs: A Survey (2018, neutral): “NetGAN [127] adopted a GAN for graph generation tasks.”
Adversarial Attacks on Graph Neural Networks via Meta Learning (2019, background): “…classical approaches to node classiﬁcation (London & Getoor, 2014; Chapelle et al., 2006), recently deep learning on graphs has gained much attention (Monti et al., 2017; Bojchevski & G¨unnemann, 2018a; Battaglia et al., 2018; Perozzi et al., 2014; Bojchevski et al., 2018; Klicpera et al., 2019).”