Computing the diffusion state distance on graphs via algebraic multigrid and random projections. Issue 3 (7th February 2018)

• Record Type: Journal Article
• Authors: Lin, Junyuan; Cowen, Lenore J.; Hescott, Benjamin; Hu, Xiaozhe
• Other Names: Dendy Joel E. guestEditor.
• Is Part Of: Numerical linear algebra with applications. Volume 25:Issue 3(2018)
• Page Start: n/a
• Page End: n/a
• Publication Date: 2018-02-07
• Subjects: algebraic multigrid -- diffusion state distance -- random projections; Algebras, Linear -- Periodicals; 512.5
• DOI: 10.1002/nla.2156
• Languages: English
• ISSNs: 1070-5325

Abstract

Summary: In this paper, we consider efficient and robust algorithms for computing the diffusion state distance (DSD) metric on graphs developed recently. In order to efficiently compute DSD, we reformulate the problem into graph Laplacians and use unsmoothed aggregation algebraic multigrid to solve the resulting linear system of equations. To further reduce the computational cost, we approximate DSD by using random projections based on the Johnson–Lindenstrauss lemma. Numerical results for real‐world protein–protein interaction networks are presented to demonstrate the efficiency and robustness of the proposed new approaches.