Almost-linear-time algorithms for Markov chains and new spectral primitives for directed graphs
In this paper, we begin to address the longstanding algorithmic gap between general and reversible Markov chains. We develop directed analogues of several spectral graph-the oretic tools that had previously been available only in the undirected setting, and for which it was not clear that directed v...
| المؤلفون الرئيسيون: | , , , , , , |
|---|---|
| مؤلفون آخرون: | |
| التنسيق: | مقال |
| منشور في: |
Association for Computing Machinery (ACM)
2018
|
| الوصول للمادة أونلاين: | http://hdl.handle.net/1721.1/115991 https://orcid.org/0000-0002-7388-6936 https://orcid.org/0000-0002-4257-4198 https://orcid.org/0000-0002-6514-3761 https://orcid.org/0000-0003-0722-304X |
| _version_ | 1826215260425551872 |
|---|---|
| author | Peng, Richard Rao, Anup B. Sidford, Aaron Cohen, Michael B. Kelner, Jonathan Adam Peebles, John Lee Thompson Vladu, Adrian Valentin |
| author2 | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science |
| author_facet | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Peng, Richard Rao, Anup B. Sidford, Aaron Cohen, Michael B. Kelner, Jonathan Adam Peebles, John Lee Thompson Vladu, Adrian Valentin |
| author_sort | Peng, Richard |
| collection | MIT |
| description | In this paper, we begin to address the longstanding algorithmic gap between general and reversible Markov chains. We develop directed analogues of several spectral graph-the oretic tools that had previously been available only in the undirected setting, and for which it was not clear that directed versions even existed. In particular, we provide a notion of approximation for directed graphs, prove sparsifiers under this notion always exist, and show how to construct them in almost linear time. Using this notion of approximation, we design the first almost-linear-time directed Laplacian system solver, and, by leveraging the recent framework of [Cohen-Kelner-Peebles-Peng-Sidford-Vladu, FOCS'16], we also obtain almost-linear-time algorithms for computing the stationary distribution of a Markov chain, computing expected commute times in a directed graph, and more. For each problem, our algorithms improve the previous best running times of O((nm [superscript 3/4] + n[superscript 2/3]m) log[superscript O(1)] (nkϵ[superscript -1])) to O((m + n2[superscript O (√log n loglogn))] log[superscript O(1)] (nkϵ [superscript -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 that they will serve as a stepping stone for designing a new generation of fast algorithms for directed graphs. |
| first_indexed | 2024-09-23T16:20:42Z |
| format | Article |
| id | mit-1721.1/115991 |
| institution | Massachusetts Institute of Technology |
| last_indexed | 2024-09-23T16:20:42Z |
| publishDate | 2018 |
| publisher | Association for Computing Machinery (ACM) |
| record_format | dspace |
| spelling | mit-1721.1/1159912022-09-29T19:38:57Z Almost-linear-time algorithms for Markov chains and new spectral primitives for directed graphs Peng, Richard Rao, Anup B. Sidford, Aaron Cohen, Michael B. Kelner, Jonathan Adam Peebles, John Lee Thompson Vladu, Adrian Valentin Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Massachusetts Institute of Technology. Department of Mathematics Cohen, Michael B. Kelner, Jonathan Adam Peebles, John Lee Thompson Vladu, Adrian Valentin In this paper, we begin to address the longstanding algorithmic gap between general and reversible Markov chains. We develop directed analogues of several spectral graph-the oretic tools that had previously been available only in the undirected setting, and for which it was not clear that directed versions even existed. In particular, we provide a notion of approximation for directed graphs, prove sparsifiers under this notion always exist, and show how to construct them in almost linear time. Using this notion of approximation, we design the first almost-linear-time directed Laplacian system solver, and, by leveraging the recent framework of [Cohen-Kelner-Peebles-Peng-Sidford-Vladu, FOCS'16], we also obtain almost-linear-time algorithms for computing the stationary distribution of a Markov chain, computing expected commute times in a directed graph, and more. For each problem, our algorithms improve the previous best running times of O((nm [superscript 3/4] + n[superscript 2/3]m) log[superscript O(1)] (nkϵ[superscript -1])) to O((m + n2[superscript O (√log n loglogn))] log[superscript O(1)] (nkϵ [superscript -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 that they will serve as a stepping stone for designing a new generation of fast algorithms for directed graphs. 2018-05-30T18:42:43Z 2018-05-30T18:42:43Z 2017-06 2018-05-24T13:19:24Z Article http://purl.org/eprint/type/ConferencePaper 978-1-4503-4528-6 http://hdl.handle.net/1721.1/115991 Cohen, Michael B. et al. “Almost-Linear-Time Algorithms for Markov Chains and New Spectral Primitives for Directed Graphs.” Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing - STOC 2017 (2017), 19-23 June, 2017, Montreal, Canada, Association for Computing Machinery, 2017. https://orcid.org/0000-0002-7388-6936 https://orcid.org/0000-0002-4257-4198 https://orcid.org/0000-0002-6514-3761 https://orcid.org/0000-0003-0722-304X http://dx.doi.org/10.1145/3055399.3055463 Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing - STOC 2017 Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Association for Computing Machinery (ACM) arXiv |
| spellingShingle | Peng, Richard Rao, Anup B. Sidford, Aaron Cohen, Michael B. Kelner, Jonathan Adam Peebles, John Lee Thompson Vladu, Adrian Valentin Almost-linear-time algorithms for Markov chains and new spectral primitives for directed graphs |
| title | Almost-linear-time algorithms for Markov chains and new spectral primitives for directed graphs |
| title_full | Almost-linear-time algorithms for Markov chains and new spectral primitives for directed graphs |
| title_fullStr | Almost-linear-time algorithms for Markov chains and new spectral primitives for directed graphs |
| title_full_unstemmed | Almost-linear-time algorithms for Markov chains and new spectral primitives for directed graphs |
| title_short | Almost-linear-time algorithms for Markov chains and new spectral primitives for directed graphs |
| title_sort | almost linear time algorithms for markov chains and new spectral primitives for directed graphs |
| url | http://hdl.handle.net/1721.1/115991 https://orcid.org/0000-0002-7388-6936 https://orcid.org/0000-0002-4257-4198 https://orcid.org/0000-0002-6514-3761 https://orcid.org/0000-0003-0722-304X |
| work_keys_str_mv | AT pengrichard almostlineartimealgorithmsformarkovchainsandnewspectralprimitivesfordirectedgraphs AT raoanupb almostlineartimealgorithmsformarkovchainsandnewspectralprimitivesfordirectedgraphs AT sidfordaaron almostlineartimealgorithmsformarkovchainsandnewspectralprimitivesfordirectedgraphs AT cohenmichaelb almostlineartimealgorithmsformarkovchainsandnewspectralprimitivesfordirectedgraphs AT kelnerjonathanadam almostlineartimealgorithmsformarkovchainsandnewspectralprimitivesfordirectedgraphs AT peeblesjohnleethompson almostlineartimealgorithmsformarkovchainsandnewspectralprimitivesfordirectedgraphs AT vladuadrianvalentin almostlineartimealgorithmsformarkovchainsandnewspectralprimitivesfordirectedgraphs |