Given a set of graph statistics $S = (s_1 , s_2 , ..., s_n)$ (these statistics can include degree statistics, clustering coefficients, or motifs or graphlets), compute the each statistic $s_i$ for both the generated graphs and a test graph. From there, we can compute the distance between the statistics' distributions on the test graph and generated graph using a distributional measure, such as the total variation distance:

$d(s_{i,G_{test}}, s_{i,G_{gen}}) = \sup_{x \in \mathbb{R}} |s_{i,G_{test}}(x) - s_{i,G_{gen}}(x)|$

Finally, we can compute the average pairwise distributional distance between a set of generated graphs and graphs in a test set for each statistic $s_i \in S$

Formal Definition of Graph Generation Evaluation

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.

Carleton 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 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.

Learn Before

Related

Learn After