# Generating the Graph Gestalt: Kernel-Regularized Graph Representation
Learning

Kiarash Zahirnia, Ankita Sakhuja, Oliver Schulte, Parmis Nadaf, Ke Li, Xia Hu

###### Abstract

Recent work on graph generative models has made remarkable progress towards
generating increasingly realistic graphs, as measured by global graph features
such as degree distribution, density, and clustering coefficients. Deep
generative models have also made significant advances through better modelling
of the local correlations in the graph topology, which have been very useful
for predicting unobserved graph components, such as the existence of a link or
the class of a node, from nearby observed graph components. A complete
scientific understanding of graph data should address both global and local
structure. In this paper, we propose a joint model for both as complementary
objectives in a graph VAE framework. Global structure is captured by
incorporating graph kernels in a probabilistic model whose loss function is
closely related to the maximum mean discrepancy (MMD) between the global
structures of the reconstructed and the input graphs. The ELBO objective
derived from the model regularizes a standard local link reconstruction term
with an MMD term. Our experiments demonstrate a significant improvement in the
realism of the generated graph structures, typically by 1-2 orders of
magnitude of graph structure metrics, compared to leading graph VAE and GAN
models. Local link reconstruction improves as well in many cases.

##  1 Introduction

Many important datasets contain relational information about entities and
their links that can be represented as a graph. Deep generative learning on
graphs has become a popular research topic Hamilton [2020], with many
applications including molecule design Samanta et al. [2020], matrix
completion for inference, and recommendation Do et al. [2019]. Computational
methods for analysing graph data have developed two distinct traditions
Chakrabarti and Faloutsos [2012], that emphasize (i) local correlations in the
graph topology Kipf and Welling [2016], Pan et al. [2018], Grover et al.
[2019] (ii) global aspects of the graph structure. The paper develops a new
approach to jointly modelling both local correlations and global graph
structure in a deep generative framework.

Typical graph-based local predictions are predicting the existence of a link
between two nodes from node attributes and other links, and predicting a class
attribute of a node Hamilton [2020]. For example, in a social network, a
typical task is to recommend potential new friends based on existing
friendship links. An example of node classification is to predict the
political affiliation of a user given their friendships and affiliations of
their friends. Deep graph representation learning has achieved excellent
performance on local prediction tasks by computing embeddings, or latent
features, of nodes or edges Kipf and Welling [2016], Pan et al. [2018], Grover
et al. [2019].

Structural generative graph models, often drawing on network analysis
Chakrabarti and Faloutsos [2012], aim to capture global graph features You et
al. [2018], Li et al. [2018], Samanta et al. [2020], such as degree
distribution, density, and clustering coefficients. We refer to these
properties collectively as the _graph gestalt_ ; gestalt is a term from
psychology that denotes the overall organization of a set of objects that is
more than just the set of its parts. Figure 1 illustrates the concept. For
another example, in a grid graph, small cliques of edges are not distinctive
in themselves, but collectively form a highly regular pattern.

(a) Original Graph

(b) Generated Graph 1

(c) Generated Graph 2

Figure 1: The difference between local and global structure. The two right
graphs (1(b)), (1(c)) score the same in terms of number of edges reconstructed
from the left graph (1(a)). However the middle graph (1(b)), is structurally
more similar to (1(a)), containing the same number of connected components.

You et al. [2018] have shown empirically that local representation learning
provides a poor model of graph gestalt: graphs generated from local embeddings
have an unrealistic global structure. The reason for this is that link
reconstruction is inherently local: the objective function is based on
element-wise local comparisons between the observed and the predicted
adjacency matrix. In a graph VAE (GVAE), the local link reconstruction
probability is the product of link probabilities that are conditionally
independent given node embeddings. While conditional independence supports
easy and stable optimization, it measures only local data fit and not the
global graph properties. Moreover, the link reconstruction probability weights
all edges equally, but as Figure 1 illustrates, not all edges in the graphs
are equally important Faisal et al. [2015]. A complete model of graph data
should capture both global and local properties, which can reinforce each
other in a joint model to improve both. Modelling global structure supports
inductive graph learning You et al. [2018] when the graph gestalt is a stable
high-level pattern that generalizes from subgraphs to a larger graph.

Approach. We utilize a joint probabilistic model over both individual graph
adjacencies and global graph features. Graph features are represented by user-
specified graph kernels. The ELBO objective of the model regularizes a
standard local adjacency reconstruction term with a maximum mean distance
(MMD) term derived from the graph kernels; we refer to it as the kernel-
regularized ELBO . Kernel regularization connects graph representation
learning with the rich body of work on graph kernels. We show that the kernel-
regularized ELBO has two complementary interpretations: i) As an adjacency
reconstruction objective with a graph moment matching constraint. ii) As a
joint reconstruction objective over both adjacencies and graph features.

Evaluation. Our evaluation compares training GVAEs with and without kernel
regularization. We keep architecture, datasets, and evaluation metrics the
same and change only the objective function. Our comparison methods include
three GVAEs, two state-of-the-art and one benchmark vanilla GVAE. We also
benchmark against a SOTA graph GAN and auto-regressive architectures designed
for generating realistic graphs You et al. [2018], Liao et al. [2019]. The
input graph kernels are based on node degree and transition probabilities. For
GVAEs, kernel-regularization improves the reconstruction of graph structure
metrics by orders of magnitude. Compared to auto-regressive architectures for
generating realistic graphs, kernel-regularization generates graph structure
of competitive quality, and scales much better to larger graphs. We also
provide evidence that matching input graph structure often has the effect of a
co-training objective for local graph modelling, improving local link
reconstruction, and increasing test predictive accuracy for node
classification.

Contributions. Our contributions can be summarized as follows.

  * •

A new joint probabilistic model over both individual graph adjacencies and
global graph features.

  * •

Deriving a kernel-regularized ELBO as a new objective function for training
graph variational auto-encoders.

  * •

Differentiable extensions of previous graph kernels to so they can be applied
to reconstructed probabilistic adjacency matrices.

##  2 Related Work

We briefly discuss the relationship to the most relevant work.

Graph Neural Networks. This paper investigates several deep generative graph
models, including those based on GANs, VAEs, and auto-regressive models.
Overviews can be found in Zhou et al. [2020], Hamilton [2020]. Graph GANs De
Cao and Kipf [2018] and VAEs Kipf and Welling [2016], Grover et al. [2019],
Mehta et al. [2019] use scalable edge-parallel generation based on conditional
independence of edges. On the other hand, auto-regressive architectures Liao
et al. [2019], You et al. [2018] generate edges sequentially, which allows
them to capture complex dependencies between a new edge and edges already
generated. They typically require a canonical node ordering for generating
edges in order. Our contribution is not a new model but a new objective
function for training generative graph models. While our exposition focuses on
kernel-regularization for graph VAEs, in principle it could be used with other
architectures as well.

Graph Moment Matching. As we show in Section 3.2, kernel-regularization can be
interpreted as a graph moment matching condition, that rewards a model for
matching observed graph statistics (e.g. node distribution). Graph moment
matching has been previously studied in network statistics; see [Orbanz and
Roy, 2014, Sec.7]. This work has focused on theoretical properties of graph
moment estimators with increasing graph size. Our goal is to describe and
evaluate a practical computational architecture within a deep encoder-decoder
framework.

Graph Sparsity. A well-known issue with edge-parallel models is that they
generate unrealistically dense graphs [Orbanz and Roy, 2014, Sec.7], which has
motivated graph moment matching. Kipf and Welling [2016] suggest increasing
the weight of existing edges to reduce density, but this reduces overall graph
reconstruction quality Qiao et al. [2020]. Our experiments show that kernel
regularization offers a principled approach for reducing edge-parallel
density.

Constrained ELBO Maximization. Ma et al. [2018] describe general constrained
ELBO maximization using quadratic constraints comparable to our MMD term. They
require the constraint to hold for almost all latent variable instances
$\boldsymbol{z}$ with measure 1 in the prior distribution $p(\boldsymbol{Z})$,
whereas our formulation requires the constraint to hold for almost all latent
variables instances in the posterior distribution
$q_{\varphi}(\boldsymbol{Z}|\boldsymbol{X},\boldsymbol{A})$. This difference
arises because the goal of Ma et al. is to capture a prior constraint valid
for all graphs in a domain, whereas our goal is to reconstruct a specific
input graph.

Graph Kernels. We define differentiable kernels for two graph aspects: the
node degree distribution and transition probabilities from random walks. For
node degrees, we adapt the vector label histogram (VLH) graph kernel
Nikolentzos et al. [2019], which guarantees permutation invariance (i.e., the
degree histogram does not depend on the ordering of the nodes). The main
difference is that VLH was originally defined for discrete node labels whereas
we apply it with degrees as continuous node features. Utilizing multi-step
transition probability matrices as a basis for a graph kernel was explored by
Zhang et al. [2018]. The difference is that we use a simpler kernel to compare
transition probability matrices but utilize more information, especially the
off-diagonal entries.

##  3 Data Model and ELBO Objective

An attributed graph is a pair $G=(V,E)$ comprising a finite set of nodes and
edges where each node is assigned an $d$-dimensional attribute
$\boldsymbol{x}_{i}$ with $d>0$. An attributed graph can be represented by an
$N\times N$ adjacency matrix $\boldsymbol{A}$ with $\\{0,1\\}$ Boolean
entries, together with an $N\times d$ node feature matrix $\boldsymbol{X}$.
Following Ma et al. [2018], we view the observed adjacency matrix as a sample
from an underlying probabilistic adjacency matrix $\tilde{\boldsymbol{A}}$
with $\tilde{\boldsymbol{A}}_{i,j}\in[0,1]$. The sampling distribution for
independent edges is given by

