Graph Coarsening with Neural Networks
Authors: Chen Cai
Dingkang Wang
Yusu Wang
Venue: ICLR 2021 Poster (2021)
Keywords: graph coarsening
graph neural network
Doubly-weighted Laplace operator

Abstract: As large scale-graphs become increasingly more prevalent, it poses significant computational challenges to process, extract and analyze large graph data. Graph coarsening is one popular technique to reduce the size of a graph while maintaining essential properties. Despite rich graph coarsening literature, there is only limited exploration of data-driven method in the field. In this work, we leverage the recent progress of deep learning on graphs for graph coarsening. We first propose a framework for measuring the quality of coarsening algorithm and show that depending on the goal, we need to carefully choose the Laplace operator on the coarse graph and associated projection/lift operators. Motivated by the observation that the current choice of edge weight for the coarse graph may be sub-optimal, we parametrize the weight assignment map with graph neural networks and train it to improve the coarsening quality in an unsupervised way. Through extensive experiments on both synthetic and real networks, we demonstrate that our method significantly improves common graph coarsening methods under various metrics, reduction ratios, graph sizes, and graph types. It generalizes to graphs of larger size (more than $25\times$ of training graphs), adaptive to different losses (both differentiable and non-differentiable), and scales to much larger graphs than previous work.

Published as a conference paper at ICLR 2021
GRAPH COARSENING WITH NEURAL NETWORKS
Chen Cai *
Dingkang Wang"
Yusu Wang
ABSTRACT
As large-scale graphs become increasingly more prevalent, it poses significant computational challenges to process, extract and analyze large graph data. Graph coarsening is one popular technique to reduce the size of a graph while main- taining essential properties. Despite rich graph coarsening literature, there is only limited exploration of data-driven methods in the field. In this work, we lever- age the recent progress of deep learning on graphs for graph coarsening. We first propose a framework for measuring the quality of coarsening algorithm and show that depending on the goal, we need carefully choose the Laplace operator on the coarse graph and associated projection/lift operators. Motivated by the obser- vation that the current choice of edge weight for the coarse graph may be sub- optimal, we parametrize the weight assignment map with graph neural networks and train it to improve the coarsening quality in an unsupervised way. Through ex- tensive experiments on both synthetic and real networks, method significantly improves common graph coarsening methods under various metrics, reduction ratios, graph sizes, and graph types. It generalizes to graphs of larger size (25x of training graphs), is adaptive to different losses (differentiable and non-differentiable). and scales much larger graphs than previous work.
demonstrate that our
INTRODUCTION
Many complex structures can be modeled by graphs, such as social networks, molecular graphs, bio- logical protein-protein interaction networks, knowledge graphs, and recommender systems. As large ceale-graphs become increasingly ubiquitous in various applications, they pose significant computa- tional challenges to process, extract and analyze information. It is therefore natural to look for ways to simplify the graph while preserving the properties of interest.
There are two major ways to simplify graphs. First, one may reduce the number of edges, known as graph edge sparsification. It is known that pairwise distance (spanner), graph cut (cut sparsifier), eigenvalues (spectral sparsifier) can be approximately maintained via removing edges. A key result (Spielman & Teng 2004) in the spectral sparsification is that any dense graph of size N can be sparsified to O(Nlog" N7c²) edges in nearly linear time using simple randomized algorithm based on the effective resistance.
Alternatively, one could also reduce the number of nodes subset of the original node set. The first challenge here is how to choose the topology (edge set) of the smaller graph spanned by the sparsified node set. On the extreme, one can take the complete graph spanned by the sampled nodes. However, its dense structure prohibits easy interpretation and poses computational overhead for setting the (n2) weights of edges. This paper focuses on graph coarsening, which reduces the number of nodes by contracting disjoint sets of connected vertices. The original idea dates back to the algebraic multigrid literature (Ruge & Stüben 1987) and has found various applications in graph partitioning (Hendrickson & Leland 1995; Karypis & Kumar 1998] Kushnir et al. (006). visualization (Harel & Koren, 2000; Hu| 2005| Walshaw 2000) and machine learning (Lafon &
Lee 2006 Gavish et al. 2010 Shuman al. (0155).
However, most existing graph coarsening algorithms come with two restrictions. First, they are prespecified and not adapted to specific data nor different goals. Second, most coarsening algorithms set the edge weights of the coarse graph equal to the sum of weights of crossing edges in the original
* "University of California, San Diego,
1 OOio State University, wang. 61506osu, edu I University of California, San Diego, yusuwang@ucad.cc

---

Published as a conference paper at ICLR 2021
graph. This means the weights of the coarse graph is determined by the coarsening algorithm (of the vertex set), leaving no room for adjustment.
With the two observations above, aim to develop data-driven approach to better assigning weights for the coarse graph depending on specific goals at hand. We will leverage the recent progress of deep learning on graphs develop framework learn assign edge weights in an unsupervised manner from a collection of input (small) graphs. This learned weight-assignnet map can then be applied new graphs (of potentially much larger sizes). In particular, our contributions are threefold.
First, depending on the quantity of interest F (such the quadratic form w.r.t Laplace oper- ator), one has to carefully choose projection/lift operator to relate quantities defined on graphs of different sizes. We formulate this as the invariance of F under lift map, and provide three cases of projection/lift map as well as the corresponding operators on the coarse graph. Interest- ingly, those operators all can be seen as the special cases of doubly-weighted Laplace operators on coarse graphs (Horak & Jost 2013).
Second, we are the first to propose and develop framework learn the edge weights of the coarse graphs via graph neural networks (GNN) in an unsupervised manner. We show convincing results both theoretically and empirically that changing the weights is crucial to improve the quality of coarse graphs.
Third, through extensive experiments on both synthetic graphs and real networks, we demonstrate that our method GOREN significantly improves common graph coarsening methods under differ- ent evaluation metrics, reduction ratios, graph sizes, and graph types. generalizes to graphs of larger size (than the training graphs), adapts to different losses (so as to preserve different prop- erties of original graphs), and scales to much larger graphs than what previous work can handle. Even for losses that are not differentiable w.r.t the weights of the coarse graph, we show training networks with a differentiable auxiliary loss still improves the result.
2 RELATED WORK
Graph sparsification. Graph sparsification is firstly proposed to solve linear systems involy- ing combinatorial graph Laplacian efficiently. [Spielman & Tengl (2011); [Spielman & Srivastava (201T) showed that for any undirected graph G of N vertices, a spectral sparsifier of G with only O(Nloy 2) edges can be constructed in nearly-linear time. [ Later on, the time complexity and the dependency on the number of the edges are reduced by various researchers (Batson et al. 2012
Allen-Zhu et al. 2015 Lee & Sun 2018 2017).
Graph coarsening. Previous work on graph coarsening focuses on preserving different properties, usually related to the spectrum of the original graph and coarse graph. [oukas & Vandergheynst (018)]; [oukas| (2019) focus on the restricted spectral approximation, a modification of the spec- tral similarity measure used for graph sparsification. [Hermsdorff & Gunderson (2019) develop probabilistic framework to preserve inverse Laplacian.
Deep learning on graphs. As an effort of generalizing convolution neural network to the graphs and manifolds, graph neural networks is proposed to analyze graph-structured data. They have achieved state-of-the-art performance in node classification (Kipf & Welling 2016). knowledge graph com-
pletion (Schlichtkrull et al., 2018), link prediction (Dettmers et al. 2018 Gurukar et al. 2019).
combinatorial optimization (Li et al., 2018b; Khalil et al.] 2017). property prediction (Duvenaud et al. 2015 Xie & Grossman 2018) and physics simulation
et al.) (020).
Deep generative model for graphs. To generative realistic graphs such as molecules and parse trees, various approaches have been taken to model complex distributions over structures and at- tributes, such as variational autoencoder (Simonovsky & Komodakis) 2018 Ma et al.] (208)) gen- erative adversarial networks (GAN) (De Cao & Kipt, 2018 Zhou et al. 2019), deep autoregres- sive model (Liao et al.) 2019 You et al. 2018b]] Li et al. 2018a), and reinforcement learning type approach (You et al.) 2018a). Zhoou al. (2019) proposes
based framework to preserve the hierarchical community structure via algebraic multigrid method during the generation process. However, different from our approach, the coarse graphs in Zhou et al. 2019) are not learned.
'The algorithm runs in (M.polly) time, where M and N are the numbers of edges and vertices.
2

---

