Spectral sparsification of hypergraphs

DOI10.1137/1.9781611975482.159MaRDI QIDQ5236349zbMATH OpenOpenAlexFDO

Authors Tasuku Soma, Yuichi Yoshida

Publication date 15 October 2019

Published in Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1807.04974

zbMATH Keywords

\(\varepsilon\)-spectral sparsifiersubmodular function

Mathematics Subject Classification ID

Hypergraphs (05C65) Learning and adaptive systems in artificial intelligence (68T05)

Abstract: For an undirected/directed hypergraph $G=(V,E)$, its Laplacian $L_{G}colonmathbb{R}^{V}omathbb{R}^V$ is defined such that its ``quadratic form $$ captures the cut information of $G$. In particular, $$ coincides with the cut size of $SsubseteqV$, where $$ 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 $$ holds for every $$. 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}logn/epsilo{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 $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 $fcolon{2}^{V}omathbb{R}_{+}$ 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{2}^{V}o[0,1]$ with $f(emptyset)=f(V)=0$, with $O(n^{4}log(n/epsilon)/epsilo{n}^4)$ samples.

Recommendations

• An SDP-based algorithm for linear-sized spectral sparsification
• Spectral sparsification of graphs
• Graph sparsification by effective resistances
• Twice-Ramanujan sparsifiers
• Spectral sparsification in the semi-streaming setting

Cited in

(21)

• Sparse topologies with small spectrum size
• L_p regular sparse hypergraphs
• Sparsification of Binary CSPs
• Sparsification of binary CSPs
• Quantum Speedup for Graph Sparsification, Cut Approximation, and Laplacian Solving
• The algebraic structure of the densification and the sparsification tasks for CSPs
• A conjecture on spectral sparsification with respect to hyperbolicity cones
• Splitting-off in hypergraphs
• Almost-tight bounds on preserving cuts in classes of submodular hypergraphs
• Cut sparsification and succinct representation of submodular hypergraphs
• Splitting-off in hypergraphs
• Partial recovery and weak consistency in the non-uniform hypergraph stochastic block model
• Vertex sparsifiers for hyperedge connectivity
• Additive sparsification of CSPs
• Online algorithms for spectral hypergraph sparsification
• Online algorithms for spectral hypergraph sparsification
• Sparsification of directed graphs via cut balance
• Sublinear time hypergraph sparsification via cut and edge sampling queries
• Hypergraph connectivity augmentation in strongly polynomial time
• A theory of spectral CSP sparsification
• Near-optimal hypergraph sparsification in insertion-only and bounded-deletion streams

This page was built for publication: Spectral sparsification of hypergraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5236349)