$P(\boldsymbol{A}|\tilde{\boldsymbol{A}})=\prod_{i=1}^{N}\prod_{j=1}^{N}\tilde{\boldsymbol{A}}_{i,j}^{\boldsymbol{A}_{i,j}}(1-\tilde{\boldsymbol{A}}_{i,j})^{1-\boldsymbol{A}_{i,j}}.$
(1)

A graph kernel $k(G,G^{\prime})$ measures the similarity of two (attributed)
graphs. For a given graph kernel $k$ and two graph sets
$\boldsymbol{G}=\\{G_{l}\\}_{l=1}^{S}$ and
$\boldsymbol{G^{\prime}}=\\{G^{\prime}_{l})\\}_{l=1}^{M}$ the maximum mean
distance is defined as $\mathit{MMD}^{2}_{k}$ as usual between two sets (see
You et al. [2018]). For the special case of comparing a single graph to
another ($S=M=1$), we write

$\mathit{D}^{2}_{k}(G,G^{\prime})\equiv\mathit{MMD}^{2}_{k}(\\{G\\},\\{G^{\prime}\\})=k(G_{l},G_{l})+k(G^{\prime}_{l},G^{\prime}_{l})-2k(G_{l},G^{\prime}_{l}).$

We also write $k(\boldsymbol{A},\boldsymbol{A}^{\prime})$ and
$\mathit{D}^{2}_{k}(\boldsymbol{A},\boldsymbol{A}^{\prime})$ if we wish to
emphasize that a graph kernel and MMD can be computed as a function of the
adjacencies only.

###  3.1 Kernel-Regularized ELBO Objective

Figure 2 shows the standard generative graphical model for GVAEs Kipf and
Welling [2016], Grover et al. [2019].

Figure 2: Latent variable model for VAE. Observed evidence variables in gray.

We formulate a new variational objective function in a generic encoder-decoder
framework with the following properties.

  * •

The encoder deterministically maps an input graph representation
$(\boldsymbol{A},\boldsymbol{X})$ to a posterior latent distribution
$q_{\varphi}(\boldsymbol{Z}|\boldsymbol{X},\boldsymbol{A})$ where
$\boldsymbol{Z}_{N\times t}$ specifies a latent $t$-dimensional feature vector
for each node $i$. The encoder parameters to be optimized are denoted
$\varphi$.

  * •

The decoder deterministically maps a latent representation $\boldsymbol{z}$ to
a probabilistic graph $\tilde{\boldsymbol{A}}_{\boldsymbol{z}}$. The decoder
parameters to be optimized are denoted $\theta$.

  * •

A list of differentiable graph kernels $k_{1},\ldots,k_{m}$ where
$k_{u}(\boldsymbol{A},\boldsymbol{A}^{\prime})$ measures the similarity of two
graphs in terms of their adjacency matrices. Each kernel $k_{u}$ can be
applied to general weighted adjacency matrices, including probabilistic
adjacencies Vishwanathan et al. [2010].

Combining the mapping $\tilde{\boldsymbol{A}}_{\boldsymbol{z}}$ with the
sampling distribution Eq. (1) defines the (local) link reconstruction
probability denoted
$p_{\theta}(\boldsymbol{A}|\tilde{\boldsymbol{A}}_{\boldsymbol{z}})$. The
notation $L_{\textsc{elbo}}$ denotes the standard ELBO objective for a graph
VAE Kipf and Welling [2016] and $L_{\textsc{kelbo}}$ our new kernel ELBO
objective that adds an MMD term to the link reconstruction probability.

$\displaystyle L_{\textsc{kelbo}}(\varphi,\theta,\boldsymbol{\lambda})$
$\displaystyle\equiv$ $\displaystyle E_{\boldsymbol{z}\sim
q_{\varphi}(\boldsymbol{Z}|\boldsymbol{X},\boldsymbol{A})}\big{[}\ln
p_{\theta}(\boldsymbol{A}|\tilde{\boldsymbol{A}}_{\boldsymbol{z}})-\sum_{u=1}^{m}\boldsymbol{\lambda}_{u}\mathit{D}^{2}_{k_{u}}(\boldsymbol{A},\tilde{\boldsymbol{A}}_{\boldsymbol{z}})\big{]}-KL\big{(}q_{\varphi}(\boldsymbol{Z}|\boldsymbol{X},\boldsymbol{A})||p(\boldsymbol{Z})\big{)}$
(2)

where $p(\boldsymbol{Z})$ is a prior distribution over the latent space. We
treat the kernel weights $\boldsymbol{\lambda}$ as a hyperparameter and
maximize $L_{\textsc{kelbo}}$ with respect to the encoder-decoder parameters
$\varphi,\theta$. The next subsection shows that the kernel objective is a
lower bound on the graph log-likelihood for two complementary generative
models.

###  3.2 Interpretation of the Kernel ELBO

For notational simplicity, we focus on the case of one graph kernel $k$. By
Mercer’s theorem, a kernel defines implicit feature map $\phi$ such that
$k(\boldsymbol{A},\boldsymbol{A}^{\prime})=\phi(\boldsymbol{A})\bullet\phi(\boldsymbol{A}^{\prime})$.
We can think of $\phi$ as extracting a structural feature vector of a graph.
The $\mathit{D}^{2}_{k}$ term represents the Euclidean distance between the
input graph feature vector and the reconstruction feature vector:
$\mathit{D}^{2}_{k}(\boldsymbol{A},\boldsymbol{A}^{\prime})=||\phi(\boldsymbol{A})-\phi(\boldsymbol{A}^{\prime})||^{2}.$

The $\mathit{D}^{2}_{k}$ term therefore encourages the model to match the
observed structural features. We next show that objective (2) is a lower bound
on the data log-likelihood under two probabilistic models: 1) adding a feature
matching constraint to the standard graph VAE ELBO . 2) A data augmentation
model that defines a joint reconstruction probability for both observed
adjacencies and graph features.

#### Feature Matching Constraint

We consider maximizing the standard graph VAE ELBO Kipf and Welling [2016]
with a feature matching constraint: Taking the expectation with respect to the
posterior, we seek to maximize the reconstruction log-probability
$p(\boldsymbol{A}|\tilde{\boldsymbol{A}}_{\boldsymbol{z}})$ subject to 0
expected MMD:

$\operatorname*{arg\,max}_{\theta,\varphi}E_{\boldsymbol{z}\sim
q_{\varphi}(\boldsymbol{Z}|\boldsymbol{X},\boldsymbol{A})}\big{[}\ln
p_{\theta}(\boldsymbol{A}|\tilde{\boldsymbol{A}}_{\boldsymbol{z}})]-KL\big{(}q_{\varphi}(\boldsymbol{Z}|\boldsymbol{X},\boldsymbol{A})||p(\boldsymbol{Z})\big{)}\mbox{
s.t. }0=E_{\boldsymbol{z}\sim
q_{\varphi}(\boldsymbol{Z}|\boldsymbol{X},\boldsymbol{A})}\big{[}\mathit{D}^{2}_{k_{u}}(\boldsymbol{A},\tilde{\boldsymbol{A}}_{\boldsymbol{z}})]$
(3)

The constraint forces the expected reconstructed graph feature vector to match
the input graph features.

###### Observation 1

The Lagrangian of the constrained optimization problem (3) is equivalent to
the kernel ELBO (2).

Proof. The Lagrangian function is

$E_{\boldsymbol{z}\sim
q(\boldsymbol{Z}|\boldsymbol{X},\boldsymbol{A})}\big{[}\ln
p(\boldsymbol{A}|\tilde{\boldsymbol{A}}_{\boldsymbol{z}})]-KL\big{(}q_{\varphi}(\boldsymbol{Z}|\boldsymbol{X},\boldsymbol{A})||p(\boldsymbol{Z})\big{)}-\boldsymbol{\lambda}E_{\boldsymbol{z}\sim
q(\boldsymbol{Z}|\boldsymbol{X},\boldsymbol{A})}\big{[}\mathit{D}^{2}_{k_{u}}(\boldsymbol{A},\tilde{\boldsymbol{A}}_{\boldsymbol{z}})].$

Since both expectations are over the same posterior, we can combine them into
a single expectation, which yields to Equation (2).

#### Data Augmentation

We can view the graph features $\phi(\boldsymbol{A})$ as part of the observed
data, in addition to $\boldsymbol{A}$ and $\boldsymbol{X}$, and adopt a
product joint reconstruction model:

$\displaystyle p(\boldsymbol{A}|\boldsymbol{z})\propto
p(\boldsymbol{A}|\tilde{\boldsymbol{A}}_{\boldsymbol{z}})\cdot
p(\boldsymbol{\phi}(\boldsymbol{A})|\boldsymbol{z}))$ (4)

Suppose that the implicit kernel feature space has finite dimension $l$. Then
as usual with VAEs, we use an isotropic $l$-dimensional Gaussian
reconstruction model centered on the deterministic input reconstruction:

$p(\phi(\boldsymbol{A})|\boldsymbol{z})=N(\phi(\boldsymbol{A})|\phi(\tilde{\boldsymbol{A}}_{\boldsymbol{z}}),\frac{1}{2\lambda}I)\mbox{
with variance }\lambda\geq 0$ (5)

