# Graph Sparsification by Approximate Matrix Multiplication

Preprint · Neophytos Charalambides, Alfred O. Hero

- Archive id: arxiv:2304.08581
- Published: 2023-04-17
- arXiv: https://arxiv.org/abs/2304.08581
- Source URL: https://arxiv.org/abs/2304.08581
- PDF: https://arxiv.org/pdf/2304.08581
- Provenance: arxiv

## Abstract

Graphs arising in statistical problems, signal processing, large networks, combinatorial optimization, and data analysis are often dense, which causes both computational and storage bottlenecks. One way of \\textit{sparsifying} a \\textit{weighted} graph, while sharing the same vertices as the original graph but reducing the number of edges, is through \\textit{spectral sparsification}. We study this problem through the perspective of RandNLA. Specifically, we utilize randomized matrix multiplication to give a clean and simple analysis of how sampling according to edge weights gives a spectral approximation to graph Laplacians. Through the $CR$-MM algorithm, we attain a simple and computationally efficient sparsifier whose resulting Laplacian estimate is unbiased and of minimum variance. Furthermore, we define a new notion of \\textit{additive spectral sparsifiers}, which has not been considered in the literature.

_Abstract reproduced under CC0-1.0 (arXiv descriptive metadata)._

---
Space Kitty Archive · https://space-kitty.com · API: https://space-kitty.com/api/v1 · MCP: https://space-kitty.com/mcp · Premium: $0.20/request via x402 (Base Sepolia (testnet)). Metadata: arXiv (CC0), OpenAlex (CC0), Europe PMC (CC BY/CC0 works), ClinicalTrials.gov.