Unsupervised Learning of Graph Hierarchical Abstractions with Differentiable Coarsening and Optimal Transport
Authors: Tengfei Ma
Jie Chen
Venue:  (2020)
Keywords: Unsupervised learning
hierarchical representation learning
graph neural networks

Abstract: Hierarchical abstractions are a methodology for solving large-scale graph problems in various disciplines. Coarsening is one such approach: it generates a pyramid of graphs whereby the one in the next level is a structural summary of the prior one. With a long history in scientific computing, many coarsening strategies were developed based on mathematically driven heuristics. Recently, resurgent interests exist in deep learning to design hierarchical methods learnable through differentiable parameterization. These approaches are paired with downstream tasks for supervised learning. In this work, we propose an unsupervised approach, coined \textsc{OTCoarsening}, with the use of optimal transport. Both the coarsening matrix and the transport cost matrix are parameterized, so that an optimal coarsening strategy can be learned and tailored for a given set of graphs. We demonstrate that the proposed approach produces meaningful coarse graphs and yields competitive performance compared with supervised methods for graph classification.

Under review as a conference paper at ICLR 2020
UNSUPERVISED LEARNING OF GRAPH HIERARCHICAL ABSTRACTIONS WITH DIFFERENTIABLE COARSENING AND OPTIMAL TRANSPORT
Anonymous authors Paper under double-blind review
ABSTRACT
Hierarchical abstractions are a methodology for solving large-scale graph prob- lems in various disciplines. Coarsening is one such approach: it generates pyra- mid of graphs whereby the one in the next level is a structural summary of the prior one. With long history in scientific computing, many coarsening strategies were developed based on mathematically driven heuristics. Recently, resurgent interests exist in deep learning to design hierarchical methods learnable through differentiable parameterization. These approaches are paired with downstream tasks for supervised learning. In practice, however, supervised signals (e.g., la- bels) are scarce and are often laborious and expensive to obtain. In this work, we propose an unsupervised approach, coined OTCOARSENING, with the use of optimal transport. Both the coarsening matrix and the transport cost matrix are parameterized, so that an optimal coarsening strategy can be learned and tailored for given set of graphs. We demonstrate that the proposed approach produces meaningful coarse graphs and yields competitive performance compared with su- pervised methods for graph classification and regression.
INTRODUCTION
A proliferation of graph neural networks emerged as competitive alternatives graph kernels for various graph applications; e.g.. theorem proving (Wang et al. (017) and chemoinformaties (Jin (et al. 2017 Fout et al. 2017 Schütt et al. 2017). These models learn sophisticated feature repre- sentations of graph and its constituents (i.e., nodes and edges) through layers of feature transfor- mation. Among them, a broad array work is convolutional, extending convolution filters in the spatial domain to the spectral domain or to local neighborhoods (Bruna et al.) 2014; Henaff et al. 2013 Duvenaud et al. 2015 Defferrard et al. 2016 Kipf & Welling 2017 Hamilton et al.) 2017 Chen et al. 2018 Velickovć et al., 2018: Ying et al.] [018a]] Liao et al. 2019 Xu et al. 2019b); whereas a few others are recurrent, which treat the representation of a graph node as the state of a dynamical system, being recurrently updated (Scarselli et al.) 2009 Li al. 2016 Gilmer al., 2017 Jin et al.) 2017). Several convolution architectures (Xu et al. 2019b) Morris et al. (219)) are connected the Weisfeiler-Lehman (WL) graph isomorphism test because of the resemblance it- crative node (re)labeling. They are stated to be as expressive as WL in isomorphism tests, rendering strong competitors WL graph kernels [Shervashidze al. 2011 inspired by the same procedure.
An image analog of graph neural networks is convolutional neural networks, whose key components are convolution and pooling. The pooling operation reduces the spatial dimensions of an image and forms hierarchical abstraction through successive downsampling. For graphs, similar hierarchical abstraction particularly important maintaining the structural information and deriving faithful feature representation. A challenge, however, is that unlike image pixels that are spatially regular, graph nodes are irregularly connected and hence pooling is less straightforward.
Several graph neural networks perform pooling in a hierarchical manner. Bruna et al. (2014) build a multiresolution hierarchy of the graph with agglomerative clustering, based on e-covering, Def- ferrard et al. (2016) and Fey et al. (2018) employ Graclus that successively coarsens graph based on the heavy-edge matching heuristic. Simonovsky & Komodakis (2017) construct the hierarchy through combined use of spectral polarity and Kron reduction. These neural networks build the

---

Under review as a conference paper at ICLR 2020
graph hierarchy in the preprocessing step, which defines in advance how pooling is performed given a graph. No learnable parameters are attached. In fact, most practical coarsening methods to date are built mathematical heuristics; how they affect the structure and properties of the graph is less understood (Loukas & Vandergheynst 2018).
Recently, hierarchical abstractions learnable neural network module surfaced in the literature of graph representation learning. Representative approaches include DIFFPOOL (Ying et al. 2018b), GRAPH U-NET (Gao & Ji 2019), and S SAGOOOL (Lee et al. 2019). In the first approach, a soft clustering of nodes is parameterized and learned. The next graph in the hierarchy is thus a com- plete graph of the clusters. In the second approach, the top nodes according to some parameterized ordering are selected and the induced subgraph becomes the next graph in the hierarchy. The third approach is similar to the second one, except that the ordering is computed through self-attention. All approaches treat the learnable hierarchy as part of the neural network (in conjunction with a predictive model), which trained with downstream task in (semi- jspprviiee manner.
In this work, we propose an unsupervised approach, called OTCOARSENING, that produces hierar- chical abstraction of a graph independent of downstream tasks. Therein, node features for the graphs in the hierarchy are derived simultaneously, so that they can be used for different tasks through train- ing separate downstream predictive models. OTCOARSENING consists of two ingredients: a param- eterized graph coarsening strategy in the algebraic multigrid (AMG) style; and an optimal transport that minimizes the structural transportation between two consecutive graphs in the hierarchy. The "OT" part of the name comes from Optimal Transport. We show that this unsupervised approach produces meaningful coarse graphs that are structure preserving; and that the learned representations perform competitively with supervised approaches in graph classification and regression.
The contribution of this work is threefold. First, for unsupervised learning we introduce a new technique based on hierarchical abstraction through minimizing discrepancy along the hierarchy. Second, key to a successful hierarchical abstraction is the coarsening strategy. We develop one motivated by AMG and empirically show that the resulting coarse graphs qualitatively preserve the graph structure. Third, we demonstrate that the proposed technique, combining coarsening and unsupervised learning, performs comparably with supervised approaches but is advantageous in practice facing label scarcity.
2 RELATED WORK
Hierarchical (a.k.a. multilevel or multiscale) methods are behind the solutions of a variety of prob- lems, particularly for graphs. Therein, coarsening approaches are being constantly developed and applied. Two active areas are graph partitioning and clustering. The former is often used in parallel processing, circuit design, and solutions of linear systems, among many others. The latter appears in deseriptive data analysis. Several representative developments are discussed here. It is not intended to be full account of the overwhelming literature and long history.
Many of the graph hicrarchical approaches consist of coarsening and an uncoarsening phase. The coarsening phase successively reduces the size of a given graph, that easy solution can be obtained for the smallest one. Then, the small solution is lifted back to the original graph through successive refinement the reverse coarsening order. For coarsening. a class of approaches applies heave-edge matching heuristics (Hendrickson & Leland 1995) Karypis & Kumar 1998; Dhillon al., 2007). In the conceptual level, nodes connected by heavily weighted edge are grouped into node in the coarse graph, so that the edge is protected from partitioning. The use of matching heuris- ties was not much analyzed until recently. Loukas and coauthors show that for certain graphs, the principal eigenvalues and eigenspaces of the coarsened and the original graph Laplacians are close under randomized matching (Loukas & Vandergheynst, (2018) Loukas| 2019). On the other hand, in the uncoarsening phase, refinement can be done in several ways. One approach is Kernighan refinement (Kernighan & Lin| 1970), which is commonly applied in spectral partitioning and spec- tral clustering methods (Shi & Malik 2000 Luxburg (007). whether not done in multilevel fashion. Another approach uses kernel k-menss, as in Dhillon et al. (2007).
Another class of coarsening approaches selects subset of nodes from the original graph. Call them coarse nodes; they form the node set of the coarse graph. Other nodes are aggregated with weights to the coarse nodes in certain ways, which, simultaneously define the edges in the coarse graph.
2

---

Under review as a conference paper at ICLR 2020
Many of these methods were developed akin to algebraic multigrid (AMG) (Ruge & Stüben 1987 as also is this work. In AMG, the set C' of coarse nodes is initialized as empty. Then, each node in the complement of C is investigated in some order; if its coupling to the current C' is sufficiently weak, the node is moved to C. The coupling may be defined based on edge weights (Kushnir et 2006), diffusion distances (Livne & Brandt 2012), algebraic distances (Ron et al. 2011] Chen & Safroj 2011; Safro et al.) 2014). The aggregation weights are defined accordingly. In this work, the selection of the coarse nodes and the aggregation weights are parameterized and learned instead. Besides the AMG style, the dominant eigenvector of the graph Laplacian has also been used for selecting coarse nodes (Shuman et al. 2015), who however use a combination of Kron reduction (Dörfler & Bullo 2013) and graph sparsification to define the edges of the coarse graph.
Hierarchical graph representation is emerging in graph deep learning. Representative approaches include DIFFPOOL (Ying et al., 2018b), GRAPH U-NET (Gao & Jil 2019), and SAGPoOT. (Lee) al. 2019). Cast in the above setting, DIFFPOOL. more similar to the first class of coarsening approaches, whereas GRAPH U-NET and SAGPOOL more similar to the latter. All methods are supervised, as opposed to ours.
Our work is additionally drawn upon optimal transport, tool recently used for defining similarity of distances
graphs (Vayer et al. 2019; Xu et al., 2019a). In the referenced work, developed that incorporate both node features and graph structures. Morcover, a transportation distance from the graph to its subgraph is developed by Garg & Jaakkola (2019). Our approach is based relatively simpler Wasserstein distance, whose calculation admits an iterative procedure more friendly to neural network parameterization.
3 METHOD
In this section, we present the proposed method OTCOARSENING, beginning with the two main ingredients: coarsening and optimal transport, followed by a summary of the computational steps in training and the use of the results for downstream tasks.
3.1 AMG-STYLE COARSENING
The first ingredient coarsens graph G into smaller one G.. For differentiable parameterization, an operator will need be defined that transforms the corresponding graph adjacency matrix E Raxa into A E _ where n and m the number of nodes of G and G. respectively, with m n. We motivate the definition by algebraic multigrid (Ruge Stüben, 1987). because of the hierarchical connection and a thehr-theoretic interpretation. AMG also happened to be referenced as a potential candidate for pooling in some graph neural network architectures (Bruna et al. 2014 Defferrard et al. 2016).
3.1.1 BACKGROUND ON ALGEBRAIC MULTIGRID
AMG belongs the family of multigrid methods (Briggs al. 2000) for solving large, sparse linear systems of the form Ar = b, where A is the given sparse matrix, is the right-hand vector, and is the unknown vector be solved for. For simplicity, we assume throughout that is symmetric. The simplest algorithm, two-grid V-cycle, consists of the following steps: (i) Approximately solve the system with an inexpensive iterative method and obtain an approximate solution x'. Let b- Ax' be the residual vector. (ii) Find a tall matrix S E R and solve the smaller residual system (ST AS)y = S for the shorter unknown vector y. (iii) Now we have a better approximate solution xr = r' + Sy to the original system. Repeat the above steps until the residual is sufficiently small.
In practice, is unlikely that the residual system (ST AS)y STr in the second step, though smaller, can be solved exactly, if the original system Az b cannot be. Hence, naturally appeals to recursion. That is, one solves (S" AS)y = ST only approximately, obtains the residual, constructs further smaller residual system, and proceeds recursively, until when sufficiently small residual system can be solved exactly and inexpensively.
The matrix of the residual system, ST AS, is called the Galerkin coarse- grid operator. One may show that step (ii), if solved exactly, minimizes the energy norm of the error x z" over all possible corrections from the range of the matrix S. Decades of efforts on AMG discover practical definitions
3

---

Under review as a conference paper at ICLR 2020
(a) Graph G
(b) Coarse nodes (red) and fine nodes (blue)
(c) Coarse graph G. (using only half of the nodes in G)
Figure 1: Example graph and coarsening.
of S that both is economic construct/apply and encourages fast convergence. We depart from these efforts and define/parameteriiee an S that best suites graph representation learning.
3.1.2 COARSENING FRAMEWORK
Following the above motivation, we settle with the coarsening framework
A. ST AS,
where named the coarsening matrix. For parameterization, we might have treated S as pa- rameter matrix, but it requires fixed size to be learnable and hence it can only be applied to graphs of the same size. This restriction both is unnatural in practice and destroys permutation invariance of the nodes. In what follows, we discuss the properties of S from graph theoretic view, which leads to a natural parameterization.
3.1.3 PROPERTIES S
Let V be the node set of the graph G. AMG partitions V into two disjoint subsets C and F, whose elements are called coarse nodes and fine nodes, respectively. See Figure [bb). For coarsening, C becomes the node set of the coarse graph and the nodes in F are eliminated.
The rows of the coarsening matrix correspond the nodes in V and columns nodes in C. This notion is consistent with definition (I), because the rows and columns of Ag correspond to the coarse nodes. also distinguishes from DIFFPOOL (Ying et al. 2018b), which although defines the next graph by the same equation (T). does not use the nodes in the original graph as those of the smaller graph.
If S is dense, so is Ac. Then, the graphs in the coarsening hierarchy are all complete graphs, which are less desirable. Hence, we would like to sparse. Assuming so, one sees that each column of S plays the role of aggregation. Consider the matrix vector product j-th node in the coarse graph, yΙ, is an aggregation the values of the original nodes Ø1. Ina where the aggregation weights come from the j-th column of S. For convenience, to be the set of nonzero locations of this column and call it the aggregation set of the coarse node j- The following result characterizes the existence of edge in the coarse graph. Its proof is simple exercise; see the appendix.
S" x. The value of the
define x())
Theorem 1. There is an edge connecting two nodes j and je in the coarse graph if and only if there an edge connecting the two aggregation sets x(j) and x(j') in the original graph.
Hence, order to encourage sparsity of the coarse graph, many of the aggregation set pairs should not be connected by edge. One principled approach ensuring is restrict the aggregation set to contain at most direct neighbors and the node itself. The following corollary is straightforward We say that the distance of nodes is the number of edges in the shortest path connecting them.
4

---

Under review as a conference paper at ICLR 2020
Corollary 2. If each aggregation set contains at most direct neighbors and the node itself. then there is an edge connecting two nodes in the coarse graph only if the distance between them in the original graph is most 3.
Consequently, in what follows will let S have the same sparsity structure the corresponding part of + I. The identity matrix is used to introduce self loops. An illustration of the resulting coarse graph is given in Figure Tc), with self loops omitted.
3.1.4 PARAMETERIZATION OF S
With the graph-theoretic interpretation of S, we now parameterize The strategy consists of the following computational steps. First, select coarse nodes in differentiable manner, so that the sparsity structure of S is determined. Then, compute the nonzero elements of S.
The selection of coarse nodes may be done in several ways, such as the top-k approach that or- ders nodes by projecting their feature vectors along a learnable direction (see, e.g., Cangeea et al. (2018); Gao & Ji (019)). This approach, however, leverages only node features but not the graph information. To leverage both, we apply one graph convolution
sigmoid AXW.)
to compute vector E Rax1 that weighs all nodes (Lee et al. 2019). Here, À E Raxx is the nor- malized graph adjacency matrix defined in graph convolutional networks (Kipf & Welling 2017). X Ra*d is the node feature matrix, and Wa [ddx1 is parameter vector. The weighting cessitates using sigmoid (or other invertible functions) rather than ReI.U as the activation function. than graph convolution layer enrich model expres- siveness. See implementation details in the appendix.
Naturally, may explore using
For coarsening into m nodes, we pick the top m values of a and list them in the sorted order. Denote by 0, E mR such a vector, where the subscript means sorted and picked. We similarly denote by A, E RR the column-sorted and picked version of A.
We let be overlay of the graph adjacency matrix with the node weights a,, Specifically, define
$ = L ny-row-normalize//l A, o (1a?),
where 1 means column vector of all ones.
There are several reasons why S is so defined. First, S carries the nonzero structure of Ag, which, following Corollary [ renders more likely sparse coarse graph. Second, the use of the normalized adjacency matrix introduces self loops, which ensure that an edge in the coarse graph exists the distance is no more than three, rather than exactly three (which is too restrictive). Third, because both A, and a, are nonnegative, the row normalization ensures that the total edge weight of the graph is preserved after coarsening. To see this, note that 1 A.A = 5T AS1 = ATA
3.2 OPTIMAL TRANSPORT
The second ingredient of the proposed OTCOARSENING uses optimal transport for unsupervised learning. Optimal transport (Peyré & Cuturi 2019) is a framework that defines the distance of two probability measures through optimizing over all possible joint distributions of them. If the two measures lie on the same metric space and if the infinitesimal mass transportation cost is a distance metric, then optimal transport is the same the Wasserstein-1 distance. In setting, extend this framework for defining the distance of the original graph G and its coarsened version Ge. Then, the distance constitutes the coarsening loss, from which model parameters are learned in an unsupervised manner.
3.2. 1 OPTIMAL TRANSPORT DISTANCE
To extend the definition of optimal transport of two probability measures to that of two graphs G and G., we treat the node features from each graph as atoms an empirical measure. The coarse node features result from graph neural network mappings, carrying information of both the initial node
5

---

Under review as a conference paper at ICLR 2020
features and the graph structure. Hence, the empirical measure based on node features characterizes the graph and leads to a natural definition of graph distance.
Specifically, let M be matrix whose element My denotes the transport cost from node i in G to a node j in Ge. We define the distance of two graphs as
Wg G.) == min PEU(a.))
(P.M)-7E(C)
(4)
where P, matrix of the same size as M, denotes the joint probability distribution constrained to the space U ((a 6) == {P E Ri P1 = a, p = b} characterized by marginals a and b; E' the entropic regularization E(P) == : bi Poy(log P.j - 1); and y > is the regularization magnitude. The first term M) is the usual definition of the transportation cost between two discrete measures. Because we treat them empirical measures, each of and b has constant elements that sum to unity, respectively. As is well known, the optimum of (P. Mf) is unstable and the cost of obtaining it through linear programming is high. A popular remedy is the entropic regularization (Wilson 1969). P)P) which brings in an additional benefit that the optimization (4)
admits computational procedure that is friendly to parameterizations inside M.
Through a simple argument of Lagrange multipliers, it is known that the optimal P, that solves (4) exists and is unique, the form
P.y = diag(u) K diag(u).
where и and v are certain positive vectors of matching dimensions and K = exp(-M/>>) with the exponential being element-wise. The solution Py may be computationally obtained by using Sinkhorn's algorithm (Sinkhorn 1964): Starting with any positive vector 20, itterate
for i = 0, 1, until convergence, u²+1 Ø (Kv*) and vi+ = a (KTw+))
(5)
Because the solution P.y is part of the loss function to be optimized, we cannot iterate indefinitely. Hence, we instead define a computational solution P by iterating only finite number k times:
pk diag(u") ( > diag(o*).
Accordingly, we arrive at the k-step optimal transport distance
W (P,,M) M) -E()t)
The distance 7 is the sample loss for training.
3.2.2 PARAMETERIZATION OF M
With the distance defined, it remains to specify the transport cost matrix M. As discussed earlier, we model My, as the distance between the feature vector of node i from and that of node j from G.- This approach the one hand is consistent with the Wasserstein distance and on the other hand, carries both node feature and graph structure information.
Denote by GNN X)) generic graph neural network architecture that takes the graph adjacency matrix A and node feature matrix X as input and produces as output a transformed feature matrix. We produce the feature matrix X₂ of the coarse graph through the following encoder-decoder-like architecture:
= C)), 2. =z
X. = G.N(AAA..: Z.).
The encoder produces an embedding matrix Z, of the coarse graph through combination of GNN transformation and aggregation ST whereas the decoder maps Ze to the original feature space so that the resulting X. lies in the same metric space as X. Then, the transport cost, or the metric distance, Mi is the p-th power of the Euclidean distance of the two feature vectors:
My = [i. xx(i.:)lB.
In this case, the optimal transport distance the p-th root of the Wasserstein-p distance. The power p is normally set as or two.

---

Under review as a conference paper at ICLR 2020
Algorithm Unsupervised training: forward pass
for each coarsening level do Compute coarsening matrix S according to and
2:
3: Perform coarsening and obtain A, and X, according
and
4: Obtain also node embeddings Ze from the computation
5:
Compute transport cost matrix M according to
6:
Compute k-step joint probability estimate Pt according to 5 and (6
7:
Compute current-level loss (k-step optimal transport distance) W (G, G.) according
8: Set G + Ge, A + Ac, and X + X
9:
end for
10: Sum the loss for all coarsening levels as the sample loss
3.3 TRAINING AND DOWNSTREAM USE
With the technical ingredients developed in the preceding subsections, we summarize the computa- tional steps into Algorithm which is self explanatory.
After training, for each graph G we obtain coarsening sequence and the corresponding node em- bedding matrices Ze for each graph in the sequence. These node embeddings may be used for downstream task. Take graph classification as an example. For each node embedding matrix, we perform global pooling (e.g., concatenation of max pooling and mean pooling) across the nodes and obtain summary vector. then concatenate the summary vectors for coarsening levels to form the feature vector of the graph. A multilayer perceptron is then built to predict the graph label.
4 EXPERIMENTS
In this section, conduct comprehensive set of experiments to evaluate the performance of the proposed method OTCOARSENING, Through experimentation, we aim at answering the following questions. (i) As unsupervised hierarchical method, how well does it perform downstream task, compared with supervised approaches and unsupervised non-hierarchical approaches? (ii) How does the choice of hyperparamters specific to this method affect the performance? (iii) multi-task setting, how well does it perform compared with supervised models trained separately for each task? (iv) Do the coarse graphs carry the structural information the original graphs (i.e., are they meaningful)?
4.1 SETUP
We perform experiments with the following data sets: PROTEINS, MUTAG, NC1109, IMDB- BINARY (IMDB-B B for short), LMDB-MULTY (IMDB-) M for short), and DD. They popularly used benchmarks publicly available from Kersting et al. (2016). Except IMDB-B and IMDB-M which are derived from social networks, the rest of the data sets all come from the bioinformatics domain. Information of the data sets is summarized in Table 3 in the appendix. The downstream task graph classification.
We gauge the performance of OTCOARSENING with several supervised approaches. They in- clude the plain GCN (Kipt & Welling 2017) followed by a gloabl mean pooling, as well as five more sophisticated pooling methods: SORTPOOL (Zhang et al., 2018). which retains the top-k nodes for fixed-size convolution; DIFFPOOL (Ying al.) 2018b). which applies soft clustering; SET2SET (Vinyals et al. 2015). which is used together with GR APHS AGE (Hamilton et al. 2017) as a pooling baseline in Ying al. (2018h); GPOOL (Cangea et al., 2018, [ao & Ji 2019). which retains the top-k nodes for graph coarsening, as is used by GRAPH U-NET; and SAGPOOL (Lee) ct al. 2019), which applies self-attention to compute the top-k nodes. Among them, DIFFPOOL, GPoOL, and SAGPOOL hierarchical methods, similar to ours.
Additionally, we employ a simple unsupervised baseline. Named GRAPHAE-UNSURE this base- line is graph autoencoder that does not perform coarsening, but rather, applies GCN twice to respectively encode the node features and decode for reconstruction. The encoder serves the same purpose that of the plain GCN and the decoder is needed for training without supervised signals.

