Document Open Access Logo

Approximation of the Diagonal of a Laplacian’s Pseudoinverse for Complex Network Analysis

Authors Eugenio Angriman , Maria Predari , Alexander van der Grinten , Henning Meyerhenke

PDF
Thumbnail PDF

File

LIPIcs.ESA.2020.6.pdf
  • Filesize: 0.71 MB
  • 24 pages

Document Identifiers

Author Details

Eugenio Angriman
  • Department of Computer Science, Humboldt-Universität zu Berlin, Germany
Maria Predari
  • Department of Computer Science, Humboldt-Universität zu Berlin, Germany
Alexander van der Grinten
  • Department of Computer Science, Humboldt-Universität zu Berlin, Germany
Henning Meyerhenke
  • Department of Computer Science, Humboldt-Universität zu Berlin, Germany

Funding

This work is partially supported by German Research Foundation (DFG) grant ME 3619/3-2 within Priority Programme 1736 Algorithms for Big Data and by DFG grant ME 3619/4-1 (Accelerating Matrix Computations for Mining Large Dynamic Complex Networks).

Acknowledgements

We thank our colleague Fabian Brandt-Tumescheit for his technical support for the experiments.

Cite AsGet BibTex

Eugenio Angriman, Maria Predari, Alexander van der Grinten, and Henning Meyerhenke. Approximation of the Diagonal of a Laplacian’s Pseudoinverse for Complex Network Analysis. In 28th Annual European Symposium on Algorithms (ESA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 173, pp. 6:1-6:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.ESA.2020.6

Abstract

The ubiquity of massive graph data sets in numerous applications requires fast algorithms for extracting knowledge from these data. We are motivated here by three electrical measures for the analysis of large small-world graphs G = (V, E) - i. e., graphs with diameter in O(log |V|), which are abundant in complex network analysis. From a computational point of view, the three measures have in common that their crucial component is the diagonal of the graph Laplacian’s pseudoinverse, L^+. Computing diag(L^+) exactly by pseudoinversion, however, is as expensive as dense matrix multiplication - and the standard tools in practice even require cubic time. Moreover, the pseudoinverse requires quadratic space - hardly feasible for large graphs. Resorting to approximation by, e. g., using the Johnson-Lindenstrauss transform, requires the solution of O(log |V| / ε²) Laplacian linear systems to guarantee a relative error, which is still very expensive for large inputs. In this paper, we present a novel approximation algorithm that requires the solution of only one Laplacian linear system. The remaining parts are purely combinatorial - mainly sampling uniform spanning trees, which we relate to diag(L^+) via effective resistances. For small-world networks, our algorithm obtains a ± ε-approximation with high probability, in a time that is nearly-linear in |E| and quadratic in 1 / ε. Another positive aspect of our algorithm is its parallel nature due to independent sampling. We thus provide two parallel implementations of our algorithm: one using OpenMP, one MPI + OpenMP. In our experiments against the state of the art, our algorithm (i) yields more accurate approximation results for diag(L^+), (ii) is much faster and more memory-efficient, and (iii) obtains good parallel speedups, in particular in the distributed setting.

Subject Classification

ACM Subject Classification
  • Theory of computation → Approximation algorithms analysis
  • Theory of computation → Graph algorithms analysis
  • Theory of computation → Parallel algorithms
  • Mathematics of computing → Solvers
Keywords
  • Laplacian pseudoinverse
  • electrical centrality measures
  • uniform spanning tree
  • effective resistance
  • parallel sampling

Metrics

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

Related Versions

References

  1. David J. Aldous. The random walk construction of uniform spanning trees and uniform labelled trees. SIAM J. Discret. Math., 3(4):450–465, November 1990. URL: https://doi.org/10.1137/0403039.
  2. Vedat Levi Alev, Nima Anari, Lap Chi Lau, and Shayan Oveis Gharan. Graph clustering using effective resistance. In Anna R. Karlin, editor, 9th Innovations in Theoretical Computer Science Conference, ITCS 2018, January 11-14, 2018, Cambridge, MA, USA, volume 94 of LIPIcs, pages 41:1-41:16, Cambridge, Massachusetts, USA, 2018. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik. URL: https://doi.org/10.4230/LIPIcs.ITCS.2018.41.
  3. Patrick Amestoy, Iain S. Duff, Jean-Yves L'Excellent, and François-Henry Rouet. Parallel computation of entries of a^-1. SIAM J. Scientific Computing, 37(2):C268-C284, 2015. URL: https://doi.org/10.1137/120902616.
  4. Eugenio Angriman, Maria Predari, Alexander van der Grinten, and Henning Meyerhenke. Approximation of the diagonal of a laplacian’s pseudoinverse for complex network analysis, 2020. URL: http://arxiv.org/abs/2006.13679.
  5. Eugenio Angriman, Alexander van der Grinten, Moritz von Looz, Henning Meyerhenke, Martin Nöllenburg, Maria Predari, and Charilaos Tzovas. Guidelines for experimental algorithmics: A case study in network analysis. Algorithms, 12(7):127, 2019. Google Scholar
  6. Haim Avron and Sivan Toledo. Randomized algorithms for estimating the trace of an implicit symmetric positive semi-definite matrix. J. ACM, 58(2):8:1-8:34, 2011. URL: https://doi.org/10.1145/1944345.1944349.
  7. David A Bader, Guojing Cong, and John Feo. On the architectural requirements for efficient execution of graph algorithms. In 2005 International Conference on Parallel Processing (ICPP'05), pages 547-556, Oslo, Norway, 2005. IEEE, IEEE. Google Scholar
  8. Simon Barthelmé, Nicolas Tremblay, Alexandre Gaudillière, Luca Avena, and Pierre-Olivier Amblard. Estimating the inverse trace using random forests on graphs, 2019. URL: http://arxiv.org/abs/1905.02086.
  9. C. Bekas, E. Kokiopoulou, and Y. Saad. An estimator for the diagonal of a matrix. Appl. Numer. Math., 57(11-12):1214-1229, November 2007. URL: https://doi.org/10.1016/j.apnum.2007.01.003.
  10. Elisabetta Bergamini, Michele Borassi, Pierluigi Crescenzi, Andrea Marino, and Henning Meyerhenke. Computing top-k closeness centrality faster in unweighted graphs. TKDD, 13(5):53:1-53:40, 2019. URL: https://doi.org/10.1145/3344719.
  11. Elisabetta Bergamini, Michael Wegner, Dimitar Lukarski, and Henning Meyerhenke. Estimating current-flow closeness centrality with a multigrid laplacian solver. In Proc. 7th SIAM Workshop on Combinatorial Scientific Computing, CSC 2016, pages 1-12. SIAM, 2016. URL: https://doi.org/10.1137/1.9781611974690.ch1.
  12. Guy E. Blelloch, Anupam Gupta, Ioannis Koutis, Gary L. Miller, Richard Peng, and Kanat Tangwongsan. Near linear-work parallel sdd solvers, low-diameter decomposition, and low-stretch subgraphs, 2011. URL: https://doi.org/10.1145/1989493.1989496.
  13. Paolo Boldi and Sebastiano Vigna. Axioms for centrality. Internet Mathematics, 10(3-4):222-262, 2014. URL: https://doi.org/10.1080/15427951.2013.865686.
  14. Béla Bollobás. Modern Graph Theory, volume 184 of Graduate Texts in Mathematics. Springer, 2002. URL: https://doi.org/10.1007/978-1-4612-0619-4.
  15. Enrico Bozzo and Massimo Franceschet. Resistance distance, closeness, and betweenness. Social Networks, 35(3):460-469, 2013. URL: https://doi.org/10.1016/j.socnet.2013.05.003.
  16. Ulrik Brandes and Daniel Fleischer. Centrality measures based on current flow. In Proceedings of the 22nd Annual Symposium on Theoretical Aspects of Computer Science, STACS 2005, volume 3404 of LNCS, pages 533-544. Springer, 2005. URL: https://doi.org/10.1007/978-3-540-31856-9_44.
  17. A. Broder. Generating random spanning trees. In Proceedings of the 30th Annual Symposium on Foundations of Computer Science, SFCS ’89, page 442–447, USA, 1989. IEEE Computer Society. URL: https://doi.org/10.1109/SFCS.1989.63516.
  18. Ashok K Chandra, Prabhakar Raghavan, Walter L Ruzzo, Roman Smolensky, and Prasoon Tiwari. The electrical resistance of a graph captures its commute and cover times. Computational Complexity, 6(4):312-340, 1996. Google Scholar
  19. Michael B. Cohen, Rasmus Kyng, Gary L. Miller, Jakub W. Pachocki, Richard Peng, Anup B. Rao, and Shen Chen Xu. Solving sdd linear systems in nearly mlog1/2n time. In Proceedings of the Forty-Sixth Annual ACM Symposium on Theory of Computing, STOC ’14, page 343–352, New York, NY, USA, 2014. Association for Computing Machinery. URL: https://doi.org/10.1145/2591796.2591833.
  20. Wendy Ellens, Flora Spieksma, P. Mieghem, A. Jamakovic, and Robert Kooij. Effective graph resistance. Linear Algebra and its Applications, 435:2491-2506, November 2011. URL: https://doi.org/10.1016/j.laa.2011.02.024.
  21. Josh Ericson, Pietro Poggi-Corradini, and Hainan Zhang. Effective resistance on graphs and the epidemic quasimetric. Involve, a Journal of Mathematics, 7(1):97-124, 2013. Google Scholar
  22. Hutchinson M. F. A stochastic estimator of the trace of the influence matrix for laplacian smoothing splines. J. Commun. Statist. Simula., 19(2):433-450, 1990. Google Scholar
  23. Arpita Ghosh, Stephen Boyd, and Amin Saberi. Minimizing effective resistance of a graph. SIAM Rev., 50(1):37-66, February 2008. URL: https://doi.org/10.1137/050645452.
  24. Chris Godsil and Gordon F Royle. Algebraic graph theory, volume 207. Springer Science & Business Media, 2013. Google Scholar
  25. Gene H. Golub and Charles F. Van Loan. Matrix computations. Johns Hopkins University Press, 1996. Google Scholar
  26. Gaël Guennebaud, Benoît Jacob, et al. Eigen v3, 2010. URL: http://eigen.tuxfamily.org.
  27. Takanori Hayashi, Takuya Akiba, and Yuichi Yoshida. Efficient algorithms for spanning tree centrality. In IJCAI, pages 3733-3739. IJCAI, 2016. Google Scholar
  28. Mathias Jacquelin, Lin Lin, and Chao Yang. Pselinv – a distributed memory parallel algorithm for selected inversion: The non-symmetric case. Parallel Computing, 74:84-98, 2018. Parallel Matrix Algorithms and Applications (PMAA'16). URL: https://doi.org/10.1016/j.parco.2017.11.009.
  29. William B Johnson and Joram Lindenstrauss. Extensions of lipschitz mappings into a hilbert space. Contemporary mathematics, 26(189-206):1, 1984. Google Scholar
  30. Jonathan A Kelner, Lorenzo Orecchia, Aaron Sidford, and Zeyuan Allen Zhu. A simple, combinatorial algorithm for solving sdd systems in nearly-linear time. In Proceedings of the forty-fifth annual ACM symposium on Theory of computing, pages 911-920. ACM, 2013. Google Scholar
  31. Douglas Klein and Milan Randic. Resistance distance. Journal of Mathematical Chemistry, 12:81-95, December 1993. URL: https://doi.org/10.1007/BF01164627.
  32. Ioannis Koutis, Gary L. Miller, and Richard Peng. A nearly-m log n time solver for SDD linear systems. In Rafail Ostrovsky, editor, IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS 2011, Palm Springs, CA, USA, October 22-25, 2011, pages 590-598. IEEE Computer Society, 2011. URL: https://doi.org/10.1109/FOCS.2011.85.
  33. Ioannis Koutis, Gary L. Miller, and Richard Peng. Approaching optimality for solving SDD linear systems. SIAM J. Comput., 43(1):337-354, 2014. URL: https://doi.org/10.1137/110845914.
  34. Ioannis Koutis, Gary L. Miller, and David Tolliver. Combinatorial preconditioners and multilevel solvers for problems in computer vision and image processing. Computer Vision and Image Understanding, 115(12):1638-1646, 2011. Google Scholar
  35. Jérôme Kunegis. KONECT: the koblenz network collection. In Leslie Carr, Alberto H. F. Laender, Bernadette Farias Lóscio, Irwin King, Marcus Fontoura, Denny Vrandecic, Lora Aroyo, José Palazzo M. de Oliveira, Fernanda Lima, and Erik Wilde, editors, 22nd International World Wide Web Conference, WWW '13, Rio de Janeiro, Brazil, May 13-17, 2013, Companion Volume, pages 1343-1350. International World Wide Web Conferences Steering Committee / ACM, 2013. URL: https://doi.org/10.1145/2487788.2488173.
  36. R. Kyng and S. Sachdeva. Approximate gaussian elimination for laplacians - fast, sparse, and simple. In 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS), pages 573-582. IEEE, October 2016. URL: https://doi.org/10.1109/FOCS.2016.68.
  37. 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 Forty-Eighth Annual ACM Symposium on Theory of Computing, STOC ’16, page 842–850, New York, NY, USA, 2016. Association for Computing Machinery. URL: https://doi.org/10.1145/2897518.2897640.
  38. Huan Li, Richard Peng, Liren Shan, Yuhao Yi, and Zhongzhi Zhang. Current flow group closeness centrality for complex networks? In Ling Liu, Ryen W. White, Amin Mantrach, Fabrizio Silvestri, Julian J. McAuley, Ricardo Baeza-Yates, and Leila Zia, editors, The World Wide Web Conference, WWW 2019, San Francisco, CA, USA, May 13-17, 2019, pages 961-971. ACM, 2019. URL: https://doi.org/10.1145/3308558.3313490.
  39. Huan Li and Zhongzhi Zhang. Kirchhoff index as a measure of edge centrality in weighted networks: Nearly linear time algorithms. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 2377-2396. SIAM, SIAM, 2018. Google Scholar
  40. Oren E Livne and Achi Brandt. Lean algebraic multigrid (LAMG): Fast graph laplacian linear solver. SIAM Journal on Scientific Computing, 34(4):B499-B522, 2012. Google Scholar
  41. L. Lovász. Random walks on graphs: A survey. In D. Miklós, V. T. Sós, and T. Szőnyi, editors, Combinatorics, Paul Erdős is Eighty, volume 2, pages 353-398. János Bolyai Mathematical Society, Budapest, 1996. Google Scholar
  42. Andrew Lumsdaine, Douglas Gregor, Bruce Hendrickson, and Jonathan Berry. Challenges in parallel graph processing. Parallel Processing Letters, 17(01):5-20, 2007. Google Scholar
  43. Russell Lyons and Yuval Peres. Probability on Trees and Networks. Cambridge University Press, USA, 1st edition, 2017. Google Scholar
  44. Clémence Magnien, Matthieu Latapy, and Michel Habib. Fast computation of empirically tight bounds for the diameter of massive graphs. Journal of Experimental Algorithmics (JEA), 13:1-10, 2009. Google Scholar
  45. Charalampos Mavroforakis, Richard Garcia-Lebron, Ioannis Koutis, and Evimaria Terzi. Spanning Edge Centrality: Large-scale Computation and Applications. In Proceedings of the 24th International Conference on World Wide Web, WWW 2015, pages 732-742. ACM, 2015. Google Scholar
  46. Brendan D McKay et al. Practical graph isomorphism. Department of Computer Science, Vanderbilt University Tennessee, USA, 1981. Google Scholar
  47. Onuttom Narayan and Iraj Saniee. Scaling of random walk betweenness in networks. In Luca Maria Aiello, Chantal Cherifi, Hocine Cherifi, Renaud Lambiotte, Pietro Lió, and Luis M. Rocha, editors, Complex Networks and Their Applications VII, pages 41-51, Cham, 2019. Springer International Publishing. Google Scholar
  48. Mark Newman. Networks (2nd Ed.). Oxford university press, 2018. Google Scholar
  49. Kazuya Okamoto, Wei Chen, and Xiang-Yang Li. Ranking of closeness centrality for large-scale social networks. In International workshop on frontiers in algorithmics, pages 186-195. Springer, Springer, 2008. Google Scholar
  50. Melissa E. O'Neill. Pcg: A family of simple fast space-efficient statistically good algorithms for random number generation. Technical Report HMC-CS-2014-0905, Harvey Mudd College, Claremont, CA, September 2014. Google Scholar
  51. Richard Peng and Daniel A. Spielman. An efficient parallel solver for sdd linear systems, 2014. URL: https://doi.org/10.1145/2591796.2591832.
  52. Gyan Ranjan, Zhi-Li Zhang, and Daniel Boley. Incremental computation of pseudo-inverse of laplacian. In Zhao Zhang, Lidong Wu, Wen Xu, and Ding-Zhu Du, editors, Combinatorial Optimization and Applications, pages 729-749, Cham, 2014. Springer International Publishing. Google Scholar
  53. Aaron Schild. An almost-linear time algorithm for uniform random spanning tree generation. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, page 214–227, New York, NY, USA, 2018. Association for Computing Machinery. URL: https://doi.org/10.1145/3188745.3188852.
  54. John Shawe-Taylor and Nello Cristianini. Kernel Methods for Pattern Analysis. Cambridge University Press, USA, 2004. Google Scholar
  55. Jack Sherman and Winifred J. Morrison. Adjustment of an inverse matrix corresponding to a change in one element of a given matrix. Ann. Math. Statist., 21(1):124-127, March 1950. Google Scholar
  56. Roger B. Sidje and Yousef Saad. Rational approximation to the fermi-dirac function with applications in density functional theory. Numerical Algorithms, 56(3):455-479, March 2011. URL: https://doi.org/10.1007/s11075-010-9397-6.
  57. Daniel A. Spielman and Nikhil Srivastava. Graph sparsification by effective resistances. SIAM Journal on Computing, 40(6):1913-1926, 2011. URL: https://doi.org/10.1137/080734029.
  58. Christian L. Staudt, Aleksejs Sazonovs, and Henning Meyerhenke. Networkit: A tool suite for large-scale complex network analysis. Network Science, 4(4):508-530, 2016. URL: https://doi.org/10.1017/nws.2016.20.
  59. Jok M. Tang and Yousef Saad. A probing method for computing the diagonal of a matrix inverse. Numerical Linear Algebra with Applications, 19(3):485-501, 2012. Google Scholar
  60. Piet Van Mieghem, Karel Devriendt, and H Cetinay. Pseudoinverse of the laplacian and best spreader node in a network. Physical Review E, 96(3):032311, 2017. Google Scholar
  61. Moritz von Looz, Mustafa Safa Özdayi, Sören Laue, and Henning Meyerhenke. Generating massive complex networks with hyperbolic geometry faster in practice. In 2016 IEEE High Performance Extreme Computing Conference, HPEC 2016, Waltham, MA, USA, September 13-15, 2016, pages 1-6. IEEE, 2016. URL: https://doi.org/10.1109/HPEC.2016.7761644.
  62. David Bruce Wilson. Generating random spanning trees more quickly than the cover time. In Proceedings of the Twenty-eighth Annual ACM Symposium on Theory of Computing, STOC '96, pages 296-303, New York, NY, USA, 1996. ACM. URL: https://doi.org/10.1145/237814.237880.
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 Imprint Privacy Contact