Title: GRAPHGAN: GENERATING GRAPHS VIA RANDOM WALKS

Abstract: 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.

1. INTRODUCTION:

Generative models for graphs have a longstanding history, with applications including data augmentation, anomaly detection and recommendation (Chakrabarti & Faloutsos, 2006) . Explicit probabilistic models such as Barabási-Albert or stochastic blockmodels are the de-facto standard in this field (Goldenberg et al., 2010) . 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 (Barabási & Albert, 1999) . More recent works, like Dong et al. (2017) , 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 (Kingma & Welling, 2013) and Generative Adversarial Networks (GANs) (Goodfellow et al., 2014) significantly advanced the state of the art over the classic prescribed approaches like Mixtures of Gaussians (Blanken et al., 2007) . GANs achieve unparalleled results in scenarios such as image and 3D objects generation (e.g., Radford et al., 2015; Berthelot et al., 2017; Wu et al., 2016) . 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 (Goodfellow, 2016) . 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 visualize a subset of nodes selected from the complete graphs. The graphs show similar structure but are not identical. (c) shows that the degree distributions of the input graph as well as the graphs generated by GraphGAN and the degree-corrected stochastic blockmodel are very similar.

model is based on the Wasserstein GAN (Arjovsky et al., 2017) , 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 Fig. 1 shows that the graphs generated by GraphGAN possess similar properties as the input graph, as shown by the degree distributions in Fig. 1c . 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 Fig. 1 ). 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.

2. RELATED WORK:

There are only two attempts of using GANs in the context of graphs (Tavakoli et al., 2017; Liu et al., 2017) . Tavakoli et al. (2017) 's approach tries to generate the full adjacency matrix of the graph directly (treating it as a binary image). To circumvent the issue of having a single graph, they apply random permutations to the adjacency matrix to generate additional training data. Since their model explicitly generates the full adjacency matrix -including zero-elements -the output (input) size of their generator (discriminator) is equal to the number of nodes squared. Such a quadratic complexity is infeasible in practice, allowing to process only small graphs. Indeed, this fundamental limitation becomes evident in their reported runtime of over 60 hours for a graph with only 154 nodes -the largest graph they processed. In contrast, our model operates on the random walks, thus only considering the non-zero elements of the adjacency matrix and efficiently exploiting the sparsity of real-wolrd graphs.

While not focusing on generating full graphs, Liu et al. (2017) use GANs to learn graph topological features. They decompose the graph into multiple subgraphs, where each subgraph is then processed by a GAN using standard image operations (e.g. convolution, deconvolution) which contain the built-in assumption that pixels located closely (within the same receptive field) are in some way correlated. Clearly, when talking about an adjacency matrix such assumption is not sensible, as permutations of rows/columns correspond to the exact same graph but very different receptive fields.

In contrast to their approach our model does not make any spatial dependence assumptions about the adjacency matrix. Moreover, since their GAN only generates edges within the subgraphs, but not between them, all inter-subgraph edges from the original graph have to be stored and copied manually to a potential new graph. In contrast, our model is learned end-to-end, it allows to generate the whole graph, and it handles arbitrary permutations of the given input graph.

Due to the challenging nature of the problem, only few approaches able to generate discrete data using GANs exist. Most approaches focus on generating discrete sequences such as text, with some of them using reinforcement learning techniques to address the difficulty of backpropagation through sampling discrete random variables (Yu et al., 2017; Kusner & Hernández-Lobato, 2016; Li et al., 2017; Liang et al., 2017) . Other approaches modify the GAN objective to tackle the same challenge (Che et al., 2017; Hjelm et al., 2017) . Focusing on non-sequential discrete data, Choi et al. (2017) generate high-dimensional discrete features (e.g. binary indicators, counts) in patient records. None of these methods has considered graph structured data.

Apart from GANs, prescribed generative models for graphs have a long history and are well-studied. For a comprehensive survey see Chakrabarti & Faloutsos (2006) ; Goldenberg et al. (2010) . Based on the different modeling assumptions, the generative power of these models varies significantly. A substantial portion cannot even handle power-law degree distributions as found in most real-world networks. One of the simplest model is the configuration model (Bender & Canfield, 1978; Molloy & Reed, 1995) that rewires edges at random, but preserves the node degrees. A stronger representative able to capture power-law degree distributions, as well as diverse network topologies and community structure is the well-established degree-corrected stochastic blockmodel (DC-SBM) (Karrer & Newman, 2011) . Another broad family of models are exponential random graph models (ERGM) (Holland & Leinhardt, 1981 ) that explicitly preserve some manually specified graph statistics (e.g. edge count, degrees, node attribute statistics, etc.). ERGMs represent a probability distribution over all possible networks of a given fixed size, by specifying one parameter per statistic.

We compare against the configuration model, DC-SBM and ERGM as baselines. We will see in Sec. 4.1 that as expected, all properties which these approaches explicitly model are preserved, while the rest deviate significantly from the input graph. This highlights the need for implicit models such as ours, that capture the properties of real-world graphs without having to manually specify them.

3. GANS FOR GRAPHS:

In this section we introduce GraphGAN -a Generative Adversarial Network model for graphs. Its core idea lies in learning the topology of a graph by learning the distribution over the random walks.

Given is an input graph of N nodes, defined by an unweighted adjacency matrix A ∈ {0, 1} N ×N . First, we sample a set of random walks of length T from A. This collection of random walks serves as a training set for our model. We use the biased second-order random walk sampling strategy described in Grover & Leskovec (2016) , as it better captures both local and global graph structure. An important advantage of using random walks is their invariance under node reordering. Additionally, random walks only include the nonzero entries of A, thus efficiently exploiting the sparsity of real-world graphs.

