Spectral Sparsification of Graphs

By Daniel A. Spielman, Shang-Hua Teng. 2008

592 citations recorded by the source corpus.

We introduce a new notion of graph sparsification based on spectral similarity of graph Laplacians: spectral sparsification requires that the Laplacian quadratic form of the sparsifier approximate that of the original. This is equivalent to saying that the Laplacian of the sparsifier is a good preconditioner for the Laplacian of the original. We prove that every graph has a spectral sparsifier of nearly linear size. Moreover, we present an algorithm that produces spectral sparsifiers in time $O(m\log^{c}m)$, where $m$ is the number of edges in the original graph and $c$ is some absolute constant. This construction is a key component of a nearly linear time algorithm for solving linear equations in diagonally dominant matrices. Our sparsification algorithm makes use of a nearly linear time algorithm for graph partitioning that satisfies a strong guarantee: if the partition it outputs is very unbalanced, then the larger part is contained in a subgraph of high conductance.

Subfields: Computational Theory and Mathematics, Geometry and Topology, Graph Learning

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 Geometry and Topology

In Graph Learning

Citations in the corpus

Big Bird: Transformers for Longer Sequences (2020, background): “It is well-known that random graphs are expanders and can approximate complete graphs in a number of different contexts including in their spectral properties [81, 39].”
Random Projections, Graph Sparsification, and Differential Privacy (2013, methodology): “[32, 33] Let G = (V,E) be an arbitrary graph.”
Twice-ramanujan sparsifiers (2008, methodology): “We consider the spectral notion of similarity introduced by Spielman and Teng [16, 18]: we say that H is a κ-approximation of G if for all x ∈ R , x LGx ≤ x LHx ≤ κ · x LGx, (1) where LG and LH are the Laplacian matrices of G and H.”
Graph stream algorithms: a survey (2014, background): “Spielman and Teng [59] introduced the more general notion of spectral sparsi.cation based on approximating the Laplacian of a graph.”
Nearly-Linear Time Algorithms for Preconditioning and Solving Symmetric, Diagonally Dominant Linear Systems (2006, methodology): “Our construction of ultra-sparsifiers in section 11 builds upon the simpler construction but requires the use of spectral sparsifiers [54].”
Sketching as a Tool for Numerical Linear Algebra (2014, methodology): “One can use algorithms for approximating the leverage scores of general matrices [44], though more efficient algorithms, whose overall running time is near-linear in the number of edges of G, are known [111, 110].”
Graph sparsification by effective resistances (2008, methodology): “The tools we use to do this are Spielman and Teng’s nearly-linear time solver [23, 24] and the Johnson-Lindenstrauss Lemma [17, 1].”
A Survey on Vision Transformer (2020, background): “Inspired graph theories [113, 25], various sparse graph are combined together to approximate the dense graph in the transformer model, which also achieve O(N) complexity.”
An Almost-Linear-Time Algorithm for Approximate Max Flow in Undirected Graphs, and its Multicommodity Generalizations (2013, methodology): “1, we follow as similar approach as the spectral sparsifcation algorithm of Spielman and Teng [25] and partition the input graph into vertex sets,”
Differentially-Private Multi-Party Sketching for Large-Scale Statistics (2020, background): “The sparsifiers of [12, 63, 64, 10] are not linear and do not appear to be mergeable.”
A Note on Over-Smoothing for Graph Neural Networks (2020, unknown): “Novel techniques in (Lee & Sun, 2017; Spielman & Srivastava, 2011; Spielman & Teng, 2004; 2011) may be applicable.”