Space efficient method speeds graph cut approximation in data streams
Near-Optimal Space and Time Cut Sparsification in Turnstile Streams
Data Structures and Algorithms
Summary
Graphs can be very large and hard to store or process entirely, so it's useful to create smaller versions that still keep key features like how cuts divide the graph. The authors improved a method that reads updates about a weighted graph one by one in a stream and builds a smaller graph preserving all cuts approximately. Their approach uses less memory and runs faster than previous ones while maintaining accuracy. This helps when dealing with big, changing graphs like social networks or traffic systems.
What this means in practice
- •For network engineers: Improve real-time monitoring systems by efficiently maintaining approximate network cuts using limited memory and fast updates on streaming link data.
- •For database system developers: Enable fast, memory-efficient approximate graph analytics on large weighted graphs that update dynamically in streaming settings.
Authors
Honghao Lin, Vahab Mirrokni, David P. Woodruff
Abstract
A seminal result of Ahn, Guha, and McGregor (PODS'12) showed that a cut sparsifier of an unweighted graph can be computed from a near-linear number of linear measurements. Later work extended this to spectral sparsifiers (Kapralov et al., FOCS'14) and to near-linear recovery time (Kapralov et al., SODA'20). For weighted graphs, these sketches rely on grouping edges by weight, which general turnstile streams do not allow. Chen, Khanna, and Li (FOCS'22) removed this limitation, using $\tilde{O}(n/\varepsilon^3)$ bits of space. We improve the space to $\tilde{O}(n/\varepsilon^2)$ bits. Our algorithm makes one pass over a general turnstile stream of a weighted graph, processes each update in $\tilde{O}(1)$ time, and recovers, in $\tilde{O}(n/\varepsilon^2)$ time, a reweighted subgraph with $O(n\varepsilon^{-2}\log^2 n)$ edges that preserves every cut within a factor of $1\pm\varepsilon$. Its space, update time, and recovery time are all optimal up to polylogarithmic factors.