Spectrally approximating large graphs with smaller graphs
This work addresses a theoretical gap for researchers and practitioners in graph learning and spectral methods, offering incremental insights into coarsening effects.
The paper tackles the problem of understanding how graph coarsening affects spectral properties, establishing conditions under which the principal eigenvalues and eigenspaces of coarsened and original graph Laplacians are close, with the approximation depending on graph-theoretic properties like degree and eigenvalue distributions. It shows that for spectral clustering, coarse eigenvectors can yield good assignments without refinement, providing formal justification for a previously observed phenomenon.
How does coarsening affect the spectrum of a general graph? We provide conditions such that the principal eigenvalues and eigenspaces of a coarsened and original graph Laplacian matrices are close. The achieved approximation is shown to depend on standard graph-theoretic properties, such as the degree and eigenvalue distributions, as well as on the ratio between the coarsened and actual graph sizes. Our results carry implications for learning methods that utilize coarsening. For the particular case of spectral clustering, they imply that coarse eigenvectors can be used to derive good quality assignments even without refinement---this phenomenon was previously observed, but lacked formal justification.