One important benefit of the GAN-based framework is that it removes the complication of specifying a node ordering in the loss computation. As long as the discriminator model is permutation invariant, the GAN approach does not require any node ordering to be specified.

However, GAN-based approaches to graph generation have so far received less attention and success than their variational counterparts. This is likely due to the difficulties involved in the minimax optimization that GAN-based approaches require, and investigating the limits of GAN-based graph generation is currently an open problem.

Benefits and limitations of the GAN approach

The basic Generative Adversarial Network (GAN) based approach to graph generation is similar to graph-level Variational Autoencoders (VAEs). For the generator, a simple multi-layer perceptron (MLP) can be employed to generate a matrix of edge probabilities given a seed vector $$z$$: $$\tilde{A}=\sigma(MLP(z))$$. Given this matrix, a discrete adjacency matrix $$\hat{A} \in Z^{|V| \times |V|}$$ is generated by sampling independent Bernoulli variables for each edge, where probabilities are given by the entries of $$\tilde{A}$$. For the discriminator, any Graph Neural Network (GNN) based graph classification model can be employed. The generator and discriminator models are then trained using standard tools for GAN optimization.

Basic GAN Approach to Graph Generation

- **Proposition 1**: The optimal discriminator $$D$$ for a given generator $$G$$ is:
  $$D_g^*(\bold x) = \frac{p_{data}(\bold x)}{p_{data}(\bold x) + p_g(\bold x)}$$
- **Theorem 1**: The global minimum of the virtual training criterion $$C(G)$$ is achieved if and only if $$p_g = p_{data}$$, having a value of $$-\log 4$$.
- **Proposition 2**: The generative distribution $$p_g$$ converges to $$p_{data}$$ if:
  1. $$G$$ and $$D$$ have enough capacity.
  2. At each step of the training algorithm, the discriminator is allowed to reach its optimum given $$G$$.
  3. $$p_g$$ is updated to improve the criterion:
     $$\mathbb{E}_{\bold x \sim p_{data}}[\log D_g^*(\bold x)] + \mathbb{E}_{\bold x \sim p_g}[\log(1 - D_g^*(\bold x))]$$

Propositions and Theorems of Generative Adversarial Networks (GANs)

Many recent generative models leverage alternative generative frameworks, and among them, Generative Adversarial Networks (GANs) are one of the most popular. The basic idea behind a general GAN-based generative model is to first define a trainable generator network $$g_{\theta}: R^{d}\rightarrow \chi$$. This generator network is trained to generate realistic data samples $$\tilde{x} \in \chi$$ by taking a random seed $$z \in R^{d}$$ as input. At the same time, a discriminator network $$d_{\phi}: \chi \rightarrow [0,1]$$ is defined. The discriminator's goal is to distinguish between real data samples $$x \in \chi$$ and samples generated by the generator $$\tilde{x} \in \chi$$.

University of Michigan - Ann Arbor

Google

A generative adversarial network (GAN) is a class of machine learning framework where two neural networks, a generative model and a discriminant model, contest against each other in a "game" (in the form of a zero-sum game, where one agent's gain is another agent's loss). Given a training set, this technique learns to generate new data with the same statistics as the training set. 

The core idea of a GAN is based on the "indirect" training through the discriminator, which itself is also being updated dynamically. This basically means that the generator is not trained to minimize the distance to a specific image, but rather to fool the discriminator and the discriminator is rewarded every time it correctly deduces if a sample is from the model distribution or the data distribution. This enables the model to learn in an unsupervised manner.

Generative adversarial network(GAN)

Hamilton, W.L. Graph Representation Learning. *Synthesis Lectures on Artificial Intelligence and Machine Learning*. 2020, 14(3), 1–159. https://doi.org/10.2200/S01045ED1V01Y202009AIM046

Graph Representation Learning by William Hamilton

Goodfellow, Ian; Pouget-Abadie, Jean; Mirza, Mehdi; Xu, Bing; Warde-Farley, David; Ozair, Sherjil; Courville, Aaron; Bengio, Yoshua (2014). Generative Adversarial Networks (PDF). Proceedings of the International Conference on Neural Information Processing Systems (NIPS 2014). pp. 2672–2680.

Generative Adversarial Networks

A known dataset serves as the initial training data for the discriminator, presenting it with samples from the training dataset, until it achieves acceptable accuracy. Typically the generator is seeded with randomized input that is sampled from a predefined latent space (e.g. a multivariate normal distribution). Thereafter, candidates synthesized by the generator are evaluated by the discriminator. Independent backpropagation procedures are applied to both networks so that the generator produces better images, while the discriminator becomes more skilled at flagging synthetic images. The generator is typically a deconvolutional neural network, and the discriminator is a convolutional neural network.

Method of GAN

GAN applications have increased rapidly:

1. Fashion, art and advertising.

2. Science.

3. Video games.

4. Miscellaneous applications.

Applications of GAN

1. Deep Convolutional GANs (DCGANs)
2. Conditional GANs (cGANs)
3. StackGAN
4. InfoGANs
5. Wasserstein GANs(WGAN)

Different types of GANs

Auto-Regressive Networks are a kind of directed probability graph. The conditional probability is described using neural networks and the chain rule. The key definition of an Auto-Regressive Network is: $$p(x) =\prod_{i=1}^{n_i} p(x_i|x_{i-1},...,x_1)$$

Auto-Regressive Network

Restricted Boltzmann Machines (RBM), Deep Boltzmann Machines (DBM), and variants:
- Undirected graphical models with latent variables instead of directed

Deep Belief Networks (DBN):
- Single undirected layer and multiple directed layers

Score Matching and Noise-contrastive Estimation (NCE):
- Don't approximate or bound log-likelihood

Generative Stochastic Network (GSN):
- Don’t involve defining a probability distribution explicitly; instead trains a generative machine to draw samples from the desired distribution


Related Work to GANs

When tested against three different generative models using the same starting dataset and evaluated using log-likelihood estimates, adversarial nets produce acceptable results to stay competitive with existing models. 

Below are some of the challenges/benefits that some generative models encounter while testing:

GANs tested performance

Legend:
- $\bold{z}$: Noise distribution (mapped to $\bold{x}$).
- $\bold x$: Data distribution.
- **Blue**: Discriminative Distribution.
- **Green**: Generative Distribution.
- **Black**: Data Distribution.

The discriminative distribution is repeatedly updated to minimize the difference between our generative distribution and true data distribution (shown in figure left to right) so the generative distribution becomes a more accurate approximation of what the data shows.

Illustration of GAN's

Updating Algorithm for GAN's

### Advantages
- **No need for Markov chains**: GANs do not require Markov chains for sampling or training.
- **Sharp distributions**: They handle sharp, degenerate distributions well compared to Markov chain methods.
- **Simple training**: Only backpropagation is used to obtain gradients.
- **No inference**: No statistical inference is needed during learning.

### Disadvantages
- **No explicit density**: There is no explicit representation of the generative distribution $$p_g(x)$$.
- **Training imbalance**: It is necessary to synchronize the models carefully to avoid over-training the generative model without updating the discriminative model.

Learn Before

Related

Learn After