Like any typical GAN architecture, GraphGAN consists of two main components -a generator G and a discriminator D. The goal of the generator is to generate synthetic random walks that are plausible in the input graph. At the same time, the discriminator learns to distinguish the synthetic random walks from the real ones that come from the training set. Both G and D are trained end-toend using backpropagation. At any point of the training process it is possible to use G to generate a set of random walks, which can then be used to produce an adjacency matrix of a new generated graph. In the rest of this section we describe each stage of this process and our design choices in more detail. An overview of our model's complete architecture can be seen in Fig. 2 .

3.1 ARCHITECTURE z ∼ N (0, I d ) m 0 = g θ (z) v 1 ∼ Cat(p 1 ), (p 1 , m 1 ) = f θ (m 0 , 0) v 2 ∼ Cat(p 2 ), (p 2 , m 2 ) = f θ (m 1 , v 1 ) . . . . . . v T ∼ Cat(p T ), (p T , m T ) = f θ (m T -1 , v T -1 )

Generator. In this work we focus our attention on the Long short-term memory (LSTM) architecture for f θ , introduced by Hochreiter & Schmidhuber (1997) . The memory state m t of an LSTM is represented by the cell state C t , and the hidden state h t . The latent code z goes through two separate streams, each consisting of two fully connected layers with tanh activation, and then used to initialize (C 0 , h 0 ).

A natural question might arise: "Why use a model with memory and temporal dependencies, when the random walks are Markov processes?" (2nd order Markov for biased RWs). Or put differently, what's the benefit of using random walks of length greater than 2. In theory, a model with large enough capacity could simply memorize all existing edges in the graph and recreate them. However, for large graphs achieving this in practice is not feasible. More importantly, pure memorization is not the goal of GraphGAN, rather we want to have generalization and generate similar sibling graphs, not exact replicas. Having longer random walks combined with memory helps the model to learn the topology and general patterns in the data (e.g. community structure). Our experiments in Sec. 4.2 confirm this, showing that longer random walks are indeed beneficial.

After each time step, in order to generate the next node in the random walk, the network f θ needs to output the vector of probabilities p t of length N . Operating in such high dimensional space within the LSTM cell is infeasible, and leads to unnecessary computational overhead. For this reason, we do the following: the model outputs o t ∈ R H , with H N , which is then up-projected to R N using W up ∈ R N ×H . One can view it as similar to context embeddings in representation learning.

Given the probability distribution over the next node in the random walk, p t ∈ ∆ N -1 , from which v t is to be drawn, we are faced with another challenge: Sampling from a categorical distribution is a non-differentiable operation -thus, it blocks the flow of gradients and precludes backpropagation. We circumvent this problem by using the Straight-Through Gumbel estimator by Jang et al. (2016) . More specifically, we perform the following transformation: First, we let

Generator architecture C 0 h 0 C 1 h 1 o 1 o T v T v 2 v 1 v 1 ⋯ ⋯ ⋯ Wdown p 1 p N p 1 p N W up W up GraphGAN architecture Graph G(z)

Random walk:

Discriminator

D real D fake Generator z ∼ N (0, I d ) z sample sample (a) (b)

Figure 2 : The GraphGAN architecture proposed in this work (b) and the generator architecture (a).

v * t = softmax ((log p t + g)/τ ))

, where τ is a temperature parameter, and g i 's are i.i.d. samples from a Gumbel distribution with zero mean and unit scale. Then, the next sample is computed as v t = onehot(arg max v * t ). While the one-hot sample v t is passed as input to the next time step, during the backward pass the gradients will flow through the differentiable v * t . The choice of τ allows to trade-off between better flow of gradients (large τ , more uniform v * t ) and more exact calculations (small τ , v * t ≈ v t ). Now that a new node v t is sampled, it needs to be projected back to a lower-dimensional representation before feeding into the LSTM. This is done by means of down-projection matrix W down ∈ R H×N . Together with the up-projection matrix W up , the matrix W down deserves a special mention, as it happens to learn -as a byproduct -meaningful information about the nodes. We can view these matrices as a form of node "embeddings" and to gain a better understanding of our model we study their properties in Sec. 4.2 and 4.3.

Discriminator. The discriminator D is based on the standard LSTM architecture. At every time step t, a one-hot vector v t , denoting the node at the current position, is fed as input. After processing the entire sequence, the discriminator outputs a single score that represents the probability of the random walk being real.

3.2. TRAINING:

Wasserstein GAN. We train our model based on the Wasserstein GAN (WGAN) framework (Arjovsky et al., 2017) . To enforce the Lipschitz constraint of the discriminator, we use the gradient penalty as in Gulrajani et al. (2017) . We observe that in our setting using the WGAN objective leads to noticeable improvements over the vanilla GAN: it prevents mode collapse, as well as leads to a more stable learning procedure overall. The model parameters {θ, θ } are trained using stochastic gradient descent with Adam (Kingma & Ba, 2014) . Weights are regularized with an L 2 penalty.

