Title: GRAPH GENERATION VIA SCATTERING

Abstract: Generative networks have made it possible to generate meaningful signals such as images and texts from simple noise. Recently, generative methods based on GAN and VAE were developed for graphs and graph signals. However, the mathematical properties of these methods are unclear, and training good generative models is difficult. This work proposes a graph generation model that uses a recent adaptation of Mallat's scattering transform to graphs. The proposed model is naturally composed of an encoder and a decoder. The encoder is a Gaussianized graph scattering transform, which is robust to signal and graph manipulation. The decoder is a simple fully connected network that is adapted to specific tasks, such as link prediction, signal generation on graphs and full graph and signal generation. The training of our proposed system is efficient since it is only applied to the decoder and the hardware requirement is moderate. Numerical results demonstrate stateof-the-art performance of the proposed system for both link prediction and graph and signal generation. These results are in contrast to experience with Euclidean data, where it is difficult to form a generative scattering network that performs as well as state-of-the-art methods. We believe that this is because of the discrete and simpler nature of graph applications, unlike the more complex and high-frequency nature of Euclidean data, in particular, of some natural images.

1. INTRODUCTION:

Generative neural networks have been successfully applied to various tasks such as the generation of images and texts. Their development is based on fruitful methods of deep learning, such as convolutional and recurrent neural networks. These and other methods of deep learning, which were initially developed for problems in the Euclidean domain1 , have been successfully generalized to address supervised learning tasks in the graph domain. In particular, a variety of graph convolutional networks have been developed, including networks with prescribed parameters (Zou & Lerman, 2018; Gama et al., 2018) and trained networks (Henaff et al., 2015; Defferrard et al., 2016; Kipf & Welling, 2017; Chen et al., 2017) . It is natural to use these tools to build generative models in the graph domain.

Most generative graph networks directly use standard graph networks by following either of the following two generative frameworks: the generative adversarial network (GAN) (Goodfellow et al., 2014) and the variational auto-encoder (VAE) (Kingma & Welling, 2014) . In a GAN, a generator and an auxiliary adversarial discriminator are trained together. On the other hand, in VAE, an encoder and a decoder (or generator) are both trained according to Bayesian models. Both frameworks contain two components (generator and discriminator or encoder and decoder), where each of them requires training. For GAN, training two components corresponds to a difficult min-max problem. On the other hand, training the two components in VAE can be described as a non-convex minimization problem. However, it is a crude approximation to the motivating variational inference formulation. Given an encoding process with guaranteed mathematical properties, one can focus on training only the decoder, or the generator, which is more tractable. In the Euclidean domain, Angles & Mallat (2018) use the scattering transform as an encoder, which is robust to deformations of input signals, and learn a generative model by minimizing the l 1 -loss for reconstructing the training images. We adopt a similar method, using the graph scattering transform (Zou & Lerman, 2018) as an encoder for graph signals, which is robust to signal and graph manipulations, and train neural networks corresponding to respective tasks. However, numerical experience indicates that a conventional generative scattering network is not as competitive as state-of-the-art results based on GAN and VAE. This is probably due to the complexity of some Euclidean-type datasets and their nontrivial high frequency components. Nevertheless, graph-type datasets have a discrete nature, and they often do not exhibit high frequency components. Therefore, the graph scattering transform might be competitive and efficient for specific generative tasks in the graph domain.

We consider three types of graph generation tasks:

• Link prediction: In this task, one is interested in predicting whether two vertices from the same graph are connected. The common input includes a graph with missing edges and features of vertices. The goal is to decide whether an edge exists between any pair of vertices. This can be viewed as generating a graph from a latent representation of the partially available graph.

A well-known application of this task is the prediction of citations. Common citation datasets were collected by Sen et al. (2008) and further pre-processed by Kipf & Welling (2016) . These datasets of publications and citations contain features for each publication as well as citation linkage, which are modeled by an undirected graph. In the pre-processed data, one only partially knows the citation linkage and the task is to recover the citations for all pairs of publications.

