Graph Sparsification, Spectral Sketches, and Faster Resistance Computation via Short Cycle Decompositions

DOI10.1137/19M1247632MaRDI QIDQ6139829zbMATH OpenOpenAlexFDO

Authors Timothy Chu, Yu Gao, Richard Peng, Sushant Sachdeva, Saurabh Sawlani, Junxing Wang

Publication date 19 December 2023

Published in SIAM Journal on Computing (Search for Journal in Brave)

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

zbMATH Keywords

spectral sparsificationeffective resistancegraph sketchingdegree-preserving sparsifiersEulerian sparsifiersresistance sparsifiers

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Abstract: We develop a framework for graph sparsification and sketching, based on a new tool, short cycle decomposition -- a decomposition of an unweighted graph into an edge-disjoint collection of short cycles, plus few 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 $2logn$, and at most $2n$ extra edges. We give an $m^{1+o(1)}$ time algorithm for constructing a short cycle decomposition, with cycles of length $n^{o(1)}$, and $n^{1+o(1)}$ extra edges. These decompositions enable us to make progress on several open questions: * We give an algorithm to find $(1pmepsilon)$-approximations to effective resistances of all edges in time $m^{1+o(1)}epsilo{n}^{-1.5}$, improving over the previous best of $ildeO(minmepsilo{n}^{-2},n^{2}epsilo{n}^{-1})$. This gives an algorithm to approximate the determinant of a Laplacian up to $(1pmepsilon)$ in $m^{1+o(1)}+n^{15/8+o(1)}epsilo{n}^{-7/4}$ time. * We show existence and efficient algorithms for constructing graphical spectral sketches -- a distribution over sparse graphs H such that for a fixed vector $x$, we have w.h.p. $x^{\prime }{L}_{H}x=(1pmepsilon)x^{\prime }{L}_{G}x$ and $x^{\prime }{L}_H^{+}x=(1pmepsilon)x^{\prime }{L}_G^{+}x$. This implies the existence of resistance-sparsifiers with about $nepsilo{n}^{-1}$ edges that preserve the effective resistances between every pair of vertices up to $(1pmepsilon).$ * By combining short cycle decompositions with known tools in graph sparsification, 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 solving linear systems in directed Laplacians. Improved algorithms for constructing short cycle decompositions will lead to improvements for each of the above results.

Cites work

• scientific article; zbMATH DE number 5485537 (Why is no real title available?)
• scientific article; zbMATH DE number 5764910 (Why is no real title available?)
• scientific article; zbMATH DE number 1256718 (Why is no real title available?)
• scientific article; zbMATH DE number 6850349 (Why is no real title available?)
• scientific article; zbMATH DE number 878897 (Why is no real title available?)
• scientific article; zbMATH DE number 7561582 (Why is no real title available?)
• scientific article; zbMATH DE number 3061533 (Why is no real title available?)
• A Nearly-m log n Time Solver for SDD Linear Systems
• A Scheme for Fast Parallel Communication
• A framework for analyzing resparsification algorithms
• Almost-linear-time algorithms for Markov chains and new spectral primitives for directed graphs
• An SDP-based algorithm for linear-sized spectral sparsification
• An almost-linear-time algorithm for approximate max flow in undirected graphs, and its multicommodity generalizations
• An efficient parallel solver for SDD linear systems
• Approaching optimality for solving SDD linear systems
• Approximate undirected maximum flows in \(O(m\operatorname{polylog}(n))\) time
• Cascades and myopic routing in nonhomogeneous Kleinberg's small world model
• Computing cut-based hierarchical decompositions in almost linear time
• Concentration Inequalities and Martingale Inequalities: A Survey
• Dynamic spanning forest with worst-case update time: adaptive, Las Vegas, and \(O(n^{1/2-\epsilon})\)-time
• Efficient $\widetilde{O}(n/\epsilon)$ Spectral Sketches for the Laplacian and its Pseudoinverse
• Electric routing and concurrent flow cutting
• Electrical flows, Laplacian systems, and faster approximation of maximum flow in undirected graphs
• Expander decomposition and pruning: faster, stronger, and simpler
• Fast generation of random spanning trees and the effective resistance metric
• Fully dynamic randomized algorithms for graph spanners
• Graph sparsification by effective resistances
• Improved dynamic algorithms for maintaining approximate shortest paths under deletions
• Improved spectral sparsification and numerical algorithms for SDD matrices
• Kirchhoff index as a measure of edge centrality in weighted networks: nearly linear time algorithms
• Massively Parallel Algorithms for Finding Well-Connected Components in Sparse Graphs
• Nearly linear time algorithms for preconditioning and solving symmetric, diagonally dominant linear systems
• On sketching quadratic forms
• Optimal lower bounds for sketching graph cuts
• Ramanujan graphs
• Sampling random spanning trees faster than matrix multiplication
• Scalable Algorithms for Data and Network Analysis
• Short cycles via low-diameter decompositions
• Sparsification—a technique for speeding up dynamic graph algorithms
• Sparsified Cholesky and multigrid solvers for connection Laplacians
• Spectral sparsification and regret minimization beyond matrix multiplicative updates
• Spectral sparsification of graphs
• Spectral sparsification via random spanners
• Spectrum Approximation Beyond Fast Matrix Multiplication: Algorithms and Hardness
• The Laplacian paradigm: emerging algorithms for massive graphs
• Towards resistance sparsifiers
• Twice-Ramanujan sparsifiers
• User-friendly tail bounds for sums of random matrices
• \(\lambda_ 1\), isoperimetric inequalities for graphs, and superconcentrators

Cited in

(1)

• Random walks, conductance, and resistance for the connection graph Laplacian

This page was built for publication: Graph Sparsification, Spectral Sketches, and Faster Resistance Computation via Short Cycle Decompositions

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