Graph Sparsification, Spectral Sketches, and Faster Resistance Computation, via Short Cycle Decompositions
Graph Sparsification, Spectral Sketches, and Faster Resistance Computation, via Short Cycle Decompositions
复制标题
DOI：
10.1109/focs.2018.00042
复制
发表时间：
2018-05
期刊：
影响因子：
--
通讯作者：
T. Chu;Yu Gao;Richard Peng;Sushant Sachdeva;Saurabh Sawlani;Junxing Wang
中科院分区：
文献类型：
--
作者：
T. Chu;Yu Gao;Richard Peng;Sushant Sachdeva;Saurabh Sawlani;Junxing Wang
我们开发了一个基于新工具的图稀疏化框架，图的短周期分解-将图分解为短周期的集合，加上少量额外的边。一个简单的观察表明，在n个顶点上有m条边的每个图G可以在O（mn）时间内分解成最长为2 log n的循环，最多有2n个额外的边。我们给出了一个m1+o(1)时间算法来构造图的短周期分解，周期长度为n^o(1)，并且有n^1+o(1)个额外边。这种分解的存在变体和算法变体使我们能够在随机图算法中的几个开放问题上取得进展。1. 我们提出了一种算法，该算法运行时间为m^1+o(1)ε^-1.5，并返回所有边的有效阻力的（1±ε）近似，改进了之前的最佳算法Õ（min{mε^-2, n^2 ε^-1}）。这给出了一种算法，可以近似图拉普拉斯行列式的因子（1±ε），大致为m + n^15/8 ε^-7/4。2. 我们证明了构造图形谱草图的存在性和有效算法-一个具有约nε^-1条边的稀疏图H上的分布，使得对于一个固定向量x，我们有x^T L_H x =(1±eps) x^T L_G x和x^T L+_H x =(1±ε) x^T L+_G x具有高概率，其中L是图的拉普拉斯算子，L+是它的伪逆。这意味着具有约nε边的电阻稀疏器可以在每对顶点之间保持高达（1 + eps）的有效电阻。3. 通过将短周期分解与重要采样相结合，我们证明了近线性大小的度保持谱稀疏器的存在，以及有向图的显着稀疏逼近。后者对于近期有向随机漫步快速算法和有向拉普拉斯线性系统的突破至关重要。我们的谱草图和度保持（定向）稀疏化算法的运行时间和输出质量受到我们产生短周期分解的例程的效率的限制。短周期分解的改进算法将导致这些算法的改进。
We develop a framework for graph sparsification based on a new tool, short cycle decomposition for graphs – a decomposition of a graph into a collection of short cycles, plus a small number of extra edges. A simple observation gives that every graph G on n vertices with m edges can be decomposed in O(mn) time into cycles of length at most 2 log n, and at most 2n extra edges. We give an m1+o(1) time algorithm for constructing a short cycle decomposition of the graph, with cycles of length n^o(1), and n^1+o(1) extra edges. Both the existential and algorithmic variants of this decomposition enable us to make progress on several open problems in randomized graph algorithms. 1. We present an algorithm that runs in time m^1+o(1)ε^-1.5 and returns (1 ± ε)-approximations to effective resistances of all edges, improving over the previous best of Õ(min{mε^-2, n^2 ε^-1}) This gives an algorithm to approximate the determinant of a graph Laplacian up to a factor of (1 ± ε) in roughly m + n^15/8 ε^-7/4. 2. We show existence and efficient algorithms for constructing graphical spectral sketches – a distribution over sparse graphs H with about nε^-1 edges such that for a fixed vector x, we have x^T L_H x = (1 ± eps) x^T L_G x and x^T L+_H x = (1 ± ε) x^T L+_G x with high probability, where L is the graph Laplacian and L+ is its pseudoinverse. This implies resistance-sparsifiers with about nε edges that preserve the effective resistances between every pair of vertices up to (1 + eps). 3. By combining short cycle decomposition with importance sampling, we show the existence of nearly-linear sized degree-preserving spectral sparsifiers, as well as significantly sparser approximations of directed graphs. The latter is critical to recent breakthroughs on faster algorithms for directed random walks and linear systems in directed Laplacian. The running time and output qualities of our spectral sketch and degree-preserving (directed) sparsification algorithms are limited by the efficiency of our routines for producing short cycle decompositions. Improved algorithms for short cycle decompositions will lead to improvements for each of these algorithms.