We propose GraphGAN - the first implicit generative model for graphs that enables to mimic real-world networks.
 We pose the problem of graph generation as learning the distribution of biased random walks over a single input graph.
 Our model is based on a stochastic neural network that generates discrete output samples, and is trained using the Wasserstein GAN objective. GraphGAN enables us to generate sibling graphs, which have similar properties yet are not exact replicas of the original graph. Moreover, GraphGAN learns a semantic mapping from the latent input space to the generated graph's properties. We discover that sampling from certain regions of the latent space leads to varying properties of the output graphs, with smooth transitions between them. Strong generalization properties of GraphGAN are highlighted by its competitive performance in link prediction as well as promising results on node classification, even though not specifically trained for these tasks. Generative models for graphs have a longstanding history, with applications including data augmentation, anomaly detection and recommendation BID6 . Explicit probabilistic models such as Barabási-Albert or stochastic blockmodels are the de-facto standard in this field BID11 . However, it has also been shown on multiple occasions that our intuitions about structure and behavior of graphs may be misleading. For instance, heavy-tailed degree distributions in real graphs were in stark disagreement with the models existing at the time of their discovery BID2 . More recent works, like BID9 , keep bringing up other surprising characteristics of real-world networks, not accounted for by the models at hand. This leads us to the question: "How do we define a model that captures all the essential (potentially still unknown) properties of real graphs?" An increasingly popular way to address this issue in other fields is by switching from explicit (prescribed) models to implicit ones. This transition is especially notable in Computer Vision, where Variational Autoencoder BID23 and Generative Adversarial Networks (GANs) BID13 significantly advanced the state of the art over the classic prescribed approaches like Mixtures of Gaussians BID5 . GANs achieve unparalleled results in scenarios such as image and 3D objects generation (e.g., BID32 BID4 . However, despite their massive success when dealing with real-valued data, adapting GANs to handle discrete objects like graphs or text remains an open research problem BID12 . Indeed, the combinatorial structure of the graph is only one of the obstacles when applying GANs to graphs. Second, large repositories of graphs, which all come from the same distribution, do not exist. This means that in a typical setting one has to learn from a single graph. And last, any model operating on a graph necessarily has to be permutation invariant, as the graphs remain isomorphic under node reordering.In this work we introduce GraphGAN -the first implicit generative model for graphs, that tackles all of the above challenges. We formulate the problem of learning the graph topology as learning the distribution of biased random walks over the graph. Like in the typical GAN setting, the generator G -in our case defined as a stochastic neural network with discrete output samples -learns to generate random walks that are plausible in the real graph, while the discriminator D then has to distinguish them from the true ones that are sampled from the original graph. The objective function of our model is based on the Wasserstein GAN , which allows to learn multimodal distributions and leads to more stable convergence. Our GraphGAN exhibits strong generalization properties, which we study in detail in the experimental section. The example in FIG0 shows that the graphs generated by GraphGAN possess similar properties as the input graph, as shown by the degree distributions in FIG0 . The generated graphs, however, are not simply exact replicas: as the visualized subset of nodes in Figs. 1a and 1b shows, the graphs exhibit similar structure while being not identical; in fact, the two graphs have less than 50% of edges in common. This initial insight is underlined by an extensive comparison of graphs generated by GraphGAN and the respective input networks in the experimental section of this work. And even more, when generating graphs based on specific regions of the latent space learned by GraphGAN, we can smoothly interpolate between graphs with varying properties. Our main contributions are:• We introduce GraphGAN -the first of its kind GAN that generates graphs via random walks. Our model tackles the associated challenges of staying permutation invariant, learning from a single graph and generating discrete output.• We show that our model generalizes, and is able to produce sibling graphs to the given input graph. These graphs posses similar topological characteristics, but are not exact replicas (see FIG0 ). We further demonstrate how latent space interpolation leads to generation of graphs with smoothly changing properties.• We highlight the generalization properties of GraphGAN by its link prediction performance, which is competitive with the state of the art on real-word datasets, although not trained explicitly for this task. Additionally, to give the reader a better insight about the behavior of our model, we analyze the learned weights of our model -that can be viewed as node "embeddings" -and by using them in a node classification task we show that they capture meaningful structural information. When evaluating different graph generative models in Sec. 4.1, we observed a major limitation of explicit models. While the prescribed approaches excel at recovering the properties that are directly included in their definition, they perform significantly worse with respect to the rest of the metrics. This phenomenon clearly indicates the need for implicit graph generators, such as GraphGAN. Indeed, we notice that our model is able to consistently capture all the important graph characteristics (see TAB1 ). Moreover, GraphGAN generalizes beyond the input graph, as can be seen by its strong link prediction performance in Sec. 4.2.Still, being the first model of its kind, GraphGAN possesses certain limitations, and a number of related questions could be addressed in follow-up works:Scalability. We have observed in Sec. 4.2 that it takes a large number of generated random walks to get representative transition counts for large graphs. While sampling random walks from GraphGAN is trivially parallelizable, a possible extension of our model is to use a conditional generator, i.e. the generator can be provided a desired starting node, thus ensuring a more even coverage. On the other hand, the sampling procedure itself can be sped up by incorporating a hierarchical softmax output layer -a method commonly used in natural language processing.Evaluation. It is nearly impossible to judge whether a graph is realistic by visually inspecting it (unlike images, for example). In this work we already quantitatively evaluate the performance of GraphGAN on a large number of standard graph statistics. However, developing new measures applicable to (implicit) graph generative models will deepen our understanding of their behavior.Experimental scope. In the current work we focused on the setting of a single connected graph.Other scenarios, such as dealing with a collection of smaller i.i.d. graphs, that frequently occur in other fields (e.g., chemistry, biology), would be an important application area for the proposed model. Studying the influence of the graph topology (e.g., sparsity, diameter) on performance of GraphGAN will shed more light on its properties.Other types of graphs. While plain graphs are ubiquitous, many of real-world applications deal with attributed, k-partite or heterogeneous networks. Adapting the GraphGAN model to handle these other modalities of the data is a promising direction for future research. Especially important would be an adaptation to the dynamic / inductive setting, when new nodes are added over time. GraphGAN is the first work to successfully bridge the worlds of implicit modeling and graphs. Our work enables future researchers to gain better insight into the properties of real networks and opens new and exciting lines of research. We are able to generate realistic graphs by learning to generate (biased) random walks from the same distribution as the random walks from an input graph. We employ the GAN framework to learn our implicit generative model, overcoming key challenges such as permutation invariance, working in the discrete domain and having a single graph as input. Our generator is able to generate sibling graphs that maintain structural similarity with the original graph without being exact replicas. Better yet, using our defined stopping criteria, we can control how close are the generated graphs to the original. We further show that GraphGAN learns a semantic mapping from the latent space to the properties of the generated graph, which is evidenced by the smooth transitions of the output. GraphGAN shows strong generalization properties, as demonstrated by the competitive performance on the link prediction and the promising results on the node classification task, without being explicitly trained with these tasks in mind.
Using GANs to generate graphs via random walks. The authors proposed a generative model of random walks on graphs that allows for model-agnostic learning, controllable fitting, ensemble graph generation Proposes a WGAN formulation for generating graphs based on random walks using node embeddings and an LSTM architecture for modeling.