# Towards Tight Bounds for Spectral Sparsification of Hypergraphs

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 12 Nov 2020.

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

- [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)
- [SHyPar: A Spectral Coarsening Approach to Hypergraph Partitioning](https://mlsanity.com/paper/2410.10875/) (2024)
- [Sparsifying Suprema of Gaussian Processes](https://mlsanity.com/paper/2411.14664/) (2024)

## Abstract (arXiv)

Cut and spectral sparsification of graphs have numerous applications, including e.g. speeding up algorithms for cuts and Laplacian solvers. These powerful notions have recently been extended to hypergraphs, which are much richer and may offer new applications. However, the current bounds on the size of hypergraph sparsifiers are not as tight as the corresponding bounds for graphs. Our first result is a polynomial-time algorithm that, given a hypergraph on n vertices with maximum hyperedge size r, outputs an ε-spectral sparsifier with O^*(nr) hyperedges, where O^* suppresses (ε-1 log n)O(1) factors. This size bound improves the two previous bounds: O^*(n3) [Soma and Yoshida, SODA'19] and O^*(nr3) [Bansal, Svensson and Trevisan, FOCS'19]. Our main technical tool is a new method for proving concentration of the nonlinear analogue of the quadratic form of the Laplacians for hypergraph expanders. We complement this with lower bounds on the bit complexity of any compression scheme that (1+ε)-approximates all the cuts in a given hypergraph, and hence also on the bit complexity of every ε-cut/spectral sparsifier. These lower bounds are based on Ruzsa-Szemer'edi graphs, and a particular instantiation yields an Omega(nr) lower bound on the bit complexity even for fixed constant ε. This is tight up to polylogarithmic factors in n, due to recent hypergraph cut sparsifiers of [Chen, Khanna and Nagda, FOCS'20]. Finally, for directed hypergraphs, we present an algorithm that computes an ε-spectral sparsifier with O^*(n2r3) hyperarcs, where r is the maximum size of a hyperarc. For small r, this improves over O^*(n3) known from [Soma and Yoshida, SODA'19], and is getting close to the trivial lower bound of Omega(n2) hyperarcs.