Graph Sparsification Approaches for Laplacian Smoothing
Veeru Sadhanala, Yu-Xiang Wang, Ryan Tibshirani
Abstract
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.
BibTeX
@InProceedings{pmlr-v51-sadhanala16,
title = {Graph Sparsification Approaches for Laplacian Smoothing},
author = {Sadhanala, Veeru and Wang, Yu-Xiang and Tibshirani, Ryan},
booktitle = {Proceedings of the 19th International Conference on Artificial Intelligence and Statistics},
pages = {1250--1259},
year = {2016},
editor = {Gretton, Arthur and Robert, Christian C.},
volume = {51},
series = {Proceedings of Machine Learning Research},
address = {Cadiz, Spain},
month = {09--11 May},
publisher = {PMLR},
pdf = {http://proceedings.mlr.press/v51/sadhanala16.pdf},
url = {https://proceedings.mlr.press/v51/sadhanala16.html},
abstract = {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.}
}