Spectral Hypergraph Sparsifiers of Nearly Linear Size
Spectral Hypergraph Sparsifiers of Nearly Linear Size
复制标题
近线性尺寸的谱超图稀疏器
DOI：
10.1109/focs52979.2021.00114
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Yoshida Yuichi
中科院分区：
文献类型：
--
作者：
Kapralov Michael;Krauthgamer Robert;Tardos Jakab;Yoshida Yuichi
在过去的二十年里，图形稀疏化已经得到了广泛的研究，最终得到了最佳尺寸的光谱稀疏化器（达到常数因子）。谱超图稀疏化是这个问题的自然模拟，对于这个问题，稀疏化器大小的最佳边界是未知的，主要是因为超图拉普拉斯算子是非线性的，因此缺乏对图非常有效的线性代数结构和工具。我们的主要贡献是为具有超边的超图构建光谱稀疏化器的第一个算法，其中抑制了因子。这个边界独立于秩（超边缘的最大基数），并且由于最近的超图稀疏化的位复杂度下界，本质上是最好的。这一结果是通过引入两个新工具得到的。首先，我们给出了图稀疏子的谱集中界的一个新的证明；它避免了线性代数方法，取代了例如矩阵Bernstein不等式的通常应用，因此适用于（非线性）超图设置。为了达到这个结果，我们在单位球上设计了一个新的超图依赖网络序列。其次，我们将Chen， Khanna和Nagda [FOCS'20]的权重分配技术扩展到光谱稀疏化设置。令人惊讶的是，权值分配后生成树的数量可以作为指导谱设置中重权过程的潜在函数。
Graph sparsification has been studied extensively over the past two decades, culminating in spectral sparsifiers of optimal size (up to constant factors). Spectral hypergraph sparsification is a natural analogue of this problem, for which optimal bounds on the sparsifier size are not known, mainly because the hypergraph Laplacian is non-linear, and thus lacks the linear-algebraic structure and tools that have been so effective for graphs. Our main contribution is the first algorithm for constructing-spectral sparsifiers for hypergraphs withhyperedges, wheresuppressesfactors. This bound is independent of the rank(maximum cardinality of a hyperedge), and is essentially best possible due to a recent bit complexity lower bound offor hypergraph sparsification. This result is obtained by introducing two new tools. First, we give a new proof of spectral concentration bounds for sparsifiers of graphs; it avoids linear-algebraic methods, replacing e.g. the usual application of the matrix Bernstein inequality and therefore applies to the (non-linear) hypergraph setting. To achieve the result, we design a new sequence of hypergraph-dependent-nets on the unit sphere in. Second, we extend the weight-assignment technique of Chen, Khanna and Nagda [FOCS'20] to the spectral sparsification setting. Surprisingly, the number of spanning trees after the weight assignment can serve as a potential function guiding the reweighting process in the spectral setting.