Early stopping. Because we are interested in generalizing the input graph, the "trivial" solution where the generator has memorized all existing edges is of no interest to us. This means that we need to control overfitting of our model. To achieve this, we employ two early stopping strategies. The first strategy, named VAL-CRITERION is concerned with the generalization properties of GraphGAN. During training, we keep a sliding window of the random walks generated in the last 1,000 iterations and use them to construct a matrix of transition counts. This matrix is then used to evaluate the link prediction performance on a validation set (i.e. ROC and AP scores, for more details see Sec. 4.2). We stop with training when the validation performance stops improving.

The second strategy, named EO-CRITERION makes GraphGAN very flexible and gives the user control over the graph generation. We stop training when we achieve a user specified edge overlap between the generated graphs (see next section) and the original one at a given iteration. Based on her end task the user can choose to generate graphs with either small or large edge overlap with the original, while maintaining structural similarity. This will lead to generated graphs that either generalize better or are closer replicas respectively, yet still capture the properties of the original.

3.3. ASSEMBLING THE ADJACENCY MATRIX:

After finishing the training, we use the generator G to construct a score matrix S of transition counts, i.e. we count how often an edge appears in the set of generated random walks (typically, using a much larger number of random walks than for early stopping, e.g., 500K). While the raw counts matrix S is sufficient for link prediction purposes, we need to convert it to a binary adjacency matrix Ã, if we wish to reason about the synthetic graph. First, S is symmetrized by setting s ij = s ji = max{s ij , s ji }. Because we cannot explicitly control the starting node of the random walks generated by G, some high-degree nodes will likely be overrepresented. Thus, a simple binarization strategy like thresholding or choosing top-k entries might lead to leaving out the low-degree nodes and producing singletons. To address this issue, we use the following approach. (i) We ensure that every node i has at least one edge by sampling a neighbor j with probability p ij = sij v siv . If an edge was already sampled before, we repeat the procedure. (ii) We continue sampling edges without replacement, using for each edge (i, j) the probability p ij = sij u,v suv , until we reach the desired amount of edges (e.g., as many edges as in the original graph). Note that this procedure is not guaranteed to produce a fully connected graph.

4. EXPERIMENTS:

Besides using GraphGAN to generate graphs, we also evaluate its output and learned representations on other typical graph mining tasks, most prominently link prediction and node classification. We evaluate GraphGAN on these tasks and several real-world datasets and compare it with state-of-theart methods. Furthermore, we demonstrate how we can generate graphs with smoothly changing properties via latent space interpolation.

Datasets. For our evaluation, we use several well-know citation datasets, as well as the Political Blogs dataset. Table 1 show the dataset statistics. Cora-ML is the subset of machine learning papers from the original Cora dataset typically considered in other works. For all our experiments, we consider only the largest connected component in each network and treat them as undirected. In this task, we use GraphGAN to generate sibling graphs to a given input graph, and compare its performance to the baselines. The goal is to generate graphs that are similar in their properties to the input graph -while not trivially copying the input network. We randomly hide 15% of the edges (which are used for the stopping criterion; see Sec. 3.2) and train GraphGAN and DC-SBM on the remaining graph. We then sample graphs from the trained models and compare their properties with the input graph. We report the results for CORA-ML here, and for CITESEER in the appendix. Evaluation. Fig. 3a shows that GraphGAN and DC-SBM are able to generate graphs whose degree distributions nicely match the input graph's. For DC-SBM, this is not surprising, given that it explicitly encodes the degree distribution in the model. GraphGAN, however, does not have access to the degree distribution of the input graph -yet is still able to model it to a high accuracy. Going beyond the degree distribution, in Table 2 we show seven other important graph statistics and see that for most of them GraphGAN closely matches the original graph. We do not expect that GraphGAN is superior to every existing explicit model in every possible regard. Rather, our goal is to lay a foundation for the study of implicit models for graph generation. We report the results for both early stopping strategies: VAL-CRITERION and EO-CRITERION. In line with our intuition, we can see that higher EO leads to generated graphs with statistics closer to the original. Results for additional statistics, respective definitions, as well as details about the baselines can be found in the appendix.

GraphGAN:

Figs. 3b and 3c show how the graph statistics evolve as we train GraphGAN on CORA-ML. In Fig. 3b we see that after 40K training iterations we are able to reach the assortativity value of the original graph. Fig. 3c shows that the edge overlap smoothly increasing with the number of epochs. 9.8e-4 ±1e-5 9.9e-4 ±2e-5 node2vec naïve (1% EO) 14 ± 1.4 -0.007 ± 0.011 16 ± 4.4 1.68 ± 0.001 2,810 ± 0.1 1.4e-3 ±1e-5 3.8e-4 ±2e-5 DC-SBM (11% EO) 165 ± 9.0 -0.052 ± 0.004 1,403 ± 67 1.814 ± 0.008 2,474 ± 18.9 6.7e-4 ±2e-5 1.2e-3 ±4e-5 ERGM (56% EO) 243 ± 1.94 -0.077 ± 0.000 2,293 ± 23 1.786 ± 0.003 2,489 ± 11.0 6.9e-4 ±2e-5 1.2e-3 ±1e-5 GraphGAN VAL (39% EO) 199 ± 6.7 -0.060 ± 0.004 1,410 ± 30 1.773 ± 0.002 2,809 ± 1.6 6 .5e-4 ±1e-5 1 .3e-3 ±2e-5 GraphGAN EO (52% EO) 233 ± 3.6 -0.066 ± 0.003 1,588 ± 59 1.793 ± 0.003 2,807 ± 1.6 6.0e-4 ±1e-5 1.4e-3 ±1e-5