• Signal generation on graphs: In this task, the graph is fixed and the set of vertices and edges is known. The goal is to generate signals on the given graph. Although we are unaware of convincing data of this type, we believe that this is a potentially useful task. Among the three tasks we review here, it is most similar to generation tasks in Euclidean domains. We can thus enforce some graph structure in special Euclidean-type or grid-type datasets. Here we pursue this idea with the Fashion-MNIST dataset of images of clothing items (Xiao et al., 2017) . We do not consider the domain of a 28 × 28 pixel image as Euclidean, but associate to it a graph, where each pixel is connected by an edge with its nearby neighbors. Each image is then a signal on this graph. One then needs graph-based methods for generating these signals.

• Graph and signal generation: In this task, one needs to generate both the graph structure and the signals on the graph. An interesting application is the design of chemical molecules. A network learns from a given dataset, such as QM9 (Ramakrishnan et al., 2014) , to generate both the atoms (signals on vertices) and the bonds (edges) from a latent sample. This can be used as a pure machine learning approach for the design of new drugs (Olivecrona et al., 2017) .

Our proposed method is easy to implement. Furthermore, the adjustment of the structure of the decoder to the three types of tasks does not require a lot of effort. Unlike GAN or VAE, the model in this paper does not require training two components either iteratively or at the same time. Meanwhile, there is flexibility in designing the graph wavelets and in choosing the decoder structure. We believe it is a highly adaptable method for various graph tasks and indeed our numerical experiments demonstrate competitive results.

2. BACKGROUND:

We overview previous relevant works as follows: §2.1 reviews generative scattering networks, §2.2 reviews graph convolutional networks, and §2.3 reviews some recent graph generative models.

2.1. SCATTERING NETWORKS FOR GENERATIVE MODELS:

The generative scattering network (Angles & Mallat, 2018) can be considered as an encoder-decoder system in which one only needs to train the decoder. The feature extraction part of the encoder is a scattering transform (Mallat, 2012; Bruna & Mallat, 2013) with fixed parameters. It provides multi-scale signal representation, which is Lipschitz continuous with respect to small deformations. The next part of the encoder transforms the representations of the input signals into samples of a Gaussian latent variable. Figure 1 shows the structure of a generative scattering model.

The decoder of the generative scattering network can be taken to be a multi-layer perceptron (MLP). We denote the encoder by Φ and the decoder by D. Given input samples {x (t) } T t=1 , the decoder is trained by minimizing the expected reconstruction loss

L Φ (D) = T t=1

x (t) -D(Φ(x (t) ))

1

.

Figure 1 : The structure of a generative scattering network.

This generative scattering network is interesting because of its simple implementation with a prescribed encoder and because of the mathematically guaranteed properties of this encoder.

2.2. GRAPH CONVOLUTIONAL NETWORKS:

Convolution is a key contributor for the recent success of deep learning. In the Euclidean domain, convolutional networks are helpful in learning multi-scale representations. The same idea was introduced to graphs by exploiting the spectral graph representation, that is, the spectral decomposition of the graph weight matrix or graph Laplacian (Bruna et al., 2014; Henaff et al., 2015) . A common proposal for a graph convolution uses pointwise multiplication of the graph Fourier-transformed signals, where the graph Fourier transform uses the basis of the spectral decomposition of the Graph Laplacian in place of the discrete Fourier basis. One can apply nonlinear functions such as the ReLU for each graph vertex. A variety of good approximations to the spectral approach are able to speed up the spectral decomposition process and maintain accuracy (Defferrard et al., 2016; Kipf & Welling, 2017) .

A special type of graph convolutional network (GCN) is the graph scattering network (Zou & Lerman, 2018) , which does not require training and was proved to be approximately invariant to permutations and stable to sufficiently small signal or graph manipulations. A graph scattering network uses graph wavelets (Hammond et al., 2011) defined on the eigenspace of the graph Laplacian to construct multi-layer models. Alternatively, Gama et al. (2018) construct graph scattering transforms using an earlier graph wavelet transform (Coifman & Maggioni, 2006) . In general, the graph wavelets of Hammond et al. (2011) are more flexible as one can choose different kinds of wavelets on the spectral domain according to different tasks. While the graph wavelets of Coifman & Maggioni (2006) are not flexible, they use the normalized graph Laplacian and the corresponding diffusion map and metric, which might be natural for particular applications.

2.3. GRAPH GENERATIVE NETWORKS:

Several recent papers address graph generation networks with either a GAN or a VAE structure. We briefly survey these two types of graph models.

2.3.1. GAN-TYPE GRAPH NETWORKS:

