Graph Sparsiﬁcation by Effective Resistances

By Daniel A. Spielman, Nikhil Srivastava

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 deﬁnes the new edge labeling, enhanced with spectral sparsiﬁcation of edges [37].”
Stochastic gradient descent, weighted sampling, and the randomized Kaczmarz algorithm (2013, neutral): “See [5, 25, 44, 9], and references therein for applications to the column subset selection problem and matrix completion.”
The Johnson-Lindenstrauss Transform Itself Preserves Differential Privacy (2012, neutral): “There’s a rich literature on sparsiﬁers (see [BK96, ST04, SS08]), and the current best known construction [BSS09] gives a (weighted) sparsiﬁer with O ( n/η 2 ) edges with all edge-weights ≤ poly( n ).”
Solving linear programs in the current matrix multiplication time (2018, unknown): “Similar to (2), Lemma 4.2 shows that The previously fastest algorithm involves maintaining the matrix inverse ( A A (cid:62) ) − 1 using sub-space embedding techniques [Sar06, CW13, NN13] and leverage score sampling [SS11].”
An Almost-Linear-Time Algorithm for Approximate Max Flow in Undirected Graphs, and its Multicommodity Generalizations (2013, unknown): “…[ 29 ] to each G i , we obtain weighted graphs and the property that cuts are preserved 7 for all i : Moreover, the spectral sparsiﬁcation of [ 29 ] constructs the weights { w i ( e ) } e ∈ E i such that To complete the description of the algorithm, we output the partition ( F, ¯ F ) of E,…”
Nearly-Linear Time Algorithms for Preconditioning and Solving Symmetric, Diagonally Dominant Linear Systems (2006, unknown): “In particular, Spielman and Srivastava [SS08] construct sparsiﬁers with c 2 = 1, but these constructions require the solution of linear equations in Laplacian matrices, and so can not be used to help speed up the algorithms in this paper.”
Variational Quantum Linear Solver (2019, unknown): “Linear systems of equations play an important role in many areas of science and technology, including machine learning [1, 2], solving partial differential equations [3], fitting polynomial curves [4], and analyzing electrical circuits [5].”
A sparse Johnson: Lindenstrauss transform (2010, unknown): “…applications including nearest-neighbor search [2, 19], compressed sensing [11], data stream computations [5], computational geometry [13], numerical linear algebra [14,17,26,28], machine learning [8,33], graph sparsiﬁcation [30], and more; see the monograph [32] for further applications.”