---

Under review as a conference paper at ICLR 2020
We implement the proposed method and the graph autoencoder by using the PyTorch Geometric library, which is shipped with off fffthhesheeff implementation of all other compared methods. We refer the readers to the appendix for implementation and experimentation details. The code is available http://:ghh..aaccco/o/oo/o//ooos
4.2
GRAPH CLASSIFICATION
Graph classification accuracies are reported Table T OTCOARSENING outperforms the com- pared methods in five out of six data sets: PROTEINS, MUTAG, IMDB-B, IMDB-M, and DD. Moreover, it improves significantly the accuracy on DD. Interestingly, on these data sets the su- pervised runner up is always DIFFPOOL, outperforming the subsequently proposed GPOOL and SAGPOOL. On the other hand, these two methods perform the best on the other data set NC1109, with SAGPOOL taking the first place. On NCI109, OTCOARSENING performs par with the lower end of the compared methods. It appears low- now-performing, possibly because of the lack of useful node features that play important role in the optimal transport distance. Based on these observations, we may conclude that hierarchical methods indeed are promising for handling graph structured data. Moreover, as an unsupervised method, the proposed OTCOARSENING performs competitively with strong supervised approaches. In fact, even for the simple unsupervised baseline GRAPHAE- UNSUPV, outperforms DIFFPooL on PROTEINS, MUTAG, and DD. This observa- tion indicates that unsupervised approaches are quite competitive, paving the way for possible uses other applications and tasks.
Table 1: Graph classification accuracy.
Method GCN
PROTEINS
MUTAG
NCI109
IMDB-B
IMDB-M
DD
0.723
0.734
0.696
0.713
0.505
0.718
SET2SET
0.734
0.746
0.703
0.729
0.497
0.708
SORTPOOL
0.735
0,801
0.691
0.716
0.499
0.737
DIFFPOoL
0.742
0.845
0.717
0.743
0.503
0.739
GPOOL.
0.722
0.762
0.724
0.730
0.495
0.715
SAGPOOL
0.733
0.786
0.731
0.722
0.504
0.720
GRAPHAAE-NSUPP
0.743
0.846
0.664
0.724
0.499
0.765
OTCOARSENING
0.749
0.856
0.685
0.746
0.509
0.772
0.9
0.9
0.8
0.8
0.75
0.75
0.7
0.7
0.6
0.6
0.001
0.01
0.1
10
10
25
100
PROTEINS MUTAG NNO109
IMDB-8
PROTEINS MUTAG
NC1109
IMDB-8
Entropic regularization, 7
Sinkhorn steps,
Figure 2: Classification accuracy as parameters vary.
4.3 SENSITIVITY ANALYSIS
OTCOARSENING introduces few parameters owing to the computational nature of optimal trans- port: (a) the entropic regularization strength y; and (b) the number of Sinkhorn steps, k. In Figure perform sensitivity analysis and investigate the change of classification accuracy these pa- rameters vary. One sees that most of the curves are relatively flat, except the case of y on NCI109. This observation indicates that the proposed method is relatively robust the parameters of optimal transport. The curious case of NC1109 inherits the weak performance observed the preceding subsection, possibly caused by the lack of informative input features.
8

