diGRASS: Directed Graph Spectral Sparsification via Spectrum-Preserving Symmetrization
diGRASS: Directed Graph Spectral Sparsification via Spectrum-Preserving Symmetrization
复制标题
DOI：
10.1145/3639568
复制
发表时间：
2024-01
影响因子：
3.6
通讯作者：
Ying Zhang;Zhiqiang Zhao;Zhuo Feng
中科院分区：
文献类型：
--
作者：
Ying Zhang;Zhiqiang Zhao;Zhuo Feng
最近的谱图稀疏化研究旨在构造超稀疏子图以保留原始图的谱（结构）属性，例如前几个拉普拉斯特征值和特征向量，这导致了各种近线性时间数值和图算法的发展。然而，有向图谱稀疏化的进展非常有限。在这项工作中，我们证明了在某些条件下有向图存在近线性大小的谱稀疏器。此外，我们引入了一种实用高效的谱算法（diGRASS），利用谱矩阵扰动分析来稀疏化现实世界的大规模有向图。所提出的方法已使用从实际应用中获得的各种有向图进行了评估，显示了解决有向图拉普拉斯算子、有向图的谱划分以及近似计算（个性化）PageRank 向量的有希望的结果。
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.