A Sketching Algorithm for Spectral Graph Sparsification

الأصل · EN

We study the problem of compressing a weighted graph G on n vertices, building a "sketch" H of G, so that given any vector x ∈ Rⁿ, the value xᵗ LG x can be approximated up to a multiplicative 1+ε factor from only H and x, where LG denotes the Laplacian of G. One solution to this problem is to build a spectral sparsifier H of G, which, using the result of Batson, Spielman, and Srivastava, consists of O(n ε⁻²) reweighted edges of G and has the property that simultaneously for all x ∈ Rⁿ, xᵗ Lₕ x = (1 ± ε) xᵗ LG x. The O(n ε⁻²) bound is optimal for spectral sparsifiers. We show that if one is interested in only preserving the value of xᵗ LG x for a fixed x ∈ Rⁿ (specified at query time) with high probability, then there is a sketch H using only O(n ε⁻¹.⁶) bits of space. This is the first data structure achieving a sub-quadratic dependence on ε. Our work builds upon recent work of Andoni, Krauthgamer, and Woodruff who showed that O(n ε⁻¹) bits of space is possible for preserving a fixed cut query (i.e., x∈ {0,1}ⁿ) with high probability; here we show that even for a general query vector x ∈ Rⁿ, a sub-quadratic dependence on ε is possible. Our result for Laplacians is in sharp contrast to sketches for general n × n positive semidefinite matrices A with O(n) bit entries, for which even to preserve the value of xᵗ A x for a fixed x ∈ Rⁿ (specified at query time) up to a 1+ε factor with constant probability, we show an Ω(n ε⁻²) lower bound.