Unsupervised Hierarchical Graph Representation Learning with Variational Bayes
Authors: Shashanka Ubaru
Jie Chen
Venue:  (2020)
Keywords: Hierarchical Graph Representation
Unsupervised Graph Learning
Variational Bayes
Graph classification

Abstract: Hierarchical graph representation learning is an emerging subject owing to the increasingly popular adoption of graph neural networks in machine learning and applications. Loosely speaking, work under this umbrella falls into two categories: (a) use a predefined graph hierarchy to perform pooling; and (b) learn the hierarchy for a given graph through differentiable parameterization of the coarsening process. These approaches are supervised; a predictive task with ground-truth labels is used to drive the learning. In this work, we propose an unsupervised approach, \textsc{BayesPool}, with the use of variational Bayes. It produces graph representations given a predefined hierarchy. Rather than relying on labels, the training signal comes from the evidence lower bound of encoding a graph and decoding the subsequent one in the hierarchy. Node features are treated latent in this variational machinery, so that they are produced as a byproduct and are used in downstream tasks. We demonstrate a comprehensive set of experiments to show the usefulness of the learned representation in the context of graph classification.

Under review as a conference paper at ICLR 2020
UNSUPERVISED HIERARCHICAL GRAPH REPRESEN- TATION LEARNING WITH VARIATIONAL BAYES
Anonymous authors Paper under double-blind review
ABSTRACT
Hierarchical graph representation learning is emerging subject owing the increasingly popular adoption of graph neural networks in machine learning and applications. Loosely speaking, work under this umbrella falls into two categories: (a) use predefined graph hierarchy to perform pooling; and (b) learn the hierar- chy for given graph through differentiable parameterization of the coarsening process. These approaches are supervised; predictive task with ground-truth -ruth labels is used to drive the learning. this work, we propose an unsupervised ap- proach, BAYESPOOL, with the use of variational Bayes. It produces graph repre- sentations given a predefined hierarchy. Rather than relying on labels, the training signal comes from the evidence lower bound of encoding a graph and decoding the subsequent one in the hierarchy. Node features are treated latent in this variational machinery, that they are produced as byproduct and are used in downstream tasks. We demonstrate a comprehensive set of experiments to show the usefulness of the learned representation in the context of graph classification.
INTRODUCTION
Graph representation learning has attracted a surge of interest recently, inspired by the widespread success of representation learning in the image and language domains through the use of deep neu- ral networks for parameterization. A substantial number of graph neural network (GNN) architec- tures (Bruna et al., 2014; Henaff et al., 2015; Duvenaud et al., 2015; Defferrard et al., 2016; Kipf & Welling, 2017; Hamilton et al., 2017; Chen et al., 2018; Velišković al., 2018; Ying et al., 2018a; Liao et al., 2019; Xu et al., 2019) extend the convolution filters for regular grid of data (e.g.. image pixels, time series, and sequences) to irregularly connected graph neighborhoods. This extension naturally stimulates the quest of also extending the pooling operation in convolutional neural net- works (CNN) to graphs. The challenge lies in the irregular connections as opposed to a regular grid structure, whereby partitioning is straightforward.
Graph pooling is used in at least two scenarios. One is global pooling: it pools the vector represen- tations of all nodes a single vector the graph representation. Simple operators such as max or mean are applied. A slightly more complex operator is the weighted sum, wherein the weights are computed through attention (Veličković al., 2018: Lee et al., 2019). A recently proposed operator is top-k pooling (Zhang et al., 2018), whereby a fixed number of node representations at the top of a sorted list is retained so that convolutions or ferd-forward transformations are applied.
The second use of pooling is the creation of graph hierarchy. In this scenario, pooling is local, more similar to that in CNNs.
interfaced with graph coarsening (also called graph reduction or graph compression), generic form of which is to cluster the nodes of the original graph into a node of the coarse graph. Then, the representations of the nodes the cluster are pooled. The clustering may be obtained by using cxisting graph coarsening or graph clustering approaches, as in Bruna et al. (2014); Defferrard et al. (2016); Simonovsky & Komodakis (2017); or learned through parameterization in Ying al. (2018b); Gao & Ji (2019); Lee et al. (2019). In either approach, the result include both a hierarchy graphs and the accompanying node representations.
Representation learning in these local pooling approaches is supervised, with the training signal coming from labels of the downstream task. In this work, we propose an unsupervised learning approach, named BAYEsPoOL, through the use of variational Bayes. We use existing coarsening

---

