Source-linked AI summary
Spectral Sparsification of Graphs
Daniel A. Spielman, Shang-Hua Teng
TL;DR
Existing sparsification notions capture distance or cut similarity, while this paper introduces spectral sparsification based on Laplacian quadratic forms. It proves nearly linear-size spectral sparsifiers exist and can be computed in nearly linear time.
Problem
Existing graph sparsification notions target distance or cut similarity, motivating a notion based on spectral similarity for numerical linear algebra and spectral graph theory.
Method
The paper defines spectral sparsifiers through Laplacian quadratic-form approximation and constructs them using graph partitioning, recursive partitioning, sampling, and graph contraction for arbitrary weights.
Results
Nearly linear-size spectral sparsifiers exist for every weighted graph and can be computed in eO(m) time, with a (1+ε) approximation using eO(n) edges.
Takeaways & Limitations
Spectral sparsification is stronger than cut sparsification and provides a graph-Laplacian preconditioning framework for efficient numerical linear algebra.
Takeaways & Limitations
The construction does not optimize the hidden logarithmic constants and powers, which are quite large; an ideal decomposition routine is also NP-hard, while an available approximate routine may take quadratic time.
Abstract
from arXiv · showhide
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.
1 Introduction
The paper introduces spectral sparsification, which preserves a graph’s Laplacian quadratic form for all real vector inputs, and proves that sparse approximations can be constructed efficiently.
- Spectral sparsification requires a subgraph’s Laplacian quadratic form to approximately match the original graph’s for all real vector inputs.This notion is motivated by numerical linear algebra and spectral graph theory.
- The spectral notion is stronger than cut sparsification because cut sparsifiers require the approximation inequalities only for vectors in {0, 1}^V.The paper gives an example showing that the two approximation notions differ.
- Every weighted graph has a spectral sparsifier with eO(n) edges that can be computed in eO(m) time.Here n = |V| and m = |E|.
- For every ǫ > 0, the construction produces a re-weighted subgraph that is a (1+ǫ) approximation of the original graph.The authors emphasize nearly-linear size and construction time rather than optimal hidden logarithmic factors.
- The algorithm uses ApproxCut, a nearly-linear-time partitioning algorithm with a high-conductance guarantee for the larger side of an unbalanced cut.With high probability, if the returned set is small, its complement lies in a subgraph of conductance at least Ω(φ^2/log^4 m).
2 The Bigger Picture
The paper connects spectral sparsifiers to preconditioning for Laplacian systems, showing how spectral approximation controls condition numbers and supports efficient iterative solving.
- The sparsification work is part of a three-paper effort on nearly-linear-time algorithms for diagonally-dominant linear systems.The first paper develops graph-partitioning routines, while the third uses sparsifiers to build preconditioners.
- A σ-spectral approximation implies a relative condition number κ(G, eG) ≤ σ^2.The condition number measures the quality of the sparsifier as a preconditioner.
- Preconditioned Conjugate Gradient can solve Laplacian systems by repeatedly solving systems in the sparsifier and multiplying by the original graph’s Laplacian.The number of sparsifier solves is O(σ log(1/ǫ)) for accuracy ǫ.
- The companion paper reduces the resulting solve time to eO(m log(1/ǫ)), where m is the number of non-zero entries in the Laplacian.This bound is nearly optimal when the Laplacian has Ω(n^2) non-zero entries.
3 Outline
The paper’s construction combines sampling with high-conductance graph decomposition, applies these tools to unweighted and weighted graphs, and concludes by surveying subsequent improvements.
- The paper motivates its construction with examples of graphs and sparsifiers that clarify key elements of the method.These examples appear in Section 5.
- The algorithm has three components: random sampling, fast partitioning into high-conductance parts, and procedures for sparsifying unweighted and weighted graphs.Sampling is analyzed for high-conductance graphs, while partitioning reduces arbitrary graphs to that setting.
- The unweighted-graph algorithm is extended to weighted graphs in Section 10.The outline separates the construction into unweighted sparsification followed by weighted sparsification.
- The paper concludes by surveying improvements to sparsification and the graph-partitioning routines on which its construction depends.These improvements are discussed in Section 11.
4 Background and Notation
The background defines spectral-approximation notation and conductance-related graph quantities used throughout the paper, including Laplacian order relations and induced subgraphs.
- The paper uses “σ-approximation” as shorthand for “σ-spectral approximation” when no confusion arises.
- The notation A ≼ B expresses the paper’s matrix inequality for comparing spectral quantities.The corresponding graph notation G ≼ eG means LG ≼ L_eG.
- Graph addition is defined by adding corresponding edge weights, so Laplacians add and spectral inequalities can be combined.The paper states that G ≼ eG and H ≼ eH imply G + H ≼ eG + eH.
- The paper preserves vertex identities in induced subgraphs so inequalities over different subgraphs can be summed for the original graph.
- For an unweighted graph, d_v denotes vertex degree, E(S,T) denotes edges between disjoint sets, and G(S) is the induced subgraph on S.
- Conductance is defined using the edge boundary of a vertex set normalized by the smaller volume of the set and its complement.The graph conductance is the minimum conductance over nonempty proper subsets.
- Conductance is related to the smallest non-zero eigenvalue of the normalized Laplacian, which the analysis connects through Cheeger’s inequality.The normalized Laplacian is formed using the diagonal degree matrix D.
5 A few examples
The examples show how weighted spectral sparsifiers preserve Laplacian behavior, combine across subgraphs, and distinguish spectral approximation from cut approximation.
- Complete graphs: Ramanujan graphs, suitably reweighted, provide sparse spectral approximations to complete graphs.The construction rescales each edge by n/d while preserving the relevant eigenvalue bounds.
- Joined complete graphs: A sparsifier for two joined complete graphs combines sparsifiers of each clique with the single connecting edge.The Laplacian-order argument combines the three component approximations.
- Joined complete graphs: Every sparsifier of the joined graph must retain the bridge edge, whereas no other edge is especially important.The example illustrates both unequal edge weights and composition of subgraph sparsifiers.
- Distinguishing cut and spectral sparsifiers: A graph differing from its cut sparsifier by one long-range edge can remain a (1 + 1/2k)-cut approximation while failing spectral approximation for small σ.The added edge creates a large quadratic-form discrepancy for a suitable vector.
6 Sampling Graphs
The section develops random edge sampling for high-conductance graphs, proving that appropriately reweighted samples preserve spectral structure with high probability.
- Sampling procedure: Sampling retains edge (i, j) with probability p_i,j and assigns it weight 1/p_i,j when selected.The procedure preserves expected edge contributions while reducing the edge set.
- Sampling procedure: Υ controls the expected sample size and is chosen at least Ω(log n) so every vertex retains an attached edge.This requirement supports connectivity-related guarantees in the sampled graph.
- Guarantee: High conductance enables the sampling method to produce a good spectral sparsifier with high probability.The theorem applies sampling to edges within a vertex subset while retaining the remaining edges.
- Guarantee: The sampled edge count is bounded by 288 max(log^2(3/p), log^2 n).This bound appears in the sampling guarantee for the sampled edge set.
- Analysis: The analysis bounds the normalized Laplacian error using matrix norms, eigenvalue moments, trace powers, and walk encodings.Nonzero contributions correspond to walks whose traversed edges appear at least twice.
7 Graph Decompositions
The section establishes graph decompositions into high-conductance components with few intercomponent edges, then explains how these decompositions support spectral sparsification.
- Decomposition: Every graph can be decomposed into high-conductance components with relatively few edges bridging the components.The decomposition is measured using vertex-induced subgraphs while volumes retain the original graph’s degrees.
- Decomposition: A φ-decomposition has component conductance at least φ, and Cheeger’s inequality makes it a (φ^2/2)-spectral decomposition.The spectral condition is stated through the smallest non-zero normalized Laplacian eigenvalue.
- Connection to sparsification: Applying the decomposition theorem reduces sparsification of arbitrary graphs to random sampling within high-conductance components.The resulting component decomposition supplies the spectral structure required by the sampling theorem.
- Algorithmic limitation: The decomposition theorem is non-algorithmic because idealDecomp requires solving an NP-hard problem.An approximate alternative could also be too slow if it takes quadratic time.
- Recursive construction: The recursive decomposition adds at most a φ fraction of edges at each level and has depth at most log_{4/3} Vol(V).Consequently, the boundary contains at most half of the original edges.
8 Approximate Sparsest Cuts
ApproxCut replaces infeasible sparsest-cut certification with a nearly-linear-time procedure whose unbalanced outputs certify high conductance in the remaining region.
- Algorithm: ApproxCut repeatedly invokes Partition through Partition2 to collect cuts until sufficient graph volume is removed or enough calls are made.The construction strengthens the underlying partitioning guarantee for low-conductance sets.
- Proof strategy: The proof constructs nested sets in stages, combining a high-conductance set U_i with surviving vertices to form W_i.At each stage, the volume outside the high-conductance set shrinks by at least a factor of 2.
- Proof strategy: If a sparse set S_i is large, ApproxCut likely returns a large cut; otherwise the constructed U_i has high conductance.The procedure therefore either satisfies the large-cut outcome or produces the desired high-conductance container.
9 Sparsifying Unweighted Graphs
UnwtedSparsify recursively partitions an unweighted graph and sparsifies selected subgraphs, combining the resulting pieces with boundary edges. Its output preserves approximation quality while reducing the edge count to a near-linear bound.
- UnwtedSparsify uses ApproxCut to partition the graph, sparsifies a high-conductance larger part after a small cut, and recurses when the cut is large.
- PartitionAndSample returns sparsified subgraphs together with the edges crossing their vertex-set partition.
- (1 + ˆǫ)1+log29/28 Vol(V) approximation is guaranteed for PartitionAndSample's output.
- c3ǫ−2 |V| log30(n/p) bounds the total number of edges in the PartitionAndSample output.
- The final UnwtedSparsify output uses only original edges, is a (1 + ǫ)-approximation, and has at most c4ǫ−2n log31(n/p) edges.
- The expected running time combines ApproxCut and sampling costs with two additional O(log n) factors from recursion and repeated partitioning.
10 Sparsifying Weighted Graphs
The section develops sparsification methods for weighted graphs, first handling bounded integral weights and then arbitrary weights through graph contraction and pullbacks. The resulting sparsifiers preserve spectral approximation while achieving nearly linear edge bounds, with an optional per-vertex blow-up guarantee.
- Bounded Weights: O(log U) extra sparsifier edges suffice when integral edge weights lie in {1, ..., U}, by decomposing weights into powers of two.Each resulting weight-1 graph is sparsified independently and the outputs are recombined.
- Bounded Weights: BoundedSparsify returns a reweighted subgraph that is a (1 + ǫ)-approximation with at most c4ǫ−2n log U log31(n/p) edges.Its edges remain a subset of the input graph's edges.
- Coping with Arbitrary Weights: Graph Contraction: Graph contraction handles arbitrary weights by contracting stronger connected components and sparsifying the lower-weight intercomponent edges through pullbacks.The method is motivated by treating much heavier edges as contracted when processing a given weight scale.
- Coping with Arbitrary Weights: Graph Contraction: The pullback analysis uses a path preconditioning inequality to relate low-weight edges to high-weight paths within and between contracted components.For a unit-weight edge, the path contributes a coefficient equal to the sum of reciprocal path-edge weights.
- Coping with Arbitrary Weights: Graph Contraction: Sparsify produces a (1 + ǫ)-approximation with at most c5ǫ−2n log33(n/p) edges in expected nearly linear time.The output edges are a subset of the input graph's edges.
- Bounding Blow-Up: Sparsify2 preserves the (1 + ǫ)-approximation using at most c6ǫ−2n log34(n/p) edges while bounding every vertex's blow-up by 2.This modifies the construction to control the total incident weight increase at each vertex.
11 Final Remarks
The authors note that subsequent work substantially improved spectral sparsification bounds and algorithms, while related graph-partitioning components were also improved. Later sparsifiers reduced edge counts and improved running-time guarantees, and newer linear-system solvers no longer relied on this construction.
- Final Remarks: Subsequent work established spectral sparsifiers with O(n log n/ǫ2) and later O(n/ǫ2) edges, improving the paper's nearly-linear-size result.The O(n log n/ǫ2) construction is available in nearly-linear time, while the O(n/ǫ2) construction uses a polynomial-time algorithm.
- Final Remarks: Koutis, Miller, and Peng developed a faster solver for Laplacian systems that does not rely on this paper's sparsifier construction.Their algorithm finds α-approximate solutions in time O(m log2 n log α−1).
- Final Remarks: Andersen and Peres improved the related partitioning algorithm by increasing speed and saving a factor of log2 m in the conductance guarantee.Their guarantee replaces the earlier f1(τ) term with O(τ 2/ log n).