Spectrally Approximating Large Graphs with Smaller Graphs

Andreas Loukas, Pierre Vandergheynst
Proceedings of the 35th International Conference on Machine Learning, PMLR 80:3237-3246, 2018.

Abstract

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v80-loukas18a, title = {Spectrally Approximating Large Graphs with Smaller Graphs}, author = {Loukas, Andreas and Vandergheynst, Pierre}, booktitle = {Proceedings of the 35th International Conference on Machine Learning}, pages = {3237--3246}, year = {2018}, editor = {Dy, Jennifer and Krause, Andreas}, volume = {80}, series = {Proceedings of Machine Learning Research}, month = {10--15 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v80/loukas18a/loukas18a.pdf}, url = {https://proceedings.mlr.press/v80/loukas18a.html}, abstract = {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.} }
Endnote
%0 Conference Paper %T Spectrally Approximating Large Graphs with Smaller Graphs %A Andreas Loukas %A Pierre Vandergheynst %B Proceedings of the 35th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2018 %E Jennifer Dy %E Andreas Krause %F pmlr-v80-loukas18a %I PMLR %P 3237--3246 %U https://proceedings.mlr.press/v80/loukas18a.html %V 80 %X 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.
APA
Loukas, A. & Vandergheynst, P.. (2018). Spectrally Approximating Large Graphs with Smaller Graphs. Proceedings of the 35th International Conference on Machine Learning, in Proceedings of Machine Learning Research 80:3237-3246 Available from https://proceedings.mlr.press/v80/loukas18a.html.

Related Material