---

Under review as a conference paper at ICLR 2020
4.4 MULTI-TASK LEARNING
We further investigate the value of unsupervised graph representation through the lens of multi-task learning. We compare three scenarios: (A) single representation trained without knowledge of the downstream tasks (method: OTCOARSENING); (B) a single representation trained jointly with all downstream tasks (methods: GCN, SET2SET, SORTPOOL, DIFFPOOL, GPoOL, and SAGPOOL, all suffixed with "-joint"); and (C) different representations trained separately with each task (method: DIFFPOOL--ep).
The data set is QM7b (Wu et al. 2018), which consists of 14 regression targets. Following Gilmer al. (2017), standardize each target mean 0 and standard deviation 1; we also use MSE the training loss but test with MAE. reports the MAE and timing results.
Table 2: Multi-task regression error and training time (in seconds).
Method
MAE
Time
Method
MAE
Time
(A)
OTCOARSENING
0.6609
2622
BB)
SORTPOOL-joint
2.4408
2652
(C)
PIFFPOoL-sep
0.1714
15520
(B)
DirFPooL-joint
2.4231
1100
B
GCN-joint
2.4225
2122
(B) GPOOL-joint
2.4200
2117
(B)
SET2SET-joint
2.4256
2657
(B)
SAGPOOL-joint
2.4221
1874
One sees from Table 2 that in terms of regression error, single unsupervised representation (A) significantly outperforms single supervised representations (B), whilist being inferior separate supervised representations (C). Each scenario outperforms another at the cost of longer training time. is expected that (C) is much slower than other scenarios, because trains 14 models whereas others only 1. The timings for (B) are comparable with that of (A). The timing variation is caused by several factors, including the architecture difference and versss-ersussspasee implementation. DIFFPool. is implemented with dense matrices, which may be faster compared with other methods that treat the graph adjacency matrix sparse, when the graphs are small.
4.5 QUALITATIVE STUDY
As discussed in Section 2 coarsening approaches may be categorized in two classes: clustering based and node-selection based. Methods the former class (e.g., DIFFPOOL) coarsen a graph through clustering similar nodes. In graph representation learning, similarity of nodes is measured by not only their graph distance but also the closeness their feature vectors. Hence, two distant nodes bear risk of being clustered together if their input features similar. In this case, the graph structure is destroyed.
On the other hand, methods in the latter class (e.g., GRAPH U-NET and SAGPoOL) nodes in the original graph as coarse nodes. If the coarse nodes are connected based on only their graph distance but not feature vectors, the graph structure is more likely be preserved. Such is the case for OTCOARSENING, where only nodes within a 3-hop neighborhood are connected. Such is also the case for GRAPH U-NET and SAGPOOL, where the neighborhood is even more restricted (c.g., only I-hop neighborhood). However, if two coarse nodes are connected only when there is an edge in the original graph, these approaches bear another risk of resulting in disconnected coarse graphs.
Theoretical analysis is beyond scope. Hence, we conduct a qualitative study and visually inspect the coarsening results. In Figure 3] we show a few graphs from the data set MUTAG, placing the coarsening sequence of OTTOARSENING on the left and that of SAGPOOL on the right for comparison. The hollow nodes are selected as coarse nodes.
For the graph on the top row, OTCOARSENING selects nodes across the consecutive rings in the first-level coarsening, whereas SAGPOOL selects the ring in the middle. For the graph in the middle row, both OTCOARSENING and SAGPOOL select the periphery of the honeycomb for the first- level coarsening, but differ in the second level in that one selects again the periphery but the other selects the heart. For the graph the bottom row, OTCOARSENING preserves the butterfly topol- ogy through coarsening but the result of SAGPOOL is hard to comprehend. This qualitative study corroborates that the coarse graphs produced by OTCOARSENING meaningful.

