# A Gromov--Wasserstein Geometric View of Spectrum-Preserving Graph Coarsening arXiv: https://arxiv.org/abs/2306.08854 ยท HTML: https://mlsanity.com/paper/2306.08854/ ## Key facts - Cited by 15 papers in the map (data through 14 Oct 2026). - Builds on 27 of its 66 references that are in the map. - First posted on arXiv 15 Jun 2023. ## Builds on (most cited first, 27 of 27) - [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016) - [Open Graph Benchmark: Datasets for Machine Learning on Graphs](https://mlsanity.com/paper/2005.00687/) (2020) - [Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering](https://mlsanity.com/paper/1606.09375/) (2016) - [Hierarchical Graph Representation Learning with Differentiable Pooling](https://mlsanity.com/paper/1806.08804/) (2018) - [TUDataset: A collection of benchmark datasets for learning with graphs](https://mlsanity.com/paper/2007.08663/) (2020) - [Benchmarking Graph Neural Networks](https://mlsanity.com/paper/2003.00982/) (2020) - [Optimal Transport for structured data with application on graphs](https://mlsanity.com/paper/1805.09114/) (2018) - [Graph Condensation for Graph Neural Networks](https://mlsanity.com/paper/2110.07580/) (2021) - [Gromov-Wasserstein Learning for Graph Matching and Node Embedding](https://mlsanity.com/paper/1901.06003/) (2019) - [Scalable Gromov-Wasserstein Learning for Graph Partitioning and Matching](https://mlsanity.com/paper/1905.07645/) (2019) - [Propagation Kernels](https://mlsanity.com/paper/1410.3314/) (2014) - [Scaling Up Graph Neural Networks Via Graph Coarsening](https://mlsanity.com/paper/2106.05150/) (2021) - [Understanding Pooling in Graph Neural Networks](https://mlsanity.com/paper/2110.05292/) (2021) - [HARP: Hierarchical Representation Learning for Networks](https://mlsanity.com/paper/1706.07845/) (2017) - [Spectrally approximating large graphs with smaller graphs](https://mlsanity.com/paper/1802.07510/) (2018) - [Graph Coarsening with Neural Networks](https://mlsanity.com/paper/2102.01350/) (2021) - [NetLSD: Hearing the Shape of a Graph](https://mlsanity.com/paper/1805.10712/) (2018) - [Graph Coarsening with Preserved Spectral Properties](https://mlsanity.com/paper/1802.04447/) (2018) - [Generalized Spectral Clustering via Gromov-Wasserstein Learning](https://mlsanity.com/paper/2006.04163/) (2020) - [A Consistent Histogram Estimator for Exchangeable Graph Models](https://mlsanity.com/paper/1402.1888/) (2014) - [Learning Graphons via Structured Gromov-Wasserstein Barycenters](https://mlsanity.com/paper/2012.05644/) (2020) - [A Unifying Framework for Spectrum-Preserving Graph Sparsification and Coarsening](https://mlsanity.com/paper/1902.09702/) (2019) - [Graph coarsening: From scientific computing to machine learning](https://mlsanity.com/paper/2106.11863/) (2021) - [Semi-relaxed Gromov-Wasserstein divergence with applications on graphs](https://mlsanity.com/paper/2110.02753/) (2021) - [Graph Summarization Methods and Applications: A Survey](https://mlsanity.com/paper/1612.04883/) (2016) - [Temporal Graph Kernels for Classifying Dissemination Processes](https://mlsanity.com/paper/1911.05496/) (2019) - [Improved initialisation of model-based clustering using Gaussian hierarchical partitions](https://mlsanity.com/paper/1507.07114/) (2015) ## Built on by (most cited first, 15 of 15) - [Distributional Reduction: Unifying Dimensionality Reduction and Clustering with Gromov-Wasserstein](https://mlsanity.com/paper/2402.02239/) (2024) - [Graph Coarsening with Message-Passing Guarantees](https://mlsanity.com/paper/2405.18127/) (2024) - [Representing Molecules as Random Walks Over Interpretable Grammars](https://mlsanity.com/paper/2403.08147/) (2024) - [Structure-Centric Graph Foundation Model via Geometric Bases](https://mlsanity.com/paper/2605.08689/) (2026) - [Taxonomy of reduction matrices for Graph Coarsening](https://mlsanity.com/paper/2506.11743/) (2025) - [Partition-wise Graph Filtering: A Unified Perspective Through the Lens of Graph Coarsening](https://mlsanity.com/paper/2505.14033/) (2025) - [GBGC: Efficient and Adaptive Graph Coarsening via Granular-ball Computing](https://mlsanity.com/paper/2506.19224/) (2025) - [Rethinking Efficient Graph Coarsening via a Non-Selfishness Principle](https://mlsanity.com/paper/2605.13021/) (2026) - [Interpolating between Clustering and Dimensionality Reduction with Gromov-Wasserstein](https://mlsanity.com/paper/2310.03398/) (2023) - [Connecting Domains and Contrasting Samples: A Ladder for Domain Generalization](https://mlsanity.com/paper/2510.16704/) (2025) - [Efficient and Scalable Granular-ball Graph Coarsening Method for Large-scale Graph Node Classification](https://mlsanity.com/paper/2603.29148/) (2026) - [Bridging Maximum Likelihood and Optimal Transport for Efficient Inference and Model Selection in Stochastic Block Models](https://mlsanity.com/paper/2605.28488/) (2026) - [Diffusion enabled Optimal Transport distances for graph matching](https://mlsanity.com/paper/2607.06646/) (2026) - [Remedying Coarsening-Based GNN Training under Heterophily via Adaptive Complementary Enhancement](https://mlsanity.com/paper/2607.21885/) (2026) - [Gromov-Wasserstein Quantization and Clustering: Structure, Rates, and Algorithms](https://mlsanity.com/paper/2608.11016/) (2026) ## Abstract (arXiv) Graph coarsening is a technique for solving large-scale graph problems by working on a smaller version of the original graph, and possibly interpolating the results back to the original graph. It has a long history in scientific computing and has recently gained popularity in machine learning, particularly in methods that preserve the graph spectrum. This work studies graph coarsening from a different perspective, developing a theory for preserving graph distances and proposing a method to achieve this. The geometric approach is useful when working with a collection of graphs, such as in graph classification and regression. In this study, we consider a graph as an element on a metric space equipped with the Gromov--Wasserstein (GW) distance, and bound the difference between the distance of two graphs and their coarsened versions. Minimizing this difference can be done using the popular weighted kernel K-means method, which improves existing spectrum-preserving methods with the proper choice of the kernel. The study includes a set of experiments to support the theory and method, including approximating the GW distance, preserving the graph spectrum, classifying graphs using spectral information, and performing regression using graph convolutional networks. Code is available at https://github.com/ychen-stat-ml/GW-Graph-Coarsening .