Graph Coarsening with Preserved Spectral Properties

Yu Jin, Andreas Loukas, Joseph JaJa
Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, PMLR 108:4452-4462, 2020.

Abstract

In graph coarsening, one aims to produce a coarse graph of reduced size while preserving important graph properties. However, as there is no consensus on which specific graph properties should be preserved by coarse graphs, measuring the differences between original and coarse graphs remains a key challenge. This work relies on spectral graph theory to justify a distance function constructed to measure the similarity between original and coarse graphs. We show that the proposed spectral distance captures the structural differences in the graph coarsening process. We also propose graph coarsening algorithms that aim to minimize the spectral distance. Experiments show that the proposed algorithms can outperform previous graph coarsening methods in graph classification and stochastic block recovery tasks.

Cite this Paper

BibTeX
@InProceedings{pmlr-v108-jin20a, title = {Graph Coarsening with Preserved Spectral Properties}, author = {Jin, Yu and Loukas, Andreas and JaJa, Joseph}, booktitle = {Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics}, pages = {4452--4462}, year = {2020}, editor = {Chiappa, Silvia and Calandra, Roberto}, volume = {108}, series = {Proceedings of Machine Learning Research}, month = {26--28 Aug}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v108/jin20a/jin20a.pdf}, url = {https://proceedings.mlr.press/v108/jin20a.html}, abstract = {In graph coarsening, one aims to produce a coarse graph of reduced size while preserving important graph properties. However, as there is no consensus on which specific graph properties should be preserved by coarse graphs, measuring the differences between original and coarse graphs remains a key challenge. This work relies on spectral graph theory to justify a distance function constructed to measure the similarity between original and coarse graphs. We show that the proposed spectral distance captures the structural differences in the graph coarsening process. We also propose graph coarsening algorithms that aim to minimize the spectral distance. Experiments show that the proposed algorithms can outperform previous graph coarsening methods in graph classification and stochastic block recovery tasks. } }
Endnote
%0 Conference Paper %T Graph Coarsening with Preserved Spectral Properties %A Yu Jin %A Andreas Loukas %A Joseph JaJa %B Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2020 %E Silvia Chiappa %E Roberto Calandra %F pmlr-v108-jin20a %I PMLR %P 4452--4462 %U https://proceedings.mlr.press/v108/jin20a.html %V 108 %X In graph coarsening, one aims to produce a coarse graph of reduced size while preserving important graph properties. However, as there is no consensus on which specific graph properties should be preserved by coarse graphs, measuring the differences between original and coarse graphs remains a key challenge. This work relies on spectral graph theory to justify a distance function constructed to measure the similarity between original and coarse graphs. We show that the proposed spectral distance captures the structural differences in the graph coarsening process. We also propose graph coarsening algorithms that aim to minimize the spectral distance. Experiments show that the proposed algorithms can outperform previous graph coarsening methods in graph classification and stochastic block recovery tasks.
APA
Jin, Y., Loukas, A. & JaJa, J.. (2020). Graph Coarsening with Preserved Spectral Properties. Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 108:4452-4462 Available from https://proceedings.mlr.press/v108/jin20a.html.

Related Material