Spectral Sparsification of Hypergraphs

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.