Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: 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.

Overall, 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). 

In 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).

I'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.

It 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.
review_title: Nice formulations with reasonable approaches

final_score: rating: 7: Good paper, accept
review_content: 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. 

Recommendation: 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.




review_title: Graph Coarsening with Neural Networks 

final_score: rating: 6: Marginally above acceptance threshold
review_content: 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. 

In general, I believe this paper is well-written, and the results are strong. 
My 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. 

Without 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. 
review_title: Solid paper with theoretical and experimental results. 

final_score: rating: 6: Marginally above acceptance threshold
review_content: 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.

Review:

This 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. 

Comment on writing: 
I 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

Strength of the submission:
- the proposed method is novel
- the proposed method demonstrates empirical improvement 

Weakness of the submission:
- 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.  

Typos:
- In abstract, "adaptive to different loss" -> "is adaptive / adapts to different loss"


Updated review:

I 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.

But just to harass the authors a bit more, I have this curious question:
- 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.

I 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. 

review_title: A ML framework for learning coarsen graph edge weights

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)