Source: Guizhi
[ New Zhiyuan Introduction] This article provides an extensive overview of the literature in the field of deep generation models used for graph generation.
https://www.zhuanzhi.ai/paper/a904f0aa0762e65e1dd0b8b464df7168
Figures are important data representations that describe objects and their relationships, and they appear in various real scenarios. Graph generation is one of the key issues in this field, and it considers learning the distribution of a given graph to generate more new graphs. However, due to its wide application, generative models of graphs with rich history have traditionally been hand-made and can only model some of the statistical properties of graphs.
Recent advances in deep generative models for graph generation are an important step in improving the fidelity of generated graphs and paving the way for new types of applications. This paper provides an extensive overview of the literature in the field of deep generative models used in graph generation. First, the formal definition and preliminary knowledge of the deep generation model for graph generation are given; second, the classification of the deep generation models used for unconditional and conditional graph generation is proposed respectively; and the respective existing work is compared and analyzed. After this, the evaluation metrics in this specific area will be outlined. Finally, the application of depth map generation is summarized and five research directions with development prospects are pointed out.
Introduction
Figures are everywhere in the real world, representing objects and their relationships, such as social networks, citation networks, biological networks, transportation networks, etc. As we all know, the graph also has a complex structure, which contains rich underlying values [1]. People have made great efforts in this regard, resulting in rich relevant literature and methods for dealing with various graph problems.
These work can be divided into two categories: 1) predict and analyze the patterns of a given graph. 2) Learn the distribution of a given graph and generate more novel graphs. The first type covers many research areas, including node classification, graph classification, and link prediction. A lot of work has been done in this field over the past few decades. Compared with the first type of problem, the second type of problem is related to the graph generation problem, which is also the focus of this article.
graph generation includes the process of modeling and generating real-world graphs. It has applications in several fields, such as understanding interaction dynamics in social networks [2], [3], [4], anomaly detection [5], protein structure modeling [6], [7], source code generation and translation [8], [9], semantic analysis [10]. Due to its wide application, the development of graph generative models has a rich history, resulting in famous models such as random graphs, small world models, random block models and Bayesian network models, which generate graphs based on prior structural hypothesis [11]. These graph generation models [12], [13], [14] are designed to model preselected graph families such as random graphs [15], small world networks [16], and scale-free graphs [12]. However, due to its simplicity and hand-crafted nature, these random graph models often have limited modeling capabilities for complex dependencies and can only model some of the statistical properties of the graph.
These methods are usually well suited for properties tailored to predefined principles, but are usually not well suited for other properties. For example, the contact network model can fit influenza popularity, but cannot fit dynamic functional connections. However, in many fields, the nature and principles of network generation are largely unknown, such as those that explain mental illness in brain networks, cyber attacks and the spread of malware. For another example, Erdos-Renyi's graph does not have the typical heavy tail distribution in many real-world networks. Furthermore, the use of prior hypotheses limits the exploration of more applications of these traditional techniques in larger fields where the prior knowledge of the graph is always unavailable.
Taking into account the limitations of traditional graph generation techniques, a key open challenge is to develop methods that can directly learn generative models from observed graph sets, which is an important step in improving the fidelity of generated graphs. It paves the way for new types of applications such as discovering new drugs [17], [18], and protein structural modeling [19], [20], [21].Recent advances in deep generative models, such as Variational Autoencoder (VAE) [22] and Generative Adversarial Networks (GAN) [23], have been proposed for generating graphs that formalize promising areas of deep generative models for generating graphs, which are the focus of this review.
has carried out various advanced work in depth map generation, from one-time graph generation to sequential graph generation process, adapting to various deep generation learning strategies. These approaches are designed to address one or more of the above challenges through work in different fields, including machine learning, bioinformatics, artificial intelligence , human health and social network mining. However, methods developed in different research fields often use different vocabulary to solve problems from different perspectives.
In addition, standard and comprehensive evaluation procedures are lacking to verify the deep generation model of the developed graph. To this end, this paper systematically reviews the deep generation model used for graph generation. The purpose is to help interdisciplinary researchers choose the right technology to solve the problems in their application fields. More importantly, they help graph generation researchers understand the basic principles of graph generation and identify open research opportunities in the field of depth graph generation. To our knowledge, this is the first comprehensive review of the deep generative model used for graph generation. Below, we summarize the main contributions of this review:
This paper proposes a deep generation model classification method for graph generation, which is classified according to problem settings and methods. The advantages and disadvantages and relationships between different subcategories are introduced. The depth generation model used for graph generation and the basic depth generation model are described, analyzed and compared in detail.
- We summarize and classify the results of existing evaluation procedures and indicators, benchmark datasets and corresponding graph generation tasks for the deep generation model.
- We introduce the existing application areas of graph depth generation models, as well as the potential benefits and opportunities they bring to these applications.
- We propose several open questions and promising future research directions in the field of deep generative models for graph generation.
Unconditional depth generation model used for graph generation
The purpose of unconditional depth map generation is to learn the distribution pmodel(G) through a set of observed real maps sampled from the real distribution p(G) by the depth generation model. According to the style of the generation process, we can divide these methods into two main branches: (1) sequential generation: generate nodes and edges in sequence; (2) sequential generation: build a probability graph model based on matrix representation, and generate all nodes and edges at once. These two methods of generating graphs have their own advantages and disadvantages. Sequential generation Although local decisions of the former generation are efficiently performed, there are difficulties in maintaining long-term dependencies. Therefore, some global properties of the graph (such as scaleless properties) are difficult to include. Furthermore, existing work on sequence generation is limited to predefined sequence order, leaving the role of permutation. One-time generation method can synchronize and refine the entire graph (i.e. nodes and edges) through multiple iterations to model the global properties of the graph. However, since the global relationship between nodes is required to collectively model, its time complexity is usually greater than O(N2), so most methods are difficult to scale to large graphs.
conditional depth generation model used for graph generation
conditional depth map generation goal is to learn the conditional distribution pmodel(G|y) based on the observed set of realistic graphs G and its corresponding auxiliary information (i.e. condition y). The auxiliary information can be category tags, semantic contexts, graphs from other distribution spaces, etc. In addition to the challenges in generating graphs, conditional generation needs to consider how to extract features from a given condition and integrate them into the generation of graphs.
Therefore, in order to systematically introduce the existing conditional depth map generation model, we mainly describe how these methods deal with conditions.Since conditions can be any form of auxiliary information, they are divided into three types, including graph, sequence and semantic context, as shown in the yellow part of the taxonomy tree in Figure 1
Reference:
https://mp.weixin.qq.com/s/aqIeqHoeJtRyh3B5dhhcDA
