Reviews: Scalable Gromov-Wasserstein Learning for Graph Partitioning and Matching

The GW distance produces as a byproduct of its computation a transportation coupling, which can be used to infer node-to-node correspondences between graphs. In addition, the optimal transport framework has the appealing property of generalizing to multi-distribution comparisons thorough barycenters, which is exploited in this work to yield joint multi-graph approaches to partitioning and matching. Instead of a the more traditional projected gradient descent approach, the authors rely on a regularized proximal gradient method to compute the GW distance and barycenters. In order to scale up to large graphs, they propose a recursive divide-and-conquer approach. Various experiments on benchmark graph/network partitioning and matching tasks are performed, showing that the proposed method compares favorably (both in terms of accuracy and runtime) to various popular baselines. Strengths: - Strong theoretical foundations (the Gromov-Wasserstein distance) to a task often approach with heuristic methods - Superbly written paper: clear and concise argumentation, easy to follow, and a pleasure to read - The thorough experimental results, which show that the proposed approach is effective and efficient in practice - Rigorous and comprehensive review of computational complexities of the proposed alternative methods Weaknesses: - Limited novelty of methods / theory Major Comments/Questions: 1. Novelty/Contributions. While GW has been used for graph matching repeatedly in previous work (albeit for small tasks - see below), I am not aware of other work that uses it for graph partitioning, so I would consider this an important contribution of this paper. It should be noted that most of the individual components used in this work are not novel (the GW itself, its application to graph matching, the proximal gradient method). However, I see consider its main contribution combining those components in a coherent and practical way, and producing as a consequence a promising and well-founded approach to two important tasks.