mlsanityData to 14 Oct 2026

A Gromov--Wasserstein Geometric View of Spectrum-Preserving Graph Coarsening

arXiv 2306.08854 ↗First posted 15 Jun 2023cs.LG cs.AI stat.COcited by 15

Not on the map. Why?

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 .

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

27 of 66 references.

References · 27

  1. 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,361
  2. 2020Open Graph Benchmark: Datasets for Machine Learning on Graphscited by 2,163
  3. 2016Convolutional Neural Networks on Graphs with Fast Localized Spectral Filteringcited by 2,089
  4. 2018Hierarchical Graph Representation Learning with Differentiable Poolingcited by 787
  5. 2020TUDataset: A collection of benchmark datasets for learning with graphscited by 728
  6. 2020Benchmarking Graph Neural Networkscited by 680
  7. 2018Optimal Transport for structured data with application on graphscited by 172
  8. 2021Graph Condensation for Graph Neural Networkscited by 150
  9. 2019Gromov-Wasserstein Learning for Graph Matching and Node Embeddingcited by 126
  10. 2019Scalable Gromov-Wasserstein Learning for Graph Partitioning and Matchingcited by 103
  11. 2014Propagation Kernelscited by 88
  12. 2021Scaling Up Graph Neural Networks Via Graph Coarseningcited by 80
15 more
  1. 2021Understanding Pooling in Graph Neural Networkscited by 69
  2. 2017HARP: Hierarchical Representation Learning for Networkscited by 58
  3. 2018Spectrally approximating large graphs with smaller graphscited by 56
  4. 2021Graph Coarsening with Neural Networkscited by 55
  5. 2018NetLSD: Hearing the Shape of a Graphcited by 52
  6. 2018Graph Coarsening with Preserved Spectral Propertiescited by 41
  7. 2020Generalized Spectral Clustering via Gromov-Wasserstein Learningcited by 38
  8. 2014A Consistent Histogram Estimator for Exchangeable Graph Modelscited by 37
  9. 2020Learning Graphons via Structured Gromov-Wasserstein Barycenterscited by 37
  10. 2019A Unifying Framework for Spectrum-Preserving Graph Sparsification and Coarseningcited by 31
  11. 2021Graph coarsening: From scientific computing to machine learningcited by 21
  12. 2021Semi-relaxed Gromov-Wasserstein divergence with applications on graphscited by 21
  13. 2016Graph Summarization Methods and Applications: A Surveycited by 16
  14. 2019Temporal Graph Kernels for Classifying Dissemination Processescited by 14
  15. 2015Improved initialisation of model-based clustering using Gaussian hierarchical partitionscited by 3

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2023: 1; 2024: 3; 2025: 4; 2026: 7.

15 papers.

Sort:

  1. 2024Distributional Reduction: Unifying Dimensionality Reduction and Clustering with Gromov-Wassersteincited by 12
  2. 2024Graph Coarsening with Message-Passing Guaranteescited by 9
  3. 2024Representing Molecules as Random Walks Over Interpretable Grammarscited by 7
  4. 2026Structure-Centric Graph Foundation Model via Geometric Basescited by 5
  5. 2025Taxonomy of reduction matrices for Graph Coarseningcited by 3
  6. 2025Partition-wise Graph Filtering: A Unified Perspective Through the Lens of Graph Coarseningcited by 2
  7. 2025GBGC: Efficient and Adaptive Graph Coarsening via Granular-ball Computingcited by 2
  8. 2026Rethinking Efficient Graph Coarsening via a Non-Selfishness Principlecited by 1
  9. 2023Interpolating between Clustering and Dimensionality Reduction with Gromov-Wassersteincited by 0
  10. 2025Connecting Domains and Contrasting Samples: A Ladder for Domain Generalizationcited by 0
  11. 2026Efficient and Scalable Granular-ball Graph Coarsening Method for Large-scale Graph Node Classificationcited by 0
  12. 2026Bridging Maximum Likelihood and Optimal Transport for Efficient Inference and Model Selection in Stochastic Block Modelscited by 0
3 more
  1. 2026Diffusion enabled Optimal Transport distances for graph matchingcited by 0
  2. 2026Remedying Coarsening-Based GNN Training under Heterophily via Adaptive Complementary Enhancementcited by 0
  3. 2026Gromov-Wasserstein Quantization and Clustering: Structure, Rates, and Algorithmscited by 0