As in regular GAN's, GAN-type graph networks use a discriminator in order to compete with the generator and make its training more powerful. In the following, we describe some recent graph generation models of this type.

NetGAN. The NetGAN (Bojchevski et al., 2018) first generates random walks on the graph vertices, whose features are given. Such features include various properties of the vertices. Specifically, the random walks are sequential processes that depart from the graph vertices and travel along edges of the complete graph. To form the edges and thus generate the graph, a threshold is put on the frequency of travels between pairs of vertices. A Wasserstein GAN structure is used for training the generator. Both the generator and the discriminator take the structure of a Long-Short-Term-Memory (LSTM) network (Hochreiter & Schmidhuber, 1997) . This model is mainly designed for link prediction or graph generation with given features of vertices. It is successful in generating graphs with properties, such as max degree and triangle count, that are similar to those of the samples. However, the model is complicated and hard to train.

GraphGAN. The GraphGAN (Wang et al., 2018) generates for each vertex the distribution of edges associated with it. It adopts the original GAN setting, where the objective is to minimize the sum over all vertices of KL-divergences between real and generated distributions. An interesting graphtype softmax function is used to overcome some problems that arise when applying the common softmax function to this network. This model is used for link prediction problems or graph generation with given features of vectors. Wang et al. (2018) demonstrate results for node classification and recommendation problems, whose tasks are very similar to that of the link prediction problem.

MolGAN. The MolGAN (De Cao & Kipf, 2018) generates signals with respect to both vertices and edges. It seeks to minimize the sum of two Wasserstein loss functions, where the first one includes a sum over all vertices and the second one a sum over pairs of vertices to account for possible edges. Therefore, MolGAN is designed to solve the graph and signal generation problem in the context of molecule generation. The signals for edges provide the bonds and the vertex signals assign for each vertex a type of atom. In order to emphasize respective molecular properties and improve scores for them, MolGAN utilizes an auxiliary reward network. The generator is trained with both the adversarial discriminator and the reward network.

2.3.2. VAE-TYPE GRAPH NETWORKS:

VAE can be generalized for graphs by considering distributions on graph vertices. It still utilizes the encoder-decoder system, but the encoder is usually taken to be a graph convolutional neural network.

VGAE. The variational graph auto-encoder (VGAE) of Kipf & Welling (2016) is designed mainly for link prediction. Its generator has a structure similar to a regular VAE. It contains a GCN (Kipf & Welling, 2017) encoder and an inner product decoder. The GCN produces either the mean and variance of the latent code (in the probabilistic version), or just the latent code itself. The latent code produces vectors for the vertices, and their inner-product provides a similarity measure, which is used to determine whether a link exists between two vertices.

GraphVAE. The GraphVAE (Simonovsky & Komodakis, 2018 ) also uses a VAE setting. Unlike VGAE, it focuses on the graph and signal generation problem. To achieve this, it considers the adjacency matrix A, edge features E, which is a set of signals of the graph edges, and vertex features F , which is a set of signals on the graph vertices. The loss that needs to be optimized is a function of A, E and F . The computational complexity of GraphVAE is of order O(N 4 ). Therefore, it is most suitable for tasks with a small number of vertices, such as molecule generation. A recent variant of VAE, JT-VAE (Jin et al., 2018) , is specifically designed for generating complex molecules while enforcing validity. Since our numerical experiments do not consider complex molecules, it is not relevant for this manuscript.

3. GRAPH GENERATIVE SCATTERING NETWORK:

In general, the design of the graph generation networks in §2.3 is complex and their hyperparameter selections are difficult. Furthermore, training GAN and VAE are known to be difficult. In view of these obstacles, we propose here the graph generative scattering network. It is composed of two components: an encoder and a decoder. The encoder is a graph scattering network (Zou & Lerman, 2018) , which produces a latent representation for the graph signal. We use it to form a latent Gaussian distribution. The parameters of the graph scattering network are predetermined, unlike the parameters of a generative auto-encoder that are learned. The decoder learns the mapping from the latent Gaussian distribution according to the corresponding tasks. In any of the graphspecific tasks we mentioned in §1, the decoder can be taken to be a network with fully-connected layers, whose structure is determined by the specific task. More details on forming the encoder and decoder are provided in §3.1 and §3.2, respectively.