Under review as a conference paper at ICLR 2020
Figure I: Coarsening sequence of graph by using the method of Loukas (2019).
method obtain the graph hierarchy, an example of which shown in Figure 1. Then, our con- tribution is the learning of node representations for all graphs in this sequence. The high-level idea to employ an encoder-decoder architecture: the encoder takes the graph and its node features as input and produces node features for the next graph in the hierarchy, whereas the decoder uses these produced node features to construct the graph. The objective is to obtaín a decoding result as close to the given next graph as possible. The tool we use is variational Bayes. It is, however, slightly different from variational autoencoders (Kingma & Welling, 2014), because our decoder does not intend to reconstruct the input graph.
clear benefit of unsupervised learning that the learned representation is not tailored to a specific downstream task and hence may be more generalizable. Morcover, the coarsening method adopt a recent development that holds spectral guarantee (Loukas & Vandergheynst, 2018; Loukas, 2019) the quality of the coarse graphs. We demonstrate the effectiveness of such combination of hierarchical production and node representation learning in the context of graph classificationn. In particular, the classification performance is rather competitive with tf-e-offthhe-at supervised GNN approaches.
2 RELATED WORK
This work is in part based on graph coarsening that produces a hierarchy for given graph. Denote by G = (V, E) a graph with the vertex set V and the edge set E. Graph coarsening is concerned with computing smaller (coarse) graph Ge (Ve, Ee) with V.l < [V] that retains the structure of G. A multilevel coarsening technique recursively coarsens the graph, yielding a hierarchy. Graph coars- ening has been studied in the context of graph partitioning (Karypis & Kumar, 1998; Dhillon et al., 2007), graph visualization (Harel & Koren, 2000), machine learning (Lafon & Lee, 2006; Gavish et al. 00 Ubaru & Saad, 2019), and pooling in graph neural networks (Bruna et al., 2014; Def- ferrard et al., 2016; Simonovsky & Komodakis, 2017). A variety of heuristic coarsening techniques have been proposed in different disciplines, including matching (Hendrickson & Leland, 1995; Ubaru & Saad, 2019), first choice (Cong & Shinnerl, 2013), contraction based schemes (Dhillon schemes (Sharon
et al., 2005; Sanders & Schulz, 2011), and algebraic multigrid et al., 2000; Hu & Scott, 2001; Ron et al., 2011; Chen & Safro, 2011). Many well-known soft- ware packages exist for graph coarsening, e.g., Jostle (Walshaw & Cross, 2007), Metis (Karypis & Kumar, 1998), and DiBaP (Meyerhenke et al., 2008).
Recently, few graph coarsening techniques achieving certain theoretical guarantees were pre- sented (Moitra, 2011; Dorfler & Bullo, 2012; Loukas & Vandergheynst, 2018). Loukas (2019) presented variational approaches for graph coarsening with spectral guarantees. In particular, was shown that the coarse graphs preserve the top eigenspace (whose dimension is an input to the method) within a predefined error tolerance. Here, we use this variational approach to obtain the graph hierarchy.
This work is concerned with unsupervised graph representation learning. Recent literature has fo- cused on generative models to achieve the same; see. e.g., Kipf & Welling (2016); Li et al. (2018); Ma et al. (2018); Simonovsky & Komodakis (2018); Zhang et al. (2019). For learning hierarchical representations of graphs, most of the works that we are aware of are based supervised learn- ing, including Bruna et al. (2014); Defferrard et al. (2016); Simonovsky & Komodakis (2017); Ying et al. (2018b): Gao & Ji (2019); Lee et al. (2019). Methods most relevant to our work include: DIFFPooL (Ying et al., 2018b), where the coarsening matrices are learned in an end-to-end fashion; GRAPH U-NET (Gao & Ji, 2019), where graph pooling is achieved using learnable vector and
2

---

