Gromov-Wasserstein Graph Coarsening

We study the problem of graph coarsening within the Gromov-Wasserstein geometry. Specifically, we propose two algorithms that leverage a novel representation of the distortion induced by merging pairs of nodes. The first method, termed Greedy Pair Coarsening (GPC), iteratively merges pairs of nodes that locally minimize a measure of distortion until the desired size is achieved. The second method, termed $k$-means Greedy Pair Coarsening (KGPC), leverages clustering on pairwise distortion metrics to merge clusters of nodes directly. We provide conditions under which the algorithms are guaranteed to provide an optimal coarsening and validate their performances on six large-scale datasets and a downstream clustering task. Results show that the proposed approaches outperform existing approaches on a wide range of parameters and scenarios.