

























Abstract:Graph-based techniques and spectral graph theory have enriched the field of machine learning with a variety of critical advances. A central object in the analysis is the graph Laplacian L, which encodes the structure of the graph. We consider the problem of learning over this Laplacian in a distributed streaming setting, where new edges of the graph are observed in real time by a network of workers. In this setting, it is hard to learn quickly or approximately while keeping a distributed representation of L. To address this challenge, we present a novel algorithm, GSQUEAK, which efficiently sparsifies the Laplacian by maintaining a small subset of effective resistances. We show that our algorithm produces sparsifiers with strong spectral approximation guarantees, all while processing edges in a single pass and in a distributed fashion.
| Comments: | International Conference on Machine Learning (ICML 2018) |
| Subjects: | Machine Learning (cs.LG) |
| Cite as: | arXiv:2604.20078 [cs.LG] |
| (or arXiv:2604.20078v1 [cs.LG] for this version) | |
| https://doi.org/10.48550/arXiv.2604.20078 arXiv-issued DOI via DataCite (pending registration) |
From: Michal Valko [view email]
[v1]
Wed, 22 Apr 2026 00:49:31 UTC (193 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。