Spectrally approximating large graphs with smaller graphs.

How does coarsening affect the spectrum of a general graph? We provideconditions such that the principal eigenvalues and eigenspaces of a coarsenedand original graph Laplacian matrices are close. The achieved approximation isshown to depend on standard graph-theoretic properties, such as the degree andeigenvalue distributions, as well as on the ratio between the coarsened andactual graph sizes. Our results carry implications for learning methods thatutilize coarsening. For the particular case of spectral clustering, they implythat coarse eigenvectors can be used to derive good quality assignments evenwithout refinement---this phenomenon was previously observed, but lacked formaljustification.