Improved large-scale graph learning through ridge spectral sparsification

Daniele Calandriello 1, 2 Ioannis Koutis 3 Alessandro Lazaric 4 Michal Valko 1
1 SEQUEL - Sequential Learning
Inria Lille - Nord Europe, CRIStAL - Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - UMR 9189
Abstract : The representation and learning benefits of methods based on graph Laplacians, such as Lapla-cian 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 sparsifica-tion routine with Laplacian learning. Given a graph G as input, our algorithm computes a sparsi-fier in a distributed way in O(n log 3 (n)) time, O(m log 3 (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 sparsifica-tion 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.
Document type :
Conference papers
Complete list of metadatas

Cited literature [1 references]  Display  Hide  Download

https://hal.inria.fr/hal-01810980
Contributor : Michal Valko <>
Submitted on : Friday, June 8, 2018 - 1:42:07 PM
Last modification on : Friday, March 22, 2019 - 1:36:34 AM
Long-term archiving on : Sunday, September 9, 2018 - 5:06:22 PM

File

calandriello2018improved.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-01810980, version 1

Citation

Daniele Calandriello, Ioannis Koutis, Alessandro Lazaric, Michal Valko. Improved large-scale graph learning through ridge spectral sparsification. International Conference on Machine Learning, ICML 2018 - Thirty-fifth International Conference on Machine Learning, Jul 2018, Stockholm, Sweden. ⟨hal-01810980⟩

Share

Metrics

Record views

399

Files downloads

227