Almost-Linear-Time Algorithms for Markov Chains and New Spectral Primitives for Directed Graphs

2016/11/02 by Michael B. Cohen, Cohen, Michael B., Jonathan Kelner +12 · 6 citations
Computer Science · Mathematics · #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Graph theory and applications #Markov Chains and Monte Carlo Methods #Matrix Theory and Algorithms #cs.DS

paper · pdf · doi:10.48550/arxiv.1611.00755

arxiv created 2016/11/02 · openalex publication_date 2016/11/02 · arxiv updated 2016/11/03 · openalex created_date 2022/10/04 · openalex updated_date 2026/07/28

Abstract

In this paper we introduce a notion of spectral approximation for directed graphs. While there are many potential ways one might define approximation for directed graphs, most of them are too strong to allow sparse approximations in general. In contrast, we prove that for our notion of approximation, such sparsifiers do exist, and we show how to compute them in almost linear time. Using this notion of approximation, we provide a general framework for solving asymmetric linear systems that is broadly inspired by the work of [Peng-Spielman, STOC`14]. Applying this framework in conjunction with our sparsification algorithm, we obtain an almost linear time algorithm for solving directed Laplacian systems associated with Eulerian Graphs. Using this solver in the recent framework of [Cohen-Kelner-Peebles-Peng-Sidford-Vladu, FOCS`16], we obtain almost linear time algorithms for solving a directed Laplacian linear system, computing the stationary distribution of a Markov chain, computing expected commute times in a directed graph, and more. For each of these problems, our algorithms improves the previous best running times of O((nm^3/4 + n^2/3 m) log^O(1) (n κε^-1)) to O((m + n2^O(√lognloglogn)) log^O(1) (n κε^-1)) where n is the number of vertices in the graph, m is the number of edges, κ is a natural condition number associated with the problem, and ε is the desired accuracy. We hope these results open the door for further studies into directed spectral graph theory, and will serve as a stepping stone for designing a new generation of fast algorithms for directed graphs.

Cited by

• HyperEF 2.0: Spectral Hypergraph Coarsening via Krylov Subspace Expansion and Resistance-based Local Clustering
• On Solving Asymmetric Diagonally Dominant Linear Systems in Sublinear Time
• Online Sparsification of Bipartite-Like Clusters in Graphs
• Fully Dynamic Spectral and Cut Sparsifiers for Directed Graphs
• Approaching Optimality for Solving Dense Linear Systems with Low-Rank Structure
• Estimating Random-Walk Probabilities in Directed Graphs

Related

• Faster Algorithms for Computing the Stationary Distribution, Simulating Random Walks, and More
• Solving Directed Laplacian Systems in Nearly-Linear Time through Sparse LU Factorizations
• Derandomizing Directed Random Walks in Almost-Linear Time
• Singular Value Approximation and Sparsifying Random Walks on Directed Graphs
• Better Sparsifiers for Directed Eulerian Graphs