The kernel ELBO is a lower bound on the graph log-likelihood in the joint
reconstruction model, up to constant terms independent of the VAE parameters.

###### Proposition 1

Assume that the reconstruction probability $p(\boldsymbol{A}|\boldsymbol{z})$
is defined by Equations (4) and (5). Then

$\ln{P(\boldsymbol{A})}=\ln{\int_{\boldsymbol{z}}p(\boldsymbol{A}|\boldsymbol{z})p(\boldsymbol{z})d\boldsymbol{z}}\geq
L_{\textsc{kelbo}}(\varphi,\theta)+\frac{l}{2}\ln{2\lambda}-\frac{l}{2}\ln{2\pi}.$

The lower bound (1) differs from the kernel ELBO (2) only by a term that is
independent of the model parameters. The proof is in the appendix.

##  4 Experimental Design: Comparison Methods

Our comparison methods include i) GVAE ii) a SOTA Graph GAN method iii) auto-
regressive graph generation methods.

###  4.1 Input Graph Kernels

The kernel ELBO (2) requires a user-specified input kernel. In our
experiments, we utilize simple kernels based on (soft) adjacency matrices that
are differentiable with respect to the matrix entries, and easy to interpret:
the degree distribution and the $s$-step transition probability matrices, for
$s=1,\ldots 5$.

#### Degree Distribution Kernel.

For a weighted undirected graph $\tilde{\boldsymbol{A}}$, the degree of node
$v_{i}$ is defined as $d(v_{i})=\sum_{j}\tilde{\boldsymbol{A}}_{ij}$. We adapt
the vector label histogram (VLH) Nikolentzos et al. [2019]. To form a degree
histogram of graph $\tilde{\boldsymbol{A}}$, we bin the soft degrees. Binning
creates a histogram comparable to the (hard) degree histogram. Adopted VLH is
based on a soft assignment of points to bins given bin centers and widths. We
choose the bin centers to be the possible (hard) node degrees $b=0,\ldots,N$.
All widths are uniformly set to 0.1 (based on experimentation). The soft
assignment is then given by $a(v_{i},b)=\max\\{0,1-0.1\cdot|d(v_{i})-b|\\}$.
Thus the membership of a node in a bin ranges from 0 to 1 and decreases with
the difference between the node’s expected degree and the bin center. The VLH
assigns to each bin the sum of nodes membership in the bin.

$\displaystyle\textbf{d}_{\tilde{\boldsymbol{A}}}(b)\equiv\sum_{i=1}^{N}a(v_{i},b)$
(6) $\displaystyle
k_{h}(\tilde{\boldsymbol{A}},\tilde{\boldsymbol{A}}^{\prime})=\textbf{d}_{\tilde{A}}\bullet\textbf{d}_{\tilde{A}^{\prime}}$

In a naive implementation, the computational cost of finding the
$\textbf{d}_{\tilde{\boldsymbol{A}}}(b)$ vector is $O(n^{2})\;$. This can be
improved using speed-up techniques for nearest neighbour methods.

#### S-Step transition probability kernel.

The $s$-step transition probability matrix of adjacency matrix
$\tilde{\boldsymbol{A}}$, is a $N\times N$ matrix such that
${P^{s}(\tilde{\boldsymbol{A}})}_{i,j}$ is the probability of a transition
from node $i$ to node $j$ in a random walk of $s$ steps, where the probability
of each transition is the normalized link probability. The transition matrix
$P^{s}(\tilde{\boldsymbol{A}})$ can be computed by

$P^{s}(\tilde{\boldsymbol{A}})=(D(\tilde{\boldsymbol{A}})^{-1}\tilde{\boldsymbol{A}})^{s}$

where the degree matrix $D(\tilde{\boldsymbol{A}})$ is a diagonal matrix whose
entries $D(\tilde{\boldsymbol{A}})_{ii}\equiv d(i)$ are the expected node
degrees defined by Equation (6). The transition probability matrix
$P^{s}(\boldsymbol{A})$ is generally dense and encodes the connectivity
information of the graph. An important difference to the adjacency matrix is
that whereas adding or removing an edge changes only one adjacency, it can and
often does result in a substantive change in many transition matrix elements.
The impact on the transition probabilities thus measures the importance of an
edge in the graph structure. To compare transition probabilities, we use an
expected likelihood kernel Jebara and Kondor [2003]

$\sum_{i=1}^{N}\sum_{j=1}^{N}P^{s}(\tilde{\boldsymbol{A}})_{ij}P^{s}(\tilde{\boldsymbol{A}}^{\prime})_{ij}.$
(7)

The computational cost of computing the transition probability matrix exactly
is $O(n^{3})$. Sampling the matrix entries can reduce the computational cost
Jebara and Kondor [2003].

#### Kernel Weights.

The kernel weights $\boldsymbol{\lambda}$ were set by a grid search to
maximize the kernel ELBO for the DGLFRM decoder. We used the same weights for
Graphite and FC. Our experiments show that these weights achieve good results
without tuning them specifically for these two methods. The detailed values
are given in the Appendix.

##  5 Graph Neural Network Comparison Methods

We examine the effect of kernel regularization on several GVAE architectures.
Our methodology is to keep the architecture the same as published and change
only the objective function for training. As the architectures are not new, we
describe them briefly and refer the reader to the appendix for details.

#### Edge-Parallel Methods

For the encoder as in previous work, all our GVAE methods utilize a multi-
layer Graph convolutional Network (GCN) for computing the parameters of the
variational posterior distribution. We assume isotropic Gaussian distributions
for the prior and posterior Kipf and Welling [2016].

For the decoder, we evaluate the following approaches (1) Graphite Grover et
al. [2019], which uses a simple dot product decoder after GCN-style iterated
message passing to transform the encoder output node representations
$\boldsymbol{Z}$ to final node representations
$\boldsymbol{\boldsymbol{Z}^{*}}$. (2) DGLFRM Mehta et al. [2019], which
applies a stochastic block model decoder. We combine the SBM decoder with the
Graphite technique of transforming the node representations $\boldsymbol{Z}$
to another set $\boldsymbol{Z^{*}}$. (3) FC, a fully connected neural network
$f(\boldsymbol{Z})=\tilde{\boldsymbol{A}}$ that directly maps the node
representation to a probabilistic adjacency matrix. We include the vanilla FC
decoder as a baseline because it avoids confounding the effect of kernel
regularization with the influence of a specific decoder architecture. (4)
MolGAN De Cao and Kipf [2018] is a SOTA method for that generates edges
independently based on a GAN architecture.

#### Auto-Regressive Methods.

We utilize two SOTA Auto-Regressive architectures. (1) GRAN. An Auto-
Regressive graph generative model that generates one block of nodes and
associated edges at a step with $O(N)$ decision steps Liao et al. [2019]. (2)
GraphRNN. An Auto-Regressive framework that generates the adjacency matrix
sequentially. Each step generates one entry or one column through an RNN with
$O(N^{2})$ decision steps. In all experiments we utilized Multivariate
Bernoulli version of the GraphRNN You et al. [2018].

All models are trained with backpropagation for 3,000 epochs, which is similar
to previous work You et al. [2018], Liao et al. [2019] and sufficient for
convergence in our datasets. For other hyperparameter settings we used those
given in the original papers. The appendix contains details on the settings.
We used the original papers’ public repository; hence no consent was needed to
curate this study.

##  6 Training/Test Data and Metrics Reported

Our design closely follows previous experiments on generating realistic graph
structures, especially You et al. [2018], Liao et al. [2019], in the datasets
and evaluation metrics used. None of the datasets used for this research study
contain any personally identifiable information or offensive content.
Following You et al. [2018], Liao et al. [2019], we utilize two sets of
synthetic graphs and one set of real graphs.

Grid

Includes 100 synthetic 2D graphs with $100\leq|V|<400$.

Lobster

Includes 100 synthetic trees with $10\leq|V|\leq 100$. Generated using the
code from You et al. [2018].

Protein

Consist of 918 real-world protein graphs with $100\leq|V|\leq 500$ Dobson and
Doig [2003].

Training/Test Split. We follow You et al. [2018] and use their code from a
public repository to generate synthetic graphs, and randomly split the graphs
sets into training graphs (80%), and $T$ testing graphs (20%), see Figure 3.
We used the same train and test graph sets for all models. After training a
graph VAE model, we generate $T$ new graphs from the model Kipf and Welling
[2016], Ma et al. [2018] independently of the training graphs.

Figure 3: Each dataset is split into train and test sets. The train set is
then given to the generative model, and the trained model generates new sample
graphs. The set of samples is then compared, to the test set using with
respect to global graph features.

Evaluation Metrics. We measure how close the generated graphs are to the test
graphs with respect to a set of structural graph features. For each feature,
this distance is measured by Maximum Mean Discrepancy (MMD) using a Gaussian
kernel exactly as in You et al. [2018]. We use the same three structure
metrics as You et al. [2018] and add graph sparsity.

Degree distribution:

The probability distribution of node degrees over the graph. This metric
compares the the hard adjacency matrices of test graphs and generated graphs.

Clustering coefficient distributions:

The probability distribution of the number of closed triplets111A triplet
consists of three nodes that are connected by either two (open triplet) or
three(closed triplet) undirected ties. to the total number of triplets.

Average orbit counts:

The number of occurrences of all orbits (motifs) with 4 nodes.

Sparsity:

The number of zero-valued elements divided by the total number of elements in
adjacency matrix representation of the graph.

##  7 Experimental Results

We evaluate the quality of generated graph structures, by visual inspection
and by structure metrics. We also compare graph generation speed.

###  7.1 Quality of Generated Structures

Qualitative Evaluation. Figure 4 provides a visual comparison of randomly
selected test graphs, whose structure is the same as that of the training
graphs, and generated graphs. More examples are provided in the Appendix.

(a) Test

(b) MolGAN

(c) Graphite

(d) FC

(e) DGLFRM

(f) DGLFRM-Kernel

Figure 4: Visualization of generated graphs from Grid and Lobster inputs,
first and second row respectively. The left-most column (4(a)) shows 1
randomly selected target graph from the test set of each dataset. Sample
graphs were generated independently of the target (from the prior) by each
method named. Each column shows the visually most similar sample graph.
DGLFRM-Kernel (4(f)) matches the target graph the best, and much better than
(4(e)) DGLFRM without kernel regularization.

Quantitative Evaluation. Table 1 shows the MMD for parallel-edge models (VAE
and GAN) models. The table shows a very large MMD improvement from kernel
regularization. For the previous GVAE methods, kernel regularization reduces
MMD by at least 1 order of magnitude on almost all datasets. The improvement
for FC is less pronounced because it has by far the largest number of decoder
parameters for fitting the training graphs. Generally the most improved metric
is sparsity. As Table 2 shows, the improvement stems from generating sparser
graphs that achieve realistic densities.

Lesion studies in the appendix investigate the effects of the kernels in more
detail. 1) The results of removing one kernel component at a time shows that
both kernel components (degree and transition probability kernels) reinforce
each other and contribute to matching the input graph gestalt. 2) Removing
both kernel components shows that kernel regularization improves the local
reconstruction quality: Matching global graph features works as a co-training
objective for local link reconstruction.

Table 1: The impact of kernel regularization on edge-parallel models for graph
generation. For the named graph structural feature, each column reports the
MMD between the test set graphs (left-most column in Figure 4) and the
generated graphs (see other columns in Figure 4).

Method | Grid | Lobster | Protein
---|---|---|---
Deg. | Clus. | Orbit | Sparsity | Deg. | Clus. | Orbit | Sparsity | Deg. | Clus. | Orbit | Sparsity
MolGAN De Cao and Kipf [2018] | $1.28$ | $1.45$ | $0.86$ | $2.01e^{-4}$ | $0.73$ | $1.50$ | $0.52$ | $3.21e^{-6}$ | $1.06$ | $0.67$ | $0.93$ | $1.65e^{-3}$
Graphite Grover et al. [2019] | $1.19$ | $1.52$ | $0.88$ | $1.32e^{-7}$ | $0.85$ | $1.37$ | $0.79$ | $2.58e^{-8}$ | $1.67$ | $1.24$ | $1.09$ | $1.78e^{-2}$
DGLFRM Mehta et al. [2019] | $1.21$ | $1.69$ | $0.95$ | $4.65e^{-8}$ | $1.17$ | $1.56$ | $0.91$ | $8.83e^{-9}$ | $0.80$ | $0.95$ | $0.80$ | $2.33e^{-6}$
FC | $0.66$ | $0.91$ | $0.47$ | $1.18e^{-9}$ | $0.61$ | $1.44$ | $0.18$ | $2.34e^{-7}$ | $0.87$ | $1.74$ | $0.81$ | $4.65^{-6}$
Graphite-Kernel | $0.48$ | $0.81$ | 0.02 | $2.45e^{-9}$ | $0.12$ | $\textbf{2e}^{\textbf{-3}}$ | $0.13$ | $\textbf{1.56e}^{\textbf{-9}}$ | $0.72$ | $0.29$ | $\textbf{2.2e}^{\textbf{-3}}$ | $0.45e^{-3}$
DGLFRM-Kernel | 0.21 | $0.26$ | $0.03$ | $\textbf{3.55e}^{\textbf{-11}}$ | $0.07$ | $0.24$ | $0.08$ | $3.25e^{-9}$ | $0.65$ | 0.08 | $0.74$ | $\textbf{1.73e}^{\textbf{-8}}$
FC-Kernel | $0.27$ | 0.15 | $0.11$ | $1.36e^{-9}$ | 0.06 | $0.38$ | 0.04 | $5.45e^{-8}$ | 0.32 | $1.32$ | $0.36$ | $3.2e^{-8}$

Method | Grid | Lobster | Protein
---|---|---|---
Test Set | $400.90$ | $44.45$ | $604.08$
MolGAN De Cao and Kipf [2018] | $859.12$ | $192.46$ | $21560.03$
Graphite Grover et al. [2019] | $796.38$ | $132.85$ | $12936.78$
DGLFRM Mehta et al. [2019] | $742.00$ | $152.3$ | $3693.18$
FC | $674.37$ | $121.62$ | $19068.93$
Graphite-Kernel | $578.48$ | $75.47$ | $940.35$
DGLFRM-Kernel | $344.32$ | $34.60$ | $823.51$
FC-Kernel | $587.72$ | $47.79$ | $927.81$

Table 2: Comparison to SOTA one-shot deep generative models for average number
of edges in generated graphs . The first row reports the average edge number
of edges in the test set. The real-world Protein graphs show the largest
improvement in density matching from kernel regularization.

Figure 5: Comparison of Auto-Regressive and edge-parallel models; Generation
time for a 20 graph mini-batch vs graph quality on protein data set; (0,0) is
optimum.

Kernel Graph VAE vs. Auto-Regressive Graph Generation. Compared to the complex
Auto-Regressive methods, kernel regularization achieves competitive structure
performance, with no clear pattern of superiority; the Appendix provides
detailed MMD metrics. The big advantage of edge-parallel methods is
scalability: While the SOTA Auto-Regressive models are limited to generating
graphs with at most 5K nodes, training graph VAEs with kernel regularization
easily scales up to 80K nodes. Figure 5 visualizes the trade-off between
generation time and structure quality by placing methods in a 2-D grid where
the x-axis represents overall structural quality, measured by the sum of the 4
MMD terms, and the y-axis represents generation time of protein samples. The
generation time for each method is measured in seconds on a single GTX 1080Ti
GPU. The same comparison for the other data sets appears in the Appendix.

Both Auto-Regressive methods require substantially more generation time than
edge-parallel methods, especially GRAN. GRAN is also a positive outlier in
achieving an excellent aggregate structure match to training graphs. On the
aggregate structure metric, DGLFRM-Kernel actually outperforms GraphRNN.
Comparing DGLFRM-Kernel to the other edge-parallel methods, the overhead from
kernel computation is small. Kernel regularization therefore offers an
attractive sweet spot between scalability of training and realism of graph
structures.

To complement graph structure metrics, we assessed how the learned node
representations support node classification as a local prediction class. As
the results in the Appendix show, node classification accuracies measured on 3
further datasets improves for most datasets and methods.

##  8 Limitations

The main limitation is scaling kernel regularization with the graph size,
because the complexity of evaluating graph kernels grows quadratically or more
with domain size (see Section 4.1 for formulas). It may be possible to apply
previous work on fast graph kernel evaluation Nikolentzos et al. [2019] to
address this limitation. Another limitation is the need to set kernel weights
as hyperparameters.

##  9 Conclusion and Future Work

Within the graph VAE framework, we introduced a joint observation model for
local and global graph features and derived a new ELBO objective that combines
both. As the objective subtracts a kernel-based graph distance term from the
standard local link reconstruction probability, we refer to it as kernel
regularization. An efficient encoder-decoder graph generation architecture for
kernel regularization can be obtained by extending existing graph kernels. We
adapted degree and multi-step transition probability kernels for soft
(reconstructed) edges. Empirical evaluation shows that kernel regularization
improves generated graph structure by orders of magnitude compared to previous
edge-parallel methods. Compared to Auto-Regressive graph generation, kernel
regularization achieves competitive graph quality, and therefore offers an
attractive trade-off between graph generation speed and graph structure
quality.

Kernel regularization opens a number of fruitful avenues for future work. i) A
new application area for graph kernels Nikolentzos et al. [2019] is to
investigate which are best suited to support neural graph generation. ii)
Combining kernel regularization with other graph generative architectures. For
example in an Auto-Regressive framework, after generating a graph an MMD term
can be added to the loss function to include in backpropagation. 3) Graph
embeddings Hamilton [2020] can be used to summarize global graph features and
increase the power of neural graph generators.

In sum, modelling both global graph structure and local correlations enhances
scientific modelling of graph data. In terms of learning performance, we find
that they are mutually reinforcing objectives that improve each other.

##  10 Societal Impact

Graph generation could have both positive and negative societal impact,
depending on what the graph models. On the positive side, graphs could
represent molecules, and so better modelling could aid drug discovery. On the
negative side, network analysis as a field has potential to increase and
misuse control over network participants. For example to motivate violations
of privacy in targeting recommendations, or identify users through their
social links. However, these harms can be mitigated by strengthening privacy
protections during data collection. Furthermore, network analysis can provide
significant societal benefit, for example by highlighting the existence and
situation of marginalized communities and understanding the flow of influence
and (mis)information in social networks. For a more detailed discussion about
the impact of network analysis on society, see the readings by the McGill
Center for Network Dynamics. The main contribution of our work supports more
beneficial uses by enhancing the understanding of global network structure, as
opposed to the potentially harmful targeting of individuals.

