On Weighted Graph Sparsification by Linear Sketching
Yu Chen, Sanjeev Khanna, Huan Li · 2022
A seminal work of [Ahn-Guha-McGregor, PODS’12] showed that one can compute a cut sparsifier of an unweighted undirected graph by taking a near-linear number of linear measurements on the graph. Subsequent works also studied computing other graph sparsifiers using linear sketching, and obtained near-linear upper bounds for spectral sparsifiers [Kapralov-Lee-Musco-Musco-Sidford, FOCS’14] and first non-trivial upper bounds for spanners [Filtser-Kapralov-Nouri, SODA’21]. All these linear sketching algorithms, however, only work on unweighted graphs, and are extended to weighted graphs by weight grouping, a non-linear operation not implementable in, for instance, general turnstile streams.In this paper, we initiate the study of weighted graph sparsification by linear sketching by investigating a natural class of linear sketches that we call incidence sketches, in which each measurement is a linear combination of the weights of edges incident on a single vertex. This class captures all aforementioned linear sketches for unweighted sparsification. It also covers linear sketches implementable in the simultaneous communication model, where edges are distributed across n machines. Our results are:1)Weighted cut sparsification: We give an algorithm that computes a $(1+\epsilon)$-cut sparsifier using $\tilde{O}(n\epsilon^{-3})$ linear measurements, which is nearly optimal. This also implies a turnstile streaming algorithm with $\tilde{O}(n\epsilon^{-3})$ space. Our algorithm is achieved by building a so-called “weighted edge sampler” for each vertex.2)Weighted spectral sparsification: We give an algorithm that computes a $(1+\epsilon)$-spectral sparsifier using $\tilde{O}(n^{6/5}\epsilon^{-4})$ linear measurements. This also implies a turnstile streaming algorithm with $\tilde{O}(n^{6/5}\epsilon^{-4})$ space. Key to our algorithm is a novel analysis of how the effective resistances change under vertex sampling. Complementing our algorithm, we then prove a superlinear lower bound of $\Omega(n^{21/20-o(1)})$ measurements for computing some O(1)-spectral sparsifier using incidence sketches.3)Weighted spanner computation: We first show that any $o(n^{2})$ linear measurements can only recover a spanner of stretch that in general depends linearly on $\frac{w_{\max}}{w_{\min}}$. We thus focus on graphs with $\frac{w_{\max}}{w_{\min}}=O(1)$ and study the stretch’s dependence on n. On such graphs, the algorithm in [FiltserKapralov-Nouri, SODA’21] can obtain a spanner of stretch $\tilde{O}\left(n^{\frac{2}{3}\left(1-\alpha\right)}\right)$ using $\tilde{O}(n^{1+\alpha})$ measurements for any $\alpha\in [0,1]$. We prove that, for incidence sketches, this tradeoff is optimal up to an $n^{o(1)}$ factor for all $\alpha\lt 1/10$.We prove both our lower bounds by analyzing the “effective resistances” in certain matrix-weighted graphs, where we develop a number of new tools for reasoning about such graphs – most notably (i) a matrix-weighted analog of the widely used expander decomposition of ordinary graphs, and (ii) a proof that a random vertex-induced subgraph of a matrix-weighted expander is also an expander. We believe these tools are of independent interest.