Spectral sparsification via random spanners

In this paper we introduce a new notion of distance between nodes in a graph that we refer to as robust connectivity. Robust connectivity between a pair of nodes u and v is parameterized by a threshold κ and intuitively captures the number of paths between u and v of length at most κ. Using this new notion of distances, we show that any black box algorithm for constructing a spanner can be used to construct a spectral sparsifier. We show that given an undirected weighted graph G, simply taking the union of spanners of a few (polylogarithmically many) random subgraphs of G obtained by sampling edges at different probabilities, after appropriate weighting, yields a spectral sparsifier of G. We show how this be done in ˜ O(m) time, producing a sparsifier with ˜ O(n/e²) edges. While the cut sparsifiers of Benczur and Karger are based on weighting edges according to (inverse) strong connectivity, and the spectral sparsifiers are based on resistance, our method weights edges using the robust connectivity measure. The main property that we use is that this new measure is always greater than the resistance when scaled by a factor of O(κ) (κ is chosen to be O(log n)), but, just like resistance and connectivity, has a bounded sum, i.e. ˜ O(n), over all the edges of the graph.