---

Under review as a conference paper at ICLR 2020
Figure 3: Coarsening sequence for graphs from MUTAG. Left (magenta): OTCOARSENING, Right
(orange): SAGPOOL. Hollow nodes are coarse nodes.
CONCLUDING REMARKS
Coarsening is common approach for solving large-scale graph problems in various scientific disci- plines. It generates a sequence of successively smaller graphs, each one being a structural summary of the prior one, that the challenging solution with the original graph may be obtained through interpolation, starting from the easy solution with the coarsest graph and interpolating back with refinement, following the reverse order of coarsening. This idea is adopted in the AMG method for solving large, sparse linear systems of equations. When applied to machine learning, the same idea may explored for learning hierarchical abstraction of graphs, which a challenging analog of images that are comprised of regularly connected pixels, because node connections in graphs are generally irregular. How one effectively aggregates nearby nodes and coarsens the graph motivates the present work.
Whereas plethora of coarsening methods were proposed in the past and are used today, these methods either do not have learning component, have parameters that need be learned with downstream task. In this work, we present OTCCARSENING,, which an unsupervised approach, follows the concepts of AMG but learns the selection of the coarse nodes and the coarsening matrix through the use of optimal transport. We demonstrate its successful use graph classification and regression tasks and show that the coarse graphs preserve the structure of the original one. We envision that the proposed idea and architecture may be adopted in many other graph learning scenarios and downstream tasks, such graph autoencoders, structure learning, and generative modeling.
REFERENCES
William L. Briggs, Van Emden Henson, and Steve MeCormick. multigrid tutorial. SIAM, second edition, 2000.
Joan Bruna, Wojciech Zaremba, Arthur Szlam, and Yann LeCun. Spectral networks and locally connected networks on graphs. In ICLR, 2014.
Cätälina Cangea, Petar Veličković, Nikola Jovanovié, Thomas Kipf, and Pietro Liò. Towards sparse hierarchical graph classifiers. In NIPS Workshop on Relational Representation Learning, 2018.
Jie Chen and Πlya Safro. Algebraic distance on graphs. SIAM Journal on Scientific Computing, 33 113366834490 2011.
Jie Chen, Tengfei Ma, and Cao Xiao. FastGCN: Fast learning with graph convolutional networks via importance sampling. In ICLR, 2018.
10

