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

DOI10.1137/19M1247632arXiv1805.12051OpenAlexW3034963086MaRDI QIDQ6139829FDOQ6139829

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)

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.

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)

Cites Work

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

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)