Document Open Access Logo

Density Independent Algorithms for Sparsifying k-Step Random Walks

Authors Gorav Jindal, Pavel Kolev, Richard Peng, Saurabh Sawlani

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2017.14.pdf
  • Filesize: 0.55 MB
  • 17 pages

Document Identifiers

Author Details

Gorav Jindal
Pavel Kolev
Richard Peng
Saurabh Sawlani

Cite As Get BibTex

Gorav Jindal, Pavel Kolev, Richard Peng, and Saurabh Sawlani. Density Independent Algorithms for Sparsifying k-Step Random Walks. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 81, pp. 14:1-14:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2017.14

Abstract

We give faster algorithms for producing sparse approximations of the transition matrices of k-step random walks on undirected and weighted graphs. These transition matrices also form graphs, and arise as intermediate objects in a variety of graph algorithms. Our improvements are based on a better understanding of processes that sample such walks, as well as tighter bounds on key weights underlying these sampling processes. On a graph with n vertices and m edges, our algorithm produces a graph with about nlog(n) edges that approximates the k-step random walk graph in about m + k^2 nlog^4(n) time. In order to obtain this runtime bound, we also revisit "density independent" algorithms for sparsifying graphs whose runtime overhead is expressed only in terms of the number of vertices.

Subject Classification