Note: EO is a suitable measure of closeness since we generate graphs with same node ordering and same number of edges as the input. We provide similar plots for the other graph statistics and for CITESEER in the appendix.

4.2. LINK PREDICTION:

Link prediction is a classical task in graph mining, where the goal is to predict new links in a given graph. We use it to evaluate the generalization properties of GraphGAN. We hold out 10% of edges from the graph for validation, and 5% as the test set, along with the same amount of randomly selected non-edges. We also ensure that the training network remains connected and does not contain any singletons. We measure the performance with the commonly used metrics area under the ROC curve (AUC) score and precision-recall AUC score, known as average precision (AP).

To evaluate GraphGAN's link prediction performance, we sample a specific number of random walks (500K/100M) from the trained generator. We use the observed transition counts between any two nodes as a measure of how likely there is an edge between them. Additionally, we concatenate W down and W up and use the dot product as an alternative way to perform link prediction. We compare with Adamic/Adar (Adamic & Adar, 2003) , the degree-corrected stochastic blockmodel (DC-SBM) (Karrer & Newman, 2011) , and node2vec (Grover & Leskovec, 2016) .

Evaluation. The results are listed in Table 3 . There is no overall dominating method, with different methods achieving best results on different datasets. GraphGAN shows competitive performance for all datasets, for both the transition count based and the dot product based link prediction, even achieving state-of-the-art results for some of them, despite not being explicitly trained for this task. Interestingly, for the transition count based link prediction, the GraphGAN performance increases when increasing the number of random walks sampled from the generator. This is especially true for the larger networks (CORA, DBLP, PUBMED), since given their size we need more random walks to cover the entire graph. This suggests that for an additional computational cost, one can get significant gains in performance. Note that while 100M may seem like an large number, the sampling process is trivially parallelizable.

Sensitivity analysis. Although GraphGAN has many hyperparameters -typical for a GAN model, in practice most of them are not critical for performance. The two important exceptions are the length of the random walks T , and the discriminator type. Fig. 4 empirically confirms the choice of a neural network that generates random walks of length T as opposed to just edges; the model does not have the capacity to fit the model by just considering edges (i.e. random walks of length 2). In the experiment we sample 500K random walks from the trained models for each T , averaged over five runs. The performance gain for random walk length 20 over 16 is marginal and does not outweigh the additional computational cost; therefore, we use random walks of length 16 for all experiments. In the appendix we show that our choice of a recurrent discriminator achieves better link prediction performance than a variant based on convolutions, hence we use it for all experiments in this work.

4.3. NODE CLASSIFICATION:

We perform node classification using W up and W down , which can be viewed as low-dimensional feature representations of the nodes, to show the generalization properties of GraphGAN. We evaluate both W down , W up , as well as their concatenation, comparing with node2vec as a strong baseline. Note that unlike in the link prediction task we cannot use the generated graphs to perform node classification. Similar to (Grover & Leskovec, 2016; Perozzi et al., 2014) we train a logistic regression model on a small randomly selected subset (< 20% of nodes) using the ground-truth labels and evaluate the classification performance on the remaining samples. Additionally, we visualize W up using t-SNE to demonstrate that a community structure has emerged in the embedding space. Evaluation. In Fig. 5a , we visualize the weighted macro F1 score for node classification. The results are averaged over five trials, and the shaded areas indicate the standard deviation of the respective curves. The embedding-like weights in W up produced by GraphGAN as a byproduct show comparable performance with node2vec -an algorithm specifically designed to learn node embeddings. This indicates that during the process of learning to generate random walks GraphGAN also captured meaningful structural information. The emergent community structure seen in Fig. 5b further emphasizes this. In this t-SNE visualization of W up , we can clearly see a grouping of nodes from the same community, which means that they lie in similar regions of the embedding space. Although GraphGAN's learned node representations clearly show they they capture useful information about the nodes, they are only a byproduct of the training procedure. Recall that the main goal of GraphGAN is graph generation; if node classification is the user goal, dedicated node embedding algorithms are the preferred option.

4.4. LATENT VARIABLE INTERPOLATION:

Latent space interpolation is a good way to gain insight into what kind of structure the generator was able to capture. To be able to visualize the properties of the generated graphs we train our model using noise z drawn from a bivariate standard normal distribution, which corresponds to a 2-dimensional latent space Ω = R 2 . Then, instead of sampling z from the entire latent space Ω, we now sample from subregions of Ω and visualize the results. More specifically, we divide Ω into 20×20 subregions (bins) of equal probability mass using the cumulative distribution function Φ. For each bin we generate 62.5K random walks. We evaluate properties of both the generated random walks themselves, as well as properties of the resulting graph when sampling a binary adjacency matrix for each bin, visualizing them as heatmaps.

Evaluation. In Fig. 6a and 6b we see properties of the generated random walks; in Fig. 6c and 6d , we visualize properties of graphs sampled from the random walks in the respective bins. In all four heatmaps, we see distinct patterns, e.g. higher average degree of starting nodes for the bottom right region of Fig. 6a , or higher degree distribution inequality in the top-right area of Fig. 6c . While Fig. 6c and 6d show that certain regions of z correspond to generated graphs with very different degree distributions, recall that sampling from the entire latent space (Ω) yields sibling graphs with degree distribution similar to the original graph (see Fig. 1c ). The model was trained on CORA-ML.

We provide further heatmaps for other metrics (16 in total) as well as visualizations for CITESEER in the appendix.

This experiment clearly demonstrates that by interpolating in the latent space we can obtain graphs with smoothly changing properties. The smooth transitions in the heatmaps provide evidence that our model learns to map specific parts of the latent space to specific properties of the graph. We can also see this mapping from latent space to the generated graph properties in the community distribution histograms on a 10 × 10 grid in Fig. 7 . Marked by (*) and (Ω) we see the community distributions for the input graph and the graph obtained by sampling on the complete latent space, respectively. In Fig. 7b and 7c , we see the evolution of selected community shares when following a trajectory from top to bottom, and left to right, respectively. The community histograms resulting from sampling random walks from opposing regions of the latent space are very different; again the transitions between these histograms are smooth, as can be seen in the trajectories in Fig. 7b and 7c .

5. DISCUSSION AND FUTURE WORK:

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 Table 2 ). 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.

6. CONCLUSION:

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.

APPENDIX:

We denote as V the set of all nodes in a graph, E as the set of edges, and as C i ⊆ V , i ∈ {1, . . . , k} communities in a graph. Every node in the graphs we consider is assigned to exactly one of these communities. N (v) = {v |(v, v ) ∈ E} denotes the set of neighbors of a node v, and d(v) = |N (v)| is the degree of node v.

Given two graphs G 1 and G 2 with the same number of nodes and edges, i.e.

|V 1 | = |V 2 |, |E 1 | = |E 2 |, we define their edge overlap as EO(G 1 , G 2 ) = |E 1 ∩ E 2 | |E 1 | = |E 1 ∩ E 2 | |E 2 | .

GRAPH GENERATION BASELINES:

Graph generation from node embeddings. As a naïve baseline for generating a graph from node embeddings, we propose the following strategy. As suggested by Grover & Leskovec (2016) , we train a logistic regression model on node embeddings learned by node2vec to get edge probabilities. Using these link prediction scores, we generate first-order random walks. The starting nodes are sampled from a categorical distribution where the probability for each node is proportional to its degree in the input graph. The subsequent nodes are sampled using the logistic regression model, i.e. proportional to the log probabilities of a link between the previous node and all other nodes. We repeat this for T=16 time steps and for 500K random walks. We use our procedure described in Section 3.3 to assemble an adjacency matrix from the transition counts.

Configuration model. In addition to randomly rewiring all edges in the input graph, we also generate random graphs with similar overlap as graphs generated by GraphGAN using the configuration model. For this, we randomly select a share of edges (e.g. 39%) and keep them fixed, and shuffle the remaining edges. This leads to a graph with the specified edge overlap; in Table 2 we show that with the same edge overlap, GraphGAN's generated graphs in general match the input graph better w.r.t the statistics we measure.

Exponential random graph model. The ERGM we used takes as parameters the edge count, density, degree correlation, deg1.5, and gwesp. Here, deg1.5 is the sum of all degrees to the power of 1.5, and gwesp refers to the geometrically weighted edgewise shared partner distribution (see Handcock et al. (2017) for details). Exponent of the power law distribution, where d min denotes the minimum degree in a network.

Gini coefficient

2 |V | i=1 i di |V | |V | i=1 di -|V |+1 |V |

Common measure for inequality in a distribution, where d is the sorted list of degrees in the graph.

Triangle count |{{u,v,w}|{(u,v),(v,w) Rel. edge distr. entropy

1 ln |V | v∈V -d(v) |E| ln d(v)

|E|:

Entropy of degree distribution, 1 means uniform, 0 means a single node is connected to all others.

Assortativity:

ρ = cov(X,Y ) σX σY

Pearson correlation of degrees of connected nodes, where the (x i , y i ) pairs are the degrees of connected nodes. Table 5 : GraphGAN with recurrent vs convolutional discriminator. We train GraphGAN with the recurrent and convolutional discriminator variants five times each and measure their link prediction scores on the CORA-ML dataset to evaluate which variant is suited better for our task. 

Discri:



:



Figures and Tables:

Figure1: GraphGAN is able to generate a sibling graph to the CITESEER network. (a) and (b) visualize a subset of nodes selected from the complete graphs. The graphs show similar structure but are not identical. (c) shows that the degree distributions of the input graph as well as the graphs generated by GraphGAN and the degree-corrected stochastic blockmodel are very similar.

Figure 3: Properties of generated graphs, trained on CORA-ML.

Figure 4: Effect of the random walk length on the performance.

Figure 5: (a) Node classification performance on CORA-ML, and (b) t-SNE visualization of W up , where the color indicates the ground truth communities.

Figure 6: Properties of the random walks as well as the graphs sampled from the 20 × 20 bins. 6a and 6b show properties of the random walks, 6c and 6d show properties of the generated graphs.

Figure 7: Community distributions (see appendix for definition) when sampling random walks on subsets of the latent space z. (a) shows complete community histograms on a 10 × 10 grid. (b) and (c) show exemplary trajectories in latent space. (Ω) is the community distribution when sampling from the entire latent space, and (*) is the community distribution of the CORA-ML network. Also available as an animation https://goo.gl/BGDX4o.

,(u,w)}⊆E}| 6 Number of triangles in the graph, where u ∼ v denotes that u and v are connected. Number of wedges, i.e. two-hop paths in an undirected graph.

Figure 10: Properties of the random walks as well as the graphs sampled from the 20 × 20 latent space bins, trained on CORA-ML.

Cat(p t ), and together with m t passed into f θ at the next step t + 1. Similarly to the classic GAN setting, a latent code z drawn from a multivariate standard normal distribution is passed through a parametric function g θ to initialize m 0 . The generative process of G is summarized in the box above.

Table content: <table><tr><td>The generator G defines an</td></tr><tr><td>implicit probabilistic model for generating</td></tr><tr><td>the random walks: (v 1 , ..., v T ) ∼ G. We model G as a sequential process based on</td></tr><tr><td>a neural network f θ parametrized by θ. At</td></tr><tr><td>each step t, f θ produces two values: the</td></tr><tr><td>probability distribution over the next node</td></tr><tr><td>to be sampled, denoted as p t , and the cur-</td></tr><tr><td>rent memory state of the model, denoted as</td></tr><tr><td>m t . The new node v t (represented as a</td></tr><tr><td>one-hot vector) is sampled from</td></tr></table>

Dataset statistics

Table content: <table><tr><td/><td colspan="2">Pol. Blogs Cora-ML</td><td>Cora</td><td>Citeseer</td><td>Pubmed</td><td>DBLP</td></tr><tr><td/><td/><td colspan="5">(McCallum et al., 2000) (Giles et al., 1998) (Sen et al., 2008) (Pan et al., 2016)</td></tr><tr><td>Number of nodes</td><td>1,490</td><td>2,995</td><td>19,793</td><td>3,312</td><td>19,717</td><td>17,716</td></tr><tr><td>Largest conn. comp. size</td><td>1,222</td><td>2,810</td><td>18,800</td><td>2,110</td><td>19,717</td><td>16,191</td></tr><tr><td>Number of edges</td><td>19,025</td><td>8,416</td><td>65,311</td><td>4,715</td><td>44,324</td><td>52,867</td></tr><tr><td>Edges in LCC</td><td>16,714</td><td>8,229</td><td>64,529</td><td>3,757</td><td>44,324</td><td>51,913</td></tr><tr><td>Number of communities</td><td>2</td><td>7</td><td>70</td><td>6</td><td>3</td><td>4</td></tr><tr><td colspan="2">4.1 GRAPH GENERATION</td><td/><td/><td/><td/><td/></tr></table>

Comparison of graph statistics between the original CORA-ML graph and graphs generated by GraphGAN and the baselines, averaged over 5 trials. Marked in bold and italics are the results that are closest and second-closest to the input graph, respectively. * indicates values for the configuration model that by definition exactly match the input graph.

Table content: <table><tr><td>Graph</td><td/><td colspan="2">Max. degree</td><td colspan="2">Assorta-tivity</td><td>Triangle count</td><td colspan="2">Power law exponent</td><td>Largest conn. comp.</td><td>Avg. Inter-com-munity density</td><td>Avg. Intra-com-munity density</td></tr><tr><td/><td/><td colspan="2">Avg. Std.</td><td>Avg.</td><td>Std.</td><td colspan="2">Avg. Std. Avg.</td><td>Std.</td><td>Avg. Std.</td><td>Avg.</td><td>Std.</td><td>Avg.</td><td>Std.</td></tr><tr><td>CORA-ML</td><td/><td>240</td><td/><td>-0.075</td><td/><td>2,814</td><td>1.86</td><td/><td>2,810</td><td>4.3e-4</td><td>1.7e-3</td></tr><tr><td>Conf. model Conf. model</td><td>(1% EO) (52% EO)</td><td>* *</td><td>* *</td><td colspan="3">-0.030 ± 0.003 322 ± 31 -0.051 ± 0.002 626 ± 19</td><td>* *</td><td>* *</td><td>2,785 ± 4.9 2793 ± 6.0</td><td>1.6e-3 ±1e-5 2.8e-4 ±1e-5</td></tr></table>

Link prediction performance.

Table content: <table><tr><td>Method</td><td>CORA-ML ROC AP</td><td>CORA ROC AP</td><td>CITESEER ROC AP</td><td>DBLP ROC AP</td><td>PUBMED ROC AP</td><td>POLBLOGS ROC AP</td></tr><tr><td>Adamic/Adar</td><td colspan="6">92.16 85.43 93.00 86.18 88.69 77.82 91.13 82.48 84.98 70.14 85.43 92.16</td></tr><tr><td>DC-SBM</td><td colspan="6">96.03 95.15 98.01 97.45 94.77 93.13 97.05 96.57 96.76 95.64 95.46 94.93</td></tr><tr><td>node2vec</td><td colspan="6">92.19 91.76 98.52 98.36 95.29 94.58 96.41 96.36 96.49 95.97 85.10 83.54</td></tr><tr><td>GraphGAN (500K)</td><td colspan="6">94.00 92.32 82.31 68.47 95.18 91.93 82.45 70.28 87.39 76.55 95.06 94.61</td></tr><tr><td>GraphGAN (100M)</td><td colspan="6">95.19 95.24 84.82 88.04 96.30 96.89 86.61 89.21 93.41 94.59 95.51 94.83</td></tr><tr><td colspan="7">GraphGAN ([W down , W up ]) 90.29 88.29 84.38 79.36 92.95 92.44 86.59 81.96 91.79 89.37 70.01 62.72</td></tr></table>

Graph statistics used to measure graph properties in this work.

Table content: <table><tr><td>Metric name</td><td colspan="4">Computation</td><td>Description</td></tr><tr><td>Maximum degree</td><td>max v∈V</td><td colspan="2">d(v)</td><td>Maximum degree of all nodes in a graph.</td></tr><tr><td colspan="5">Community distribution c i = v∈C i d(v) v∈V d(v)</td><td>Share of in-and outgoing edges of community C i , nor-malized by the number of edges in the graph.</td></tr><tr><td>LCC</td><td colspan="4">N max = max f ⊆F</td><td>|f |</td><td>Size of largest connected component, where F are all connected components.</td></tr><tr><td/><td/><td/><td/><td>-1</td></tr><tr><td>Power law exponent</td><td colspan="2">1 + n</td><td>u∈V</td><td>log d(u) dmin</td></tr></table>

Comparison of graph statistics between the CITESEER/CORA-ML graph and graphs generated by GraphGAN and DC-SBM, averaged after 5 trials. Marked in bold and italic are the results that are closest and second-closest to the ground truth graph, respectively, except for edge overlap, where lower can be considered better. ± 0.009 316 ± 11.2 2.154 ± 0.003 6.5e-4 ±2e-5 8 .0e-4 ±2e-5GraphGAN (76% EO) 63 ± 4.3 -0.054 ± 0.006 227 ± 13.3 2.204 ± 0.003 5.9e-4 ±2e-5 8.6e-4 ±1e-5 DC-SBM (6.6% EO) 53 ± 5.6 0.022 ± 0.018 257 ± 30.9 2.066 ± 0.014 7.6e-4 ±2e-5 5.3e-4 ±3e-5

Table content: <table><tr><td/><td/><td/><td>-</td><td colspan="2">ROC AUC</td><td colspan="2">Avg. Prec.</td><td/><td/><td/></tr><tr><td/><td/><td colspan="2">minator</td><td colspan="2">Mean Std.</td><td colspan="2">Mean Std</td><td/><td/><td/></tr><tr><td/><td/><td colspan="6">Recurrent 92.07 ± 0.005 94.88 ± 0.002 Conv. 89.70 ± 0.017 93.02 ± 0.011</td><td/><td/><td/></tr><tr><td>Graph</td><td>Max. degree</td><td/><td colspan="2">Assortativity</td><td>Triangle count</td><td colspan="2">Power law exponent</td><td colspan="3">Avg. Inter-com-munity density</td><td>Avg. Intra-com-munity density</td></tr><tr><td/><td colspan="2">Avg. Std.</td><td>Avg.</td><td>Std.</td><td colspan="2">Avg. Std. Avg.</td><td>Std.</td><td colspan="2">Avg.</td><td>Std.</td><td>Avg.</td><td>Std.</td></tr><tr><td>CITESEER</td><td>77</td><td/><td>-0.022</td><td/><td>451</td><td>2.239</td><td/><td colspan="2">4.9e-4</td><td/><td>9.3e-4</td></tr><tr><td colspan="12">GraphGAN (42% EO) -0.082 Conf. model 54 ± 4.2 * * -0.017 ± 0.006 20 ± 6.50 Conf. model (42% EO) * * -0.020 ± 0.009 54 ± 8.8 Conf. model (76% EO) * * -0.024 ± 0.006 207 ± 11.8 node2vec naïve 9 ± 0.4 -0.052 ± 0.021 2 ± 0.49 2.04 ± 0.002 1.1e-3 ±2e-5 2.7e-4 ±1e-5 * * 1.1e-3 ±1e-5 2.3e-4 ±2e-5 * * 8.4e-4 ±1e-5 5.1e-4 ± 1e-5 * * 6 .3e-4 ±1e-5 7.6e-4 ± 1e-5 ERGM (27% EO) 66 ± 1 0.052 ± 0.005 415.6 ± 8 2.0 ± 0.01 9.3e-4 ±2e-5 4.8e-4 ±6e-6 CORA-ML 240 -0.075 2,814 1.86 4.3e-4 1.7e-3</td></tr><tr><td>GraphGAN (39% EO) GraphGAN (52% EO) DC-SBM (11% EO) Conf. model Conf. model (39% EO) Conf. model (52% EO) node2vec naïve ERGM (56% EO)</td><td colspan="5">199 ± 6.7 233 ± 3.6 165 ± 9.0 * * * * * * 14 ± 1.4 243 ± 1.94 -0.077 ± 0.000 2,293 ± 23 -0.060 ± 0.004 1,410 ± 30 -0.066 ± 0.003 1,588 ± 59 -0.052 ± 0.004 1,403 ± 67 -0.030 ± 0.003 322 ± 31 -0.050 ± 0.005 420 ± 14 -0.051 ± 0.002 626 ± 19 -0.007 ± 0.011 16 ± 4.4</td><td colspan="6">1.773 ± 0.002 6 .5e-4 ±1e-5 1 .3e-3 ±2e-5 1.793 ± 0.003 6.0e-4 ±1e-5 1.4e-3 ±1e-5 1.814 ± 0.008 6.7e-4 ±2e-5 1.2e-3 ±4e-5 * * 1.6e-3 ±1e-5 2.8e-4 ±1e-5 * * 1.1e-3 ±1e-5 8.0e-4 ±1e-5 * * 9.8e-4 ±1e-5 9.9e-4 ±2e-5 1.68 ± 0.001 1.4e-3 ±1e-5 3.8e-4 ±2e-5 1.786 ± 0.003 6.9e-4 ±2e-5 1.2e-3 ±1e-5</td></tr><tr><td>Graph</td><td colspan="2">Wedge count</td><td colspan="2">Rel. edge distr. entr.</td><td>Largest conn. comp</td><td colspan="2">Claw count</td><td/><td colspan="2">Gini coeff.</td><td>Edge overlap</td></tr><tr><td/><td>Avg.</td><td>Std.</td><td>Avg.</td><td>Std.</td><td>Avg. Std.</td><td>Avg.</td><td colspan="2">Std.</td><td>Avg.</td><td>Std.</td><td>Avg.</td><td>Std.</td></tr><tr><td>CITESEER</td><td>16,824</td><td/><td>0.959</td><td/><td>2,110</td><td colspan="2">125,701</td><td/><td>0.404</td><td/><td>1</td></tr><tr><td>GraphGAN (42% EO) GraphGAN (76% EO) DC-SBM (6.6% EO) Conf. model Conf. model (42% EO) Conf. model (76% EO) node2vec naïve ERGM (27% EO) CORA-ML</td><td colspan="2">12,998 ± 84.6 15,202 ± 378 15,531 ± 592 * * * * * * 8,157 ± 36.0 16,346 ± 101 101,872</td><td colspan="6">0.969 ± 0.000 2,079 ± 12.6 57,654 ± 4,226 0.963 ± 0.000 2,053 ± 23 94,149 ± 11,926 0.938 ± 0.001 1,697 ± 27 69,818 ± 11,969 0.955 ± 0.001 2,011 ± 6.8 * * 0.956 ± 0.001 2,045 ± 12.5 * * 0.957 ± 0.001 2,065 ± 10.2 * * 0.986 ± 0.000 2,110 ± 0.0 6,671 ± 121.4 0.945 ± 0.001 1,753 ± 15 80,510 ± 1,337 0.941 2,810 3.1e6</td><td colspan="3">0.354 ± 0.001 0.42 ± 0.006 0.385 ± 0.002 0.76 ± 0.01 0.502 ± 0.005 0.066 ± 0.011 * * 0.008 ± 0.001 * * 0.42 ± 0.002 * * 0.76 ± 0.0 0.257 ± 0.002 0.004 ± 0.001 0.474 ± 0.003 0.27 ± 0.01 0.482 1</td></tr><tr><td>GraphGAN (39% EO) GraphGAN (52% EO) DC-SBM (11% EO) Conf. model Conf. model (39% EO) Conf. model (52% EO) node2vec naïve ERGM (56% EO)</td><td colspan="11">75,724 ± 1,401 0.959 ± 0.000 2,809 ± 1.6 86,763 ± 1,096 0.954 ± 0.001 2,807 ± 1.6 73,921 ± 3,436 0.934 ± 0.001 2,474 ± 18.9 1.2e6 ± 170,045 0.523 ± 0.003 0.11 ± 0.003 1.8e6 ± 141,795 0.398 ± 0.002 0.39 ± 0.004 2 .6e6 ± 103,667 0.42 ± 0.003 0.52 ± 0.001 * * 0.928 ± 0.002 2,785 ± 4.9 * * * * 0.013 ± 0.001 * * 0.931 ± 0.002 2,793 ± 2.0 * * * * 0.39 ± 0.0 * * 0.933 ± 0.001 2,793 ± 6.0 * * * * 0.52 ± 0.0 31,456 ± 91.5 0.990 ± 0.000 2,810 ± 0.1 47,548 ± 516 0.226 ± 0.002 0.006 ± 0.001 98,615 ± 385 0.932 ± 0.001 2,489 ± 11 3, 1e6 ± 57,092 0.517 ± 0.002 0.56 ± 0.014</td></tr></table>

