A Systematic Survey on Deep Generative Models for Graph Generation

Graphs are important data representations for describing objects and their relationships, which appear in a wide diversity of real-world scenarios. As one of a critical problem in this area, graph generation considers learning the distributions of given graphs and generating more novel graphs. Owing to their wide range of applications, generative models for graphs, which have a rich history, however, are traditionally hand-crafted and only capable of modeling a few statistical properties of graphs. Recent advances in deep generative models for graph generation is an important step towards improving the fidelity of generated graphs and paves the way for new kinds of applications. This article provides an extensive overview of the literature in the field of deep generative models for graph generation. First, the formal definition of deep generative models for the graph generation and the preliminary knowledge are provided. Second, taxonomies of deep generative models for both unconditional and conditional graph generation are proposed respectively; the existing works of each are compared and analyzed. After that, an overview of the evaluation metrics in this specific domain is provided. Finally, the applications that deep graph generation enables are summarized and five promising future research directions are highlighted.

图是描述对象及其关系的重要数据表示形式，在各种各样的现实场景中都会出现。作为该领域的一个关键问题，图生成考虑学习给定图的分布并生成更多新的图。由于其广泛的应用，图的生成模型有着丰富的历史，然而，传统上是手工构建的，并且只能对图的少数统计特性进行建模。用于图生成的深度生成模型的最新进展是提高生成图的逼真度的重要一步，并为新型应用铺平了道路。本文对用于图生成的深度生成模型领域的文献进行了广泛综述。首先，给出了用于图生成的深度生成模型的正式定义和预备知识。其次，分别提出了用于无条件和有条件图生成的深度生成模型的分类法；对每一类的现有工作进行了比较和分析。之后，提供了这一特定领域的评估指标综述。最后，总结了深度图生成所支持的应用，并强调了五个有前景的未来研究方向。