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

Yifan Chen*, Rentian Yao, Yun Yang, Jie Chen

*Corresponding author for this work

Research output: Chapter in book/report/conference proceedingConference proceedingpeer-review


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.
Original languageEnglish
Title of host publicationProceedings of 40th International Conference on Machine Learning, ICML 2023
EditorsAndreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, Jonathan Scarlett
PublisherML Research Press
Number of pages25
Publication statusPublished - Jul 2023
Event40th International Conference on Machine Learning, ICML 2023 - Honolulu, United States
Duration: 23 Jul 202329 Jul 2023

Publication series

NameProceedings of Machine Learning Research
PublisherML Research Press
ISSN (Print)2640-3498


Conference40th International Conference on Machine Learning, ICML 2023
Country/TerritoryUnited States
Internet address

Scopus Subject Areas

  • Software
  • Artificial Intelligence
  • Control and Systems Engineering
  • Statistics and Probability


Dive into the research topics of 'A Gromov-Wasserstein Geometric View of Spectrum-Preserving Graph Coarsening'. Together they form a unique fingerprint.

Cite this