3.1. DETAILS OF THE ENCODER:

In order to fully understand the formation of the encoder, we review the graph scattering network of Zou & Lerman (2018) and explain how to form a Gaussian distribution from its output. We consider a graph G = (V, E) with |V | = N vertices. A signal in L 2 (V ; R K ) can be regarded as a matrix X ∈ R N ×K . The scattering transform can be regarded as a function that acts on the columns of X.

Let L ∈ R N ×N be the unnormalized graph Laplacian L = D -W , where D is the diagonal matrix of degrees and W is the weight (adjacency) matrix whose (n, m)-th entry is the weight of the edge connecting vertices v n and v m . Its spectral decomposition can be written as

L = N -1 l=0 λ l u l u * l , with 0 = λ 0 ≤ • • • ≤ λ N -1 .

We assume dyadic wavelets φ and ψ satisfying for some

J ∈ Z, | φ-J | 2 + j>-J | ψj | 2 = 1, where ψj (ω) = ψ(2 -j ω) for j > -J and φ-J (ω) = φ(2 -J ω).

For f ∈ R N , the graph wavelet transform (Hammond et al., 2011) is

f * ψ j = N -1 l=0 u l u * l f ψ(2 -j λ l ), for j > -J ; and f * φ -J = N -1 l=0 u l u * l f φ(2 J λ l ) .

For any m no larger than the number of layers, a path p = (j 1 , • • • , j m ) is a vector of m scales of the graph wavelets, which satisfy 0

≤ j 1 , • • • , j m ≤ J -1.

The scattering propagator with respect to a path p is obtained by consecutive application of convolutions with wavelets of these scales and absolute values, which serve as nonlinearities, in the following way

U [p]f = f * ψ j1 * ψ j2 * • • • * ψ jm .

The scattering transform with respect to the path p is obtained by

S[p]f = U [p]f * φ -J .

Let P denote the collection of all paths of length no larger than the number of layers. The scattering transform of f with respect to P is

S[P]f = (S[p]f ) p∈P .

We note that the scattering transform depends on the underlying graph. For simplicity, we exclude this dependence from our notation.

For the

K-dimensional signal X = [X 1 | • • • |X K ] ∈ R N ×K , the scattering transform is S[P]X = (S[P]X k ) K k=1 .

We remark that if the set P is finite and has L elements, then denoting M = LK, S[P](X) can be represented as a matrix in R N ×M or a vector in R N •M . We denote the latter vector by X.

To make an effective encoder, an affine transformation A is applied to S[P](X) as a whitening filter as follows. Let { X(t) } T t=1 be the scattering transform vectors of the input samples {X (t) } T t=1 . Let X and X be the representing matrices of

{X (t) } T t=1 and { X(t) } T t=1 , respectively. That is, X = (X (t) ) T t=1 ∈ R T ×N K and X = ( X(t) ) T t=1 ∈ R T ×N M .

As advocated in Angles & Mallat (2018) , a dimension reduction by PCA can be further applied to { X(t) } T t=1 and X . Next, using the following mean and sample covariance of the scattering transform vectors

µ = 1 T T t=1 X(t) and Σ = 1 T T t=1 ( X(t) -µ)( X(t) -µ) * ,

X is linearly transformed in the following way

A X = Σ -1/2 ( X -µ) .

(1) We denote the matrix A X by Φ[P](X ), or in short Φ(X ). We note that the mapping Φ is a decomposition of the scattering transform and whitening and can also be applied to any signal X ∈ R N ×K . We denote the feature vector corresponding to the K-dimensional signal X by z = Φ[P](X) ∈ R N ×M . We also refer to z as a latent code. Zou & Lerman (2018) proved that the scattering transform S[P] is robust to small perturbations of the signal and the graph. The affine transform A only amplifies their perturbation estimates by at most Σ -1/2 , that is, by the spectral norm of Σ -1/2 . Therefore, their result applies to the encoder.

3.2. DETAILS OF THE DECODER:

We recall that the decoder is a network with fully-connected layers. We describe its architecture according to the following three different tasks.

3.2.1. LINK PREDICTION:

For link prediction, we encode the features of the partially available graph into a latent vector, and use the same vector to generate the full graph via the learned decoder. Note that in this task only one fixed graph is given, and thus no Gaussianization procedure is applied in the encoder. That is, the linear transformation A in (1) is the identity. The input includes a weight matrix W train , which contains weights for the partially available edges, and a feature matrix X ∈ R N ×K of Kdimensional signals on the N nodes. The encoder is a scattering network Φ that maps X and W train ∈ R N ×N into a latent representation z ∈ R N ×M . As in Kipf & Welling (2016) , the decoder is a simple network D such that D(z) = σ( D(z) D(z) T ), where σ is the softmax function and D is an MLP. The network D, whose parameters are those of D, is trained to minimize the cross-entropy loss function

L(D) = i,j:W (i,j) =0 [-log D(Φ(X, W ))(i, j)] .

(2)

The structure of the entire network is illustrated in Figure 2 . 

3.2.2. SIGNAL GENERATION ON GRAPHS:

For signal generation on graphs, which we also refer to as graph signal generation, one is given a fixed graph domain and different signals on the nodes of this graph and the goal is to generate similar signals. An input random variable X ∈ R N ×K is first mapped by the scattering transform to S[P](X) and then to a Gaussian z = Φ[P](X) ∈ R N ×M . The decoder D is taken to be an MLP that maps z to a matrix D(z) in R N ×K . The parameters of D are obtained by minimizing the reconstruction loss function

EQUATION

where {X (t) } T t=1 are the training data points. The structure of the generative network is the same as in Figure 1 , where in the current case S is the graph scattering transform. Figure 3 illustrates the generation procedure.

3.2.3. GRAPH AND SIGNAL GENERATION:

The scattering transform can be used as an encoder for generating both the graph and the signal on it. We train two MLP's D 1 and D 2 , where both take the Gaussian random variable z = Φ(X) as input. The network D 1 is used to generate the graph signal X and the network D 2 (z) = σ( D2 (z) D2 (z) T ) is used to generate the weight matrix W . They are trained at the same time, with the reconstruction loss function where {(X (t) , W (t) )} T t=1 are the training data points. The norms can be replaced with cross-entropy losses if one wants the outputs to be categorical. Figure 4 illustrates this generation procedure. 

EQUATION

4. EXPERIMENTS:

We test our proposed method, which we refer to in short as "SCAT", and compare it with other available algorithms using datasets addressing the three different tasks reviewed in §1. We describe our results in the three subsections below according to these tasks. Our method requires moderate memory and GPU, and we thus use a PC with 8GB RAM and a single GTX1060 GPU. All the neural networks in this section are trained using the TensorFlow library. Following Zou & Lerman (2018) we use in all experiments the simple Shannon wavelet, J = 3 and 3 layers.

4.1. LINK PREDICTION FOR CITATION DATA:

We predict links for the three citation datasets of Sen et al. (2008) : Cora, Citeseer and Pubmed. Each dataset contains information about publications in certain fields and the corresponding citation linkage between these publications. This information can be embedded in a graph in which the publications and citations are represented by vertices and edges, respectively. Although the citation link is directed, we follow the common convention of assuming an undirected and unweighted graph. That is, if any of two papers cite the other, an edge is drawn between them. Some characteristics of the three datasets are listed in Table 1 . We construct the encoder of SCAT using a scattering transform, where the output dimension is reduced to 128. The decoder D in §4.1 is taken to be a single dense layer of size 512, activated by the ReLU function. In order to minimize (2), we use the Adam optimizer with a learning rate of 0.001, where we train 1,000 epochs for each run. We record the following two common scores: area under curve (AUC) and average precision (AP). Similarly to Kipf & Welling (2016) , we take 10 runs for each setting and record the average and standard deviation. Table 2 reports our results for SCAT together with results obtained in Kipf & Welling (2016) for VGAE, spectral clustering (SC) (Tang & Liu, 2011) and deep walk (DW) (Peyré et al., 2017) . We could test the results of VGAE using Cora and Citeseer on our own machine and thus reported these results, where we mention the corresponding results of Kipf & Welling (2016) in the caption of Table 2 . However, on the high-dimensional Pubmed dataset, a direct run of the VGAE codes exhausts the computing resource on our machine. We also did not verify the reported results of SC and DW as we lacked their codes. We note that SCAT improves over the previous results for the three datasets 