Peer review (iclr2018):
 I am overall positive about the work but I would like to see some questions addressed. Quality: The paper is good but does not address some important issues. The paper proposes a GAN model to generate graphs with non-trivial properties. This is possibly one of the best papers on graph generation using GANs currently in the literature. However, there are a number of statistical issues that should be addressed. I fear the paper is not ready yet, but I am not opposed to publication as long as there are warnings in the paper about the shortcomings. Originality: This is an original approach. Random walks sometimes are overused in the graph literature, but they seem justified in this work. But it also requires extra work to ensure they are generating meaningful graphs. Significance: The problem is important. Learn to generate graphs is a key task in drug discovery, relational learning, and knowledge discovery. Evaluation: The link prediction task is too easy, as links are missing at random. It would be more useful to predict links that are removed with an unknown bias. The graph (wedge, claw, etc) characteristics are good (but simple) metrics; however, it is unclear how a random graph with the same size and degree distribution (configuration model) would generate for the same metrics (it is not shown for comparison). Issues that I wish were addressed in the paper: a) How is the method learning a generator from a single graph? What are the conditions under which the method is likely to perform well? It seems to rely on some mixing RW conditions to model the distinct graph communities. What are these mixing conditions? These are important questions that should have at least an empirical exploration. b) What is the spatial independence assumption needed for such a generator? c) Would this approach be able to generate a lattice? Would it be able to generate an expander graph? What about a graph with poorly connect communities? Is there any difficulties with power law graphs? d) How is the RW statistically addressing the generation of high-order (subgraph) features? e) Can this approach be used with multiple i.i.d. graphs? f) Isn’t learning the random walk sample path a much harder / higher-dimensional task than it is necessary? Again, the short walk may be capturing the communities but the high-dimensional random walk sample path seems like a high price to pay to learn community structure. g) Clearly, with a large T (number of RW steps), the RW is not modeling just a single community. Is there a way to choose T? How larger values of T to better model inter-community links? Would different communities have different choices of T? h) And a related question, how well can the method generate the inter-community links? i) The RW model is actually similar to an HMM. Would learning a mixture of HMMs (one per community) have similar performance?