# Spectral Hypergraph Sparsifiers of Nearly Linear Size

arXiv: https://arxiv.org/abs/2106.02353 · HTML: https://mlsanity.com/paper/2106.02353/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 4 Jun 2021.

## Built on by (most cited first, 5 of 5)

- [HyperEF: Spectral Hypergraph Coarsening by Effective-Resistance Clustering](https://mlsanity.com/paper/2210.14813/) (2022)
- [Sparsification of Decomposable Submodular Functions](https://mlsanity.com/paper/2201.07289/) (2022)
- [Cheeger Inequalities for Directed Graphs and Hypergraphs Using Reweighted Eigenvalues](https://mlsanity.com/paper/2211.09776/) (2022)
- [Ridge Leverage Score Sampling for ℓp Subspace Approximation](https://mlsanity.com/paper/2407.03262/) (2024)
- [SHyPar: A Spectral Coarsening Approach to Hypergraph Partitioning](https://mlsanity.com/paper/2410.10875/) (2024)

## Abstract (arXiv)

Graph sparsification has been studied extensively over the past two decades, culminating in spectral sparsifiers of optimal size (up to constant factors). Spectral hypergraph sparsification is a natural analogue of this problem, for which optimal bounds on the sparsifier size are not known, mainly because the hypergraph Laplacian is non-linear, and thus lacks the linear-algebraic structure and tools that have been so effective for graphs. Our main contribution is the first algorithm for constructing ε-spectral sparsifiers for hypergraphs with O^*(n) hyperedges, where O^* suppresses (ε-1 log n)O(1) factors. This bound is independent of the rank r (maximum cardinality of a hyperedge), and is essentially best possible due to a recent bit complexity lower bound of Omega(nr) for hypergraph sparsification. This result is obtained by introducing two new tools. First, we give a new proof of spectral concentration bounds for sparsifiers of graphs; it avoids linear-algebraic methods, replacing e.g.~the usual application of the matrix Bernstein inequality and therefore applies to the (non-linear) hypergraph setting. To achieve the result, we design a new sequence of hypergraph-dependent ε-nets on the unit sphere in ℝn. Second, we extend the weight assignment technique of Chen, Khanna and Nagda [FOCS'20] to the spectral sparsification setting. Surprisingly, the number of spanning trees after the weight assignment can serve as a potential function guiding the reweighting process in the spectral setting.