Keywords
  • random walks
  • graph sparsification
  • spectral graph theory
  • effective resistances

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Ittai Abraham, David Durfee, Ioannis Koutis, Sebastian Krinninger, and Richard Peng. On fully dynamic graph sparsifiers. In Foundations of Computer Science (FOCS), 2016 IEEE 57th Annual Symposium on, pages 335-344. IEEE, 2016. Available at: URL: http://arxiv.org/abs/1604.02094.
  2. Ittai Abraham and Ofer Neiman. Using petal-decompositions to build a low stretch spanning tree. In Proceedings of the forty-fourth annual ACM symposium on Theory of computing, pages 395-406. ACM, 2012. Available at: URL: https://www.microsoft.com/en-us/research/wp-content/uploads/2012/01/spanning-full1.pdf.
  3. Sayan Bhattacharya, Monika Henzinger, and Giuseppe F Italiano. Deterministic fully dynamic data structures for vertex cover and matching. In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 785-804. SIAM, 2014. Available at: URL: https://arxiv.org/abs/1412.1318.
  4. Andreas Björklund, Rasmus Pagh, Virginia Vassilevska Williams, and Uri Zwick. Listing triangles. In International Colloquium on Automata, Languages, and Programming, pages 223-234. Springer, 2014. Google Scholar
  5. A. Borodin and I. Munro. The computational complexity of algebraic and numeric problems. American Elsevier Pub. Co New York, 1975. Google Scholar
  6. Karl Bringmann and Konstantinos Panagiotou. Efficient sampling methods for discrete distributions. In Artur Czumaj, Kurt Mehlhorn, Andrew Pitts, and Roger Wattenhofer, editors, Automata, Languages, and Programming: 39th International Colloquium, ICALP 2012, Warwick, UK, July 9-13, 2012, Proceedings, Part I, pages 133-144. Springer Berlin Heidelberg, Berlin, Heidelberg, 2012. URL: http://dx.doi.org/10.1007/978-3-642-31594-7_12.
  7. Dehua Cheng, Yu Cheng, Yan Liu, Richard Peng, and Shang-Hua Teng. Efficient sampling for Gaussian graphical models via spectral sparsification. Proceedings of The 28th Conference on Learning Theory, pages 364-390, 2015. Available at URL: http://jmlr.org/proceedings/papers/v40/Cheng15.pdf.
  8. Yu Cheng and Dehua Cheng. Personal Communication, 2016. Google Scholar
  9. Michael B. Cohen, Yin Tat Lee, Cameron Musco, Christopher Musco, Richard Peng, and Aaron Sidford. Uniform sampling for matrix approximation. In Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science, ITCS'15, pages 181-190, New York, NY, USA, 2015. ACM. URL: http://dx.doi.org/10.1145/2688073.2688113.
  10. Michael B. Cohen, Gary L. Miller, Jakub W. Pachocki, Richard Peng, and Shen Chen Xu. Stretching stretch. arXiv preprint arXiv:1401.2454, 2014. Available at: URL: https://arxiv.org/abs/1401.2454.
  11. Michael B. Cohen, Cameron Musco, and Christopher Musco. Input sparsity time low-rank approximation via ridge leverage score sampling. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January 16-19, pages 1758-1777, 2017. URL: http://dx.doi.org/10.1137/1.9781611974782.115.
  12. Peter G. Doyle and J. Laurie Snell. Random Walks and Electric Networks, volume 22 of Carus Mathematical Monographs. Mathematical Association of America, 1984. Available at: URL: https://arxiv.org/abs/math/0001057.
  13. David Durfee, Rasmus Kyng, John Peebles, Anup B. Rao, and Sushant Sachdeva. Sampling random spanning trees faster than matrix multiplication. CoRR, abs/1611.07451, 2016. Available at: URL: http://arxiv.org/abs/1611.07451.
  14. David Durfee, John Peebles, Richard Peng, and Anup B. Rao. Determinant-preserving sparsification of SDDM matrices with applications to counting and sampling spanning trees. CoRR, abs/1705.00985, 2017. URL: http://arxiv.org/abs/1705.00985.
  15. Michael L. Fredman and Robert Endre Tarjan. Fibonacci heaps and their uses in improved network optimization algorithms. J. ACM, 34:596-615, July 1987. Google Scholar
  16. Andrew V. Goldberg and Robert E. Tarjan. Efficient maximum flow algorithms. Communications of the ACM, 57(8):82-89, 2014. Available at: URL: http://cacm.acm.org/magazines/2014/8/177011-efficient-maximum-flow-algorithms/fulltext.
  17. Gramoz Goranci, Monika Henzinger, and Mikkel Thorup. Incremental exact min-cut in poly-logarithmic amortized update time. In Piotr Sankowski and Christos D. Zaroliagis, editors, 24th Annual European Symposium on Algorithms, ESA 2016, August 22-24, 2016, Aarhus, Denmark, volume 57 of LIPIcs, pages 46:1-46:17. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016. Full version available at: https://arxiv.org/abs/1611.06500. URL: http://dx.doi.org/10.4230/LIPIcs.ESA.2016.46.
  18. Manoj Gupta and Richard Peng. Fully dynamic (1+ e)-approximate matchings. In 54th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2013, 26-29 October, 2013, Berkeley, CA, USA, pages 548-557, 2013. URL: http://dx.doi.org/10.1109/FOCS.2013.65.
  19. Dov Harel and Robert Endre Tarjan. Fast algorithms for finding nearest common ancestors. siam Journal on Computing, 13(2):338-355, 1984. Google Scholar
  20. Nick Harvey. Matrix concentration and sparsification. Workshop on "Randomized Numerical Linear Algebra (RandNLA): Theory and Practice", 2012. Available at: URL: http://www.drineas.org/RandNLA/slides/Harvey_RandNLA@FOCS_2012.pdf.
  21. Monika Henzinger, Sebastian Krinninger, and Danupon Nanongkai. Sublinear-time decremental algorithms for single-source reachability and shortest paths on directed graphs. In Proceedings of the Forty-sixth Annual ACM Symposium on Theory of Computing, STOC'14, pages 674-683, 2014. Available at: URL: https://arxiv.org/abs/1504.07959.
  22. Gorav Jindal and Pavel Kolev. Faster spectral sparsification of laplacian and SDDM matrix polynomials. CoRR, abs/1507.07497, 2015. Available at: URL: http://arxiv.org/abs/1507.07497.
  23. Michael Kapralov and Rina Panigrahy. Spectral sparsification via random spanners. In Proceedings of the 3rd Innovations in Theoretical Computer Science Conference, pages 393-398. ACM, 2012. Available at: URL: https://www.microsoft.com/en-us/research/wp-content/uploads/2012/01/sig-alternate.pdf.
  24. Donald E. Knuth. The Art of Computer Programming, Volume 2 (3rd Ed.): Seminumerical Algorithms. Addison-Wesley Longman Publishing Co., Inc., Boston, MA, USA, 1997. Google Scholar
  25. Ioannis Koutis. Simple parallel and distributed algorithms for spectral graph sparsification. In Proceedings of the 26th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA'14, pages 61-66, New York, NY, USA, 2014. ACM. Available at: http://arxiv.org/abs/1402.3851. URL: http://dx.doi.org/10.1145/2612669.2612676.
  26. Ioannis Koutis, Alex Levin, and Richard Peng. Faster spectral sparsification and numerical algorithms for SDD matrices. ACM Trans. Algorithms, 12(2):17:1-17:16, December 2015. Google Scholar
  27. Rasmus Kyng, Yin Tat Lee, Richard Peng, Sushant Sachdeva, and Daniel A. Spielman. Sparsified cholesky and multigrid solvers for connection laplacians. In Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, pages 842-850. ACM, 2016. Available at URL: http://arxiv.org/abs/1512.01892.
  28. Rasmus Kyng, Jakub Pachocki, Richard Peng, and Sushant Sachdeva. A framework for analyzing resparsification algorithms. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA'17, pages 2032-2043, Philadelphia, PA, USA, 2017. Society for Industrial and Applied Mathematics. Available at: URL: https://arxiv.org/abs/1611.06940.
  29. Rasmus Kyng and Sushant Sachdeva. Approximate gaussian elimination for laplacians-fast, sparse, and simple. In Foundations of Computer Science (FOCS), 2016 IEEE 57th Annual Symposium on, pages 573-582. IEEE, 2016. Available at: URL: https://arxiv.org/abs/1605.02353.
  30. László Lovász. Random walks on graphs: A survey, 1993. Available at: URL: http://www.cs.elte.hu/~lovasz/erdos.pdf.
  31. Rasmus Pagh and Charalampos E. Tsourakakis. Colorful triangle counting and a mapreduce implementation. Information Processing Letters, 112(7):277-281, 2012. Google Scholar
  32. Richard Peng and Daniel A. Spielman. An efficient parallel solver for SDD linear systems. In Proceedings of the 46th Annual ACM Symposium on Theory of Computing, STOC'14, pages 333-342, New York, NY, USA, 2014. ACM. Available at URL: http://arxiv.org/abs/1311.3286.
  33. Franco P. Preparata and Michael I. Shamos. Computational Geometry: An Introduction. Springer-Verlag New York, Inc., New York, NY, USA, 1985. Google Scholar
  34. Christian Sommer. Shortest-path queries in static networks. ACM Computing Surveys (CSUR), 46(4):45, 2014. Available at: URL: http://www.shortestpaths.com/spq-survey.pdf.
  35. D. Spielman and N. Srivastava. Graph sparsification by effective resistances. SIAM Journal on Computing, 40(6):1913-1926, 2011. URL: http://dx.doi.org/10.1137/080734029.
  36. Daniel A. Spielman. Lecture notes on graphs and networks, October 2007. Available at: URL: http://www.cs.yale.edu/homes/spielman/462/2007/lect9-07.pdf.
  37. Joel A. Tropp. User-friendly tail bounds for sums of random matrices. Found. Comput. Math., 12(4):389-434, August 2012. URL: http://dx.doi.org/10.1007/s10208-011-9099-z.
  38. Charalampos E. Tsourakakis. Fast counting of triangles in large real networks without counting: Algorithms and laws. In Data Mining, 2008. ICDM'08. Eighth IEEE International Conference on, pages 608-617. IEEE, 2008. Available at URL: http://people.seas.harvard.edu/~babis/tsourICDM08.pdf.
  39. A. J. Walker. New fast method for generating discrete random numbers with arbitrary frequency distributions. Electronics Letters, 10(8):127-128, April 1974. URL: http://dx.doi.org/10.1049/el:19740097.
  40. David P. Woodruff et al. Sketching as a tool for numerical linear algebra. Foundations and Trendsregistered in Theoretical Computer Science, 10(1-2):1-157, 2014. Available at: URL: http://researcher.watson.ibm.com/researcher/files/us-dpwoodru/journal.pdf.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact