Generating Graphs with Deep Learning and Graph Theory Public
Ji, Yuliang (Spring 2022)
Published
Abstract
Deep generative models attract lots of attention in recent years. With deep neural networks and specific designs, deep generative models can generate high-quality realistic data. In this thesis, I focus on combining the deep generative models with the traditional graph theory algorithms to reduce the dependence on the volume of the training data and also improve the quality of the generated graphs. In particular, I first propose a deep learning method to improve the Havel-Hakimi graph realization algorithm in order to generate doppelganger graphs from a single graph. Second, I present a few new architectures of normalizing flow models with improved performance and theoretical guarantees. Finally, I develop a permutation invariant method via leveraging graph theory and denoising diffusion models for generating molecular graphs.
Table of Contents
1 Introduction 1
1.1 History of Deep Neural Networks . . . . . . . . . . . . . . . . . . . . 1
1.2 Basic Structure of Deep Neural Networks . . . . . . . . . . . . . . . . 2
1.3 Training Process of Deep Neural Networks . . . . . . . . . . . . . . . 4
1.4 Deep Generative Model . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.4.1 Variational AutoEncoder . . . . . . . . . . . . . . . . . . . . . 6
1.4.2 Generative Adversarial Network . . . . . . . . . . . . . . . . . 7
1.4.3 Normalizing Flow . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.4.4 Denoising Diffusion Model . . . . . . . . . . . . . . . . . . . . 13
1.4.5 Comparison of Generative Models on a Simple 2D Dataset . . 15
1.5 Graph and Graph Neural Network . . . . . . . . . . . . . . . . . . . . 21
1.5.1 Graph . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
1.5.2 Graph Neural Network . . . . . . . . . . . . . . . . . . . . . . 21
1.6 Summary of Contributions . . . . . . . . . . . . . . . . . . . . . . . . 23
2 Generating a doppelganger graph from a single graph 25
2.1 Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
2.2 Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
2.3 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
2.4 Generating a Doppelganger Graph: Resembling but Distinct . . . . . 28
2.4.1 Graph Realization Algorithm: Havel–Hakimi . . . . . . . . . . 28
2.4.2 Improved Havel–Hakimi . . . . . . . . . . . . . . . . . . . . . 32
2.4.3 Link Predictor for Improved HH . . . . . . . . . . . . . . . . . 34
2.4.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
2.4.5 Theoretical Analysis . . . . . . . . . . . . . . . . . . . . . . . 36
2.5 Numerical Experiments . . . . . . . . . . . . . . . . . . . . . . . . . . 41
2.5.1 Experiment Setting . . . . . . . . . . . . . . . . . . . . . . . . 41
2.5.2 Comparison of Baseline Models and the Proposed Method . . 45
2.5.3 Visualization of Generated Graphs . . . . . . . . . . . . . . . 48
2.5.4 Link Prediction and GAN Training Results . . . . . . . . . . . 49
2.6 Downstream Task Example: Node Classification . . . . . . . . . . . . 51
2.6.1 Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
2.6.2 Experiment Setting . . . . . . . . . . . . . . . . . . . . . . . . 51
2.6.3 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
3 AUTM Normalizing Flows 53
3.1 Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
3.1.1 Coupling Flows . . . . . . . . . . . . . . . . . . . . . . . . . . 55
3.1.2 Autoregressive Flows . . . . . . . . . . . . . . . . . . . . . . . 55
3.1.3 Continuous Flows . . . . . . . . . . . . . . . . . . . . . . . . . 56
3.1.4 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
3.2 Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
3.3 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
3.4 Atomic Unrestricted Time Machine (AUTM) flows . . . . . . . . . . 60
3.4.1 AUTM Flow Layer . . . . . . . . . . . . . . . . . . . . . . . . 60
3.4.2 Theoretical Analysis . . . . . . . . . . . . . . . . . . . . . . . 65
3.5 Numerical Experiments . . . . . . . . . . . . . . . . . . . . . . . . . . 72
3.5.1 Density Estimation . . . . . . . . . . . . . . . . . . . . . . . . 73
3.5.2 Experiments on Image Dataset . . . . . . . . . . . . . . . . . 75
3.5.3 Numerical Inversion of AUTM . . . . . . . . . . . . . . . . . . 77
3.5.4 Reconstruction on Image Dataset . . . . . . . . . . . . . . . . 78
3.5.5 Comparison of FFJORD and AUTM . . . . . . . . . . . . . . 79
3.6 For Graph Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
4 Denoising Diffusion Models for Generating Graphs 82
4.1 Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
4.2 Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
4.3 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
4.4 Graph DDPM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
4.4.1 Graph Auto-Encoder . . . . . . . . . . . . . . . . . . . . . . . 84
4.4.2 DDPM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
4.4.3 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
4.4.4 Theoretical Analysis . . . . . . . . . . . . . . . . . . . . . . . 86
4.5 Numerical Experiments . . . . . . . . . . . . . . . . . . . . . . . . . . 87
4.5.1 Experiment Setting . . . . . . . . . . . . . . . . . . . . . . . . 87
4.5.2 Comparison of Baseline Models and Our Method . . . . . . . 89
4.5.3 Visualization of Generated Graphs . . . . . . . . . . . . . . . 89
4.5.4 Graph Auto-Encoder Training Results . . . . . . . . . . . . . 91
4.5.5 DDPM Training Results . . . . . . . . . . . . . . . . . . . . . 92
5 Summary and Future Work 93
Bibliography 95
About this Dissertation
School | |
---|---|
Department | |
Degree | |
Submission | |
Language |
|
Research Field | |
Mot-clé | |
Committee Chair / Thesis Advisor | |
Committee Members |
Primary PDF
Thumbnail | Title | Date Uploaded | Actions |
---|---|---|---|
|
Generating Graphs with Deep Learning and Graph Theory () | 2022-03-26 16:03:11 -0400 |
|
Supplemental Files
Thumbnail | Title | Date Uploaded | Actions |
---|