Graph Sparsification by Effective Resistances

We present a nearly linear time algorithm that produces high-quality spectral sparsifiers of weighted graphs. Given as input a weighted graph $G=(V,E,w)$ and a parameter $\epsilon>0$, we produce a weighted subgraph $H=(V,\tilde{E},\tilde{w})$ of G such that $|\tilde{E}|=O(n\log n/\epsilon^2)$ and all $x\in\mathbb{R}^V$ satisfy $(1-\epsilon)\sum_{uv\in E}\,(x(u)-x(v))^2w_{uv}\leq\sum_{uv\in\tilde{E}}\,(x(u)-x(v))^2\tilde{w}_{uv}\leq(1+\epsilon)\sum_{uv\in E}\,(x(u)-x(v))^2w_{uv}$. This improves upon the spectral sparsifiers constructed by Spielman and Teng, which had $O(n\log^{c}n)$ edges for some large constant c, and upon the cut sparsifiers of Benczúr and Karger, which only satisfied these inequalities for $x\in\{0,1\}^V$. A key ingredient in our algorithm is a subroutine of independent interest: a nearly linear time algorithm that builds a data structure from which we can query the approximate effective resistance between any two vertices in a graph in $O(\log n)$ time.