Tutorials
Improved large-scale graph learning through ridge spectral sparsification
arXiv:2604.20078v1 Announce Type: new 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 th
arXiv:2604.20078v1 Announce Type: new 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.
Related
- Machine Learning for Two-Stage Graph Sparsification for the Travelling Salesman Problem
- Accelerating Optimization and Machine Learning through Decentralization
- Optimizing the Network Topology of a Linear Reservoir Computer
- TopFeaRe: Locating Critical State of Adversarial Resilience for Graphs Regarding Topology-Feature Entanglement
Source: arXiv cs.LG | 2026-04-23