Graph Reduction with Spectral and Cut Guarantees

Can one reduce the size of a graph without significantly altering its basic properties? The graph reduction problem is hereby approached from the perspective of restricted spectral approximation, a modification of the spectral similarity measure used for graph sparsification. This choice is motivated by the observation that restricted approximation carries strong spectral and cut guarantees, and that it implies approximation results for unsupervised learning problems relying on spectral embeddings. The article then focuses on coarsening - the most common type of graph reduction. Sufficient conditions are derived for a small graph to approximate a larger one in the sense of restricted approximation. These findings give rise to algorithms that, compared to both standard and advanced graph reduction methods, find coarse graphs of improved quality, often by a large margin, without sacrificing speed.


Publié dans:
Journal of Machine Learning Research, 20, 116, 1-42
Année
2019
Publisher:
Brookline, MICROTOME PUBL
Mots-clefs:
Note:
All published papers are freely available online.
Lien supplémentaire:
Laboratoires:




 Notice créée le 2019-08-26, modifiée le 2020-04-20


Évaluer ce document:

Rate this document:
1
2
3
 
(Pas encore évalué)