---

Under review as a conference paper at ICLR 2020
Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks graphs with fast localized spectral filtering. In NIPS, 2016.
1. Dhillon, Y. Guan, and B. Kulis. Weighted graph cuts without eigenvectors: A multilevel approach.
IEEE Transactions on Pattern Analysis and Machine Intelligence, 29(1 1):4444 1957, 2007.
Dörfter and F. Bullo. Kron reduction of graphs with applications to electrical networks. /EEE Transactions Circuits and Systems I: Regular Papers, 60(1):150-163, 2013.
David Duvenaud, Dougal Maclaurin, Jorge Iparrauu-,, Rafael Bonne--ommaarlli,, Tim- othy Hirzel, Alán Aspuru-Guzik, and Ryan P. Adams. Convolutional networks on graphs for learning molecular fingerprints. In NIPS, 2015.
Matthias Fey, Jan Eric Lenssen, Frank Weichert, and Heinrich Müller. SplineCNN: Fast geometric deep learning with continuous b-spline kernels. In CVPR, 2018.
Alex Fout, Jonathon Byrd, Basir Shariat, and Asa Ben-Hur. Protein interface prediction using graph convolutional networks. In NIPS, 2017.
Hongyang Gao and Shuiwang Graph U-Nets. ICMI,, 2019.
Vikas K. Garg and Tommi Jaakkola. Solving graph compression via optimal transport. In NeurIPS, 2019.
Justin Gilmer, Samuel Schoenholz, Patrick F. Riley, Oriol Vinyals, and George E. Dahl. Neural message passing for quantum chemistry. In 2017.
William L. Hamilton, Rex Ying, and Jure Leskovec. Inductive representation learning on large graphs. In NIPS, 2017.
Mikael Henaff, Joan Bruna, and Yann LeCun. Deep convolutional networks on graph-structured data. arXiv:1 506.00566,.5,,, 2015.
B. Hendrickson and R. Leland. A multi-level algorithm for partitioning graphs. In SC, 1995.
Wengong Jin, Connor W. Coley, Regina Barzilay, and Tommi Jaakkola. Predicting organic reaction outcomes with Weisfeiler-Lemmar network. In NIPS, 2017.
G. Karypis and V. Kumar. A fast and high quality multilevel scheme for partitioning irregular graphs SIAM Journal on Scientific Computing, (0(1):359-392 1998.
B. W. Kernighan and Shen Lin. An efficient heuristic procedure for partitioning graphs. Bell System Technical Journal, 49:291-307, 1970.
Kristian Kersting, Nils M. Kriege, Christopher Morris, Petra Mutzel, and Marion Neumann. Bench- mark data sets for graph kernels, 2016. UR//attp://grapheeeneess es tu-dortmund.
de
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization, arXiv preprint arXiv:1412.6980, 2014.
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional net- works. ICLR, 2017.
Dan Kushnir, Meirav Galun, and Achi Brandt. Fast multiscale clustering and manifold identification. Pattern Recogn., 39100)1886-1181, 2006.
Junhyun Lee, Inyeop Lee, and Jaewoo Kang. Self-attention graph pooling. In ICML, 2019.
Yujia Li, Daniel Tarlow, Mare Brockschmidt, and Richard Zemel. Gated graph sequence neural networks. In ICLR, 2016.
Renjie Liao, Zhizhen Zhao, Raquel Urtasun, and Richard Zemel. Lanczosnet: Multi-scale deep graph convolutional networks. In ICLR, 2019.

