Hierarchical abstractions are a methodology for solving large-scale graph problems in various disciplines. Coarsening is one such approach: it generates a pyramid of graphs whereby the one in the next level is a structural summary of the prior one. With a long history in scientific computing, many coarsening strategies were developed based on mathematically driven heuristics. Recently, resurgent interests exist in deep learning to design hierarchical methods learnable through differentiable parameterization. These approaches are paired with downstream tasks for supervised learning. In practice, however, supervised signals (e.g., labels) are scarce and are often laborious and expensive to obtain. In this work, we propose an unsupervised approach, coined OTCOARSENING, with the use of optimal transport. Both the coarsening matrix and the transport cost matrix are parameterized, so that an optimal coarsening strategy can be learned and tailored for a given set of graphs. We demonstrate that the proposed approach produces meaningful coarse graphs and yields competitive performance compared with supervised methods for graph classification and regression.
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.