# Spectral Sparsification of Hypergraphs

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 13 Jul 2018.

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

- [Partial recovery and weak consistency in the non-uniform hypergraph Stochastic Block Model](https://mlsanity.com/paper/2112.11671/) (2021)
- [HyperEF: Spectral Hypergraph Coarsening by Effective-Resistance Clustering](https://mlsanity.com/paper/2210.14813/) (2022)
- [HyperSF: Spectral Hypergraph Coarsening via Flow-based Local Clustering](https://mlsanity.com/paper/2108.07901/) (2021)
- [Sparsification of Decomposable Submodular Functions](https://mlsanity.com/paper/2201.07289/) (2022)
- [Benchmarking graph construction by large language models for coherence-driven inference](https://mlsanity.com/paper/2502.13953/) (2025)
- [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)
- [Efficient Sparsification of Simplicial Complexes via Local Densities of States](https://mlsanity.com/paper/2502.07558/) (2025)
- [Coherence-driven inference for cybersecurity](https://mlsanity.com/paper/2509.18520/) (2025)
- [Automatic coherence-driven inference on arguments](https://mlsanity.com/paper/2509.18523/) (2025)

## Abstract (arXiv)

For an undirected/directed hypergraph G=(V,E), its Laplacian LGcolonℝV→ ℝV is defined such that its ``quadratic form'' boldsymbolx^top LG(boldsymbolx) captures the cut information of G. In particular, boldsymbol1S^top LG(boldsymbol1S) coincides with the cut size of S subseteq V, where boldsymbol1S ∈ ℝV is the characteristic vector of S. A weighted subgraph H of a hypergraph G on a vertex set V is said to be an ε-spectral sparsifier of G if (1-ε)boldsymbolx^top LH(boldsymbolx) ≤ boldsymbolx^top LG(boldsymbolx) ≤ (1+ε)boldsymbolx^top LH(boldsymbolx) holds for every boldsymbolx ∈ ℝV. In this paper, we present a polynomial-time algorithm that, given an undirected/directed hypergraph G on n vertices, constructs an ε-spectral sparsifier of G with O(n3log n/ε2) hyperedges/hyperarcs. The proposed spectral sparsification can be used to improve the time and space complexities of algorithms for solving problems that involve the quadratic form, such as computing the eigenvalues of LG, computing the effective resistance between a pair of vertices in G, semi-supervised learning based on LG, and cut problems on G. In addition, our sparsification result implies that any submodular function fcolon 2V → ℝ_+ with f(emptyset)=f(V)=0 can be concisely represented by a directed hypergraph. Accordingly, we show that, for any distribution, we can properly and agnostically learn submodular functions fcolon 2V → [0,1] with f(emptyset)=f(V)=0, with O(n4log (n/ε) /ε4) samples.