Generating Graphs with Deep Learning and Graph Theory Open Access

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

Rights statement

• Permission granted by the author to include this thesis or dissertation in this repository. All rights reserved by the author. Please contact the author for information regarding the reproduction and use of this thesis or dissertation.

School	Laney Graduate School
Department	Mathematics
Degree	Ph.D.
Submission	Dissertation
Language	English
Research Field	Mathematics Computer Science
Keyword	generative model graph theory deep learning
Committee Chair / Thesis Advisor	Yuanzhe Xi, Emory University
Committee Members	Lars Ruthotto, Emory University Hao Huang, Emory University

Last modified

Primary PDF

Thumbnail	Title	Date Uploaded	Actions
	Generating Graphs with Deep Learning and Graph Theory ()	2022-03-26 16:03:11 -0400	Press to Select an action Download

Supplemental Files

Thumbnail	Title	Date Uploaded	Actions