Graph Sparsification Approaches for Laplacian Smoothing


Veeru Sadhanala, Yu-Xiang Wang, Ryan Tibshirani ;
Proceedings of the 19th International Conference on Artificial Intelligence and Statistics, PMLR 51:1250-1259, 2016.


Given a statistical estimation problem where regularization is performed according to the structure of a large, dense graph G, we consider fitting the statistical estimate using a \it sparsified surrogate graph \mathbfG, which shares the vertices of G but has far fewer edges, and is thus more tractable to work with computationally. We examine three types of sparsification: spectral sparsification, which can be seen as the result of sampling edges from the graph with probabilities proportional to their effective resistances, and two simpler sparsifiers, which sample edges uniformly from the graph, either globally or locally. We provide strong theoretical and experimental results, demonstrating that sparsification before estimation can give statistically sensible solutions, with significant computational savings.

Related Material