## Checklist

  1. 1.

For all authors…

    1. (a)

Do the main claims made in the abstract and introduction accurately reflect
the paper’s contributions and scope? [Yes]

    2. (b)

Did you describe the limitations of your work? [Yes] See Section 8 for
details.

    3. (c)

Did you discuss any potential negative societal impacts of your work? [Yes]
See Section 10 for details.

    4. (d)

Have you read the ethics review guidelines and ensured that your paper
conforms to them? [Yes]

  2. 2.

If you are including theoretical results…

    1. (a)

Did you state the full set of assumptions of all theoretical results? [Yes]
See Section 3 for details.

    2. (b)

Did you include complete proofs of all theoretical results? [Yes] See Section
3 and Appendix for details.

  3. 3.

If you ran experiments…

    1. (a)

Did you include the code, data, and instructions needed to reproduce the main
experimental results (either in the supplemental material or as a URL)? [Yes]
Code, data sets and library requirements can be found in our repository

    2. (b)

Did you specify all the training details (e.g., data splits, hyperparameters,
how they were chosen)? [Yes] See Sections 6 and Appendix for all experiment
settings. We also added all details, including models, generated samples,
training logs and library requirements in our public repository.

    3. (c)

Did you report error bars (e.g., with respect to the random seed after running
experiments multiple times)? [No] The reported baselines generally have
training time in order of hours which make it hardly possible to run with
multiple seeds on several datasets. Also the effects are large: on the key
structure metrics, the proposed approach typically results in 1-2 orders of
magnitude of compared metrics improvement. This evidence seems to be
sufficient without error bars.

    4. (d)

Did you include the total amount of compute and the type of resources used
(e.g., type of GPUs, internal cluster, or cloud provider)? [Yes] See Section 7
for machine details.

  4. 4.

If you are using existing assets (e.g., code, data, models) or
curating/releasing new assets…

    1. (a)

If your work uses existing assets, did you cite the creators? [Yes] Reported
data sets and codes are open-source and publicly available. We cited them
clearly in Tables and Context

    2. (b)

Did you mention the license of the assets? [Yes] All codes and data sets used
in this study are publicly available and clearly mentioned in the Section 6.

    3. (c)

Did you include any new assets either in the supplemental material or as a
URL? [Yes] We included our model implementation and it is publicly available
at -

    4. (d)

Did you discuss whether and how consent was obtained from people whose data
you’re using/curating? [Yes] As mentioned in Section 6, we used the original
papers’ public repository; hence no consent was needed to curate this study.
Also all used data sets are open source and publicly available.

    5. (e)

Did you discuss whether the data you are using/curating contains personally
identifiable information or offensive content? [Yes]  As mentioned in Section
6, None of the data sets used for this research study contain any personally
identifiable information or offensive content.

  5. 5.

If you used crowdsourcing or conducted research with human subjects…

    1. (a)

Did you include the full text of instructions given to participants and
screenshots, if applicable? [N/A] This point is not applicable for this
research study.

    2. (b)

Did you describe any potential participant risks, with links to Institutional
Review Board (IRB) approvals, if applicable? [N/A] This point is not
applicable for this research study.

    3. (c)

Did you include the estimated hourly wage paid to participants and the total
amount spent on participant compensation? [N/A] No such participants were used
for this research study.

## References

  * Chakrabarti and Faloutsos [2012] Deepayan Chakrabarti and Christos Faloutsos.  Graph mining: laws, tools, and case studies.  _Synthesis Lectures on Data Mining and Knowledge Discovery_ , 7(1):1–207, 2012.
  * De Cao and Kipf [2018] Nicola De Cao and Thomas Kipf.  Molgan: An implicit generative model for small molecular graphs.  _arXiv preprint arXiv:1805.11973_ , 2018.
  * Do et al. [2019] Tien Huu Do, Duc Minh Nguyen, Evaggelia Tsiligianni, Angel Lopez Aguirre, Valerio Panzica La Manna, Frank Pasveer, Wilfried Philips, and Nikos Deligiannis.  Matrix completion with variational graph autoencoders: Application in hyperlocal air quality inference.  In _ICASSP 2019-2019 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)_ , pages 7535–7539. IEEE, 2019.
  * Dobson and Doig [2003] Paul D Dobson and Andrew J Doig.  Distinguishing enzyme structures from non-enzymes without alignments.  _Journal of molecular biology_ , 330(4):771–783, 2003.
  * Faisal et al. [2015] SM Faisal, Georgios Tziantzioulis, AM Gok, Nikolaos Hardavellas, S Ogrenci-Memik, and Srinivasan Parthasarathy.  Edge importance identification for energy efficient graph processing.  In _2015 IEEE International Conference on Big Data (Big Data)_ , pages 347–354. IEEE, 2015.
  * Grover and Leskovec [2016] Aditya Grover and Jure Leskovec.  node2vec: Scalable feature learning for networks.  In _Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining_ , pages 855–864, 2016.
  * Grover et al. [2019] Aditya Grover, Aaron Zweig, and Stefano Ermon.  Graphite: Iterative generative modeling of graphs.  In _Proceedings of the 36th International Conference on Machine Learning_ , volume 97 of _Proceedings of Machine Learning Research_ , pages 2434–2444, 2019.
  * Hamilton [2020] William L Hamilton.  Graph representation learning.  _Synthesis Lectures on Artifical Intelligence and Machine Learning_ , 14(3):1–159, 2020.
  * Higgins et al. [2017] Irina Higgins, Loïc Matthey, Arka Pal, Christopher Burgess, Xavier Glorot, Matthew Botvinick, Shakir Mohamed, and Alexander Lerchner.  beta-vae: Learning basic visual concepts with a constrained variational framework.  In _5th International Conference on Learning Representations, ICLR 2017_ , 2017.  URL https://openreview.net/forum?id=Sy2fzU9gl.
  * Jebara and Kondor [2003] Tony Jebara and Risi Kondor.  Bhattacharyya expected likelihood kernels.  In _Computational Learning Theory and Kernel Machines, 16th Annual Conference on Computational Learning Theory and 7th Kernel Workshop, COLT/Kernel 2003_ , volume 2777, pages 57–71, 2003.  doi: 10.1007/978-3-540-45167-9\\_6.  URL https://doi.org/10.1007/978-3-540-45167-9_6.
  * Kingma and Welling [2014] Diederik P. Kingma and Max Welling.  Auto-Encoding Variational Bayes.  In _2nd International Conference on Learning Representations, ICLR_ , 2014.
  * Kipf and Welling [2016] Thomas Kipf and M. Welling.  Variational graph auto-encoders.  _ArXiv_ , abs/1611.07308, 2016.
  * Li et al. [2018] Yujia Li, Oriol Vinyals, Chris Dyer, Razvan Pascanu, and Peter Battaglia.  Learning deep generative models of graphs.  _arXiv preprint arXiv:1803.03324_ , 2018.
  * Liao et al. [2019] Renjie Liao, Yujia Li, Yang Song, Shenlong Wang, William L. Hamilton, David Duvenaud, Raquel Urtasun, and Richard S. Zemel.  Efficient graph generation with graph recurrent attention networks.  In _Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019_ , pages 4257–4267, 2019.  URL https://proceedings.neurips.cc/paper/2019/hash/d0921d442ee91b896ad95059d13df618-Abstract.html.
  * Ma et al. [2018] Tengfei Ma, Jie Chen, and Cao Xiao.  Constrained generation of semantically valid graphs via regularizing variational autoencoders.  In _Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurIPS 2018_ , pages 7113–7124, 2018.  URL https://proceedings.neurips.cc/paper/2018/hash/1458e7509aa5f47ecfb92536e7dd1dc7-Abstract.html.
  * Mehta et al. [2019] Nikhil Mehta, Lawrence Carin, and Piyush Rai.  Stochastic blockmodels meet graph neural networks.  _CoRR_ , abs/1905.05738, 2019.
  * Nikolentzos et al. [2019] Giannis Nikolentzos, Giannis Siglidis, and Michalis Vazirgiannis.  Graph kernels: A survey.  _arXiv preprint arXiv:1904.12218_ , 2019.
  * Orbanz and Roy [2014] Peter Orbanz and Daniel M Roy.  Bayesian models of graphs, arrays and other exchangeable random structures.  _IEEE transactions on pattern analysis and machine intelligence_ , 37(2):437–461, 2014.
  * Pan et al. [2018] Shirui Pan, Ruiqi Hu, Guodong Long, Jing Jiang, Lina Yao, and Chengqi Zhang.  Adversarially regularized graph autoencoder for graph embedding.  In _Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence, IJCAI_ , 2018.
  * Qiao et al. [2020] Heng Qiao, Daniela Oliveira, and Dapeng Wu.  A novel criterion of reconstruction-based anomaly detection for sparse-binary data.  In _GLOBECOM 2020-2020 IEEE Global Communications Conference_ , pages 1–6. IEEE, 2020.
  * Samanta et al. [2020] Bidisha Samanta, Abir De, Gourhari Jana, Vicenç Gómez, Pratim Kumar Chattaraj, Niloy Ganguly, and Manuel Gomez-Rodriguez.  NEVAE: A deep generative model for molecular graphs.  _J. Mach. Learn. Res._ , 21:114:1–114:33, 2020.  URL http://jmlr.org/papers/v21/19-671.html.
  * Vishwanathan et al. [2010] S Vichy N Vishwanathan, Nicol N Schraudolph, Risi Kondor, and Karsten M Borgwardt.  Graph kernels.  _Journal of Machine Learning Research_ , 11:1201–1242, 2010\.
  * Xiang and Neville [2011] Rongjing Xiang and Jennifer Neville.  Relational learning with one network: An asymptotic analysis.  In _Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics_ , pages 779–788. JMLR Workshop and Conference Proceedings, 2011.
  * Yahyaei and Katre [2018] L. Yahyaei and S.A. Katre.  Dimension of a lobster.  _AKCE International Journal of Graphs and Combinatorics_ , 2018.  ISSN 0972-8600.  doi: https://doi.org/10.1016/j.akcej.2018.08.001.  URL https://www.sciencedirect.com/science/article/pii/S0972860017302906.
  * You et al. [2018] Jiaxuan You, Rex Ying, Xiang Ren, William Hamilton, and Jure Leskovec.  Graphrnn: Generating realistic graphs with deep auto-regressive models.  In _International Conference on Machine Learning_ , pages 5708–5717. PMLR, 2018.
  * Yun et al. [2019] Seongjun Yun, Minbyul Jeong, Raehyun Kim, Jaewoo Kang, and Hyunwoo J. Kim.  Graph transformer networks.  In _Advances in Neural Information Processing Systems, NeurIPS_ , pages 11960–11970, 2019.
  * Zhang et al. [2018] Zhen Zhang, Mianzhi Wang, Yijian Xiang, Yan Huang, and Arye Nehorai.  Retgk: Graph kernels based on return probabilities of random walks.  In _Advances in Neural Information Processing Systems_ , volume 31, 2018.  URL https://proceedings.neurips.cc/paper/2018/file/7f16109f1619fd7a733daf5a84c708c1-Paper.pdf.
  * Zhou et al. [2020] Jie Zhou, Ganqu Cui, Shengding Hu, Zhengyan Zhang, Cheng Yang, Zhiyuan Liu, Lifeng Wang, Changcheng Li, and Maosong Sun.  Graph neural networks: A review of methods and applications.  _AI Open_ , 1:57–81, 2020.