W. The normalized Published as a conference paper at ICLR 2021
3 PROPOSED APPROACH: LEARNING EDGE WEIGHT WITH GNN
3.1 HIGH-LEVEL OVERVIEW
Our input is non-attributed (weighted unweighted) graph G (V. E). Our goal to construct an appropriate "coarser" graph G
g
(V.E) that preserves certain properties of G. Here, by a "coarser"
[V] and there is a surjective map т V + V that we call the vertex map. Intuitively, (see figure on the right), for any node è V, all nodes x - V are mapped to this super-node i in the coarser graph G. We will later propose a GNN based framework that can be trained using a collection of existing graphs in an unsupervised manner, as to construct such coarse graph G for a future input graph G' (presumably coming from the same family as training graphs) that can preserve properties G effectively.
graph, we assume that [V| <<
We will in particular focus preserving properties of the Laplace operator Og of G, which is by far the most common operator associated to graphs, and forms the foundation for spectral methods. Specifically, given G (V {V1,-... UN F) with
F + R being the weight function for G (all edges have weight if G is unweighted). let W the corresponding N x N edge-weight matrix where W []] = w (%, Uz) if edge (U), 22)) E E' and otherwise. Set D to be the N N diagonal matrix with D [b]][i] equal to the sum of weights of all edges incident to ey. The standard (un- normalized) combinatorial Laplace operator of G is then defined as
Laplacian is defined as L = D- 1/22 1/2 = - D 122 1/2
LD-1/2
However, make this problem as well as our proposed approach conerete, various components need to be built appropriately. We provide an overview here, and they will be detailed in the remainder of this section.
Assuming that the set of super-nodes V well as the map π V V are given, one still need to decide how to set up the connectivity (i.e, edge set E) for the coarse graph G (V, E). We introduce a natural choice in Section B.2, and provide some justification for this choice.
As the graph G and the coarse graph 2 have the different number of nodes, their Laplace operators Og and Og of two graphs are not directly comparable. Instead, we will compare F(OG. f) and F(O f). where F is functional intrinsic to the graph at hand (invariant to the permutation of vertices), such as the quadratic form or Rayleigh quotient. However, it turns out that depending on the choice of F,, we need to choose the precise form of the Laplacian Og. as well as the (so-called lifting and projection) maps relating these two objects, carefully, so they are comparable. We describe these in detail in Section 3.3
In Section 3.4 we show that adjusting the weights of the coarse graph G can significantly improve the quality of G. This motivates a learning approach to learn strategy (a map) to assign these weights from a collection of given graphs. We then propose a GNN-based framework to do so in
an unsupervised manner. Extensive experimental studies will be presented in Section 4
3.2 CONSTRUCTION OF COARSE GRAPH
Assume that we are already given the set of super-nodes V (iI,..., } for the coarse graph G together with the vertex map : V + V - There has been much prior work on computing the sparsified set V C V and æ (Loukas & Vandergheynst 2018 Loukas 2019); and if the vertex map v is not given, then we can simply define it by setting क (u) for each v E to be the nearest neighbor
of v in V in terms of graph shortest path distance in G Dey et al. 2013).
To construct edges for the coarse graph & = (V, Ê) together with the edge weight function ú Σ - R. instead of using complete weighted graph over V. which is too dense and expensive, we set É to be those edges "induced" from G when collapsing each cluster π (6) to its corresponding super- node i E V: Specifically, (ú, 6') E.r if and only if there is an edge (v, w') E E such that π T(w) à and x (v') V.. The weight of this edge is údū 8') := Σ (v."") (x=1()),x--()))) (1()) w(v, (() where
E(A, B) C E stands for the set of edges crossing sets A, B C V.e, w(ē, 8') is the total weights of all crossing edges in G between clusters म -1() and - (6') in V. We refer to & constructed
3

---

Let W be the edge weight matrix, and 1) be the diagonal matrix encoding the sum of edge weights incident to each vertex as before. Then the standard combinatorial Laplace operator w.r.t. G is simply L = D W. Published as a conference paper at ICLR 2021
this way the V -inducced coarse graph. As shown in Dey et al. (2013). if the original graph G is the 1-skeleton of a hidden space X, then this induced graph captures the topological X at coarser level if is a so-called ô-net of the original vertex set V w.r.t. the graph shortest path metric.
Interestingly, this construction of the coarse graph G coincides with the coarse Laplace operator for sparsified vertex set constructed by Loukas (2019) We will use this view of the Laplace operator later; hence we briefly introduce the construc- tion of Loukas 2019) (adapted to our setting): Given the vertex map π : V - V, we set a n N ma- if U3 E ((p)
Relation to the operator of (Loukas 2019).
trix P by P(r,
(6-)
what follows, we denote "/ == | (6,)
otherwise
for any E [1, n). which the size of the cluster of 8, in V. P can be considered the weighted projection matrix of the vertex set from V to V. Let P denote the Moore-Penrose pseudoinverse of P, which can be intuitively viewed as a way to lift a function on V (a vector in I2") to a function over V vector in R As shown in Loukas (219)), p+ is the N n matrix where p+ r] if and only if π (v;) = ê, See Appendix A.2 for toy example. Finally, Loukas (2019) defines an operator for the coarsened vertex set V to be L
(p+)" LPt Intuitively, L operators n-vectors. For any n-vector f E I2,, f first lifts ff to a N-vector f = p+ and then perform L on f, and then project it down to n-dimensional via (P+)².
Proposition 3.1. (Loukas 2019) The combinatorial graph Laplace operator L = δ W for the V -induced coarse graph G constructed above equals to the operator Lg = -(P+)TI.t
3.3 LAPLACE OPERATOR FOR THE COARSE GRAPH
We now have input graph G (V, and coarse graph G induced from the sparsified node set V. and we wish compare their corresponding Laplace operators. However, Og operates on RV (i.e, functions on the vertex set V of G) and O₂ operates on R", we will compare them by their effects on "corresponding" objects. Loukas & Vandergheynst (2018); Loukas (2119) proposed to use the quadratic form to measure the similarity between the two linear operators. In particular, given linear operator A on N and any x E R.N, Qx(x) x Ax. The quadratic form has also been used for measuring spectral approximation under edge sparsification. The proof of the following result is in Appendix A.2
Proposition 3.2. For any vector à E. R". we have that Q7(())
(2) (p where L is the com- binatorial Laplace operator for the Viinduced coarse graph G constructed above. That is, set = P a as the lift of ā in N then at = x"' La.
Intuitively, this suggests that if later, we measure the similarity between L and some Laplace operator for the coarse graph G based on a loss from quadratic form difference, then we should choose the Laplace operator Og to be L and compare Q7. (Pxz) with Qz(.). We further formalize this by considering the lifting map U IR"" N well projection map P R R" where p.u 2 = Id,. Proposition 3.2 suggests that for quadratic form-based similarity, the choices are
u = P and Og L. See the first row in Table
Table 1: Depending on the choice of F (quantity that we want to preserve) and Oc, we have different projection/lift operators and resulting Og on the coarse graph.
Quantity F of intorest On Projection
Liftl
Og
Invariant under 1/
Quadmatic form Q
p+
Combinatoraa Laplace
(t()))) 9 (R)
Rayleigh quotient R
p-r-1/2
weubly-weighhed Laplace (M()) (x)
Quadratic form Q
Bu2pD
Normalized Laplace &
Q2(4F) Qz(R)
On the other hand, eigenvectors and eigenvalues of a linear operator A are more directly related, via Courant-Fischer Min-Max Theorem, to its Rayleigh quotient R R* ='Az, Interestingly, in
4

---

Published as a conference paper at ICLR 2021
this case, to preserve the Rayleigh quotient, we should change the choice of Og to be the following doigly-weighted Laplace operator for a graph that is both edge and vertex weighted.
Specifically, for the coarse graph G we assume that each vertex Ô E V is weighted by Va = JT (0)), the size of the cluster from G that got collapsed into è. Let I' be the vertex matrix, which is the n X n diagonal matrix with [[r][r] Yé.. The doubly-weighled Laplace operator for a vertex-
and adge-weighted graph G is then defined as:
- (D W/ = 1/2 1r- - -PP-TT-1Y
The concept of weight- Laplace for a vertex- and edge-weighted graph is not new, see e.g Chung & Langlands (1996); Horak & Jost (2013); Xu et al. (2019). In particular, Horak & Jost (2013) proposes a general form of combinatorial Laplace operator for a simplicial complex where all simplices are weighted, and our doubly-weighted Laplace has the same eigenstructure as their Laplacian when restricted to graphs. See Appendix A.I for details. Using the doubly-weighted Laplacian for Rayleigh quotient based similarity measurement between the original graph and the coarse graph is justified by the following result (proof in Appendix (A.I).
Proposition 3.3. For any vector I E IR", we have that ( = R2 That is, set the
lift of & in RNN to be x = p-pp-/--ppppp 1/2 then we have that
La x= Lx
272 x²
Finally, if using the normalized Laplace L for the original graph G, then the appropriate Laplace operator for the coarse graph and corresponding projection/lift maps are listed in the last row of with proofs in Appendix|A.. A.2
Table I
3.4 GNN-BASED FRAMEWORK FOR LEARNING FOR CONSTRUCTING THE COARSE GRAPH
G
CDREN
Mirimtee
Loas(Do, Oa))
Figure 1: An illustration of learnable coarsening framework. Existing coarsening algorithm deter- mines the topology of coarse graph G, while GOREN resets the edge weights of the coarse graph.
In the previous section, we argued that depending on what similarity measures we use, appropriate Laplace operator Og for the coarse graph G should be used. Now consider the specific case of Rayleigh quotient, which can be thought of as a proxy to measure similarities between the low- frequency eigenvalues of the original graph Laplacian and the one for the coarse graph. As described
above, here we set Og the doubly-weighted Laplacian [ 1-11111/22 1 -1/2
The effect of weight adjustments. We develop an iterative algorithm with convergence guarantee (to KKT point (.4 for optimizing over edge weights of G for better spectrum alignment. As shown in the figure on the right, after changing the edge weight of the coarse graph, the resulting graph Laplacian has eigenvalues much closer (almost identical) to the first n eigenvalues of the original graph Laplacian. More specifically, in this figure, G.e and Gc.e stand for the cigenvalues of the original graph G and coarse graph G constructed by the so-called Variation- Edge coarsening algorithm (Loukas (011)). "After- Opt" stands for the eigenvalues of coarse graphs when weights are optimized by our iterative algorithm. See Appendixii for the description of our iterative algorithm, its conver- gence results, and full experiment results.
GNN-based framework for learning weight assignment map. The discussions above indicate that we can obtain better Laplace operators for the coarse graph by using better-informed weights than simply summing up the weights of crossing edges from the two clusters. More specifically, suppose we have fixed strategy to generate V from an input graph G = (V, E). Now given an edge (6, 0') E in the induced coarse graph & (V, F), model its weight vú 0') by
5

---

Published as a conference paper at ICLR 2021
weightt-ssignnen function subset of vertices A. However, it is not clear how to setup this function μ.. Instead, we will learn from collection of input graphs in an unsupervised manner. Specifically, we will parametrize the weight-assignment map/ ja by learnable neural network Ma. See Figure 1
where G| is the subgraph of G induced by
for an illustration.
In particular, we Graph Isomorphism Network (GIN) (Xu et al. 2018) to represent Ma- We initialize the model by setting the edge attribute of the coarse graph to be 1. Our node feature is set to be a 5-dimensional vector based on LDP (Local Degree Profile) (Cai & Wang 2018). We enforce the learned weight of the coarse graph to be positive by applying one extra ReLU layer to the final output. All models are trained with Adam optimizer with a learning rate of 0.001. See Appendix for more details. We name our model as Graph cOarsening RefinemEnt Network (GOREN).
Given graph G and a coarsening algorithm A, the general form of loss is
Loss(Oc, O
F(Oa. F(O a. Pf(),,
where Si is signal on the original graph (such as eigenvectors) and Pf; is its projection. We use Og to denote the operator of the coarse graph during training, while Og standing for the operator defined w.r.t. the coarse graph output by coarsening algorithm A. That is, we will start with O and modify it to Og during the training. The loss can be instantiated for different cases in Table For example, loss based quadratic form means that we choose Oc, Og to be the combinatoral Laplacian of G and G2 and the resulting quadratic loss has the form: &
Loss( L,. L.)
1 T: I -PA
It can be seen as a natural analog of the loss for spectral sparsification in the context of graph coars- ening, which is also adopted in Loukas| (2019). Similarly. one can use loss based on the Rayleigh quotient, by choosing F from the second row of Table [ Our framework for graph coarsening is flexible. Many different loss functions can be used as long as it is differentiable the weights of the coarse graph. we will demonstrate this point in Section 4.4
Finally, given collection of training graphs GI...., Gm. we will train for parameters in the module Mo to minimize the total loss training graphs When test graph Gtest is given, we simply apply Mo to set up weight for each edge in Gtests obtaining new graph Grest,t- We compare Loss (Orrarr O Grann against Coss(OGraass O G and expect the former loss is smaller.
4 EXPERIMENTS
In the following experiments, we apply six existing coarsening algorithms to obtain the coarsened vertex set V. which Affinity (Livne & Brandt 2012). Algebraic Distance (Chen & Safro 2011 1) Heavy edge matching (Dhillon et al. 2207] et al. 2011)) 1) as well as two local variation methods based on edge and neighborhood respectively (Loukas) 2019). and simple baseline (BL); See Appendix D for detailed descriptions. The two local variation methods are considered to be state- of-the-art graph coarsening algorithms Loukas (2019). We show that our GOREN framework can improve the qualities of coarse graphs produced by these methods.
4.1 PROOF OF CONCEPT
As proof of concept, we show that GOREN can improve common coarsening meth- ods on multiple graphs (see C.2 for de- tails). Following the same setting as Loukas 2019), we use the relative eigenvalue er- for as evaluation metric. It is defined 1 EΣ [ where Ar 2, denotes eigenvalues of combinatorial Laplacian L for G and weight-weighted Laplacian [ for G respectively, and k is set to be 40. For simplicity,
Table 2: The error reduction after applying GOREN,
Algebraic Distance
Heavy Edge
Local var (odges)
Local var (neigh.)
Datasct
Affinity
Airfoil
91.7%
88.2%
86.1%
43.2%
73.6%
Minnesota
49.8%
57, 57.2%
30.1%
5.50%
1.60%
Yeast
49.7%
51.3%
37.4%
27.9%
21.1%
Bunny
84.7%
69.1%
61.2%
19.3%
81.6%

---

Published as a conference paper at ICLR 2021
Table 3: Loss: quadratic loss. Laplacian: combinatorial Laplacian for both original and coarse graphs. Each entry svy) is: x loss w/o learning, and improvement percentage.
Dataset
BL
Affinity
Algehraic Distance
Heavy
Local var (edgos)
Local var (acigh.)
Edge
Syntheric
BA
0.44 (16.1%)
0.44 (4.4%)
0.68 (4.3%)
0.61 (3.6%)
0.21 (14.1%)
0.18 (72.7%)
FR
0.36 (1.1%)
0.52 (0.8%)
0.35 (0.4%)
0.36 (0.2%)
0.18 (1.2%)
0.02 (7.4%)
GEO
0.71 (87.3%)
0.20 (57.8%)
0.24 (31 4%%)
0.55 (80.4%)
0.10 (59.6%)
0.27 (65.0%)
WS
0.45 (62.9%
0.09 (82.1%)
0.09 (60 6%)
0.52 (51.8%)
0.09 (69.9%)
0.11 (84,2%)
CS
0.39 (40.0%
0.21 (29.8%)
0.17 (26.4%)
0.14 (20.9%)
0.06 (36.9%)
0.0 (59.0%)
Hickr
0.25 (10.2%)
0,25 (5.0%)
0.19 (6.4%)
0.26 (5.6%)
0.11 (11.2%))
0.07 (21.8%)
Real
Physicy
0:40 (47.44%)
0.37 (42.4%)
0.32 (49.7%)
0.14 (28.0%)
0.15 (60.3%
0.0 (-0.3%)
PubMed
0.30 (23.4%)
0.13 (10.5%)
0.12 (15.9%)
0.24 (10.8%)
0.06 (11.8%)
0.01 (36.4%)
Shape
0.23 (91.4%)
0.08 (89.8%)
0.06 (82.2%)
0.17 (88.2%)
0.04 (80.2%)
0.08 (79.4%)
this error is denoted as Eigenerror in the remainder of the paper. Denote the Eigenerror of graph coarsening method as 1 and Eigenerror obtained by GOREN as 12. In Table we show the error- reduction ratio, defined as 11-12, The ratio is upper bounded by 100% in the case of improvement (and the larger the value is, the better); but it not lower bounded.
Since it is hard to directly optimize Eigenerror, the loss function we use in our GOREN set to be the Rayleigh loss Loss(O O = & (F(c.... - F( Pfii where F is Rayleigh quotient, P = ( and Og being use Rayleigh loss as a differentiable proxy for the Eigenerror. As we can see in Table 2 GOREN reduces the Figenerror by a large margin for training graphs, which serves as a sanity check for our framework, as well as for using Rayleigh loss as proxy for Eigenerror. Due to space limit, see Table G.T for full results where we reproduce the results in [Loukas] (2019) up to small differences. In Table 5
Laplacian L, In other words, We
we will demonstrate this training strategy also generalizes well to unseen graphs.
4.2 SYNTHETIC GRAPHS
We train the GOREN on synthetic graphs from common graph generative models and test on larger unseen graphs from the same model. We randomly sample 25 graphs of size {512, 612, 712, .... 2912] from different generative models. If the graph is disconnected, we keep the largest component. We train GOREN on the first graphs, use the graphs from the rest 20 graphs the validation set and the remaining 15 as test graphs. We use the following synthetic graphs: Frrdös-Rnyy graphs (ER), Kerabasi-Albert Graph (BA), Watts- Strott-trrgatz Graph (WS), ran- dom geometric graphs (GEO). See Appendix for datasets details.
For simplicity, we only report experiment results for the reduction ratio 0.5. For complete results of all reduction ratios (0.3, 0.5, 0.7), see Appendix G We report both the loss Loss(L, L) of different
algorithms (w/o learning) and the relative improvement percentage defined as -oss(L. Loss(L,L)
when GOREN is applied, shown in parenthesis. As we can see in Table 3 for most methods, trained on small graphs, GOREN also performs well on test graphs of larger size across different algorithms and datasets Again, the larger improvement percentage is, the larger the improvement by our algorithm is, and a negative value means that our algorithm makes the loss worse. Note the size of test graphs are on average 2.6x the size of training graphs. For ER and BA graphs, the improvement is relatively smaller compared to GEO and WS graphs. This makes sense since ER and BA graphs are rather homogenous graphs, leaving less room for further improvement.
4.3 REAL NETWORKS
We test on five real networks: Shape, PubMed, Coauthor-CSS (CS), Coauthor-Physic (Physics), and Flickr (largest one with 89k vertices), which are much larger than datasets used in Hermsdorff & Gunderson 2019 (< 1.5k) and Loukas 2019) (S 4k). Since it is hard to obtain multiple large graphs (except for the Shape dataset, which contains meshes from different surface models) coming from similar distribution, we bootstrap the training data in the following way. For the given graph, randomly sample collection of landmark vertices and take random walk of length I starting from selected vertices. We take subgraphs spanned by vertices of random walks as training and validation graphs and the original graph as the test graph. See Appendix C.3 for dataset details.
7

---

Published as a conference paper at ICLR 2021
Table Loss: quadratic loss. Laplacian: normalized Laplacian for original and coarse graphs. Each entry svy) is: x = loss w/o learning, and y improvement percentage.
Dataset
BL
Aflinity
Distance
Algebnicc
Heavy Edge
var (edges)
Local (ncigh)
Synthetic
BA
0.13 (76.2%)
0.14 (45.0%)
0.15 0.15 (51.8%)
0.15 (46.6%)
0.14 (55.39))
0.06 (57.25%
ER
0.10 (82.2%)
0.10 (83.9%)
0.09 (79.3%)
0.09
0.06 (64.6%)
0.06 (75.4%)
GEO
0.01 (52.8%)
0.01 (12.4%)
0.01 (27.0%)
0.03 (56.3%)
0.01 (-145.1%)
0.02 (-9.7%)
WS
0.05 (83.3%)
0.01 (-1.7%)
0.01 (38.6%)
0.05 (50.3%)
0.01 (10.9%)
0.01 (10.8%)
CS
0.08 (58.0%)
0.06 (37.2%)
0.04 (12.8%)
0.05 (41.5%)
0.02 (16.8%))
0.01 (50.4%)
Flickr
0.08 (-31.9%
0.06 (-27.6%)
0.06 (-67.2%)
0.07 (-73,8%)
0.02 (-440.1%)
0.02 (-43,9%)
Physics
0.07 (47.9%)
(40.1%)
0.04 (17.4%)
(61.4%)
0.02 (:23.35))
(35.6%)
PuhMed
0.05 (47.8%%
0.05 (35.0%5)
0.05 (41.1%)
0.12 (46.8%)
0.03 (-66.4%)
0.01 (-118.0%)
Shape
0.02 (84.4%)
0.01 (67.7%)
0.01 (58.4%)
0.02 (87.4%)
0.0 (13.39)
0.01 (43.8%)
Table 5: Loss: Eigenerror. Laplacian: combinatorial Laplacian for original graphs and doubly- weighted Laplacian for coarse ones. Each entry sxy) is: = loss w/o learning, and y improve- ment percentage. t stands for out of memory.
Algebraic
Hcavy
Local var (odges)
Local (neigh.)
Dataset
BL
Aflinity
Distance
Edge
Synthetic
BA
0.36 (7.1%)
0.17 (8.2%)
0.22 (6.5%)
0.22 (4.7%)
0.11 (21.1%)
(-15.99))
ER
0.61 (0.5%)
0.70 (1.0%)
0.35 (0.6%)
0.36 (0.2%)
0.19 (1.2%)
0.02 (0.8%)
GEO
1.72 (50.3%)
0.16 (89. 4%)
0.18 (91.2%)
0.45 (84.9%)
0.08 (55.6%)
0.20 (86.8%)
1.59 (43.9%)
0.11 (88.2%)
(83.9%)
0.58 (23.5%)
0.10 (88.2%)
0.12 (79.79)
CS
1.10 (18.0))
0.55 (49.8%)
0.33 (60.6%)
0.42 (44.5%)
0.21 (75.2%)
(-154.2%)
Flickr
0.57 (55.7%)
(20.2%)
(55.0%)
0.11 (67.6%)
0.07 (60.3%
Physics
1.06 (21.7%)
0.58 (67.1%)
0.33 (69.5%)
0.35 (64.6%)
0.20 (79.0%
0.0 (-377.9%)
PubMedl
1.25 (7.1
0.50 (15.5%)
0.51 (12.3%)
(-110.)0
0.35 (-8.8%)
0.02 (60.4%)
Shape
2,07 (67.7%)
0,24 (93.3%)
0.17 (90.9%)
0.49 (93.0%)
0,11 (84.2%)
0.20 (90.75)
As shown in the bottom half of Table 3 across all six different algorithms, GOREN significantly improves the result among all five datasets in most cases. For the largest graph Flickr, the size of test graphs is more than 25 x the training graphs, which further demonstrates the strong generalization.
4.4 OTHER LOSSES
Other differentiable loss. To demonstrate that our framework is flexible, we adapt GOREN to the following two losses. The two losses are both differentiable w.r.t the weights of coarse graph.
(1) Loss based normalized graph Laplacian: Loss(C, 2.) E If Lf: (Pf) (P))) Here {fi} are the set of first & eigenvectors of the normalized Laplacian of original grpah G, and P = 11/2 1/2 (2) Conductance difference between original graph and coarse graph. Eecsuis ai where
Loss = -E - (((((S))) ((S) is the conductance (s()) :=
(Sn(((()).((5))
a(S) Eies EiesEjev aij. We randomly sample & subsets of nodes Sp. So.,...55 Sp V where |S,] is set to be random number sampled from the uniform distribution (VV1/4, Due to space limits, we present the result for conductance in Appendix G.3
Following the same setting as before, we perform experiments to minimize two different losses. As shown in Table 4 and Appendix G.3 for most graphs and methods, GOREN still shows good generalization capacity and improvement for both losses. Apart from that, we also observe the initial loss for normalized Laplacian is much smaller than that for standard Laplacian, which might be due to that the fact that eigenvalues of normalized Laplacian are in [0, 2].
Non-differentiable loss. In Section 4.1 we use Rayleigh loss as a proxy for training but the Eigen- error for validation and test. Here we train GOREN with Rayleigh loss but evaluate Eigenerror on test graphs, which is more challenging. Number of vectors & is 40 for synthetic graphs and 200 for real networks. As shown in Table S our training strategy via Rayleigh loss can improve the eigen- value alignment between original graphs and coarse graphs in most cases. Reducing Eigenerror is more challenging than other losses, possibly because we are minimizing a differentiable proxy (the Rayleigh loss). Nevertheless, improvement is achieved in most cases.
8

---

Published as a conference paper at ICLR 2021
Table 6: Model comparison between MI. and GOREN. Loss: quadratic loss. Laplacian: combina- torial Laplacian for both original and coarse graphs. Each entry x xyy is: I = loss w/o learning, and y improvement percentage.
Datasel
Ratio
BL.
Affinity
Distance
Algehmic
Heavy Edge
(odges)
Local var
Local var (neigh.)
0.3
0.27 (46.258)
0.04 (4.19)
0.04 (:38.0%)
0:43 (31.2%)
0.06 (67 09%)
+ ML.P
0.5
0.45 (62.99)
0.09 15g
(15.0)))
0.52 (31.25))
0.09 (31.6%)
(58.59)
0,7
0.65 (70,45)
0.15 (57.6%)
0.34 (31.6%)
0.67 (76.6%)
0.15
0.16 (54.7%)
0.3
0.27 (16.2%)
(604 (65.6%)
0.04 (-26.9%)
0:43 (32,9%)
0.02 (68.2%)
0.06 (73.25)))
COREN
0.5
0.45 (62,953
0.09 (82.11)
0.09 (60.6%)
0.52 (518%)
0.09 (69,916
0.11 (84.2%)
0.7
0.65 (73.4%))
0.15 (78.488)
0.14 (66.7%6)
0.67 (76.6%)
0.15 (80.8%)
0.16 (K3.2%)
0.3
0.13 (76.6%)
0.04 (-53.496)
0.03 (-157.0%)
0.11 (69.3%)
0.0 (-229.688))
0.04
Shape + MLP
0.5
0.23 (78849%)
0.08 (-11 (.6)
(57.686)
0.17 (83.25)
0.04 (44.2%)
0.08 (-1 (-1.9%)
0.34 (69.9%)
(8))
(73.58)
0.24 (65.8%)
(74.3%)
(85,
0,3
0.13 (56.8%)
0.04 (79.8%)
0.03 (69.09%
0.11 (69.7%)
0.0 (1.39)
0.04 (73.69)
Shape GOREN
(91.433
(89.8%)
0.06 (82.2%%
(80.2%)
(79.15)
0.7
0.34 (91.155)
0.17 (94.3%%
0.1 (74.7%6)
0.24 (93.9%
0.09 (64.6%
0.13 (84.8%)
4.5 ON THE USE OF GNN WEIGIIT-ASSIGNMENT MAP
Recall that we use GNN to represent edge-weight assignment map for an edge (ú, 6) between two super-nodes ú, è in the coarse graph G. The input will be the subgraph GR,E in the original graph G spanning the clusters π (i)), π 15), and the crossing edges among them; while the goal is to compute the weight of edge (û, 6) based on this subgraph Ga,ø. Given that the input is local graph Ga,s, GNN will be natural choice to parameterize this edge-wad weight assignment map. Nevertheless, in principle, any architecture applicable to graph regression can be used for this purpose. To better understand if it is necessary use the power of GNN, replace GNN with the following baseline for graph regression. In particular, the baseline is a composition of mean pooling of node features in the original graph and a 4-layer MIP with embedding dimension 200 and ReI.U nonlincarity. We use mean-pooling as the graph regression component needs to be permutation invariant over the set of node features. However, this baseline ignores the detailed graph structure which GNN will leverage. The results for different reduction ratios are presented in the table 6 We have also implemented another baseline where the MLP module replaced by a simpler linear regression module. The results are worse than those of MLP (and thus also GNN) expected, and therefore omitted from this paper.
As we can see, MLP works reasonably well in most cases, indicating that learning the edge weights is indeed useful for improvement. On the other hand, we see using GNN to parametrize the map generally yields larger improvement over the MLP, which ignores the topology of subgraphs in the original graph. A systematic understanding of how different models such as various graph kernels (Kriege et al. 2020 Vishwanathan et al. 2010) and graph neural networks affect the performance is an interesting question that we will leave for future work.
5 CONCLUSION
We present a framework to compare original graph and the coarse one via the properly chosen Laplace operators and projection/lift map. Observing the benefits of optimizing over edge weights, we propose a GNN-based framework to learn the edge weights of coarse graph to further improve the existing coarsening algorithms. Through extensive experiments, we demonstrate that our method GOREN significantly improves common graph coarsening methods under different metrics, reduction ratios, graph sizes, and graph types.
ACKNOWLEDDGMMEN
This work is partially supported by National Science Foundation under grants OAC-2039794 and IIS 105-0000 Chen Cai would like to thank Huang Fang for helpful discussion on optimization algorithms.

---

Published as a conference paper at ICLR 2021
REFERENCES
Zeyuan Allen-Zhu, Zhenyu Liao, and Lorenzo Orecchia. Spectral sparsification and regret mini- mization beyond matrix multiplicative updates. In Proceedings of the forty-seventh annual ACM symposium on Theory of computing, pp. 237-245, 2015.
Francesco Barioli and Shaun Fallat. On two conjectures regarding an inverse eigenvalue problem for acyclic symmetric matrices. The Electronic Journal of Linear Algebra, 11, 2004.
Joshua Batson, Daniel Spielman, and Nikhil Srivastava. Twice-ramanujan sparsifiers. SIAM Journal on Computing, (1tenng...11))))))))) 1764:117041 2012.
Chen Cai and Yusu Wang. A simple yet effective baseline for non-attributed graph classification. arXiv preprint arXiv: 181.00881,003508,, 2018.
Cätälina Cangea, Petar Veličković, Nikola Jovanović, Thomas Kipf, and Pictro Liò. Towards sparse hierarchical graph classifiers. arXiv preprint arXiv:1811.01287, 2018.
Jie Chen and Ilya Safro. Algebraic distance graphs. SIAM Journal on Scientific Computing, 33 (6):3468-344 2011.
Fan RK Chung and Robert Langlands. A combinatorial laplacian with vertex weights. journal of combinatorial theory, Series A, 75(2):316-32) 1996.
Nicola De Cao and Thomas Kipf. Molgan: An implicit generative model for small molecular graphs. arXiv preprint 0rXiv:/805.11973, 2018.
Tim Dettmers, Pusquale Minervini. Pontus Stenetorp. and Sebastian Riedel. Convolutional 2d knowledge graph embeddings. In Thirty-Second AAAI Conference on Artificial Intelligence, 2018.
Tamal Krishna Dey, Fengtao Fan, and Yusu Wang. Graph induced complex on point data. In Proceedings of the twenty-ninth annual symposium on Computational geometry, pp. 107-116, 2013.
Inderjit S Dhillon, Yuqiang Guan, and Brian Kulis. Weighted graph cuts without eigenvectors multilevel approach. IEEE transactions on paltern analysis and machine intelligence, 29(11): 1944-1957, 2007.
Yihe Dong and Will Sawin. Copt: Coordinated optimal transport on graphs. In Ad-
vances in Neural Information Processing Systems, volume 33, pp. 19338, 2020.
URL httpss://procceeddng...tt neurips cc/ wctpappr//02///111..... 60220039807223330770000000-----2
David K Duvenaud, Dougal Maclaurin, Jorge Iparraguirre, Rafael Bombarell, Timothy Hirzel, Alán Aspuru-Guzik, and Ryan P Adams. Convolutional networks on graphs for learning molecular fingerprints. In Advances in neural information processing systems, pp. 2224-2232, 2015.
Shaun M Fallat, Leslie Hogben, Jephian C-H Lin, and Bryan L Shader. The inverse eigenvalue problem of graph, zero forcing, and related parameters. Notices of the American Mathematical Society, 62)2), 2020.
Matthias Fey and Jan Eric Lenssen. Fast graph representation learning with pytorch geometric. arXiv preprint arXiv: 1xX3:2/903302223 2019.
Hongyang Gao and Shuiwang Ji. Graph u-nets. arXiv preprint arXiv: 19550:1905.05178, 2019.
Vikas Garg and Tommi Jaakkola. Solving graph compression via optimal transport. In Advances in Neural Information Processing Systems, pp. 8012-8023, 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 ICML, pp. 367-374, 2010.
David Gleich. Matlabbgl. matlab graph library. Institute for Computational and Mathematical Engineering, Stanford University, 2008
10

---

Published as a conference paper at ICLR 2021
Saket Gurukar, Priyesh Vijayan, Aakash Srinivasan, Goonmeet Bajaj. Chen Cai, Moniba Key- manesh, Saravana Kumar, Pranav Maneriker, Anasua Mitra, Vedang Patel, et al. Network repre- sentation learning: Consolidation and renewed bearing. arXiv preprint arxtv:1905.00987 2019.
David Harel and Yehuda Koren, A fast multi-scall method for drawing large graphs. In International symposium on graph drawing, pp. 183-196. Springer, 2000.
Bruce Hendrickson and Robert W Leland. A multi-level algorithm for partitioning graphs. SC, 95 (28):1-14, 1995.
Gecia Bravo Hermsdorff and Lee Gunderson. A unifying framework for Seectrum-preservvin graph sparsification and coarsening. In Advances in Neural Information Processing Systems, pp. 7734- 7745, 2019.
Leslie Hogben. Spectral graph theory and the inverse eigenvalue problem of a graph. The Electronic Journal of Linear Algebra, 14, 2005.
Danijela Horak and Jürgen Jost. Spectra of combinatorial laplace operators on simplicial complexes. Advances in Mathematics, 244:303-336, 2013.
Yifan Hu. Efficient, high-quality force-directed graph drawing. Mathematica Journal, 10(1):37-71, 2005.
Hawoong Jeong, Sean P Mason, A-L Barabási, and Zoltan N Oltvai. Lethality and centrality in protein networks. Nature, 41 (66833)441-2,,
George Karypis and Vipin Kumar. A fast and high quality multilevel scheme for partitioning irreg- ular graphs. SIAM Journal on scientific Computing, 20(1):359-392, 1998.
Elias Khalil, Hanjun Dai, Yuyu Zhang, Bistra Dilkina, and Le Song. Learning combinatorial op- timization algorithms over graphs. In Advances in Neural Information Processing Systems, pp. 6348-6358, 2017.
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. arXiv preprint arXiv: wew.iii699.2277.. 2016.
Nils M Kriege, Fredrik Johansson, and Christopher Morris. A survey on graph kernels. Applied Network Science, 5(1):1-42, 2020.
Sandeep Kumar, Jiaxi Ying, Jose Vinieius de Miranda Cardoso, and Daniel Palomar. Structured graph learning via laplacian spectral constraints. In Advances in Neural Information Processing Systems, pp. 11651-11663. 2019.
Dan Kushnir, Meirav Galun, and Achi Brandt. Fast multiscale clustering and manifold identification. Pattern Recognition, 19(10):1876-199 2006.
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 pattern analysis and machine intelligence,
2006.
Junhyun Lee, Inyeop Lee, and Jaewoo Kang. Self-attention graph pooling. arXiv preprint 1eXiv:1904.08085 2019,
Yin Tat Lee and He Sun. An sdp-based algorithm for linear-sized spectral sparsification. In Pro- ceedings of the 49th annual acm sigact symposium on theory of computing, pp. 678-687, 2017.
Yin Tat Lee and He Sun. Constructing linear-sized spectral sparsification in almost-linear time.
SIAM Journal on Computing, 47(6):23152231 2336, 2018.
Richard Lehoueq, Danny C Sorensen, and Chao Yang. ARPACK users' guide: solution of large- scale eigenvalue problems with implicitly restarted Arnoldi methods, volume 6. Siam, 1998.
11

---

Published as a conference paper at ICLR 2021
Yujia Li, Oriol Vinyals, Chris Dyer, Razvan Pascanu, and Peter Battaglia. Learning deep generative models of graphs. arXiv preprint arXiv:1803.03322 2018a.
Zhuwen Li, Qifeng Chen, and Vladlen Koltun. Combinatorial optimization with graph convolutional networks and guided tree search. In Advances in Neural Information Processing Systems, pp. 539-548, 2018b.
Renjie Liao, Yujia Li, Yang Song. Shenlong Wang, Will Hamilton, David K Duvenaud, Raquel Urtasun, and Richard Zemel. Efficient graph generation with graph recurrent attention networks. In Advances in Neural Information Processing Systems, pp. 4255-4265, 2019.
Oren E Livne and Achi Brandt. Lean algebraic multigrid (lamg): Fast graph laplacian linear solver. SIAM Journal on Scientific Computing, 34(4):B499-B522 2012.
Andreas Loukas. Graph reduction with spectral and cut guarantees. Journal of Machine Learning Research, 20( 16):1-42 2019.
Andreas Loukas and Pierre Vandergheynst. Spectrally approximating large graphs with smaller graphs. arXiv preprint arXiv:1802.07550, 2018.
Tengfei Ma and Jie Chen. Unsupervised learning of graph hierarchical abstractions with differen- tiable coarsening and optimal transport. arXiv preprinl 1rXiv: 2019.
Tengfei Ma, Jie Chen, and Cao Xiao. Constrained generation of semantically valid graphs via regularizing variational autoencoders. In Advances Neural Information Processing Systems, pp. 7113-7124, 2018.
Hermina Petric Maretic, Mireille El Gheche, Giovanni Chierchia, and Pascal Frossard. Got: An op- timal transport framework for graph comparison. Advances in Neural Information Processing Systems, pp. 13876-13887, 2019.
Adam Paszke, Sam Gross, Soumith Chintala, Gregory Chanan, Edward Yang, Zachary DeVito, Zeming Lin, Alban Desmaison, Luca Antiga, and Adam Lerer. Automatic differentiation in pytorch. 2017.
Robert Preis and Ralf Diekmann. Party-a software library for graph partitioning. Advances in Computational Mechanics with Parallel and Distributed Processing, pp. 63-71, 1997.
Dorit Ron, llya Safro, and Achi Brandt. Relaxation-based coarsening and multiscale graph organi- zation. Multiscale Modeling & Simulation, 9():407-4233 2011.
John W Ruge and Klaus Stüben. Algebraic multigrid. In Multigrid methods, pp. 73-130. SIAM, 1987.
Alvaro
Jonathan Godwin, Tobias Pfaff, Rex Ying, Jure Leskovec, and Pe- ter W Battaglia. Learning simulate complex physics with graph networks. arXiv preprint arXiv:2002.09900 2020.
Michael Schlichtkrull, Thomas N Kipf, Peter Bloem, Rianne Van Den Berg, Ivan Titov, and Max Welling. Modeling relational data with graph convolutional networks. In European Semantic Web Conference, pp. 393-607. Springer, 2018.
Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi-Rad. Collective classification network data. Al magazine, 29(3):93-99) 93, 2008
David Shuman, Mohammad Javad Faraji, and Pierre Vandergheynst. A multiscale pyramid trans- form for graph signals. IEEE Transactions on Signal Processing, 64(8):2119-2134 2015.
Martin Simonovsky and Nikos Komodakis. Graphvae: Towards generation of small graphs using variational autoencoders. In International Conference Artificial Neural Networks, pp. 412- 422. Springer, 2018.
Daniel Spielman and Nikhil Srivastava. Graph sparsification by effective resistances. SIAM Journal on Computing, 1066)1111-1126, 2011.
12

---

Published as a conference paper at ICLR 2021
Daniel A Spielman and Shang-Hue Teng. Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems. In Proceedings of the thirty-sixth annual ACM symposium Theory of computing, pp. 81-90, 2004.
Daniel A Spielman and Shang-Huu Teng. Spectral sparsification of graphs. SIAM Journal on Computing, 40(4):981-1025, 2011.
Greg Turk and Mare Levoy. Zippered polygon meshes from range images. In Proceedings of the 21st annual conference on Computer graphics and interactive techniques, pp. 311-318, 1994.
S Vichy N Vishwanathan, Nicol N Schraudolph, Risi Kondor, and Karsten M Borgwardt. Graph kerness. The Journal of Machine Learning Research, 11:1201-1242, 2010.
Chris Walshaw. A multilevel algorithm for force-directed graph drawing. International Sympo- sium on Graph Drawing, pp. 171-182. Springer, 2000.
Tian Xie and Jeffrey C Grossman. Crystal graph convolutional neural networks for an accurate and interpretable prediction of material properties. Physical review letters, 20(14):14530, 2018.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? arXiv preprint arXiv:1810.00822 2018.
Shijie Xu, Jiayan Fang, and Xiang-Yang Li. Weighted laplacian and its theoretical applications. arXiv preprint arXiv:1911.1033 2019.
Zhitao Ying, Jiaxuan You, Christopher Morris, Xiang Ren, Will Hamilton, and Jure Leskovec. Hi- erarchical graph representation learning with differentiable pooling. In Advances in neural infor- mation processing systems, pp. 4800 4800,4410.2000 2018
Jiaxuan You, Bowen Liu, Zhitao Ying. Vijay Pande, and Jure Leskovec. Graph convolutional pol- icy network for goal-directed molecular graph generation. In Advances in neural information processing systems, pp. 6410-642) 2018a.
Jiaxuan You, Rex Ying, Xiang Ren, William I. Hamilton, and Jure Leskovec. Graphrnn: Generating realistic graphs with deep auto-regressive models. arXiv preprint 1rXiv:1802.08773, 2018b.
Hanqing Zeng, Hongkuan Zhou, Ajitesh Srivastava, Rajgopal Kannan, and Viktor Prasanna. Graph- saint: Graph sampling based inductive learning method. arXiv preprint
2019.
Dawei Zhou, Lecheng Zheng, Jiejun Xu, and Jingrui He. Misc-gan: A multi-scale generative model for graphs. Frontiers in Big Data, 2:3, 2019.
A CHOICE OF LAPLACE OPERATOR
A.1 LAPLACE OPERATOR ON WEIGHTED SIMPLICIAL COMPLEX
Its most general form in the discrete case, presented as the operators on weighted simplicial com- plexes, is:
C.TH = W. W B, L = B- W;
where B; is the matrix corresponding to the coboundary operator 5,, and W; is the diagonal ma- trix representing the weights of i-th dimensional simplices. See (Horak & Jost 2013) for details. When restricted to the graph (1 simplicial complex), we recover the most common graph Laplacians as special case of LhPe Note that although the L.P and Edown is not symmetric, we can always symmetrize them by multiple properly chosen diagonal matrix and its inverse from left and right without altering the spectrum.
A.2 MISSING PROOFS
13

---

Published as a conference paper at ICLR 2021
We provide the missing proofs regarding the properties of the projec- tion/lift map and the resulting operators on the coarse graph.
Figure A toy example.
Recall toy example, coarsening algorithm will take graph on the left in figure A.2 and generate a coarse graph on the right,
0
0
1/3
1/3
1/3
0
0
0
0
with coarsening matrix P
p+
0
0
0
1/3
1/3
1/3
1
1
1
1
1/3
1/3
1/3
0
0
0
1/3
1/3
1/3
0
0
0
1/3
1/3
1/3
0
0
0
in general is x block matrix of
0
0
0
1/3
1/3
1/3
0
0
0
1/3
1/3
1/3
0
0
0
1/3
1/3
1/3
rank n. All entries in each block 11, is equal 1
where 7/j = [0)]
Table 7: Depending on the choice of F (quantity that we want to preserve) and Oc. we have different projection/lift operators and resulting Og on the coarse graph.
Quantity F of interest
Oc
Projection P
Lift
G
Invariant under 24
Quadratic form Q
L
p+
Combinatorial Laplace Σ Doubly-weighted Laplace
Qu(U)) Qg
Rayleigh quotient R
L
p+r-1/2 D1
(1( = (
Quadratic form Q C
D1/2
Normalized Laplace E
Qc(U() Q₂(0)
We first make an observation about projection and lift operator, P and U. Lemma A.1. P ol = P II.
Proof. For the first case, it's easy Pou PP = P II.
For the second P u 1-12(pt))pt1-12 1-1/2111-1/3 1.
ooP P Ptr =I
For the third case,
= 2P0
-DV2P(Pt))-111 -11215-112211
MoP D112ppt/0-11/h22pp7> = (D/2(P+))DD-
11/22TDD-1/2 -T.
Now we prove the three lemmas in the main paper. Proposition A.2. For any vector E R", we have that Q2(i) = Ql(Pt&) &). In other words, set
= P & as the lift of &t in N then aT La La.
Proof. Qr. (Ua)
= - (z)
14

---

Published as a conference paper at ICLR 2021
Proposition A.3. For any vector R", we have that RT(2) R (P(PPTT11/55 That is, set the lift of it in RN to be p+ then we have that La
x Lz
xx
Proof. By definition (2
Q.(( RL(x)
(m)
We will prove the lemma by showing
1
(u())) (z) and | ||a:112-
QL (U (2E)²* LU
T /
= --'
L
Qr(3)
= 1P x = || Since both numerator and denominator stay the same under the action U., conclude Ry (U1) (2).
Proposition AA. For any vector I E 12", we have that Q Q2(z) Qc(D)/2p' 2)/22). That is, set the lift of &t in TNN to be = D2/2 p+ n2 then we have that T Li = x²² Lx.
Proof.
Qu = (U2)² Cue
&D -DD-12PP"""D (DLDDD//LDDD2
" -aD-112LD-11 1/2
= =āC Qπ)
B MORE RELATED WORK
Graph pooling. Graph pooling (Lee et al. 2019) proposed in context of the hierarchical graph representation learning. DifiPool (Ying et al. 2018) is proposed to use graph neural networks to parametrize the soft clustering nodes. Its limitation in quadratic memory later improved by Gao & Ji 2019 Cangea al. 2018). All those methods supervised and tested for the graph classification task.
Optimal transportation theory. Several recent works adapt the concepts from optimal transporta- tion theory to compare graphs of different sizes. Garg & Jaakkola (2019) aims to minimize optimal transport distance between probability measures on the original graph and coarse graph. Maretic
et al. (2019) proposes a framework based on Wasserstein distance between graph signal distributions terms of their graph Laplacian matrices, Ma & Chen (219) replaces supervised loss tailored for specific downstream tasks with unsupervised ones based on Wasserstein distance. Dong & Sawin (2200) introduces novel metric by computing coordinated pair of optimal transport maps, which applicable to graph sketching and graph comparison.
C DATASET
C.I SYNTHETIC GRAPHS
Erdös-Rényi graphs (ER). G(n.p) p) where p = 0.1w512
Random geometric graphs (GBO). The random geometric graph model places nodes uniformly at random the unit cube. Two nodes are joined by an edge distance between nodes is at most radius r. We set
5.12
VB
15

---

Published as a conference paper at ICLR 2021
Barabasi-Albert Graph (BA). A graph of nodes is grown by attaching nodes each with m edges that are preferentially attached to existing nodes with high degrees. We set m to be 4.
Watts-SSrogattz Graph (WS). It is first created from ring is joined to its nearest neighbors (or by replacing some edges as follows: for each edge (u, in the underlying "n-ring with is nearest neighbors" with probability replace with a new edge (u, w) with uniformly random choice of existing node w. We k, p to 10 and 0.1.
nodes. Then each node in the ring odd). Then shortcuts are created
neighbors
C.2 DATASET FROM LOUKAS'S PAPER
Yeast. Protein-to-proter interaction network in budding yeast, analyzed by (Jeong et al. 2001 The network has N 1458 vertices and M 1948 edges.
Airfoil. Finite-element graph obtained by airow simulation (Preis & Diekmann 1997 consisting of N 4000 vertices and M 11, 490 edges.
Minnesota (Gleich 2008
Road network with N = 2642 vertices and M = 3304 edges.
Bunny TTrk & Levoy 1994). Point cloud consisting of N 2503 vertices and M 65, 490 edges. The point cloud has been sub-sampled from its original size.
C.3 REAL NETWORKS
Shape graphs (Shape). Each graph KNN graph formed by 1024 points sampled from shapes from ShapeNet where each node is connected 10 nearest neighbors.
Coauthor-CS (CS) and Seauthor-Physice (Physics) co-authorship graphs based on the Microsoft
Academic Graph from the KDD Cup 2016 challenge. Coauthor CS has N = 18, 333 nodes and M 81, 894 edges. Coauthor Physics has N 34, 493 nodes and M 247, 962 edges.
PubMed (Sen et al. 2008) has N = 19, 717 nodes and M = 44, 324 edges. Nodes are documents and edges are citation links.
Flickr Zeng et al. 2019) has N = 89, 250 nodes and M 899, 756 edges. One node in the graph represents one image uploaded Flickr. two images share some common properties (e.g., same geographic location, same gallery, comments by the same user, etc.), there is an edge between the nodes of these two images.
D EXISTING GRAPH COARSENING METHODS
Heavy Edge Matching. At each level of the scheme, the contraction family is obtained by com- puting a maximum-weigh matching with the weight of each contraction set (0,, uy) calculated as wij/ /ij/max/ (d,, d, }. In this manner, heavier edges connecting vertices that well separated from the rest of the graph are contracted first.
Algebraic Distance. This method differs from heavy edge matching in that the weight of each 1/2 where vg is an N-dimensional didate set (v,, 0₁) E E is calculated as (>g-)) (c,, (i) ( ()))²)
test vector computed by successive sweeps of Jacobi relaxation. The complete method is described
by Ron et al. (201T) see also (hen & Safro 2011).
Affinity. This is a vertex proximity heuristic the spirit of the algebraic distance that was proposed by Livne & Brandt (2012) in the context of their work on the lean algebraic multigrid. As per the author suggests, the Q = test vectors are here computed by a single sweep of Gauss-Seidel iteration.
Local Variation. There are two variations of local variation methods, edge-based local variation, and neighborhood-based local variation. They differ in how the contraction set is chosen. Edge- based variation is constructed for each edge, while the neighborhood basedd variant takes every ver- tex and its neighbors contraction set. What two methods have common is that they both optimize an upper bound of the restricted spectral approximation objective. In each step, they greedily pick the sets whose local variation is the smallest. See Loukas (2019) for more details.
16

---

Published as a conference paper at ICLR 2021
Baseline. We also implement simple baseline that randomly chooses collection of nodes in the original graph as landmarks and contract other nodes to the nearest landmarks. If there are multiple nearest landmarks, randomly break the tie. The weight of the coarse graph is set to be the sum of the weights of the crossing edges.
E DETAILS OF THE EXPERIMENTAL SETUP
Feature Initialization. We initialize the the node feature of subgraphs 5 dimensional fea- ture based on a simple heuristics local degree profile (LDP) (Cai & Wang. 2018). For each node GVV), let (N(v) denote the multiset of the degree of all the neighboring nodes of i, i.e., (N( {degree (u, v) E EJ. We take five node features, which are (degree(v), min(DN(v)), max (DN((DD))) (ea()DN((v)) DN())) std(DN()))
other words, each node feature summarizes the degree information of this node and its 1- neighborhood. We use the edge weight dimensional edge feature.
Optimization. All models are trained with Adam optimizer (Kingma & Ba 2014) with learning rate of 0.001 and batch size 600. We use Pytorch (Paszke al. (017)) and Pytorch Geometric (Fey & Lenssen 2019) for all of our implementation. We train graphs one by one where for each graph we train the model minimize the loss for certain epochs (see hyper- syper-pprramttrs for details) before moving to the next graph. We save the model that performs best on the validation graphs and test it on the test graphs.
The building block of our graph neural networks is based on the modification of Graph Isomorphism Network (GIN) that can handle both node and edge features. In particular, first linear transform both node feature and edge feature be vectors of the same dimension. At the k-th layer, GNNs update node representations by
Model Architecture.
h(00 ReLU (MP(())
Σ
l((-11)
WEN(C)U(M
(()))
where (Nv) is a of nodes adjacent to v, and (v; v) represents the self-loop edge. Edge features he (k-1) is the same across the layers.
We use average graph pooling to obtained the graph representation from node embeddings, i.e.,
ha MEAN ({ ( E G)). The final prediction of weight is 1 + ReLu(((ha)) where + is linear layer. We set the number of layers to be and the embedding dimension to be 50.
Time Complexity. In the preprocessing step, need compute the first & eigenvectors of Lapla- cian (either combinatorial or normalized one) of the original graph as test vectors. Those can be efficiently computed by Restarted Lanczos Method (Lehoueq et al. 1998 to find the eigenvalues and eigenvectors.
In the training time, our model needs recompute the term in the loss involving the coarse graph update the weights of the graph neural networks for each batch. For loss involving Laplacian (either combinatorial or normalized Laplacian), the time complexity where [E| is the number of edges in the coarse graph and & is the number of test vectors. For loss involving conductance, computing the conductance of one subset S E still O(EE)) so total the time complexity is also O(E)k) kk). In summary, the time complexity for each batch is linear in the number of edges of training graphs. All experiments are performed on single Intel Xeon CPU ES-2633 v4@ 2.20GHz x 40 and 64GB RAM machine.
compute the xx Lx is ({E)
More concretely, for synthetic graphs, it takes a few minutes to train the model. For real graphs like CS, Physics, PubMed, it takes around hour. For the largest network Flickr of 89k nodes and 899k edges, it takes about 5 hours for most coarsening algorithms and reduction ratios.
Hyperparameters, We list the major hyperparameters of GOREN below.
epoch: 50 for synthetic graphs and 30 for real networks.
17

---

Published as a conference paper at ICLR 2021
walk length: 5000 for real networks. Note the size of the subgraph is usually around 3500 since the random walk visits some nodes more than once.
number of eigenvectors k: 40 for synthetic graphs and 200 for real networks.
embedding dimension: 50
batch size: 600
learning rate: 0.001
F ITERATIVE ALGORITHM FOR SPECTRUM ALIGNMENT
F.1 PROBLEM STATEMENT
Given graph G and its coarse graph & output by existing algorithm A, ideally we would like to set edge weight of G so that spectrum of L (denoted Σw below) has prespecified eigenvalues X, i.,,
Ew = U Diag( A)UT subject to w 2 0, 0,UT==I
We would like to make an important note that in general, given sequence of non decreasing num- bers 0 = Å1 S >2,..., . An and a coarse graph G. is not always possible to set the edge weights (always positive) that the resulting cigenvalues of graph Laplacian of G is {0 X1 Ag. .... An We introduce some notations before we present the theorem. The theorem is developed the context of inverse eigenvalue problem for graphs (Barioli & Fallat (0044] Hogben 2005 Fallat al. 2020), which aims to characterize the all possible sets of eigenvalues that can be realized by symmetric matrices whose sparsity pattern is related the topology of given graph.
For a symmetric real n X matrix M, the graph of M is the graph with vertices {1,..., _) and edges {(i,5) byj * 0 and + j}. Note that the diagonal of M is ignored in determining ((M). Let Sn, be the set of real symmetric n x n matrices. For a graph with n nodes, define S(G) = M E Sn ((MM) -GM))=G]
Theorem F.1. (Barioli & Fallat 2004 Hogben 2005 If 'T is tree, for any M S(T), the diameter Tf is less than the number of distinct eigenvalues of M.
For any graph G, its Laplacian (both combinatorial and normalized Laplacian) belongs to S(G), the above thcorem therefore applies. In other words, given a tree T and given a sequence of non- decreasing numbers 0 A1 < ...,. as long as the number of distinct values in sequences is less than the diameter of T, then this sequence can not be realized as the eigenvalues graph Laplacian of T, matter how we set the edge weights.
Therefore Instead of looking for the a graph with exact spectral alignment with original graph, which is impossible for some nondecreasing sequences illustrated by the theorem [F.1] we relax the equality in equation by instead minimizing the [[S - U Diag( AI We first present an algorithm for the complete graph & of size This algorithm is essentially the special case of Kumar al. 2019 We then show relaxing & from the complete graph the arbitrary graph will not change the convergence result. Before that, we introduce some notations.
F.2 NOTATION
nén 1)
Definition 1. The linear operator L w R. 2
Lw E gaxn defined as
Wetd Lwwse ا [Swla]
i> j i> j i=j
[Dwlis
where dj =-j+ + (2n j)
18

---

Published as a conference paper at ICLR 2021
A toy example is given to illustrate the operators, Consider [wi, W2, w3, whg Wh, w6] T The Laplacian operator on gives
weight vector
Σ 1.2.3 Wi
w1
U2
W3
w1
Σ:
1,45 W2
004
W6
Σw
W2
W1
Σ
2,1,6 Wi
W6
W3
Σ 3,5,6
Adjoint operator - is defined satisfy (Sw, Y) (w, LY
F.3
COMPLETE GRAPH CASE
Recall our goal is to
minimize w.U
Lww U Diag DiaggA)U=
(5)
subject to
w 2 0, U- =1
Algorithm 1: Iterative algorithm for edge weight optimization
Input:
coarse graph G, error tolerance c, iteration limit
Output: coarse graph with new edge weights
Initialize U as random element orthogonal group Onn, R) and t = 0.
while is smaller than the threshold or > T do
Update w(+1 Us++1 according to and Lemma R.4
Compute Error
t=t+1
From w", output coarse graph with new edge weights.
where À is the desired eigenvalues of the smaller graph. One choice of À can be the first eigenval- ues of the original graph of size N. w and U are variables size n 1)/2 and n x n.
The algorithm proceeds by iteratively updating U and while fixing the other one.
Update for w: It can be seen when is fixed, minimizing w is equivalent to a non-negative quadratic problem
minimize w20
f(w) 1_ |Sw 1|
c. w
which is strictly convex where L (U "" It is easy to see that the problem is strictly convex. However, due the the non-negativity constraint for w, there no closed form solution. Thus we derive majorization function via the following lemma.
Lemma F.2. The function (w) is majorized at we by the function
+ Ta 1|w w'll
g(wlw")= = f(w') (w w'
where w' is the update from previous iteration an L, = ||_1| = 2n.
After ignoring the constant terms in 7 the majorized problem of at w is given
minimize
g(wlw") w w Tw. w20
(8)
where a w In (WW')) and VS(w") = -x (Ew') -c
Lemma F.3. From the KKT optimality conditions we can easily obtain the optimal solution to as
w1+1 (w"
V)(w())+
L1
where (x)+ max
19

---

Published as a conference paper at ICLR 2021
Update for U: When is fixed, the problem of optimizing U is equivalent to
minimize U
tr(UT LwU (w)Diag(2))
(9)
subject
UTU=1
It can be shown that the optimal U at iteration t is achieved by U eigenvectors(Lun)
Lemma F.4. From KKT optimality condition, the solution to eigenvectors(ww)
given by U
The following theorem is proved at (Kumar et al. 2019).
Theorem F.5. The sequence (w',U') U²) generated by Algorithm converges to the set of K KT points of
F.4 NON-COMPLETE GRAPH CASE
The only complication in the case of the non-complete graph is that w has only EE| number of free variables instead of m(x-1) variables the case of the complete graph. We will argue that will stay at the subspace of dimension | during the iteration.
For simplicity, given a non-compete graph G = (V, PF), let us denote ē = [n] = (1, 2, n) and and i,j E [n]. easy
each edge will be represented as (i,j) where each edge (i.j) (i > j) to k-thh coordinate w via = ((1.)) = -j + (j (2p--1)
that we can map
2
Let us denote w (to emphasize its dependence on G. it is also denoted we later.) to be the same as w on coordinates that corresponds to edges in G and for the rest entries. In other words,
w[k]
if (K)
A
0
O.W.
Similarly, for any symmetric matrix A of size X
A[i,J] [ Ait
if(i,,) E (1
O.W.
Let us also define G-subspace of (denoted as G-subspace when there is no ambiguity) as (w/w w E IR (R((n21/22). What we need to prove is that if we initialize the algorithm with wa in- stead of w. w will remain in the G-subspace of w for any E E
First, we have the following lemma. Lemma F6. We have
1. Lw Lw.
2. (WI. W2) (WI, W2) = (WI, W2).
3. - = L
Proof. Lemma and 2 can be proved by definition. Now we prove the last lemma. For any w m(n-1)
12
and Y E paxn
(w, LY (Sw, Y)- (Sw, Y) (Sw, Y) (w, LY (w, L-Y)
where the fourth equation follows from the definition of L and the other equations directly follows from the previous lemmas. Therefore y Y
20

---

Published as a conference paper at ICLR 2021
-33
Gr.
23
-1.
-0.5
-1.2
-1.4
15
-1.
250
500
750
1000
1250
10
20
40
500 1003
1530
2000
Figure 3: After optimizing edge weights, we can construct smaller graph with eigenvalues much closer to eigenvalues of original graph. G.e and Ga.e stand for the eigenvalues of original graph and coarse graph output by Variation-Eode -dge algorithm. After-Opt stands for the eigenvalues of graphs where weights are optimized. The eπrоr is measured by the maximum absolute difference over all cigenvalues of original graph and the coarse graph (after optimization).
Recall that we minimize the following objective when updating w
minimize w220
[Swe U Diag(A))U1
which is equivalent to be
minimize wg20
[wa U Diag A)UT
(10)
Now following the same process for the case of complete graph. Equation i0 equivalent to _ F1 ct wa
minimize w2
f(wa)
where c = -* (U Diag(A)UT))
Use the same majorization function the case of complete graph, can get the following update rule
Lemma E7. From the KKT optimality conditions we can easily obtain the optimal solution to as
w 1+1 = =(w's L1 vf(w
where (x)+ = max(x, 0) and Vs(w') (Lw' U Diag(A)UT)
Since V S((w') 1* (Sww)) A) (Sw' - A) (Lw' A) where A = U Diag(A)Ux therefore w 1+1 will remain in the G-subspace if w/ is in the G-subspace. Since w is initial- ized inside G Subspacc,, by induction w' stays in the G-subspace for any z Therefore, we conclude
Theorem F.8. In the case of non-complete graph, the sequence (w², UU) generated by Algorithml / converges to the set of KKT points 5
Remark: since for each iteration full eigendecomposition conducted, the computational com- plexity is O(z²) for each iteration, which is certainly prohibitive for large scale application. Another drawback is that the algorithm is not adaptive to the data so we have to run the same algorithm for graphs from the same generative distribution. The main takeaway of this algorithm is that it is pos- sible to improve the spectral alignment of the original graph and coarse graph by optimizing over edge weights, shown in Figure
21

---

Published as a conference paper at ICLR 2021
Table 8: Relative eigenvalue error (Figenerror) by different coarsening algorithm and the improve- ment (in percentage) after applying GOREN.
Algebraic Distance
Heavy
Local var (edges)
Local var (neigh.)
Dataset
Ratio
Affinity
Edge
0.3
0.262 (82.1%) (6)
0.208 (64.9%)
0.279 (80.3%)
0.102 (6676%)
0.184 (69.6%)
Airfoil
0.5
0.750 (91.7%)
0.672 (88.2%)
0.568 (86.1%)
0.336 (43.2%)
0.364 (73.6%)
0.7
2.422 (96.4%)
2. 136 (93.5%)
1.979 (96.7%)
0.782 (78.8%)
0.876 (87.8%)
0.3
0.322 (-5.0%)
0.206 (0.5%)
0.357 (-4.5%)
0.118 (-5.9%)
0.114 (-14.0%)
Minnesota
0.5
1.345 (49.8%)
1.054 (57.2%)
0.996 (30.1 1%)
0,457 (5.5%)
0.382 (1.6%)
0.7
4,290 (70.4%)
3.787 (76.6%)
3.423 (58.99))
2.073 (55.0%)
1.572 (38.1%)
0.3
0,202 (10.4%)
0. 1080 (5.6%)
0.291 (1.4%)
0.113 (6.2%)
0.024 (-58.3%)
Yeast
0.5
0.795 (49.7%)
0.485 (51.3%)
1.080 (37.4%)
0.398 (27.5 .9%)
0.133 (21.1%)
0.7
2,520 (60.4%)
2.479 (72.4%)
3.482 (52.9%)
2.073 (58.9%)
0.458 (45.95)
0.3
0.046 (32.6%)
0.217 (50.0%)
0.258 (74.4%)
0.007 (-328.5%)
0.082 (74.8%)
Bunny
0.5
0.085 (84.7%)
0.372 (69.1%) (%)
0.420 (61.2%)
0.057 (19.3%)
0.169 (81.65)
0.7
0,182 (84.6%)
0,574 (78.6%)
0.533 (75.4%)
0.094 (45.7%)
0.283 (73.9%)
G MORE RESULTS
We list the full results from Section 4.4 for loss involving normalized Laplacian and conductance.
G.1 DETAILS ABOUT SECTION
We list the full details of Section 4.1
G.2 DETAILS ABOUT SECTION
AND
We list the full details of Section 4.2 and 4.3
G.3 DETAILS ABOUT SECTION 4.4
We list the full details of Section 4.4
G.4 DETAILS ABOUT EIGENERROR
We list the Eigenerror for all datasets when the objective function is Loss( T,, 1)).
H VISUALIZATION
We visualize the subgraphs corresponding randomly sampled edges of coarse graphs. For ample, in WS graphs, some subgraphs have only a few nodes and edges, while other subgraphs have some common patterns such as the dumbbell shape graph. For PubMed, most subgraphs have tree-like structures, possibly due to the edge sparsity in the citation network.
In Figure H we visualize the weight difference between coarsening algorithms with and without learning. We also plot the cigenvalues of coarse graphs, where the first 40 eigenvalues of the original graph are smaller than the coarse ones. After optimizing edge weights via GOREN, we see both methods produce graphs with eigenvalues closer to the eigenvalues of the original graphs.
22

---

Published as a conference paper at ICLR 2021
Table 9: Loss: quadratic loss. Laplacian: combinatorial Laplacian for both original and coarse graphs. Each entry xzy) is: loss w/o learning, and y improvement percentage. BL stands for the baseline.
Algebraic Distance
Heavy
Local var (edges)
Local var (neigh.)
Datasel
Ratio
BL
Affinity
Edge
0.3
0.36 (6.8%)
0.22 (2.9%)
0.56 (1.9%)
0.49 (1.7%)
0.06 (16.6%)
0.17 (73.1%)
BA
0.44 (16.1%)
0.44 (4.4%)
0.68 (4.3%)
0.61 (3.6%)
0.21 (14.1%)
0.18 (72.7%)
0.7
0.21 (32.0%)
0.43 (16.5%)
0.47 (17.7%)
0.4 (19.3%)
0.2 (48.2%)
0.11 (11.1%)
0.3
0.25 (28.7%)
0.08 (24.8%)
0.05 (21.5%%
0.09 (15.6%)
(-254.3%)
0.0 (60.6%))
CS
0.5
0.39 (40.0%)
0.21 (29.8%)
0.17 (26.4%)
0.14 (20.9%)
0,06 (36.9%-)
0.0 (59.0%)
0.7
0.46 (55.5%)
0.57 (36.8%)
0.33 (36.6%)
0.28 (29.3%)
0.18 (44.2%)
0.09 (26.5%)
0.3
0.26 (35.4%)
0.36 (36.6%)
0.2 (29.7%)
0.1 (18.6%)
0.0 (-42.0%)
0.0 (2.5%)
Physics
0.5
0.4 (47.4%)
0.37 (42.456
0.32 (49.7%%
0.14 (28.098)
0.15 (60.3%
0.0 (-0.3%)
0.7
0.47 (60.0%)
0.53 (55.3%)
0.42 (61.4%)
0.27 (34.4%)
0.25 (67 (67.0%)
0.01 (-4.9%)
0.3
0.16 (5.3%)
0.17 (2.0%)
0.08 (4.3%)
0.18 (2.7%)
0.01 (16.0%)
0.02 (33.7%)
Flickr
0.5
0.25 (10.2%)
0,25 (5.0%)
0.19 (6.4%)
0.26 (5.6%)
0.11 1 (1 1.2%))
0.07 (21.8%)
0.7
0.28 (21.0%)
0.31 (12.4%)
0.37 (18.7%)
0.33 (11.3%)
(17.2%)
0.2 (21.4%)
0.3
0.17 (13.6%)
0,06 (6.2%)
0.03 (9.5%)
0.1 (4.7%)
0.01 (18.8%)
0.0 (39.9%)
PubMed
0.5
0.3 (23.4%)
0.13 (10.5%)
0.12 (15.9%)
(10.8%)
0.06 (1188%)
0.01 (36.4%)
0.7
0.31 (41.3%)
0.23 (22.4%)
0.14 (8.3%)
0.14 (-491.6%)
0.16 (12.5%)
0.05 (21.2%)
0.3
0.25 (0.5%)
0.41 (0.2%)
0.2 (0.5%)
0.23 (0.2%5
0.01 (4.8%)
0.01 (5.9%)
ER
0.5
0.36 (1.1%) 1%))
0.52 (0.8%)
0.35 (0.4%)
0.36 (0.2%)
0.18 (1.2%)
0.02 (7.4%)
0.7
0.39 (3.2%)
0.55 (2.5%)
0.44 (2.0%)
0.43 (0.8%)
0.23 (2.9%)
0.29 (10.4%)
0.3
0.44 (86.4%)
0.11 (65.1%)
0.12 (81.5%)
0.34 (80.7%)
0,01 (0.3%)
0.14 (70.4%)
GEO
(87.3%)
(57.8%)
0.24 (31.4%)
0.55 (80.4%)
(59.6%)
0.27 (65.0%)
0.7
0.96 (83.2%)
0.4 (55.2%)
0.33 (54.8%)
0.72 (90.0%)
0.19 (72.4%)
0.41 (61.0%)
0.13 (86.6%)
0.04 (79.8%)
0.03 (69.0%)
0.11 (69.7%)
(1.3%)
0.04 (73.6%)
Shape
0.5
0.23 (91.4%)
0.08 (89.8%)
0.06 (82.2%)
0.17 (88.2%)
0.04 (80.2%)
0.08 (79.4%)
0.7
0.34 (91.1%)
0.17 (94.3%)
0.1 (74.7%)
0.24 (95.9%)
0.09 (64.6%)
0.13 (84.8%)
0.3
0.27 (46.2%)
0.04 (65.6%)
0.04 (-26.9%)
0.43 (32.9%)
0.02 (68.2%)
0.06 (75.2%)
WS
0.5
0.45 (62.9%)
0.09 (82.1%)
0.09 (60.6%)
0.52 (51.8%)
0.09 (69.9%)
0.11 (84.2%)
0.7
0.65 (73.4%)
0.15 (78.4%)
0.14 (66.7%)
0.67 (76.6%)
0.15 (80.8%)
0.16 (83.25)
23

---

Published as a conference paper at ICLR 2021
Table 10: Loss: quadratic loss. Laplacian: normalized Laplacian for both original and coarse graphs. Each entry z(y) is: x losss w/o learning, and y improvement percentage. BL stands for the baseline.
Algebraic Distance
Heavy Edge
Local var (edges)
Local var (neigh.)
Dataset
Ratio
BL
Affinity
0.3
0.06 (68.6%)
0.07 (73.9%)
0.08 (80.6%)
0.08 (79.6%)
0.06 (79.4%)
0.01 (-15.8%)
BA
0.5
0.13 (76.2%)
0.14 (45.0%)
0.15 (5188)
0.15 (46.6%)
0.14 (55.3%)
0.06 (57.2%)
0.7
0.22 (17.0%)
0,23 (5.5%)
0.24 (10.8%)
0.24 (9.7%)
0.23 (5.4%)
0.17 (36.8%)
0.04 (50.2%)
0.03 (44.1%)
0.01 (-7.0%)
0.03 (50.1 1%)
0.0 (-135.00%)
0.01 (-11.7%)
CS
0.5
0.08 (58.0%)
0.06 (37.2%)
0.04 (12.8%)
0.05 (41.5%)
0.02 (16.8%)
0.01 (50.4%)
0.7
0.13 (57.8%)
0.1 (36.3%)
0.09 (21.4%)
0.09 (29.3%)
0.05 (1 (16.%
0.04 (10.8%)
0.3
0.05 (32.3%)
0.04 (5.4%)
0.02 (-16.5%)
0.03 (69.3%)
0-0
0.0 (-59.8%)
Physics
0,07 (47.9%)
0.06 (40.1%)
0.04 (17.4%)
0.04 (61.4%)
0.02 (-23.3%%
0.01 (35.6%)
0.7
0.14 (60.8%)
(52.0%)
0.06 (20.9%)
0.07 (29.9%)
0.04 (11.9%)
0.02 (39.1%)
0.3
0,05 (-29.8%)
0.05 (-31.7%))
0.05 (-21.8%)
0.05 (-66.8%)
0.0 (-293..45)
0.01 (13.4%)
Flickr
0.5
0.08 (-31.9%)
0.06 (-27.6%%
0.06 (-67.2%6)
0.07 (-73.89)
0.02 (-440. 19))
0.02 (-43.9%%
0.7
0.08 (-55.3%)
0.07 (-32.3%)
0.04 (-316.0%)
0.07 (-138.4%)
0.03 (-384.6%)
0.04 (-195.6%)
0.3
0.03 (13.1%)
0.03 (-15.7%)
0.01 (-79.9%)
0.04 (-3.2%)
0.01 (-191.7%)
0.0 (-53.7%)
PubMed
0.5
0.05 (47.8%)
0.05 (35.0%)
0.05 (41.1%)
0.12 (46.8%)
0.03 (-66.4%)
0.01 (-1 18.0%)
0.7
0.09 (58.0%)
0.09 (34.7%)
0.07 (68.7%)
0.07 (21.2%)
0.08 (67.2%)
0.03 (43.1%)
0.06 (84.3%)
0.06 (82.0%)
0.05 (76.8%)
0.06 (80.5%)
0.03 (65.2%)
0.04 (80.8%)
ER
0.5
0.1 (82.2%)
0.1 (83.9%)
0.09 (79.3%)
0.09 (78.8%)
0.06 (64.6%)
0.06 (75.4%)
0.7
0.12 (59.0%)
0.14 (52.3%)
0.12 (55.7%)
0.13 (57.1%)
0.08 (25.1
0.09 (50.3%)
0.3
0.02 (73.1%)
0.01 (-37.1%)
0.01 (-4.9%)
0.02 (64.8%)
0.0 (-204.1%)
0.01 (-22.0%)
GBO
0.5
0.04 (52.8%)
0.01 (12.4%)
0.01 (27.0%)
0.03 (56.3%)
0.01 (-145. 116)
0.02 (-9.7%)
0.7
0.05 (66.5%)
0.02 (39.8%)
0.02 (42.6%)
0.04 (66.0%)
0.01 (-56.2%8
0.02 (0.9%)
0.3
0.01 (82.6%)
0.0 (41.9%)
0.0 (25.6%)
0.01 (87.3%)
0.0 (-73..%%
0.0 (1188)
Shape
0.5
0.02 (84.4%)
0.01 (67.7%)
0.01 (58.4%)
0.02 (87.4%)
0.0 (13.3%)
0.01 (43.8%)
0.7
0.03 (85.2%)
0.01 (78.9%)
0.01 (58.2%)
0.02 (87.9%)
0.01 (43.6%)
0.01 (59.4%)
0.3
0.03 (78.9%)
0.0 (-4.4%)
0.0 (-7.2%)
0.04 (73.7%)
0.0 (-253.3%)
0.01 (60.8%)
WS
0.5
0.05 (83.3%)
0.01 (-1.7%)
0.01 (38.6%)
0.05 (50.3%)
0.01 (40.9%)
0.01 (10.8%)
0.7
0.07 (84.1%)
0.01 (56.45)
0.01 (65.7%)
0.07 (89.5%)
0.01 (62.6%)
0.02 (68.6%)
24

---

Published as a conference paper at ICLR 2021
Table 11: Loss: conductance difference. Each entry =(y) is: loss w/o learning, and improvement percentage. i stands for out of memory error.
Algehraic
Heavy
Local (edges)
Local var (neigh.)
Dataset
Ratio
BL.
Affinity
Distance
Edge
0.3
0.11 (82.3%)
0.08 (78.5%)
0.10 (74,8%)
0.10 (74.3%)
0.09 (79.3%)
0.11 (83.6%)
BA
0.5
0.14 (69.6%)
0.13 (31.5%)
0.14 (37.4%)
0.14 (33.9%)
0.13 (34.3%)
0.13 (56.2%)
0.7
0.22 (48.1%)
0,20 (11.0%)
0.21 (22.4%)
0.21 (20.0%)
0.20 (13.2%)
0.21 (47.8%)
0.3
0.10 (81.0%)
0.09 (74.7%)
0.10 (74.3%)
0.10 (72.5%)
0.09 (76.4%)
0.12 (79.0%)
ER
0.5
0.13 (64.0%)
0.14 (33.8%)
0.14 (33.6%)
0.14 (32.5%)
0.14 (31.9%)
0.12 (1.4%)
0.7
0.20 (43.4%)
0.19 (10.1 16)
0.20 (17.6%)
0.20 (17.2%)
0.19 (23.4%)
0.17 (15.7%)
0.3
0.10 (91.2%)
0.09 (87.0%)
0.10 (84.8%)
0.10 (85.5%)
0.10 (84.6%)
0.11 (92,3%)
GRO
0.5
0.12 (88.1%)
0.13 (33.9%)
0.13 (32.6%)
0.13 (37.6%)
0.13 (35.3%)
0.13 (90.1%)
0.7
0.21 (86.7%)
0.17 (21.9%)
0.19 (25.2%) (%%)
0.19 (27.3%))
0.19 (27.8%)
0.11 (72.4%)
0.3
0.10 (82.3%)
0.10 (86.8%)
0.09 (85.8%)
0.09 (86.3%)
0.09 (84.8%)
0.09 (92.0%)
Shape
0.5
0.14 (33.2%)
0. (34.7%)
0.13 (34.6%)
0.13 (37.7%)
0.13 (40.8%)
0.12 (89.8%)
0.7
0.17 (41.4%))
0.19 (23.4%)
0.20 (27.7%)
0.20 (34.0%)
0.20 (34.3%)
0.11 (76.8%)
0.3
0.10 (86.7%)
0.09 (82.1 (6)
0.10 (84.3%)
0.10 (82.9%)
0.09 (9%)
0.10 (90.5%)
WS
0.5
0.13 (80.8%)
0.13 (31.2%)
0.13 (33.1%)
0.13 (27.7%)
0.13 (34.0%)
0.13 (86.5%)
0.7
0.19 (45.3%)
0.19 (19.35)
0.19 (27.0%)
0.19 (26.6%))
0,20 (27.1%) 1%)
0.11 (12.8%)
0.3
0.11 (75.8%)
0.08 (86.8%)
0.12 (71.4%)
0.11 (62.6%)
0.11 (76.7%)
0.14 (87.9%)
CS
0.5
0.14 (48.3%)
0.12 (16.7%)
0.15 (50.0%)
0.11 (-7.2%)
0.11 (6.7%)
0.09 (9.6%)
0.7
0.26 (40.1%)
0.22 (29.0%)
0.24 (35.0%)
0.24 (41.0%)
0.23 (35.2%)
0.17 (28.8%)
0.3
0.10 (81.7%)
0.07 (79.2%)
0.11 (73.6%)
0.10 (73.7%)
0.11 (79.0%)
0.13 (4.4%)
Physics
0.5
0.13 (20.5%)
0.19 (39.7%)
0.15 (27.8%)
0.16 (31.7%)
0.15 (25.4%)
0.11 (-22.3%)
0.7
0.24 (60.2%)
0.16 (26.1%)
0.23 (15.3%)
0.24 (16.5%)
0.23 (11.2%)
0.20 (35. 9%)
0.3
0.12 (42.8%)
0.10 (0.4%)
0.18 (3.6%)
0.18 (-0.2%)
0.19 (0.9%
0.11 (26.4%)
PubMed
0.5
0.15 (19.7%)
0.19 (1.3%)
0.24 (-12.9%)
0.39 (3.7%)
0.39 (11.8%)
0.16 (16.0%)
0.7
0.25 (27.3%)
0.33 (0.8%)
0.36 (0.0%)
0.31 (33.2%)
0.28 (35.3%)
0.23 (14.1%)
0.3
0.11 (62.6%)
0.13 (52.5%)
0.13 (54.7%)
0.12 (74.2%)
0.16 (58,3%)
Flickr
0.5
0.09 (-34.5%)
0.15 (3.1%)
0.16 (3.4%)
0.15 (19.9%)
0.13 (-6.7%)
0.7
0.19 (35.6%)
0.20 (6.0%)
0.28 (-3.1%)
(5.3%)
0.12 (-25.4%%
25

---

Published as a conference paper at ICLR 2021
Table 12: Loss: Eigenerror. Laplacian: combinatorial Laplacian for original graphs and doubly- weighted Laplacian for coarse graphs. Each entry xxy) is: æ = loss w/o learning, and improve- ment percentage. stands for out of memory error.
Algebraic Distance
Heavy
Local var (edges)
Locul var (neigh.)
Dataset
Ratio
BL
Atfinity
Edge
0.3
(4.1%)
(5.4%)
(5.6%)
0.12 (5.0%)
0.03 (25.4%)
0.1 (-32.2%%
BA
0.5
0.36 (7.1%)
0.17 (8.2%)
0.22 (6.5%)
0.22 (4.7%)
0.11 (21.1
0.17 (-15.9%)
0.7
0.55 (9.2%)
0.32 (12.4%)
0.39 (10.2%)
0.37 (10.9%)
0.21 (33.0%)
0.28 (-29.5%%
0.3
0.46 (16.5%)
0.3 (56.9%)
0.11 (59.15) 1%)
0.23 (38.9%)
0.0 (-347.6%)
0.0 (-191.88%
CS
0.5
1.1 (18.0%)
0.55 (49.8%)
0.33 (60.6%)
0.42 (44.5%)
0.21 (75.2%)
0.0 (-154.2%)
0.7
2,28 (16.9%)
0.82 (57.0%)
0.66 (53.3%)
0,73 (38.9%)
0.49 (73.4%)
0.34 (63.3%)
0.3
0.48 (19.5%)
0.35 (67.2%)
0.14 (65.2%)
0.2 (57.4%)
(-521.6%)
0.0 (20.7%)
Physics
0.5
1.06 (21.7%))
0.58 (67. 1%) (%)
0.33 (69.5%)
0.35 (64.6%)
0.2 (79.0%)
0.0 (-377.996)
0.7
2.11 (19.1%))
0.88 (72.9%)
0.62 (66.7%)
0.62 (64.9%)
0.31 (70.3%)
0.01 (-434.0%)
0.3
0.33 (20.4%)
0.16 (7.8%)
0.16 (9.1%)
0.02 (63.0%)
0.04 (-88.9%)
Flickr
0.5
0.57 (55.7%))
0.33 (20.2%)
0.31 (55.0%)
0.11 (67.6%)
0,07 (60.3%)
0.7
0.86 (85.2%)
0.6 (32.65)
0.57 (38.7%)
0.23 (92.25))
0.21 (40.7%)
0.3
0.56 (5.6%)
0.27 (13.8%)
0.13 (17.4%)
0.34 (10.6%)
0.06 (-0.4%)
0.0 (31.1%)
PubMed
0.5
1,25 (7.1%)
0.5 (15.5%)
0.51 (12.3%)
1.19 (-110.1%)
0.35 (-8.8%)
0.02 (60.4%)
0.7
2.61 (8.9%)
1.12 (19.4%)
2.24 (- (-149.8%)
4.31 (-238.6%)
1.51 (-260.2%)
0.27 (75.8%)
0.3
0.27 (-0.1%%
0.35 (0.4%)
0.15 (0.6%)
0.18 (0.5%)
0.01 (5.7%)
0.01 (-10.4%%
ER
0.5
0.61 (0.5%)
0.7 (1.0%)
0.35 (0.6%)
0.36 (0.2%)
0.19 (1.2%)
0,02 (0.8%)
0.7
1.42 (0.8%)
1.27 (2.1%))
0.7 (1.4%)
0.68 (0.3%)
0.29 (3.5%)
0.33 (10.25))
0.3
0.78 (43.4%%)
0.08 (80.3%)
0.09 (77.1%)
0.27 (82.2%)
0.01 (-524.6%)
0.1 (82.5%)
GEO
0.5
1.72 (50.3%)
0.16 (89.4%)
0.18 (91.2%)
0.45 (84.9%)
0.08 (55.6%)
0.2 (86.8%)
0.7
3.64 (30.4%)
0.33 (86.0%)
0.25 (86.7%)
0.61 (93.0%)
0.15 (88.7%)
0.32 (79.3%)
0.3
0.87 (55.4%%
0.12 (88.6%)
0.07 (56.7%)
0.29 (80.4%)
0.01 (33.1 16)
0.09 (84.5%)
Shape
0.5
2.07 (67.7%)
0.24 (93.3%)
0.17 (90.9%)
0.49 (93.0%)
0.11 (84.2%)
0.2 (90.7%)
0.7
4,93 (69.1%)
0.47 (94.9%)
0.27 (68.5%)
0.71 (95.7%)
0.25 (79.1%)
0.34 (87.4%)
0.3
0.7 (32.3%)
0.05 (84.7%)
0.04 (58.9%)
0.44 (37.3%)
0.02 (75.0%)
0.06 (83.4%)
WS
0.5
1.59 (43.9%)
0.11 (88.2%)
0.11 (83.9%)
0.58 (23.5%)
0.1 (88.2%)
0.12 (79.7%)
0.7
3.52 (45.6%)
0.18 (77.7%)
0.17 (78.2%)
0.79 (82.8%)
0.17 (90.9%)
0.19 (65.8%)
26

---

Published as a conference paper at ICLR 2021
Figure 4: A collection of subgraphs corresponding to edges in coarse graphs (WS and PubMed)
generated by variation neighborhood algorithm. Reduction ratio is 0.7 and 0.9 respectively.
Eigessloot Consarsico
Sgened Compa
1.5
128
515
825-
Figure 5: The first row illustrates the weight difference for local variation neighborhood (left) and heavy edge (right) with 0.5 as the reduction ratio. Blue (red) edges denote edges whose learned weights is smaller (larger) than the default ones. The second row shows the first 40 eigenvalues of the original graph Laplacian, coarse graph w/o learning, and coarse graph w/ learning.
27


Reviews:
[{"review_id": "YQapnG9LlYv", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary of the paper: To solve the problem of graph coarsening, this paper proposes a data-driven framework to: 1) measure the quality of the coarsening algorithm and 2) provide a graph neural network (GNN)-based method to handle the suboptimal problem of edge weight occurring in current methods. The proposed model can handle larger graphs than previous methods. The experimental results demonstrate the effectiveness of the proposed method. \n\nRecommendation: I think contributions of this paper on graph coarsening are new and technically solid. The authors propose a new way (GNN model) to do graph coarsening. Some strong points: (1) The authors provide three new projection operators on graph coarsening. (2) A new framework is proposed to learn better edge weights of the coarse graphs by using a GNN model in an unsupervised manner. (3) Empirical results support their findings (most results are significantly better than baseline methods). Based on these observations, I tend to accept this paper.\n\n\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "V70WqmsgR1p", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper studied the problem of graph coarsening in the context of data-driven deep generative models. The authors studied a family of Laplacian operators and differentiable losses in order to construct high-quality coarse graphs. The paper is well-motivated by providing extensive theoretical analysis to support the rationale of the proposed model. The proposed model is developed based on GAN, which automatically learns a mapping function from the fine-grained graph to the coarse-grained graph. Experimental results show the effectiveness of the proposed model across a bunch of datasets (both synthetic and real ones) and a set of evaluation metrics. \n\nIn general, I believe this paper is well-written, and the results are strong. \nMy only concern comes from the technical contribution of the proposed algorithm. In particular, the authors claimed that \" we are the first to propose and develop a framework to learn coarse graphs with GNN in an unsupervised manner\". However, similar ideas (e.g., Misc-GAN) have already been approached in the network generation setting.  Although, in the graph generation setting, the previous work constructs coarse graphs for the purpose of preserving hierarchical network structures, while in the graph coursing setting, the goal is to alleviate the computational challenges in dealing with massive graphs. But, regarding the framework design, they share some commonalities at a high-level (i.e., GAN-based models for constructing coarse graphs). Please correct me if I am wrong here. \n\nWithout that, I have no question regarding this paper. Moreover, if the author can clear my only concerns above, I would like to higher my score to 7. ", "extra_scores": {}, "extra_text": {}}, {"review_id": "MTinSxrMLpG", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Comment before review: This submission seems to use a different margin. The margins of tables and figures are also tiny which makes the submission hard to read. For example, see Table 1. UPDATE: seems like the authors have corrected the margin issue.\n\nReview:\n\nThis submission proposes a machine learning framework to learn the edge weights of coarsened graphs. The authors propose to use graph neural network (specifically, Graph Isomorphism Network) to embed the nodes being coarsened and use the sub-graph embeddings to compute coarsened graph edges. The proposed method leads to a reduction of the eigen error of the coarsened graphs. As far as I know, the proposed method is novel. \n\nComment on writing: \nI think the current presentation complicates the introduction to the proposed method. The description of the proposed method does not appear until page 5 (aside from the introduction). I recommend the authors to condense the discussion in section 3.1 through section 3.3 and focus more on their own contribution\n\nStrength of the submission:\n- the proposed method is novel\n- the proposed method demonstrates empirical improvement \n\nWeakness of the submission:\n- My main concern with this submission is that it lacks an understanding of the proposed method. This paper points out that learning-based method can further reduce the eigenerror by assigning better weights to the coarsened graph, which I am convinced. However, I am less convinced about the proposed learning process. Is the use of a graph neural network really necessary? Considering the input to the GNN here is just simple degree statistics, I doubt if the network can learn much. The author should consider using linear model or simpler models like MLP to learn the edge weights. Without a comprehensive comparison to these baseline, I would not be convinced.  \n\nTypos:\n- In abstract, \"adaptive to different loss\" -> \"is adaptive / adapts to different loss\"\n\n\nUpdated review:\n\nI thank the author for their new experiments during the discussion period. Given the superior performance of GNN over MLP, I am more convinced that the usage of GNNs in this application is justified. I have updated my review rating from 4 -> 6 to reflect this.\n\nBut just to harass the authors a bit more, I have this curious question:\n- Is the worse performance of MLP due to generalization or expressive power? In other words, can the MLP fit the training data well? Also, when comparing MLP and GOREN, are the authors controlling the number of parameters when comparing MLP and GOREN? As the authors mentioned in their reply, which I agree, \"MLP generally works better than LR due to model capacity\". We want to make sure that MLP and GOREN have similar model capacity but GOREN captures better inductive biases.\n\nI believe this submission finds an interesting application for GNNs. I encourage the authors to bring out the full potential of this idea by having solid, rigorous empirical studies. \n", "extra_scores": {}, "extra_text": {}}, {"review_id": "EUxGJTtMfiT", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper studies a graph coarsening strategy where a new way of assigning weights to a coarse graph is proposed. By focusing on preserving properties of the Laplace operator, appropriate projection/lift operators are presented. Based on the observation that better-informed weights enable us to obtain better Laplace operators for coarse graph, a GNN-based weight adjustment method is proposed. The proposed method called GOREN learns the weight-assignment map $\\mu$ from a collection of input graphs in an unsupervised manner, and can be generalized to test graphs of larger size than the training graphs. Experimental results show that GOREN improves common graph coarsening methods under different evaluation metrics.\n\nOverall, the paper is well-written, and the contributions are concrete. The Laplace operator is considered to be one of the most important operators because it can explain much about the graph structure. When a graph is converted to a coarse graph, preserving the properties of the Laplace operator can be a critical issue. This paper nicely formulates this issue and the theoretical analysis seems to be technically sound (I did not thoroughly check all the details, though). \n\nIn terms of the graph reduction ratio, the values of (0.3, 0.5, 0.7) are chosen in the experiments and the authors simply enumerate the results according to the reduction ratios. I'm wondering if there is a way to find an appropriate reduction ratio by theoretical analysis (e.g., returning an appropriate reduction ratio given a desirable error bound).\n\nI'm wondering how the proposed method scales to many real graphs. It would be helpful to know running times of the proposed method on different sizes of graphs.\n\nIt would be great if the authors can explain how the proposed method can be utilized in downstream tasks. Any specific examples/applications will be helpful to understand the practical value of the proposed method.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper presents a way to use GNNs to learn edge weights of a coarsened graph given the node mapping from the original graph to the coarsened graph.  The paper is well-written and the approach is well-motivated as learning makes it easy to adapt the edge weights to different tasks and objectives, as illustrated in the graph Laplacian and Rayleigh quotient examples.  All the reviewers gage positive reviews for this paper, hence I recommend accepting this paper.

The reason for not promoting this paper further to spotlight or oral is that the paper addressed a relatively small problem, learning the edge weights given the node mapping, and the proposed method is quite simple.  Therefore this paper’s impact could be limited.

One suggestion to the authors is to present more results on downstream tasks, i.e. how does the proposed coarsening algorithm improve downstream task performance, instead of just losses defined without a downstream task in mind.  Example things to consider: does this approach improve graph classification accuracy?  Does this improve downstream GNN model’s efficiency without sacrificing accuracy?
Decision: Accept (Poster)