TY - GEN

T1 - Improved large-scale graph learning through ridge spectral sparsification

AU - Calandriello, Daniele

AU - Koutis, Ioannis

AU - Lazaric, Alessandro

AU - Valko, Michal

PY - 2018/1/1

Y1 - 2018/1/1

N2 - The representation and learning benefits of methods based on graph Laplacians, such as Laplacian smoothing or harmonic function solution for semi-supervised learning (SSL), are empirically and theoretically well supported. Nonetheless, the exact versions of these methods scale poorly with the number of nodes n of the graph. In this paper, we combine a spectral sparsification routine with Laplacian learning. Given a graph G as input, our algorithm computes a sparsi- fier in a distributed way in O(n log3 (n)) time, O(m log3 (n)) work and O(n log(n)) memory, using only log(n) rounds of communication. Furthermore, motivated by the regularization often employed in learning algorithms, we show that constructing sparsifiers that preserve the spectrum of the Laplacian only up to the regularization level may drastically reduce the size of the final graph. By constructing a spectrally-similar graph, we are able to bound the error induced by the sparsification for a variety of downstream tasks (e.g., SSL). We empirically validate the theoretical guarantees on Amazon co-purchase graph and compare to the state-of-the-art heuristics.

AB - The representation and learning benefits of methods based on graph Laplacians, such as Laplacian smoothing or harmonic function solution for semi-supervised learning (SSL), are empirically and theoretically well supported. Nonetheless, the exact versions of these methods scale poorly with the number of nodes n of the graph. In this paper, we combine a spectral sparsification routine with Laplacian learning. Given a graph G as input, our algorithm computes a sparsi- fier in a distributed way in O(n log3 (n)) time, O(m log3 (n)) work and O(n log(n)) memory, using only log(n) rounds of communication. Furthermore, motivated by the regularization often employed in learning algorithms, we show that constructing sparsifiers that preserve the spectrum of the Laplacian only up to the regularization level may drastically reduce the size of the final graph. By constructing a spectrally-similar graph, we are able to bound the error induced by the sparsification for a variety of downstream tasks (e.g., SSL). We empirically validate the theoretical guarantees on Amazon co-purchase graph and compare to the state-of-the-art heuristics.

UR - http://www.scopus.com/inward/record.url?scp=85057285175&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85057285175&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:85057285175

T3 - 35th International Conference on Machine Learning, ICML 2018

SP - 1081

EP - 1090

BT - 35th International Conference on Machine Learning, ICML 2018

A2 - Dy, Jennifer

A2 - Krause, Andreas

PB - International Machine Learning Society (IMLS)

T2 - 35th International Conference on Machine Learning, ICML 2018

Y2 - 10 July 2018 through 15 July 2018

ER -