Graph sparsification by effective resistances

By Daniel A. Spielman, Nikhil Srivastava. 2008

1,061 citations recorded by the source corpus.

We present a nearly-linear time algorithm that produces high-quality sparsifiers of weighted graphs. Given as input a weighted graph G=(V,E,w) and a parameter ε>0, we produce a weighted subgraph H=(V,~E,~w) of G such that |~E|=O(n log n/ε2) and for all vectors x in RV. (1-ε) ∑uv ∈ E (x(u)-x(v))2wuv≤ ∑uv in ~E(x(u)-x(v))2~wuv ≤ (1+ε)∑uv ∈ E(x(u)-x(v))2wuv. This improves upon the sparsifiers constructed by Spielman and Teng, which had O(n logc n) edges for some large constant c, and upon those of Benczur and Karger, which only satisfied (1) for x in {0,1}V. We conjecture the existence of sparsifiers with O(n) edges, noting that these would generalize the notion of expander graphs, which are constant-degree sparsifiers for the complete graph. 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.

Subfields: Computational Theory and Mathematics, Computer Networks and Communications

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Theory and Mathematics

In Computer Networks and Communications

Citations in the corpus

Dynamic Edge-Conditioned Filters in Convolutional Neural Networks on Graphs (2017, neutral): “This is followed by Kron reduction [13], which also defines the new edge labeling, enhanced with spectral sparsification of edges [36].”
Stochastic gradient descent, weighted sampling, and the randomized Kaczmarz algorithm (2013, methodology): “See [5,9,25,44], and references therein for applications to the column subset selection problem and matrix completion.”
An Almost-Linear-Time Algorithm for Approximate Max Flow in Undirected Graphs, and its Multicommodity Generalizations (2013, background): “Moreover, the spectral sparsification of [29] constructs the weights {w′ i(e)}e∈E′ i such that”
Per-instance Differential Privacy and the Adaptivity of Posterior Sampling in Linear and Ridge regression (2017, methodology): “Leverage score measures the importance/uniqueness of a data point relative to the rest of the data set and it is used extensively in regression analysis [4] (for outlier detection and experiment design), compressed sensing (for adaptive sampling) [24] and numerical linear algebra (for fast matrix co”
Randomized numerical linear algebra: Foundations and algorithms (2020, methodology): “The idea of sparsifying a graph by randomly sampling edges in proportion to the effective resistances was developed by Spielman and Srivastava (2011); the analysis above is drawn from Tropp (2019).”
Matrix Scaling and Balancing via Box Constrained Newton's Method and Interior Point Methods (2017, methodology): “The resulting algorithm for implementing the k-oracle would take time Õ(m+n), by taking advantage of spectral sparsification algorithms [49], [50], [51].”
Discrete Signal Processing on Graphs: Sampling Theory (2015, background): “Instead of focusing on preserving connectivity properties as in prior work [37], we emphasize the interplay between signals and structures.”
An Almost-Linear-Time Algorithm for Approximate Max Flow in Undirected Graphs , and its Multicommodity Generalizations (2013, neutral): “…inequalities we have ρ(A) = max x∈R E U −1 WBL † B T U x ∞ x ∞ ≤ max x∈R E UBL † B T U x 2 1 √ |E| x 2 = |E| · UBL † B T U 2 The result follows from the fact in [29] that Π def = UBL † B T U is an orthogonal projection, and therefore Π 2 ≤ 1 and the fact in [31] [12] [14] [11] that T L † = O(|E|).”
On the Embeddability of Random Walk Distances (2013, methodology): “Since network effective resistance is analogous to commute time, [40] uses graph sparsification to compute effective resistances between any pair of nodes in O(log n) time.”
Random Projections, Graph Sparsification, and Differential Privacy (2013, methodology): “Before we move to arbitrary graphs, we give an alternative for the local sparsification technique of Spielman and Teng [31].”
Per-instance Differential Privacy (2017, methodology): “…of the data set and it is used extensively in regression analysis (Chatterjee & Hadi, 1986) (for outlier detection and experiment design), graph sparsification (for adaptive sampling) (Spielman & Srivastava, 2011) and numerical linear algebra (for fast matrix computation)(Drineas et al., 2012).”
Sums of random Hermitian matrices and an inequality by Rudelson (2010, background): “This important result has been applied to several different problems, such as bringing a convex body to near-isotropic position [11]; the analysis of for low-rank approximations of matrices [12, 6] and graph sparsification [13]; estimating of singular values of matrices with independent rows [10]; a”