Spectral Sparsification of Graphs

Abstract

We introduce a new notion of graph sparsificaiton 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 $\softO{m}$, where $m$ is the number of edges in the original graph. This construction is a key component of a nearly-linear time algorithm for solving linear equations in diagonally-dominant matrcies. 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.

This revision addresses comments of the referees. In particular, we have completely re-written the proof of the main graph partitioning theorem in section 8

References in corpus (2)

• Nearly-Linear Time Algorithms for Preconditioning and Solving Symmetric, Diagonally Dominant Linear Systems
• A Local Clustering Algorithm for Massive Graphs and its Application to Nearly-Linear Time Graph Partitioning

Cited by in corpus (7)

• Single pass sparsification in the streaming model with edge deletions
• Effective Resistances, Statistical Leverage, and Applications to Linear Equation Solving
• Information Graph Flow: a geometric approximation of quantum and statistical systems
• Graph Sparsification by Edge-Connectivity and Random Spanning Trees
• Finite Volume Spaces and Sparsification
• LSP : Acceleration and Regularization of Graph Neural Networks via Locality Sensitive Pruning of Graphs
• Edge sampling using network local information