Graph Coarsening with Preserved Spectral Properties
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.
WOS:000559931301063
2020-01-01
Boston
Proceedings of Machine Learning Research
108
4452
4461
REVIEWED
Event name | Event place | Event date |
ELECTR NETWORK | Aug 26-28, 2020 | |