##  11 Appendix

###  11.1 Proof of Proposition 1.

From the product likelihood (4) we have

$p(\boldsymbol{A}|\boldsymbol{z})=\frac{1}{C(\boldsymbol{z})}p(\boldsymbol{A}|\tilde{\boldsymbol{A}}_{\boldsymbol{z}})\cdot
p(\boldsymbol{\phi}(\boldsymbol{A})|\boldsymbol{z}))$

where
$C(\boldsymbol{z})=\sum_{\boldsymbol{A}}p(\boldsymbol{A}|\tilde{\boldsymbol{A}}_{\boldsymbol{z}})\cdot
p(\boldsymbol{\phi}(\boldsymbol{A})|\boldsymbol{z}))$ is a normalization
constant.

We observe that

$\displaystyle 1$
$\displaystyle=\int_{\phi}N(\phi|\phi(\tilde{\boldsymbol{A}}_{\boldsymbol{z}}),\frac{1}{2\lambda}*I)d\phi$
$\displaystyle\geq\sum_{\phi:\exists\boldsymbol{A}.\phi=\phi(\boldsymbol{A})}N(\phi|\phi(\tilde{\boldsymbol{A}}_{\boldsymbol{z}}),\frac{1}{2\lambda}*I)$
(8)
$\displaystyle\geq\sum_{\phi:\exists\boldsymbol{A}.\phi=\phi(\boldsymbol{A})}N(\phi|\phi(\tilde{\boldsymbol{A}}_{\boldsymbol{z}}),\frac{1}{2\lambda}*I)\cdot
p(\boldsymbol{A}|\tilde{\boldsymbol{A}}_{\boldsymbol{z}})=C(\boldsymbol{z})$

The last inequality holds because
$p(\boldsymbol{A}|\tilde{\boldsymbol{A}}_{\boldsymbol{z}})\in[0,1]$. Hence
$-\ln{C(\boldsymbol{z})}\geq 0$ and therefore

$\displaystyle\ln{p(\boldsymbol{\phi}(\boldsymbol{A})|\boldsymbol{z}))}-\ln{C(\boldsymbol{z})}$
$\displaystyle\geq\ln{N(\phi(\boldsymbol{A})|\phi(\tilde{\boldsymbol{A}}_{\boldsymbol{z}}),\frac{1}{2\lambda}*I)}$
$\displaystyle=-\lambda||\phi(\boldsymbol{A})-\phi(\tilde{\boldsymbol{A}}_{\boldsymbol{z}})||^{2}+\frac{l}{2}\ln{2\lambda}-\frac{l}{2}\ln{2\pi}$
$\displaystyle=-\lambda\mathit{D}^{2}_{k}(\boldsymbol{A},\tilde{\boldsymbol{A}}_{\boldsymbol{z}})+\frac{l}{2}\ln{2\lambda}-\frac{l}{2}\ln{2\pi}$
(9)

Applying the general VAE lower bound to the product likelihood together with
Inequality (11.1) yields

$\begin{split}\ln{P(\boldsymbol{A})}&\geq E_{\boldsymbol{z}\sim
q(\boldsymbol{Z}|\boldsymbol{X},\boldsymbol{A})}\big{[}\ln{p(\boldsymbol{A}|\tilde{\boldsymbol{A}}_{\boldsymbol{z}})}+\ln{p(\boldsymbol{\phi}(\boldsymbol{A})|\boldsymbol{z}))}-\ln{C(\boldsymbol{z})}\big{]}-KL\big{(}q_{\varphi}(\boldsymbol{Z}|\boldsymbol{X},\boldsymbol{A})||p(\boldsymbol{Z})\big{)}\\\
&\geq E_{\boldsymbol{z}\sim
q(\boldsymbol{Z}|\boldsymbol{X},\boldsymbol{A})}\big{[}\ln{p_{\theta}(\boldsymbol{A}|\tilde{\boldsymbol{A}}_{\boldsymbol{z}})}-\lambda\mathit{D}^{2}_{k}(\boldsymbol{A},\tilde{\boldsymbol{A}}_{\boldsymbol{z}})+\frac{l}{2}\ln{2\lambda}-\frac{l}{2}\ln{2\pi}\big{]}-KL\big{(}q_{\varphi}(\boldsymbol{Z}|\boldsymbol{X},\boldsymbol{A})||p(\boldsymbol{Z})\big{)}\\\
&=L_{\textsc{kelbo}}(\varphi,\theta)+\frac{l}{2}\ln{2\lambda}-\frac{l}{2}\ln{2\pi}\end{split}$

###  11.2 Graph VAEs Encoder and decoder architecture

#### Encoder

All GVAE methods (DGLFRM, Graphite and FC) utilize a multi-layer Graph
Convolutional Network (GCN) for computing the parameters of the variational
posterior distribution. We assume isotropic Gaussian distributions for the
prior and posterior Kipf and Welling [2016]. The inference model equations are
as follows.

$\displaystyle p(\boldsymbol{Z})$
$\displaystyle=\prod_{i=1}^{N}{p(\boldsymbol{z}_{i})}=\prod_{i=1}^{N}N(\boldsymbol{z}_{i}|0,I)$
$\displaystyle
q({\boldsymbol{Z}}\left|{\boldsymbol{X},\boldsymbol{A})}\right.$
$\displaystyle=\prod_{i=1}^{N}{q(\boldsymbol{z}_{i}|{\boldsymbol{X},\boldsymbol{A})}}=\prod_{i=1}^{N}{N(\boldsymbol{z}_{i}|{\mu_{i},\sigma^{2}_{i}*{\rm{I}})}}$
$\displaystyle\boldsymbol{\mu},\boldsymbol{\sigma}$
$\displaystyle=GCN(\boldsymbol{A},\boldsymbol{X})$

$\boldsymbol{\mu}_{i}$ and $\boldsymbol{\sigma}_{i}$ denote the mean and
standard deviation vectors for the node $i$ posterior,

$\mu,\boldsymbol{\sigma}=GCN(\boldsymbol{A},\boldsymbol{X})$ (10)

#### Decoder

A decoder is a deterministic function with signature
$\textsc{DECODE}:R^{t}\times R^{t}\rightarrow R$ Hamilton [2020]. Link
reconstruction probabilities are computed by applying a sigmoid function to
the decoder output.

$[\tilde{\boldsymbol{A}}_{\boldsymbol{z}}]_{i,j}=\sigma(\textsc{DECODE}(\boldsymbol{\boldsymbol{z}}^{*}_{i},\boldsymbol{\boldsymbol{z}}^{*}_{j}))$

Grover et al. [2019] introduced the idea of transforming the output
representations of the encoder $\boldsymbol{Z}$ to a new node representation
set $\boldsymbol{\boldsymbol{Z}^{*}}$. While our GVAE comparison methods share
the same GCN encoder, they differ in the decoder as follows.

Graphite

Uses a simple dot product decoder
$\textsc{DECODE}(\boldsymbol{\boldsymbol{z}}^{*}_{i},\boldsymbol{\boldsymbol{z}}^{*}_{j})=\boldsymbol{\boldsymbol{z}}^{*}_{i}\bullet\boldsymbol{\boldsymbol{z}}^{*}_{j}$.
Applies GCN-style iterated message passing to transform $\boldsymbol{Z}$ to
$\boldsymbol{\boldsymbol{Z}^{*}}$.

DGLFRM

