  Large-scale graphs are widely used to represent object relationships in many
real world applications. The occurrence of large-scale graphs presents
significant computational challenges to process, analyze, and extract
information. Graph coarsening techniques are commonly used to reduce the
computational load while attempting to maintain the basic structural properties
of the original graph. As there is no consensus on the specific graph
properties preserved by coarse graphs, how to measure the differences between
original and coarse graphs remains a key challenge. In this work, we introduce
a new perspective regarding the graph coarsening based on concepts from
spectral graph theory. We propose and justify new distance functions that
characterize the differences between original and coarse graphs. We show that
the proposed spectral distance naturally captures the structural differences in
the graph coarsening process. In addition, we provide efficient graph
coarsening algorithms to generate graphs which provably preserve the spectral
properties from original graphs. Experiments show that our proposed algorithms
consistently achieve better results compared to previous graph coarsening
methods on graph classification and block recovery tasks.
