Gromov-Wasserstein Graph Coarsening

We study graph coarsening in 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, Greedy Pair Coarsening (GPC), iteratively merges pairs of nodes that locally minimize a distortion measure until the desired size is reached. The second method, termed k-means Greedy Pair Coarsening (KGPC), leverages clustering based on pairwise distortion metrics to directly merge node clusters. We provide conditions that guarantee optimal coarsening for our methods and validate their performance across six large-scale datasets and a downstream clustering task. Results show that the proposed methods outperform existing approaches on a wide range of parameters and scenarios.