Under review as a conference paper at ICLR 2020
node ranking: and SAGPOOL (Lee et al., 2019), which is similar to GRAPH U-NET but graph self-attention to compute the ranking.
METHOD
The proposed method BAYESPOOL is an extension variational autoencoders. the name sug- gests, the goal of an autoencoder is to reconstruct the original input object after encoding it in the latent space. Our approach does not reconstruct the original input, but rather, aims as decoding an output faithful to another prescribed object. To this end, first revisit variational Bayes and justify the use variational lower bound for learning. Then, the machinery is applied to the graph context.
3.1 VARIATIONAL. BAYES
Let be the observed (data) variable and be the unobserved (latent) variable. A core subject of Bayesian inference is concerned with estimating the posterior distribution p(z[æ)). It is related to the prior p(z) and the likelihood p(x|2) through the Bayes theorem
p(=|z) p(x)=))(==)
2)(2,2)
The challenge lies in the marginalization over in the denominator, which is generally computation- ally intractable. Hence, various approximations were developed. Typically one adopts a surrogate model (2)) independent of data; and recently in the context of VAEs. the data dependent distribution (<((>)) is often used. In our setting, we introduce a new variable T and consider ((=(7)).
The difference, in terms of the Kullback Kullback-Leibler divergence, between the surrogate (variational) posterior (=(3)) and the true posterior p(2|æ) may be decomposed as
((=(T) log [(= dz
DKL. [<< (lp((()))(((x))
p(2[x)
f (=|33) log
{(>107 dz log
/ q(>|āt log (()l)) dz.
p(z)
DKi (a(=(#)
log p(x)
Ea log [=]l))
It consists of three terms: the KL. divergence between the variational posterior and the prior p(2), the log-evidence log p(x), and the marginal log-likelihood log p(z|2) under the surrogate distribution. Because the KL divergence is nonnegative, the log-evidence is lower bounded by the combination of the other two terms:
((r) 2 Ea(a(a) [log((x)e)) DKL (lp)))
The better the surrogate, the tigher the lower bound.
One sees that the right-hand side of (1) is almost the same the usual log-evidence lower bound (ELBO), except that the surrogate g(2(²) ()) appears in place of ((22z). This observation is not surpris- ing, because the marginalization is over the latent variable and has nothing to do with and т. We
thus conclude that the usual machinery of VAE applies, with only a notational change of the varia- tional posterior. In the usual VAE setting, the first term of the right-hand side of (1) is considered the decoding accuracy, whereas the second term is a regularization in the latent space. Our setting follows this interpretation.
3.2 GRAPH REPRESENTATION LEARNING WITH VARIATIONAL BAYES
In our setting, a pair of graphs-thh original one and the coarse one-is given. Let A E R and A, E mmmxm be the corresponding graph adjacency matrices, respectively. Similarly, denote by X E R=xd and X. E mxx the corresponding node feature matrices. We apply the encoder- decoder formalism, whereby the encoder encodes A and X into the coarse graph features X. that we seek, such that the decoder can use X, to decode a coarse graph as similar to A, as possible. See Figure for an illustration.

---

Under review as a conference paper at ICLR 2020
encoding
decoding
A, x
X
A
Figure 2: Encoder-decoder architecture.
Specifically, in the language of generative modeling, the encoder is the parameterized inference model that produces the parameters (Xx,AA, X) and the decoder the parameterized generative model that produces the parameters of p(Ae]]o)) Following (1), A plays the role of x, X. plays the role of 2, and (A, X) plays the role of The variational lower bound for model learning is thus
ELBO EX(X,AX) logp(A.|Xx) DxL xlIx
(2)
Maxmizing the ELBO amounts to maximizing the likelihood of decoding the coarse Ag (given coarse node features X, resulting from the encoder), while minimizing a regularization of the vari- ational posterior q(Xel A, X) that departs from the latent distribution p(X.).
3.3 MODELING AND PARAMETERIZATION
Generally, the latent space may be kept simple and unparameterized, with more emphasis placed on the encoder and the decoder. Thus, we let the prior p(X.) be the standard matrix normal .M((X. 0mxx' Im Ig.). Occasionally, specifying simple Gaussian structures improve performance, such as letting p(X.) be the factored Gaussian, with the mean and the agonal variance being parameters to learn. We have not yet, however, obtained strong empirical evidence of the benefit of using parameterized factored Gaussian in this case.
p(X.) may
For the decoder (generative model), natural choice is treat each element of the coarse graph adjacency matrix as a Bernoulli variable (scaled to the magnitude of the corresponding edge weight), with the success probability parameterized by function of the corresponding coarse node features. For notational convenience, let the column vector xf = Xx(i,;)² and let A Ac(i.j). Then, p(A,)X, is the product of independent Bernoulii distributions:
p(A.(Xa)
II p( {
p(AG
II $
Bernouli [Pt),
where 1ag, is the indicator function that returns if AG f and otherwise, and Ptj is param- eterized function that computes the success probability. A simple choice of the probability is an (unparameterized) dot product:
Ptj ((] 2f)),
but there exist several other straightforward parameterized variants. For example,
Pij = sigmoid (WT 25, W' and Púj = sigmoid(ww" (if o (x))))
(4)
where W and w are a parameter matrix and vector, respectively. One may also replace them by an MIP. Note that all these functions are symmetric with respect to i and j because the graph is undirected.
For the encoder (inference model). we treat the variational posterior g(X,|A, X) as a factored Gaus- sian: each coarse node x. an independent Gaussian with vector mean μ4 and diagonal variance diag(o?). Then,
q (X(1A, = II A II N(a5) 44, diag(o?)),
4

---

Under review as a conference paper at ICLR 2020
where 14; and parameterized functions of A and X. By doing so, the KL term in the ELBO (2) admits a closed form. We transpose the column vectors 14, and stack them to form a matrix M. Sim- ilarly, proceed with the o; is and form a matrix S. In what follows, model the parameterized function for M. The one for S is analogous.
Let C' be the set of coarse nodes; hence A(C,:) keeps only the rows of A that correspond to the coarse nodes. We let
M (HHWi),
(5)
where W1 a parameter matrix, H has the same nonzero pattern as A(C.:), and a is an activation function. This expression is in form similar to one graph convolution layer in GCN (Kipf & Welling, 2017), except that the square normalized adjacency matrix is replaced by a fat rectangular matrix H. Rather than basing H the original adjacency matrix, we designate its nonzero elements to be self-attention weights computed from the node features. Specifically, the nonzero elements of the i-th of H is computed
(wi) tanh(Wa3 Wanz))
softmax meigghbor(
where wh is parameter vector and W3 and Wa are parameter matrices. As an alternative, may replace the attention calculation by that in GAT (Veličković et al., 2018):
softmax @(nighhonr(3)
(LeakyReT.U(ud [Waa;; Wazzl))-
(7)
To further enhance the representational power, in the parameterization (5) one may replace the orig- inal feature matrix X by the node embedding matrix Z output from GCN:
M = (H ZW1) with Z = GCN(A, Ws).
(8)
The GCN introduces additional parameters W3 that may be useful for large data sets.
In Section 4, experiment with the different variants and suggest default choice that works generally well.
3.4 MULTILEVEL LEARNING
Coarsening may be done recursively, forming sequence of increasingly coarse graphs. Let the adjacency matrices of this sequence be Ao, . where Ag = A corresponds to the initial given graph. Given this sequence and the initial feature matrix Xo X, the goal is to obtain the subsequent feature matrices XI.
To this end, model learning is conducted through maximizing the evidence of observing AI...., AL. treated independently. That is, we want to optimize log p(Ai) + +... ... log p(Az). Following the argument as before, the actual quantity optimize is the evidence lower bound. Inserting the layer index l into (2), we have
ELBO, Ex(X log p(A)))) - -DRL - Xe (Ixx((
Then, the log-evidence lower bound is the sum
ELBO-
ELBO
The encoder and decoder parameters across coarsening levels differ but they are jointly learned through maximizing the ELBO.
3.5 DOWNSTREAM TASKS
The learned features XI...., Xz, together with the original Xo. may be used for predictive tasks through learning a separate predictive model. We follow a common practice and define the model as
yp MLP MLP(connatt coonca(reedouute reeddot "ireduuuuu. .readout(Xx)))
where readout is global pooling across graph nodes (e.g.. concatenation of the max pooling and the mean pooling), concat denotes vector concatenation, MLP eelf-explanatory, and yp is the class probability vector. In this paper, consider the graph classification task.
5

---

Under review as a conference paper at ICLR 2020
4 EXPERIMENTS
In this section, we evaluate the performance BAYESPOOL through the task of graph classification. Note again that BAYESPOOL is an unsupervised method; but as we will see, it is rather competitive with recently proposed supervised methods, even outperforming them on several data sets. We first present the details of the experimented data sets, the compared methods, and the training proce- dure. Then, we compare the graph classification accuracies. We also perform sensitivity analysis regarding the number of coarsening levels and compare the performance of several variants in the implementation of BAYESPOOL.
Data sets: We consider the same data sets used by Lee et al. (2019). They are standard benchmarks publicly available from Kersting et al. (2016). Table summarizes the information.
Table Data set statistics.
Data set
No. graphs
Nodes (max)
Nodes (avg)
Edges (avg)
Classes
DD
1178
5748
284.32
715.66
2
PROTEINS NCII
1113
620
39.06
72.82
2
4110
111
29.87
32.30
2
NCI109
4127
111
29.68
32.13
2
FRANKENSTEIN
4337
146
16.90
17.88
2
The first two data sets are related to protein structures. The graphs in DD (Dobson Doig, 2003) have different amino acids nodes; and the edges correspond to the distance between the nodes. Labels indicate if the protein is an enzyme or not. The PROTEINS (Dobson & Doig, 2003) graphs have secondary structure elements of proteins nodes. The edges indicate whether the nodes in amino acids. NCI1 and NCI109 are biological data sets popularly used for anticancer activity classification (Wale al., 2008). Here, the graphs correspond chemical compounds, with the atoms and the chemical bonds represented as the nodes and edges, respectively. The FRANKEN- STEIN (Orsini al., 2015) data set contains molecular graphs with 780 node features. The labels indicate if a molecule is mutagen or non-mutagen. Data sets DD, NCII, and NCI109 do not come with node attributes for use as features. Hence, we employ transformations of node degrees as features, following the practice of DIFFPOOL.
Compared methods: We compare with three supervised hierarchical graph representation learn- ing methods, namely PIrrPooL, GRAPH U-NET, and SAGPOOL. We duplicate the test accuracies of these methods reported by Lee et al. (2019).
DIFFPOoL (Ying al., 2018b) computes hierarchical representations of graphs by using end-to-end trainable pooling based on soft clustering. This method is expensive because of the computation of the dense projection matrix. Lee et al. (2019) report that the method ran of memory for pooling ratio greater than 0.5. GRAPH U-NET (Gao & Ji, 2019) uses a learnable scoring vector to rank the graph nodes and selects top-ranked nodes for pooling. SAGPOOL. (Lee al., 2019) uses similar approach as GRAPHI U-NET for pooling, but incorporates self-attention layer for learning the scoring vector. In both methods, the pooling ratio was to be 0.5.
Training procedure: We follow Lee et al. (2019) and perform several rounds of random splits with 80% training, 10% validation and 10% test. The learning rate is tuned over the range [le-2, 5e-2, 1e-3, 5e-3, le-4]. The hidden dimensions are tuned over [10, 20, 32, 48). For LeakyReL.U, the slope coefficient is set to 0.01. The coarsening ratio p is experimented with [0.25, 0.5, 0.75]; see Section 4.2 for sensitivity analysis. The dimension of the top eigenspace to be preserved by the coarsening procedure is set to optimizer. The training employs early stopping with patience of 50 epochs. The training setting for other methods are reported in Lee et al. (2019).
5. We implement the method Py Torch and use Adam as the
For fair comparison, use the same MLP classifier in Lee et al. (2019). For readout, mean pooling and max pooling and concatenate the two outputs. We then use feedforward layers along with softmax for classification. The classifier is trained for 150 epochs.

---

Under review as a conference paper at ICLR 2020
For architecture variation, the following combination consistently achieves the best results: the de- coder uses an unparameterized dot product (3), the encoder uses parameterization (5) with the atten- tion matrix H computed by using the GAT form (7). The classification results reported in Section 4.1 below follow this choice. The results of other variants are reported in the subsections that follow.
The
code is available
https: / awwaymooouuuuu.o// 4open scwenceeeeeccccccc / Seefffcc-eeeeeelBeeee
450d6411-5577-4e244
4.1 GRAPH CLASSIFICATION
We compare the performance of BAYESPOOL with several high-performing supervised methods recently proposed. These methods are all hierarchical methods. Table 2 lists the average test accu- racies. The pooling/coarsening ratio is 0.5 in all cases.
Table 2: Graph classification accuracies.
Data set
Method
DD
PROTEINS
NCT1
NCT109
FRANKENSTEIN
DIFFPOOL 66.95
68.20
62.32
61.98
60.60
GRAPH U-NET 75.01
71.10
67.02
66.12
61,46
SAGPOOL 76.45
71.86
67.45
67.86
61.73
BAYESPOOL 78.12
76,85
61.86
61.04
62.65
BAYESPOOL outperforms other methods on three out of five data sets. Its performance is also on par with DIFFPOOL on the other two data sets, although infereior to GRAPH U-NET and SAGPOOL. The graphs in DD and PROTEINS are relatively large; with a coarsening ratio 50% there does not seem cause information loss. Hence, BAYESPOOL works rather appealingly. On the other hand, although the graphs are smaller in FRANKENSTEIN, the data set contains large number (780) of features, which possibly dwarf the graph structure information. Therefore, all methods yield similar results (with an unsupervised method; hence, these results show that the method highly competitive for downstream tasks such graph classification. It enables incorporating sophisticated coarsening techniques such as Loukas (2019) for graph representation learning.
slightly outperforming the others). Encouragingly, BAYEsPOOL
Note that the adjacency matrices of the graphs typically sparse. BAYESPOOT. leverages sparse matrix computation, as opposed to DIFFPOOL where the projection matrix does not have an priori sparsity structure. The coarsening procedure used by BAYESPOOL is implemented in sparse matrix format, along with the calculations of the neural network. This implementation results in lower time cost and space complexity.
4.2 EFFECT OF COARSENING RATIO
One of the key factors that affects the performance of BAYESPOOL is the amount of graph reduction (the ratio of the coarse graph size to the initial size), or equivalently, the number of coarsening levels. This ratio is an input parameter to the coarsening method of Loukas (2019) that we use. In Table 3, we evaluate the performance of BAYESPOOL on two data sets with respect to the coarsening ratio. These data sets have relatively large graphs so that aggressive coarsening possible.
Table Graph classification accuracies for different coarsening ratios.
Coarsening ratio
DD
PROTEINS
P 0.75
77.87
77.27
P 0.5
78.12
76.85
p = 0.25
68.75
66.96
In the table, we report the results for three different levels coarsening with ratio p o= m/n, where m is the number nodes in the coarse graph and the original graph. We observe that the performance of BAYESPooL is relatively stable when p 2 0.5, but degrades as p becomes smaller. As we lower P. more and more nodes and edges removed, causing significant loss of information. However,
7

---

Under review as a conference paper at ICLR 2020
for p 0.25, BAYESPOOL still yields comparable results to DIFFPOOL according to Table 2. We conclude that = 0.5 appears to be the right tradeoff.
4.3 VARIANTS OF ARCHITECTURE
As discussed in Section few parameterizations of the encoder and the decoder are possible. In this subsection, we comprehensively study the different variants, with the aim of obtaining a combination that generally works well. The results are reported in Table
Table 4: Graph classification accuracies for different architecture variants.
Encoder
Variants
DD
PROTEINS
Leaky + plain [ (7) (5)
78.12
76,85
Leaky ReLU + GCN [ (7) (8)
75.68
74.51
tanh plain (6) + (5)
75.48
73.78
tanh GCN (6) (8)
74.80
73.52
Decoder
Variants
DD
PROTEINS
Plain dot product (3)
78.12
76.85
Parameterized dot product (4) left
71.06
73.58
Parameterized dot product (4) right
71.69
70.58
Replace W in (4) left by 2-layer MLP
72.83
75.65
In the top part of Table 4 we compare the performance of four variants of the encoder output M (as well as S). The variants include (i) the attention calculation and (ii) whether or to apply GCN before attention. The former contains two versions (6) and (7) and the latter also admits two versions (5) and (8), hence four combinations in total.
From the table, we observe that the GAT approach with LeakyReLU yields better performance; and interestingly, using additionally GCN for parameterization lowers the performance. The intro- duction of the additional parameters inside GCN does not seem helpful.
In the bottom part of Table 4 we compare the performance four variants of the decoder output Pij. Along with the three variants discussed in Section 3.3 (unparamterized (3) and matrix/vector- paramterized (4)), we also consider replacing the matrix W in (4) by 2-layer MLP.
From the table, we observe that the plain dot product performs the best for both data sets. Again, the introduction of additional parameters does not seem helpful; rather, the accuracies deteriorate. This observation is consistent for both the encoder and the decoder. It is possible that the use of many parameters adversely affects the performance on data sets of a scale that we experimented with here.
CONCLUSION
We have presented an unsupervised approach BAYESPOOL for hierarchical graph representation learning. Compared with supervised approaches, a clear benefit is that the learned representations are generalizable to different downstream tasks. BAYESPOOL, consists of an encoder-decoder ar- chitecture and adopts variational Bayes for training. but it is different from standard VAEs in that does not attempt to reconstruct the input graph; rather, the decoder aims at producing the next graph the hierarchy. Together with the use the graph coarsening approach of Loukas (2019), we per- form empirical evaluations that show that the learned representations yield competitive classification accuracies with state-of-the-ee supervised GNN methods.
REFERENCES
Joan Bruna, Wojciech Zaremba, Arthur Szlam, and Yann LeCun. Spectral networks and locally connected networks graphs. In ICLR, 2014.
8

---

Under review as a conference paper at ICLR 2020
Jie Chen and Ilya Safro. Algebraic distance graphs. SIAM Journal on Scientific Computing, 33 (6):3468-349)) 2011.
Jie Chen, Tengfei Ma, and Cao Xiao. FastGCN: Fast learning with graph convolutional networks via importance sampling. In ICLR, 2018.
Jingsheng Jason Cong and Joseph R Shinnerl. Multilevel optimization in VLSICAD, volume 14. Springer Science & Business Media, 2013.
Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks on graphs with fast localized spectral filtering. In NIPS, 2016.
Inderjit Dhillon, Yuqiang Guan, and Brian Kulis. A fast kernel-based multilevel algorithm for graph clustering. Proceedings of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining, pp. 629-634. ACM, 2005.
Inderjit S Dhillon, Yuqiang Guan, and Brian Kulis. Weighted graph cuts without eigenvectors multilevel approach. IEEE transactions on pattern analysis and machine intelligence, 29(1 I): 1944-1957, 2007.
Paul Dobson and Andrew Doig. Distinguishing enzyme structures from non-enzymes without alignments. Journal of molecular biology, 330(4))771-783, 2003.
Florian Dorfler and Francesco Bullo. Kron reduction of graphs with applications electrical net- works. IEEE Transactions on Circuits and Systems I: Regular Papers, 60(1):150-163, 2012.
David Duvenaud, Dougal Maclaurin, Jorge Aguilera-Iparraguiine Rafael Gómez-Bombarelli, Tim- othy Hirzel, Alán Aspuru-Guzik, and Ryan Adams. Convolutional networks on graphs for learning molecular fingerprints. In NIPS, 2015.
Hongyang Gao and Shuiwang Ji. Graph U-Nets. ICML, 2019.
Matan Gavish, Boaz Nadler, and Ronald Coifman. Multiscale wavelets on trees, graphs and high dimensional data: theory and applications to semi supervised learning. In Proceedings of the 27th International Conference on International Conference on Machine Learning, pp. 367-374. Omnipress, 2010.
William L. Hamilton, Rex Ying, and Jure Leskovec. Inductive representation learning on large graphs. In NIPS, 2017.
David Harel and Yehuda Koren. A fast multi-scale method for drawing large graphs. In International symposium on graph drawing. pp. 183-196. Springer, 2000.
Mikael Henaff, Joan Bruna, and Yann LeCun. Deep convolutional networks on graph-structured data. 156.v:1506.05166 2015.
Hendrickson and R Leland. A multi-level algorithm for partitioning graphs. In Supercompul- ing '95: Proceedings of the 1995 ACM/IEEE Conference Supercompuling, pp. 28-28. IEEE, 1995.
YF Hu and Jennifer A Scott. A multilevel algorithm for wavefront reduction. SIAM Journal on Scientific Computing, 23(4): 1352-13755 2001.
George Karypis and Vipin Kumar. A fast and high quality multilevel scheme for partitioning irreg- ular graphs. SIAM Journal scientific Computing, 20(1):359-392, 1998.
Kristian Kersting, Nils M. Kriege, Christopher Morris, Petra Mutzel, and Marion Neumann. Bench- mark data sets for graph kernels, 2016. URL htt.: / htttt:::/ggaphheeeels.ooom cs. tu- dortmund. de.
Diederik Kingma and Max Welling. Auto-encoding variational bayes. In ICLR, 2014.
Thomas N. Kipf and Max Welling. Variational graph auto-encoders. In NIPS Workshop on Bayesian Deep Learning, 2016.

---

Under review as a conference paper at ICLR 2020
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional net- works. In ICLR, 2017.
Stephane Lafon and Ann B Lee. Diffusion maps and coarse-graining: A unified framework for dimensionality reduction, graph partitioning. and data set parameterization. IEEE transactions on patter analysis and machine intelligence, 13(9):139331444) 2006.
Junhyun Lee, Inyeop Lee, and Jaewoo Kang. Self-attention graph pooling. In ICML, 2019.
Yujia Li, Oriol Vinyals, Chris Dyer, Razvan Pascanu, and Peter Battaglia. Learning deep generative models of graphs. In ICML, 2018.
Renjie Liao, Zhizhen Zhao, Raquel Urtasun, and Richard Zemel. Lanczosnet: Multi-scale deep graph convolutional networks. In ICLR, 2019.
Andreas Loukas. Graph reduction with spectral and cut guarantees. JMLR, 2019.
Andreas Loukas and Pierre Vandergheynst. Spectrally approximating large graphs with smaller graphs. In ICML, 2018.
Tengfei Ma, Jie Chen, and Cao Xiao. Constrained generation of semantically valid graphs via regularizing variational autoencoders. In NeuriPS, 2018.
Henning Meyerhenke, Burkhard Monien, and Thomas Sauerwald. A diffusion- multi- level algorithm for computing graph partitions of very high quality. In 2008 IEEE International Symposium on Parallel and Distributed Processing, pp. 1-13. IEEE, 2008
Ankur Moitra. Vertex sparsification and universal rounding algorithms. PhD thesis, Massachusetts Institute of Technology, 2011.
Francesco Orsini, Paolo Frasconi, and Lue De Raedt. Graph invariant kernels. In Twenty-Fourth International Joint Conference Artificial Intelligence, 2015.
Dorit Ron, Iya Safro, and Achi Brandt, Relaxation-based coarsening and multiscale graph organi- zation. Multiscale Modeling & Simulation, 9():407-423, 2011.
Peter Sanders and Christian Schulz. Engineering multilevel graph partitioning algorithms. In Euro- pean Symposium Algorithms, pp. 469-480. Springer, 2011.
Eitan Sharon, Achi Brandt, and Ronen Basri. Fast multiscale image segmentation. In Proceedings IEEE Conference Computer Vision and Pattern Recognition. CVPR 2000 (Cat. No. PR00662), volume 1, pp. 70-77. IEEE, 2000.
Martin Simonovsky and Nikos Komodakis. Dynamic edge-conditioned filters in convolutional neu- ral networks on graphs. In CVPR, 2017.
Martin Simonovsky and Nikos Komodakis. Graph VAE: Towards generation of small graphs using variational autoencoders. ICANN, 2018.
Shashanka Ubaru and Yousef Saad. Sampling and multilevel coarsening algorithms for fast matrix approximations. Numerical Linear Algebra with Applications, 26(3). 2019.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pictro Liò, and Yoshua Bengio. Graph attention networks. In ICLR, 2018.
Nikil Wale, lan A Watson, and George Karypis. Comparison of descriptor spaces for chemical com- pound retrieval and classification. Knowledge and Information Systems, 14(3):347-375, 2008.
Chris Walshaw and Mark Cross. Jostle: parallel multilevel graph-partitioning software-an overview. 2007.
Keyulu Xu, Weihua Hu. Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In ICLR, 2019.
10

---

Under review as a conference paper at ICLR 2020
Rex Ying, Ruining He. Kaifeng Chen, Pong Eksombatchai, William L. Hamilton, and Jure Leskovec. Graph convolutional neural networks for web-scale recommender systems. KDD, 2018a.
Rex Ying, Jiaxuan You, Christopher Morris, Xiang Ren, William L. Hamilton, and Jure Leskovec. Hierarchical graph representation learning with differentiable pooling. In NIPS, 2018b.
Muhan Zhang, Zhicheng Cui, Marion Neumann, and Yixin Chen. An end-to-end deep learning architecture for graph classification. AAAI, 2018.
Muhan Zhang, Shali Jiang, Zhicheng Cui, Roman Garnett, and Yixin Chen. D-VAE: variational autoencoder for directed acyclic graphs. In NeurlPS, 2019.


Reviews:
[{"review_id": "SJljZmHL9S", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper proposes an unsupervised approach to learn a representation of graphs. The idea comes from an encoder-decoder architecture, which is common in related literature. The paper uses a variational Bayes approach in the learning process. Thorough experiments are provided to justify the feasibility of the method. \n\nThis paper provides an unsupervised style of learning graph representations, which may not be coupled with a specific downstream task so that it may be more useful in general; also, the experiments themselves seem to be at least comparable to the recent methods.  \n\nHowever, I vote for rejecting this submission for the following concerns. \n\n(1) I did not find too many significant differences between this paper and [Kingma & Welling, 2014] in the design of encoder-decoder architecture as well as the learning procedure (I am not an expert in this area so please correct me if I am wrong).\n\n(2) The intuition of learning the representation in an unsupervised manner is interesting and important to me, though the experiments are mostly on the classification tasks. I think it would be helpful to demonstrate the representation power of the learned representation of the graph in tackling other tasks.\n", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_thoroughness_in_paper_reading": "I made a quick assessment of this paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "SJg6jDF6tr", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The authors propose in this paper a new unsupervised graph representation learning method. The method leverages recent advances in graph coarsening, mainly Loukas' method. The key idea of the method consists in using a reconstruction target that is not the classical one in an auto-encoder setting. More precisely, the encoder takes as an input the original adjacency matrix and node features but the decode only aims at reconstructing the coarse adjacency matrix (obtained via Loukas' method). \n\nThe experimental evaluation is quite thorough and shows that the method performs quite well, especially considering it is unsupervised but is compared to supervised representation methods. It would be nice to include statistical tests to assess the significance of the differences in cases were accuracies are very close one to another. A missing part would be to explore the relevance of the learned representation for other tasks (i.e. to use a multi task data set). Of course as the representation is learned in an unsupervised way, one can argue that the current evaluation is already providing an answer.\n\nOverall, I find the paper clear, but the variational bayes part could be much clearer. In fact I'm not sure why this is presented as variational bayes and not only variational. I do not see any prior distribution over parameters, for instance. I understand that the recent \"tradition\" in variational auto-encoder is to use this terminology, but as a (part time) bayesian, this is a bit annoying. ", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I made a quick assessment of this paper.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I did not assess the derivations or theory."}, "extra_text": {}}, {"review_id": "BJezGUojtr", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary: This work proposes an unsupervised hierarchical graph representation learning method, named BayesPool. The method learns a coarsening sequence of graphs together with the corresponding node representations. The coarsening sequence is learned using the method in Loukas (2019). The node representations are learned using an encoder-decoder structure, where the encoder encodes a graph to coarsened node representations, and the decoder decodes the node representations to a coarsened graph. The adopted objective function is analogous to VAE, except that the decoder does not aims to reconstruct an identical graph. Experiments on graph classification is performed on 5 different datasets, and competitive accuracy is achieved.\n\nConcerns: The authors claim that the leant representation in an unsupervised manner is more desirable in terms of generalization. However, they only provide very limited experimental results, which is not very convincing. Moreover, the authors also do not explain clearly on when the node representation of the coarsening sequence is needed.", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper presents an unsupervised method for graph representation, building upon Loukas' method for generating a sequence of gradually coarsened graphs. The contribution is an "encoder-decoder" architecture trained by variational inference, where the encoder produces the embedding of the nodes in the next graph of the sequence, and the decoder produces the structure of the next graph. 

One important merit of the approach is  that this unsupervised representation can be used effectively for supervised learning, with results quite competitive to the state of the art. 

However the reviewers were unconvinced by the novelty and positioning of the approach. The point of whether the approach should be viewed as variational Bayesian, or simply variational approximation was much debated between the reviewers and the authors. 

The area chair encourages the authors to pursue this very promising research, and to clarify the paper; perhaps the use of "encoder-decoder" generated too much misunderstanding. 
Another graph NN paper you might be interested in is "Edge Contraction Pooling for Graph NNs", by Frederik Diehl. 

Decision: Reject