---

Under review as a conference paper at ICLR 2020
Oren E. Livne and Achi Brandt. Lean algebraic multigrid (LAMG): Fast graph Laplacian linear solver. SIAM Journal on Scientific Computing, (4(4))B499-B33) 2012.
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.
Ulrike Luxburg. A tutorial on spectral clustering. Statistics and Computing, 17(4):395-41, 2007.
Christopher Morris, Martin Ritzert, Matthias Fey, William I.. Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe. Weisfeiler and Leman go neural: Higher-order graph neural networks. In AAAI, 2019.
Gabriel Peyré and Marco Cuturi. Computational optimal transport. Foundations and Trends in Machine Learning, 1(5-66):3556077 2019.
D. Ron, Safro, and A. Brandt. Relaxation- based coarsening and multiscale graph organization. SIAM Journal on Multiscale Modeling and Simulation, 9:407-423, 2011.
J. W. Ruge and K. Stüben. Algebraic multigrid. In Stephen F. McCormick (ed.), Multigrid Methods, Frontiers in Applied Mathematics, chapter 4. SIAM, 1987.
I. Safro, P. Sanders, and C. Schulz. Advanced coarsening schemes for graph partitioning. Journal of Experimental Algorithmics, 19:2.2:1-2.2:244 2014.
Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. The graph neural network model. IEEÉ Transactions on Neural Networks, 20(1):61-80, 2009.
Kristof T. Schütt, Picter-Jan Kindermans, Huziel E. Sauceda, Stefan Chmiela, Alexandre Tkatchenko, and Klaus-Robert Müller. SchNet: A continuous-illee convolutional neural network for modeling quantum interactions. NIPS, 2017.
Nino Shervashidze, Pascal Schweitzer, Erik Jan van Leeuwen, Kurt Mchlhorn, and Karsten M. Borgwardt. Weisfeiler-Lehman graph kemels. Journal of Machine Learning Research, 2011.
Jianbo Shi and Jitendra Malik. Normalized cuts and image segmentation. IEEE Transactions on Pattern Analysis and Machine Intelligence, 22(8):888 905, 2000.
David Shuman, Mohammad Javad Faraji, and Pierre Vandergheynst. multiscale pyramid trans- form for graph signals. IEEE Transactions on Signal Processing, 64(8):2119-2134, 2015.
Martin Simonovsky and Nikos Komodakis. Dynamic edge-conditioned filters in convolutional neu- ral networks on graphs. In CVPR, 2017.
Richard Sinkhorn. A relationship between arbitrary positive matrices and doubly stochastic matri- ces. Annals of Mathematical Statististics, 35(2):876-879, 1964.
Titouan Vayer, Laetitia Chapel, Rémi Flamary, Romain Tavenard, and Nicolas Courty. Optimal transport for structured data with application graphs. In ICML, 2019.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. In ICLR, 2018.
Oriol Vinyals, Samy Bengio, and Manjunath Kudlur. Order matters: Sequence to sequence for sets. In ICLR, 2015.
Mingzhe Wang. Yihe Tang, Jian Wang, and Jia Deng. Premise selection for theorem proving by deep graph embedding. In NIPS, 2017.
Alan Geoffrey Wilson. The use of entropy maximising models, in the theory of trip distribution, mode split and route split. Journal of Transprrt Economics and Policy, 3(1):108-126 1969.
Zhenqin Wu, Bharath Ramsundar, EvanN. Feinberg, Joseph Gomes, Caleb Geniesse, Aneesh S. Pappu, Karl Leswing, and Vijay Pande. MoleculeNet: benchmark for molecular machine learn- ing. Chemical Science, 9()):113-330 2018.
12