Applies a stochastic block model decoder
$\textsc{DECODE}(\boldsymbol{\boldsymbol{z}}^{*}_{i},\boldsymbol{\boldsymbol{z}}^{*}_{j})=\boldsymbol{\boldsymbol{z}}^{*}_{i}\Lambda\boldsymbol{\boldsymbol{z}}^{*\top}_{j}$
where $\Lambda$ is a learnable parameter matrix Mehta et al. [2019]. We use a
neural network $f(\boldsymbol{Z})=\boldsymbol{Z}^{*}$ to transform the encoder
node representations.

FC

A fully connected neural network $f(\boldsymbol{Z})=\tilde{\boldsymbol{A}}$
that directly maps the node representation to a probabilistic adjacency
matrix.

###  11.3 Hyperparameter details

All models are trained with backpropagation for $3,000$ epochs, which is
similar to previous work You et al. [2018], Liao et al. [2019]. For Graphite,
we used the implementation provided by the authors Grover et al. [2019]. For
DGLFRM and vanilla FC, we use an architecture of 128-128-256 units for the
3-layer encoder. Both models are trained using the Adam optimizer Kingma and
Welling [2014] with a learning rate of $.0001$. We also used the Beta-VAE
Higgins et al. [2017] approach with $\beta=20$ to adjust latent channel
capacity for both models. For DGLFRM decoder, we use five hidden layers with
256$N$-1024-1024-1024-256$N$ units and $256\times 256\leavevmode\nobreak\
\Lambda$ matrix. For vanilla FC decoder we use $256N$-512-512-512-$N^{2}$
architecture where $N$ is the size of maximum graph in data set.
For the input Kernel weights see table 3. For all the other methods, we apply
the hyperparameter settings suggested by the original papers. The GRAN authors
suggest several settings; we use block size and stride are both set to 1.

Table 3: The input Kernel weights $\boldsymbol{\lambda}$ for each data-set
used in graph generation task. Note we used the same weight for all models.

Data set | Transition Probability $(s=1\dots 5)$ | In/Out Degree Dist
---|---|---
Grid | $e^{2}$ | $e^{-4}$
Lobster | $e^{2}$ | $e^{-4}$
Protein | $e^{3}$ | $2e^{-5}$

###  11.4 Qualitative evaluation of graph VAE models and kernel regularization
approach in detatil

We examine the effect of kernel regularization on several GVAE architectures.
Our methodology is to keep the architecture the same as published and change
only the objective function for training. Figure 6 and 2 provides a visual
comparison of state-of-the-art GVAE architecture and the effect of kernel
regularized approach. For each model we generate 200 samples from prior
distribution $p(\boldsymbol{z})$ and visually select and plot the most similar
ones to the test set . The first row in each of the figures shows randomly
selected target graphs from the test set. Each block compares the effect of
the kernel regularized approach on the named model. As illustrated regularized
approach noticeably improved the model’s ability to generate similar graphs.

| Test
---
|  |  |
| FC
---
|  |  |
| FC-Kernel
---
|  |  |
| DGLFRM
---
|  |  |
|  15cmDGLFRM-
---
Kernel
|  |  |
| Graphite
---
|  |  |
|  15cmGraphite-
---
Kernel
|  |  |
Figure 6: Visualization of generated graphs from Grid inputs by SOTA graph VAE models and kernel regularization effect. The first rows show randomly selected target graphs from the test set. The first and second rows in each block show original and kernel regularized models respectively. Generated graphs by kernel regularized approach, FC-Kernel and DGLFRM-Kernel, match the target graph the best and makes a noticeable improvement in comparison to the original models. Note that generated graphs are generated independently of the target from the prior distribution $P(\boldsymbol{z})$ by each method. In addition, for each model we visually select and visualize the most similar generated samples to the test set.  | Test
---
|  |  |
| FC
---
|  |  |
| FC-Kernel
---
|  |  |
| DGLFRM
---
|  |  |
|  15cmDGLFRM-
---
Kernel
|  |  |
| Graphite
---
|  |  |
|  15cmGraphite-
---
Kernel
|  |  |
Figure 7: Visualization of generated graphs from Lobster inputs, a Lobster
graph is a tree in which the removal of leaves, leaves a caterpillar222A
caterpillar is a graph which reduces to a path after removing its leaves.
Yahyaei and Katre [2018], by SOTA graph VAE models and kernel regularization
effect. The first row shows randomly selected target graphs from the test set.
The first and second rows in each block show the generated graphs by original
and the kernel regularized models respectively. Generated samples by kernel
regularized models matched the target graph the best and kernelized models
make a noticeable improvement in comparison to the original models. Note that
generated graphs are generated independently of the target, from the prior
distribution $P(\boldsymbol{z})$ by each method. In addition, for each model
we generate $200$ samples, and visually select and visualize the most similar
ones to the test set.

###  11.5 Lesion Study on Kernel ELBO components

In this section we drill down into the different components of the Kernel
objective. Our next results study the respective importance of the input graph
features used, degree distribution and transition probabilities. Table 4 shows
that both kernels are necessary for achieving full structural quality. For
example, compared to a single graph input feature, combining the two input
graph features improves the sparsity match on grid graphs by 2 orders of
magnitude, and by 1 order on Lobster graphs. Taken in isolation, matching
observed transition probabilities has an even bigger impact than matching
observed degree distribution—even in the Deg. columns that measure that match
to degree distribution. These results provide evidence that rather than being
competing objectives, matching observed graph features achieve a co-training
effect where each kernel reinforces the other.

Table 4: Lesion Study on MMD between the test set graphs and the generated
graphs using DGLFRM model.

Method | Grid | Lobster | Protein
---|---|---|---
Deg. | Clus. | Orbit | Sparsity | Deg. | Clus. | Orbit | Sparsity | Deg. | Clus. | Orbit | Sparsity
DGLFRM Mehta et al. [2019] | $1.21$ | $1.69$ | $0.95$ | $4.65e^{-8}$ | $1.17$ | $1.56$ | $0.91$ | $8.83e^{-9}$ | $0.80$ | $0.95$ | $0.80$ | $2.33e^{-6}$
DGLFRM-Deg | $0.53$ | $0.65$ | $0.27$ | $1.13e^{-9}$ | $0.96$ | $1.43$ | $0.54$ | $4.08e^{-8}$ | $0.78$ | 0.08 | $0.862$ | $1.45e^{-8}$
DGLFRM-Step | $0.29$ | $0.53$ | $0.08$ | $1.66e^{-9}$ | 0.06 | $0.41$ | 0.06 | $8.35e^{-8}$ | $0.88$ | $1.16$ | $0.81$ | $2.15e^{-7}$
DGLFRM-Kernel | 0.21 | 0.26 | 0.03 | $\textbf{3.55e}^{\textbf{-11}}$ | $0.07$ | 0.24 | $0.08$ | $\textbf{3.25e}^{\textbf{-9}}$ | 0.65 | 0.08 | 0.74 | $\textbf{1.73e}^{\textbf{-8}}$

###  11.6 Adjacency reconstruction vs. MMD.

Compared to the standard graph VAE ELBO based on the cross-entropy for the
local graph adjacencies, the kernel ELBO adds an MMD term to match global
features. Does the MMD compete with maximizing graph adjacency reconstruction
or can it be seen as a co-training objective? Comparing the standard ELBO

$\displaystyle L_{\textsc{elbo}}(\varphi,\theta)$ $\displaystyle\equiv$
$\displaystyle E_{\boldsymbol{z}\sim
q_{\varphi}(\boldsymbol{Z}|\boldsymbol{X},\boldsymbol{A})}\big{[}\ln
p_{\theta}(\boldsymbol{A}|\tilde{\boldsymbol{A}}_{\boldsymbol{z}})]-KL\big{(}q_{\varphi}(\boldsymbol{Z}|\boldsymbol{X},\boldsymbol{A})||p(\boldsymbol{Z})\big{)}$
(11)

with the kernelized ELBO from Equation (2), we find that in all datsets and
for all methods, kernel regularization leads to both larger values of
$L_{\textsc{elbo}}$ and $L_{\textsc{kelbo}}$. This shows that the kernel loss
term
$\sum_{u=1}^{m}\boldsymbol{\lambda}_{u}\mathit{D}^{2}_{k_{u}}(\boldsymbol{A},\tilde{\boldsymbol{A}}_{\boldsymbol{z}})$
serves as a co-training objective that improves the standard ELBO (11) taken
by itself. Table 5 gives details on the improvement in each component. We see
that kernel regularization improves the local link reconstruction component
and slightly increases the negative KLD. This suggests that matching global
graph features helps local learning converge to a better minimum. Figure 8
confirms this hypothesis by looking at the adjacency reconstruction loss
dynamics of VAE training. We see that the adjacency reconstruction loss
decreases more quickly without the MMD regularizer (FC plot). For example on
grid input graphs, it falls below 0.45 already after about 100 epochs. On the
other hand, convergence to an optimal reconstruction value is much more rapid
with kernel regularization. For example on the grid and lobster input graphs,
it occurs around 500 epochs, whereas without regularization it occurs around
1500 epochs. These results also indicate that while kernel regularization
makes each step of gradient descent more costly, it reduces the overall number
of steps required for convergence.

