Back to Search
Start Over
diGRASS: Directed Graph Spectral Sparsification via Spectrum-Preserving Symmetrization.
- Source :
- ACM Transactions on Knowledge Discovery from Data; May2024, Vol. 18 Issue 4, p1-25, 25p
- Publication Year :
- 2024
-
Abstract
- Recent spectral graph sparsification research aims to construct ultra-sparse subgraphs for preserving the original graph spectral (structural) properties, such as the first few Laplacian eigenvalues and eigenvectors, which has led to the development of a variety of nearly-linear time numerical and graph algorithms. However, there is very limited progress for spectral sparsification of directed graphs. In this work, we prove the existence of nearly-linear-sized spectral sparsifiers for directed graphs under certain conditions. Furthermore, we introduce a practically-efficient spectral algorithm (diGRASS) for sparsifying real-world, large-scale directed graphs leveraging spectral matrix perturbation analysis. The proposed method has been evaluated using a variety of directed graphs obtained from real-world applications, showing promising results for solving directed graph Laplacians, spectral partitioning of directed graphs, and approximately computing (personalized) PageRank vectors. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 15564681
- Volume :
- 18
- Issue :
- 4
- Database :
- Complementary Index
- Journal :
- ACM Transactions on Knowledge Discovery from Data
- Publication Type :
- Academic Journal
- Accession number :
- 175564683
- Full Text :
- https://doi.org/10.1145/3639568