A Gromov--Wasserstein Geometric View of Spectrum-Preserving Graph
  Coarsening
Yifan Chen Rentian Yao Yun Yang Jie Chen
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 .