# Improved large-scale graph learning through ridge spectral sparsification

arXiv: https://arxiv.org/abs/2604.20078 · HTML: https://mlsanity.com/paper/2604.20078/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 11 of its 35 references that are in the map.
- First posted on arXiv 22 Apr 2026.

## Builds on (most cited first, 11 of 11)

- [An Introduction to Matrix Concentration Inequalities](https://mlsanity.com/paper/1501.01571/) (2015)
- [Graph-based Anomaly Detection and Description: A Survey](https://mlsanity.com/paper/1404.4679/) (2014)
- [Turning Big data into tiny data: Constant-size coresets for k-means, PCA and projective clustering](https://mlsanity.com/paper/1807.04518/) (2018)
- [Input Sparsity Time Low-Rank Approximation via Ridge Leverage Score Sampling](https://mlsanity.com/paper/1511.07263/) (2015)
- [Frequent Directions : Simple and Deterministic Matrix Sketching](https://mlsanity.com/paper/1501.01711/) (2015)
- [Approximate Gaussian Elimination for Laplacians: Fast, Sparse, and Simple](https://mlsanity.com/paper/1605.02353/) (2016)
- [Fast Randomized Kernel Methods With Statistical Guarantees](https://mlsanity.com/paper/1411.0306/) (2014)
- [Lectures on Randomized Numerical Linear Algebra](https://mlsanity.com/paper/1712.08880/) (2017)
- [Online Row Sampling](https://mlsanity.com/paper/1604.05448/) (2016)
- [Analysis of Kelner and Levin graph sparsification algorithm for a streaming setting](https://mlsanity.com/paper/1609.03769/) (2016)
- [A Framework for Analyzing Resparsification Algorithms](https://mlsanity.com/paper/1611.06940/) (2016)

## Built on by (most cited first, 2 of 2)

- [Learning Gaussian Graphical Models under Total Positivity via Spectral Graph Sparsification](https://mlsanity.com/paper/2605.17154/) (2026)
- [Spectral Sparsification of Laplacian-Constrained Gaussian and H"usler-Reiss Graphical Models](https://mlsanity.com/paper/2606.16681/) (2026)

## Abstract (arXiv)

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.