Singular Value Approximation and Sparsifying Random Walks on Directed Graphs

In this paper, we introduce a new, spectral notion of approximation between directed graphs, which we call singular value (SV) approximation. SV-approximation is stronger than previous notions of spectral approximation considered in the literature, including spectral approximation of Laplacians for undirected graphs [ST04], standard approximation for directed graphs [CKP + 17], and unit-circle (UC) approximation for directed graphs [AKM + 20]. Further, SV approximation enjoys several useful properties not possessed by previous notions of approximation, e. g. , it is preserved under products of randomwalk matrices and bounded matrices. We provide a nearly linear-time algorithm for SV-sparsifying (and hence UC-sparsifying) Eulerian directed graphs, as well as $\ell$-step random walks on such graphs, for any $\ell \leq \operatorname{poly}(n)$. Combined with the Eulerian scaling algorithms of [CKK + 18], given an arbitrary (not necessarily Eulerian) directed graph and a set S of vertices, we can approximate the stationary probability mass of the $\left(S, S^{c}\right)$ cut in an $\ell$-step random walk to within a multiplicative error of $1 / \operatorname{polylog}(n)$ and an additive error of $1 / \operatorname{poly}(n)$ in nearly linear time. As a starting point for these results, we provide a simple black-box reduction from SV-sparsifying Eulerian directed graphs to SV-sparsifying undirected graphs; such a directed-to-undirected reduction was not known for previous notions of spectral approximation.

Authors

• AmirMahdi Ahmadinejad
• John Peebles
• Edward Pyne
• Aaron Sidford
• Salil P. Vadhan

Keywords

• Computer science
• Laplace equations
• Additives
• Directed graphs
• Closed box
• Approximation algorithms
• Standards
• Random Walk
• Singular Value
• Directed Graph
• Undirected
• Linear Time
• Unit Circle
• Spectral Estimation
• Square Root
• Authoritarian
• Geometric Mean
• Eigenvectors
• Stationary Distribution
• Edge Weights
• Quality Estimation
• Laplacian Matrix
• Positive Semidefinite
• Power-of-two
• Degree Matrix
• Self-loops
• Side Of Inequality
• Right-hand Side Of Inequality
• Root Of Unity
• Back Edge
• Sparse Algorithm
• Original Graph
• Asymmetric Matrix
• Left Singular Vectors
• graph algorithms