Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 6: Weak Accept
review_content: This paper proposes an unsupervised hierarchical approach for learning graph representations. The proposed architecture is constructed by unrolling k-steps of a parametrized algebraic multigrid approach for minimizing the Wasserstein metric between the graph and its representation. The node distance (transport cost) used in the Wasserstein metric is also learned as an L2 distance between the embeddings of some graph embedding function. The approach is compared against 6 other state of the art approaches on 5 graph classification tasks, showing significant improvements 4 of them.

The paper is reasonably well written, however, I think some of the explanations can be tightened further. Especially a lot on the background of AMG is not really that relevant, since the authors are not transferring technical results from AMG. Also, it seems like a better flow for presenting this argument might be to switch the order of sections 3.2.1 and 3.1.2. It looks like the main point is  that this architecture is trying to emulate iterative coarsened residual optimization of the Wasserstein metric between a graph and its representation. How the coarsening matrix is derived is more of a technical point (it looks like the results would be much more sensitive to a switch of metric than to a switch of parametrization for S). 

The empirical results are quite intriguing. There are, however, natural and important questions left unanswered. First and foremost, how does the amount of downsampling (compression) compare between methods. How many parameters do different methods require? It would also be good to see what the baseline performance would have been without any input compression as to understand how close these approaches are to the upper bound.

Finally, I think the main issue of this paper, is left unresolved, namely, what is the point of not having supervision from the downstream task. As a user of graph representations trying to solve some problem, the only thing I would want from my representation is to capture some notion of sufficient statistics that are small enough to be efficient and allow me to solve my problem. I would not necessarily care about how well the learned representation resembles the original graph unless I believed that my downstream task was hard to evaluate  and that it was very smooth in the Wasserstein metric. I read the paper multiple times, trying to find any discussion on this, but it seems that the fact that an unsupervised representation is a good thing is taken for granted. A point could at least be made using the same representation for different tasks experimentally. Or, perhaps, literally doing an AMG-type unpacking of the downstream task itself as a comparison. This would shed light on the question of whether the iterated residuals or the choice of distance is what's driving the observed results.
review_title: Official Blind Review #3

final_score: rating: 6: Weak Accept
review_content: 
The paper proposes a differentiable coarsening approach for graph neural network (GNNs).
To this end, it is motivated by algebraic multigrid and optimal transport methods. 

GNNs is indeed an interesting line of research. And introducing coarsening into them, it a highly relevant step. However, there are some major downsides. First, some of the statements are a little but too strong. The paper starts with claiming that GNNs are competitive to graph kernels. But then for instance

Christopher Morris, Martin Ritzert, Matthias Fey, William L. Hamilton, Jan Eric Lenssen, Gaurav Rattan, Martin Grohe:
Weisfeiler and Leman Go Neural: Higher-Order Graph Neural Networks. AAAI 2019: 4602-4609

show that many (if not all) GNNs are equivalently expressive as the Weisefeiler-Lehman (WL) graph kernel. Hence, the competitiveness has to be qualified. Moreover, since you also employ graph convolutional networks for coarsening, you are also in the regime of this paper. Consequently, one should actually compare to WL, at least one should mention this connection. Actually, given that the datasets are not that large, one should run some statistical significance test. Moreover, if you check the paper above, they report much better results for PatchySan on MUTAG, better results on Protein for graph kernels, better results on IMDB-B using a hierarchical GNN approach, based on ideas of higher-order WL. 

Nevertheless, indeed, the present paper shows that a differentiable pooling using WL kind of ideas is competitive to existing pooling approach. This is nice, but in the light of the work above, the novelty is unclear. This has to be clarified before publication. 
review_title: Official Blind Review #1

final_score: rating: 3: Weak Reject
review_content: This paper proposes a method to summarize a given graph based on the algebraic multigrid and optimal transport, which can be further used for the downstream ML tasks such as graph classification.
Although the problem of graph summarization is a relevant task, there are a number of unclear points in this paper listed below:

- In Section 3.1, the coarsening method has been proposed, which is said to be achieved by finding S such that A_C = S^T A S. 
    However, A_C is usually not binary for S \in R^{n x m}, hence how to get the coarse graph G_C from A_C is not clear. Please carefully explain this point.
- In the proposed method, coarse nodes should be selected beforehand. Is there any guideline of how to choose them?
- In Section 3.2, optimal transport is introduced and the distance between G and G_C is measured via entropic optimal transport in Equation (4) or (7).
    However, in Equation (4), a and b should come from the input G and G_C , and it is not clearly explained how to obtain them from the input.
    Moreover, how to use the distance between G and G_C in the proposed coarsening method is also not clear. It seems that it is not used in Algorithm 1.
- I do not understand why the k-step optimal transport distance is needed. Since it converges to the global optimum as k becomes large, it is usually enough to set k to be large enough.
- In experiments, how is the proposed method used for graph classification?
    Since the proposed method is for generating coarse graphs in an unsupervised manner, graph classification cannot be directly performed by itself.
- In addition to the above issue, to assess the effectiveness of the the proposed method, the following experiment is recommended:
    Fix some classifier and compare performance of graph classification for the original graphs and for the coarse graphs.
- In the qualitative study in Section 4.4, while the authors discuss coarse nodes, they are just an input from the user and results are arbitrary. Hence such discussion is not informative.

Minor comments:
- What is "X" in Equation (2)?
- I recommend to write domain for matrices when they used at the first time.

review_title: Official Blind Review #2

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

Decision: Reject