We use the Fashion-MNIST dataset (Xiao et al., 2017) for a sanity check of SCAT for the problem of graph signal generation. Any element of this dataset is a 28 × 28 grayscale pixel image and can be considered as a graph in the following way: the pixels are the graph vertices, and nearby pixels are connected by graph edges. The edges and weights are formed as in Zou & Lerman (2018) . That is, each pixel represents a vertex and it is connected with its four nearest neighbors with weight e -1 and its four nearest diagonal neighbors with weight e -2 .

The encoder of this network is a graph scattering transform, whereas the output dimension is reduced to 256 from 28 × 28 × 13 = 10, 192. The decoder is an MLP of two hidden layers of size 512. In order to minimize (3), we use the Adam optimizer with a learning rate of 0.001, where we train 200 epochs for each run. We have restricted the dataset to the "boots" category, which contains 5,454 training examples. Sample images from this category are demonstrated in Figure 5a .

To generate an "image" (or graph signal), we take a sample z ∈ R N from the standard normal distribution, and report the output of the decoder. Figure 5c illustrates samples generated by the network, while using the graph associated with a 28 × 28 pixel image. The reconstruction loss defined in (3) is 0.022. The relative error, which is obtained by dividing the reconstruction loss by the average L1-norm of the training images, which equals 174.56, is 0.0126%. We remark that the scattering transform for the whole training data takes 5.05s and it takes 5.38s to train each epoch.

In Figure 5b the encoder uses the original data of Figure 5a as input and its output is fed into the decoder. This figure then reports the corresponding output of the decoder.

We note that the random generated "images" (or graph signals) in Figure 5 cover a variation of boot shapes and heel types. However, some high frequency components of these images are missing. This is expected in scattering networks and is evident in results obtained by the Euclidean generative scattering network of Angles & Mallat (2018) . Nevertheless, graph-type data often do not have high resolution and frequencies. For instance, in the molecular data reviewed in §4. Figure 5 : Original and generated images for boots of MNIST-fashion data. We assume the graph associated with the 28 × 28 pixel image. Figure 5a shows samples from the original data, 5b shows samples generated using features encoded by the scattering transform from the same samples, and Figure 5c shows samples generated from random Gaussian noise.

generating high-frequency components. This problem is more noticeable with our graph version of GAN than with the other two methods, that is, graph version of vanilla VAE and SCAT.

4.3. GRAPH GENERATION FOR MOLECULAR DATA:

We test graph and signal generation using the molecular dataset QM9 (Ramakrishnan et al., 2014) . This dataset contains 134k molecules made of the following atoms: C, H, O, N, and F. There are two common ways of embedding these kinds of datasets into an interpretable feature space. Kusner et al. (2017) treats molecules as "words" by looking at their simplified molecular-input line-entry (SMILE) strings. Graphs are also commonly used to represent molecules, where the graph vertices represent the atoms composing the molecule and the graph edges are the bonds. The vertex signals assign the four different atom types to the vertices. While there are five type of atoms, H is automatically determined by the other atoms and the given chemical bonds. We thus represent the atoms C, O, N and F as one-hot vectors, that is, by the four unit vectors in R 4 .

For graph generation, there is no unique benchmark for checking the quality of the generated graphs. Bojchevski et al. (2018) proposed to use graph properties such as the max degree and the number of triangles for graph generation. However, it is often hard to compare these graph properties and for molecular generation these ideas are not well-motivated. Samanta et al. (2018) proposed to check validity (whether a sample is a valid chemical molecule), uniqueness (whether a sample is unique among all generated samples) and novelty (whether a sample is different from any sample in the training data). We use this measure since it is more quantitative and experiments on QM9 by Simonovsky & Komodakis (2018) and De Cao & Kipf (2018) also report these quantities.

The training set of our main experiment uses 90k molecules composed of nine atoms from QM9. In this experiment, we consider two different settings. In the first one, we condition the samples to be molecules of seven Carbons, one Oxygen and one Nitrogen. In the second one, we do not enforce any assumption. As explained in §3.2.3, in this particular graph generative scattering network, the decoders for both vertices and edges are MLP's. We form them with a single hidden layer, with size 4 for vertices and 32 for edges. We take the encoder to be a graph scattering transform, with output dimension reduced to 15. In order to minimize (4), we use the Adam optimizer with a learning rate of 0.001, where we train 1,000 epochs. The computation of the scattering transform for the whole training data takes 74.04s and it takes 0.424s to train each epoch.

Using SCAT, we generate 10k molecules and record the validity, uniqueness, and novelty in Table 3 . We illustrate samples generated by SCAT in Appendix §6.2. We also record in this table results reported in De Cao & Kipf (2018) for the following methods: CharacterVAE (Gómez-Bombarelli et al., 2018), GrammarVAE (Kusner et al., 2017) , GraphVAE (Simonovsky & Komodakis, 2018) and MolGAN (De Cao & Kipf, 2018) . Since there is no publicly available implementation of these algorithms, we cannot test their results on our machine using our setting. Kipf (2018) and report its result in Table 3 as "SCAT with padding". In this setting, we use the complete QM9 dataset for training. The one-hot vectors are in R 5 as an additional dimension is assigned for a non-existing atom due to padding. We form the single hidden layer, with size 5 for vertices and size 32 for edges. We take the encoder to be a graph scattering transform, with output dimension reduced to 15. In order to minimize (4), we use the Adam optimizer with a learning rate of 0.001, where we train 1,000 epochs. The computation of the scattering transform for the whole training data takes 110.57s and it takes 0.842s to train each epoch.

Our network achieves high scores for validity and novelty and moderate score for uniqueness. The moderate values of the uniqueness score may indicate on some form of mode collapse. That is, the generated molecules may not well-represent the whole variety of molecules, but a certain mode of their distribution. Nevertheless, the only two methods with higher uniqueness modes, Charac-terVAE and GraphVAE, have low scores of validity and their scores of novelty are not sufficiently competitive. 

5. CONCLUSION:

We proposed the graph generative scattering network as a generative model for graphs and graph signals. The network allows a prescribed encoder which does not require training and is approximately invariant to permutations and stable to graph deformations. Numerical experiments show competitive results for the tasks of link prediction in citation data and molecule generation. We believe this method has the potential to be used in a wider range of applications on graphs.

We used the Fashion-MNIST dataset as a sanity check for the graph signal generation, since we are unaware of a more convincing application for this specific task. In this application, we do not expect graph-based methods to compete with general methods, because graphs only retain partial spatial relationships. Indeed, the resolution of the generated images is not as good as that of the original images. Nevertheless, since the results in the similar discrete tasks of link prediction and molecule generation are competitive, we believe that SCAT also bears promise for graph signal generation, when the signals are of low resolution.

:

We remark that the Euclidean and graph domains include scenarios whose underlying datasets have Euclidean and graph structures, respectively.

Figures and Tables:

Figure 2: Sketch of a graph scattering network for link prediction.

Figure 3: Sketch of a graph scattering network for signal generation on graphs.

Figure 4: Sketch of the graph scattering network for graph and signal generation.

Characteristics of three citation datasets

Table content: <table><tr><td colspan="5">Dataset Vertices Edges Classes Features</td></tr><tr><td>Citeseer</td><td>3327</td><td>4732</td><td>6</td><td>3703</td></tr><tr><td>Cora</td><td>2708</td><td>5429</td><td>7</td><td>1433</td></tr><tr><td>Pubmed</td><td colspan="2">19717 44338</td><td>3</td><td>500</td></tr></table>

. On average, for Cora/Citeseer/Pubmed, the scattering transform takes 11.85s/4.36s/156.23s while training each epoch takes 13.9ms/13.4ms/55.1ms. In comparison, we note that the training in VGAE for Cora/Citeseer takes 80.0ms/108.2ms for each epoch, but there is no initial scattering step. Results for link prediction using common citation datasets. Only the results of SCAT and VGAE for Cora and Citeseer were done on our machine. The rest are fromKipf & Welling (2016). We remark that for VGAE,Kipf & Welling (2016) reported the following AUC and AP for Cora: 91.4 ± 0.01 and 92.6 ± 0.00 and the following ones for Citeseer: 90.8 ± 0.02 and 92.0 ± 0.00. ± 0.12 96.6 ± 0.11 97.5 ± 0.09 97.3 ± 0.06 97.3 ± 0.06 97.0 ± 0.03 VGAE 91.7 ± 0.28 93.1 ± 0.26 91.2 ± 0.08 91.5 ± 0.10 96.4 ± 0.00 96.5 ± 0.00 SC 84.6 ± 0.01 88.5 ± 0.00 80.5 ± 0.01 85.0 ± 0.01 84.2 ± 0.02 87.8 ± 0.01 DW 83.1 ± 0.01 85.0 ± 0.00 80.5 ± 0.02 83.6 ± 0.01 84.4 ± 0.00 84.1 ± 0.00