---

learning for Under review as a conference paper at ICLR 2020
Hongteng Xu, Dixin Luo, Hongyuan Zha, and Lawrence Carin. graph matching and node embedding. In JCML, 2019a.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? ICLR, 2019b.
Rex Ying, Ruining He, Kaifeng Chen, Pong Eksombatchai, William L. Hamilton, and Jure Leskovec. Graph convolutional neural networks for web-scale recommender systems. In KDD, 2018a.
Rex Ying, Jiaxuan You, Christopher Morris, Xiang Ren, William L.. Hamilton, and Jure Leskovec. Hierarchical graph representation learning with differentiable pooling. NIPS, 2018b.
Muhan Zhang, Zhicheng Cui, Marion Neumann, and Yixin Chen. An end-to-end deep learning architecture for graph classification. In AAAI, 2018.
A PROOFS
Proof of Theorem ! We say that the sum of numbers structurally nonzero if least one of the numbers is nonzero, even if they sum algebraically to zero (e.g., when one number is the opposite number the other). Structural nonzero of element in the adjacency matrix the necessary and sufficient condition for the existence of the corresponding edge in the graph.
Recall that A. 5T AS. For two coarse nodes j and j', one sees that the element A'(i,J") is structurally nonzero if and only if the submatrix A(x(j), x(i)) is nonempty. In other words, j and j' are connected by an edge the coarse graph Ge if and only there exists an edge connecting xj) and x(j") in the original graph G. Note that such edge may be self loop.
Proof of Corollary 2 there an edge connecting j and j' in the coarse graph, then according to edge connecting x(j) and i' x(j") in the original graph, for some
Theorem [ there nodes and f. Then by the assumption that the elements x are either j or j direct neighbors and similarly for x(j)), know that and j' are connected the path Li,ú, i', 5')),, J. which means that the distance between j and j' is at most 3.
B DATA SET DETAILS
See Table 3 for summary of the classification data sets used in this paper.
Table 3: Data sets.
PROTEINS
MUTAG NCT109
IMDB-B
IMDB-M
DD
# Graphs Classes
1,113
188
4,127
1,000
1,500
1,178
2
2
Average nodes
39.06
17.93
29.68
19.77
13,00
284.32
Average node degree
3.73
2.21
2.17
9.76
10.14
5.03
C IMPLEMENTATION DETAILS
The weighting vector a (cf. 22) used for coarse node selection is computed by using 1-layer GCN with activation function sigmoid o square. That is, a = (Ax
The GNNs in g for computing the coarse node embeddings Z, and coarse node features X, 1-layer GCNs.
The power p in Wasserstein-p (cf. 9 fixed as 2.
13

---

Under review as a conference paper at ICLR 2020
D EXPERIMENTATION DETAILS
We evaluate all methods using 10-fold cross validation.
For training, we the Adam optimizer (Kingma & Ba 2014) with tuned initial learning rate and a fixed decay rate 0.5 for every 50 epochs.
We perform unsupervised training for maximum of 200 epochs and choose the model the best validation loss. Afterward, we feed the learned representations into a 2-layer MLP and evaluate the graph classification performance.
We use grid search to tune hyperparameters: the learning rate is from {0.01, 0.001); and the num- ber of coarsening levels is from {1, 3) for the propoed method and {2, 4] for the compared methods. The coarsening ratio is set to 0.5 for all methods.
14


Reviews:
[{"review_id": "ryldwtXVKB", "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": "This paper proposes a method to summarize a given graph based on the algebraic multigrid and optimal transport, which can be further used for the downstream ML tasks such as graph classification.\nAlthough the problem of graph summarization is a relevant task, there are a number of unclear points in this paper listed below:\n\n- In Section 3.1, the coarsening method has been proposed, which is said to be achieved by finding S such that A_C = S^T A S. \n    However, A_C is usually not binary for S \\in R^{n x m}, hence how to get the coarse graph G_C from A_C is not clear. Please carefully explain this point.\n- In the proposed method, coarse nodes should be selected beforehand. Is there any guideline of how to choose them?\n- In Section 3.2, optimal transport is introduced and the distance between G and G_C is measured via entropic optimal transport in Equation (4) or (7).\n    However, in Equation (4), a and b should come from the input G and G_C , and it is not clearly explained how to obtain them from the input.\n    Moreover, how to use the distance between G and G_C in the proposed coarsening method is also not clear. It seems that it is not used in Algorithm 1.\n- I do not understand why the k-step optimal transport distance is needed. Since it converges to the global optimum as k becomes large, it is usually enough to set k to be large enough.\n- In experiments, how is the proposed method used for graph classification?\n    Since the proposed method is for generating coarse graphs in an unsupervised manner, graph classification cannot be directly performed by itself.\n- In addition to the above issue, to assess the effectiveness of the the proposed method, the following experiment is recommended:\n    Fix some classifier and compare performance of graph classification for the original graphs and for the coarse graphs.\n- In the qualitative study in Section 4.4, while the authors discuss coarse nodes, they are just an input from the user and results are arbitrary. Hence such discussion is not informative.\n\nMinor comments:\n- What is \"X\" in Equation (2)?\n- I recommend to write domain for matrices when they used at the first time.\n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "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.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "HygY5iIScS", "reviewer": "AnonReviewer3", "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": "This paper proposes an unsupervised hierarchical approach for learning graph representations. The proposed architecture is constructed by unrolling k-steps of a parametrized algebraic multigrid approach for minimizing the Wasserstein metric between the graph and its representation. The node distance (transport cost) used in the Wasserstein metric is also learned as an L2 distance between the embeddings of some graph embedding function. The approach is compared against 6 other state of the art approaches on 5 graph classification tasks, showing significant improvements 4 of them.\n\nThe paper is reasonably well written, however, I think some of the explanations can be tightened further. Especially a lot on the background of AMG is not really that relevant, since the authors are not transferring technical results from AMG. Also, it seems like a better flow for presenting this argument might be to switch the order of sections 3.2.1 and 3.1.2. It looks like the main point is  that this architecture is trying to emulate iterative coarsened residual optimization of the Wasserstein metric between a graph and its representation. How the coarsening matrix is derived is more of a technical point (it looks like the results would be much more sensitive to a switch of metric than to a switch of parametrization for S). \n\nThe empirical results are quite intriguing. There are, however, natural and important questions left unanswered. First and foremost, how does the amount of downsampling (compression) compare between methods. How many parameters do different methods require? It would also be good to see what the baseline performance would have been without any input compression as to understand how close these approaches are to the upper bound.\n\nFinally, I think the main issue of this paper, is left unresolved, namely, what is the point of not having supervision from the downstream task. As a user of graph representations trying to solve some problem, the only thing I would want from my representation is to capture some notion of sufficient statistics that are small enough to be efficient and allow me to solve my problem. I would not necessarily care about how well the learned representation resembles the original graph unless I believed that my downstream task was hard to evaluate  and that it was very smooth in the Wasserstein metric. I read the paper multiple times, trying to find any discussion on this, but it seems that the fact that an unsupervised representation is a good thing is taken for granted. A point could at least be made using the same representation for different tasks experimentally. Or, perhaps, literally doing an AMG-type unpacking of the downstream task itself as a comparison. This would shed light on the question of whether the iterated residuals or the choice of distance is what's driving the observed results.", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "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": "B1xsVn_aKH", "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": "\nThe paper proposes a differentiable coarsening approach for graph neural network (GNNs).\nTo this end, it is motivated by algebraic multigrid and optimal transport methods. \n\nGNNs is indeed an interesting line of research. And introducing coarsening into them, it a highly relevant step. However, there are some major downsides. First, some of the statements are a little but too strong. The paper starts with claiming that GNNs are competitive to graph kernels. But then for instance\n\nChristopher Morris, Martin Ritzert, Matthias Fey, William L. Hamilton, Jan Eric Lenssen, Gaurav Rattan, Martin Grohe:\nWeisfeiler and Leman Go Neural: Higher-Order Graph Neural Networks. AAAI 2019: 4602-4609\n\nshow that many (if not all) GNNs are equivalently expressive as the Weisefeiler-Lehman (WL) graph kernel. Hence, the competitiveness has to be qualified. Moreover, since you also employ graph convolutional networks for coarsening, you are also in the regime of this paper. Consequently, one should actually compare to WL, at least one should mention this connection. Actually, given that the datasets are not that large, one should run some statistical significance test. Moreover, if you check the paper above, they report much better results for PatchySan on MUTAG, better results on Protein for graph kernels, better results on IMDB-B using a hierarchical GNN approach, based on ideas of higher-order WL. \n\nNevertheless, indeed, the present paper shows that a differentiable pooling using WL kind of ideas is competitive to existing pooling approach. This is nice, but in the light of the work above, the novelty is unclear. This has to be clarified before publication. ", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper presents a differentiable coarsening approach for graph neural network. It provides the empirical demonstration that the proposed approach is competitive to existing pooling approaches. However, although the paper shows an interesting observation, there are remaining novelty as well as clarity concerns. In particular, the contribution of the proposed work over the graph kernels based on other forms of coarsening such as the early work of Shervashidze et al. as well as higher-order WL (pointed out by Reviewer1) remains unclear. We believe the paper currently lacks comparisons and discussions, and will benefit from additional rounds of future revisions.

Decision: Reject