Table 5: Comparing components of the loss function. For each data set the
columns show adjacency matrix reconstruction loss, $-\ln
p_{\theta}(\boldsymbol{A}|\tilde{\boldsymbol{A}}_{\boldsymbol{z}})$, KL
divergence,
$KL\big{(}q_{\varphi}(\boldsymbol{Z}|\boldsymbol{X},\boldsymbol{A})||p(\boldsymbol{Z})\big{)}$
and kernel loss ,
$\sum_{u=1}^{m}\boldsymbol{\lambda}_{u}\mathit{D}^{2}_{k_{u}}(\boldsymbol{A},\tilde{\boldsymbol{A}}_{\boldsymbol{z}})$.

Method | Grid | Lobster | Protein |
---|---|---|---|---
Rec. | KL. | Kernel. | Rec. | KL. | Kernel. | Rec. | KL. | Kernel. |
Graphite Grover et al. [2019] | $0.350$ | $1.24e^{-3}$ | $2.11e^{-3}$ | $0.100$ | $2.91e^{-3}$ | $1.82e^{-3}$ | $0.140$ | $0.001$ | $3.12e^{-4}$ |
DGLFRM Mehta et al. [2019] | $0.034$ | $1.51e^{-3}$ | $2.29e^{-4}$ | $0.025$ | $3.50e^{-3}$ | $9.55e^{-4}$ | $0.036$ | $0.002$ | $2.23e^{-4}$ |
FC | $0.044$ | $1.56e^{-3}$ | $2.67e^{-3}$ | $0.0424$ | $3.44e^{-3}$ | $3.67e^{-3}$ | $0.422$ | $0.005$ | $1.04e^{-3}$ |
Graphite-Kernel | $0.181$ | $2.92e^{-3}$ | $1.83e^{-3}$ | $0.080$ | $5.16e^{-3}$ | $0.92^{-3}$ | $0.079$ | $0.007$ | $2.50e^{-4}$ |
DGLFRM-Kernel | $0.015$ | $3.36e^{-3}$ | $3.14e^{-5}$ | $0.007$ | $7.73e^{-3}$ | $2.39e^{-5}$ | $0.002$ | $0.003$ | $7.99e^{-6}$ |
FC-Kernel | $0.033$ | $5.75e^{-3}$ | $7.46e^{-5}$ | $0.0126$ | $0.014$ | $3.97e^{-5}$ | $0.066$ | $0.011$ | $3.75e^{-4}$ |

(a) Grid

(b) Lobster

(c) Protein

Figure 8: Comparing models convergence in terms of adjacency matrix
reconstruction loss.

###  11.7 Comparison of Auto-Regressive methods with Kernel-Regularized graph
VAE

Table 6 compares DGLFRM-kernel as a representative kernel-regularized method
against SOTA complex deep generative graph architectures. These methods are
designed to generate realistic graph structures by generating edges
sequentially, not independently, which allows for complex dependencies between
new edges and edges generated so far. Given their purpose, it is not
surprising that one or both of the architectures outperform the kernel VAE on
several features and dataset, as shown in Table 6. For example, GRAN
outmatches the degree distribution of grid graphs by orders of magnitude over
DGLFRM-kernel and GraphRNN. On the other hand, DGLFRM-kernel outmatches the
sparsity of Lobster graphs by an order of magnitude over GRAN and GraphRNN. So
we do not see a clear pattern of superiority between Auto-Regressive and
kernel-regularized architectures in terms of graph structure quality. However
, as mentioned earlier both Auto-Regressive methods require substantially more
generation time than edge-parallel methods. Figure 9 visualizes the trade-off
between generation time and structure quality of Auto-Regressive and edge-
parallel models on Grid and Protein data set.

Table 6: Comparison of Kernel-Regularized graph VAE with the state-of-the-art
Auto-Regressive complex deep architectures models in Graph Generating task
using MMD. There is no clear pattern of superiority. For all MMD metrics, the
smaller the better.

Method | Grid | Lobster | Protein
---|---|---|---
Deg. | Clus. | Orbit | Sparsity | Deg. | Clus. | Orbit | Sparsity | Deg. | Clus. | Orbit | Sparsity
GRAN Liao et al. [2019] | $\textbf{2.0e}^{\textbf{-3}}$ | $7.5e^{-3}$ | $\textbf{1.90e}^{\textbf{-5}}$ | $2.49e^{-10}$ | $0.20$ | $0.33$ | $0.36$ | $2.07e^{-7}$ | 0.12 | $0.44$ | 0.03 | $\textbf{6.59e}^{\textbf{-9}}$
GraphRNN You et al. [2018] | $0.20$ | $\textbf{8.0e}^{\textbf{-4}}$ | $9.23e^{-3}$ | $4.77e^{-10}$ | $0.31$ | 0.01 | $0.14$ | $5.01e^{-7}$ | $0.82$ | $0.88$ | $0.38$ | $1.46e^{-6}$
DGLFRM-Kernel | $0.21$ | $0.26$ | $0.03$ | $\textbf{3.55e}^{\textbf{-11}}$ | 0.07 | $0.24$ | 0.08 | $\textbf{3.25e}^{\textbf{-9}}$ | $0.65$ | 0.08 | $0.74$ | $1.73e^{-8}$

(a) Grid

(b) Lobster

Figure 9: Comparison of Auto-Regressive and and edge-parallel models; The
x-axis represents overall structural quality, measured by the sum of the 4 MMD
terms, and the y-axis represents generation time. We use DGLFRM-kernel as
Kernel regularized approach representative. While the kernel regularized model
make a noticeable performance increase, has a much less generation time in
comparison to Auto-Regressive models. (0,0) is optimum.

###  11.8 Node classification

In this setting, we train a generative graph model on a single, typically
large, input graph Xiang and Neville [2011]. While generative graph models
like VAEs can be evaluated in both the multi-graph and single graph input
settings Grover et al. [2019], Hamilton [2020], most studies of graph VAEs are
based on a single input graph. The learned node representations are typically
evaluated on node classification or edge prediction tasks [Hamilton, 2020,
Ch.1], two key local prediction tasks. We conduct experiments for node
classification tasks with three single graph data sets to study the effect of
kernel regularization on local prediction. Our results also provide evidence
that kernel regularization does not lead to overfitting, in that classifier
performance on test nodes with unseen node labels improves for almost all
models and datasets. Our results show a similar pattern as in the multi-graph
setting.

Table 7:  Statistics of the single graph data sets.  Dataset | Nodes | Edges | #Node Type | #Edge Type
---|---|---|---|---
IMDb | 12,772 | 19,120 | 3 | 2
DBLP | 18,405 | 47,283 | 3 | 2
ACM | 8,993 | 18,929 | 3 | 2
Table 8: Evaluating the effect of kernel matching in node classification task.
See Table 7 for dataset details.

Method | DBLP | ACM | IMDb
---|---|---|---
Macro-F1 | Micro-F1 | Macro-F1 | Micro-F1 | Macro-F1 | Micro-F1
DGLFRM | $46.94$ | $82.20$ | $86.27$ | $97.90$ | 20.93 | 28.36
DGLFRM-Kernel | 49.29 | 84.15 | 90.38 | 99.36 | 20.93 | 28.36
Graphite | $48.04$ | $78.59$ | $26.32$ | $65.23$ | $27.77$ | $47.56$
Graphite-Kernel | 65.60 | 80.58 | 48.80 | 69.95 | 44.95 | 61.38

#### Data sets

The single graph data sets used in this study include IMDb, ACM, and DBLP. The
details of the datasets are shown in Table 7. None of the datasets used for
this research study contain any personally identifiable information or
offensive content. DBLP, ACM, and IMDb Yun et al. [2019] are Heterogeneous
graphs and consist of three different types of nodes and two types of
undirected edges. Given the node representation learned by models, we aim to
recover the node types.

#### Experimental setup

We train models for $1000$ epochs. We tuned hyperparameters of
$L_{\textsc{kelbo}}$ for node classification task for each dataset;
$\boldsymbol{\lambda}$ weight for S-Step transition probability $(s=1\dots 5)$
and In/Out degree distribution are $e^{-2}$ and $e^{-13}$, respectively. They
are the same for all methods. For Graphite we apply the hyperparameter
settings suggested by the original papers. For DGLFRM and DGLFRM-kernel we use
Adam optimizer with a learning rate of $2e^{-4}$. In addition for both models
we use three-layer GCNs with 128, 128 and 16 dimensions in the encoder.

#### Node classification.

Following Grover and Leskovec [2016] we use node feature representations as
input to a one-vs-rest logistic regression classifier. We split the data to
train and test and report the performance in terms of both Macro-F1 and
Micro-F1Grover and Leskovec [2016]. Tables 8 summarize Micro-F1 and Macro-F1
evaluations on three single graph data sets. The experiment shows that the
Kernel ELBO objective function results in a noticeable improvement on Macro-F1
and Micro-F1 on all data sets and models except for the DFLFRM on IMDb which
is almost the same.

###  11.9 Code overview

The implementation is provided at "-"333We will use our GitHub repository upon
paper acceptance.. main.py includes the training pipeline and also kernel Elbo
and Elbo objective functions implementation. Graph kernels implementation can
be found at graph-kernel.py. models.py contains the graph VAE with different
Encoder and Decoder architecture implementations. Source codes for loading
real graph datasets and generating synthetic graphs are included in data.py.
All the Python packages used in our experiments are provided in
environment.yml. Generated graph samples for each model and dataset are
provided in the "result/" directory, both in the pickle and png format. We
also added modified implementations of the Graphite and MolGAN baselines in
the "baselines/" directory. Note that we only made a few changes in the
original public repositories to be able to report the effect of the new
objective function.