VAEs model aims to train a probabilistic decoder model pθ(A|Z), from which we can sample realistic graphs (i.e., adjacency matrices) Aˆ ∼ pθ(A|Z) by conditioning on a latent variable Z. In a probabilistic sense, we aim to learn a conditional distribution over adjacency matrices (with the distribution being conditioned on some latent variable).

Variational Autoencoder Approaches (VAEs)

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

Basic models will adapt three of the most popular approaches to building general deep generative models: variational autoencoders (VAEs), generative adversarial networks (GANs), and autoregressive models.

Hamilton College

Deep generative models aim to design models that can observe a set of graphs {G1, ..., Gn} and learn to generate graphs with similar characteristics as this training set. These approaches avoid hand-coding particular properties—such as community structure or degree distributions.

Deep Generative Models

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

A key limitation of those traditional approaches is that they rely on a fixed, handcrafted generation process. In short, the traditional approaches can generate graphs, but they lack the ability to learn a generative model from data.

Limitations of Traditional Graph Generation Approaches

Basic Deep Generative Models for Graphs.

When evaluating graph generation, the current practice is to analyze different statistics of the generated graphs, and to compare the distribution of those statistics for the generated graphs to the distribution of a test graph.

Learn Before

Related

Learn After