Multiresolution Equivariant Graph Variational Autoencoder
Authors: Truong Son Hy
Risi Kondor
Venue: ICLR 2022 Submitted (2022)
Keywords: group equivariant model
graph neural network
hierarchical generative model
variational autoencoder
graph generation
link prediction
unsupervised representation learning

Abstract: In this paper, we propose Multiresolution Equivariant Graph Variational Autoencoders (MGVAE), the first hierarchical generative model to learn and generate graphs in a multiresolution and equivariant manner. At each resolution level, MGVAE employs higher order message passing to encode the graph while learning to partition it into mutually exclusive clusters and coarsening into a lower resolution that eventually creates a hierarchy of latent distributions. MGVAE then constructs a hierarchical generative model to variationally decode into a hierarchy of coarsened graphs. Importantly, our proposed framework is end-to-end permutation equivariant with respect to node ordering. MGVAE achieves competitive results with several generative tasks including general graph generation, molecular generation, unsupervised molecular representation learning to predict molecular properties, link prediction on citation graphs, and graph-based image generation.

Under review as a conference paper at ICLR 2022
MULTIRESOLUTION EQUIVARIANT GRAPH TIONAL AUTOENCODER
VARIA-
Anonymous authors Paper under double-blind review
ABSTRACT
In this paper, we propose Multiresolution Equivariant Graph Variational Autoen- coders (MGVAE), the first hierarchical generative model to learn and generate graphs multiresolution and equivariant manner. At each resolution level, MG- VAE employs higher order message passing to encode the graph while learning to partition into mutually exclusive clusters and coarsening into lower res- olution that eventually creates a hierarchy of latent distributions. MGVAE then constructs hierarchical generative model to variationally decode into a hierarchy of coarsened graphs. Importantly, our proposed framework is end-to-end permuta- tion equivariant with respect to node ordering. MGVAE achieves competitive re- sults with several generative tasks including general graph generation, molecular generation, unsupervised molecular representation learning to predict molecular properties, link prediction citation graphs, and graph-based based image generation.
INTRODUCTION
Understanding graphs in a multiscale and multiresolution perspective essential for capturing the structure of molccules, social networks, or the World Wide Web. Graph neural networks (GNNs) utilizing various ways of generalizing the concept of convolution to graphs (Scarselli et al. 2009)
(Niepert et al. 2016b) (Li et al. 2016) have been widely applied many learning tasks, including modeling physical systems (Battaglia et al.] 2016)) finding molecular representations to estimate quantum chemical computation (Duvenaud et al. 2015) (Kearnes et al. 2016) (Gilmer et al. (017b) (Hy et al.) 2018), and protein interface prediction (Fout et al.) 2017 One of the most popular types GNNs is message passing neural nets (MPNNs) that are constructed based on the message passing scheme in which each node propagates and aggregates information, encoded by vectorized messages, to and from its local neighborhood. While this framework has been immensely successful in many applications, it lacks the ability capture the multiscale and multiresolution structures that are present in complex graphs (Rustamov & Guibas 2013) (Chen et al. 2014) (Cheng et al.) 2015) (Xu al. 2019).
Ying et al. (0188) proposed a multiresolution graph neural network that employs a differential pool- ing operator coarsen the graph. While this approach is effective in some settings, it is based on soft assigment matrices, which means that (a) the sparsity of the graph is quickly lost in higher layers (b) the algorithm isn't able to learn an actual hard clustering of the vertices. The latter is important in applications such as learning molecular graphs, where clusters should idcally be interpretable as concrete subunits of the graphs, e.g., functional groups
In contrast, in this paper we propose an arhictecture called Multiresolution Graph Network (MGN), and its generative cousin, Multiresolutiin Graph Variational Autoencoder (MGVAE), which explic- itly learn multilevel hard clustering of the vertices, leading to true multiresolution hierarchy. In the decoding stage, to "uncoarsen" the graph, MGVAE needs to generate local adjacency matrices, which is inherently second order task with respect to the action of permutations on the vertices, hence MGVAE needs to leverage the recently developed framework of higher order permutation equivariant message passing networks (Hy al. 2018 Maron et al. 2019b).
Learning to generate graphs with deep generative models is a difficult problem because graphs are combinatorial objects that typically have high order correlations between their discrete substruc- tures (subgraphs) (You et al. 2018a) (Li et al., 2018) (Liao et al.] 2019) (Liu et al.] (019) (Dai et al. 2020p. based molecular generation (Gimez-Bombareli et al. 2018) (Simonovsky &

---

Under review as a conference paper at ICLR 2022
Komodakis 2018) Cao & Kipf 2018) (Jin et al. 2018 TThiede et al. 2020) involves further chal- lenges, including correctly recognizing chemical substructures, and importantly, ensuring that the generated molecular graphs chemically valid. MGN allows to extend the existing model of variational autoencoders (VAEs) with hierarchy of latent distributions that can stochastically gen- erate graph in multiple resolution levels. Our experiments show that having flexible clustering procedure from MGN enables MGVAE to detect, reconstruct and finally generate important graph substructures, especially chemical functional groups.
RELATED WORK
There have been significant advances in understanding the invariance and equivariance properties of
neural networks in general (Cohen & Welling 2016a) (Cohen & Welling 2016b), of graph neural
networks (Maron al. 2019b), of neural networks learning on sets (Zaheer al. (017) (Serviansky
et al. (0200 (Maron et al. (220). along with their expressive power on graphs (Maron et al. (019cc
(Maron et 2019a). Our work is in line with group equivariant networks operating on graphs and sets. Multiscale, multilevel, multiresolution and coarse grrrinegrainddd techniques have been widely applied
to graphs and discrete domains such as diffusion wavelets (Coifman & Maggioni (006); spectral wavelets on graphs (Hammond et al. 2011); finding graph wavelets based partitioning/cllsteree
(Rustamov & Guibas] 2013); graph clustering and finding balanced cuts on large graphs (Dhillon et (0.55 (Dhillon et al. 2007) (Chiang et al. (012) (Si et al.] 2014); and link prediction
social
networks (Shin et al.) 2012). ). Prior to our work, some authors such as (Zhou et al.) (019) proposed graphs using GAN (Goodfellow al. (0144,, but the hierarchical
multiscale generative model structure was built by heuristics algorithm, not learnable and not flexible to new data that is also an existing limitation of the field. In general, our work exploits the powerful group equivariant networks to encode a graph and to learn to form balanced partitions via back-propagation in data- driven manner without using any heuristics as in the existing works.
In the field of deep generative models, it is generally recognized that introducing hierarchy of latents and adding stochasticity among latents leads more powerful models capable of learning more complicated distributions (Blei et al. (200) (Ranganath et al.) (0066) (Ingraham & Marks, 2017) (Klushyn et al. 2019) (Wu et al.] (2200) (Vahdat & Kautz (020). Our work combines the hierarchical variational autoencoder with learning to construct the hierarchy that results into a gen-
crative model able to generate graphs at many resolution levels.
MULTIRESSLUTION GRAPH NETWORK
3.1 CONSTRUCTION
An undirected weighted graph AV, with node set V and edge set & is represented by an adjacency matrix A N/VX*|1 where Aij implies an edge between node o; and oy with weight Aij (e.g.. Aig- e 10,1} in the case of unweighted graph); while node features are represented by matrix F. TR. M/x,, and edge features are represented by a tensor F, R. xxd The second-order tensor representation of edge features is necessary for our higher-order message passing networks described in the next section. Indeed, F. can be encoded in the diagonal of F..
Definition 1. A K-cluster partition of graph G is partition of the set of nodes V into K mutually exclusive clusters V1.... Each cluster corresponds to an induced subgraph 9x- = g[ve].
Definition 2. A coarsening of G is a graph & of K nodes defined by a K K-cluster partition in which node εR of & corresponds to the induced subgraph Gr. The weighted adjacency matrix A NKKk of is
EgEneeeer Aug, Auw -E Aig,
ik==k' ik k,
where the diagonal of À denotes the number of edges inside each cluster, while the off-diagonal denotes the number of edges between two clusters.
Fig. 3.1 shows an example of Defs. T and 2 a 3-cluster partition of the Aspirin CgH&O, molecular graph and its coarsening graph. Def. 3 defines the multiresolution of graph in bottom-up manner
2

---

=(E) Under review as a conference paper at ICLR 2022
OH
V/
Figure Aspirin C4HsO4, its 3-cluster partition and the corresponding coarsen graph
in which the bottom level is the highest resolution (e.g., 9 itself) while the top level is the lowest resolution (e.g.. is coarsened into single node).
Definition 3. T-level coarsening of graph a series of graphs g()), ,.., g(,))))))) which
1. g(L) is G itself.
2. For is 1, g( is coarsening graph of g((+1) as defined in Def. 2 The number of nodes in G is equal the number of clusters in g(t+1)
3. The top level coarsening G(1) a graph consisting of a single node, and the corresponding adjacency matrix ( Nix1
Definition 4. An L-level Multiresouution Graph Network (MGN) of a graph 9 consists of L- ples of five network components { {(c(t) (f) (f) d
The l-th tuple encodes g( and transforms it into a lower resolution graph ((t-1) in the higher level. Each of these network
localt global ) ())
components has a separate set of learnable parameters (0()), g,() g ( ((()). For simplic- ity, we collectively denote the learnable parameters as O, and drop the superscript. The network components are defined as follows:
Clustering procedure c(g());0) which purtitions graph g into K clusters (0)
10) De. y Each cluster is an induced subgraph G of G(O with adjacency matrix
2. Local encoder (g) 0), which is a permutatioo equivariant (see Defs. 5 6 graph
neural network that takes input the subgraph g( and oulputs a set of node latents (
2(6) represented as a matrix of size [V( dz.
3. Local decoder diocal _0 (), which is permutation equivariant neural network that tries to reconstruct the subgraph adjacency matrix A! for each cluster from the local encoder's output latents.
4. (Optional) Global decoder dgtoral (2(1), 0), which is permutation equivariant neural net- work that reconstructs the full adjacency matrix (()) from all the node latents of K clusters g Dr 2 represented
matrix of size (1) x dz.
5. Pooling network p( 0), which is permutation invariant (see Defs. 5 6) neural net- work that takes the set of node latents 2 and outputs single cluster latent 2 e dz. The coarsening graph ((t-1) has adjacency matrix (t-1) built as in Def. 2 and the cor- responding node features ((-1)) Dr 2
=(?) represented as matrix of size K x dz.
Algorithmically. MGN works a bottom-up up manner as a tree-like hierarchy starting from the high- resolution graph (L)) going the lowest resolution (()) (see Fig. (.T). Iteratively, at f-th level, MGN partitions the current graph into K clusters by running the clustering procedure c( Then, the local encoder e
(4) and local decoder diginaal operate on each of the K subgraphs separately, and can be executed in parallel. This encoder/decoder pair is responsible for capturing the local struc- tures. Finally, the pooling network (t)) shrinks each cluster into single node of the next level.
3

---

Under review as a conference paper at ICLR 2022
0
01
G0
0
10
1
0
A
0
12
RS
F11
P12
Figure 2: Hierarchy of 3-level Multiresolution Graph Network on Aspirin molecular graph
"lobbll makes that the whole of node latents z able to capture the inter-connection between clusters.
Optionally, the global decoder (g)
In terms of time and space complexity, MGN more efficient than existing methods in the field. The cost of global decoding the highest resolution graph is proportional to [V/2. For example, while the encoder can exploit the sparsity of the graph and has complexity O(EE),, a simple dot-product has both time and space complexity of ((D))) which is infea- sible for large graphs. In contrast, the cost running K local dot-product decoders ((V)2/K), which is approximately K times more efficient.
decoder dglobal (Z) sigmoid(
3.2 HIGHER ORDER MESSAGE PASSING
In this paper we consider permutation symmetry, i.e., symmetry to the action of the symmetric group, S.. An element Sn is permutation of order n, bijective map from (1,..., n.) to ... The action of S, adjacency matrix A gaxx and on a latent matrix 2 ggndd are
[o- [o-A]in (t1)
[o 2 -Z-()))
S
Here, the adjacency matrix A is second order tensor with single feature channel, while the latent matrix Z is a first order tensor with de feature channels. In general, the action of S,, on a k-th order tensor X RRn"xe (the last index denotes the feature channels) is defined similarly as:
[o x Klinindee = Xo-1 ( (6)....0"
a Snz.
Network components of MGN (as defined Sec. 3.1 at each resolution level must be either equiv- ariant, or invariant with respect to the permutation action on the node order g(), Formally, we define these properties in Def. 5
Definition 5. An S,-equivariant (or permutation equivariant) function is a function a -xx for all S, and X R Similarly, we say that f Sy.-imvriiat (or permutation invariant) if and only if =x)
f: f:I""xx Rnn
" xd' that satisfies
xd - pg"'' xd' defined as composition Sn -qqivvaraa linear functions f1..,,f and Sn- equivariian nonlinearities "/,... Yr!
Definition 6. An 3r -eqiiirvrr network is function f: :
= forofrre fr... f1.
On the another hand, an invarraa network a function f R==xxd defined as a composition of an Sn Sn.-qquivariant network I' and an S, -nviiiraiant function top of it, e.g., f = fd f"
In order to build higher order equivariant networks, we revisit some basic tensor operations: the tensor product A @ B and tensor contraction Atz,.... (details and definitions are Sec. A). can be shown that these tensor operations respect permutation equivariance (Kondor et al. 2018). Based on these tensor contractions and Def. 5 we can construct the second-order S,, -queviiiaar networks as in Def. [6 (see Example [ f = ? Mr o.. o r M₁ The second-order networks are par- ticularly essential for to extend the original variational autoencoder (VAE) (Kingma & Welling
4

---

Under review as a conference paper at ICLR 2022
2014 model that approximates the posterior distribution by an isotropic Gaussian distribution with a diagonal covariance matrix and uses a fixed prior distribution, CoattionnN(uu (0, 1). constrast, we generalize by modeling the posterior by (H, 2) in which Σ is a full covariance matrix, and we learn an adap- tive parameterized prior N (ã. Σ) instead of fixed one. Only the second-order encoders can output permutation equivariant full covariance matrix, while lower-order networks such MPNNs are unable to. See Sec. [42 and
anddCCooo [or details.
Example 1. The second order message passing has the message Ho (BIWWVi(d,)dd)) initialized by promoting the node features Fu second order tensor (e.g.. we treat node features as self-loop edge features), and concatenating with the featuress Fe. Iteratively,
He He=)(Mi); M.=W, (A@HH-1))
where A @ H4-1 results in a fourth order tensor while ti.j contracts it down to a second order tensor along the i-th and j-th dimensions, denotes concatenation along the feature channels, and W, denotes multilaver perceptron on the feature channels. We remark that the popular MPNNs
Gilmer et al. (011bb) is a lower-order one and a special case in which M₁ D AH1 where Dis -, Auj is the diagonal matrix of node degrees. The message Hr of the last iteration is still second order, so we contract down to the first order lutent Z Q HTI,
3.3 LEARNING TO CLUSTER
Definition 7. A clustering of u objects into k clusters is a mapping π (1,..,n) (1,.., } in which (ii) = if the i-th object is assigned to the j-th cluster. The inverse mapping π - = (i [1,n] <ii)= j} gives the of all objects assigned the j-th cluster. The clustering is represented by assignment matrix II E {0, 1) jonk such that (s) =1
Definition 8. The action of Sn on a clustering w of objects into clusters and its corresponding assignment matrix II are
(0) m(-
Ta. -11),,=I1o-0)))
Definition 9. Let N be a neural network that takes as input a graph G of n nodes, and outputs clustering of k clusters. N is said to be equivariant if and only if N( 9) a (G) for all é Sp.
From Def. intuitively the assignement matrix IT still represents the same clustering if we permute its rows. The learnable clustering procedure el (()()))) is built as follows:
1. A graph neural network parameterized by encodes graph (()) into a first order tensor of K feature channels 6O R "
2. The clustering assignment is determined by a wise maximum pooling operation:
(f) arg max P.kk
(1)
k=[I,K]
that is an equivariant clustering in the sense of Def.
composition of an equivariant function (e-g. graph net) and an equivariant function (e.g., maxi- mum pooling given in Eq. [ is still an equivariant function with respect to the node permutation. Thus, the learnable clustering procedure c(g("; is permutation equivariant.
In practice, in order to make the clustering procedure differentiable for backpropagation, the maximum pooling in Eq. 1q by sampling from categorical distribution. Let n (*) (i) be categor- ical variable with class probabilities .......PP
replace
P....... K computed as softmax from p(.² The Gumbel-max
(f)
trick (Gumbel [954) et al.) 2014 lnn et al. 2017) provides a simple and efficient way
draw samples (+)) (t):
I = oot- arg max I9.k + log logp!?) ke[1,K]
where 0i, are i.i.d samples drawn from Gumbel(O, 1). Given the clustering assignment matrix II(9) the coarsened adjacency matrix (t-1) (see Defs. and can be constructed as ( (1))
5

---

Under review as a conference paper at ICLR 2022
is desirable have bulanced K-cluster partition in which clusters 1 1/ have similar sizes that are close to | The local encoders tend to generalize better for same-size subgraphs. We want the distribution of nodes into clusters be close to the uniform distribution. We enforce the clustering procedure to produce balanced cut by minimizing the following Kullback-Leibler divergence:
P(k) Q(k)
1100 [
DKL DeL
Σ P(k) log
where p=
Q =
(2)
K
K
The whole construction of MGN is equivariant with respect to node permutations of G. In the case of molecular property prediction, we want MGN learn to predict real value y E R for each graph G while learning to find a balanced cut in each resolution to construct a hierarchical structure of latents and coarsen graphs. The total loss function is
LMUN (9,n) 115(( a R(Z())) E-1
(3)
where f is a multilayer perceptron, denotes the vector concatenation, a readout function that produces a permutation invariant vector of size d given the latent Ix at the ê-th resolution, (9) IR is hyperparamter, and DKL (P(*))Q()) is the balanced-cut loss as defined in Eq.
4 HIERARCHICAL GENERATIVE MODEL
In this section, we introduce our hierarchical generative model for multiresolution graph generation based variational principles.
4.1 BACKGROUND ON GRAPH VARIATIONAL AUTOENCODER
Suppose that we have input data consisting of m graphs (data points) g ... dard variational autoencoders (VAEs), introduced by Kingma & Welling (014) have the following generation process, in which each data graph Gj for i {1, 2,.,, m) is generated independently:
9m. The stan-
1. Generate the latent variables Z = [21, 2m), where each Z, E IRIV/xxs is drawn i.i.d. from prior distribution Po (e.g., standard Normal distribution (O, 1)).
2. Generate the data graph G; po (G from the model conditional distribution pe-
We want to optimize 0 maximize the likelihood po quires computing the posterior distribution po ( = II Po (G which is usually intractable. Instead, VAEs apply the variational principle, proposed by Wainwright & Jordan (2005). approxi- mate the posterior distribution as 4s (Zl))= I 4 2219, via amortized inference and maximize evidence lower bound (ELBO) that a lower bound of the likelihood:
pe (e (G) However, this re-
LELBO ④, 0) (log)
DRL (g. (z (Z1))lpo(Z))
Σ
B (2. [.)] DxI, (1s (1.
The probabilistic encoder qo (ZG)). the approximation to the posterior of the generative model Pe 2), is modeled using equivariant graph neural networks (see Example 1b as follows. As- sume the prior over the latent variables be the centered isotropic multivariate Gaussian po( I). We let g ( be multivariate Gaussian with a diagonal covariance structure:
log qo (2,19:)
(1,
(5)
where Mi, a, e R V//xd are the mean and standard deviation of the approximate posterior output by two equivariant graph encoders. We sample from the posterior ya by using the reparameterization trick: Z, μ4 O where ~ (0, /) and @ is the element-wise product.
On the another hand, the probabilistic decoder Pe (9, defines conditional distribution over the entries of the adjacency matrix A,: ps Z.) (u,))) Pe(Aiu 1|2 Z..). For example, Kipf & Welling 2016 suggests simple dot dro-prod decoder that is trivially equivariant: po (A,ue
1[,,, ZTv) = =7( 2 Z,v). where 7 denotes the sigmoid function.

---

Under review as a conference paper at ICLR 2022
4.2 MULTIRESOLUTION VAES
Based on the construction of multiresolution graph network (see Sec. 3.1 the latent vari-
ables are partitioned into disjoint groups, 2, (2 _ .... ...), where z {[z," Ja
]e[dd & is the set of latents at the E-th resolution level in which the graph 9 is partitioned into a number clusters [G] Jk-
In the area of normalzing flows (NFs), Wu et al. 2020) has shown that stochasticity (e.g.. chain of stochastic sampling blocks) overcomes expressivity limitations of NFs. general, our MGVAE is stochastic version of the deterministic MGN such that stochastic sampling is applied at each resolution level in a bottom-up manner. The prior (Eq. 6 and the approximate posterior (Eq. 7 are represented by
p(2.)
11 (2 1-1
II Ix) 1x).
(6)
8-1
46 (2 qo (Z
II 2 (z (2 (f+1) g(())
(-L-1
in which each conditional in the approximate posterior are in the form of factorial Normal distribu- tions, in particular
go (2 _.(1)
1x| (e+1))
where each probabilistic encoder qo ([ ]x(2((()) ( operates subgraph [g[["] 1 as follows:
[[[
The pooling network p(++1) shrinks the latent z( (++1) into the node features of g as in the construction of MGN (see Def. 4
(e)) encodes each subgraph [g] J& into a mean The local (deterministic) graph encoder local
vector and a diagonal covariance matrix (see Eq. 5). ). second order encoder can produce positive semidefinite non-diagona covariance matrix, that can be interpreted as a Gaussian Markov Random Fields (details Sec. B). The new subgraph latent [2(")] ] is sampled by the reparameterization trick.
The prior can be either the isotropic Gaussian NNO..) 1) as in standard VAEs, or be implemented as a parameterized Gaussian N ((, Σ) where ğ and Σ are learnable equivariant functions (details in
Sec. C). The reparameterization trick for conventional (/(0, 1) prior is the same in Sec. [4. while
the new one for the generalized and learnable prior (A, Σ) is given in Sec. B On the another hand,
the probabilistic decoder pe (C( .... (Z()) subgraph adjacencies at each resolution level:
(2()) defines conditional distribution over all
po(g()) ( (2(" 2(1)) I] ( IIII po
Extending from Eq. 4 write our multiresolution variational lower bound LMOVAE(O, logp(9) compactly as
(e LMGVAE( 0, = B
[log to (ogg (z( (0)
(8) where the first term denotes the reconstruction loss (e.g.. 114 - - where ( is Gi itself, A (t<L) is the adjacency produced by MGN level and A! are the reconstructed ones by the de- coders); and the second term is indeed DKI (N((, x (()))))()))) {()) where n4: (1) kkd
and x) e !R! jx are the mean and covariance tensors produced by the L-th encoder for graph G,, while ğ ( and (()) are learnable ones in an equivariant manner as in Sec. C In general, the overall optimization is given as follows:
(MGVVE 0: (f( ((0) + (P,"
min (,8,(A E00),
3,8
where & denotes all learnable parameters of the encoders, 0 denotes all learnable parameters of the decoders, and DKL, (P( !1) is the balanced-cut loss for graph G; at level as defined in Sec. 3.3

---

Under review as a conference paper at ICLR 2022
Figure 3: MGVAE generates molecules QM9 (4 on the left) and ZINC (the rest) equivariantly. There are many more examples of generated molecules in Sec. D.2 Both equivariant MGVAE and autoregressive MGN generate high-quality molecules with complicated structures such rings.
Dataset
Method
Training size Input features
Validity
Novelty
Uniqueness
GraphVAE
61.00%
85.00%
40.90%
CGVAE
100K
100%
94.35%
98.57%
QM9
MoIGAN
Graph
98.1%
94.2%
10.4%
Autoregressive MGN
100%
95.01% %
97.44%
All-at-once MGVAE
100%
100%
95. 16%
GraphVAE
14.00%
100%
31.60%
CGVAE
200K
100%
100%
99.82%
ZINC
Graph
VT-VAE
100%
Autoregressive MGN
IK
100%
99.89%
99.69%
All-at-once MGVAE
IOK
Chemical
99.92%
100%
99.34%
Table 1: Molecular graph generation results. Graph VAE results are taken from
(Liu et al.
2018
EXPERIMENTS
Many more experimental results and details presented in the Sec. of the Appendix.
5.1 MOLECULAR GRAPH GENERATION
We examine the generative power of MGN and MGVAE in the challenging task of molecule genera- tion, in which the graphs are highly structured. We demonstrate that MGVAE is the first hierarchical graph VAE model generating graphs in cetpuuttttioneqivvaiii manner that is competitive against autoregressive results. We train on two datasets that are standard the field:
1. QM9 (Ruddigkeit et al. 2012) (Ramakrishnan al. 2014); contains 134K organic molecules with up to nine atoms (C, H, O, N, and F) out of the GDB-17 universe of molecules.
2. ZINC (Sterling & Irwin 2013): contains 250K purchasable drug-like chemical compounds with up to twenty-three heavy atoms.
We only use the graph features as the input, including the adjacency matrix, the one-hot vector of atom types (e.g., carbon, hydrogen, etc.) and the bond types (single bond, double bond, etc.) without any further domain knowledge from chemistry or physics. First, we train autoencoding task of reconstructing the adjacency matrix and node features. We use learnable equivariant prior (see Sec. ()) instead of the conventional (0, Then, we generate 5, 000 different samples from the prior, and decode each sample into generated graph (see Fig. We implement our graph construction (decoding) in two approaches:
All-at-once: We reconstruct the whole adjacency matrix by running the probabilistic de- coder (see Sec. 4. MGVAE enables us to generate graph at any given resolution level t. In this particular case, we select the highest resolution preserves equivariance, but is harder to train. On ZINC, extract several chemical/atomic features from RDKit as the input for the encoders to reach good convergence in training.
L.. This approach decoding
2. Autoregressive: The graph is constructed iteratively by adding similarly to (Liu et al. 2018). But this approach does not respect permutation equivariance.
edge in each iteration,
In setting for small molecules, == and K = 2 for the E-th level. We compare methods with other graph-based generative models including Graph VAE (Simonovsky & Komodakis 2018), CGVAR (Liu et al. (2018), MolGAN (Cao & Kipf 2018), and JT-VAE (Jin et al. (2018). We evaluate the quality of generated molecules in three metrics: (i) validity, (ii) novelty and (iii) uniqueness as
8

---

Under review as a conference paper at ICLR 2022
COMMUNITY-SMALL
EGO-SMALL
MODEL
DEGREE
CLUSTER
ORBIT
DEGREE
CLUSTER
ORBIT
GRAPHVAE
0.35
0.98
0.54
0.13
0.17
0.05
DEEPGMG
0.22
0.95
0.4
0.04
0.10
0.02
GRAPHRNN
0.08
0.12
0.04
0.09
0.22
0.003
GNF
0.20
0.20
0.11
0.03
0.10
0.001
GRAPHAF
0.06
0.10
0.015
0.04
0.04
0.008
MGVAE
0.002
0.01
0.01
1.74e-05
0.0006
6.53e-05
Table 2: Graph generation results depicting MMD for various graph statistics between the test set and generated graphs. MGVAE outperforms all competing methods.
the percentage of the generated molecules that are chemically valid, different from all molecules in the training set, and redundant, respectively. Because of high complexity, only train small random subset of examples while all other methods are trained on the full datasets. Our models are equivalent with the state-of-the-an even with a limited training set (see Table [ Admittedly, molecule generation is a somewhat subject task that can only be evaluated with objective numerical measures up certain point. Qualitatively, however the molecules that MGVAE generates are as good as the state of the art, in some cases better in terms of producing several high-quality drug- drug-like molecules with complicated functional groups and structures. Many further samples generated by MGVAE and their analysis can be found in the Appendix.
5.2 GENERAL GRAPH GENERATION BY MGVAE
We further examine the expressive power of hierarchical latent structure of MGVAE the task of general graph generation. We choose datasets from GraphRNN paper (You al. 2018a):
1. Community-small: A synthetic dataset 100 2-community graphs where 12 S V s 20.
2. Ego-small: 200 3-hop ego networks extracted from the Citeseer network (Sen et al. 2008) where 4 s [ 18.
The datasets are generated by the scripts from the GraphRNN codebase (You et al. 2018b). We keep 80% of the data for training and the rest for testing. We evaluate our generated graphs by computing Maximum Mean Discrepancy (MMD) distance between the distributions of graph statistics on the test set and the generated set as proposed by (You et al.] 201 8a). The graph statistics are node degrees, clustering coefficients, and orbit counts. As suggested by (Liu et al. 2019), we execute 15 runs with different random seeds, and we generate 1 1,024 graphs for each run, then we average the results over 15 runs. We compare MGVAE against Graph VAE (Simonovsky DeepGMG (Li et al., 2018), GraphRNN (You et al., 2018a). GNF (Liu al. 2019). and GraphAF (Shi et al. 2020). The baselines are taken from GNF paper (Luu al. al, 2019 and GraphAF paper (Shi et al. 2020). In our setting of (all-at-once) MGVAE,
VAE
Komodakis 2018),
implement only L 2 levels of resolution and 2d clusters for each level. Our encoders have 10 layers of message passing. Instead of using high order equivariant network the global decoder for the bottom resolution, only implement simple fully connected network that maps the latent 2 Rl//dd, into adjacency matrix of size |V] x [ For the ego dataset in particular, we implement the learnable equivariant prior in Sec. B and Sec[C] Table 2 includes our quantitative results in comparison with other methods. MGVAE outperforms all competing methods. Figs. 10 show some generated examples and training examples on the 2-community and ego datasets.
CONCLUSION
We introduced MGVAE built upon MGN, the first generative model to learn and generate graphs in a multiresolution and equivariant manner. The key idea of MGVAE is learning to construct series of coarsened graphs along with a hicrarchy of latent distributions in the encoding process while learning to decode each latent into the corresponding coarsened graph at every resolution level. MGVAE achieves state-of-the-ar results from link prediction to molecule and graph generation, suggesting that accounting for the multiscale structure of graphs is promising way to make graph neural networks even more powerful.

---

Under review as a conference paper at ICLR 2022
REFERENCES
Peter Battaglia, Razvan Pascanu, Matthew Lai, Danilo Jimenez Rezende, and Koray Kavukcuoglu. Interaction networks for leamnnng about objects, relations and physics. In Advances in Neural Information Processing Systems, volume 29, Curran Associates, Inc., 2016.
David M. Blei, Andrew Y. Ng, and Michael I. Jordan. Latent dirichlet allocation. J. Mach. Learn. Res., 19911)) March 2003. ISSN 1532-4435.
Nicola De Cao and Thomas Kipf. Molgan: An implicit generative model for small molecular graphs, 2018.
Xu Chen, Xiuyuan Cheng, and Stephane Mallat. Unsupervised deep haar scattering on graphs. In Advances in Neural Information Processing Systems, volume 27. Curran Associates, Inc., 2014.
Xiuyuan Cheng, Xu Chen, and Stéphane Mallat. 0bbs/150909111 2015.
Deep haar scattering networks CoRR,
Kai- Kang Chiang, Joyce Jiyoung Whang, and Inderjit Dhillon. Scalable clustering of signed networks using balance normalized cut. In Proceedings of the s/ ACM International Conference on Information and Knowledge Management, CIKM 12. pp. 6 615624, New York, NY, USA, 2012. Association for Computing Machinery. ISBN 9781 177814001110 11664. doi: 10. N9.1145/23967611 2336841..
Taco S. Cohen and Max Welling. Group equivariant convolutional networks. Proceedings of The
33rd International Conference on Machine Learning, 48:2990-2999 2999, 2016a.
Taco S. Cohen and Max Welling. Stecrable enns. ICLR' 17, 2016b.
Ronald R. Coifman and Mauro Maggioni. Diffusson wavelets. Applied and Computational Har- monic Analysis, 21(1):53-94, 2006. ISSN 1063-5203, doi: https://doi.org/II 10. 10116///.....ccaa
2006.04.004. URL https: /ttps://wwit /ww. sciencedirect. www. www.eic/eeeeeeeeeeeeeeeeeeeaeeee $1063520305000
Special Issue: Diffusion Maps and Wavelets.
Hanjun Dai, Azade Nazi, Yujia Li, Bo Dai, and Dale Schuurmans. Scalable deep generative model- ing for sparse graphs. Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pp. 230222312. PMLR, 13-18 Jul 2020.
Inderjit Dhillon, Yuqiang Guan, and Brian Kulis. A fast kernel-based multilevel algorithm for graph clustering. In Proceedings of the Eleventh ACM SIGKDD International Conference on Knowledge Discovery in Data Mining, KDD '05, pp. 629634, New York, NY, USA, 2005. Association for Computing Machinery. ISBN 159593135X. doi: 10.1 1870. 108 1948.
Inderjit S. Dhillon, Yuqiang Guan, and Brian Kulis. Weighted graph cuts without eigenvectors a multilevel approach. IEEE Transactions on Pattern Analysis and Machine Intelligence, 29(11): 1944-1957, 2007. doi: 10.1 1199/TPAM...00..111
Adji B. Dieng, Francisco J. R. Ruiz, David M. Blei, and Michalis K. Titsias. Prescribed generative adversarial networks, 2019.
David K Duvenaud, Dougal Maclaurin, Jorge Iparraguirre, Rafael Bombarell, Timothy Hirzel, Alan Aspuru-Guzik, and Ryan P Adams. Convolutional networks on graphs for learning molecular fin- gerprints. In Advances in Neural Information Processing Systems, volume 28, Curran Associates, Inc., 2015.
Vijay Prakash Dwivedi, Chaitanya K. Joshi, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Benchmarking graph neural networks. CoRR, abs/2003.00982, 2020.
Jack Edmonds and Richard M. Karp. Theoretical improvements in algorithmic efficiency for net- work flow problems. Journal of the ACM (JACM), 1972. doi: 00.1145332194.3211
Alex Fout, Jonathon Byrd, Basir Shariat, and Asa Ben-Hur. Protein interface prediction using graph convolutional networks. In Proceedings of the 31 International Conference on Neural Informa- tion Processing Systems, NIPS' 17, pp. 65336542, Red Hook, NY, USA, 2017. Curran Associates Inc. ISBN 1781510 10860964.
10

---

Under review as a conference paper at ICLR 2022
J. Gilmer, S. S. Schoenholz, P. F. Riley, O. Vinyals, and G. E. Dahl. Neural message passing for quantum chemistry. 70, 2017a.
Justin Gilmer, Samuel Schoenholz, Patrick Riley, Oriol Vinyals, and George E. Dahl. Neural message passing for quantum chemistry. In Proceedings of the 34th International Conference Machine Learning. volume 70 of Proceedings of Machine Learning Research, pp. 1263-1272. PMLR, 06-11 Aug 2017b.
Xavier Glorot and Yoshua Bengio. Understanding the difficulty of training deep feedforward neural networks. In Proceedings of the Thirteenthh International Conference on Artificial Intelligence and Statistics, volume of Proceedings of Machine Learning Research, pp. 249-256, Chia Laguna Resort, Sardinia, Italy, 13-15 May 2010. PMLR.
lan Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial nets. In Advances in Neural Infor- mation Processing Systems, volume 27. Curran Associates, Inc., 2014.
E. J. Gumbel. Statistical theory of extreme values and some practical applications: a series of lectures. US Govt. Print. Office, Number 33, 1954.
Rafael Gmez-Bombarelli, Jennifer N. Wei, David Duvenaud, Jos Miguel Hernndez-Lobato, Ben- jamn Snchez-Lengeling. Dennis Sheberla, Jorge Aguilera-Iparraguiree, Timothy D. Hirzel, Ryan Adams, and Aln Aspuru-Guzik. Automatic chemical design using a data-driven con- tinuous representation of molecules. ACS Central Science, 4(2):268-276 2018. doi: 10.1021/ acscentsci.7600072. PMID: 29532027.
David K. Hammond, Pierre Vandergheynst, and Rmi Gribonval. Wavelets on graphs via spec- tral graph theory. Applied and Computational Harmonic Analysis, 30(2): 150, 2011. ISSN 1063-5203. doi: https///dbioor//1..00...aaaaaaaa
URL https: /ttpps///ww.
sci sciencedi rect. com/ sc /ttp:///s...aeeaaaaaaa.e///////.
Martin Heusel, Hubert Ramsauer, Thomas Unterthiner, Bernhard Nessler, and Sepp Hochreiter. Gans trained by a two time-scale update rule converge to local nash equilibrium. In Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017.
P. Hohenberg and W. Kohn. Inhomogeneous electron gas. Phys. Rev., 136:864 871, 1964.
Truong Son Hy, Shubhendu Trivedi, Horace Pan, Brandon M. Anderson, , and Risi Kondor. Pre- dicting molecular properties with covariant compositional networks. The Journal of Chemical Physics, 148, 2018.
John Ingraham and Debora Marks. Variational inference for sparse and undirected models. In Pro- ceedings of the 34th International Conference on Machine Learning, volume 70 of Proceedings of Machine Learning Research, pp. 1607-1616. PMLR, 06-11 Aug 2017.
Eric Jang, Shixiang Gu, and Ben Poole. Categorical reparameterization with gumbel-softmax. In ICLR, 2017.
Wengong Jin, Regina Barzilay, and Tommi Jaakkola. Junction tree variational autoencoder for molecular graph generation. In Proceedings of the 35th International Conference Machine Learning, volume 80 of Proceedings of Machine Learning Research, pp. 2323-2332, PMLR, 10-15 Jul 2018.
Steven Kearnes, Kevin McCloskey, Marc Berndl, Vijay Pande, and Patrick Riley. Molecular graph convolutions: moving beyond fingerprints. Journal of Computer- Aided Molecular Design, 30(8): 595608, Aug 2016. ISSN 1573-4951. doi: 10. 1110077/110822--06-99988
Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In 3rd Inter- national Conference on Learning Representations, ICLR 2015, San Diego, CA, USA, May 7-9, 2015, Conference Track Proceedings, 2015.
Diederik P. Kingma and Max Welling. Auto-Encoding Variational Bayes. In 2nd International Conference on Learning Representations, ICLR 2014, Banff, AB, Canada, April 14-16, 2014, Conference Track Proceedings, 2014.
11

---

Under review as a conference paper at ICLR 2022
Thomas N. Kipf and Max Welling. Variational graph auto-encoders, 2016.
Alexej Klushyn, Nutan Chen, Richard Kurle, Botond Cseke, and Patrick van der Smagt. Learning hierarchical priors in vaes. In Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
Daphne Koller and Nir Friedman. In Probabilistic Graphical Models: Principles and Techniques. MIT Press, 2009.
Risi Kondor, Truong Son Hy, Horace Pan, Brandon M. Anderson, and Shubhendu Trivedi. Covariant compositional networks for learning graphs, 2018.
Nils M. Kriege, Pierre-Louis Giscard, and Richard C. Wilson On valid optimal assignment kernels and applications to graph classification. In Proceedings of the 30th International Conference on Neural Information Processing Systems. NIPS' 16, pp. 1623 1631, Red Hook, NY, USA, 2016.
Curran Associates Inc. ISBN 9781510838819.
Yann LeCun, Corinna Cortes, and Christopher J.C. Burges. The mnist database of handwritten digits. BRlLhtt::///ami lecun cww /xwm/m/idmmmiii
Yujia Li, Richard Zemel, Mare Brockschmidt, and Daniel Tarlow. Gated graph sequence neural networks. In Proceedings of ICLR' 16, April 2016.
Yujia Li, Oriol Vinyals, Chris Dyer, Razvan Pascanu, and Peter W. Battaglia. Learning deep gener- ative models of graphs. ICML'I8, 18, 00000443.,,334, 2018.
Renjie Liao, Yujia Li, Yang Song, Shenlong Wang, Will Hamilton, David Duvenaud, Raquel Urtasun, and Richard Zemel. Efficient graph generation with graph recurrent attention networks. In Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
Zinan Lin, Ashish Khetan, Giulia Fanti, and Sewoong Oh. Pacgan: The power of two samples in generative adversarial networks. In Advances in Neural Information Processing Systems, vol- ume 31. Curran Associates, Inc., 2018.
Jenny Liu, Aviral Kumar, Jimmy Ba, Jamie Kiros, and Kevin Swersky. Graph normalizing flows. In Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
Qi Liu, Miltiadis Allamanis, Mare Brockschmidt, and Alexander Gaunt. Constrained graph varia- tional autoencoders for molecule design. In Advances in Neurul Information Processing Systems, volume 31. Curran Associates, Inc., 2018
Jianxin Ma, Peng Cui, Kun Kuang, Xin Wang, and Wenwu Zhu. Disentangled graph convolutional networks. In Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pp. 4212-4221. PMLR, 09-15 Jun 2019.
Chris J Maddison, Daniel Tarlow, and Tom Minka. A sampling, In Advances in Neural Information Processing Systems, volume 27. Curran Associates, Inc., 2014.
Haggai Maron, Heli Ben-Hamu, Hadar Serviansky, and Yaron Lipman. Provably powerful graph networks. In Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019a
Haggai Maron, Heli Ben-Hamu, Nadav Shamir, and Yaron Lipman. Invariant and equivariant graph networks. In International Conference on Learning Representations, 2019b.
Haggai Maron, Ethan Fetaya, Nimrod Segol, and Yaron Lipman. On the universality of invariant networks. In Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pp.
PMLR, 09-15 Jun 2019c.
Haggai Maron, Or Litany, Gal Chechik, and Ethan Fetaya. On learning sets of symmetric elements. In Proceedings of the 37th International Conference Machine Learning, volume 1 119 of Pro- ceedings of Machine Learning Research, pp. 6734-6744, PMLR, 13-18 Jul 2020.
12

---

Under review as a conference paper at ICLR 2022
F. Monti, D. Boscaini, J. Masci, E. Rodola, J. Svoboda, and M. M. Bronstein. Geometric deep learn- ing on graphs and manifolds using mixture model cnns. 2017 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp. 5425-5434, Los Alamitos, CA, USA, jul 2017. IEEE Computer Society. doi: 10. (09/CCPR.2017.557
Kevin P. Murphy. Chapter 19: Undirected graphical models (markov random fields). In Machine Learning: Probabilistic Perspective, pp. 663-707, MIT Press, 2012.
M. Niepert, M. Ahmed, and K. Kutzkov. Learning convolutional neural networks for graphs. In Proceedings of the International Conference on Machine Learning, 2016a.
Mathias Niepert, Mohamed Ahmed, and Konstantin Kutzkov. Learning convolutional neural net- works for graphs. In Proceedings of The 33rd International Conference on Machine Learning, volume 48 of Proceedings of Machine Learning Research, pp. 2014-20233 New York, New York, USA, 20-22 Jun 2016b. PMLR.
B. Perozzi, R. Al-Rfou, and S. Skiena. Deepwalk: Online learning of social representations. Pro- ceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), pp. 701-710, 2014.
Alec Radford, Luke Metz, and Soumith Chintala. Unsupervised representation learning with deep convolutional generative adversarial networks, 2016.
Raghunathan Ramakrishnan, Pavlo O Dral, Matthias Rupp, and O Anatole von Lilienfeld. Quantum chemistry structures and properties of 134 kilo molecules. Scientific Data, 2014.
Rajesh Ranganath, Dustin Tran, and David Blei. Hierarchical variational models. In Proceedings of The 33rd International Conference on Machine Learning, volume 48 of Proceedings of Machine Learning Research, pp. 324-333, New York, New York, USA, 20-22 Jun 2016. PMLR.
Lars Ruddigkeit, Ruud van Deursen, Lorenz C. Blum, and Jean-Louis Reymond. Enumeration of 166 billion organic small molecules in the chemical universe database gdb-17. Journal of Chemical Information and Modeling, 52(1 (2111):2844222 2875, 2012. doi: 10.1021/ci300415l PMID: 23088335.
Havard Rue and Leonhard Held. Gaussian markov random fields: Theory and applications. In Monographs on Statistics and Applied Probability, volume 104, London, 2005, Chapman & Hall.
Raif Rustamov and Leonidas J Guibas. Wavelets on graphs via deep learning. In Advances in Neural Information Processing Systems, volume 26. Curran Associates, Inc., 2013.
Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini.
The graph neural network model. IEEE Transactions Neural Networks, 20(1):61-80, 2009. doi: 10.1000
Maximilian Seitzer. pytorch-fid -iorrchfidd: FID Score for PyTorch. httpp:://gituub.commmm hytorch-fidl August 2020. Version 0.1.1.
Sen, M. Namata, M. Bilgic, L. Getoor, B. Gallagher, , and T. Eliassi-Rad. Collective classifi- cation in network data. A/ Magazine, 29(3):93-106, 2008.
Hadar Serviansky, Nimrod Segol, Jonathan Shlomi, Kyle Cranmer, Eilam Gross, Haggai Maron, and Yaron Lipman. Set2graph: Learning graphs from sets. In Advances in Neural Information Processing Systems, volume 33, pp. 22080-22091. Curran Associates, Inc., 2020.
Nino Shervashidze, Pascal Schweitzer, Erik Jan van Leeuwen, Kurt Mehlhorn, and Karsten M. Borgwardt. Weisfeiler-lhmman graph kernels. Journal of Machine Learning Research, 12(77): 2539 2561, 2011.
Chence Shi, Minkai Xu, Zhaocheng Zhu, Weinan Zhang, Ming Zhang, and Jian Tang. Graphaf: flow-based autoregressive model for molecular graph generation. In International Confer- ence on Learning Representations, 2020. URL https://openzeval net/ fartt/oouune for.mmidrmm
S1 HlesMKHYPr
13

---

Under review as a conference paper at ICLR 2022
Donghyuk Shin, Si Si, and Inderjit S. Dhillon. Multi-scale link prediction. In Proceedings of the 21st ACM International Conference on Information and Knowledge Management, CIKM '12. pp. 215224, New York, NY, USA, 2012. Association for Computing Machinery. ISBN 9781450311 1564. doi: 10.1 145/2396761 .2396792.
Si Si, Donghyuk Shin, Inderjit S Dhillon, and Beresford N Parlett. Multi-scale spectral decompo- sition of massive graphs. In Advances in Neural Information Processing Systems, volume 27. Curran Associates, Inc., 2014.
Martin Simonovsky and Nikos Komodakis. Graphvae: Towards generation of small graphs using variational autoencoders. CoRR, abs/1 802.03420, 2018.
Akash Srivastava, Lazar Valkov, Chris Russell, Michael U. Gutmann, and Charles Sutton. Vee- gan: Reducing mode collapse in gans using implicit variational learning- In Advances in Neural Information Processing Systems, volume 30, Curran Associates, Inc., 2017.
Teague Sterling and John J. Irwin. Zinc 15 ligand discovery for everyone. Journal of Chemical Information and Modeling, (1111)):324-33377 2015. doi: 10.1021/acxjjiimm50005. PMID: 26479676.
L. Tang and H. Liu. Leveraging social media networks for classification. Data Mining and Knowl- edge Discovery, 23(3):477-77,, 2011.
Erik Henning Thiede, Truong Son Hy, and Risi Kondor. The general theory of permutation equiv- arant neural networks and higher order graph variational encoders. CoRR, abs/2004. 03990, 2020.
Arash Vahdat and Jan Kautz. Nvae: deep hierarchical variational autoencoder. In Advances in Neural Information Processing Systems, volume 33, pp. 19667-19679. Curran Associates, Inc., 2020.
Petar Velikovi, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Li, and Yoshua Ben- gio. Graph attention networks. In International Conference on Learning Representations, 2018.
Martin J. Wainwright and Michael I. Jordan. A variational principle for graphical models. New Directions in Statistical Signal Processing, 2005.
Hao Wu, Jonas Köhler, and Frank Noe. Stochastic normalizing flows. In Advances in Neural Information Processing Systems, volume 33, pp. 5933-5944. Curran Associates, Inc., 2020.
Bingbing Xu, Huawei Shen, Qi Cao, Yunqi Qiu, and Xueqi Cheng. Graph wavelet neural network.
In International Conference on Learning Representations, 2019.
Yiding Yang. Zunlei Feng, Mingli Song, and Xinchao Wang. Factorizable graph convolutional networks. In Advances in Neural Information Processing Systems, volume 33, pp. 20286-20296. Curran Associates, Inc., 2020.
Zhitao Ying, Jiaxuan You, Christopher Morris, Xiang Ren, Will Hamilton, and Jure Leskovec. Hi- erarchical graph representation learning with differentiable pooling. In Advances in Neural Infor- mation Processing Systems, volume 31. Curran Associates, Inc., 2018
Jiaxuan You, Rex Ying, Xiang Ren, William Hamilton, and Jure Leskovec. GraphRNN: Generat- ing realistic graphs with deep auto-regressive models. In Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pp. 5717. PMLR, 10-15 Jul 2018a
Jiaxuan You, Rex Ying. Xiang Ren, William L. Hamilton, and Jure Leskovec. Code for graphrnn: Generating realistic graphs with deep auto-regressive model. 2018b.
Manzil Zaheer, Satwik Kottur, Siamak Ravanbakhsh, Barnabas Poczos, Russ R Salakhutdinov, and Alexander Smola. Deep sets. In Advances in Neural Information Processing Systems, vol- ume 30. Curran Associates, Inc., 2017.
Dawei Zhou, Lecheng Zheng, Jiejun Xu, and Jingrui He. Misc-gan: A multi-scale generative model for graphs. Frontiers in Big Data, 2:3, 2019. ISSN 909X. doi: 10.3389/fdata. 20199.0000 URL wwwww front http:///wwwooo.oooooooooooooooaa 201...20.000000000 00003
2019
14

---

Under review as a conference paper at ICLR 2022
A BASIC TENSOR OPERATIONS
In order to build higher order equivariant networks, we revisit some basic tensor operations: tensor product (see Def. I0) and tensor contraction (see Def. [T]. It can be shown that these tensor opera- tions respect permutation equivariance. Based on them, we build our second order message passing networks.
Definition 10. The tensor product of A R= with B I yields tensor C - B R where
Cip A Biinskuiannnaa
Definition 11. The contraction of E TRn along the pair of dimensions (x, y} (assuming x < y) yields (a- 2) order tensor
Cityrbb-1: 1ihheiioo 1
Σ Ai
fziby
where we assume that iz and iy have been removed from amongst the indices of C. Using Einstein notation, this can be written more compactly as
Ci ba) Aan 8ta
where 5 the Kronecker delta. In general, the contraction of along dimensions (T11",(p)) yields tensor C = Auxi... R where
A Aa
ΣΣ... ...
A.
f21 222
or compactly
A A
Ai 8' daginea
B MARKOV RANDOM FIELDS
Undirected graphical models have been widely applied in the domains spatial or relational data, such image analysis and spatial statistics. In general, k-thh order graph encoders encode an undi- rected graph g (V,E) into a k-th order latent z ε R "d"xx,, xd, with learnable parameters 0, can be represented parameterized Markov Random Field (MRF) Markov network. Based the Hammersley-Cliife -Ciifford theorem (Murphy) 2012) (Koller & Friedman, 2009), positive distribution p(=) > satisfies the conditional independent properties of an undirected graph G iff p can be represented product of potential functions v/, one per maximal clique, i.e.,
1 7(0)
p==10)=
πI (2c((0)
(10)
CEC
where C is the set of all the (maximal) eliques of G. and Z(0) is the fartitionfunntion to ensure the overall distribution sums and given by
Z(0)
Σπ (ze(00.
eEC
Eq. 10 can be further written down
0==10)=
Il vi (z. DeV
II (s.f)cg
Vel(=sc)))
II
(=
where vyr Var and the are the first order, second order and k-th order outputs of the encoder, cor- responding to every vertex in V, every edge in & and every clique of size k C₁. respectively. However, factorizing a graph into set of maximal cliques has exponential time complexity, since the problem of determining if there a clique size & in a graph known as an NP-complete problem. Thus, the factorization based Hammersley- Hammeesley-Cliffordd theorem is intractable. The second order encoder relaxes the restriction of maximal clique into edges, that is called as pairwise MRF;
p(=(0)=
II g-t
the (2s,
15

---

Under review as a conference paper at ICLR 2022
Our second order encoder inherits Gaussian MRF introduced by (Rue & Held 2005) as pairwise MRF of the following form
p=200) oc W.s((s (x())))
ayt
where (se 2t) exp (- 22 is the edge potential, and (2) exp A + m)²e) is the vertex potental. The joint distribution can be written in the information form of multivariate Gaussian in which
A = A
n= A/
p(200) oc exp
"
A=
(1I)
is the same as sampling from the multivariate Gaussian (μ, 2) To ensure end-to-end equivariance, we set the latent layer to be two tensors μ e IRaxd, and e Raxaxd, that corresponds to dz multivariate Gaussians, whose first index, and second index are first order and second order equivariant with permutations. Computation of Σ is trickier than μ, simply because Σ must be invertible to be covariance matrix. Thus, second order encoder produces tensor L the second order activation, and set E LL"". The reparameterization trick from Kingma & Welling (2014) is changed to
Sampling z from (==(0) in Eq.
== + Le,
E~N(0,1)
C EQUIVARIANT LEARNABLE PRIOR
The original VAE published by Kingma & Welling (2144) limits each covariance matrix E to be diagonal and the prior to be (0, 1). Our second order encoder removes the diagonal restriction on the covariance matrix. Furthermore, we allow the prior (i, ((a Σ) to be learnable in which j and E are parameters optimized by back propagation in a data driven manner. Importantly Ê cannot be learned directly due to the invertibility restriction. Instead, similarly to the second order encoder, a matrix L is optimized, and the prior covariance matrix is constructed by setting E -LL". The Kullback Leibler divergence between the two distributions N N(v, Σ) and N(2, Σ) as follows:
DKI(N(H, ()) ED) = (x Σ) (A- (a (4) n +I
det det
(12)
Even though Σ is invertible, but gradient computation through the KL-divergence loss can be nu- merical instable because of Cholesky decomposition procedure in matrix inversion. Thus, we add neglectable noise 10-1 to the diagonal of both covariance matrices.
Importantly, during training, the KL--divergence loss breaks the permutation equivariance. Suppose the set of vertices are permuted by permutation matrix P, for Sn, Since μ and Σ are the first order and second order equivariant outputs of the encoder, they are changed to P o and P EPE accordingly. But
(N,,, ()) E)) D (NPP.,,
E))
To address the equivariance issue, we want to solve the following convex optimization problem that our new equivariant loss function
min T
DRa(N(P P.EP. (W E))
(13)
computationally expensive. One solution is to solve the minimum-cost cost maximum maximum-matching in a bipartite graph (Hungarian matching) with the cost matrix C,₃ I|и أ by O(n²) algorithm published by Edmonds Karp (1972). that can be still improved further into O(n"). The Hungarian matching preserves equiariance, but is still computationally expensive. In practice, instead of finding optimal permutation, we apply a free-matching scheme to find an assignment matrix II such that: Iy if and only if j arg min, ||u; Azll for each i [1. The free-matching scheme preserves equivariance and can be done efficiently in simple (n??) algorithm that is also suitable for GPU computation.
However, solving the optimization based on Eq.
16

---

Under review as a conference paper at ICLR 2022
D EXPERIMENTS
D.1 LINK PREDICTION ON CITATION GRAPHS
We demonstrate the ability of the MGVAE models to learn meaningful latent embeddings on link prediction task on popular citation network datasets Cora and Citeseer (Sen et al., 2008). At training time, 15% of the citation links (edges) were removed while all node features are kept, the models are trained on an incomplete graph Laplacian constructed from the remaining 85% of the edges. From previously removed edges, we sample the same number of pairs of unconnected nodes (non-edges). We form the validation and test sets that contain 5% and 10% of edges with an equal amount of non-edges, respectively.
We compare model MGVAE against popular methods in the field:
1. Spectral clustering (SC) (Tang & Liu
2011
2. Deep walks (DW) (Perozzi et al.
2014
3. Variational graph autoencoder (VGAE) (iipf Welling 2016)
on the ability to correctly classify edges and non-edges using two metries: area under the ROC curve (AUC) and average precision (AP). Numerical results of SC and DW are experimental settings are
taken from (Kipf & Welling. 2016). We reran the implementation of VGAE as in (Kipf & Welling 2016).
For MGVAE, initialize weights by Glorot initialization (Glorot & Bengio 2010). We repeat the experiments with different random seeds and calculate the average AUC and AP along with their standard deviations. The number of message passing layers ranges from 4. The size of latent representation is 128. The number of coarsening levels is L (3.7). In the é-th coarsening level, we partition the graph g(9) into 2 (for L = 7) or 4f (for L = 3) clusters. We train for 2,048 epochs using Adam optimization (Kingma Ba| 2015) with starting learning rate of 0.01. Hyperparameters optimization (e.g. number of layers, dimension of the latent representation, etc.) is done on the validation set. MGVAE outperforms all other methods (see T).
We propose our learning to cluster algorithm to achieve the balanced K-cut at every resolution level. Besides, we also implement two fixed clustering algorithms:
1. Spectral: It is similar to the one implemented in (Rustamov & Guibas 2013).
First, we embed each node i E V into Rf (i))a)aa))) Snmaas (i) A (i)), where {An En ) are the cigen-pairs of the graph Laplacian C D (D-A) where
Di EyAij. Aij. We assume that Ày .. Anmax In this case, 7mar 10. At the 8-th resolution level, we apply the K-Means clustering algorithm based on the above node embedding partition graph g(
2. K-Means:
First, we apply PCA to compress the sparse word frequency vectors (of size 1,433 on Cora and 3,703 on Citeseer) associating with each node into 10 dimensions.
We use the compressed node embedding for the K-Means clustering.
Tables and 5 show that our learning cluster algorithm returns much more balanced cut on the highest resolution level comparing to both Spectral and K-Means clusterings. For instance, we
Table 3: Citation graph link prediction results (AUC & AP)
Dataset
Cora
Citeseer
Method
AUC (ROC)
AP
AUC (ROC)
SC
84.6 0.01
88.5 1 0.00
80.5 1 0.01
85.0
DW
83.1 + 0.01
85.0 0.00
80.5 0.02
83.6 0.01
VGAE
90.97 a 0.77
91.88
0.83
89.63 1.04
91.10 4 1.02
MGVAE (Spectral)
91.19 = 0.76
92.27 = 0.73
90.55 + 1.17
91.89 + 1.27
MGVAE (K-Mcans)
93.07 = 5.61
92.49 = 5.77
90.81
1.19
91.98 # 1.02
MGVAE
95.67 3.11
95.02
3.36
93.93 5.87
93.06 6.33
17

---

Under review as a conference paper at ICLR 2022
Method
Min
Max
STD
KL divergence
Spectral
2020
177.52
3.14
K-Means
364
40.17
0.84
Learn to cluster
10
36
4.77
0.02
Table 4: Learning to cluster algorithm returns balanced cuts on Cora.
Method
Min
Max
STD
KL divergence
Spectral
3320
292.21
4.51
K-Means
326
41.69
0.74
Learn cluster
38
4.93
0.01
Table 5:
Learning to cluster algorithm returns balanced cuts on Citeseer.
have L = 7 resolution levels and we partition the E-th resolution into K = 2 clusters. Thus, on the bottom levels, we have 128 clusters. we distribute nodes into clusters uniformly. the expected number of nodes in a cluster is 21.15 and 25.99 on Cora (2, 708 nodes) and Citeseer (3, 327 nodes), respectively. We measure the minimum, maximum, standard deviation of the numbers of nodes in 128 clusters. Furthermore, we measure the Kullback-Lein nodes into clusters and the uniform distribution. Our learning to cluster algorithm achieves low KL losses of 0.02 and 0.01 Cora and Citeseer, respectively.
divergence between the distribution of
D.2 MOLECULAR GRAPH GENERATION
In this case, MGVAF and MGN are implemented with T, = 3 resolution levels, and the ê-th resolution graph is partitioned into K 2 clusters. On each resolution level, the local encoders and local decoders are second-order S, -qquivaria networks with up to equivariant layers. The number of channels for each node latent de is 256. We apply approaches for graph decoding:
1. All-at-once: MGVAE reconstructs all resolution adjacencies by equivariant decoder net- works. Furthermore, we apply learnable equivariant prior in Sec. [ Our second order encoders are interpreted Markov Random Fields (see Sec. B). This approach preserves permutation equivariance. In addition, we implement a correcting process: the decoder network of the highest resolution level returns probability for each edge, we sort these probabilities in a descending order and gradually add the edges that order to satisfy all chemical constraints. Furthermore, S,,-equivariant decoder by replacing it by a multilayer perceptron (MLP) decoder with hidden layers of size 512 and sigmoid nonlinearity. We find that the higher order decoder outperforms the MLP decoder given the same encoding architecture. Table 6 shows the comparison between the decoding models.
investigate the expressive power of the second order
2. Autoregressive: This decoding process is constructed in an autoregressive manner simi- larly to et al. 2018). First, we sample each vertex latent a independently. We randomly select starting node th. then apply Breath First Search (BFS) to determine particular node ordering from the node Up. however that breaks the permutation equivariance. Then iteratively we add/sample new edge to the existing graph G. at the (-th iteration (given randomly selected node Un as the start graph Gn) until completion. We apply second-order MGN with gated recurrent architecture to produce the probability of edge (u, B) where one vertex u is in the existing graph Gr and the another one is outside; and also the probability of its label. Intuitively, the decoding process is sequential classification.
We randomly select 10,000 training examples for QM9; and 1,000 (autoregressive) and 10,000 (all- at-once) training examples for ZINC. important to note that our training sets are much smaller comparing to other methods. For all of our generation experiments, we only use graph features as the imput for the encoder such as one-hot atomic types and bond types. Since ZINC molecules are larger then QM9 ones, it is more difficult to train with the second order S, -quiivarri decoders predictions or the number of entries in the adjacency matrices
(e.g.. the number of bond/non-boot proportional to squared number of nodes). Therefore, input several chemical/atomie features
18

---

Under review as a conference paper at ICLR 2022
Dataset
Method
Validity
Novelty
Uniqueness
MLP decoder
100%
99.98%
77.62%
QM9
Sn decoder
100%
100%
95.16%
Table 6: All-at-once MGVAE with MLP decoder vs. second order decoder.
Feature
Type
Number
Description
GetAtemicNum
Integer
Atomic number
Is IsInRing
Boolcan
Belongs to a ring?
IsInRingSize
Boolean
9
Belongs to ring of size & (1,.., 9}?
Get.sAromatic
Boolean
Aromaticity?
GetDegree
Integer
Vertex degree
GetExpliccitVllnce
Integer
Explicit valance
GetFormalCharge
Integer
Formal charge
GetIsotopp
Integer
Isotope
GetMass
Double
Atomic mass
GetNolmplicit
Boolean
Allowed have implicit Hs?
Get:NumExplicitB3
Integer
Number of explicit Hs
GetNumimmpliictss
Integer
Number of implicit Hs
GetNumnRddicslBleettross
Integer
Number radical electrons
GetTotalDegree
Integer
Total degree
GetTotalNuriis
Integer
Total number of Hs
GetTotalValence
Integer
Total valance
Table 7: The list of chemical/atomic features used for the all-at-once MGVAE on ZINC. We denote each feature by its API in RDKit.
computed from RDKit for the all-at-once MGVAE on ZINC (see Table 7. We concatenate all these features into vector of size 24 for each atom.
We train our models with Adam optimization method (Kingma & Ba 2015) with the initial learning rate of 10 Figs. and show some selected examples out of 5,000 generated molecules on QM9 by all-at-once MGVAE, while shoos the molecules generated by autoregressive MGN. Qual- itatively, both the decoding approaches capture similar molecular substructures (bond structures). F showws an example of interpolation on the latent space on ZINC with the all-at-once MGVAE Fig. shows some generated molecules on ZINC by the all-at-once MGVAF. Fig. and table show some generated molecules by the autoregressive MGN on ZINC dataset with high Quantita- tive Estimate of Drug-Likeness (QED) computed by RDKit and their SMILES strings. On ZINC, the average QED score of the generated molecules is 0.45 with standard deviation 0.21. On QM9, the QED score is 0.44 + 0.07.
D.3 GENERAL GRAPH GENERATION BY MGVAE
Figs. 10 II show some generated examples and training examples the 2-community and ego datasets, respectively.
D.4 UNSUPERVISED MOLECULAR PROPERTIES PREDICTION ON QM9
Density Function Theory (DFT) is the most successful and widely used approach of modern quan- tum chemistry to compute the electronic structure of matter, and calculate many properties of molecular systems with high accuracy (Hohenberg & Kohn 1964). However, DFT is computa- tionally expensive (Gilmer al.) (0077)), that leads to the use of machine learning estimate the properties of compounds from their chemical structure rather than computing them explicitly with DFT (Hy al. 2018). To demonstrate that MGVAE can learn useful molecular representations and capture important molecular structures in unsupervised and variational autoencoding manner, extract the highest resolution latents (at & L) and use them the molecular representations for the downstream tasks of predicting DFT's molecular properties on QM9 including 13 learning
19

---

Under review as a conference paper at ICLR 2022
Figure 4: Some generated examples on QM9 by the all-at-once MGVAE with second order S., equivariant decoders.
Figure 5: Some generated examples on QM9 by the all-at-once MGVAE with MLP decoder instead of the second order -quiiiarrr one. It generates more tree-like structures.
20

---

Under review as a conference paper at ICLR 2022
NH
OH
OH
OH
NH
HnN
Figure 6: Some generated examples on QM9 by the autoregressive MGN.
911
N1
Some generated examples on ZINC by the all-at-once MGVAE with second order S,,- cquivariant decoders. In addition of graph features such one-hot atomic types, include several chemical features computed from RDKit (as in Table 7 as the input for the encoders. A generated example contain more than connected components, each of them is a valid molecule.
Figure 7:
21

---

Under review as a conference paper at ICLR 2022
0.711.711
=
0
QED
HD
QED 0.879
QED 0.805
QED = 0.769
QED = 0.710
QED 0.790
QED
QED= = 0.859
QED 0.730
QED 0.901
QED 0.729
QED 0.703
QED 0.855
QED 0.895
QED 0.809
Figure 8:
Some generated molecules on ZINC by the autoregressive MGN with high QED (drug-
likeness score).
22

---

Under review as a conference paper at ICLR 2022
Row
Column
SMILES
O=CINGCCCCCcc2HH|mmmgg
3
4
COCCEZENTECCCTJCCCCCCCCCCOOOOO
2 (SFONNICCSHICCCCCNNZZZZ22
3 CECCIISSHICDNNNCCCCCc:/CCCCCDCC
4 CCITAEEETTONNITA-CCCOOIIISSESOOO
2
3
4
3
4 COCCNGGelec2ccce22n]]]
3
PEAEDDDNNEEONNNCCcccc22ooo22222 OsCIISSccccc/CUsssXNNNNNVVV
4
Table 8: SMILES of the generated molecules included in Fig. g
Online drawing tool:
https:
/ //pubchem. ncbi mlm. nih. gww.///dit.//ndeex html
Figure 9: Interpolation the latent space: we randomly select two molecules from ZINC and we reconstruct the corresponding molecular graphs on the interpolation line between the two latents.
Figure 10: The top row includes generated examples and the bottom row includes training examples on the synthetic 2-community dataset.
23

---

Under review as a conference paper at ICLR 2022
Generated examples
Training examples
Figure 11: EGO-SMALL.
24

---

Under review as a conference paper at ICLR 2022
Target
Unit
Mean
STD
Description
bohr
75,2808
8.1729
Norm of the static polarizability
CF
cal/mol/K
31.6204
4.0674
Heat capacity at room temperature
eV
-70.8352
9.4975
Free energy of atomization
gap
eV
6.8583
1.2841
Difference between HOMO and LUMO
H
cV
-77.0167
10.4884
Enthalpy of atomization at room temperature
HOMO
cV
-6.5362
0.5977
Highest occupied molecular orbital
LUMO
eV 0.3220
1.2748
Lowest unoceupied molecular orbital
D
2.6729
1.5034
Norm of the dipole moment
W1
cm
3504.1155
266.8982
Highest fundamental vibrational frequency
R
bohr" 1189,4091
280,4725
Electronic spatial extent
eV
-76,5789
10.4143
Atomization energy at room temperature
Uo
eV -76.1145
10.3229
Atomization energy at O.K
ZPVE
eV
4.0568
0.9016
Zero point vibrational energy
Table 9: Description and statisties of 13 learning targets on QM9,
alpha
gap
HOMO
LUMO
mu
omegal
R2
U
U0
ZPVE
WL
3.75
2.39
4.84
0.92
5.45
0.38
0.89
1.03
192
154
5,41
5.36
0.51
NGF
3.51
1.91
4.36
0.86
4.92
0.34
0.82
0.94
168
137
4.89
4.85
0.45
PSCN
1.63
1.09
3.13
0.77
3.56
0.30
0.75
0.81
152
61
3.54
3,50
0.38
CCN 2D
1.30
2.75
0.69
3.14
0.23
0.72
120
53
3.02
2.99
0.35
MGVAE
2.83
0.91
1.78
0.66
1.87
0.34
0.58
0.95
193
90
1.89
1.90
0.14
Unsupervised molecular representation learning by MGVAE to predict molecular prop- erties calculated by DFT on QM9 dataset.
Table 10:
targets. For the training, normalize all learning targets to have mean 0 and standard deviation 1. The name, physical unit, and statistics of these learning targets are detailed in Table
The implementation of MGVAE is the same as detailed in Sec. D.2 MGVAE trained to reconstruct the highest resolution (input) adjacency, its coarsening adjacencies and the node atomic features. In this case, do not any chemical features: the node atomic features are just one-hot atomic types. After MGVAE is converged, to obtain the -nvinrrii molecular representation, we average the node latents the L-th level into vector of size 256. Finally, we apply simple Multilayer Perceptron with hidden layers of size 512, sigmoid nonlinearity and a linear layer on top to predict the molccular properties based on the extracted molecular representation. We compare the results in Mean Average Error (MAE) in the corresponding physical units with four methods on the same split of training and testing from (Hy et al. 2018):
1. Support Vector Machine optimal-as Weisfeiler-Lehman (WL) graph kernel (Shervashidze et al.) 2011) (Kriege et al. 2016)
2. Neural Graph Fingerprint (NGF) (Duvenaud et al. 2015)
3. PATCHY-SAN (PSCN) (Niepert et al. 2016a)
4. Second order S, -qquivarri Covariant Compositional Networks (CCN 2D) (Kondor al. 2018) (Hy et al. 2018)
Our unsupervised results show that MGVAE is able to learn a universal molecular representation in an unsupervised manner and outperforms WL in 12. NGF in 10, PSCN in 8, and CCN 2D in out of 13 learning targets, respectively (see Table 10). There are other recent methods in the field that use several chemical and geometric information but comparing them would be unfair.
D.5 SUPERVISED MOLECULAR PROPERTIES PREDICTION ON ZINC
To further demonstrate the comprehensiveness of MGN, we apply our model in supervised regres- sion task to predict the solubility (LogP) on the ZINC dataset. We the same split of K/K/
25

---

Under review as a conference paper at ICLR 2022
Method
MLP
GCN
GAT
MoNet
DiscenGC.N
FactorGCN 0.366
GatedGCNg
MGN
MAE
0.667
0,503
0.479
0.407
0.538
0.363
0.290
Table 11: Supervised MGN to predict solubility ZINC dataset.
for traiiingvvalidationnesstnngg as in (Dwivedi al., 2020). The implementation of MGN is almost the same as detailed in Sec. [.2] except we include the latents of all resolution levels into the pre- diction. In particular, each resolution level, we average all the node latents into a vector of size 256; then we concatentate all these vectors into long vector of size 256 x L and apply linear layer for the regression task. The baseline results are taken from YYang et al. 2020) including:
1. Multilayer Perceptron (MLP),
2. Graph Convolution Networks (GCN),
3. Graph Attention Networks (GAT) (Velikovi et al. 2018).
4. MoNet (Monti et al. 2017).
5. Disentangled Graph Convolutional Networks (DisenGCN) (Ma et al. 2019).
6. Factorizable Graph Convolutional Networks (FactorGCN) (Yang al. 2020).
7. GatedGCN Dwivedi al., 2020) that uses additional edge information.
Our supervised result shows that MGN outperforms the state-of-the-art models in the field with margin of 20% (see Table
D.6 GRAPH-BASED IMAGE GENERATION BY MGVAE
In this additional experiment, we apply MGVAE into the task of image generation. Instead of matrix representation, an image / E IR Hx W node represents pixel, each edge is between two neighboring pixels, and each node feature the corresponding pixel's ' color (e.g., IR in gray scale, and R in RGB scale). Fig. 12 demonstrates an exmaple of graph representation for images. Since images have natural spatial clustering, instead of learning to cluster, we implement a fixed clustering procedure as follows:
is represented by a grid graph of H W nodes in which each
For the f-th resolution level, divide the grid graph of size H10,, W(O) into clusters of size h x w that results into grid graph of size "A x w supposingly and w are divisible by H()) and W(O), respectively. Each resolution is associated with image 7(1) that is zoomed out version of ((6-1)
The global encoder e!!) is implemented with 10 layers of message passing that operates on the whole ( x W(O) grid graph. We sum up all the node latents into a single latent vector (1)) e dR= The global decoder (d) is implemented by the convolutional neural network architecture of the generator of DCGAN model (Radford et al. 2016) to map z()) into an approximated image i(() The S,, -nvvariat pooler p is a network operating on each small h grid graph to produce the corresponding node feature for the next level E 1. MGVAE is trained to reconstruct all resolution images. Fig. [3] shows an example of reconstruction each resolution on test image of MNIST (after the network converged).
We evaluate MGVAE architecture the MNIST dataset (LeCun et al.) with 60,000 training examples and 10,000 testing examples. The original image size is 28 x 28. We pad zero pixels to get the image size of 2 x 2 (e.g., (5) W(5) 32). Fach cluster is a small grid graph of size 2 x (e.g., h this case, the whole network architecture is 2-dimensional quadtree. The latent size dy is selected 256. We train our model for 256 epochs by Adam optimizer (Kingma Bal 2015) with the initial learning rate 10-3 In the testing process, for the ε-th resolution, we sample a random vector of size d, from prior N (O, 1) and use the decoder (( to decode the corresponding image. We generate 10,000 examples for each resolution. We compute the Frechet Inception Distance (FID) proposed by (Heusel et al. 2017) between the testing set and the generated set as the metric to evaluate the quality
2). Accordingly, the image sizes for all resolutions are 32 32, 16 16, 8 8, etc. In
26

---

Under review as a conference paper at ICLR 2022
Method
FID, (32 x2)
FID, (16 16)
FID; (8 8)
DCGAN
113.129
VEEGAN
68.749
N/A
N/A
PACGAN
58.535
PresGAN 42.019
MGVAE
39.474
64.289
39.038
Quantitative evaluation of the generated set by FID metric for each resolution level on MNIST. It is important to note that the generation for each resolution is done separately: for the L-th resolution, we sample random vector of size dz 256 from (0, 1), and use the global decoder ((e) to decode into the corresponding image size. The baselines are taken from (Dieng et al. 2019
Table 12:
Figure 12:
An image of digit 8 from MNIST (left) and its grid graph representation at 16 16 resolution level (right).
of our generated examples. We use the FID implementation from (Seiterr 2020). We compare our MGVAE against variants of Generative Adversarial Networks (GANs) Goodfellow al. 2014 including DCGAN (Radford et al., 2016). VEEGAN (Srivastava et al. 2017). PacGAN (Lin et al. 2018 and PresGAN (Dieng et al., 2219). Table 12 shows our quantitative results in comparison with other competing generative models. The baseline results are taken from Prescribed Generative
Adversarial Networks paper (Dieng et al. 2019). MGVAE outperforms all baselines for the
highest resolution generation. Figs. 14 and
15 show some generated examples of the 32 x 32 and
16 resolution, respectively.
27

---

Under review as a conference paper at ICLR 2022
32 32
16 16
8 8
4
4
Target
4
4
Reconstruction
Figure 13: An example
reconstruction on each resolution level for a test image in MNIST,
2
6
9
3
2
3
5
3
q
/
7
5
3
5
8
9
9
3
4
1
2
/
6
3
2
7
3
2
3
B
6
4
3
8
7
5
3
2
5
7
7
0
8
5
9
3
2
3
8
6
9
8
2
8
1
7
9
4
2
9
2
8
7
4
9
3
0
9
3
3
3
1
8
2
7
7
4
2
0
2
3
3
4
0
8
9
3
7
4
9
8
8
1
5
3
2
7
3
9
3
9
3
0
5
Q
6
3
8
0
3
5
9
6
8
2
6
9
5
0
9
4
7
Figure 14: Generated examples at the highest 32 32 resolution level.
28

---

Under review as a conference paper at ICLR 2022
1
]
9
6
8
7
2
7
3
9
0
5
7
G
5
1
0
9
0
9
9
9
3
2
2
0
0
8
7
7
/
6
5
9
3
0
9
9
2
3
O
7
5
8
9
7
3
3
6
8
9
9
9
7
6
!
9
O
8
2
,
6
2
5
/
9
]
2
9
7
5
9
3
g
7
1
7
7
6
2
5
8
0
9
0
6
O
7
9
i
7
3
i
8
6
g
8
3
'
2
0
6
9
8
9
6
0
l
1
0
2
9
O
0
3
1
6
o
9
9
9
9
9
5
9
/
7
6
9
8
9
Figure 15:
Generated examples at the 16 x 16 resolution level.
29


Reviews:
[{"review_id": "xsA119KswLW", "reviewer": "Reviewer_9mH3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\n\n+ MGVAE is the first hierarchical generative model to learn and generate graphs both in a multiresolution and in an equivariant manner. \n+ Lots of experimental results. \n\n\nWeaknesses:\n\nThe paper needs a more compelling motivation for why the authors' specific approach to  generating graphs in a multiresolution and in an equivariant  manner is important, or why is it important to employ VAE, given that the (i) the idea of studying the properties of graphs via the eigenvalues and eigenvectors of their associated graph matrices at different resolutions is not novel, and neither is the (ii) permutation equivariance of graph neural networks .   \n\nThe authors have asserted  that it is desirable to have (1) balanced K-cluster partition, (2)  local encoders which the authors have asserted tend to generalize better for same-size subgraphs and (3) uniform distribution of nodes into clusters. This maybe something observed by the authors in their specific application, but it is not generally true.\n\nIn imaging, nodes( pixels) are assigned adaptatively to clusters based on high gradients or high curvatures which results in clusters of different sizes and at different locations.  \n\nWhy not perform an adaptive clustering by employing graph downsampling, graph reduction, and filtering and interpolation of signals on graphs?\n\n\n\nVasilescu20 and Vasilescu19 introduced a multiresolution hierarchical tensor factorization that model the mechanism that generated the data formation and employs a hierarchy of latent variables where the nodes (pixels) can be assigned to clusters based on adaptive strategy. They applied this approach to face recognition (Vasilescu02) and developed a generative multiresolution hierarchical TensorFaces model (Vasilecu19, Vasilescu20).\n\n\n@inproceedings{Vasilescu20,\n\nauthor={Vasilescu, M. Alex O. and Kim, Eric and Zeng, Xiao S.},\nbooktitle={2020 25th International Conference of Pattern Recognition (ICPR 2020)},\ntitle={Causal{X}: {C}ausal e{X}planations and {B}lock {M}ultilinear {F}actor {A}nalysis},\nyear={2021},\nlocation={Milan, Italy},\nmonth={Jan},\npages={10736--10743}\n}\n\n@misc{Vasilescu19,\n\nauthor={Vasilescu, M. Alex O. and Kim, Eric},\nbooktitle={The 25th ACM SIGKDD Conf. on Knowledge Discovery and Data Mining (KDD’19): Tensor Methods for Emerging Data Science Challenges Workshop},\ntitle={Compositional Hierarchical Tensor Factorization: Representing Hierarchical Intrinsic and Extrinsic Causal Factors},\nyear={2019},\nlocation={Anchrorage,AK},\nmonth={Aug. 5}, \n}\n\n\n@inproceedings{Vasilescu02,\n\n  author =\t \"M. A. O. Vasilescu and D. Terzopoulos\",\n  fullauthor =\t \"M. Alex O. Vasilescu and Demetri Terzopoulos\",\n  title =\t \"Multilinear Analysis  of Image Ensembles: {T}ensor{F}aces\",\n  booktitle =\t \"Proc. European Conf. on Computer Vision (ECCV 2002)\",\n  address =\t \"Copenhagen, Denmark\",\n  month =\t \"May\",\n  year =\t \"2002\",\n  pages =\t \"447-460\"\n}", "summary_of_the_paper": "The authors propose Multiresolution Graph Networks (MGN) and Multiresolution Graph Variational Autoencoders (MGVAE) to learn and generate graphs in a multiresolution and equivariant manner that has been applied to citation data, molecular data and  MNIST imaging data.   ", "summary_of_the_review": "MGVAE is the first hierarchical generative model to learn and generate graphs both in a multiresolution and in an equivariant manner.  The experiments are extensive.  The paper needs a stronger motivation for why the authors' specific approach is important considering  that (i) the idea of studying the properties of graphs via the eigenvalues and eigenvectors of their associated graph matrices at different resolutions is not novel, and neither is the (ii) permutation equivariance of graph neural networks \n\n\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "tpqwvHukQf", "reviewer": "Reviewer_867y", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths\n\n- The proposed method is presented in a very clear and structured way.\n\n- The approach is well-motivated, adapting and integrating aspects of various other work (VAEs, learnable hard clusterings, balanced cuts, etc.) in a seamless manner.\n\n- By being designed to be inherently permutation-equivariant with respect to node ordering, the MGVAEs lend themselves well for graph encoding and generation in a multiscale fashion.\n\n- The proposed method constitutes a novel approach towards generating graphs.\n\nWeaknesses\n\n- The work by Jin et al. (ICML 2020) seems highly relevant in the context of the proposed method. Similar to the proposed approach, they adapt VAEs for the task of hierarchical predictions of molecular graphs in a coarse-to-fine fashion. While there are of course clear differences between the approaches, a discussion of and comparison with that work seems essential for the proposed method.\n\n- In the abstract, the authors claim competitive results in graph generation, molecular generation, unsupervised molecular representation learning, link prediction on citation graphs, and graph-based image generation. However, the evaluation of the proposed method seems limited, especially in the main paper. For example, for the task of molecular graph generation, only validity, novelty, and uniqueness of the generated molecules are evaluated. Why are no additional metrics from standardised benchmarks for molecular generation evaluated (cf. Polykovskiy et al., 2018)?\nFurther, other work that has scored higher on the Citeseer dataset has been left out of the comparison (e.g., Davidson et al. 2018). The way in which the results are presented suggest that no better methods exist. I can understand if the goal of the results is to merely highlight competitive performance with respect to ‘popular’ methods and not to claim state of the art performance. However, putting the results into context with respect to the current state of the art still seems important to gauge the presented method properly. \n\n- The authors extend the prior of the VAEs from an isotropic Gaussian to a parameterized Gaussian with learnable mean and covariance. While this constitutes an interesting extension, the importance for the task at hand is unclear to me. What effect does this have on the learnability of the tasks or on performance?\n\n- The authors highlight that the approach allows to generate graphs at various levels of resolution. Under which circumstances might this be useful? What is the meaning of a low-resolution molecule? \n\n\n", "summary_of_the_paper": "The authors present a variational-autoencoder-based model for learning and generating graph structures. In particular, they propose a multiresolution graph network (MGN) that encodes a given graph in a hierarchical manner, i.e., at different levels of resolution. \nTraining the nodes of the coarsened graphs as latents of a variational auto-encoder allows for sampling a new graph in a bottom-up manner, i.e., at increasingly higher resolution.\n\nThe main contribution of this work consists of developing the framework of MGNs and demonstrating that they can be trained as hierarchical variational autoencoders, which yields the multiresolution graph variational autoencoders (MG-VAEs). The MG-VAEs represent generative models that allow for generating graphs in a multiresolution and equivariant manner.\nThe authors evaluate these models in a range of different settings, from unsupervised representation learning, over link prediction on citation graphs, to the generation of molecules or graph-based image generation.\n", "summary_of_the_review": "The authors present a novel approach for generating complex graphs, e.g., molecules by introducing a model that allows for sampling from a latent space at various levels of resolution.\nFurther, the paper is well written and generally presented in a clear manner. However, the evaluation of the method and the comparison to other work should be expanded upon. In particular, relevant work seems to be missing both for providing context of the work in the current state of the field, as well as in the evaluation and comparison of the model to other work.\nThus, while I find the method worthy of acceptance at  ICLR, I deem the paper marginally below the acceptance threshold in its current state.\n\nEdit:\nThe authors clarified my question regarding the parameterized Gaussian and I appreciate their time for doing so. I would encourage the authors to include this motivation for their approach also in the manuscript (while the method is formally described in the main text and the appendix, I cannot find a discussion for why this approach is taken). This will help readers understand the importance of this aspect better. \n\nUnfortunately, my main concerns regarding comparison with and discussion of relevant related work remain unanswered and I thus maintain the score of 5.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}, {"review_id": "X62DGJ9-VW", "reviewer": "Reviewer_XesM", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper is quite technical. Although the paper touches a number of issues regarding the equivariant and invariant concepts, this comes from the basic requirement from the GNN, see Michael Bronstein et al 5G paper. That is, the main contents in Section 3 can be regarded the major contribution of the paper. In other words, the main contribution comes from Section 4 where a hierarchical type of VAE framework is proposed, although building on the existing approaches or techniques. \n\nThe paper is readable in its current format. I dont see any specific theoretical issues and the mathematical derivation is solid (anyway this is the standard steps of building VAE models). It is nice for the authors to deal with the non-differentiable issue of the clustering assignment, i.e., eqn (1). The application of the Gumbel-max trick makes BP training possible.  However I am a bit confused or surprised that the authors did not mention at all on how to deal with the differentiable issue with the cardinality function in the KL term, see eqn (2) or (3).  It seems to me this term is non-differentiable due to counting the number of nodes in clustering which is determined by the model parameters in a complicated way.  Or the authors may make their codes available to the reviewers at this stage just like other authors do in this round.\n\n", "summary_of_the_paper": "This paper proposes Multiresolution Equivariant Graph Variational Autoen-coders (MGVAE) which can learn and generate graphs in a multiresolution and equivariant fashion. Higher order message passing is used to encode the graph while maintaining learning mutually exclusive clusters so that coarsening into a lower resolution, thus creating a hierarchy of latent distributions. The model also maintain an end-to-end permutation equivariant with respect to node ordering. Their experimental results show that MGVAE achieves competitive re-\nsults with several generative tasks and graph link prediction etc.", "summary_of_the_review": "My bit concern is the way of how to handle the KL terms in the objective. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "K8lLdgUTTpn", "reviewer": "Reviewer_KkPB", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This paper is well-motivated and easy to follow. I have some minor concerns below for the authors to address.\n\nMinor concerns:\n\n1. The literature review could be better. Recent studies have widely acknowledge the impacts of progressive or hierarchical graph generation, especially for molecular generation, e.g., *Hierarchical Generation of Molecular Graphs using Structural Motifs* and its following works. These works should also be the baselines for the proposed method.\n\n2. In the *Learning to Cluster* section, in order to make the clustering procedure learnable, Gumbel-max trick is adopted to replace the max-pooling. Do you use Gumbel-softmax in practice since Gumbel-max is not differentiable. If the Gumbel-softmax is used, then whether the complexity of $O({|V|^2}/{K})$ could not be hold since Gumbel-softmax is not hard partition.\n\n3. It's better to present empirical evidence to demonstrate the claim about the efficient of time and space complexity for the proposed framework.\n\n4. I have a strong concern about the metrics used in graph generation tasks, although they're usually used in previous literatures. More concrete, in the molecular generation (Figure 3 and Table 1), while the chemical validity is 100% on both dataset, the generated molecular structure seems wired and are most likely not stable. For example, I have asked my colleagues who have chemical-related backgrounds, and they say that most molecules shown in Fig. 3 (at least 1st, 2nd, 3rd, 5th, 8th) are incapable of stable existence. Please kindly correct me if there is anything wrong due to my limited chemical knowledge.\n\n5. Comparing the propsed framework with more recent baseline methods rather than only comparing to classical methods would make the experimental results more solid. I suggest that for the molecular generation and representation tasks, the authors could add some additional experiments to comparing baseline methods published in recent years, and especially the state-of-the-art method (https://paperswithcode.com/sota/graph-regression-on-zinc-500k).\n\n6. Capturing the graph structure is more essential for molecular modeling, I encourage the authors exploit more on molecular generation and representation, instead of image generation or social netoworks.\n\nPresentation problems or typos:\n\n1. Section 3.1 Definition 4 use $\\mathbf{d}_{local}$ to refer to local decoder, Section 4.2 use $\\mathbf{d}_{local}$ to refer to local graph encoder.\n\n2. In section 3.1, subscripts $k$ of $\\mathcal{Z}_k$ and $\\mathcal{G}_i$ are clusters indices in a graph. In section 4.2, subscripts $i$ of $\\mathcal{Z}_i$ and $\\mathcal{G}_i$ are sample indices, notation is changed to $[\\mathcal{Z}_{i}]_k$ and $[\\mathcal{G}_{i}]_k$.\n\n3. In section 4.2, there is a subscript of a set, which is confusing. May replace $Z_{i}^{(l)}=\\{[Z_{i}^{(l)}]_k \\in \\R^{|[\\mathcal{V}_i^{(l)}]_k|\\times d_z}\\}_k$ by $Z_{i}^{(l)}=\\{[Z_{i}^{(l)}]_k \\in \\R^{|[\\mathcal{V}_i^{(l)}]_k|\\times d_z}| 1\\leq k \\leq K_{i}^{(l)}\\}$.\n\n   And $Z^{(l)}(i)=\\{Z_{k}^{(l)}(i) \\in R^{|\\mathcal{V}_k^{(l)}(i)|\\times d_z}| 1\\leq k \\leq K^{(l)}(i)\\}$ may be better.\n\n4. In appendix section A Definition 11, $j$ in the indices of C should be redundant(typo).\n", "summary_of_the_paper": "This study presents a multi-scale graph VAE with hierarchical graph coarsening. The Gumbel-max trick is employed to generate learnable hard partition for clustering, and permutation equivariant tensor operations are used (Kondor et al., 2018) to construct the group equivariance network. The authos find that the proposed framework exhibits competitive performance in graph generation, molecular generation, molecular representation learning, link prediction and graph-based image generation. Given the applicability of this framework, this proposed framework may be interesting to the graph generation community, and this paper is well-written.", "summary_of_the_review": "I'm definately willing to raise my score if my concerns have been well addressed.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "COtsfdWa7L", "reviewer": "Reviewer_dMFu", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "\n**Strengths**:\n* Nice introduction.\n* Figure 1 is a nice illustration of def 1 and 2. \n* Overall clearly written.\n* Good motivation for why multi-resolution graph generation can be useful. \n\n**weaknesses**:\n* At the end of section 3.1, the authors claim that MGN (multiresolution graph networks) \"is more efficient than existing methods in the field.\" The rational is that the prediction of the adjacency matrix in the decoder happens hierarchically, and at each stage only local adjacency need to be predicted, as opposed to the full adjacency matrix prediction in one-stage decoders. However, empirical results seem to contradict this claim of efficiency. In Section 5.1 on molecule generation, the authors state the following \"because of high complexity, we only train on a small random subset of examples while all other methods are trained on the full datasets. \"  This contradiction with the earlier claim needs to be clarified. What is the source for the high complexity that prevents this method from being trained on the entire dataset (which is not that large)? Without any explanation on what the source of the complexity is, one cannot estimate if this method is scalable to larger graphs.\n* Although there are quite a few experiments in the paper, they don't give sufficient insight into why the proposed method works better and which contributions are important. For example, the influence of the multi-resolution part of the generation and encoding is not investigated with an ablation study, whereas this is one of the main components of the paper. I would expect to see ablation studies that study the influence of the number of stages in the multi-resolution generation and encoding, as well as the influence of learnable balanced partitions versus fixed graph partitioning. Furthermore, what is the effect of the learnable equivariant prior over the standard normal prior?\n* The definitions in section 3 take up unnecessarily much space and distract from the contributions of the paper. Example: def. 5 and 6 are used throughout the field and don't require that much space. Definition 9 again has much overlap with 5 and 6. Although writing a didactic paper with sufficient background is important, in this case I think it is a bit overdone, and more space and discussion should be spent in the main paper on experimental results and details of the implementation and method. For example, the matching scheme for the learnable prior with full covariance matrix will have an influence on the complexity of the method but gets almost no attention in the main paper.  \n\n**Minor comments/questions**:\n* What does \"variationally decode\" mean in the abstract. VAE's use the encoder to do variational inference, not the decoder.\n* Bottom of page 3: refers to figure 3.1 but should probably be figure 2.\n* In the paper symbol $\\mathcal{N}$ is used both for gaussian probability distribution and a neural network in definition 9. It would improve clarity if there are separate symbol for these two things.\n* The decoder distribution at the bottom of page 6 only considers the case of unweighted graphs for which the adjacency matrix contains elements of value 0 or 1, but not the weighted case. Could you extend it to the weighted case?\n* What does the index k mean in the last sentence of the first paragraph in section 4.2 in the equation for $\\mathcal{Z}^l_i$? The LHS doesn't depend on k, but the RHS does. \n* Appendix C, typo: \"preserves equiarience\" --> \"preserves equivariance\".\n", "summary_of_the_paper": "This submission considers a multiresolution graph auto-encoder framework which is equivariant with respect to node permutation. Contrary to prior work on multi-scale graph generation, in this work the hierarchical structure in the encoder is learned through differentiable graph coarsening and is encouraged to produce balanced partitions of the graph. In the decoder, the graph is generated hierarchically and at each level, local adjacency matrices need to be predicted, rather than directly predicting the adjacency matrix of the full graph.  The method is evaluated on molecular generation, community graph generation,  and citation network generation in the main paper. The supplementary materials contains additional experiments on link prediction, unsupervised and supervised molecular property predictions, and graph-based image generation.  \n", "summary_of_the_review": "Although I think this paper has potential, in its current form I vote to reject it. The weaknesses raised in the previous part of the review are the most important reason for this vote. Although each one of them consists of a significant weakness from my point of view, they are listed in order of descending importance.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "08PwvY6FLy3", "reviewer": "Reviewer_PA3h", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strength:\nThe proposed method is presented with many details. Several learning tasks are designed to support the novelty of the proposed method;\n\nWeakness:\n1. The main focus of the proposed method is its equivariance property. It would be nice to give some counter-examples that existing methods fail to guarantee this condition, which then becomes problematic. \n2. A main concern of the proposed method is its \"high complexity\". The first experiment only supports the training \"on a small random subset of examples\", according to the authors. Although the results in Table 2 tries to prove the complexity issue is minor, more evidence (probably more scenarios or perspectives?) could be provided to persuade. A similar issue arises in the second experiment, where the authors select a subset of two considerably small graphs, Cora and Citeseer.\n\nMinor issues:\n1. The concepts should be first introduced BEFORE further discussion, e.g, equivariance.\n2. Many details should be carefully looked after. For example, the in-text citations are disordered. Section 1 \"...between their discrete substructures (subgraphs) (You et al., 2018a) (Li et al., 2018) (Liao et al., 2019)...\", the names should be put in one parenthesis.\n3. The reproducibility statement was not addressed.\n4. The presentation should be taken care of. For example, \"...we generalize by modeling...\" (page 5), what is generalized here? “On the another hand” (page 6), it sounds supernatural that one has 'another' hand. ", "summary_of_the_paper": "The authors propose a multi-resolutional graph generation tool with a variational autoencoder. The graph hierarchy is learnable and flexible to new data.", "summary_of_the_review": "The paper could be more persuasive if it provides further justification regarding the necessity (and initativity) of designing an equivariance graph generation. The concern on model complexity should be addressed. Also, the paper should be carefully proofread before it is ready for acceptance.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper proposes multiresolution and equivariant generative models.  Experimental results for several applications are shown.

Pros:
- A first hierarchical generative model with multiresolution and equivariance.
- Extensive experiments

Cons:
- Marginal novelty (multiresolution and permutation equivalence each is not novel for graph neural networks.
- State-of-the-art methods are not compared as baselines.
- Some standard metrics are not evaluated, and the used metrics are questionable (some generated molecules might not be stable although the chemical validity is 100%).
- Time/space complexity evaluation is missing.

The authors did not address some of the serious concerns in the rebuttal.
Decision: Reject