sparsifier

A sparsifier is a sparser representation of a graph or matrix that approximately preserves selected properties of the original object. The concept is central in graph theory and numerical linear algebra. Sparsifiers are used to reduce size and complexity while enabling accurate computation for many algorithms, such as those that rely on cut values, eigenvalues, or quadratic forms.

Common types include cut sparsifiers, which preserve all cut values within a factor (1±ε), and spectral sparsifiers, which preserve the Laplacian quadratic form and thereby approximate eigenvalues and effective resistances. More generally, matrix sparsifiers aim to approximate positive semidefinite forms of the original matrix.

Construction methods typically involve sampling or reweighting edges according to measures of their importance. For spectral sparsification, edge sampling is guided by effective resistance; for cut sparsification, by edge connectivity. Theoretical results show that one can obtain a sparsifier with O(n log n / ε^2) edges for graphs with n vertices, with high probability, and that in some cases near-linear-time algorithms can produce such objects. In practice, sparsifiers are often constructed to balance accuracy with sparsity to fit computational budgets.

Applications span speeding up solvers for large sparse linear systems, accelerating graph algorithms, and enabling scalable machine learning on large networks. They serve as preconditioners, enabling faster convergence of iterative methods, while preserving essential structural properties.

Limitations include the probabilistic nature of many constructions, the need to choose error parameters, and the possibility of losing properties not targeted for preservation. The construction cost may be substantial for very large graphs, although it is often amortized over repeated queries on the same object.

See also: graph sparsification; spectral sparsifier; cut sparsifier.