Table content: <table><tr><td>Dataset</td><td>Cora</td><td/><td colspan="2">Citeseer</td><td colspan="2">Pubmed</td></tr><tr><td/><td>AUC (%)</td><td>AP (%)</td><td>AUC (%)</td><td>AP (%)</td><td>AUC (%)</td><td>AP (%)</td></tr><tr><td>SCAT</td><td>97.0</td><td/><td/><td/><td/></tr></table>

3, the signals on each vertex just take five different values. For comparison, Appendix §6.1 shows generated graph-based images by a graph version of vanilla VAE and GAN. These results also indicate some problems with

Table content: <table/>

The settings ofSimonovsky & Komodakis (2018),De Cao & Kipf (2018) and SCAT are not the same.Simonovsky & Komodakis (2018) assumes nine atoms for each molecule and sets aside 10k samples for testing and 10k for validation.De Cao & Kipf (2018) consider molecules with no more than nine atoms and use padding if the number is less than nine. They also use the full dataset for training. We cannot compare these methods in our setting. We are also unable to test SCAT in the setting ofSimonovsky & Komodakis (2018) since their training set is unknown to us. We are able to test SCAT in the setting ofDe Cao &

Table content: <table/>

Graph generation comparison of SCAT and other algorithms using the QM9 dataset. Values are reported in percentages. The results of the other methods are taken from De Cao & Kipf (2018); Simonovsky & Komodakis (2018) since their codes are not publicly available. We remark that SCAT (conditioned) and SCAT (unconditioned) report results trained on 90k subset of data, while SCAT with padding report results trained on the complete data; all comparisons are according to 10k generated samples.

Table content: <table><tr><td>Algorithm</td><td colspan="3">Valid Unique Novel</td></tr><tr><td>CharacterVAE</td><td>10.3</td><td>67.5</td><td>90.0</td></tr><tr><td>GrammarVAE</td><td>60.2</td><td>9.3</td><td>80.9</td></tr><tr><td>GraphVAE</td><td>55.7</td><td>76.0</td><td>61.6</td></tr><tr><td>GraphVAE (imp)</td><td>56.2</td><td>42.0</td><td>75.8</td></tr><tr><td>GraphVAE (NoGM)</td><td>81.0</td><td>24.1</td><td>61.0</td></tr><tr><td>MolGAN</td><td>98.1</td><td>10.4</td><td>94.2</td></tr><tr><td>SCAT (conditioned)</td><td>98.5</td><td>24.8</td><td>99.0</td></tr><tr><td colspan="2">SCAT (unconditioned) 92.6</td><td>19.3</td><td>99.8</td></tr><tr><td>SCAT with padding</td><td>93.9</td><td>17.6</td><td>98.6</td></tr></table>

Peer review (iclr2019):
 The paper used the graph scattering network as the encoder, and MLP as the decoder to generate links/graph signals/graphs. Pros: 1. Clearly written. Easy to follow. 2. No need to train the encoder 3. Good results on link prediction tasks Cons: 1. Lack of novelty. It is a simple combination of existing encoders and decoders. For example, compared to VGAE, the only difference in the link prediction task is using a different encoder. Even if the performance is very good, it can only demonstrate the effectiveness of others’ encoder work and this paper’s correct selection of a good encoder. 2. Lack of insights. As a combination of existing works, if the paper can deeply explain the why this encoder is effective for the generation, it is also beneficial. But we also do not see this part. In particular, in the graph generation task, the more important component may be the decoder to regulate the validness of the generated graphs (e.g. “Constrained Generation of Semantically Valid Graphs via Regularizing Variational Autoencoders. In NIPS 2018” which used the similar decoder but adding strong regularizations in VAE). 3. Results on QM9 not good enough and lack of references. Some recent works (e.g. “Junction Tree Variational Autoencoder for Molecular Graph Generation, ICML 2018”) could already achieve 100% valid.