Spectral Sparsification of Hypergraphs

Abstract

For an undirected/directed hypergraph $G=(V,E)$, its Laplacian $L_G:{\mathbb{R}}^V\to {\mathbb{R}}^V$ is defined such that its ``quadratic form'' ${\mathbf{x}}^{\top }{L}_G(\mathbf{x})$ captures the cut information of $G$. In particular, $1_S^{\top }{L}_G(1_S)$ coincides with the cut size of $S\subseteq V$, where $1_S\in {\mathbb{R}}^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 $\epsilon$-spectral sparsifier of $G$ if $(1-\epsilon ){\mathbf{x}}^{\top }{L}_H(\mathbf{x})\le {\mathbf{x}}^{\top }{L}_G(\mathbf{x})\le (1+\epsilon ){\mathbf{x}}^{\top }{L}_H(\mathbf{x})$ holds for every $\mathbf{x}\in {\mathbb{R}}^V$. In this paper, we present a polynomial-time algorithm that, given an undirected/directed hypergraph $G$ on $n$ vertices, constructs an $\epsilon$-spectral sparsifier of $G$ with $O(n^3\log n/{\epsilon }^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 $L_G$, computing the effective resistance between a pair of vertices in $G$, semi-supervised learning based on $L_G$, and cut problems on $G$. In addition, our sparsification result implies that any submodular function $f:2^V\to {\mathbb{R}}_{+}$ with $f(\varnothing )=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 $f:2^V\to [0,1]$ with $f(\varnothing )=f(V)=0$, with $O(n^4\log (n/\epsilon )/{\epsilon }^4)$ samples.