2019/03/28 by Michael Kapralov, Navid Nouri, Kapralov, Michael +5 · 1 citation
Computer Science · #Caching and Content Delivery #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #Error Correcting Code Techniques #FOS: Computer and information sciences #Optimization and Search Problems
paper · pdf · doi:10.48550/arxiv.1903.12150
openalex publication_date 2019/03/28 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In this paper we consider the problem of computing spectral approximations to\ngraphs in the single pass dynamic streaming model. We provide a linear\nsketching based solution that given a stream of edge insertions and deletions\nto a n-node undirected graph, uses O(n) space, processes each update\nin O(1) time, and with high probability recovers a spectral sparsifier\nin O(n) time. Prior to our work, state of the art results either used\nnear optimal O(n) space complexity, but brute-force \Ω(n2)\nrecovery time [Kapralov et al.'14], or with subquadratic runtime, but\npolynomially suboptimal space complexity [Ahn et al.'14, Kapralov et al.'19].\n Our main technical contribution is a novel method for `bucketing' vertices of\nthe input graph into clusters that allows fast recovery of edges of\nsufficiently large effective resistance. Our algorithm first buckets vertices\nof the graph by performing ball-carving using (an approximation to) its\neffective resistance metric, and then recovers the high effective resistance\nedges from a sketched version of an electrical flow between vertices in a\nbucket, taking nearly linear time in the number of vertices overall. This\nprocess is performed at different geometric scales to recover a sample of edges\nwith probabilities proportional to effective resistances and obtain an actual\nsparsifier of the input graph.\n This work provides both the first efficient \ℓ2-sparse recovery\nalgorithm for graphs and new primitives for manipulating the effective\nresistance embedding of a graph, both of which we hope have further\napplications.\n